acceptodds
Under review as a conference paper at ICLR 2027

State-Coarsened Future-Validity Correction for Constrained Decoding

Abstract

Grammar-constrained decoding with token masking samples from a locally renormalized distribution rather than the true grammar-conditioned distribution; on Dyck languages with GPT-2, the total-variation gap is 0.75, and single strings are over-weighted by 16 orders of magnitude. Exact correction requires the future validity of every prefix, namely the probability that the prefix can be completed legally, which is intractable in general. Practice therefore falls back on heuristics such as flattening schemas or avoiding deep nesting, without knowing whether a cheap correction is sufficient for a given schema. We replace this rule of thumb with an a priori computable criterion. We estimate future validity using a lookup table coarsened onto automaton states and remaining budget, rather than exact prefixes, and derive an exact identity that prices the resulting approximation. The identity expresses the KL divergence as a sum of per-step Jensen gaps caused by uneven relative estimation error; its second-order form shows that the residual cost is the target-weighted within-state variance of log future validity, while the optimal table entry is a target-weighted geometric mean. We map this criterion across grammar families and model scales, showing that scale does not substitute for the right state features. With a shared budget of masked rollouts, the state-level table is stably better than a prefix-level table once the budget reaches 100 rollouts, while generalizing to unseen prefixes at zero additional forward passes per step. On full-scale models, the correction adds no per-token forward passes and preserves downstream accuracy while improving sequence log-probability where the table is applicable. On content-dependent schemas, the identity predicts exactly where coarse tables stop helping and a learned content-aware correction is required. The same identity unifies several reported finite-sample failures: slow and non-monotonic convergence in ASAp, importance-weight degeneracy in our estimator ablation and AWRS, and zero-estimate collapse in rare-event twisted sequential Monte Carlo. Finally, the correction composes with grammar-masked speculative decoding at no extra cost, achieving 3.6–4.5 times fewer verifier forward passes per token while inheriting the same failure boundary.

Primary area:
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords:
constrained decoding, grammar-constrained generation, future validity, Doob transform, masking bias, JSON Schema, speculative decoding

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_54YFOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

The paper studies the distributional bias of grammar constrained decoding, where token masking samples from the locally projected distribution rather than the true grammar conditional one. Building on the future validity viewpoint of Nie et al. (2026), it derives an exact per step error identity for any approximate future validity estimator, specializes it to estimators coarsened onto automaton states indexed by parser state and remaining budget, and uses a second order expansion of that identity as an a priori criterion for whether a cheap state level correction suffices for a given grammar. Validation spans exactly enumerable toy grammars, budgeted JSON tasks on models from 135M to 1.7B, a subset of real JSONSchemaBench schemas up to Qwen3-8B, and a speculative decoding composition study with a 135M drafter and a 1.7B verifier.

Critical strengths

First, the theory is done carefully and reported honestly, which is rarer than it should be. The per step Jensen gap identity is verified numerically to machine precision, the failures are reported rather than buried, and the appendix engineering, including the equivalence tests that pin what may change in the sampler implementation, is a model of how to report systems work. Second, the scale analysis is genuinely informative: the coarsening gain is non monotone in model size, the semantic featurization improves monotonically from 135M to 7B, and the taxonomy of distribution correcting decoders as future validity estimators in Section 5 is clean and useful pedagogy for the field.

Critical weaknesses

1、First, and decisively, the method fails exactly where the paper claims it matters, and the paper's own numbers say so. On content dependent schemas the state lookup degrades total variation to 1.000, meaning disjoint support, at every scale, while accuracy barely moves (Table 4). On real JSONSchemaBench schemas the aggregate TV gets worse from masked to corrected at all three scales (0.640 to 0.931, 0.607 to 0.757, 0.508 to 0.696), and the correction helps on only 3 of 15, 6 of 15, and 3 to 5 of 15 schemas. At Qwen3-8B, the largest model tested, the headline improvement in sequence log probability is statistically unchanged. So on the toy grammars where the correction works nobody urgently needed it, and on the real schemas where practitioners would want it the method hurts more often than it helps. Framing this as the criterion working as designed is generous to the point of being backwards: a criterion whose main practical output is do not use this method is a diagnostic, not a solution, and it is not what the abstract advertises.

