Reusing GPU Kernels for Tree-Structured Temperature Sampling: A Case Study in Speculative Decoding Architecture

Introduction

In the rapidly evolving landscape of large language model inference, speculative decoding has emerged as a critical technique for improving throughput without sacrificing quality. Among the various speculative decoding strategies, DFlash with DDTree (Draft-Driven Tree) represents a sophisticated approach where a lightweight draft model proposes multiple candidate token sequences organized as a tree, and the target model verifies them in parallel. However, one significant limitation had remained: DDTree only supported greedy (deterministic) verification, raising an error when users attempted temperature sampling—a crucial feature for controlling the creativity and diversity of model outputs.

This article examines a pivotal message in a long-running coding session where an AI assistant works through the architecture, design decisions, and implementation strategy for adding temperature sampling support to DDTree's tree-structured speculative decoding. The message, occurring at index 11637 in the conversation, captures the moment of synthesis where the assistant connects the existing GPU kernel infrastructure with DDTree's tree representation, realizing that a complex CPU-side implementation can be avoided entirely by properly adapting DDTree's data structures to match an existing, optimized kernel interface.

Context: The State of DDTree Before This Message

To understand the significance of this message, we must first appreciate the broader context. The session involved deploying and optimizing the Kimi K2.6 model with DFlash speculative decoding across two hardware platforms: an 8× RTX PRO 6000 system connected via PCIe, and an 8× B300 SXM6 system with NVLink interconnects. The assistant had already achieved impressive results—up to 2.15× speedup over the autoregressive baseline on NVLink hardware—but DDTree's temperature sampling remained a hard blocker.

In the preceding messages (indices 11631–11636), the assistant had been systematically investigating how to implement temperature sampling for DDTree. The initial approach considered was a CPU-side rejection sampling walk: traversing the tree node by node, computing softmax probabilities along the accepted path, and making acceptance decisions for each child. This approach, while conceptually straightforward, raised concerns about performance impact and complexity.

The assistant then discovered that linear DFlash (the non-tree variant) already supported temperature sampling through the tree_speculative_sampling_target_only kernel from sgl_kernel. This kernel implements GPU-accelerated tree-structured rejection sampling, but it was designed for EAGLE's tree representation, which uses a specific encoding of tree topology through three index arrays: retrieve_index, retrieve_next_token, and retrieve_next_sibling. The critical question became: could DDTree's parent-child representation be converted into EAGLE's index format, allowing reuse of the same high-performance GPU kernel?

The Subject Message: A Synthesis of Architecture and Implementation

Message 11637 represents the moment where all the pieces come together. The assistant's reasoning reveals a deep understanding of both the kernel interface and DDTree's internal data structures, leading to a clean architectural insight.

Understanding the Kernel's Output Contract

The assistant begins by analyzing how the greedy verification path produces its results: an accepted path of node indices and a proposed list of tokens to emit. The kernel's output format is then mapped onto this same contract. The kernel returns flat indices into a [bs * q_len] array—accept_index contains the flat positions of accepted nodes, predict holds the token at each position, and accept_token_num tracks the count per request.

The key insight is elegant: "I can convert these flat indices back to local node indices within each request's tree using modulo arithmetic." Specifically, accept_index_row % q_len gives the local node index within each request's tree, while accept_index_row // q_len identifies which request. This simple arithmetic bridges the gap between the kernel's flat output format and DDTree's per-request tree structure.

The Shared Contract Between Greedy and Sampling Paths

A crucial architectural realization follows: both the greedy and sampling paths produce the same logical outputs—accepted node indices and proposed tokens—that follow the same contract. In both cases, the last proposed token is always the bonus token (sampled from the residual distribution when all draft candidates are rejected or as the final token), and the earlier tokens are the draft tokens that were accepted. This means the downstream commit logic—which handles KV cache bookkeeping, hidden state selection, and token emission—can be shared between both paths without modification.

This insight is the foundation of the refactoring strategy. Rather than duplicating the commit logic or creating a complex abstraction layer, the assistant plans to refactor the verify method to derive (accepted_indices, proposed_tokens) from either the greedy tree-following algorithm or the kernel's sampling output, then feed both into identical downstream code.

