- 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
- 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.
- 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
- Does SemanticTree preserve the exact constrained target distribution and maintain effective under stochastic sampling?
- How does the method behave outside JSON tool calling? The evaluation lacks other grammar types, varying constraint strengths and unconstrained-generation overhead.
- 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
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.
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:
| Allocator | Qwen3-4B BFCL | Qwen3-4B Nexus | Llama BFCL | Llama 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.
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 <= massaccepts 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.
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.