The Art of Synthetic Test Data: Building a Greedy Tree-Accept Kernel for Speculative Decoding

In the middle of constructing a native C/C++/CUDA inference engine for the Kimi K2.6 large language model, an AI assistant pauses to write a single Python file. That file, gen_accept_refs.py, is the test data generator for the third and final custom CUDA kernel in a speculative decoding pipeline known as DDTree (Draft-Tree-based speculative decoding). The message in question — message index 11885 — is a deceptively brief artifact: the assistant writes the file and announces success. But the reasoning block preceding that action reveals a fascinating microcosm of systems engineering, test design philosophy, and the careful craft of building reliable GPU software.

This article examines that single message in depth, unpacking the reasoning, assumptions, decisions, and knowledge embedded in what might otherwise appear to be a routine "write a file" step.

The Broader Mission: A Native DDTree Engine

To understand message 11885, one must first understand the project it belongs to. The assistant is building a complete native inference engine for the Kimi K2.6 model — a large language model with Multi-head Latent Attention (MLA) and Mixture-of-Experts (MoE) architecture — running on 8× NVIDIA RTX PRO 6000 Blackwell GPUs. The engine's centerpiece is a technique called DDTree (Draft-Tree speculative decoding), which accelerates inference by having a small "drafter" model propose multiple token sequences organized as a tree, which the large "target" model then verifies in parallel.

The engine is organized as three custom CUDA kernels that replace the corresponding CPU implementations in SGLang (the production inference framework):

Tree Builder (Phase 1, completed in msg 11871-11873): A GPU best-first tree builder that constructs the draft tree from the drafter's top-k predictions, replacing SGLang's per-request CPU heapq implementation.
Verify Attention (Phase 1, completed in msg 11874-11883): A custom MLA-absorb attention kernel that computes attention scores only over the tree's visible positions, using a visibility mask to enforce the tree's causal structure.
Tree Accept (Phase 1, in progress as of msg 11885): A kernel that walks the verified tree, comparing the target model's predictions against the drafted tokens to determine which tokens are accepted and what bonus token to emit. By message 11884, the first two kernels are fully validated — the tree builder passes 11 test configurations bit-exact against a numpy reference, and the verify-attention kernel passes 6 configurations with a maximum absolute error of ~2e-8 (essentially float32 precision limits). The assistant now faces a strategic decision: what to tackle next?

The Decision: Why the Tree-Accept Kernel, and Why Now?

The reasoning block in message 11884 (immediately preceding the subject message) reveals the assistant's deliberation:

"Before wrapping up, I should consider what else I can accomplish in this session that's self-contained: an end-to-end integration test chaining the tree builder output directly into the verify-attention kernel to validate their interface contract, or implementing the greedy accept logic as a kernel."

This is a classic engineering trade-off. The assistant could either (a) build an integration test that connects the two existing kernels, validating their combined behavior, or (b) implement the third kernel, completing the "trio" of DDTree operations entirely in CUDA. The assistant chooses option (b), reasoning:

"The accept step is the final piece of the greedy DDTree pipeline—it takes the target's per-node predictions and walks the verified tree to determine which tokens were accepted. This is small, testable against the Python reference, and completes the trio of build → verify-attn → accept entirely in CUDA. That's the highest-value next step."

This decision reveals several assumptions. First, the assistant assumes that completing the three-kernel trio is more valuable than integration testing at this stage — that having all three kernels implemented and individually validated creates a stronger foundation than having two kernels with a verified interface between them. Second, the assistant assumes the tree-accept kernel is "small" and "testable," implying it believes the implementation complexity is manageable within the remaining session time. Third, the assistant implicitly assumes that the interface contracts between the kernels (the data formats and memory layouts) are stable enough that individually validated kernels will compose correctly — an assumption that will later be tested by an on-device composition test.

The choice also reflects a strategic understanding of the project's phased roadmap. Phase 1 is defined as "three validated custom CUDA kernels." Completing the third kernel closes Phase 1, allowing the project to move to Phase 2 (the native engine MVP) and Phase 3 (CT200 deployment). The assistant is optimizing for milestone completion, not for integration risk reduction.

Designing the Test Data Generator

The subject message itself (msg 11885) is the execution of this decision. The assistant writes gen_accept_refs.py, a Python script that generates synthetic test data for the tree-accept kernel. The reasoning block reveals the design process in detail.

