acceptodds
Under review as a conference paper at ICLR 2027

Does a Grammar-Constrained Speculative Verifier Sample the Conditional Law? Fidelity Bounds, Numerical Paths and Exact Acquisition

Abstract

A speculative verifier samples whatever target it is supplied, so grammar-constrained speculative decoding samples the model's grammar-conditional law only if the verifier receives the future-validity-corrected target of grammar-aligned decoding. We measure what an implemented stochastic verifier actually samples once that target is supplied, on finite canonical JSON events whose conditional law is enumerated exactly. In a Qwen3-8B/DFlash block verifier, simultaneous 95% bounds place the terminal law within 0.028 total variation (TV) of the conditional law on four events, removing at least 88% of each masking gap; a registered chain-draft verifier and a second target, Qwen3-14B, reach the same conclusion, and a crossed dtype × execution-path family places every rejection in the bf16 native block forward. We show that the masking gap is the relative dispersion of the legal mass along sampled paths and cannot exceed one minus the event's probability. On 25 matched events, stating the schema in the prompt lowers the median gap from 0.28–0.48 to 0.009–0.051, and across instances the gap follows the visit-weighted dispersion of future validity. The correction itself costs the verifier 0.03 per-position acceptance. To acquire the target exactly, we prove that bounds from acquired rows alone certify a resolved-leaf sampler to within a factor two of the best terminal guarantee those rows allow once valid mass is resolved, and that draft span proposals sample the conditional law for every reachable cache state; adaptive exact samplers need as little as 0.019 of full enumeration's wall clock, and span proposals save target forwards when each forward recomputes a long prompt.

Primary area:
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords:
speculative decoding, grammar-constrained generation, distribution fidelity

Reviews

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

This paper finds that a grammar-constrained speculative verifier matches the grammar-conditional law only if it is given the future-validity-corrected target. It supplies that corrected target to real verifiers and gives exact ways to acquire it from cached probability rows and draft spans. On enumerated JSON tries, an fp32 verifier cuts mean terminal total variation from 0.355 to 0.0072, at a cost of about 0.03 in acceptance.

Critical strengths
  1. The experiments are well designed.
  2. The paper content is very rich.
Critical weaknesses
  1. The writing is unclear, verbose, and difficult to follow. Please simplify the paper, highlight the core contributions, and revise the manuscript throughout.

  2. The authors do not compare accuracy. The base model’s preferences may themselves be wrong, so correcting the sampler toward the conditional law does not necessarily make the outputs more accurate.

  3. The speedup setup in Section 5.2 is not realistic. KV cache is enabled in any real online serving system.

  4. The evaluation uses small, closed answer sets rather than JSON in the usual sense. The models are also too small for the results to be convincing.

  5. Relatedly, these small models have weak instruction following. On a larger LLM, stating the constraint in the prompt may already be sufficient.

Questions for authors

Please see weakness

2 comments
AuthorsOpenReview ↗

Response to Reviewer QeUz (1/2)

Thank you for these questions. We added the experiments reported below and revised the manuscript; table and proposition numbers refer to the accompanying revision.

“The authors do not compare accuracy…” The paper's claims concern which law a verifier samples, the grammar-conditional law being the model's own preference given validity; we now measure what that choice does to accuracy. On a fixed sample of 3,000 MMLU-Pro test questions (up to ten options, gold labels from the dataset) we enumerate for every question-event pair the exact conditional law and the exact masked law of Qwen3.5-9B, so accuracy under either law carries no sampling noise. Outputs are JSON objects: the option letter (S1), the option text (S2; 2,999 questions), and a letter-plus-text object (S3). When the format is enforced but not stated, the laws separate (median gap 0.048–0.305; a share 0.77 of questions with a gap of at least 0.10 on S3), and accuracy under the conditional law minus accuracy under the masked law is +0.2 points on S1, +3.9 points (95% interval +3.2 to +4.6) on S2 and -7.9 points (95% interval -8.8 to -7.1) on S3. Section 5.3 gives the mechanism on S3: the masked law decides at the option letter, since the text that follows is forced, and so has the accuracy of S1, while the conditional law also weighs each option by the probability of its text. When the prompt states the format, the median gap is 0.0000–0.0019 and accuracy differs by -0.49 to +0.78 points, and on S2 and S3 a share 0.05–0.11 of questions keeps a gap of at least 0.10. So without the format stated the choice of target moves accuracy by several points on S2 and S3, and the corrected verifier fixes which of two measurably different laws the decoder samples. Section 5.3 and Table 6 report this and the introduction now states the distinction.

