acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

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 on Qwen3-Coder and on Qwen3-8B. Crucially, this system-level acceleration is directly driven by substantially higher average acceptance lengths ()—yielding relative surges of up to on coding tasks—solidly confirming the effectiveness of our constrained heterogeneous allocation.

Primary area:
infrastructure, software libraries, hardware, systems, etc.
Keywords:
Speculative Decoding, Graph-Constrained Heterogeneous Tree Allocation, Workload-Adaptive

Reviews

Among:
Shape:
1234this paper, Bottom 25%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.75 over 4 reviews, above 25% of the others.
Reviewer_o1QROpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper presents GCHTA, a batch-level speculative decoding controller that jointly considers heterogeneous verification tree allocation, discrete CUDA Graph capacity, and execution-mode transitions. The method combines graph-envelope topology substitution, transition-aware marginal-utility allocation, and counterfactual supertree feedback. Experiments on two Qwen3 models across three workloads report substantial throughput improvements over DFlash.

Critical strengths

1.The paper addresses a meaningful systems problem. Optimizing speculative decoding under discrete CUDA Graph capacities and heterogeneous request characteristics is practically relevant, particularly for batched serving.

2.The proposed controller considers both expected acceptance and physical execution costs, rather than maximizing acceptance length alone. The integration of topology substitution, graph-aware allocation, and execution-mode selection is technically interesting.

3.The reported end-to-end throughput improvements are substantial across multiple workloads and batch sizes. The supplementary material also includes a detailed implementation.

Critical weaknesses

1. Insufficient isolation of the algorithmic contributions.

My main concern is whether the reported performance improvements can be attributed specifically to the proposed graph-constrained heterogeneous allocation strategy.

The system builds upon DFlash and DDTree-style tree construction, while also introducing several execution optimizations, including packed-ragged verification, GPU-side tree construction, deferred KV materialization, and native decoding fallback.

Although the paper includes a homogeneous-allocation ablation, this comparison only reports acceptance length rather than end-to-end throughput. Furthermore, DDTree already introduces efficient verification tree construction from block diffusion draft distributions. A comparison against DFlash+DDTree using the same optimized execution substrate, together with throughput-based allocation ablations, would help clarify the incremental contribution of GCHTA.

2. The ablation study does not directly evaluate the primary optimization objective.

The central objective of GCHTA is to maximize committed-token throughput under physical execution costs. However, Table 3 reports only average acceptance length.

Although the results suggest that all three proposed components improve acceptance length, they do not establish whether these improvements translate into higher end-to-end throughput. Larger or more flexible verification trees may also introduce additional target verification and execution overhead.

The paper explicitly models physical execution costs and provides mechanisms for latency profiling and CUDA Graph replay monitoring. However, the evaluation does not provide sufficient quantitative evidence to distinguish these costs and their contributions. Throughput-based component ablations and stage-level latency breakdowns would provide more direct support for the proposed system-level optimization.

3. Unclear performance attribution between heterogeneous allocation and native fallback.

For Qwen3-8B at BS=64, GCHTA substantially outperforms DFlash but achieves only approximately 1.2–1.4% higher throughput than the target-only baseline.

This observation raises the question of how much of the improvement comes from heterogeneous tree allocation versus the native fallback mechanism. Although the paper already implements and discusses native fallback, its contribution is not quantitatively separated from the other components.

Reporting the proportion of decoding rounds using speculative versus native execution, together with corresponding throughput ablations, would help clarify this distinction.

4. A possible numerical inconsistency in Table 1.

The reported average throughput improvement of 26.41% for Qwen3-Coder does not match the approximately 24.11% obtained by equally averaging the improvements from the displayed values.

In particular, GCHTA achieves 1672 tok/s on MT-Bench at BS=8, which is lower than DFlash's 2070 tok/s and contradicts the statement that GCHTA outperforms DFlash in every evaluated configuration.

If this entry should be 2672 tok/s, the reported mean improvement of 26.41% would be recovered. This may simply be a typographical error, but the authors should verify and correct it.