The Kernel's Inputs and Outputs

The assistant first defines the kernel's interface. The tree-accept kernel takes:

target_predict: The target model's predicted token IDs at each node of the draft tree.
node_token_ids: The token ID associated with each node in the draft tree (padded to a flat array).
next_token: For each node, the index of its first child in the flat array.
next_sibling: For each node, the index of its next sibling (forming a linked list of children).
actual_lengths: The actual (unpadded) lengths of each request's tree. And it outputs:
accepted_path: The sequence of node indices representing the accepted path through the tree.
proposed: The sequence of token IDs to be committed (the accepted tokens plus a bonus token). This interface is not arbitrary. It mirrors the data structures already established by the tree builder kernel, which uses a "first-child/next-sibling" encoding to represent the draft tree in flat arrays. The assistant is consciously reusing this encoding, ensuring interface compatibility between the two kernels. This is a design decision rooted in the earlier Phase 0 work (the KDTR binary format and the numpy reference implementations).

The Synthesis Strategy: Coverage Through Controlled Randomness

The most interesting part of the reasoning is the test data synthesis strategy:

"For target prediction synthesis, I'll use a strategy that gives good coverage: with 70% probability pick the first child if it exists, otherwise pick a random non-child token to force a stop; for leaves, always random. To also exercise non-first children, I'll occasionally sample a uniformly random child from all children of a node instead."

This is a carefully crafted strategy that balances several goals:

Long acceptance chains: By biasing 70% toward following the first child, the generator creates test cases where the kernel must walk deep into the tree, exercising the loop logic and boundary conditions at each depth.
Early stopping: By occasionally picking a random non-child token, the generator creates cases where acceptance stops early, testing the kernel's ability to detect mismatches and record the bonus token at the correct position.
Non-first-child acceptance: By occasionally sampling a uniformly random child, the generator exercises the sibling-chain traversal logic, ensuring the kernel correctly finds matching children that aren't the first in the list.
Leaf termination: By always using random tokens for leaf nodes, the generator ensures that acceptance never continues past the tree's depth, testing the kernel's termination condition. This strategy reveals a sophisticated understanding of what makes a good test suite. The assistant is not just generating random data — it's deliberately constructing edge cases and exercising specific code paths. The 70% bias creates a distribution where most test cases have non-trivial acceptance lengths, making the test more sensitive to bugs in the core traversal logic.

Test Configurations: Covering the Parameter Space

The assistant then defines test configurations that vary across multiple dimensions:

"varying batch size, depth, branching factor, and budget across different scenarios to cover default, mid-range, wide, underfull, chain, and large batch cases."

This is a systematic approach to covering the kernel's input space. The tree-accept kernel must handle:

Small batches (e.g., 1 request) and large batches (e.g., 64 requests)
Shallow trees (depth 3-4) and deep trees (depth 15)
Narrow branching (fanout 2-4) and wide branching (fanout 8-16)
Trees that fill their budget and trees that are underfull
Chain-like trees (where each node has exactly one child) Each configuration tests a different aspect of the kernel's behavior. The "chain" configuration, for example, tests whether the kernel correctly handles a degenerate tree where the sibling traversal is never needed. The "underfull" configuration tests whether the kernel correctly handles padding and incomplete trees.

Assumptions Embedded in the Design

The message contains several implicit assumptions worth examining:

Assumption 1: The sibling-chain traversal is equivalent to dictionary lookup. The assistant states: "since siblings have distinct tokens (generated from top-k selections at each depth), scanning through next_sibling pointers will find the matching token regardless of traversal order, just like the dict lookup would." This assumes that the tree builder guarantees that no two children of the same parent have the same token ID. This is a reasonable assumption given the top-k sampling process (which selects distinct tokens), but it's worth noting that the kernel's correctness depends on this invariant being maintained by the tree builder.

Assumption 2: The numpy reference implementation is correct. The assistant uses a Python/numpy implementation of follow_verified_tree as the ground truth for validation. This assumes that the reference implementation correctly captures the intended algorithm. Any bug in the reference would propagate to the kernel tests, causing either false failures (if the reference is wrong in a way that disagrees with the kernel) or false passes (if both are wrong in the same way).

