State-Coarsened Future-Validity Correction for Constrained Decoding

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.