Questions for authors

Although Table 3 includes a homogeneous-allocation ablation, could the authors report its end-to-end throughput and clarify the additional benefit of graph-constrained heterogeneous allocation over DDTree-style candidate construction under a comparable execution substrate?

Could the authors provide throughput-based ablations for the three proposed components, together with a quantitative breakdown of physical execution costs? In particular, how much of the improvement comes from the allocation policy rather than the underlying execution optimizations?

What proportion of decoding rounds use speculative versus native execution at different batch sizes? In particular, how much of the throughput improvement at BS=64 can be attributed to native fallback?

Could the authors verify the MT-Bench result at BS=8 in Table 1 and clarify the discrepancy between the displayed values and the reported average throughput improvement?

Reviewer_hpjiOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
2
Read review
Paper summary

This paper proposes GCHTA, a framework for batched speculative decoding that jointly optimizes request-level verification trees and CUDA Graph execution. Its main components include heterogeneous request allocation, topology substitution within compatible graph envelopes, and counterfactual feedback for refining candidate selection. Experiments on QWEN3-CODER and QWEN3-8B report throughput and acceptance-length improvements over DFlash, although the gains vary across workloads and batch sizes.

Critical strengths
  • The paper addresses a practical systems problem: optimizing speculative decoding across a batch under discrete CUDA Graph execution constraints.
  • The evaluation reports both throughput and acceptance length across multiple models, workloads, and batch sizes, providing a useful view of end-to-end performance.
Critical weaknesses
  • The proposed framework introduces several interacting mechanisms, including heterogeneous allocation, topology substitution, and counterfactual feedback, but the evaluation does not adequately isolate their contributions to end-to-end throughput. The ablation study reports only acceptance length, leaving it unclear whether the complexity of the proposed design is justified by its practical performance benefits.
  • The performance gains vary substantially across workloads and batch sizes, while the paper provides limited analysis explaining these differences. The results demonstrate promising improvements in some settings, but provide insufficient evidence to validate the claimed benefits of the individual mechanisms.
Questions for authors
  1. How does GCHTA differ from existing cost-aware tree construction methods such as CAST? Could the authors clarify the additional benefits of GCHTA's batch-level allocation and CUDA Graph-constrained optimization under comparable experimental settings?
  2. Could the authors report end-to-end throughput or latency ablations for heterogeneous allocation, topology substitution, and counterfactual feedback, to clarify the contribution of each component to the overall speedup?
  3. What explains the substantial variation in throughput improvements across workloads and batch sizes, particularly the larger gains at BS=64? Can the authors separate the effects of allocation decisions from CUDA Graph execution costs?
Reviewer_71MwOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper proposes GCHTA for adaptive speculative decoding. It assigns different tree structures to different requests and improves throughput over DFlash.

Critical strengths
  • The paper addresses a practically relevant and important problem in LLM serving: how to allocate speculative decoding resources across heterogeneous requests under CUDA Graph constraints.

  • Under the evaluated settings, the proposed method consistently achieves substantial end-to-end throughput improvements over DFlash, while using the same draft model and comparable system configurations.

Critical weaknesses
  • The paper is difficult to follow. The paper introduces many specialized concepts, such as CUDA Graph capacity, Graph envelope, topology substitution, request-local frontier, and supertree replay, without clear definitions or examples. This makes the method difficult to understand and reproduce.

  • Limited generalization. Experiments only cover Qwen3 models on H800 GPUs with one CUDA Graph configuration, so it is unclear whether the method generalizes to other models, hardware, or Graph settings.

  • Unclear optimality claim. The paper lacks empirical study in motivation part. The paper describes GCHTA as 'optimal', but its allocator greedily selects the highest-utility feasible increment.

Questions for authors

How sensitive is GCHTA to the model family, hardware platform, and CUDA Graph configuration? Do the authors have results or analysis beyond Qwen3 models on H800 GPUs? How does the greedy allocation strategy ensure 'optimality'? Authors should clarify 'optimal' and provide theoretical or empirical evidence to support this claim.

