# Efficient Nearest Neighbor Language Models

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

## Key facts

- Cited by 93 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 35 references that are in the map.
- First posted on arXiv 9 Sep 2021.

## Builds on (most cited first, 23 of 23)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Neural Machine Translation by Jointly Learning to Align and Translate](https://mlsanity.com/paper/1409.0473/) (2014)
- [Pointer Sentinel Mixture Models](https://mlsanity.com/paper/1609.07843/) (2016)
- [XLNet: Generalized Autoregressive Pretraining for Language Understanding](https://mlsanity.com/paper/1906.08237/) (2019)
- [Billion-scale similarity search with GPUs](https://mlsanity.com/paper/1702.08734/) (2017)
- [Deep contextualized word representations](https://mlsanity.com/paper/1802.05365/) (2018)
- [Generalization through Memorization: Nearest Neighbor Language Models](https://mlsanity.com/paper/1911.00172/) (2019)
- [A Neural Attention Model for Abstractive Sentence Summarization](https://mlsanity.com/paper/1509.00685/) (2015)
- [Six Challenges for Neural Machine Translation](https://mlsanity.com/paper/1706.03872/) (2017)
- [Adaptive Input Representations for Neural Language Modeling](https://mlsanity.com/paper/1809.10853/) (2018)
- [Nearest Neighbor Machine Translation](https://mlsanity.com/paper/2010.00710/) (2020)
- [Facebook FAIR's WMT19 News Translation Task Submission](https://mlsanity.com/paper/1907.06616/) (2019)
- [Unsupervised Domain Clusters in Pretrained Language Models](https://mlsanity.com/paper/2004.02105/) (2020)
- [Character-Level Language Modeling with Deeper Self-Attention](https://mlsanity.com/paper/1808.04444/) (2018)
- [Generating Sentences by Editing Prototypes](https://mlsanity.com/paper/1709.08878/) (2017)
- [Adaptive Semiparametric Language Models](https://mlsanity.com/paper/2102.02557/) (2021)
- [NeurIPS 2020 EfficientQA Competition: Systems, Analyses and Lessons Learned](https://mlsanity.com/paper/2101.00133/) (2021)
- [Learning Sparse Prototypes for Text Generation](https://mlsanity.com/paper/2006.16336/) (2020)
- [Quicker ADC : Unlocking the hidden potential of Product Quantization with SIMD](https://mlsanity.com/paper/1812.09162/) (2018)
- [Learning when to skim and when to read](https://mlsanity.com/paper/1712.05483/) (2017)

## Built on by (most cited first, 30 of 93)

- [When Not to Trust Language Models: Investigating Effectiveness of Parametric and Non-Parametric Memories](https://mlsanity.com/paper/2212.10511/) (2022)
- [In-Context Retrieval-Augmented Language Models](https://mlsanity.com/paper/2302.00083/) (2023)
- [A Survey on RAG Meeting LLMs: Towards Retrieval-Augmented Large Language Models](https://mlsanity.com/paper/2405.06211/) (2024)
- [Retrieval-Augmented Generation for AI-Generated Content: A Survey](https://mlsanity.com/paper/2402.19473/) (2024)
- [RECOMP: Improving Retrieval-Augmented LMs with Compression and Selective Augmentation](https://mlsanity.com/paper/2310.04408/) (2023)
- [Training Language Models with Memory Augmentation](https://mlsanity.com/paper/2205.12674/) (2022)
- [The Efficiency Misnomer](https://mlsanity.com/paper/2110.12894/) (2021)
- [Test-Time Training on Nearest Neighbors for Large Language Models](https://mlsanity.com/paper/2305.18466/) (2023)
- [Language Generation Models Can Cause Harm: So What Can We Do About It? An Actionable Survey](https://mlsanity.com/paper/2210.07700/) (2022)
- [Efficient Methods for Natural Language Processing: A Survey](https://mlsanity.com/paper/2209.00099/) (2022)
- [SILO Language Models: Isolating Legal Risk In a Nonparametric Datastore](https://mlsanity.com/paper/2308.04430/) (2023)
- [Neuro-Symbolic Language Modeling with Automaton-augmented Retrieval](https://mlsanity.com/paper/2201.12431/) (2022)
- [Instruction-tuned Language Models are Better Knowledge Learners](https://mlsanity.com/paper/2402.12847/) (2024)
- [Repoformer: Selective Retrieval for Repository-Level Code Completion](https://mlsanity.com/paper/2403.10059/) (2024)
- [Nonparametric Masked Language Modeling](https://mlsanity.com/paper/2212.01349/) (2022)
- [Decoupling Knowledge from Memorization: Retrieval-augmented Prompt Learning](https://mlsanity.com/paper/2205.14704/) (2022)
- [How Do Large Language Models Capture the Ever-changing World Knowledge? A Review of Recent Advances](https://mlsanity.com/paper/2310.07343/) (2023)
- [RAG-DDR: Optimizing Retrieval-Augmented Generation Using Differentiable Data Rewards](https://mlsanity.com/paper/2410.13509/) (2024)
- [Privacy Implications of Retrieval-Based Language Models](https://mlsanity.com/paper/2305.14888/) (2023)
- [Adaptive Tool Use in Large Language Models with Meta-Cognition Trigger](https://mlsanity.com/paper/2502.12961/) (2025)
- [Metacognitive Reuse: Turning Recurring LLM Reasoning Into Concise Behaviors](https://mlsanity.com/paper/2509.13237/) (2025)
- [How BPE Affects Memorization in Transformers](https://mlsanity.com/paper/2110.02782/) (2021)
- [Why do Nearest Neighbor Language Models Work?](https://mlsanity.com/paper/2301.02828/) (2023)
- [kNN-Prompt: Nearest Neighbor Zero-Shot Inference](https://mlsanity.com/paper/2205.13792/) (2022)
- [Copy Is All You Need](https://mlsanity.com/paper/2307.06962/) (2023)
- [Metacognitive Retrieval-Augmented Large Language Models](https://mlsanity.com/paper/2402.11626/) (2024)
- [RAG and RAU: A Survey on Retrieval-Augmented Language Model in Natural Language Processing](https://mlsanity.com/paper/2404.19543/) (2024)
- [Nearest Neighbor Speculative Decoding for LLM Generation and Attribution](https://mlsanity.com/paper/2405.19325/) (2024)
- [Efficient Cluster-Based k-Nearest-Neighbor Machine Translation](https://mlsanity.com/paper/2204.06175/) (2022)
- [Chunk-based Nearest Neighbor Machine Translation](https://mlsanity.com/paper/2205.12230/) (2022)

## Abstract (arXiv)

Non-parametric neural language models (NLMs) learn predictive distributions of text utilizing an external datastore, which allows them to learn through explicitly memorizing the training datapoints. While effective, these models often require retrieval from a large datastore at test time, significantly increasing the inference overhead and thus limiting the deployment of non-parametric NLMs in practical applications. In this paper, we take the recently proposed k-nearest neighbors language model (Khandelwal et al., 2020) as an example, exploring methods to improve its efficiency along various dimensions. Experiments on the standard WikiText-103 benchmark and domain-adaptation datasets show that our methods are able to achieve up to a 6x speed-up in inference speed while retaining comparable performance. The empirical analysis we present may provide guidelines for future research seeking to develop or deploy more efficient non-parametric NLMs.