# You can't pick your neighbors, or can you? When and how to rely on retrieval in the kNN-LM

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

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- Builds on 38 of its 45 references that are in the map.
- First posted on arXiv 28 Oct 2022.

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

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks](https://mlsanity.com/paper/2005.11401/) (2020)
- [Pointer Sentinel Mixture Models](https://mlsanity.com/paper/1609.07843/) (2016)
- [REALM: Retrieval-Augmented Language Model Pre-Training](https://mlsanity.com/paper/2002.08909/) (2020)
- [Megatron-LM: Training Multi-Billion Parameter Language Models Using Model Parallelism](https://mlsanity.com/paper/1909.08053/) (2019)
- [Understanding deep learning requires rethinking generalization](https://mlsanity.com/paper/1611.03530/) (2016)
- [Improving language models by retrieving from trillions of tokens](https://mlsanity.com/paper/2112.04426/) (2021)
- [LaMDA: Language Models for Dialog Applications](https://mlsanity.com/paper/2201.08239/) (2022)
- [Generalization through Memorization: Nearest Neighbor Language Models](https://mlsanity.com/paper/1911.00172/) (2019)
- [Reading Wikipedia to Answer Open-Domain Questions](https://mlsanity.com/paper/1704.00051/) (2017)
- [Compressive Transformers for Long-Range Sequence Modelling](https://mlsanity.com/paper/1911.05507/) (2019)
- [Deduplicating Training Data Makes Language Models Better](https://mlsanity.com/paper/2107.06499/) (2021)
- [Latent Retrieval for Weakly Supervised Open Domain Question Answering](https://mlsanity.com/paper/1906.00300/) (2019)
- [Deduplicating Training Data Mitigates Privacy Risks in Language Models](https://mlsanity.com/paper/2202.06539/) (2022)
- [Adaptive Input Representations for Neural Language Modeling](https://mlsanity.com/paper/1809.10853/) (2018)
- [Memorizing Transformers](https://mlsanity.com/paper/2203.08913/) (2022)
- [Nearest Neighbor Machine Translation](https://mlsanity.com/paper/2010.00710/) (2020)
- [How much do language models copy from their training data? Evaluating linguistic novelty in text generation using RAVEN](https://mlsanity.com/paper/2111.09509/) (2021)
- [COIL: Revisit Exact Lexical Match in Information Retrieval with Contextualized Inverted List](https://mlsanity.com/paper/2104.07186/) (2021)
- [Training Language Models with Memory Augmentation](https://mlsanity.com/paper/2205.12674/) (2022)
- [Self-training Improves Pre-training for Natural Language Understanding](https://mlsanity.com/paper/2010.02194/) (2020)
- [Efficient Nearest Neighbor Language Models](https://mlsanity.com/paper/2109.04212/) (2021)
- [Adaptive Semiparametric Language Models](https://mlsanity.com/paper/2102.02557/) (2021)
- [Improving Neural Language Models with a Continuous Cache](https://mlsanity.com/paper/1612.04426/) (2016)
- [RankGen: Improving Text Generation with Large Ranking Models](https://mlsanity.com/paper/2205.09726/) (2022)
- [Neuro-Symbolic Language Modeling with Automaton-augmented Retrieval](https://mlsanity.com/paper/2201.12431/) (2022)
- [Adaptive Nearest Neighbor Machine Translation](https://mlsanity.com/paper/2105.13022/) (2021)
- [Augmenting Transformers with KNN-Based Composite Memory for Dialogue](https://mlsanity.com/paper/2004.12744/) (2020)
- [Retrieval-Enhanced Machine Learning](https://mlsanity.com/paper/2205.01230/) (2022)
- [Joint Passage Ranking for Diverse Multi-Answer Retrieval](https://mlsanity.com/paper/2104.08445/) (2021)

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

- [When Not to Trust Language Models: Investigating Effectiveness of Parametric and Non-Parametric Memories](https://mlsanity.com/paper/2212.10511/) (2022)
- [Unlimiformer: Long-Range Transformers with Unlimited Length Input](https://mlsanity.com/paper/2305.01625/) (2023)
- [Reliable, Adaptable, and Attributable Language Models with Retrieval](https://mlsanity.com/paper/2403.03187/) (2024)
- [SILO Language Models: Isolating Legal Risk In a Nonparametric Datastore](https://mlsanity.com/paper/2308.04430/) (2023)
- [Repoformer: Selective Retrieval for Repository-Level Code Completion](https://mlsanity.com/paper/2403.10059/) (2024)
- [How Do Large Language Models Capture the Ever-changing World Knowledge? A Review of Recent Advances](https://mlsanity.com/paper/2310.07343/) (2023)
- [Adaptive Tool Use in Large Language Models with Meta-Cognition Trigger](https://mlsanity.com/paper/2502.12961/) (2025)
- [Why do Nearest Neighbor Language Models Work?](https://mlsanity.com/paper/2301.02828/) (2023)
- [Nearest Neighbor Speculative Decoding for LLM Generation and Attribution](https://mlsanity.com/paper/2405.19325/) (2024)
- [Learn to Memorize: Scalable Continual Learning in Semiparametric Models with Mixture-of-Neighbors Induction Memory](https://mlsanity.com/paper/2303.01421/) (2023)
- [Plan*RAG: Efficient Test-Time Planning for Retrieval Augmented Generation](https://mlsanity.com/paper/2410.20753/) (2024)
- [KNN-LM Does Not Improve Open-ended Text Generation](https://mlsanity.com/paper/2305.14625/) (2023)
- [FT2Ra: A Fine-Tuning-Inspired Approach to Retrieval-Augmented Code Completion](https://mlsanity.com/paper/2404.01554/) (2024)
- [On Retrieval Augmentation and the Limitations of Language Model Training](https://mlsanity.com/paper/2311.09615/) (2023)
- [Long-Tail Crisis in Nearest Neighbor Language Models](https://mlsanity.com/paper/2503.22426/) (2025)
- [Separating Knowledge and Perception with Procedural Data](https://mlsanity.com/paper/2508.11697/) (2025)
- [Oilbird: Training-Free Speculative Decoding with Keys the Verifier Already Computes](https://mlsanity.com/paper/2608.03839/) (2026)
- [Does Episodic Memory Help Close the Lexical Frequency Gap in Sensitivity to Syntactic Contrasts? A Test Using Retrieval-Augmented Language Models](https://mlsanity.com/paper/2608.23851/) (2026)

## Abstract (arXiv)

Retrieval-enhanced language models (LMs), which condition their predictions on text retrieved from large external datastores, have recently shown significant perplexity improvements compared to standard LMs. One such approach, the kNN-LM, interpolates any existing LM's predictions with the output of a k-nearest neighbors model and requires no additional training. In this paper, we explore the importance of lexical and semantic matching in the context of items retrieved by kNN-LM. We find two trends: (1) the presence of large overlapping n-grams between the datastore and evaluation set plays an important factor in strong performance, even when the datastore is derived from the training data; and (2) the kNN-LM is most beneficial when retrieved items have high semantic similarity with the query. Based on our analysis, we define a new formulation of the kNN-LM that uses retrieval quality to assign the interpolation coefficient. We empirically measure the effectiveness of our approach on two English language modeling datasets, Wikitext-103 and PG-19. Our re-formulation of the kNN-LM is beneficial in both cases, and leads to nearly 4% improvement in perplexity on the Wikitext-103 test set.