acceptodds
Under review as a conference paper at ICLR 2027

SemanticTree: Grammar-Aware Tree Allocation for Speculative Decoding

Abstract

Tree-based speculative decoding allocates candidate tokens before target verification. In structured generation, grammar checks come too late to reallocate this budget: 73–77% of non-root slots in EAGLE3 trees contain grammar-invalid candidates. We call this semantic waste. SemanticTree excludes unreachable candidates during tree allocation while preserving the proposer's scores and budget. A parser-state mask cache shares work across branches and rounds, and verification reuses the masks obtained during drafting. We integrate SemanticTree with an autoregressive drafter, EAGLE3, and a block drafter, DDTree. Across 35 drafter–target–workload settings at batch size one, verification rounds fall by 16.4–29.8% with EAGLE3 and 17.2–25.8% with DDTree; decode throughput rises by 19.5–40.3% and 15.5–25.6%, respectively. A cache ablation preserves all round savings but reduces the throughput gain from 33% to 7% on Qwen3-4B/Nexus with EAGLE3, showing that recovering semantic waste requires both effective allocation and low grammar-processing cost.

Primary area:
infrastructure, software libraries, hardware, systems, etc.
Keywords:
speculative decoding, structured generation, constrained decoding

Reviews

Among:
Shape:
1234this paper, Top 17%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.75 over 4 reviews, above 83% of the others.
Reviewer_EV1gOpenReview ↗
Rating
2(+1)
Confidence
4
Informativeness
2
Presentation
2
Soundness
2(+1)
Read review
Paper summary

This paper identifies semantic waste in grammar-constrained tree-based speculative decoding: candidate slots are allocated before grammar checking, so many slots are occupied by tokens that the constrained target can never accept. This paper proposes SemanticTree, which moves exact grammar eligibility checking into tree construction while preserving the original proposal scores and verification budget. It also introduces parser-state hashing and mask caching to reuse grammar masks across branches and decoding rounds. On five schema-constrained tool-calling workloads, the paper reports fewer verification rounds and higher decoding throughput.

Critical strengths

The systems analysis is careful within the evaluated setting. The paper distinguishes reductions in verification rounds from changes in per-round cost. The parser-state cache ablation is particularly informative: it shows that the same trees and round counts can produce very different end-to-end gains when grammar processing reaches the critical path. This supports the paper’s systems argument rather than attributing all gains to tree quality alone.

Critical weaknesses
  1. The validated decoding and workload regime is limited. All experiments use greedy decoding, and the verification invariant is stated only for constrained-greedy continuation. The paper does not evaluate how grammar-aware allocation performs under sampling, which is the most common configuration in real world LLM serving. The workload coverage (BFCL, Nexus, ToolHop) is narrow as every output is converted into the same schema-constrained function-call object containing a function name and arguments. The experiments therefore establish effectiveness for JSON tool-call generation, not for grammar-constrained generation in general. The method relies on both a high rate of grammar-invalid proposals and substantial parser-state reuse, and the selected workloads are particularly favorable in both respects. The paper does not establish that its benefits extend beyond strongly constrained structured outputs.
  2. The compared baselines are limited. The evaluation does not establish that SemanticTree remains useful with stronger tree-allocation methods. The empirical study only adds SemanticTree to EAGLE-3 and fixed-budget DDTree, both of which allocate candidates primarily from proposal scores under a predetermined budget. It remains unclear whether the reported gains are complementary to more advanced allocators [1-3] that adapt tree topology, width, stopping decisions, or verification budget using path-conditioned acceptance estimates and runtime costs. This interaction also may influence system overhead as grammar filtering changes the effective branching factor and the set of candidates available to each parent. An allocator that constructs a larger intermediate tree may therefore increase SemanticTree’s grammar-processing cost even if the final verification tree has the same size. The results on two fixed-budget allocators do not support the broader implication that SemanticTree is generally compatible with, or remains beneficial on top of, current tree-construction techniques.

[1] Wang, Jikai, et al. "Opt-tree: Speculative decoding with adaptive draft tree structure." Transactions of the Association for Computational Linguistics (2025). [2] Hong, Yinrong, et al. "Inference-cost-aware dynamic tree construction for efficient inference in large language models." International Conference on Learning Representations (2026). [3] Li, Tianyi, et al. "Dartree: Speculative diffusion decoding with autoregressive draft trees." arXiv preprint arXiv:2608.13524 (2026).

Questions for authors
  1. Does SemanticTree preserve the exact constrained target distribution and maintain effective under stochastic sampling?
  2. How does the method behave outside JSON tool calling? The evaluation lacks other grammar types, varying constraint strengths and unconstrained-generation overhead.
  3. How does SemanticTree compare with and combine with adaptive or cost-aware tree allocators such as OPT-Tree and DARTree? The paper lacks both end-to-end comparisons and a breakdown of the additional tree-construction and grammar-processing costs.
6 comments
AuthorsOpenReview ↗

Sampling and exactness

We thank the reviewer. Part 1/3: sampling and exactness (Q1).

Sampling (T > 0) and exactness

Short answer. SemanticTree samples the same target as standard constrained decoding: at every prefix, the locally masked and renormalized target μ^proj, which the unmodified baseline also samples. In exact arithmetic, SGLang's verifier draws an exact sample from μ^proj for any set of distinct candidates fixed before its coin, so SemanticTree changes which candidates are verified, not what is sampled. The revised Sec. 2.2 now states this sampling invariant in the main text. A pre-existing float32 boundary case in SGLang's verifier (probability 2^−24 per decision, both arms, fixed upstream) is discussed below. Under sampling, decode-only gains are +24.0% to +33.1% at T = 1 (all intervals above zero) and +10.4% to +34.5% at T = 0.7 (three of four intervals above zero).

Target and verifier. At a fixed prefix, let q = μ^proj_t be the normalized target probabilities used by standard SGLang constrained decoding, with the same grammar mask, temperature and sampling settings in both arms. Our runs set both acceptance thresholds to 1 (threshold_acc = threshold_single = 1). Sibling tokens are distinct (top-k drafting) and fixed before the verification coin is drawn.