Assumption 3: The test configurations are sufficient. The assistant selects a set of configurations covering the parameter space but does not exhaustively test all combinations. This assumes that the chosen configurations are representative and that bugs would manifest in at least one of them. This is a standard testing assumption, but it's worth noting that combinatorial testing (e.g., all combinations of batch size, depth, branching factor, and budget) would be more thorough at the cost of many more test cases.

Assumption 4: The kernel's behavior is deterministic. The assistant generates synthetic target predictions and computes expected outputs offline, then compares the kernel's output against these expectations. This assumes that the kernel is deterministic — that given the same inputs, it produces the same outputs every time. This is true for a well-written CUDA kernel with no undefined behavior, but it's an assumption that must be validated (e.g., by running the test multiple times).

The Knowledge Required to Understand This Message

To fully grasp message 11885, a reader needs knowledge spanning several domains:

Speculative decoding: Understanding that draft-trees allow a small model to propose multiple token sequences that a large model verifies in parallel, and that the "accept" step determines which tokens from the draft tree are kept.

CUDA kernel design: Understanding that GPU kernels operate on flat arrays with pointer-like indices (next_token, next_sibling), and that the "first-child/next-sibling" encoding is a standard way to represent trees in GPU memory.

Test data generation: Understanding the principles of synthetic test data — that random data alone is insufficient, and that deliberate bias (like the 70% follow-child probability) is needed to exercise specific code paths.

The KDTR binary format: Understanding that the test data is serialized to .kdtr files that can be read by both Python (for reference computation) and C++ (for kernel testing), enabling reproducible cross-language validation.

The project's phased roadmap: Understanding that this kernel is the third of three Phase-1 kernels, and that completing it enables the Phase 2 native engine MVP.

The Knowledge Created by This Message

Message 11885 creates several forms of knowledge:

A test data generator: The gen_accept_refs.py file itself is a reusable artifact that can generate test data for any tree-accept kernel implementation, not just the current one.

A validation strategy: The approach of synthesizing target predictions with controlled biases establishes a template for testing similar kernels in the future.

Interface documentation: By defining the exact input and output tensors for the tree-accept kernel, the message implicitly documents the kernel's interface contract, which is essential for integration with the tree builder and verify-attention kernels.

A milestone marker: The message marks the transition from planning to implementation for the third Phase-1 kernel, serving as a checkpoint in the project's progress.

The Thinking Process: A Window into Engineering Judgment

The reasoning block in message 11885 reveals a thinking process that is characteristic of experienced systems engineers. The assistant:

Assesses the current state: "Both Phase-1 kernels are validated."
Identifies options: Integration test vs. third kernel.
Evaluates each option: The third kernel is "small, testable against the Python reference, and completes the trio."
Makes a decision: "That's the highest-value next step."
Designs the solution: Defines inputs, outputs, and test strategy.
Implements: Writes the generator file. This is not a random walk — it's a structured decision process that balances completeness, risk, and session time. The assistant could have spent the remaining session on integration testing, which would reduce risk but leave the third kernel unimplemented. Instead, it chose to complete the kernel trio, accepting the integration risk in exchange for a more complete Phase 1. The message also reveals a deep understanding of the trade-offs in test design. The 70% bias toward first-child following is not arbitrary — it's a deliberate choice to maximize the likelihood of long acceptance chains, which are the most interesting (and bug-prone) part of the kernel. The occasional uniform-random child selection ensures that the sibling-chain traversal is exercised, catching bugs that would only manifest with non-first-child matches.

Conclusion

Message 11885 is a small but revealing artifact in the construction of a complex GPU inference engine. It captures the moment when an AI assistant, having validated two custom CUDA kernels, decides to complete the trio by implementing the third, and designs a test data generator that will validate it. The reasoning block shows a sophisticated understanding of kernel interfaces, test coverage, and engineering trade-offs. The decision to prioritize kernel completion over integration testing reflects a strategic judgment about milestone progress versus risk reduction.

The file gen_accept_refs.py may be just a few hundred lines of Python, but it encodes hours of reasoning about tree structures, sibling traversal, coverage strategies, and the delicate art of making random data actually useful for testing. It is a testament to the fact that in systems engineering, the test infrastructure is often as important as the code it tests — and that a well-designed test generator is worth its weight in debugged kernels.