2、The deployment story compounds this: latency is measured with a 135M drafter and a 1.7B verifier on V100s, a serving configuration from years ago, which undercuts the production framing of the introduction.

3、Third, the novelty and the comparative evidence are thinner than the presentation suggests. The future validity viewpoint, the Doob transform formulation, and the endpoint analysis all come from the (Nie et al., 2026), which is cited throughout; what remains new here is the middle segment, namely coarsening onto automaton states, a per step Jensen gap identity, and the geometric mean table. The identity is a standard telescoping decomposition of the KL between two path measures plus a second order expansion, and Theorem 1 is essentially moment matching. This is competent craftsmanship, but it is the natural next increment of the prior work rather than a qualitatively new idea. The a priori claim also does not survive inspection: estimating the within state variance of log Phi requires the same masked rollouts used to build the table, stabilizing only around N of 100 or more, at which point one could directly measure the corrected TV on held out rollouts and skip the identity. And the main comparative claim rests on beating the authors' own offline reimplementation of ASAp's estimand, explicitly not its online loop, with mean fallback on unseen prefixes; there is no comparison on the real schemas against any actually strong corrector, which is precisely where the state table fails and where a comparison would be informative.

4、The evaluation is also self referential throughout: every fidelity metric is distance to mu star, exactly computable only on enumerable toy languages, and on real schemas the metric collapses to TV of the output length marginal against a self normalized IS reference built from the same 200 masked samples. The paper's own observation that accuracy is preserved while TV degrades begs the question it never answers: does any user visible quantity improve when the bias is corrected? No downstream utility, calibration benefit, or human facing metric appears anywhere.

5、Last but not least, you used GPT-2 for experiment. Are you kidding me? Today is 2026!

Questions for authors
  1. On the 15 schema JSONSchemaBench subset, for the majority of schemas where the lookup does not help, can you name one realistic deployment scenario where your corrected sampler beats masking on every aggregate metric that scenario cares about?
  2. How much of the Table 2 margin over the prefix table survives if the prefix baseline is given the same smoothing and fallback tuning you afford your own table, and if it is allowed to key on parser states plus a bounded suffix window rather than exact prefixes?
  3. Can you show a single downstream task where correcting the sampling law changes a decision a user would make, at any scale at or above 7B?
Reviewer_5d8hOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

Grammar-masked decoding samples μproj\mu_{\text{proj}}, not the grammar-conditioned \mu^. The exact fix reweights each step by future validity Φ(y)\Phi(y), which is intractable. The paper estimates Φ\Phi as a lookup table keyed by automaton state and remaining budget, built offline from masked rollouts, so it costs no extra forward passes at decode time. Its main theoretical tool is an identity: KL(μ∣q)\mathrm{KL}(\mu^|q) equals a sum of per-step Jensen gaps of r=Φ/Φ^r=\Phi/\hat\Phi. To second order, this is the μ∗\mu^*-weighted within-state variance of log⁡Φ\log\Phi. The paper offers this as an a priori criterion for when a state table is enough. Experiments cover toy grammars (exact TV with GPT-2), a scale sweep up to 8B, a comparison with a prefix-keyed table, budgeted, nested and long JSON, JSONSchemaBench, speculative decoding and an xgrammar integration.

Critical strengths

Viewing approximate correctors through Φ\Phi, together with the within-state-variance explanation (Fig. 1, Table 6), is a clean way to understand when cheap corrections work. Dyck (TV 0.900 → 0.0011) and SQL with a semantic feature (0.322 → 0.034) show the idea working where Φ\Phi depends only on the state.

