# Long-Tail Crisis in Nearest Neighbor Language Models

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Placed in Generation and context integration, one of 15 directions in Retrieval-augmented generation.
- Builds on 15 of its 30 references that are in the map.
- First posted on arXiv 28 Mar 2025.

## Placed in

- Retrieval-augmented generation / [Generation and context integration](https://mlsanity.com/rag/generation-and-context-integration/)

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

- [Pointer Sentinel Mixture Models](https://mlsanity.com/paper/1609.07843/) (2016)
- [Billion-scale similarity search with GPUs](https://mlsanity.com/paper/1702.08734/) (2017)
- [Generalization through Memorization: Nearest Neighbor Language Models](https://mlsanity.com/paper/1911.00172/) (2019)
- [Nearest Neighbor Machine Translation](https://mlsanity.com/paper/2010.00710/) (2020)
- [Generating Sentences by Editing Prototypes](https://mlsanity.com/paper/1709.08878/) (2017)
- [Learning to Remember Rare Events](https://mlsanity.com/paper/1703.03129/) (2017)
- [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)
- [Unbounded cache model for online language modeling with open vocabulary](https://mlsanity.com/paper/1711.02604/) (2017)
- [Why do Nearest Neighbor Language Models Work?](https://mlsanity.com/paper/2301.02828/) (2023)
- [Learning Kernel-Smoothed Machine Translation with Retrieved Examples](https://mlsanity.com/paper/2109.09991/) (2021)
- [You can't pick your neighbors, or can you? When and how to rely on retrieval in the kNN-LM](https://mlsanity.com/paper/2210.15859/) (2022)
- [Learning Sparse Prototypes for Text Generation](https://mlsanity.com/paper/2006.16336/) (2020)
- [Adaptation Approaches for Nearest Neighbor Language Models](https://mlsanity.com/paper/2211.07828/) (2022)
- [Neural Language Modeling With Implicit Cache Pointers](https://mlsanity.com/paper/2009.13774/) (2020)

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

- [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)

The k-nearest-neighbor language model (kNN-LM), one of the retrieval-augmented language models, improves the perplexity for given text by directly accessing a large datastore built from any text data during inference. A widely held hypothesis for the success of kNN-LM is that its explicit memory, i.e., the datastore, enhances predictions for long-tail phenomena. However, prior works have primarily shown its ability to retrieve long-tail contexts, leaving the model's performance remain underexplored in estimating the probabilities of long-tail target tokens during inference. In this paper, we investigate the behavior of kNN-LM on low-frequency tokens, examining prediction probability, retrieval accuracy, token distribution in the datastore, and approximation error of the product quantization. Our experimental results reveal that kNN-LM does not improve prediction performance for low-frequency tokens but mainly benefits high-frequency tokens regardless of long-tail contexts in the datastore.