Future Validity is the Missing Statistic: From Impossibility to $Φ$-Estimation for Grammar-Faithful Speculative Decoding

• URL: http://arxiv.org/abs/2605.07698v1
• Date: Fri, 08 May 2026 13:08:18 GMT
• Title: Future Validity is the Missing Statistic: From Impossibility to $Φ$-Estimation for Grammar-Faithful Speculative Decoding
• Abstract summary: Grammar-constrained generation is often combined with local vocabulary masking and speculative decoding.<n>We show that any speculative decoder with local mask access, Leviathan rejection, and rollback soundness samples from the locally projected distribution $mathrmproj$ rather than the grammar-conditional distribution $star$.
• Score: 21.074583041375888
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Grammar-constrained generation is often combined with local vocabulary masking and speculative decoding, but the resulting sampling law is not the grammar-conditional distribution users usually intend. We show that any speculative decoder with local mask access, Leviathan rejection, and rollback soundness samples from the locally projected distribution $μ^{\mathrm{proj}}$ rather than the grammar-conditional distribution $μ^\star$. This extends the GAD impossibility result to speculative decoding; on Dyck grammars with Qwen3-8B, the total-variation gap can reach 0.996. We identify the future-validity function $Φ_t(y)=\Pr_p[\mathrm{valid\ completion}\mid y]$ as the missing correction statistic. The target distribution is a Doob transform of the base model with $h=Φ$, while local masking corresponds to setting $h$ to one. With exact $Φ$, our oracle decoder FVO-Spec samples exactly from $μ^\star$; with approximate $Φ$, we bound the resulting total-variation error. Because exact future validity is hard for general context-free grammars, we evaluate estimator hierarchies on tractable Dyck and finite JSON languages. OneStep reduces Dyck TV by 14% with under 1% throughput overhead, exact dynamic programming reduces it by 97%, and finite-language correction closes JSON gaps to numerical precision. All fidelity claims are scoped to enumerable grammars and token tries.

Related papers

• Drift Variation Autoencoder: Unifying Generation and Representation Learning through Conditional Posterior Flow Matching [0.0]
  This work takes the corresponding posterior $P(Xmid C)$ as the common statistical object for conditional generation.<n> Drift Variation autoencoder trains a masked encoder $Z=E(C)$ and a conditional flow decoder with one clean-prediction Flow Matching loss.
  arXiv  Detail & Related papers  (2026-08-25T20:38:50Z)
• The Parser Already Knows: Lightweight Bias Correction in Constrained Decoding [30.042720796822085]
  Grammar Constrained Decoding (GCD) forces Language Models (LMs) to produce syntactically valid outputs by masking out non-conforming tokens at each step.<n>Online sampling restores this distribution, but it requires computationally expensive iterative resampling.<n>We propose a lightweight, offline-trained logit correction conditioned on this syntactic and lexical state together with candidate next tokens.
  arXiv  Detail & Related papers  (2026-08-10T18:52:43Z)
• Correction and Corruption: A Two-Rate View of Error Flow in LLM Protocols [51.56484100374058]
  We propose a paired-outcome measurement interface for auditing a single protocol step on exact-match tasks.<n>For each instance, the interface records a baseline correctness bit and a post-step correctness bit.<n>These rates predict accuracy changes and define a reusable empirical interface testable across seeds, mixtures, and pipelines.
  arXiv  Detail & Related papers  (2026-04-20T13:25:40Z)
• Attention Meets Reachability: Structural Equivalence and Efficiency in Grammar-Constrained LLM Decoding [0.2864713389096699]
  We study grammar-constrained decoding (GCD) as a coupling between an autoregressive next-token distribution and a reachability over a pushdown system compiled from a context-free grammar (CFG)<n>We define decoding-cost equivalence classes of grammars and prove existence of minimal-SAC representatives within bounded rewrite families.
  arXiv  Detail & Related papers  (2026-03-04T11:49:55Z)
• Computational-Statistical Tradeoffs at the Next-Token Prediction Barrier: Autoregressive and Imitation Learning under Misspecification [50.717692060500696]
  Next-token prediction with the logarithmic loss is a cornerstone of autoregressive sequence modeling.<n>Next-token prediction can be made robust so as to achieve $C=tilde O(H)$, representing moderate error amplification.<n>No computationally efficient algorithm can achieve sub-polynomial approximation factor $C=e(log H)1-Omega(1)$.
  arXiv  Detail & Related papers  (2025-02-18T02:52:00Z)
• Private Vector Mean Estimation in the Shuffle Model: Optimal Rates Require Many Messages [63.366380571397]
  We study the problem of private vector mean estimation in the shuffle model of privacy where $n$ users each have a unit vector $v(i) inmathbbRd$. We propose a new multi-message protocol that achieves the optimal error using $tildemathcalOleft(min(nvarepsilon2,d)right)$ messages per user.
  arXiv  Detail & Related papers  (2024-04-16T00:56:36Z)
• Exact results on finite size corrections for surface codes tailored to biased noise [0.0]
  We study the XY and XZZX surface codes under phase-biased noise. We find exact solutions at a special disordered point. We show that calculating thresholds based not only on the total logical failure rate, but also independently on the phase- and bit-flip logical failure rates, gives a more confident estimate.
  arXiv  Detail & Related papers  (2024-01-08T16:38:56Z)
• Towards Optimal Statistical Watermarking [95.46650092476372]
  We study statistical watermarking by formulating it as a hypothesis testing problem. Key to our formulation is a coupling of the output tokens and the rejection region. We characterize the Uniformly Most Powerful (UMP) watermark in the general hypothesis testing setting.
  arXiv  Detail & Related papers  (2023-12-13T06:57:00Z)
• REAL: A Representative Error-Driven Approach for Active Learning [15.477921200056887]
  $REAL$ is a novel approach to select data instances with $underlineR$epresentative $underlineE$rrors for $underlineA$ctive $underlineL$. It identifies minority predictions as emphpseudo errors within a cluster and allocates an adaptive sampling budget for the cluster based on estimated error density.
  arXiv  Detail & Related papers  (2023-07-03T12:39:26Z)
• Beyond Invariance: Test-Time Label-Shift Adaptation for Distributions with "Spurious" Correlations [44.99833362998488]
  Changes in the data distribution at test time can have deleterious effects on the performance of predictive models. We propose a test-time label shift correction that adapts to changes in the joint distribution $p(y, z)$ using EM applied to unlabeled samples.
  arXiv  Detail & Related papers  (2022-11-28T18:52:33Z)
• Truncation Sampling as Language Model Desmoothing [115.28983143361681]
  Long samples of text from neural language models can be of poor quality. Truncation sampling algorithms set some words' probabilities to zero at each step. We introduce $eta$-sampling, which truncates words below an entropy-dependent probability threshold.
  arXiv  Detail & Related papers  (2022-10-27T05:52:35Z)
• Tail-to-Tail Non-Autoregressive Sequence Prediction for Chinese Grammatical Error Correction [49.25830718574892]
  We present a new framework named Tail-to-Tail (textbfTtT) non-autoregressive sequence prediction. Considering that most tokens are correct and can be conveyed directly from source to target, and the error positions can be estimated and corrected. Experimental results on standard datasets, especially on the variable-length datasets, demonstrate the effectiveness of TtT in terms of sentence-level Accuracy, Precision, Recall, and F1-Measure.
  arXiv  Detail & Related papers  (2021-06-03T05:56:57Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.