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

arXiv: https://arxiv.org/abs/2605.07698 · HTML: https://mlsanity.com/paper/2605.07698/

## Key facts

- Cited by 2 papers in the map (data through 14 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.

## Placed in

- Efficient LLM inference and serving / [Speculative decoding](https://mlsanity.com/inference/speculative-decoding/)

## Builds on (most cited first, 18 of 18)

- [Score-Based Generative Modeling through Stochastic Differential Equations](https://mlsanity.com/paper/2011.13456/) (2020)
- [Efficient Memory Management for Large Language Model Serving with PagedAttention](https://mlsanity.com/paper/2309.06180/) (2023)
- [Fast Inference from Transformers via Speculative Decoding](https://mlsanity.com/paper/2211.17192/) (2022)
- [SGLang: Efficient Execution of Structured Language Model Programs](https://mlsanity.com/paper/2312.07104/) (2023)
- [Accelerating Large Language Model Decoding with Speculative Sampling](https://mlsanity.com/paper/2302.01318/) (2023)
- [Medusa: Simple LLM Inference Acceleration Framework with Multiple Decoding Heads](https://mlsanity.com/paper/2401.10774/) (2024)
- [EAGLE: Speculative Sampling Requires Rethinking Feature Uncertainty](https://mlsanity.com/paper/2401.15077/) (2024)
- [SpecInfer: Accelerating Generative Large Language Model Serving with Tree-based Speculative Inference and Verification](https://mlsanity.com/paper/2305.09781/) (2023)
- [EAGLE-3: Scaling up Inference Acceleration of Large Language Models via Training-Time Test](https://mlsanity.com/paper/2503.01840/) (2025)
- [Efficient Guided Generation for Large Language Models](https://mlsanity.com/paper/2307.09702/) (2023)
- [COLD Decoding: Energy-based Constrained Text Generation with Langevin Dynamics](https://mlsanity.com/paper/2202.11705/) (2022)
- [DFlash: Block Diffusion for Flash Speculative Decoding](https://mlsanity.com/paper/2602.06036/) (2026)
- [XGrammar: Flexible and Efficient Structured Generation Engine for Large Language Models](https://mlsanity.com/paper/2411.15100/) (2024)
- [Grammar-Aligned Decoding](https://mlsanity.com/paper/2405.21047/) (2024)
- [XGrammar-2: Dynamic and Efficient Structured Generation Engine for Agentic LLMs](https://mlsanity.com/paper/2601.04426/) (2026)
- [Entropy-Aware Token Rejection for Improving Speculative Decoding](https://mlsanity.com/paper/2512.23765/) (2025)
- [Efficient Adaptive Rejection Sampling for Accelerating Speculative Decoding in Large Language Models](https://mlsanity.com/paper/2512.13194/) (2025)
- [Attention Meets Reachability: Structural Equivalence and Efficiency in Grammar-Constrained LLM Decoding](https://mlsanity.com/paper/2603.05540/) (2026)

## Built on by (most cited first, 2 of 2)

- [Stateful CARS: Exact Cross-History Reuse for Policy-Constrained LLM Agents](https://mlsanity.com/paper/2608.08282/) (2026)
- [GrammarRL: Effective Grammar-Constrained Decoding via Reinforcement Learning](https://mlsanity.com/paper/2609.39869/) (2026)

## 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.