“The speedup setup in Section 5.2 is not realistic…” We ran the timing matrix of Section 5.2 with the prompt state cached: all 224 histories, each timed in seven arm-order rotations (1,568 timed runs), 8 events, 7 samplers, a Qwen3.5-9B target with a Qwen3.5-0.8B draft (Table 4). At supports 64 and 256 the faster of CARS and Spec-4 needs 0.034–0.639 of the enumeration wall clock (0.019–0.655 in the submitted, uncached matrix, now Table 29). In every cell of this matrix Spec-4 needs fewer target forwards than CARS, 20–24 against 66–74 at support 256 with the long prompt and 16 outputs (Table 31), and it needs 0.25–1.00 times those of CARS when the submitted pair, Qwen3-8B with Qwen3-1.7B, runs through the same cached interface (Section 5.2). On 200 MMLU-Pro S2 and S3 events with the format stated (first 100 questions, Qwen3.5-9B with Qwen3.5-0.8B, 1 and 16 outputs, same cached interface), Spec-4 is faster than CARS in 390 of 400 cells, with a median wall-clock ratio of 0.44 (Appendix C.8, Table 33). On the eight events of Table 4, the Spec-4/CARS wall-clock ratio in the long-prompt cells is 0.892–1.471 in the cached matrix (Table 4), where the submitted table had 0.568–1.095 (Table 29), and 0.764–1.290 for the submitted pair through the cached interface (Section 5.2).

(Continued in comment 2/2.)

AuthorsOpenReview ↗

Response to Reviewer QeUz (2/2)

(Continued from comment 1/2; table and proposition numbers refer to the accompanying revision.)

“small, closed answer sets… The models are also too small…” At 27B the two laws remain separated. On Qwen3.8-27B, on the same 3,000 MMLU-Pro questions (2,999 for S2) and without the format stated, a share 0.33 of questions on S2 and 0.70 on S3 has a gap of at least 0.10 (median gap 0.057 and 0.175), and accuracy under the conditional law minus accuracy under the masked law is +4.6 points (95% interval +4.0 to +5.3) on S2 and -9.3 points (95% interval -10.0 to -8.5) on S3, the same directions as on Qwen3.5-9B (+3.9 and -7.9); on S3 the mechanism is that of Section 5.3, the masked law deciding at the option letter, with the accuracy of S1 (53.4%), while the conditional law also weighs each option by the probability of its text (Appendix C.8, Table 34). Each benchmark question defines three JSON events over up to ten options: the option letter, the option text, and both (Section 5.3); the largest event run through the verifier has 2,000 strings (Table 3), and the gap is computed analytically on Dyck events of up to 132,867 strings on real models (Appendix C.2, Table 21). Finite events are what give an exact reference: on tries A–D the terminal law of the implemented verifier has simultaneous 95% upper bounds of 0.013–0.028 on its distance from the conditional law (Table 3).

“On a larger LLM, stating the constraint in the prompt may already be sufficient.” Stating the constraint leaves a measurable gap. With the schema stated, six cells keep gaps of 0.11–0.41 on Qwen3-8B (Appendix B.2, Table 19) and of 0.014–0.150 on Qwen3-14B (Appendix B.3, Table 20), 2–4 of 25 events per prompt keep gaps of at least 0.10 on Qwen3-8B and on Qwen3.5-9B (Table 9), and on the benchmark events with the format stated a share 0.05–0.11 of questions keeps a gap of at least 0.10 on S2 and S3, where the median gap is 0.0019 and 0.0004, on Qwen3.5-9B (Section 5.3, Table 6); on Qwen3.8-27B with the format stated, a share 0.054 of questions on S2 and 0.027 on S3 keeps a gap of at least 0.10 (Appendix C.8). Proposition 5 gives the mechanism. On these dead-end-free finite tries, the gap equals half the mean absolute relative deviation, over paths sampled under the masked law, of the legal mass collected along a path, and it is at most one minus the probability of the event, so it is zero when every such path collects the same legal mass. The paper's result is the criterion and its measurement: it tells when stating the constraint suffices and when it does not.

