Recursive Speculative Decoding: Accelerating LLM Inference via Sampling Without Replacement

Existing tree-based draft methods generate tokens INDEPENDENTLY at each tree level and therefore waste the tree's diversity; and their reported superiority implicitly grants tree methods more compute because they compare at fixed draft SEQUENCE LENGTH rather than fixed target compute budget.

Samples draft tokens WITHOUT REPLACEMENT so the tree maximises candidate diversity, via either the Gumbel-Top-k trick (parallel without-replacement sampling) or Stochastic Beam Search (sequence-level sampling without replacement with early truncation of unlikely drafts, which also cuts target-side cost). The paper's methodological contribution as much as its mechanism: it evaluates at FIXED TARGET COMPUTATIONAL BUDGET, the resource-bounded-device setting prior tree work skipped.

Reports that RSD outperforms the baseline tree methods consistently at fixed draft SEQUENCE LENGTH, and in most cases at fixed TARGET COMPUTATIONAL BUDGET. No headline multiplier is quoted in the abstract, and the paper's own framing is the fixed-budget comparison - so speedup_reported records the comparison type rather than a bare number deliberately. Model pairs are Llama 2 and OPT family. Deliberately not extracting a headline number: the abstract's contribution is the fair-budget protocol, not a speedup figure.

ADOPTION: research-only. INCLUDED FOR ITS METHODOLOGY, which is the durable contribution: the fixed-target-compute-budget protocol is the correction to a real evaluation failure mode in the speculative-decoding literature (tree methods look better partly because they spend more compute). Hardware relevance is left EMPTY and that is a deliberate, meaningful choice - the method is a token-sampling/tree-construction change with no hardware-specific dependency, unlike Sequoia, whose whole point is hardware-aware tree sizing. VENUE NOTE: no venue verifiable; the arXiv comment field carries only a page/figure/table count ('82 pages, 9 figures, 54 tables'), so venue = arxiv-preprint, year = ArXiv v1 (Feb 2024). AFFILIATIONS BACKFILLED 2026-10-04 (paper-fields pass, agent w3p): OpenAlex institutions field ('Qualcomm (United Kingdom)'); the paper is from Qualcomm's AI Research group. Filled from the API/PDF rather than from memory, because an affiliation is a fact about a specific paper's author block and inference from the author's employer history is how wrong affiliations get shipped. VENUE_TRACK BACKFILL 2026-10-04 (paper-fields pass, agent w3p): venue_track 'unknown'. `venue` is 'arxiv-preprint', which means no peer-reviewed venue has been established for this work as of the verification date, so the track genuinely is not known. 'unknown' is used here rather than leaving the field null or guessing 'main': the schema separates 'unknown' from 'main' precisely so that an unprereviewed preprint is not silently counted as main-track work. This annotation is what lets a downstream filter distinguish 'peer reviewed, main track' from 'not peer reviewed' without inferring it from the venue string.