Critical weaknesses
  1. The theory is the KL chain rule, and the "a priori" claim is overstated. Per-step KL(μ(⋅∣y)∣q(⋅∣y))=log⁡Er−Elog⁡r\mathrm{KL}(\mu^(\cdot|y)|q(\cdot|y)) = \log\mathbb{E}r - \mathbb{E}\log r follows directly from the definition of qq. The variance form and the geometric-mean optimum are standard second-order facts. The criterion also requires the \mu^-weighted variance of the true log⁡Φ\log\Phi, which is the quantity that is intractable. The paper concedes it must be estimated (App. D), and the geometric-mean estimator does worse than the arithmetic mean at realistic budgets (§4.5). So the criterion is not computable before decoding in any practical sense.

  2. The method rarely helps on realistic workloads. It makes nested and long JSON worse at every scale (Table 4: TV goes to 1.000, and accuracy falls from 0.99 to 0.67 at 1.7B). It helps on only 3–6 of 15 JSONSchemaBench schemas, and aggregate TV gets worse. At 8B, log-probability is unchanged, and at 135M accuracy drops (Table 3). The speculative-decoding speedup is standard masked speculative decoding (spec-strict leaves the bias unchanged), so it is not a contribution of the correction. Reported TVs are marginals over length or element count, not sequence-level.

Questions for authors

Can the criterion be estimated from the same NN masked rollouts, with an error bar, and does it correctly predict the 15 JSONSchemaBench outcomes (help vs. hurt) before decoding? Classification accuracy on those schemas would directly support the main claim.

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

This paper studies the distributional bias of token masking in grammar-constrained decoding. Masking renormalizes over legal tokens at each step. It ignores whether a prefix can still be completed legally. So the sampled law deviates from the grammar-conditioned target. The exact fix reweights each step by the future validity Φ. Φ(y) is the probability that prefix y can still be completed legally. Φ is intractable per prefix. The authors coarsen Φ onto automaton states. They build a lookup table offline from masked rollouts. At decode time the table adds a logit bias with zero extra forwards. The core contribution is an exact error identity. The residual KL equals the within-state variance of log Φ. This gives a pre-decoding criterion for when the lookup suffices. Experiments verify the identity to machine precision. On a 49k-vocabulary JSON task the state table beats prefix-level tables at N≥100. On content-dependent schemas the predicted failures are confirmed.

Critical strengths
  1. The theoretical core is strong. The paper gives an exact error identity: with an estimated Φ̂, the KL to the target equals the sum of per-step Jensen gaps of the error ratio Φ̂/Φ; to second order the residual is the within-bucket variance of log Φ. This makes "is a cheap correction enough" computable before decoding. The identity holds to machine precision on four grammars and unifies prior failures such as ASAp's slow convergence and AWRS's ESS collapse. This is the main reason for my score above the acceptance line.

  2. The empirics are honest and the method deploys. The lookup adds zero extra forwards and plugs into unmodified xgrammar via the vLLM/SGLang logits hook at ~1% overhead. On a 49k-vocabulary budgeted JSON task the state table beats a budget-matched prefix table in every seed at N≥100. The paper reports its own failure region (3–6/15 schemas on JSONSchemaBench) and certifies latency optimizations by distribution-equivalence tests (max gap 5e-12). Per-seed reporting with negative results raises my trust in the claims.

Critical weaknesses
  1. The practical payoff is not demonstrated. On JSONSchemaBench the lookup helps on only 3 to 6 of 15 schemas, and aggregate TV worsens at all three scales. The paper conjectures that function-calling-style traffic lies inside the applicable boundary but never tests it. The contribution stops at "which schemas can be corrected" and lacks "how much is corrected on real traffic".

  2. The a-priori criterion is only half delivered. The gate's variance comes from the same pilot rollouts that build the table, so it is self-checked. E12 and E14 give no per-schema gate values, and the failure boundary is confirmed post hoc by ΔTV. Moreover the gate measures only within-pilot variance. If the online distribution drifts from the calibration distribution, the table is biased as a whole while the gate still passes, and the failure is silent.

Questions for authors
  1. E12 and E14 report no per-schema gate values. Can you provide, for each JSONSchemaBench schema, the pilot gate value alongside the observed ΔTV, and state whether the gate's pass/refuse decision matches the observed help or harm? This decides whether the a-priori criterion is validated on real schemas or only matched post hoc.

  2. The paper conjectures that function-calling-style traffic lies mostly inside the applicable boundary but never tests it. Can you report results on BFCL, xLAM, or Spider, or break JSONSchemaBench down by enum/boolean property fraction, to show what share of real traffic is inside? This determines the method's actual payoff range.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.