“The writing is unclear, verbose, and difficult to follow.” In the revision, Figure 1 gives the pipeline. The estimator hierarchy has moved to Appendix C.4, so Section 4 concentrates on what acquired rows certify (Propositions 8 and 9), with the terminal-law bounds collected in Corollary 10. Section 5 answers three questions in order: what an implemented verifier samples (5.1), what exact acquisition costs with a cached prompt (5.2), and when the two laws differ and what that does to accuracy (5.3). The core contributions are the three numbered items of Section 1, and Table 1 maps each main result to its event, reference law, sampler, statistical unit and cost measure.

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

This paper investigates the theoretical and empirical fidelity of grammar-constrained speculative decoding. The authors point out that standard local vocabulary masking (used in structured generation) distorts the underlying model's true conditional distribution, introducing a measurable "masking gap." To address this, the paper analyzes the necessity of "future-validity-corrected targets" (incorporating future legal path probabilities) and evaluates whether an implemented stochastic verifier can accurately sample the true grammar-conditional law.

Critical strengths

Identifies an overlooked gap. Speculative decoding preserves only its supplied target, so grammar masking samples the masked law, not the conditional law. The paper makes this explicit and shows the gap is large.

Clear theoretical analysis. The gap is characterized as path-mass dispersion and bounded by 1-Pr(C), with error certificates and hardness results explaining when the correction matters.

Critical weaknesses

Lack of Baselines: Missing comparisons against state-of-the-art grammar-constrained decoding acceleration baselines (e.g., standard speculative decoding with local masking, alternative structured generation frameworks).

Missing Downstream Task Evaluation: The experiments are restricted to toy canonical JSON events and lack evaluation on standard, real-world benchmarks (such as code generation or structured extraction datasets) to demonstrate practical utility.

Over-head vs. Benefit Trade-off: While the future-validity correction provides theoretical fidelity, the computational overhead of acquiring and enforcing these weights is not convincingly justified on realistic generation tasks.

Questions for authors

The evaluation is exclusively restricted to micro-benchmarks (canonical JSON tries). Why are there no evaluations on other standard structured generation tasks, such as programming code or SQL generation?

Missing Global Error Bounds: The paper relies on local leaf certificates but lacks a formal global error bound for the corrected sampler. Can the authors theoretically guarantee that cumulative errors remain controlled?

2 comments
AuthorsOpenReview ↗

Response to Reviewer 33TX (1/2)

Thank you for these questions. We added the experiments reported below and revised the manuscript; table and proposition numbers refer to the accompanying revision.

“Lack of Baselines…” SchemaTV is our implemented local-masking speculative baseline (Table 2): the same verifier with the masked target. On tries A–D the masked law it samples is 0.19–0.62 in total variation from the conditional law, and supplying the corrected target lowers the mean terminal TV from 0.355 to 0.0072, with per-position acceptance going from 0.887 to 0.855. Local-masking implementations with the same target rows, masks, stopping rule, and sampling settings sample the same masked law, so this baseline represents grammar-masking frameworks such as XGrammar and Outlines run under those settings. Table 5 adds a cost comparison under one accounting with six implementations: masked autoregressive decoding, masked speculative decoding, CARS, Spec-4, suffix-shared enumeration and batched enumeration, all through one row interface with the prompt state cached, on the eight events of Table 4 and two model pairs. The masked and the exact arms run the same sampler code: the masked arms receive locally renormalized rows (needing no row at a single-child node) and the exact arms receive absolute rows. CARS takes 1.07–2.98 times the wall clock of masked autoregressive decoding and 1.07–4.60 times its target forwards; Spec-4 takes 0.90–1.67 times the wall clock of masked speculative decoding; batched enumeration takes 0.20–6.47 times that of masked autoregressive decoding.

