DR e SD : Dense Retrieval for Speculative Decoding (2025)

Abstract: Speculative decoding (SD) accelerates Large Language Model (LLM) generation by using an efficient draft model to propose the next few tokens, which are verified by the LLM in a single forward call, reducing latency while preserving its outputs. We focus on retrieval-based SD where the draft model retrieves the next tokens from a non-parametric datastore. Sparse retrieval (CITATION)REST], which operates on the surface form of strings, is currently the dominant paradigm due to its simplicity and scalability. However, its effectiveness is limited due to the usage of short contexts and exact string matching. Instead, we introduce Dense Retrieval for Speculative Decoding (DReSD), a novel framework that uses approximate nearest neighbour search with contextualised token embeddings to retrieve the most semantically relevant token sequences for SD. Extensive experiments show that DReSD achieves (on average) 87% higher acceptance rates, 65% longer accepted tokens and 19% faster generation speeds compared to sparse retrieval (REST).

## introduction generative transformers @xcite are currently the dominant artificial intelligence paradigm with recent llms scaled to tens (or even hundreds) of billions of parameters @xcite @xcite . in spite of their strong capabilities, the auto-regressive nature of generation requires a costly forward pass for each new token. various solutions have been proposed to accelerate llms such as flash attention @xcite , mixture of experts @xcite , tensor parallelism @xcite , linear attention @xcite and others. the focus of our work is speculative decoding @xcite , which seeks to accelerate generation by using an efficient draft * equal contribution with first author, conducted during a research internship at huawei noah's ark lab, london. model to propose the next few tokens that are verified in a single forward call of the llm @xcite , guaranteeing its outputs. while several viable sd paradigms exist @xcite @xcite , this work specifically focuses on retrievalbased sd where a draft model retrieves token sequences from a non-parametric datastore, usually a suffix array/automaton. sparse retrieval has established itself as the dominant paradigm @xcite @xcite , largely due to its simplicity and efficiency. however, we hypothesise that this approach suffers from limitations such as lower precision due to the use of short contexts and reduced recall due to exact string matching. as an alternative, we introduce dense retrieval for sd (dresd) which seeks to overcome these limitations by utilising approximate nearest neighbour search with contextualised token representations. dresd is a novel plug-and-play sd framework based on semantic similarity that shows significantly improved acceptance rates. through extensive experimentation, we identify three critical factors of dense retrieval for sd and show how an optimal configuration can accelerate generation by up to 4.64x foot_0 . ## conclusions we have presented a comparative analysis of dense and sparse retrieval for speculative decoding in order to identify and overcome the limitations of the dominant (sparse) paradigm. to address these, we have introduced dresd, dense retrieval for speculative decoding, a novel framework that retrieves candidate drafts from a non-parametric datastore based on semantic similarity (via approximate nearest neighbour search) instead of exact string matching. dresd introduces a scalable and effective dense retrieval protocol that can easily integrate into modern llms. exhaustive comparisons using several model and task configurations have demonstrated that dresd achieves (on average across all settings) 87% higher acceptance rates, 65% longer accepted tokens and 19% faster generation speeds compared to sparse retrieval (rest). this is enabled by three critical factors: a) a fast and accurate dense retrieval via dimensionality reduction and dual normalisation of llm embeddings, b) a careful datastore alignment (particularly the id datastore) with high acceptance rates, longer drafts and fewer llm calls, c) an optimal draft shape explored via careful ablations that enabled up to 4.64x average speed-ups over baseline auto-regressive generation. we hope that our findings will enable new retrieval-based sd methodologies in the future.