For a candidate set S, a uniform coin assigns each candidate x an interval of length q(x), so x is accepted with probability q(x). If no candidate is accepted, the verifier samples q with S zeroed and renormalized. Writing m = Σ_{x∈S} q(x), any y outside S is emitted with probability (1−m)·q(y)/(1−m) = q(y) when m < 1; when m = 1 the residual branch has probability zero. Thus every token has its target probability, and applying the rule at successive prefixes with independent coins preserves the sequence distribution. SemanticTree changes S, not this rule or the target probabilities.

Float32 boundary (pre-existing in SGLang). With a float32 coin, coin <= mass accepts a zero-mass first candidate when the coin is exactly 0.0, an event of probability 2^−24 per such decision that affects both arms (issue #35771; fixed upstream in PR #35798, which also changes the CDF comparisons). We observed it once in 10^6 kernel draws. To isolate it, we rebuilt the CUDA verifier with a one-line skip of zero-mass candidates (target_prob > 0 && coin <= mass): on 408,000 shared coins (4 trees) the unmodified build matches the installed kernel and the patched build matches our reference verifier row by row; under forced zero coins the installed kernel accepts a zero-mass token in 2000/2000 rows and the patched kernel in 0/2000; 10^6-draw tests on the patched kernel pass (min Holm-adjusted p = 0.54, first-token TV ≤ 0.0011). The throughput results use the unmodified kernel.

Tests and throughput. These finite-sample checks complement the exact-arithmetic argument above.

  • Kernel: chain and branching trees with zero-mass illegal nodes and with legal replacements; minimum Holm-adjusted p = 0.25 at 10^5 draws and 0.33 at 10^6 draws (independent seed); first-token TV ≤ 0.001.
  • End to end: 4 prompts per (model, workload), 512 seeds per arm, against constrained autoregressive decoding on exact output, length, function name and finish reason: 128 tests, minimum Holm-adjusted p = 0.44.
  • Throughput, EAGLE3 10-7-60, all outputs retained (T = 1: 3 replicates; T = 0.7: 3 seeds); the DFlash/DDTree runtime verifies greedily, so sampling uses EAGLE3:
Target / workloadT = 1 decodeT = 1 E2ET = 0.7 decodeT = 0.7 E2E
Qwen3-4B / BFCL-multiple+29.0% [+21.0, +37.5]+15.4%+21.4% [+12.3, +30.9]+20.7%
Qwen3-4B / Nexus+33.1% [+19.2, +49.1]+16.7%+34.5% [+18.9, +49.2]+19.6%
Llama-3.1-8B / BFCL-multiple+30.8% [+26.8, +35.0]+21.4%+30.3% [+26.8, +33.8]+22.9%
Llama-3.1-8B / Nexus+24.0% [+17.9, +30.1]+6.8%+10.4% [−3.4, +25.4]+10.1% [+6.0, +14.4]

Verify rounds per token fall in every cell (e.g. 0.435 → 0.359 for Qwen3-4B/BFCL-multiple at T = 1).

Target scope. μ^proj generally differs from μ*, obtained by conditioning the entire output on the grammar (Park et al., 2024; Nie et al., 2026, Sec. 5); any decoder that accesses the grammar only through local masks, including the baseline, samples μ^proj. The main evaluation stays greedy so that every case has one deterministic reference for the per-case output-identity checks (our response to Reviewer tFdd). Appendix G gives the verifier analysis, the distribution tests and both sampling tables.

AuthorsOpenReview ↗

Generality beyond JSON tool calls

Part 2/3: generality beyond JSON tool calls (Q2).

Short answer. (1) Constraint strength: the gain grows with how tightly the grammar constrains each output position; relaxing a schema to any JSON object leaves +1.2% to +3.1%, and five JSONSchemaBench suites give +9.4% to +112.6%. (2) Other grammars: on the SMCalFlow Lispress program grammar, whose masks XGrammar computes in about 0.05 ms, SemanticTree is faster (+9.4% / +40.5%); on Spider SQL, where XGrammar's uncached masks take about 20 ms, it is 25.2% slower, so the boundary lies in the engine's mask cost. (3) Unconstrained requests take the stock path (measured change −2.4% to +2.8%). (4) Parser-state reuse is mostly within a request; without a cache, BFCL gains stay above +21%.

Constraint strength and unconstrained traffic

Within workloads, the gain is associated with constraint tightness along the output and with compiled grammar size, and only weakly with schema-level counts.

  • Same prompts, only the grammar changes (EAGLE3, B = 1, a separate run): original schema +20.3% to +33.9%; relaxed schema (enum/required/const removed) +13.1% to +33.4%; any JSON object +1.2% to +3.1%. DDTree: +18.3% to +25.2% → +1.0% to +7.6%.
  • Per-case analysis over 7 JSON workloads (485 Qwen3-4B / 494 Llama cases): the gain correlates with the fraction of output positions that allow ≤ 64 tokens (Spearman +0.18 for Qwen3-4B, +0.40 for Llama; within-workload medians +0.22 / +0.38) and negatively with the median legal-token count (−0.14 / −0.45). Property count, nesting depth, enum/anyOf count and schema size have within-workload correlations between −0.13 and +0.12; compiled grammar size reaches +0.21 / +0.28.
  • Five JSONSchemaBench suites (Github_medium, Github_hard, Kubernetes, Snowplow, WashingtonPost), whose outputs are configuration, event and content documents from these sources, × two targets: all 10 all-case CIs > 0 (Qwen3-4B +11.9% to +112.6%, Llama +9.4% to +58.7%); the Github_medium values are heavy-tailed (Qwen3-4B token-identical cohort: +20.2%). On Github_hard, the suite with the longest outputs (≈260 tokens), all-case decode-only gains are +20.1% [+14.3, +27.9] (Qwen3-4B) and +18.1% [+15.2, +21.2] (Llama), and E2E gains +18.9% [+13.4, +26.4] / +17.0% [+14.3, +19.9]: prefill is about 4–5% of a request, so nearly all of the decode gain carries over to end-to-end throughput.

Unconstrained and mixed traffic. Requests without a grammar take the stock SGLang path, and a batch that contains any such request runs the stock path as a whole. In a same-GPU interleaved re-test (Llama, B = 8), unconstrained traffic changes by −2.4% [−3.8, −1.1] / +0.8% [−2.8, +4.9] (BFCL / Nexus) and mixed traffic by −2.3% [−4.5, −0.4] / +2.8% [−1.8, +8.9]. On BFCL this is a small overhead of about 2.4%, with an interval excluding zero; same-arm drift between the passes of this test reached 6.8%. Per-row proposal selection would bring the gain to constrained requests in mixed batches. All results in this part are in the new Appendix H.

Beyond JSON: the gain follows the engine's mask cost. Both grammars below run on XGrammar and differ in mask cost.

  • SMCalFlow Lispress (Grammar Prompting's Lark grammar, Wang et al., 2023, in XGrammar's EBNF): an uncached mask takes 0.05 / 0.04 ms on average along reference outputs (Qwen3-4B / Llama), with medians of 11 / 5 legal tokens. With each arm selecting its best shape on calibration cases (B = 1, separate passes), the best SemanticTree tree is faster than the best original tree on held-out cases: +9.4% [+7.8, +11.1] (Qwen3-4B, n = 61) and +40.5% [+29.5, +51.5] (Llama, n = 51).
  • Spider with SynCode's SQL grammar (Qwen3-4B, 256 cases): XGrammar's scannerless parsing leaves most tokens context-dependent after an open SQL terminal, and an uncached mask takes about 20 ms on a 48-case replay (JSON workloads: 0.007–0.28 ms). The constrained EAGLE3 4-3-16 tree runs at 10.14 tok/s, and SemanticTree lowers it to 7.58 tok/s: −25.2% [−26.5, −23.9]. Here the cost of the engine's masks outweighs the recovered rounds.
  • As an engine contrast, llguidance 1.8.0 computes SQL masks in 0.64–0.70 ms on common token paths with a different grammar encoding (legal-token counts coincide at only 5/1965 Qwen and 34/1769 Llama positions), so these timings characterise mask cost per engine-and-encoding pair.

An engine port needs parser-state fork/advance, exact masks, a cacheable state key and commit/rollback; our implementation provides these on patched XGrammar, and we state the performance claim for workloads whose masks the engine computes cheaply or reuses.

Reliance on parser-state reuse. Reuse comes mostly from within each request: clearing the cache per request at B = 1 lowers throughput by 0.4–0.6% on BFCL/Nexus and 4.3–7.4% on Github_medium, and with no cache BFCL decode gains remain +21.4% / +32.1% (Qwen3-4B / Llama), versus +22.0% / +32.8% with 4096 rows (Appendix E.1). The grammar results are in Appendix H.

AuthorsOpenReview ↗

Stronger allocators and cost breakdown

Part 3/3: stronger allocators and cost breakdown (Q3).

Stronger allocators and the cost breakdown

Short answer. (1) SemanticTree also speeds up DARTree with its released implementation (+24.58% / +15.88%), OPT-Tree in three of four settings once each arm tunes its size, and dynamic-depth (DDD) trees (+17.2% to +30.3%). (2) The concern about larger intermediate trees holds: OPT-Tree with a 59-node budget builds 363 frontier masks per round and its gain shrinks or turns negative; per-arm size tuning restores a gain in three of four settings. (3) E2E gains and a per-round cost breakdown are given for every allocator. (4) For CAST's online cost model, per-arm throughput tuning serves as an offline proxy.

SemanticTree is an eligibility filter on the candidate pool an allocator scores. B = 1. Rows 1–3 are fixed configurations; each ±SemanticTree pair runs with identical settings, back to back on one GPU (EAGLE3 from a separate re-run of the main configuration). Row 4 tunes each arm separately on calibration cases and compares the two on held-out cases:

AllocatorQwen3-4B BFCLQwen3-4B NexusLlama BFCLLlama Nexus
EAGLE3 10-7-60+22.0% [+19.7, +24.3]+33.1% [+28.6, +37.4]+32.8% [+30.4, +35.3]+19.7% [+16.7, +22.9]
DDD (dynamic depth)+20.1% [+17.8, +22.2]+30.3% [+26.3, +34.3]+25.7% [+23.5, +28.0]+17.2% [+14.4, +20.3]
OPT-Tree, n = 59, δ = 0.5+5.0% [+3.7, +6.4]+11.2% [+7.1, +15.4]−7.5% [−8.6, −6.3]+4.5% [+2.2, +6.6]
OPT-Tree, size chosen per arm by measured throughput (held-out)+15.9% [+13.6, +18.4]+13.1% [+10.7, +15.3]+1.1% [−0.7, +2.9]+5.7% [+3.3, +7.9]

Direct DARTree test. We adapted the official DARTree implementation with the Domino-b16 correction head used by its release (Qwen3-4B, B = 1, greedy, pruned supertree width 12, candidate pool 64; both arms verify 64 non-root slots). Decode tok/s goes 152.95 → 190.54 on BFCL (N = 192): +24.58% [+22.19, +27.00]; Nexus (N = 63): 123.53 → 143.15, +15.88% [+12.71, +18.96]; E2E +19.91% [+18.01, +21.83] / +10.21% [+7.86, +12.60]. Verify rounds fall 23.0% / 17.4%, while tree-build time goes 2.84 → 4.71 / 2.91 → 4.64 ms per round. This runs in a separate Transformers runtime, so absolute TPS is compared within the DARTree pair; the protocol is in Appendix I.

Larger intermediate trees (OPT-Tree). Per round, OPT-Tree with n = 59 builds 363 frontier masks and spends 4.24 ms of host grammar time (vs 50 masks and 0.61 ms for EAGLE3 10-7-60), and the gain shrinks or turns negative. When each arm chooses its own (n, δ) by measured throughput on calibration cases, the held-out gain is +13% to +16% on Qwen3-4B, +5.7% on Llama/Nexus and +1.1% on Llama/BFCL. Appendix I also analyses how OPT-Tree's δ-stop interacts with grammar-masked probabilities (trees stop about one layer early). OPT-Tree and its tuning are our own implementation in SGLang. Against the original EAGLE3 10-7-60 tree on the same held-out cases (separate passes), EAGLE3+ST stays the fastest configuration in all four settings.

End to end. EAGLE3 +12.5% to +25.3%, DDD +10.3% to +20.0%, OPT-Tree n = 59 −6.4% to +5.0%, size-tuned OPT-Tree +0.6% to +13.3%. In absolute terms, EAGLE3 10-7-60 is the fastest original allocator in all four settings (e.g. Qwen3-4B/Nexus 116.6 vs 103.4 tok/s for DDD and 101.1 tok/s for OPT-Tree n = 59; separate passes), and SemanticTree adds as much or more to it.

Per-round cost (Qwen3-4B, B = 1, SemanticTree arms). Draft host time / grammar time / draft-graph GPU wait / frontier masks: chain d3 1.11 ms / 0.06 ms / 68 µs / 2; tree 10-7-60 4.35 ms / 0.61 ms / 91 µs / 50; DDD 7.07 ms / 1.07 ms / 118 µs / 85; OPT-Tree 7.76 ms / 4.24 ms / 520 µs / 363; cache hit rates 84.5%–99.3%. These are spans measured inside the SemanticTree arms; host and GPU spans overlap in time. Grammar wait exposed at verification is 49.9 µs per round for SemanticTree, versus a heavy-tailed 486.6 µs mean (50 µs median) for the original 10-7-60 tree. For the EAGLE3 10-7-60 tree (table above), time per round with SemanticTree is −6.4% to +1.7% of the original; the gain comes from more accepted tokens per round.

Online cost-aware allocation. Hong et al.'s CAST chooses the tree online from a runtime-cost model. The per-arm throughput tuning above is our offline proxy for this; combining SemanticTree with CAST itself is future work. All allocator tables are in the new Appendix I.

Load-adaptive speculation. SemanticTree also composes with SGLang's load-adaptive speculative decoding (chain-only upstream): on BFCL-multiple the gain is +8.9% to +28.7% at B = 1/16/32 for both targets, all intervals above zero; details in our response to Reviewer iudK.

Reviewer_CH7NOpenReview ↗
Rating
4(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This work proposes SemanticTree, a novel speculative decoding tree technique for incorporating constrained decoding masks from XGrammar with model based draft methods such as EAGLE3 and DDTree. Systems level solutions such as caching of state masks and CPU-GPU coordination via CUDA graphs enables throughput improvements by overcoming the overhead of masking the draft tree for valid grammar.

Critical strengths
  • Well motivated contribution with practical systems solutions. To the best of my knowledge, this is the first paper to combine grammar-aware speculative decoding with tree drafters, unlike prior work which focused on linear draft chains and drafter-free approaches. Solutions to practical challenges include sharing masks across parser states, reusing masks during validation, and coordination between CPU-GPU processes.
  • Empirical improvements are consistent and ablations prove the benefit of the proposed caching technique.
Critical weaknesses
  • The empirical results do not establish when constrained decoding of trees outperform constrained decoding of chains. It would be ideal to understand the tradeoffs and under what contexts the overhead of constrained decoding on trees outweighs a more straightforward chain based draft.
  • The memory overhead of the caching system and sensitivity to workload diversity is not established. The memory needed to sustain the mask caching under diverse serving settings is not clear.
Questions for authors
  • How does SemanticTree compare with EAGLE3 using constrained decoding during chain drafting? How does the comparison change with draft budget, acceptance rate, and concurrency? Helping readers understand where SemanticTree provides the most value would improve the work.
  • What is the capacity of the cache? What was its peak memory footprint and can it be shared across requests? Expanding on the overhead of the cache would strengthen confidence in the system’s practical scalability.
3 comments

We thank the reviewer.

Trees versus constrained chains

Short answer. (1) Trees with SemanticTree help most at low concurrency and where the constrained chain accepts few tokens per round: with each arm's best shape chosen on calibration cases, tree+ST is 5.9–10.8% faster than the best constrained chain in three of four settings. (2) With a very small budget (N = 8) or at B = 8, where verification dominates a round, a constrained chain can be faster. (3) The 4096-row mask cache takes 63–74 MiB, is shared by all requests of a server, and is robust to capacity on single-schema traffic; schema-diverse traffic at high batch favours the larger pool. (4) The extra GPU memory at large batch comes from pre-captured fallback CUDA graphs.

Four arms (chain, chain+ST, tree, tree+ST), each selecting its best shape on a calibration half; re-run on one GPU in ABCD→DCBA order and averaged per case; held-out decode gains, B = 1:

Target / workloadTree+ST vs Chain+STChain → Chain+STTree → Tree+STaccepted tokens / round: C / C+ST / T / T+ST
Qwen3-4B / BFCL-multiple+10.8% [+9.1, +12.5]+15.2%+19.8%1.66 / 1.94 / 1.76 / 2.27
Qwen3-4B / Nexus+9.7% [+7.0, +12.4]+14.7%+19.5%1.98 / 2.31 / 2.22 / 2.68
Llama-3.1-8B / BFCL-multiple+5.9% [+3.5, +8.5]+35.6%+21.9%2.12 / 3.18 / 2.60 / 3.67
Llama-3.1-8B / Nexus+2.9% [+0.0, +6.6] (all cases +4.5% [+2.3, +6.8])+16.4%+11.9%1.69 / 1.98 / 1.81 / 1.99

Calibration search: chains D = {3, 5, 7}; trees {2-3-8, 4-2-8, 4-3-16, 4-5-32, 8-5-40, 10-7-60}. Selected shapes are listed in Appendix D.1.

Same-arm drift is below 1% except for the Llama/Nexus original tree (+4.1%). In separate earlier passes, with an equal budget of N = 8 nodes (B = 1), SemanticTree trees (2-3-8 and 4-2-8) are +16.0% to +24.5% faster than a depth-7 constrained chain on Qwen3-4B and Llama/Nexus, but slower on Llama/BFCL-multiple (−3.2% for 2-3-8, −12.8% for 4-2-8). With concurrency the balance shifts: at B = 8 a fixed 4-3-16 SemanticTree vs chain+ST D3 is −6.3% / +0.4% (Qwen3-4B BFCL / Nexus) and −13.1% / −2.7% (Llama). These results are in the new Appendix D.1.

Acceptance dependence. In an earlier, separate-pass B = 1 analysis, we stratified held-out cases by the constrained chain's accepted tokens per round, using calibration tertiles. Tree+ST vs Chain+ST decode gains on Llama/Nexus were +25.7%, +2.7%, +0.7% (low/mid/high; n = 4/13/17); the low/high 95% CIs were [+9.3, +43.6]/[−3.1, +4.5]. Qwen/Nexus gave a flat +9.0%, +10.1%, +8.3%. In this observational stratification, the tree's advantage is largest where the constrained chain accepts least, and its size depends on the workload; the low Llama group has four cases.

Cache capacity, memory, and sharing

One cache per server, keyed by (grammar, parser state) and shared by all requests that use the same compiled grammar. A 4096-row mask pool takes 74.2 MiB (Qwen3-4B) / 62.6 MiB (Llama). Counting each case once, 88–93% of lookups hit on BFCL and Github_medium, where every case has its own schema, through reuse across siblings and rounds; on Nexus, whose cases share two schemas, 96–97% hit and 69–71% of lookups hit entries of other requests. Clearing the cache between requests lowers B = 1 throughput by 0.4–0.6% on BFCL and Nexus and 4.3–7.4% on Github_medium. With 64 rows, decoding is at most 1.3% slower than with 4096 rows on BFCL and Nexus, but 16–17% slower on Github_medium at B = 16/32 (Qwen3-4B). With capacity 0 (no cache) the Qwen3-4B/Nexus gain drops from +33.1% to +6.2%, consistent with the 33% → 7% ablation in Sec. 4.4. The serving process's GPU peak (nvidia-smi, SemanticTree − baseline) is about 10 MiB higher at B = 1, 0.8–0.9 GiB at B = 16 and 2.4–2.5 GiB at B = 32 (Qwen3-4B, B = 32: 98% present at server ready). In a start-up-only rerun at B = 32 (2.1 / 2.2 GiB at ready, Qwen3-4B / Llama), about 94% comes from the per-depth fallback CUDA graphs our implementation pre-captures for every batch-size bucket; disabling this pre-capture lowers the difference to about 0.13 GiB.

Multi-schema workloads. We also sent an interleaved stream of BFCL-multiple, Nexus and Github_medium requests to one server (EAGLE3 10-7-60). Counting each schema's first request, the hit rate is 90.6% / 91.4% (Qwen3-4B / Llama) with 4096 rows and 83.6% / 86.5% with 64 rows, where evictions per first request rise from 119 to 231 / 103 to 180. In this stream each case recurs three times; with 64 rows decode throughput changes by −8.6% [−19.5, −0.9] / −7.7% [−18.7, −0.2] relative to 4096 rows at B = 16 (−2.7% / −1.8% at B = 1). Capacity sensitivity therefore grows with schema diversity and concurrency; 4096 rows (~70 MiB) covers this multi-schema setting. The capacity, memory and multi-schema tables are in the new Appendix E.1.

At higher concurrency (B = 16/32), see also our scalability results in the response to Reviewer iudK.

I thank the authors for their detailed rebuttal. My original concerns have been satisfied and the positive comparisons to stronger tree allocators has convinced me that this work is worth including in the conference proceedings. Accordingly, I have raised my rating from 3 to 4.

Thank you for taking the time to revisit our paper and for your support. Your questions about constrained chains and cache overhead helped us clarify when tree drafting improves throughput and what it costs in practice.

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

This paper investigates speculative tree allocation within the context of grammar-constrained generation. It filters out grammar-invalid candidates during the tree-node selection process, ensuring that the limited verification budget is focused exclusively on valid candidates. Additionally, it employs parser-state mask caching to reduce the overhead of redundant checks. The authors integrate this approach into both EAGLE3 and DDTree. Across five distinct tool-use workloads—with a batch size of 1—this method improves the decoding throughput of EAGLE3 by 19.5–40.3% and that of DDTree by 15.5–25.6%. The paper also provides an ablation study on the cache mechanism, as well as batch-processing results for EAGLE3.

Critical strengths
  1. Given the same proposer and verification budget, both EAGLE3 and DDTree reduce the number of verification rounds and increase the effective decoding throughput. This facilitates the early pruning of invalid candidates, allowing the limited verification budget to be directed toward more progress accepted by the target model—with the added cost of these checks not outweighing the gains.
  2. The cache ablation study in Table 11 maintains a consistent tree structure and number of verification rounds, effectively isolating the benefits of tree allocation from the costs associated with obtaining grammar masks. For the Qwen3-4B/EAGLE3/Nexus configuration, the cache boosts the decoding gain from 7.4% to 32.5%, whereas it has negligible impact on the BFCL-multiple benchmark. This clarifies the specific conditions under which mask reuse contributes to actual speedups.
Critical weaknesses

My concern is how output identity has not been established affects the performance comparison. The primary comparison filters samples based on whether the output lengths of the baseline and SemanticTree are identical, though it allows for differences in the actual token sequences (Section 4.1). Matching output lengths does not guarantee identical generation paths or equivalent grammar-processing costs. While the full-sample results for EAGLE3 in Appendix B show positive gains, they lack a corresponding DDTree analysis; furthermore, there is no quantification of the extent of output divergence among the retained samples. Consequently, the impact of this filtering process on the observed gains for DDTree—as well as the root cause of the output divergence—remains unclear. While the existing checks for the cache and planner provide validation at the component level, they do not fully address these issues within the context of a complete decoder-level comparison.

Questions for authors
  1. If the output-length matching criterion (between the baseline and SemanticTree) is removed—while still using the original reference-completion filter—do the decode-throughput gains for DDTree persist? Could you provide these results, perhaps in a format comparable to the EAGLE3 analysis presented in Appendix B? As an additional sensitivity check, do the gains also hold on samples where both configurations generate identical token sequences?
  2. Among the samples retained in the primary comparison (following output-length matching), what proportion exhibit token-level output divergence? Have you examined the grammar masks and target logits for both configurations—specifically for the shared prefix leading up to the point of initial divergence—to determine whether numerical differences can account for the observed divergence?
3 comments
AuthorsOpenReview ↗

Output identity

We thank the reviewer for the precise questions on output identity.

Output identity and the length-matching filter

Short answer. (1) Without length matching, all 15 DDTree cells (and all 20 EAGLE3 cells) keep intervals above zero; the full DDTree table is below. (2) Among length-matched pairs, 51 of 4,802 (1.06%) differ in some token. (3) In every replayed divergence, both arms' grammar masks are identical up to and at the divergence, and the competing logits are within the numerical differences already present on the shared prefix.

How often outputs diverge. Across all 35 formal cells (4,909 paired cases), 4,802 pairs have equal length and 51 of them differ in some token; 107 pairs differ in length; 158 diverge in total (3.22%). DDTree diverges in 41 of 2,103 pairs (28 in length, 13 at equal length), EAGLE3 in 117 of 2,806. Of the 51 equal-length divergences, 13 swap equivalent terminators, 8 differ in whitespace or JSON punctuation, and 30 pick a different content token (a number, a boolean or a word) at a near-tie.

First-divergence replay. We replayed each divergent case with the formal server configuration and recorded, at every shared-prefix position and at the first divergence, both arms' grammar masks and raw target logits. 155 of the 158 cases were replayed (3 exceed the 60-round snapshot limit), and every replay reproduces both formal outputs token by token. In all 155, the masks are identical at every shared-prefix position and at the divergence, so the divergence arises in the target logits. In 152/155 the logit gap between the two competing tokens is at most the largest raw-logit difference already observed between the arms on the shared prefix; the other 3 exceed it by at most 0.25. This is consistent with bf16 differences between verification trees of different shapes.

DDTree without length matching (reference-completion filter kept; decode gain, paired case bootstrap, 95% CI):

TargetWorkloadall caseslength-matchedtoken-identical
Qwen3-4BBFCL-simple+15.1% [+12.7, +17.5]+15.5%+15.5%
Qwen3-4BBFCL-multiple+18.6% [+16.5, +20.8]+18.8%+18.8%
Qwen3-4BBFCL-multiturn+24.9% [+22.7, +27.1]+25.1%+25.1%
Qwen3-4BNexus+17.5% [+14.8, +20.5]+17.8%+18.0%
Qwen3-4BToolHop+21.9% [+18.7, +25.4]+23.0%+22.7%
Qwen3-8BBFCL-simple+23.1% [+21.0, +25.1]+22.8%+22.7%
Qwen3-8BBFCL-multiple+22.8% [+20.7, +25.0]+22.8%+22.8%
Qwen3-8BBFCL-multiturn+14.7% [+4.1, +23.5]+20.8%+20.8%
Qwen3-8BNexus+25.9% [+22.7, +29.2]+25.6%+25.6%
Qwen3-8BToolHop+22.3% [+19.2, +25.6]+22.3%+22.3%
Llama-3.1-8BBFCL-simple+18.5% [+16.8, +20.3]+18.5%+18.5%
Llama-3.1-8BBFCL-multiple+17.5% [+15.7, +19.3]+17.5%+17.5%
Llama-3.1-8BBFCL-multiturn+25.0% [+22.5, +27.7]+25.1%+25.2%
Llama-3.1-8BNexus+23.2% [+20.1, +26.7]+24.3%+24.3%
Llama-3.1-8BToolHop+24.7% [+21.7, +28.1]+24.7%+24.9%

All token-identical intervals are above zero as well (lowest lower bound +13.2%). Relative to the submission's length-matched cohort, dropping the filter changes the DDTree gains by −1.1 to +0.3 points in 14 of 15 cells; Qwen3-8B/BFCL-multiturn moves from +20.8% to +14.7% because 4 length-mismatched pairs widen its interval, and EAGLE3 shows the same pattern in the same cell. On the token-identical subset both arms emit exactly the same tokens, so differences in the generated path cannot account for the gain. EAGLE3 gives +19.0% to +40.0% on all cases and +19.5% to +40.0% on token-identical cases, all intervals above zero; on the 8 cells re-run with E2E timing, all-case E2E gains are +7.1% to +25.3%.

The full 35-cell table and the replay summary are in the new Appendix B.1, and the revised Sec. 4.1 reports this check next to the main comparison.

Thanks for additional experiments, answered my questions.

Thank you for following up. We’re glad the additional experiments addressed your questions about output matching, and we appreciate your suggestion to check the DDTree speedups both with the length-matching filter removed and on the token-identical subset.

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

This paper presents SemanticTree, a grammar-aware tree allocation approach for speculative decoding in structured generation. Existing tree-based speculative decoding methods construct draft trees before applying grammar constraints during target verification, leaving a substantial fraction of the tree budget occupied by candidates that cannot be accepted. SemanticTree addresses this inefficiency by filtering grammar-invalid candidates during tree construction and reallocating the available slots to valid alternatives, without changing the original proposer scores or verification budget.

Critical strengths
  1. A concrete and well-supported motivation for improving speculative tree allocation. The paper identifies a substantial source of wasted capacity in grammar-constrained speculative decoding, where 73–77% of the non-root slots in EAGLE3 trees are occupied by grammar-invalid candidates. Rather than pruning these candidates after tree construction, SemanticTree incorporates grammar eligibility into the allocation process, allowing valid alternatives to compete for the same fixed verification budget. The method preserves the proposer's original scores and does not require changes to the drafting model. The measured increase in reachable slots, from roughly 14–16 to 51–53 out of 59, is substantial. More importantly, the reduction in verification rounds shows that the additional valid candidates contribute to accepted decoding progress rather than simply increasing tree occupancy. This provides a clear motivation and a well-targeted solution to an inefficiency in structured generation.

  2. Careful treatment of grammar-processing overhead, supported by convincing experimental evidence. Moving grammar checks into drafting introduces CPU–GPU dependencies that could easily offset the benefits of better tree allocation. The paper addresses this through parser-state mask caching and separate execution designs for EAGLE3 and DDTree. The cache achieves 94.7–99.1% hit rates in the EAGLE3 experiments, substantially reducing repeated mask computation. The cache ablation is particularly useful: on Qwen3-4B/Nexus, disabling caching leaves the verification-round reduction unchanged but lowers the EAGLE3 throughput gain from 33% to 7%. This directly demonstrates why reducing grammar-processing overhead matters for the overall speedup. The consistent throughput improvements across 35 configurations, together with the additional batched-serving results for EAGLE3, provide solid evidence that the approach is effective beyond a single model or drafting implementation.

Critical weaknesses
  1. Limited novelty of the core algorithmic contribution. While the paper identifies a meaningful inefficiency in grammar-constrained speculative decoding, the proposed allocation strategy is conceptually straightforward. As described in Section 2.2, SemanticTree primarily incorporates grammar eligibility into the existing tree allocation process by assigning negative infinity to invalid candidates, while retaining the original scoring and selection mechanisms of EAGLE3 and DDTree. The idea of applying grammar constraints during speculative drafting has also been explored in prior work, although not necessarily in the same tree-based setting. The parser-state mask cache and CPU–GPU coordination mechanisms are useful engineering optimizations, but they mainly address the overhead introduced by this allocation change rather than providing a fundamentally different decoding or tree optimization strategy. Given that the paper's main contribution builds on existing speculative decoding and grammar-constrained generation techniques, the degree of conceptual novelty remains somewhat limited.

  2. Limited evaluation of the method's generality and scalability. The evaluation focuses on schema-constrained tool-call generation, with all five workloads constructed as fixed-context replays that produce a single JSON object. SemanticTree's effectiveness depends heavily on the proportion of grammar-invalid candidates and the reuse of parser states, yet the paper does not systematically examine how performance varies with grammar restrictiveness, schema complexity, or cache reuse rates. The reported gains are therefore difficult to generalize to structured generation workloads with different grammar characteristics. The main experiments also use batch size one on a single tensor-parallel rank, while the additional batched-serving results cover only EAGLE3 at batch sizes four and eight. Although these results demonstrate consistent improvements under the evaluated settings, they provide limited evidence of how the additional grammar-processing and CPU–GPU synchronization overhead would scale under higher concurrency and more demanding serving configurations. A broader evaluation of these factors would better establish the practical applicability of the approach.

Questions for authors

Please see weaknesses.

3 comments
AuthorsOpenReview ↗

Novelty and Generality

We thank the reviewer. Part 1/2: novelty and generality.

Novelty. We agree that the allocation rule is deliberately simple: grammar-illegal candidates receive −∞ and the proposer's scores and selection rules are otherwise unchanged. Keeping the rule this small is what lets it drop into different proposers, and at an unchanged verification budget it raises reachable EAGLE3 slots from 14–16 to 51–53 of 59.

We see the main contribution in the algorithm–system co-design that makes construction-time masking pay off in a tree. Guided speculation in TensorRT-LLM and DOMINO follows a single draft chain, which needs one mask per step. Tree integrations in SGLang+XGrammar and the concurrent TensorRT-Edge-LLM mask the finished tree at verification; in the SGLang+XGrammar baseline, 73–77% of non-root EAGLE3 slots then hold candidates the constrained target can never accept. Applying the grammar during construction changes the dependency structure: each depth needs the masks of up to K parents per request before the next depth can be expanded, so these masks sit on the critical path of every round, while the same parser states recur across siblings, rounds and requests. The parser-state hash, the mask cache keyed by it, mask reuse at verification and the in-graph frontier exchange (a staged host planner for DDTree) are therefore what turn saved verification rounds into throughput: with identical trees and the same 20% fewer rounds, the Qwen3-4B/Nexus decode-only gain is 33% with the cache and 7% without (Sec. 4.4).

Because proposer scoring is untouched, the same mechanism speeds up EAGLE3 (+19.5% to +40.3%) and DDTree (+15.5% to +25.6%) across 35 settings, and also DDD, DARTree, size-tuned OPT-Tree in three of four settings, and fixed and load-adaptive chains (allocators: our response to Reviewer EV1g, Part 3; scalability: Part 2 of this response). Against the best constrained chain, a tree with SemanticTree is faster in three of four settings (our response to Reviewer CH7N).

Generality: constraint strength, schema complexity, unconstrained traffic

Within workloads, the gain is associated with constraint tightness along the output and with compiled grammar size, and only weakly with schema-level counts.

  • Same prompts, only the grammar changes (EAGLE3, B = 1, a separate run): original schema +20.3% to +33.9%; relaxed schema (enum/required/const removed) +13.1% to +33.4%; any JSON object +1.2% to +3.1%. DDTree: +18.3% to +25.2% → +1.0% to +7.6%.
  • Per-case analysis over 7 JSON workloads (485 Qwen3-4B / 494 Llama cases): the gain correlates with the fraction of output positions that allow ≤ 64 tokens (Spearman +0.18 for Qwen3-4B, +0.40 for Llama; within-workload medians +0.22 / +0.38) and negatively with the median legal-token count (−0.14 / −0.45). Property count, nesting depth, enum/anyOf count and schema size have within-workload correlations between −0.13 and +0.12; compiled grammar size reaches +0.21 / +0.28.
  • Five JSONSchemaBench suites (Github_medium, Github_hard, Kubernetes, Snowplow, WashingtonPost), whose outputs are configuration, event and content documents from these sources, × two targets: all 10 all-case CIs > 0 (Qwen3-4B +11.9% to +112.6%, Llama +9.4% to +58.7%). On Github_hard, the suite with the longest outputs (≈260 tokens), all-case decode-only gains are +20.1% [+14.3, +27.9] (Qwen3-4B) and +18.1% [+15.2, +21.2] (Llama), and E2E gains +18.9% [+13.4, +26.4] / +17.0% [+14.3, +19.9]: prefill is about 4–5% of a request, so nearly all of the decode gain carries over to end-to-end throughput.

Unconstrained and mixed traffic. Requests without a grammar take the stock SGLang path, as does every batch that contains one. In a same-GPU interleaved re-test (Llama, B = 8), unconstrained traffic is −2.4% [−3.8, −1.1] / +0.8% [−2.8, +4.9] (BFCL / Nexus) and mixed traffic −2.3% [−4.5, −0.4] / +2.8% [−1.8, +8.9]. Same-arm drift between the two passes of this test reaches 6.8%, the same order as these differences. Per-row proposal selection is the next step to bring the gain to constrained requests in mixed batches. All results in this part are in the new Appendix H.

Beyond JSON, the gain follows the cost of the engine's masks (Part 2 of our response to Reviewer EV1g): on SMCalFlow Lispress, whose masks XGrammar computes in about 0.05 ms, the best SemanticTree tree is +9.4% / +40.5% faster than the best original tree (Qwen3-4B / Llama); on Spider SQL, whose uncached masks take about 20 ms under XGrammar's scannerless parsing, SemanticTree is slower.

AuthorsOpenReview ↗

Scalability and cache reuse

Part 2/2: scalability and cache reuse.

Scalability

EAGLE3 at B = 32 (4096-row cache; pooled decode throughput, one pass per setting): +20.0% / +17.9% (Qwen3-4B BFCL / Nexus), +14.0% / +6.4% (Llama), and +144% / +100% (Qwen3-4B / Llama) on JSONSchemaBench Github_medium. Github_medium is already +115% / +58% at B = 1 (pooled, from the cache-capacity runs), and at high batch its gain depends on the cache: with 64 rows instead of 4096, Qwen3-4B throughput is 16–17% lower at B = 16/32.

Tensor parallelism (TP = 2). EAGLE3 10-7-60 with the target and drafter sharded over two GPUs (PCIe), full case sets, decode-only:

Target / workloadTP = 2, B = 1TP = 2, B = 16
Qwen3-4B / BFCL-multiple+23.0% [+21.4, +24.7]+11.7% [+8.6, +14.9]
Qwen3-4B / Nexus+35.2% [+29.9, +40.4]+26.5% (3 cohorts)
Llama / BFCL-multiple+33.3% [+30.8, +35.8]+23.7% [+19.0, +28.6]
Llama / Nexus+17.7% [+12.9, +23.3]+12.5% (4 cohorts)

At B = 1 the gains are close to the single-GPU runs (+19.7% to +33.1%); across B = 1 and 16, verify rounds fall by 14–25% while time per round changes by −9.2% to +3.8%. E2E gains are +11.6% to +24.5% at B = 1. Limitation. Our GPUs (RTX 5880 Ada) have no NVLink, so TP = 2 runs over PCIe with NCCL peer-to-peer transfers disabled; absolute TP = 2 throughput is therefore lower than on NVLink systems. Both arms share this setup, so the paired gains compare like with like.

Batched DDTree (B = 16/32). We extended DDTree from B = 1 to batches, planning each request exactly as at B = 1 (510/510 B = 1 outputs identical to the original runtime), with both arms sharing the same batched implementation:

Target / workloadB = 16 decode gainB = 32 decode gain
Qwen3-4B / BFCL-multiple+7.5% [+3.7, +11.6]+4.0% [−1.0, +8.3]
Qwen3-4B / Nexus+3.8% (4 cohorts)+2.0% (2 cohorts)
Llama / BFCL-multiple+12.4% [+0.6, +23.7]+6.9% [+3.4, +10.9]
Llama / Nexus−0.2% (4 cohorts)+2.2% (2 cohorts)

Verify rounds still fall by 17%–25%, and the gain is smaller than at B = 1 in the same runtime (+18.3% to +24.6%): per-request grammar planning on the host runs single-threaded (about 11 ms median per round at B = 16), and parallelizing it is a direct engineering extension. BFCL has 12 / 6 cohorts at B = 16 / 32, and three of its four decode intervals lie above zero; Nexus has 4 / 2, so we report point estimates.

Combining with load-adaptive speculation. SGLang's adaptive speculative decoding switches the number of draft steps (0, 1, 3 or 7) at run time from the observed acceptance length, and drafts chains. We combined it with SemanticTree (our experimental implementation) and compared with a fixed 3-step chain on BFCL-multiple, decode-only:

TargetBfixed chain → +SemanticTreeadaptive → +SemanticTree
Qwen3-4B1+16.5% [+15.2, +17.8]+16.4% [+15.0, +17.8]
Qwen3-4B16+11.4% [+2.8, +20.2]+11.8% [+2.6, +21.0]
Qwen3-4B32+10.4% [+5.4, +15.7]+13.2% [+5.3, +22.9]
Llama-3.1-8B1+25.2% [+23.5, +27.0]+28.7% [+26.4, +31.1]
Llama-3.1-8B16+15.4% [+9.9, +20.5]+20.3% [+13.2, +28.9]
Llama-3.1-8B32+14.3% [+10.5, +19.1]+8.9% [+2.5, +16.3]

The two are complementary. Under load the unmodified controller falls back to short drafts (Qwen3-4B at B = 32: 0- or 1-step drafts in 77% of rounds); with SemanticTree the acceptance length stays high enough that it keeps 3-step drafts in every round. In this chain setting at B = 1, outputs with and without SemanticTree are identical on all cases.

Setting. Requests are released in synchronous cohorts of B. All B = 16/32 results are in the new Appendix D.2.

Cache reuse. Masks are cached per (grammar, parser state). Counting each case once, 88–93% of lookups hit on BFCL and Github_medium (reuse across siblings and rounds) and 96–97% on Nexus, whose cases share two schemas; clearing the cache between requests lowers B = 1 throughput by 0.4–7.4%. Full cache and memory results are in our response to Reviewer CH7N.

Dear Reviewer iudK, As the author reviewer discussion period is closing soon, we wanted to gently check whether our two-part response and new experiments have addressed your concerns on generality and scalability. We would greatly appreciate any brief feedback or remaining questions. Thank you again for your time and review.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General response

We thank all reviewers. Each question is answered in the reply to the reviewer who raised it; where reviewers share a topic, we point to the reply that holds the full answer. New experiments since submission:

  • divergence re-count and first-divergence replay for all 35 formal cells, and EAGLE3/DDTree gains without length matching and on token-identical cases (Reviewer tFdd);
  • sampling at T = 1 with kernel-level and end-to-end distribution tests, including a float32 boundary case in SGLang's verifier that is fixed upstream (Reviewer EV1g);
  • constraint-strength ladder, per-case schema-complexity analysis, five JSONSchemaBench suites, unconstrained and mixed traffic, Spider SQL with the SynCode grammar and SMCalFlow Lispress (Reviewers iudK, EV1g);
  • SemanticTree on OPT-Tree, dynamic-depth (DDD) and DARTree allocators and a per-round cost breakdown (Reviewer EV1g);
  • a four-arm chain/tree study with held-out selection, re-run interleaved on one GPU (Reviewer CH7N);
  • cache capacity 0–4096 rows at B = 1/16/32 with memory accounting, and multi-schema traffic (Reviewer CH7N);
  • EAGLE3 up to B = 32 and with tensor parallelism (TP = 2), a batched DDTree at B = 16/32, and SemanticTree combined with SGLang's load-adaptive speculation (Reviewer iudK).

Unless stated otherwise, new results use all cases whose constrained target-only reference terminates before the token cap (the submission's reference-completion filter) and keep every such case for both arms; the T = 1 runs use all cases. All new results are in the revised appendices (B.1, D.1, D.2, E.1, G, H, I), cited in each reply. The main text adds a sampling paragraph (Sec. 2.2), the output-identity check (Sec. 4.1) and Sec. 4.5 with Table 3, which summarises the new settings.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.