The Composition Test: Validating the Greedy DDTree Step Trio on Device

A Single Bash Command That Confirms a Major Milestone

In the course of building a native C/C++/CUDA speculative decoding engine for the Kimi K2.6 language model, a single bash command executed at message index 11905 represents the culmination of an intense, multi-step engineering effort. The message is deceptively simple — it runs a build-and-test script and reports the tail of the output:

[assistant] [bash] cd /home/theuser/glm-kimi-sm120-rtx6000bw/kdtree-engine
bash scripts/build_and_test.sh 2>&1 | tail -12
      Start 24: greedy_step_step_batch16
24/27 Test #24: greedy_step_step_batch16 .........   Passed    0.25 sec
      Start 25: greedy_step_step_default
25/27 Test #25: greedy_step_step_default .........   Passed    0.22 sec
      Start 26: greedy_step_step_mid
26/27 Test #26: greedy_step_step_mid .............   Passed    0.25 sec
      Start 27: greedy_step_step_wide
27/27 Test #27: greedy_step_step_wide ............   Passed    0.25 sec

100% tests passed, 0 tests failed out of 27

Four new tests — greedy_step_step_batch16, greedy_step_step_default, greedy_step_step_mid, and greedy_step_step_wide — have joined the suite, and all 27 tests now pass. This message is not merely a status report; it is the validation of a critical architectural invariant that the entire speculative decoding engine depends upon.

Why This Message Was Written

The message exists because of a deliberate, reasoned decision made by the assistant in the preceding message ([msg 11900]). After completing and committing the three individual DDTree kernels — the GPU best-first tree builder, the MLA-absorb tree-verify attention kernel, and the greedy tree-accept kernel — the assistant faced a fork in the road. The remaining work split into two major tracks: integrating the kernels into the SGLang inference server on production hardware, or building out the full native C++ engine with weight loading and distributed inference. Both tracks were substantial multi-day efforts requiring the actual model and hardware to validate against.

Rather than proceeding blindly down either path, the assistant paused to consider what could be accomplished in the current session that was self-contained and high-value. Several options were weighed: creating a Python ctypes binding layer for clean SGLang integration, scaffolding the Phase 2 engine's KV cache manager and decode loop interfaces, writing a detailed integration specification document, or building an end-to-end composition test that chains the kernels together on consistent data. The assistant recognized that the composition test was "the highest-value move" because it "directly de-risks integration and is fully testable locally."

This reasoning reveals a disciplined engineering mindset: before committing to a complex integration effort, validate that the components actually compose correctly at the device-buffer level. The composition test is the bridge between "individual kernels pass their unit tests" and "the engine can rely on these kernels working together." The message at index 11905 is the moment that bridge is crossed.

The Technical Challenge of Composition Testing

The composition test is not trivial. The assistant identified a key constraint during the planning phase: verify_attn produces attention output, not target token predictions. To chain all three kernels end-to-end — tree_build → verify_attn → tree_accept — one would need the full target language model with its lm_head to generate argmax predictions from the attention output. Without the model loaded, a pure-kernel composition test cannot complete the full chain.

The assistant's solution was elegant and pragmatic. Instead of testing the full chain, the composition test validates that tree_build's outputs (node IDs, visibility masks, next_token and next_sibling pointers) feed correctly into tree_accept entirely on-device, without any host round-trip of the tree structure. This is precisely the buffer contract the engine will rely on during speculative decoding: the GPU builds the draft tree, the GPU verifies it (with attention), and the GPU accepts or rejects tokens — all without copying intermediate data back to the host.

The test works as follows: it runs the GPU tree builder, then synthesizes a target_predict array (simulating what the language model head would produce), and feeds this directly into the tree-accept kernel on the GPU. The outputs are compared against a numpy reference computed from the same tree-building inputs. Because the tree builder is bit-exact with its reference implementation, the numpy reference is guaranteed to match — and the test confirms that the device-buffer pipeline preserves this correctness.

What This Message Reveals About the Engineering Process

The message at index 11905 is the output of a bash command, but it encodes deep information about the state of the project. The test names themselves tell a story: greedy_step_step_batch16 tests the composition with a batch of 16 requests, exercising the kernel's ability to handle multiple concurrent speculative decoding streams. greedy_step_step_default, greedy_step_step_mid, and greedy_step_step_wide test different tree configurations — varying depth, branching factor, and budget — to ensure the composition works across the full range of tree shapes that the engine will encounter in production.

The jump from 23 tests (after the individual kernel tests were added in [msg 11894]) to 27 tests reflects the addition of these four composition tests plus the reference data generators. The fact that all 27 pass with execution times around 0.22–0.25 seconds per test indicates that the kernels are not only correct but also efficient — the composition adds negligible overhead beyond the individual kernel launches.

Assumptions and Their Validation

The assistant made several assumptions in designing this composition test. First, that the device-buffer contract between tree_build and tree_accept is stable and well-defined — that the node IDs, sibling pointers, and visibility masks produced by the builder are consumed correctly by the acceptor without reinterpretation. Second, that the numpy reference is a trustworthy oracle for the combined pipeline, which depends on the tree builder being bit-exact (already proven in earlier tests). Third, that testing with synthetic target_predict data is sufficient to validate the composition, even though real inference would use the model's logits.

These assumptions are reasonable and the passing tests validate them. The composition test does not, however, test the full tree_build → verify_attn → tree_accept chain with real attention output — that requires the full model and is left as a future validation step when the engine is integrated with SGLang on production hardware. The assistant explicitly acknowledged this limitation in its reasoning, showing clear understanding of the test's scope and boundaries.

Input and Output Knowledge

To understand this message, one must grasp the DDTree speculative decoding algorithm, where a small "drafter" model proposes a tree of candidate tokens and the large "target" model verifies them in parallel. The three kernels implement the critical path: building the draft tree from the drafter's logprobs, computing attention over the tree with a visibility mask, and greedily accepting the longest prefix that matches the target's predictions. One must also understand CUDA kernel launch patterns, device memory management, and the CMake/ctest build infrastructure.

The message produces crucial knowledge: the composition test passes, confirming that the device-buffer pipeline is correct. This unblocks the next phase of work — whether that is SGLang integration or native engine development — because the risk of subtle buffer-mismatch bugs between kernels has been eliminated. The project can proceed with confidence that the three kernels compose correctly on the GPU.

The Broader Significance

This message represents a natural checkpoint in a complex engineering effort. The assistant had completed Phase 0 (build infrastructure, reference implementations, binary container format) and Phase 1 (three individual CUDA kernels with 23 unit tests). The composition test at message 11905 is the capstone of Phase 1 — it proves that the kernels work together as a coherent pipeline, not just in isolation. The 100% pass rate across 27 tests is the green light for the next phase.

The disciplined approach — pause, evaluate options, choose the highest-value self-contained task, execute, validate — is a model of how to manage complex, multi-stage engineering projects in an interactive coding session. Rather than rushing toward the finish line, the assistant invested in validation infrastructure that de-risks everything that follows. The bash command at message 11905 is the sound of that investment paying off.