First Light: Validating the DDTree Reference Pipeline

In the long arc of building a native C/C++/CUDA inference engine for Kimi K2.6's speculative decoding drafter, there comes a quiet but critical moment when the scaffolding is complete and the first real computation runs. Message [msg 11859] captures exactly that moment: the assistant generates reference test data bundles and verifies that the entire Phase 0 data pipeline works end-to-end before a single CUDA kernel is written.

The Context: Building from Scratch

The assistant had just created a new repository called kdtree-engine/ ([msg 11851]) and laid down the foundational infrastructure across several messages. A plan document was saved to plans/0001-ccuda-ddtree-engine-plan.md ([msg 11852]). A custom binary container format called KDTR was invented, with both a Python writer (python/kdtr_io.py, [msg 11855]) and a C++ header-only reader (src/common/kdtr_io.h, [msg 11856]). A faithful numpy reference implementation of the DDTree tree-building algorithm was ported from SGLang's build_ddtree_tree_from_topk into python/ddtree_ref.py ([msg 11857]). And finally, a test-data generator script python/gen_tree_build_refs.py was written to produce random inputs, run them through the reference, and bundle inputs and expected outputs together into KDTR files ([msg 11858]).

All of this was preparation. Message [msg 11859] is where the preparation meets reality.

What the Message Actually Does

The message consists of two commands executed in sequence. First, the assistant runs the test-data generator:

cd /home/theuser/glm-kimi-sm120-rtx6000bw/kdtree-engine
python3 python/gen_tree_build_refs.py 2>&1

This script generates random top_log_probs and top_token_ids arrays across multiple configurations, feeds them through the numpy reference implementation, and writes the inputs and expected outputs to .kdtr files in tests/refs/. The output shows four files were produced:

tree_build_default.kdtr — B=6, D=7, K=4, budget=8, q_len=9, actual=[9,9]
tree_build_mid.kdtr — B=4, D=7, K=4, budget=16, q_len=17, actual=[17,17]
tree_build_wide.kdtr — B=4, D=7, K=8, budget=32, q_len=33, actual=[33,33]
A fourth file whose output is truncated in the conversation The second command is a Python heredoc that loads the first file (tree_build_default.kdtr) and prints its contents to verify the round-trip. The output shows the file's keys (meta, actual, node_token_ids, node_depths, parents, next_token, next_sibling, visibility), the metadata array [budget, D, K, B], the per-request actual node counts, and the first request's tree structure data.

Why This Message Matters: The "First Light" Principle

This message is the software engineering equivalent of a "first light" test in hardware — the moment you power on a new system for the first time to see if anything catches fire. After building the KDTR format, the reference implementation, and the generator, the assistant needs to confirm that:

The generator runs without crashing. Import errors, type mismatches, shape inconsistencies, or algorithmic bugs would surface here.
The KDTR format round-trips correctly. Data written by the Python writer must be readable by the Python reader (and, by extension, the C++ reader that will be used in the test harness).
The data shapes and values look plausible. The metadata, actual node counts, and tree structure arrays should match expectations given the configuration parameters. The output confirms all three: the generator completes, the file loads successfully, and the printed values show a coherent tree structure with 9 actual nodes (root + 8 budget nodes) for a budget of 8, depths ranging from 0 to 4, and a visibility matrix that shows the expected triangular structure.

The Reasoning Behind the Approach

The assistant's thinking, visible in the preceding messages, reveals several deliberate design decisions that culminate in this test.

Why a custom binary format instead of .npy? The assistant considered using NumPy's native .npy format but opted for a custom KDTR format instead. The reasoning, articulated in [msg 11855], was that a custom format gives "full control and simplicity" — a minimal binary format with a magic header, version, and array metadata followed by raw data. This eliminates dependency on NumPy's C library for the C++ test harness and makes the format trivially portable between Python and C++.

Why generate random test data instead of hand-crafted cases? Random generation with sorted log probabilities (each row sorted descending, as the parallel head function would produce) ensures the test covers a wide range of inputs without manual effort. The assistant generates multiple configurations — varying batch size (B), depth (D), top-k (K), and budget — to exercise different regions of the algorithm's behavior space.

Why verify the round-trip immediately? The assistant is practicing defensive engineering. Before writing a single CUDA kernel that depends on this data pipeline, it confirms that the pipeline itself is sound. If the KDTR format had a bug — wrong endianness, incorrect stride calculation, misaligned shape metadata — it would be far easier to debug with a Python round-trip than after the C++ test harness is built and failing mysteriously.

Assumptions Embedded in This Message