The Implementation Plan

The assistant outlines a concrete five-step implementation plan:

Add a helper to compile the DDTree retrieval structure: Convert DDTree's parents_per_req and child_maps_per_req into EAGLE-style (retrieve_next_token, retrieve_next_sibling) index arrays. This requires ordering siblings by their cumulative log-probabilities in descending order, so the kernel tries the highest-probability candidates first during rejection sampling.
Augment the builder to track node log-weights: The tree builder already computes cumulative log-probabilities during the heap-based construction. These need to be stored and returned so the retrieve-encoding helper can sort siblings correctly.
Store retrieval metadata on the verify input: Rather than computing the retrieval structure lazily during verification (which would add latency to the sampling path), the assistant decides to compute it eagerly during tree construction and store it on the DDTreeVerifyInput object. This is a deliberate trade-off: slightly more memory usage in exchange for cleaner code and predictable performance.
Refactor the verify method: Split the verification into two phases—a decision phase that produces (accepted_indices, proposed_tokens) via either greedy or sampling logic, and a shared commit phase that handles KV cache updates, hidden state selection, and token emission.
Remove the guard blocking non-greedy DDTree verification: Currently, DDTree's verify method raises an error when temperature is not 0. This guard is removed once the sampling path is implemented.

Handling Sibling Ordering Correctly

One of the more subtle challenges the assistant grapples with is sibling ordering. The DDTree builder uses a max-heap that pops nodes in order of descending cumulative log-probability. However, siblings of the same parent are not necessarily popped in descending order—they can be interleaved with nodes from other parents. The rejection sampling kernel, however, needs to try siblings in descending draft-probability order for correctness (it attempts the most likely candidate first, which maximizes acceptance probability).

The assistant traces through the build logic carefully: "when a node is popped, it pushes its next sibling (rank+1) and its first child (rank 0). So siblings of the same parent share the same depth and parent, but their relative order in the tree depends on when they were pushed and popped." The solution is to sort siblings by their cumulative log-weight after construction, using the node_logws that the augmented builder will provide.

Assumptions and Design Decisions

Several important assumptions underpin this design:

The kernel handles draft probabilities correctly when set to zero. The assistant verifies that EAGLE passes draft_probs=zeros to the same kernel, meaning the kernel performs standard tree verification using only the target probabilities and the tree structure indices. This is a critical assumption—if the kernel required non-zero draft probabilities for tree-structured inputs, the approach would fail. The assistant confirms this by examining EAGLE's code in message 11634.

The modulo arithmetic for flat-to-local index conversion is correct. The assumption is that the kernel's accept_index contains flat indices where the row (request) and column (node position) are packed as row * q_len + col. If the kernel used a different packing scheme, the conversion would produce incorrect node indices.

The commit logic is truly identical for both paths. The assistant asserts that "the shared commit loop will work correctly for both branches without modification." This assumes that the greedy and sampling paths produce structurally identical outputs, differing only in which nodes are accepted. If the sampling path produced a different output shape or required different KV cache handling, the shared code would need branching anyway.

Eager retrieval structure computation is acceptable. The assistant chooses to compute the retrieval structure during tree construction rather than lazily during verification. This assumes the memory and computation cost is negligible relative to the overall inference workload—a reasonable assumption given that the tree is typically small (budget of 8–16 nodes per request).

Potential Pitfalls and Considerations

While the design is elegant, several potential issues deserve scrutiny:

The sibling ordering guarantee. The assistant notes that siblings are "mostly" in descending log-probability order from the heap construction but plans to sort them explicitly. If the sorting is implemented incorrectly—for example, sorting by raw log-probability rather than cumulative log-weight—the kernel might try candidates in suboptimal order, reducing acceptance rates.

Padding handling. DDTree pads the tree to the budget length with root tokens when there aren't enough nodes. The retrieve structure needs valid but harmless values for these padded positions. If the padding values cause the kernel to attempt invalid tree traversals, it could produce incorrect results or crash.

