# Nearest Neighbor Speculative Decoding for LLM Generation and Attribution

arXiv: https://arxiv.org/abs/2405.19325 · HTML: https://mlsanity.com/paper/2405.19325/

## Key facts

- Cited by 25 papers in the map (data through 14 Oct 2026).
- Placed in Speculative decoding, one of 12 directions in Efficient LLM inference and serving.
- Builds on 52 of its 61 references that are in the map.
- First posted on arXiv 29 May 2024.

## Placed in

- Efficient LLM inference and serving / [Speculative decoding](https://mlsanity.com/inference/speculative-decoding/)

## Builds on (most cited first, 30 of 52)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [LLaMA: Open and Efficient Foundation Language Models](https://mlsanity.com/paper/2302.13971/) (2023)
- [Llama 2: Open Foundation and Fine-Tuned Chat Models](https://mlsanity.com/paper/2307.09288/) (2023)
- [Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks](https://mlsanity.com/paper/2005.11401/) (2020)
- [Measuring Massive Multitask Language Understanding](https://mlsanity.com/paper/2009.03300/) (2020)
- [PaLM: Scaling Language Modeling with Pathways](https://mlsanity.com/paper/2204.02311/) (2022)
- [Dense Passage Retrieval for Open-Domain Question Answering](https://mlsanity.com/paper/2004.04906/) (2020)
- [HotpotQA: A Dataset for Diverse, Explainable Multi-hop Question Answering](https://mlsanity.com/paper/1809.09600/) (2018)
- [Pointer Sentinel Mixture Models](https://mlsanity.com/paper/1609.07843/) (2016)
- [TruthfulQA: Measuring How Models Mimic Human Falsehoods](https://mlsanity.com/paper/2109.07958/) (2021)
- [TriviaQA: A Large Scale Distantly Supervised Challenge Dataset for Reading Comprehension](https://mlsanity.com/paper/1705.03551/) (2017)
- [REALM: Retrieval-Augmented Language Model Pre-Training](https://mlsanity.com/paper/2002.08909/) (2020)
- [Self-RAG: Learning to Retrieve, Generate, and Critique through Self-Reflection](https://mlsanity.com/paper/2310.11511/) (2023)
- [Fast Inference from Transformers via Speculative Decoding](https://mlsanity.com/paper/2211.17192/) (2022)
- [Improving language models by retrieving from trillions of tokens](https://mlsanity.com/paper/2112.04426/) (2021)
- [FActScore: Fine-grained Atomic Evaluation of Factual Precision in Long Form Text Generation](https://mlsanity.com/paper/2305.14251/) (2023)
- [Leveraging Passage Retrieval with Generative Models for Open Domain Question Answering](https://mlsanity.com/paper/2007.01282/) (2020)
- [Accelerating Large Language Model Decoding with Speculative Sampling](https://mlsanity.com/paper/2302.01318/) (2023)
- [Atlas: Few-shot Learning with Retrieval Augmented Language Models](https://mlsanity.com/paper/2208.03299/) (2022)
- [Generalization through Memorization: Nearest Neighbor Language Models](https://mlsanity.com/paper/1911.00172/) (2019)
- [REPLUG: Retrieval-Augmented Black-Box Language Models](https://mlsanity.com/paper/2301.12652/) (2023)
- [Reading Wikipedia to Answer Open-Domain Questions](https://mlsanity.com/paper/1704.00051/) (2017)
- [In-Context Retrieval-Augmented Language Models](https://mlsanity.com/paper/2302.00083/) (2023)
- [MedMCQA : A Large-scale Multi-Subject Multi-Choice Dataset for Medical domain Question Answering](https://mlsanity.com/paper/2203.14371/) (2022)
- [MAUVE: Measuring the Gap Between Neural Text and Human Text using Divergence Frontiers](https://mlsanity.com/paper/2102.01454/) (2021)
- [Large Language Models Struggle to Learn Long-Tail Knowledge](https://mlsanity.com/paper/2211.08411/) (2022)
- [Trusting Your Evidence: Hallucinate Less with Context-aware Decoding](https://mlsanity.com/paper/2305.14739/) (2023)
- [RARR: Researching and Revising What Language Models Say, Using Language Models](https://mlsanity.com/paper/2210.08726/) (2022)

## Built on by (most cited first, 25 of 25)

- [EAGLE-2: Faster Inference of Language Models with Dynamic Draft Trees](https://mlsanity.com/paper/2406.16858/) (2024)
- [EAGLE-3: Scaling up Inference Acceleration of Large Language Models via Training-Time Test](https://mlsanity.com/paper/2503.01840/) (2025)
- [Multi-Layer Transformers Gradient Can be Approximated in Almost Linear Time](https://mlsanity.com/paper/2408.13233/) (2024)
- [A Tighter Complexity Analysis of SparseGPT](https://mlsanity.com/paper/2408.12151/) (2024)
- [Mixture of Attentions For Speculative Decoding](https://mlsanity.com/paper/2410.03804/) (2024)
- [Retrofitting Large Language Models with Dynamic Tokenization](https://mlsanity.com/paper/2411.18553/) (2024)
- [TokenShapley: Token Level Context Attribution with Shapley Value](https://mlsanity.com/paper/2507.05261/) (2025)
- [Improving Factuality with Explicit Working Memory](https://mlsanity.com/paper/2412.18069/) (2024)
- [Speculate, then Collaborate: Fusing Knowledge of Language Models during Decoding](https://mlsanity.com/paper/2502.08020/) (2025)
- [Attribution, Citation, and Quotation: A Survey of Evidence-based Text Generation with Large Language Models](https://mlsanity.com/paper/2508.15396/) (2025)
- [DReSD: Dense Retrieval for Speculative Decoding](https://mlsanity.com/paper/2502.15572/) (2025)
- [VIBE: Vector Index Benchmark for Embeddings](https://mlsanity.com/paper/2505.17810/) (2025)
- [A Survey on Proactive Defense Strategies Against Misinformation in Large Language Models](https://mlsanity.com/paper/2507.05288/) (2025)
- [Large Language Model Sourcing: A Survey](https://mlsanity.com/paper/2510.10161/) (2025)
- [TokenSwift: Lossless Acceleration of Ultra Long Sequence Generation](https://mlsanity.com/paper/2502.18890/) (2025)
- [Advancing Decoding Strategies: Enhancements in Locally Typical Sampling for LLMs](https://mlsanity.com/paper/2506.05387/) (2025)
- [OmniDraft: A Cross-vocabulary, Online Adaptive Drafter for On-device Speculative Decoding](https://mlsanity.com/paper/2507.02659/) (2025)
- [Yggdrasil: Bridging Dynamic Speculation and Static Runtime for Latency-Optimal Tree-Based LLM Decoding](https://mlsanity.com/paper/2512.23858/) (2025)
- [DIVERSED: Relaxed Speculative Decoding via Dynamic Ensemble Verification](https://mlsanity.com/paper/2604.07622/) (2026)
- [Breaking the Attention Bottleneck](https://mlsanity.com/paper/2406.10906/) (2024)
- [Flow of Spans: Generalizing Language Models to Dynamic Span-Vocabulary via GFlowNets](https://mlsanity.com/paper/2602.10583/) (2026)
- [CATS: Cascaded Adaptive Tree Speculation for Memory-Limited LLM Inference Acceleration](https://mlsanity.com/paper/2605.11186/) (2026)
- [Near-Exponential Convergence Rates for kNN Classification based on Boltzmann Margin](https://mlsanity.com/paper/2606.10361/) (2026)
- [Oilbird: Training-Free Speculative Decoding with Keys the Verifier Already Computes](https://mlsanity.com/paper/2608.03839/) (2026)
- [Guaranteeing Faithful Evidence Extraction in Speculative Retrieval-Augmented Generation](https://mlsanity.com/paper/2609.10046/) (2026)

## Abstract (arXiv)

Large language models (LLMs) often hallucinate and lack the ability to provide attribution for their generations. Semi-parametric LMs, such as kNN-LM, approach these limitations by refining the output of an LM for a given prompt using its nearest neighbor matches in a non-parametric data store. However, these models often exhibit slow inference speeds and produce non-fluent texts. In this paper, we introduce Nearest Neighbor Speculative Decoding (NEST), a novel semi-parametric language modeling approach that is capable of incorporating real-world text spans of arbitrary length into the LM generations and providing attribution to their sources. NEST performs token-level retrieval at each inference step to compute a semi-parametric mixture distribution and identify promising span continuations in a corpus. It then uses an approximate speculative decoding procedure that accepts a prefix of the retrieved span or generates a new token. NEST significantly enhances the generation quality and attribution rate of the base LM across a variety of knowledge-intensive tasks, surpassing the conventional kNN-LM method and performing competitively with in-context retrieval augmentation. In addition, NEST substantially improves the generation speed, achieving a 1.8x speedup in inference time when applied to Llama-2-Chat 70B. Code will be released at https://github.com/facebookresearch/NEST/tree/main.