Every test encodes assumptions, and this one is no exception. The assistant is assuming that:

The reference implementation is correct. The numpy port of build_ddtree_tree_from_topk faithfully reproduces the SGLang algorithm. Any bug in the reference would be inherited by the CUDA kernel tests, producing false confidence.
Random float values produce distinct cumulative log-weights. The heap tie-breaking logic relies on the assumption that exact ties in cumulative log probabilities are "measure-zero" — effectively impossible with continuous random floats. If ties occurred, the kernel's tie-breaking (insertion order) might diverge from Python's heapq tie-breaking (tuple comparison), causing spurious test failures.
The generated configurations are representative. The chosen parameters (B=4-6, D=7, K=4-8, budget=8-32) cover the algorithm's important regimes but may miss edge cases like budget=1, K=1 (the chain case), or depth exceeding the reachable tree height.
The truncated output is benign. The fourth file's output is cut off in the conversation, but the assistant does not flag it as an error. The assumption is that the generator completed successfully and the truncation is a display artifact.

Input Knowledge Required

To understand this message, one needs to know:

What DDTree speculative decoding is. The tree-building algorithm constructs a draft tree from the top-k log probabilities at each depth, using a best-first heap expansion to select the most promising paths under a budget constraint. This is the core of the speculative decoding drafter being implemented.
The KDTR binary format. A custom container with a magic header, array metadata (name, dtype, shape), and raw data. The Python writer and C++ reader share this format to enable cross-language test data exchange.
The reference algorithm's structure. The tree builder takes top_log_probs (shape [B, D, K]) and top_token_ids (shape [B, D, K]) and produces node tokens, depths, parents, visibility matrix, and retrieval pointers — all padded to the budget length.
The project's phase structure. This is Phase 0 (infrastructure) leading into Phase 1 (CUDA kernel implementation). The reference bundles are the bridge between the two phases.

Output Knowledge Created

This message produces several concrete artifacts:

Four validated KDTR reference files in tests/refs/, each containing batched test cases with inputs and expected outputs. These will be loaded by the C++ test harness to validate the CUDA kernel.
Confirmation of the KDTR round-trip. The Python writer and reader are verified to be compatible, establishing confidence that the C++ reader will also work.
A visual sanity check of the tree structure. The printed arrays show a tree with 9 nodes (root + 8 budget), depths 0-4, and a visibility matrix that visually confirms the triangular dependency structure — the first row is all ones (root is visible to all), subsequent rows show the parent-child relationships.
A baseline for kernel development. With known-good reference data in hand, the assistant can now implement the CUDA tree builder kernel and immediately test it against these bundles.

The Thinking Process Visible in the Reasoning

The assistant's reasoning, spread across the context messages, reveals a methodical approach to a complex engineering task. The thought process moves from high-level architecture ("one thread per request manages the heap, remaining threads parallelize visibility matrix construction") to low-level numerical concerns ("float operation order matters for bit-exact matching") to practical engineering trade-offs ("use insertion order for tie-breaking since exact ties are measure-zero").

A particularly insightful thread appears in [msg 11857], where the assistant traces through the log-weight accumulation to verify that the kernel will produce identical values to the reference:

"Since the kernel replays the same best-first expansion in the same order, it will compute identical logw values through the same sequence of operations, making the whole process self-consistent — identical ordering produces identical operations produces identical logw produces identical ordering."

This is a correctness argument by induction on the heap operations. If the initial state is identical and each operation is deterministic, the entire execution trace is deterministic. The only potential divergence is tie-breaking, which the assistant correctly identifies as a measure-zero concern.

A Subtle Concern: The Truncated Output

One detail worth noting is that the output of the generator is truncated in the conversation. The fourth file's path is cut off mid-string: wrote /home/theuser/glm-kimi-sm120-rtx6000bw/kdtree-engine.... This is almost certainly a display artifact — the generator completed successfully (the verification script runs immediately after and loads the first file without error) — but it serves as a reminder that the conversation transcript is not always a complete record. The assistant, operating in a non-interactive mode, does not flag or react to the truncation.

Conclusion

Message [msg 11859] is a small but essential milestone in a much larger project. It is the moment when abstract infrastructure — a custom binary format, a ported reference algorithm, a test generator — becomes concrete, verified data. The assistant could have jumped straight into CUDA kernel implementation, trusting that the Python pieces would work. Instead, it paused to test the pipeline, to inspect the output, to confirm that the foundation is solid before building on top of it. This is the mark of disciplined engineering: verify early, verify often, and never assume that code works until you see it run.