The bonus token's hidden state. The assistant notes that "the bonus token's node's hidden state is what we need for the next block." This assumes that the bonus token's position in the tree has a corresponding hidden state that can be extracted for the next drafting step. If the bonus token is sampled from the residual distribution rather than from a draft node, its hidden state might need special handling.

Input Knowledge Required

To fully understand this message, one needs familiarity with:

Speculative decoding: The technique where a draft model proposes candidates and a target model verifies them in parallel.
DDTree (Draft-Driven Tree): A tree-structured speculative decoding approach where multiple candidate paths are explored simultaneously.
EAGLE: Another speculative decoding framework that uses a similar tree structure.
The tree_speculative_sampling_target_only kernel: A GPU kernel from sgl_kernel that implements rejection sampling over tree-structured candidates.
KV cache management: The mechanism for caching key-value pairs from previous tokens to avoid recomputation.
CUDA graph capture: A technique for recording and replaying GPU operations to reduce launch overhead.

Output Knowledge Created

This message produces a concrete architectural plan that bridges the gap between DDTree's tree representation and the existing GPU kernel interface. The key outputs are:

A verified approach for reusing the tree sampling kernel: Rather than implementing a new CPU-side rejection sampling algorithm, the assistant confirms that DDTree's parent-child structure can be converted to EAGLE's index format, enabling reuse of the existing high-performance GPU kernel.
A refactoring strategy for the verify method: The plan to split verification into a decision phase (greedy vs. sampling) and a shared commit phase provides a clean architecture that minimizes code duplication.
Specific data structure augmentations: The need to track node_logws in the build result and compute retrieval indices during tree construction.
A correctness argument: The insight that both greedy and sampling paths produce outputs following the same contract (accepted node indices + proposed tokens), enabling shared downstream logic.

The Thinking Process: A Window into Architectural Reasoning

What makes this message particularly valuable is the visible reasoning process. The assistant doesn't just state a plan—it works through the implications step by step, questioning assumptions and verifying understanding.

The reasoning begins with a concrete problem: "The kernel outputs give me flat indices into the flattened [bs*q_len] arrays." From this concrete detail, the assistant builds upward: how to convert flat indices to local node indices, how to map accepted nodes to KV cache entries, how to extract hidden states for the next drafting step.

The assistant then generalizes: "I'm realizing the kernel path should map accepted flat positions to node indices, extract the corresponding predicted tokens, and feed them into the same downstream logic for keeping nodes and committing tokens." This is the moment of synthesis—seeing that the kernel's output format, once properly interpreted, feeds naturally into the existing infrastructure.

The reasoning also shows careful attention to edge cases. The assistant considers the bonus token explicitly: "this aligns the number of kept nodes with the number of committed tokens, and handles the bonus token correctly since its node's hidden state is what we need for the next block."

Finally, the assistant produces a concrete action plan: "adding a helper to compile the DDTree retrieval structure, augmenting the builder to track node log-weights, storing the retrieval metadata on the verify input, refactoring the verify method to handle both greedy and sampling with a shared commit phase, adding a method to sample tree paths via the kernel, and removing the guard that currently blocks non-greedy DDTree verification."

Conclusion

Message 11637 represents a critical architectural turning point in the implementation of temperature sampling for DDTree speculative decoding. By recognizing that DDTree's tree structure can be encoded into the index format expected by the existing tree_speculative_sampling_target_only kernel, the assistant avoids a costly and complex CPU-side implementation while gaining the performance and correctness benefits of a battle-tested GPU kernel.

The design is characterized by careful attention to data structure compatibility, a shared-contract approach that minimizes code duplication, and a clear separation between the decision logic (greedy vs. sampling) and the commit logic (KV cache management, token emission). The message demonstrates how deep understanding of existing infrastructure can enable clean extensions that feel almost inevitable in retrospect—the hallmark of good software architecture.

The implementation that follows from this message would go on to enable temperature-controlled DDTree verification, unlocking the full range of sampling strategies (temperature scaling, top-k filtering, top-p filtering) for tree-structured speculative decoding, and ultimately contributing to the impressive throughput improvements documented in the session's findings report.