“Missing Downstream Task Evaluation… Why are there no evaluations on other standard structured generation tasks, such as programming code or SQL generation?” We evaluate on finite events rather than unrestricted code or SQL outputs because a finite event can be enumerated into an exact reference law, so every fidelity statement is checked against exact values: the distance of an implemented verifier's terminal law from the conditional law has simultaneous 95% upper bounds of 0.013–0.028 on tries A–D (Table 3). The added benchmark with gold labels, MMLU-Pro with JSON outputs (Table 6), applies the same exact enumeration to a standard task. The guarantees hold under the paper's bounded-stopping assumptions, including events that are unions of tokenizations. On a fixed sample of 3,000 questions (2,999 for the option-text event) we enumerate the exact conditional and masked laws of Qwen3.5-9B and compute accuracy under each. With the format enforced but not stated, the median gap is 0.048–0.305 and accuracy under the conditional law minus accuracy under the masked law is +3.9 points (95% interval +3.2 to +4.6) on the option-text event and -7.9 points (95% interval -8.8 to -7.1) on the letter-plus-text object. Section 5.3 gives the mechanism on the letter-plus-text object: the masked law decides at the option letter, since the text that follows is forced, while the conditional law also weighs each option by the probability of its text. With the format stated in the prompt the median gap is 0.0000–0.0019 and overall accuracy differs by -0.49 to +0.78 points, and a share 0.05–0.11 of questions keeps a gap of at least 0.10 on the option-text and letter-plus-text events. Without the format stated, the choice of target therefore changes accuracy on these two events by several points.

(Continued in comment 2/2.)

AuthorsOpenReview ↗

Response to Reviewer 33TX (2/2)

(Continued from comment 1/2; table and proposition numbers refer to the accompanying revision.)

“Over-head vs. Benefit Trade-off…” The measurements quantify both sides. The benefit is the masking gap that the correction removes: 0.19–0.62 on tries A–D, a median of 0.465 on twenty unseen schemas whose prompts do not state the schema (Section 5.3), and a median of 0.048–0.305 on the MMLU-Pro events without the format stated; with the format stated, a share 0.05–0.11 of questions keeps a gap of at least 0.10 on the option-text and letter-plus-text events. The cost to the verifier is 0.03 of per-position acceptance. The cost of acquiring the target exactly was measured on the eight events of Table 4: CARS takes 1.07–2.98 times the wall clock of masked autoregressive decoding (Table 5), and the faster of CARS and Spec-4 needs 0.034–0.639 of the enumeration wall clock at supports 64 and 256 (Table 4). Proposition 8 certifies the approximation error of the midpoint-corrected kernel from the acquired rows.

“Missing Global Error Bounds…” The bound is Theorem 6(c). For the laws over complete sequences, the total variation between the sampler with estimated future validity and the conditional law is at most the sum over steps of the expected per-prefix term min{1, δ̄_t/Φ̄_t}, taken along the sampler's own prefixes, with a charge of one at a prefix that has zero probability of acceptance under p. It bounds the terminal law, not a single step. Corollary 10 of the revision collects the versions that use acquired rows. For the midpoint decoder of Proposition 8, each certificate b_t is computed from the rows acquired at its state, without knowledge of Φ, and the expectation of their sum over the decoder's states bounds the terminal law. If in addition the numerical verifier satisfies TV(K_t, q_t) ≤ e_t at every reachable state, then TV(K, μ*) ≤ min{1, Σ_t E_K[min{1, e_t + b_t}]}. For a fixed prefix-closed set of acquired rows with L > 0, the resolved-leaf sampler has terminal error at most R/(L+R). Under the additional assumptions of Proposition 9 (a non-empty unqueried frontier, no further queries, and an out-of-event exit at every non-terminal prefix), any sampler that uses only those rows and the topology has worst-case error at least half of that certificate; with an empty frontier the resolved-leaf sampler is exact. The certificate R/(L+R) is never violated on 180 query traces on the twenty unseen schemas and 150 panel traces.

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

This paper investigates whether grammar-constrained speculative decoding produces samples that faithfully follow the language model's conditional distribution over valid outputs, as well as the computational cost of achieving exact sampling. To address this problem, the authors propose Spec-4, which enables exact sampling with relatively low computational overhead.

Critical strengths
  1. The paper systematically investigates the sampling fidelity of combining Grammar-Constrained Decoding (GCD) with Speculative Decoding (SD) from three perspectives: theoretical analysis, empirical verification, and computational efficiency. The study is novel and comprehensive.

  2. The experimental evaluation is extensive, covering multiple estimation methods and reporting a range of statistical metrics to assess sampling fidelity.

  3. Building on CARS, the proposed Spec-4 preserves exact sampling from μ* across different reachable cache states, even when the cache is updated between sampling attempts.

