---
res:
  bibo_abstract:
  - "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.@eng"
  bibo_authorlist:
  - foaf_Person:
      foaf_givenName: Sergei
      foaf_name: Pankratov, Sergei
      foaf_surname: Pankratov
      foaf_workInfoHomepage: http://www.librecat.org/personId=f773bf05-72ef-11ef-b75a-a383d22f454b
  - foaf_Person:
      foaf_givenName: Dan-Adrian
      foaf_name: Alistarh, Dan-Adrian
      foaf_surname: Alistarh
      foaf_workInfoHomepage: http://www.librecat.org/personId=4A899BFC-F248-11E8-B48F-1D18A9856A87
    orcid: 0000-0003-3650-940X
  bibo_doi: 10.18653/v1/2026.eacl-long.301
  dct_date: 2026^xs_gYear
  dct_language: eng
  dct_publisher: Association for Computational Linguistics@
  dct_title: 'Speculative decoding speed-of-light: Optimal lower bounds via branching
    random walks@'
...