Reviewer_1JS4OpenReview ↗
Rating
2
Confidence
4
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

This work proposes Graph-Constrained Heterogeneous Tree Allocation (GCHTA), which optimizes the CUDA-Graph operation of tree drafting for the diffusion based speculative decoding, especially for large batch sizes. In batched serving, the real limit is the small set of fixed CUDA graph sizes. Specifically, a slightly larger tree can push the whole batch into a bigger and slower graph, so accepting more tokens does not always mean higher throughput. GCHTA thus is designed to allocate more tokens to requests that can be easily speculated, while allocates less tokens or non to hard ones. It also finds the best tree shapes when it fits in the same graph based on the heuristic signals. After verification, it reuses the accepted path to estimate how other candidate trees would have done, so it can update acceptance estimates without running them. This work compares GCHTA with DFlash and plain AR decoding on Qwen3-Coder-30B-A3B and Qwen3-8B across GSM8K, HumanEval, and MT-Bench, with batch sizes from 1 to 64. It reports average throughput gains over DFlash of 26.41% on Qwen3-Coder and 22.59% on Qwen3-8B.

Critical strengths

I think the problem solved by this work is meaningful. In production serving, CUDA graphs only come in a few fixed sizes for the tree drafting based speculative decoding, and crossing a size boundary costs a lot. In terms of the description, the efforts to implement this system work is non-trivial including the packed-ragged verification, GPU-size tree construction, deferred draft KV and per-round plan validation, etc. The corresponding improvements on throguhput across different batches are also making sense.

Critical weaknesses

(1) Unfortunately, this work misses a very important baseline and several important related works. ECHO [1] studies almost the same problem. It treats the whole batch as one “super-tree” under a shared verification budget, moves this budget across requests and between tree depth and width. It should be both discussed and compared against. The paper also misses PRESTO [2], which builds draft trees from diffusion drafters and solves the drafting-verification misalignment issue for diffusion drafter. Other tree-based methods such as Sequoia [3], SpecInfer [4], and EAGLE-3 [5] should also be discussed.

(2) The acceptance length is only reported as an average over batch sizes 1 to 64. Since GCHTA gives each request fewer nodes as the batch grows, acceptance length should vary a lot with batch size. The authors should report it for each batch size, and clarify how the average is computed.

(3) In Table 1 (Qwen3-Coder, MT-Bench, BS = 8), GCHTA’s throughput is 1672, exactly the same as at BS=4 and lower than DFlash. This contradicts the claim that GCHTA outperforms DFlash in every configuration. The average gain for Qwen3-Coder is 24.11%, not the reported 26.41%.

(4) Many important method details are missing, which makes the method hard to understand and reproduce. For example, the paper does not explain how the six latency terms in Eq.~(3) are predicted. Key parameters such as βA\beta_A, βL\beta_L, λswitch\lambda_{\text{switch}}, ηhit\eta_{\text{hit}} and the union budget CiC_i are never given. ``Graph-envelope compatible'' is only described in words, and it is unclear why tree topology affects CUDA Graph capture when trees have the same number of nodes. The authors should provide these details and the hyperparameter settings.


[1] Hu et al. ECHO: Elastic Speculative Decoding with Sparse Gating for High-Concurrency Scenarios. ICML 2026.

[2] Wang et al. PRESTO: Prefix-Aligned Tree Drafting for Diffusion Speculative Decoding. ICML 2026.

[3] Chen et al. Sequoia: Scalable, Robust, and Hardware-aware Speculative Decoding. arXiv:2402.12374, 2024.

[4] Miao et al. SpecInfer: Accelerating Large Language Model Serving with Tree-based Speculative Inference and Verification. ASPLOS 2024.

[5] Li et al. EAGLE-3: Scaling up Inference Acceleration of Large Language Models via Training-Time Test. arXiv:2503.01840, 2025.

Questions for authors

Please see weaknesses.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.