---
OA_place: repository
OA_type: green
_id: '22302'
abstract:
- lang: eng
  text: "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 \\mathbb{E}[X]
    ≤ (\U0001D707 + \U0001D707(2))log(B )/\U0001D7072 + O(1), where B is the verifier’s
    batch size, \U0001D707 is the expected entropy of the verifier’s output distribution,
    and \U0001D707(2) is this entropy’s second 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."
article_processing_charge: No
arxiv: 1
author:
- first_name: Sergei
  full_name: Pankratov, Sergei
  id: f773bf05-72ef-11ef-b75a-a383d22f454b
  last_name: Pankratov
- first_name: Dan-Adrian
  full_name: Alistarh, Dan-Adrian
  id: 4A899BFC-F248-11E8-B48F-1D18A9856A87
  last_name: Alistarh
  orcid: 0000-0003-3650-940X
citation:
  ama: 'Pankratov S, Alistarh D-A. Speculative decoding speed-of-light: Optimal lower
    bounds via branching random walks. In: <i>Proceedings of the 19th Conference of
    the European Chapter of the Association for Computational Linguistics</i>. Association
    for Computational Linguistics; 2026:6404–6418. doi:<a href="https://doi.org/10.18653/v1/2026.eacl-long.301">10.18653/v1/2026.eacl-long.301</a>'
  apa: 'Pankratov, S., &#38; Alistarh, D.-A. (2026). Speculative decoding speed-of-light:
    Optimal lower bounds via branching random walks. In <i>Proceedings of the 19th
    Conference of the European Chapter of the Association for Computational Linguistics</i>
    (pp. 6404–6418). Rabat, Morocco: Association for Computational Linguistics. <a
    href="https://doi.org/10.18653/v1/2026.eacl-long.301">https://doi.org/10.18653/v1/2026.eacl-long.301</a>'
  chicago: 'Pankratov, Sergei, and Dan-Adrian Alistarh. “Speculative Decoding Speed-of-Light:
    Optimal Lower Bounds via Branching Random Walks.” In <i>Proceedings of the 19th
    Conference of the European Chapter of the Association for Computational Linguistics</i>,
    6404–6418. Association for Computational Linguistics, 2026. <a href="https://doi.org/10.18653/v1/2026.eacl-long.301">https://doi.org/10.18653/v1/2026.eacl-long.301</a>.'
  ieee: 'S. Pankratov and D.-A. Alistarh, “Speculative decoding speed-of-light: Optimal
    lower bounds via branching random walks,” in <i>Proceedings of the 19th Conference
    of the European Chapter of the Association for Computational Linguistics</i>,
    Rabat, Morocco, 2026, pp. 6404–6418.'
  ista: 'Pankratov S, Alistarh D-A. 2026. Speculative decoding speed-of-light: Optimal
    lower bounds via branching random walks. Proceedings of the 19th Conference of
    the European Chapter of the Association for Computational Linguistics. EACL: 
    Conference of the European Chapter of the Association for Computational Linguistics,
    6404–6418.'
  mla: 'Pankratov, Sergei, and Dan-Adrian Alistarh. “Speculative Decoding Speed-of-Light:
    Optimal Lower Bounds via Branching Random Walks.” <i>Proceedings of the 19th Conference
    of the European Chapter of the Association for Computational Linguistics</i>,
    Association for Computational Linguistics, 2026, pp. 6404–6418, doi:<a href="https://doi.org/10.18653/v1/2026.eacl-long.301">10.18653/v1/2026.eacl-long.301</a>.'
  short: S. Pankratov, D.-A. Alistarh, in:, Proceedings of the 19th Conference of
    the European Chapter of the Association for Computational Linguistics, Association
    for Computational Linguistics, 2026, pp. 6404–6418.
conference:
  end_date: 2026-03-29
  location: Rabat, Morocco
  name: 'EACL:  Conference of the European Chapter of the Association for Computational
    Linguistics'
  start_date: 2026-03-24
corr_author: '1'
das_tickbox: '0'
date_created: 2026-07-13T10:48:03Z
date_published: 2026-04-01T00:00:00Z
date_updated: 2026-07-14T06:18:11Z
day: '01'
department:
- _id: DaAl
- _id: GradSch
doi: 10.18653/v1/2026.eacl-long.301
external_id:
  arxiv:
  - '2512.11718'
language:
- iso: eng
month: '04'
oa_version: Preprint
page: 6404–6418
publication: Proceedings of the 19th Conference of the European Chapter of the Association
  for Computational Linguistics
publication_status: published
publisher: Association for Computational Linguistics
quality_controlled: '1'
researchdata_availability: no
scopus_import: '1'
status: public
supplementarymaterial: no
title: 'Speculative decoding speed-of-light: Optimal lower bounds via branching random
  walks'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2026'
...