Graph-Constrained Heterogeneous Tree Allocation for Workload-Adaptive Speculative Decoding

Speculative decoding improves language-model serving by verifying draft tokens in parallel, but its benefit is limited when a heterogeneous batch must share a discrete execution budget. Requests differ in draft confidence, acceptance history, and transition cost, whereas captured Graphs impose discrete capacity and topology constraints. Consequently, maximizing accepted tokens or assigning a homogeneous verification width to every request is not equivalent to maximizing end-to-end throughput. We present GCHTA (Graph-Constrained Heterogeneous Tree Allocation), a batch-level controller designed for this setting. Given DFlash proposals and DDTree-style candidates, GCHTA constructs request-local frontiers, performs topology substitution within a valid Graph envelope, and allocates heterogeneous speculative work using transition-aware utility. Furthermore, nested and bounded-union supertrees provide counterfactual acceptance feedback, elegantly separating simulated policy exploration from physically measured replay latency and graph validity. This algorithmic policy operates on an optimized CUDA-Graph substrate featuring packed-ragged verification, GPU-side tree construction, deferred draft-KV materialization, and reversible native execution. Evaluations on Qwen3-Coder and Qwen3-8B demonstrate that GCHTA significantly outperforms DFlash across diverse workloads (GSM8K, HumanEval, MT-Bench). It achieves mean throughput improvements of $26.41\%$ on Qwen3-Coder and $22.59\%$ on Qwen3-8B. Crucially, this system-level acceleration is directly driven by substantially higher average acceptance lengths ($\tau$)—yielding relative $\tau$ surges of up to $80.7\%$ on coding tasks—solidly confirming the effectiveness of our constrained heterogeneous allocation.