Critical weaknesses
  1. Limited efficiency evaluation with KV caching. The efficiency evaluation of Spec-4 does not incorporate KV caching. Although the authors provide a modeled cost analysis, experiments with actual KV caching would strengthen the evaluation, as the speedup over CARS may diminish when prefix computations are reused.

  2. Limited generalizability of the experimental setting. The verifier fidelity experiments focus on finite sets of valid JSON strings and typically retain only one canonical tokenization per string. It remains unclear whether the findings generalize to more complex grammar-constrained decoding scenarios with larger or potentially infinite valid-output spaces and multiple valid tokenizations.

  3. Lack of a framework overview. The paper does not include an overview figure illustrating the workflow of Spec-4. A clear framework diagram would help readers better understand the proposed method and its differences from CARS.

Questions for authors

Please refer to the weaknesses above.

1 comment
AuthorsOpenReview ↗

Response to Reviewer fttR

Thank you for these questions. We added the experiments reported below and revised the manuscript; table and proposition numbers refer to the accompanying revision.

“Limited efficiency evaluation with KV caching…” We ran the timing matrix of Section 5.2 with the prompt state cached: 224 histories, each timed in seven arm-order rotations (1,568 timed runs), 8 events, 7 samplers, a Qwen3.5-9B target and a Qwen3.5-0.8B draft (Table 4; the submitted, uncached matrix is now Table 29, and both use the same statistic). At supports 64 and 256 the faster of CARS and Spec-4 needs 0.034–0.639 of the enumeration wall clock (0.019–0.655 in the uncached matrix), and Spec-4 is faster than enumeration in 11 of 16 cells (12 of 16 in the uncached matrix). Spec-4 batches a span into one target forward: 20–24 target forwards against 66–74 for CARS at support 256 with the long prompt and 16 outputs, and 0.25–1.00 times those of CARS when the submitted pair, Qwen3-8B with Qwen3-1.7B, runs through the same cached interface (Section 5.2). On 200 MMLU-Pro option-text and letter-plus-text events with the format stated (first 100 questions, Qwen3.5-9B with Qwen3.5-0.8B, 1 and 16 outputs, same cached interface), Spec-4 is faster than CARS in 390 of 400 cells, with a median wall-clock ratio of 0.44 (Appendix C.8, Table 33); its exactness for every reachable cache state (Proposition 12) is unchanged. On the eight events of Table 4, the Spec-4/CARS wall-clock ratio in the long-prompt cells is 0.892–1.471 in the cached matrix (Table 4), against 0.568–1.095 in the uncached matrix (Table 29), and 0.764–1.290 for the submitted pair through the cached interface (Section 5.2).

“Limited generalizability of the experimental setting…” The stated guarantees apply under the paper's bounded-stopping assumptions, including events that are unions of tokenizations (Section 3). The JSON experiments use one canonical tokenization per string so that the conditional law can be enumerated, and Appendix G reports the share of non-canonical tokenizations among sampled event hits for the three models of its three-layout study (Table 36). On size, the largest event run through the verifier has 2,000 strings (Table 3) and 2,232 non-terminal prefixes (Section 5.1); beyond JSON, the gap is computed analytically on Dyck events of up to 132,867 strings on real models (Appendix C.2, Table 21) and exactly on regular events of up to 614,429,672 strings under an iid Bernoulli base model, where the exact correction recovers the conditional law (Table 27). The revision adds benchmark events built from MMLU-Pro: three JSON events per question over up to ten options (the option letter, the option text, and both), on a fixed sample of 3,000 questions (2,999 for the option-text event; Section 5.3, Appendix C.8). On Qwen3.5-9B the median gap between the masked and the conditional law is 0.048–0.305 without the format stated in the prompt and 0.0000–0.0019 with it (Table 6), and with the format stated a share 0.05–0.11 of questions keeps a gap of at least 0.10 on the option-text and letter-plus-text events. On Qwen3.8-27B, without the format stated, a share 0.33 of questions on the option-text event and 0.70 on the letter-plus-text event has a gap of at least 0.10 (Appendix C.8, Table 34).

“Lack of a framework overview…” Figure 1 of the revision is an overview with four parts: the event and its trie; the target supplied to the verifier, masked or corrected; how the corrected target is acquired, by a full table, by CARS, or by Spec-4 span proposals inside CARS; and the accept/residual verification step with the terminal law it produces. Spec-4 differs from CARS in one place: where CARS acquires one row and draws one token, Spec-4 proposes up to four tokens from the draft and verifies them against the rows of one target forward (Algorithm 1).

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.