mlsanityData to 7 Oct 2026

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

arXiv 2605.07698 ↗First posted 8 May 2026cs.LG cs.IT math.ITcited by 2

On the map: Efficient LLM inference and serving → Speculative decoding

Abstract (arXiv)

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 μ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 Phit(y)=Prp[valid completionmid y] as the missing correction statistic. The target distribution is a Doob transform of the base model with h=Phi, while local masking corresponds to setting h to one. With exact Phi, our oracle decoder FVO-Spec samples exactly from μ^star; with approximate Phi, 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.

Key facts. Cited by 2 papers in the map (data through 7 Oct 2026). Placed in Speculative decoding, one of 12 directions in Efficient LLM inference and serving. Builds on 18 of its 22 references that are in the map. First posted on arXiv 8 May 2026.

Builds on

18 of 22 references.

Closest ancestors · 9

Same direction, newest first

  1. 2026DFlash: Block Diffusion for Flash Speculative Decoding5 Feb
  2. 2025Entropy-Aware Token Rejection for Improving Speculative Decoding29 Dec
  3. 2025Efficient Adaptive Rejection Sampling for Accelerating Speculative Decoding in Large Language Models15 Dec
  4. 2025EAGLE-3: Scaling up Inference Acceleration of Large Language Models via Training-Time Test3 Mar
  5. 2024EAGLE: Speculative Sampling Requires Rethinking Feature Uncertainty26 Jan
  6. 2024Medusa: Simple LLM Inference Acceleration Framework with Multiple Decoding Heads19 Jan
  7. 2023SpecInfer: Accelerating Generative Large Language Model Serving with Tree-based Speculative Inference and Verification16 May
  8. 2023Accelerating Large Language Model Decoding with Speculative Sampling2 Feb
  9. 2022Fast Inference from Transformers via Speculative Decoding30 Nov

Other references · 9

  1. 2020Score-Based Generative Modeling through Stochastic Differential Equationscited by 8,964
  2. 2023Efficient Memory Management for Large Language Model Serving with PagedAttentioncited by 5,767
  3. 2023SGLang: Efficient Execution of Structured Language Model Programscited by 1,107
  4. 2023Efficient Guided Generation for Large Language Modelscited by 192
  5. 2022COLD Decoding: Energy-based Constrained Text Generation with Langevin Dynamicscited by 159
  6. 2024XGrammar: Flexible and Efficient Structured Generation Engine for Large Language Modelscited by 73
  7. 2024Grammar-Aligned Decodingcited by 54
  8. 2026XGrammar-2: Dynamic and Efficient Structured Generation Engine for Agentic LLMscited by 6
  9. 2026Attention Meets Reachability: Structural Equivalence and Efficiency in Grammar-Constrained LLM Decodingcited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2026: 2.

2 papers.

  1. 2026Stateful CARS: Exact Cross-History Reuse for Policy-Constrained LLM Agentscited by 0
  2. 2026GrammarRL: Effective Grammar-Constrained Decoding via Reinforcement Learningcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2026A Practical Investigation of Training-free Relaxed Speculative Decoding
  2. 2024A Theoretical Perspective for Speculative Decoding Algorithm
  3. 2024Unlocking Efficiency in Large Language Model Inference: A Comprehensive Survey of Speculative Decoding
  4. 2024Closer Look at Efficient Inference Methods: A Survey of Speculative Decoding
  5. 2026MARS: Unleashing the Power of Speculative Decoding via Margin-Aware Verification
  6. 2023Speculative Contrastive Decoding
  7. 2026Speculative Decoding with a Speculative Vocabulary
  8. 2025Training-Free Loosely Speculative Decoding: Accepting Semantically Correct Drafts Beyond Exact Match