mlsanityData to 14 Oct 2026

Speculative Decoding Speed-of-Light: Optimal Lower Bounds via Branching Random Walks

arXiv 2512.11718 ↗First posted 12 Dec 2025cs.CLcited by 0

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

Abstract (arXiv)

Speculative generation has emerged as a promising technique to accelerate inference in large language models (LLMs) by leveraging parallelism to verify multiple draft tokens simultaneously. However, the fundamental limits on the achievable speedup remain poorly understood. In this work, we establish the first ``tight'' lower bounds on the runtime of any deterministic speculative generation algorithm. This is achieved by drawing a parallel between the token generation process and branching random walks, which allows us to analyze the optimal draft tree selection problem. We prove, under basic assumptions, that the expected number of tokens successfully predicted per speculative iteration is bounded as mathbbE[X] ≤ (μ + μ(2))log(P )/μ2 + O(1), where P is the verifier's capacity, μ is the expected entropy of the verifier's output distribution, and μ(2) is the expected second log-moment. This result provides new insights into the limits of parallel token generation, and could guide the design of future speculative decoding systems. Empirical evaluations on Llama models validate our theoretical predictions, confirming the tightness of our bounds in practical settings.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Placed in Speculative decoding, one of 12 directions in Efficient LLM inference and serving. Builds on 18 of its 26 references that are in the map. First posted on arXiv 12 Dec 2025.

Builds on

18 of 26 references.

Closest ancestors · 9

Same direction, newest first

  1. 2025EAGLE-3: Scaling up Inference Acceleration of Large Language Models via Training-Time Test3 Mar
  2. 2024A Theoretical Perspective for Speculative Decoding Algorithm30 Oct
  3. 2024EAGLE-2: Faster Inference of Language Models with Dynamic Draft Trees24 Jun
  4. 2024Break the Sequential Dependency of LLM Inference Using Lookahead Decoding3 Feb
  5. 2024EAGLE: Speculative Sampling Requires Rethinking Feature Uncertainty26 Jan
  6. 2024Medusa: Simple LLM Inference Acceleration Framework with Multiple Decoding Heads19 Jan
  7. 2023Accelerating LLM Inference with Staged Speculative Decoding8 Aug
  8. 2023Accelerating Large Language Model Decoding with Speculative Sampling2 Feb
  9. 2022Fast Inference from Transformers via Speculative Decoding30 Nov

Other references · 9

  1. 2021Training Verifiers to Solve Math Word Problemscited by 10,109
  2. 2023Judging LLM-as-a-Judge with MT-Bench and Chatbot Arenacited by 8,626
  3. 2023Efficient Memory Management for Large Language Model Serving with PagedAttentioncited by 5,944
  4. 2023SGLang: Efficient Execution of Structured Language Model Programscited by 1,141
  5. 2016Abstractive Text Summarization Using Sequence-to-Sequence RNNs and Beyondcited by 812
  6. 2019Fast Transformer Decoding: One Write-Head is All You Needcited by 717
  7. 2023FlexGen: High-Throughput Generative Inference of Large Language Models with a Single GPUcited by 575
  8. 2018Blockwise Parallel Decoding for Deep Autoregressive Modelscited by 323
  9. 2024LayerSkip: Enabling Early Exit Inference and Self-Speculative Decodingcited by 307

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2025Fail Fast, Win Big: Rethinking the Drafting Strategy in Speculative Decoding via Diffusion LLMs
  2. 2026LibraSpec: Dynamic Diffusion-Based Speculative Decoding via Marginal-Gain-Driven Optimization
  3. 2024Recursive Speculative Decoding: Accelerating LLM Inference via Sampling Without Replacement
  4. 2023PaSS: Parallel Speculative Sampling
  5. 2025Speculative Sampling via Exponential Races
  6. 2024Block Verification Accelerates Speculative Decoding
  7. 2026Cost-Aware Diffusion Draft Trees for Speculative Decoding
  8. 2025Traversal Verification for Speculative Tree Decoding