---
title: "Efficient Nearest Neighbor Language Models — He 2021"
description: "The analysis offers practical guidance for building and deploying retrieval-based… 0.1 perplexity. 36 references, cited by 63 papers here."
authors: ["Junxian He", "Graham Neubig", "Taylor Berg-Kirkpatrick"]
year: 2021
venue: "Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing"
source: "https://aclanthology.org/2021.emnlp-main.461/"
doi: "10.18653/v1/2021.emnlp-main.461"
licence: "CC BY 4.0 (ACL Anthology)"
licence_url: "https://creativecommons.org/licenses/by/4.0/"
summary_licence: "Elamur Cosmic License"
canonical: "https://research.elamur.ai/free/en/papers/he-2021-efficient-nearest-neighbor-language-models/"
---
[Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/he-2021-efficient-nearest-neighbor-language-models/)

[home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [2021](https://md.research.elamur.ai/free/en/papers/2021/page/4/) / Efficient Nearest Neighbor Language Models

# Efficient Nearest Neighbor Language Models

**Authors:** [Junxian He](https://md.research.elamur.ai/free/en/authors/junxian-he/), [Graham Neubig](https://md.research.elamur.ai/free/en/authors/graham-neubig/) and [Taylor Berg-Kirkpatrick](https://md.research.elamur.ai/free/en/authors/taylor-berg-kirkpatrick/) · **Year:** 2021 · **Venue:** [Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing](https://md.research.elamur.ai/free/en/venues/emnlp/) ([EMNLP 2021](https://md.research.elamur.ai/free/en/venues/emnlp/2021/)) · **Publisher:** [Association for Computational Linguistics](https://md.research.elamur.ai/free/en/publishers/association-for-computational-linguistics/) · **Licence:** [CC BY 4.0 (ACL Anthology)](https://creativecommons.org/licenses/by/4.0/)

**Links:** [Publisher's page](https://aclanthology.org/2021.emnlp-main.461/) · [PDF](https://aclanthology.org/2021.emnlp-main.461.pdf) · [DOI 10.18653/v1/2021.emnlp-main.461](https://doi.org/10.18653/v1/2021.emnlp-main.461) · [OpenAlex](https://openalex.org/W3213851426)

**Citations:** 64 citations (OpenAlex, 2026-10-14) · [63](https://md.research.elamur.ai/free/en/papers/he-2021-efficient-nearest-neighbor-language-models/cited-by/) in our library, of the 141,840 papers whose bibliographies we read

## Summary
Non-parametric language models such as the kNN-LM (Khandelwal et al., 2019) improve perplexity by consulting an external datastore of context–token pairs. However, searching that datastore at every prediction step makes inference far slower than with a standard parametric NLM. He, Neubig and Berg-Kirkpatrick study how to cut this cost through three complementary techniques:
- **Adaptive retrieval:** a small learned adaptor decides when retrieval can be skipped.
- **Datastore pruning:** entries are compressed, for example by greedy merging.
- **Dimension reduction:** PCA, using the FAISS implementation, shrinks the stored context vectors.

They evaluate on the WikiText-103 benchmark and on the Law-MT domain-adaptation setting. Each technique is tuned on validation data to give the largest speed-up while losing at most about 0.1 perplexity against the vanilla kNN-LM. Combined, the techniques make the kNN-LM roughly 5–6.6x faster with essentially unchanged or even better perplexity. The analysis offers practical guidance for building and deploying retrieval-based language models at lower cost.

## Key points
- On the WikiText-103 test set, combining all three methods gives 16.67 ppl at 1835 tokens/s, compared with 16.65 ppl at 277 tokens/s for the vanilla kNN-LM, a 6.6x speed-up. The parametric NLM baseline reaches 18.66 ppl.
- PCA from 1024 to 512 dimensions slightly improves WikiText-103 perplexity (16.40) and runs 3.6x faster. Reducing below 256 dimensions hurts badly, and below 128 dimensions the kNN-LM loses its edge over the NLM.
- Adaptive retrieval skips 50% of lookups on WikiText-103 for nearly 2x speed. On Law-MT it removes only 10%, because the domain datastore matters much more there.
- Greedy merging prunes 40% of the datastore, costing 0.2 ppl on WikiText-103 and 0.7 ppl on Law-MT. The smaller Law-MT datastore (19M entries vs. 103M) appears less redundant.
- On Law-MT, the combined system runs 5.4x faster than the kNN-LM and improves perplexity (12.29 vs. 12.64). Code is available at github.com/jxhe/efficient-knnlm.

*Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.*

## Institutions

- [Carnegie Mellon University](https://md.research.elamur.ai/free/en/universities/carnegie-mellon-university/) — University, Pittsburgh, United States · 365 works · 158,048 citations
- [University of California San Diego](https://md.research.elamur.ai/free/en/universities/university-of-california-san-diego/) — University, San Diego, United States · 34 works · 51,167 citations

📚 Shelves (4): [🖥️ Computer Science](https://md.research.elamur.ai/free/en/shelves/computer-science/) · 9,086 works · [🤖 Artificial Intelligence](https://md.research.elamur.ai/free/en/shelves/computer-science/artificial-intelligence/) · 8,889 works · [🎭 Arts and Humanities](https://md.research.elamur.ai/free/en/shelves/arts-and-humanities/) · 9,296 works · [🗣️ Language and Linguistics](https://md.research.elamur.ai/free/en/shelves/arts-and-humanities/language-and-linguistics/) · 9,206 works

🧭 Topics (1): [🧠 Language models & pretraining](https://md.research.elamur.ai/free/en/topics/language-models/) · 1,343 works

## Cite

Cite as: Junxian He, Graham Neubig and Taylor Berg-Kirkpatrick. 2021. Efficient Nearest Neighbor Language Models. Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing.

The paper itself, not this page. BibTeX from the library's record of the work.

```bibtex
@inproceedings{he2021efficient,
  title = {{Efficient Nearest Neighbor Language Models}},
  author = {Junxian He, Graham Neubig and Taylor Berg-Kirkpatrick},
  booktitle = {Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing},
  year = {2021},
  doi = {10.18653/v1/2021.emnlp-main.461},
  url = {https://doi.org/10.18653/v1/2021.emnlp-main.461}
}
```

- [← previous Can Language Models be Biomedical Knowledge Bases?](https://md.research.elamur.ai/free/en/papers/sung-2021-can-language-models-be-biomedical/)
- [next → Exposing the limits of Zero-shot Cross-lingual Hate Speech Detection](https://md.research.elamur.ai/free/en/papers/nozza-2021-exposing-limits-zero-shot-cross/)
- [↑ back to papers of 2021](https://md.research.elamur.ai/free/en/papers/2021/page/4/)

## References

36 references, 10 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

1. Roee Aharoni and Yoav Goldberg. 2020. [Unsupervised domain clusters in pretrained language models](https://md.research.elamur.ai/free/en/papers/aharoni-2020-unsupervised-domain-clusters-pretrained-language/). In Proceedings of ACL.
2. Rami Al-Rfou, Dokook Choe, Noah Constant, Mandy Guo, and Llion Jones. 2019. Character-level language modeling with deeper self-attention. In Proceedings of AAAI. [find](https://scholar.google.com/scholar?q=Rami+Al%2DRfou%2C+Dokook+Choe%2C+Noah+Constant%2C+Mandy+Guo%2C+and+Llion+Jones%2E+2019%2E+Character%2Dlevel+language+modeling+with+deeper+self%2Dattention%2E+In+Proceedings+of+AAAI%2E)
3. Fabien André, Anne-Marie Kermarrec, and Nicolas Le Scouarnec. 2019. Quicker adc: Unlocking the hidden potential of product quantization with simd. IEEE transactions on pattern analysis and machine intelligence. [find](https://scholar.google.com/scholar?q=Fabien+Andr%C3%A9%2C+Anne%2DMarie+Kermarrec%2C+and+Nicolas+Le+Scouarnec%2E+2019%2E+Quicker+adc%3A+Unlocking+the+hidden+potential+of+product+quantization+with+simd%2E+IEEE+transactions+on+pattern+analysis+and+machine+int)
4. Alexei Baevski and Michael Auli. 2019. Adaptive input representations for neural language modeling. In Proceedings of ICLR. [find](https://scholar.google.com/scholar?q=Alexei+Baevski+and+Michael+Auli%2E+2019%2E+Adaptive+input+representations+for+neural+language+modeling%2E+In+Proceedings+of+ICLR%2E)
5. Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. 2015. [Neural machine translation by jointly learning to align and translate](https://md.research.elamur.ai/free/en/papers/bahdanau-2014-neural-machine-translation-jointly-learning/). In Proceedings of ICLR.
6. Tom B Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. 2020. [Language models are few-shot learners](https://md.research.elamur.ai/free/en/papers/brown-2020-language-models-few-shot-learners/). arXiv preprint arXiv:2005.14165.
7. Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019. [Bert: Pre-training of deep bidirectional transformers for language understanding](https://md.research.elamur.ai/free/en/papers/devlin-2019-bert-pre-training-deep-bidirectional/). In Proceedings of NAACL.
8. Martin Ester, Hans-Peter Kriegel, Jörg Sander, and Xiaowei Xu. 1996. A density-based algorithm for discovering clusters in large spatial databases with noise. In Proceedings of KDD. [find](https://scholar.google.com/scholar?q=Martin+Ester%2C+Hans%2DPeter+Kriegel%2C+J%C3%B6rg+Sander%2C+and+Xiaowei+Xu%2E+1996%2E+A+density%2Dbased+algorithm+for+discovering+clusters+in+large+spatial+databases+with+noise%2E+In+Proceedings+of+KDD%2E)
9. Aristides Gionis, Piotr Indyk, Rajeev Motwani, et al. 1999. Similarity search in high dimensions via hashing. In Proceedings of VLDB. [find](https://scholar.google.com/scholar?q=Aristides+Gionis%2C+Piotr+Indyk%2C+Rajeev+Motwani%2C+et+al%2E+1999%2E+Similarity+search+in+high+dimensions+via+hashing%2E+In+Proceedings+of+VLDB%2E)
10. Yunchao Gong, Svetlana Lazebnik, Albert Gordo, and Florent Perronnin. 2012. Iterative quantization: A procrustean approach to learning binary codes for large-scale image retrieval. IEEE transactions on pattern analysis and machine intelligence, 35(12):2916–2929. [find](https://scholar.google.com/scholar?q=Yunchao+Gong%2C+Svetlana+Lazebnik%2C+Albert+Gordo%2C+and+Florent+Perronnin%2E+2012%2E+Iterative+quantization%3A+A+procrustean+approach+to+learning+binary+codes+for+large%2Dscale+image+retrieval%2E+IEEE+transactions+o)
11. Ruiqi Guo, Philip Sun, Erik Lindgren, Quan Geng, David Simcha, Felix Chern, and Sanjiv Kumar. 2020. Accelerating large-scale inference with anisotropic vector quantization. In Proceedings of ICML. [find](https://scholar.google.com/scholar?q=Ruiqi+Guo%2C+Philip+Sun%2C+Erik+Lindgren%2C+Quan+Geng%2C+David+Simcha%2C+Felix+Chern%2C+and+Sanjiv+Kumar%2E+2020%2E+Accelerating+large%2Dscale+inference+with+anisotropic+vector+quantization%2E+In+Proceedings+of+ICML%2E)
12. Kelvin Guu, Tatsunori B Hashimoto, Yonatan Oren, and Percy Liang. 2018. [Generating sentences by editing prototypes](https://md.research.elamur.ai/free/en/papers/guu-2017-generating-sentences-editing-prototypes/). Transactions of the Association for Computational Linguistics, 6:437–450.
13. Junxian He, Taylor Berg-Kirkpatrick, and Graham Neubig. 2020. Learning sparse prototypes for text generation. In Proceeings of NeurIPS. [find](https://scholar.google.com/scholar?q=Junxian+He%2C+Taylor+Berg%2DKirkpatrick%2C+and+Graham+Neubig%2E+2020%2E+Learning+sparse+prototypes+for+text+generation%2E+In+Proceeings+of+NeurIPS%2E)
14. Sepp Hochreiter and Jürgen Schmidhuber. 1997. Long short-term memory. Neural computation, 9(8):1735–1780. [find](https://scholar.google.com/scholar?q=Sepp+Hochreiter+and+J%C3%BCrgen+Schmidhuber%2E+1997%2E+Long+short%2Dterm+memory%2E+Neural+computation%2C+9%288%29%3A1735%E2%80%931780%2E)
15. Herve Jegou, Matthijs Douze, and Cordelia Schmid. 2010. Product quantization for nearest neighbor search. IEEE transactions on pattern analysis and machine intelligence, 33(1):117–128. [find](https://scholar.google.com/scholar?q=Herve+Jegou%2C+Matthijs+Douze%2C+and+Cordelia+Schmid%2E+2010%2E+Product+quantization+for+nearest+neighbor+search%2E+IEEE+transactions+on+pattern+analysis+and+machine+intelligence%2C+33%281%29%3A117%E2%80%93128%2E)
16. Alexander Johansen and Richard Socher. 2017. Learning when to skim and when to read. In Proceedings of the 2nd Workshop on Representation Learning for NLP. [find](https://scholar.google.com/scholar?q=Alexander+Johansen+and+Richard+Socher%2E+2017%2E+Learning+when+to+skim+and+when+to+read%2E+In+Proceedings+of+the+2nd+Workshop+on+Representation+Learning+for+NLP%2E)
17. Jeff Johnson, Matthijs Douze, and Hervé Jégou. 2019. [Billion-scale similarity search with gpus](https://md.research.elamur.ai/free/en/papers/johnson-2017-billion-scale-similarity-search-gpus/). IEEE Transactions on Big Data.
18. Urvashi Khandelwal, Angela Fan, Dan Jurafsky, Luke Zettlemoyer, and Mike Lewis. 2020. Nearest neighbor machine translation. arXiv preprint arXiv:2010.00710. — [arXiv:2010.00710](https://arxiv.org/abs/2010.00710) [find](https://scholar.google.com/scholar?q=Urvashi+Khandelwal%2C+Angela+Fan%2C+Dan+Jurafsky%2C+Luke+Zettlemoyer%2C+and+Mike+Lewis%2E+2020%2E+Nearest+neighbor+machine+translation%2E+arXiv+preprint+arXiv%3A2010%2E00710%2E+%E2%80%94+%5BarXiv%3A2010%2E00710%5D%28https%3A%2F%2Farxiv%2Eorg%2Fabs%2F)
19. Urvashi Khandelwal, Omer Levy, Dan Jurafsky, Luke Zettlemoyer, and Mike Lewis. 2019. Generalization through memorization: Nearest neighbor language models. In Proceedings of ICLR. [find](https://scholar.google.com/scholar?q=Urvashi+Khandelwal%2C+Omer+Levy%2C+Dan+Jurafsky%2C+Luke+Zettlemoyer%2C+and+Mike+Lewis%2E+2019%2E+Generalization+through+memorization%3A+Nearest+neighbor+language+models%2E+In+Proceedings+of+ICLR%2E)
20. Diederik P Kingma and Jimmy Ba. 2015. Adam: A method for stochastic optimization. In Proceedings of ICLR. [find](https://scholar.google.com/scholar?q=Diederik+P+Kingma+and+Jimmy+Ba%2E+2015%2E+Adam%3A+A+method+for+stochastic+optimization%2E+In+Proceedings+of+ICLR%2E)
21. Philipp Koehn and Rebecca Knowles. 2017. Six challenges for neural machine translation. In Proceedings of the First Workshop on Neural Machine Translation. [find](https://scholar.google.com/scholar?q=Philipp+Koehn+and+Rebecca+Knowles%2E+2017%2E+Six+challenges+for+neural+machine+translation%2E+In+Proceedings+of+the+First+Workshop+on+Neural+Machine+Translation%2E)
22. Stephen Merity, Caiming Xiong, James Bradbury, and Richard Socher. 2017. [Pointer sentinel mixture models](https://md.research.elamur.ai/free/en/papers/merity-2016-pointer-sentinel-mixture-models/). In Proceedings of ICLR. 2019. XLNet: Generalized autoregressive pretraining for language understanding. In Proceedings of NeurIPS.
23. Tomáš Mikolov, Martin Karafiát, Lukáš Burget, Jan Černockỳ, and Sanjeev Khudanpur. 2010. Recurrent neural network based language model. In Eleventh annual conference of the international speech communication association. [find](https://scholar.google.com/scholar?q=Tom%C3%A1%C5%A1+Mikolov%2C+Martin+Karafi%C3%A1t%2C+Luk%C3%A1%C5%A1+Burget%2C+Jan+C%CC%8Cernocky%CC%80%2C+and+Sanjeev+Khudanpur%2E+2010%2E+Recurrent+neural+network+based+language+model%2E+In+Eleventh+annual+conference+of+the+international+speech+comm)
24. Dani Yogatama, Cyprien de Masson d’Autume, and Lingpeng Kong. 2021. Adaptive semiparametric language models. Transactions of the Association for Computational Linguistics, 9:362–373. [find](https://scholar.google.com/scholar?q=Dani+Yogatama%2C+Cyprien+de+Masson+d%E2%80%99Autume%2C+and+Lingpeng+Kong%2E+2021%2E+Adaptive+semiparametric+language+models%2E+Transactions+of+the+Association+for+Computational+Linguistics%2C+9%3A362%E2%80%93373%2E)
25. Sewon Min, Jordan Boyd-Graber, Chris Alberti, Danqi Chen, Eunsol Choi, Michael Collins, Kelvin Guu, Hannaneh Hajishirzi, Kenton Lee, Jennimaria Palomaki, et al. 2020. [find](https://scholar.google.com/scholar?q=Sewon+Min%2C+Jordan+Boyd%2DGraber%2C+Chris+Alberti%2C+Danqi+Chen%2C+Eunsol+Choi%2C+Michael+Collins%2C+Kelvin+Guu%2C+Hannaneh+Hajishirzi%2C+Kenton+Lee%2C+Jennimaria+Palomaki%2C+et+al%2E+2020%2E)
26. Neurips 2020 efficientqa competition: Systems, analyses and lessons learned. arXiv preprint arXiv:2101.00133. — [arXiv:2101.00133](https://arxiv.org/abs/2101.00133) [find](https://scholar.google.com/scholar?q=Neurips+2020+efficientqa+competition%3A+Systems%2C+analyses+and+lessons+learned%2E+arXiv+preprint+arXiv%3A2101%2E00133%2E+%E2%80%94+%5BarXiv%3A2101%2E00133%5D%28https%3A%2F%2Farxiv%2Eorg%2Fabs%2F2101%2E00133%29)
27. Marius Muja and David G Lowe. 2009. Fast approximate nearest neighbors with automatic algorithm configuration. In Proceedings of the International Conference on Computer Vision Theory and Applications. [find](https://scholar.google.com/scholar?q=Marius+Muja+and+David+G+Lowe%2E+2009%2E+Fast+approximate+nearest+neighbors+with+automatic+algorithm+configuration%2E+In+Proceedings+of+the+International+Conference+on+Computer+Vision+Theory+and+Applications)
28. Nathan Ng, Kyra Yee, Alexei Baevski, Myle Ott, Michael Auli, and Sergey Edunov. 2019. [Facebook fair’s wmt19 news translation task submission](https://md.research.elamur.ai/free/en/papers/ng-2019-facebook-fair-s-wmt19-news/). In Proceedings of the Fourth Conference on Machine Translation (Volume 2: Shared Task Papers, Day 1).
29. Matthew Peters, Mark Neumann, Mohit Iyyer, Matt Gardner, Christopher Clark, Kenton Lee, and Luke Zettlemoyer. 2018. [Deep contextualized word representations](https://md.research.elamur.ai/free/en/papers/peters-2018-deep-contextualized-word-representations/). In Proceedings of NAACL.
30. Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. 2019. Language models are unsupervised multitask learners. OpenAI blog, 1(8):9. [find](https://scholar.google.com/scholar?q=Alec+Radford%2C+Jeffrey+Wu%2C+Rewon+Child%2C+David+Luan%2C+Dario+Amodei%2C+and+Ilya+Sutskever%2E+2019%2E+Language+models+are+unsupervised+multitask+learners%2E+OpenAI+blog%2C+1%288%29%3A9%2E)
31. Alexander M Rush, Sumit Chopra, and Jason Weston. 2015. A neural attention model for abstractive sentence summarization. In Proceedings of EMNLP. [find](https://scholar.google.com/scholar?q=Alexander+M+Rush%2C+Sumit+Chopra%2C+and+Jason+Weston%2E+2015%2E+A+neural+attention+model+for+abstractive+sentence+summarization%2E+In+Proceedings+of+EMNLP%2E)
32. Josef Sivic and Andrew Zisserman. 2003. Video google: A text retrieval approach to object matching in videos. In Proceedings of ICCV. [find](https://scholar.google.com/scholar?q=Josef+Sivic+and+Andrew+Zisserman%2E+2003%2E+Video+google%3A+A+text+retrieval+approach+to+object+matching+in+videos%2E+In+Proceedings+of+ICCV%2E)
33. Martin Sundermeyer, Ralf Schlüter, and Hermann Ney. 2012. Lstm neural networks for language modeling. In Thirteenth annual conference of the international speech communication association. [find](https://scholar.google.com/scholar?q=Martin+Sundermeyer%2C+Ralf+Schl%C3%BCter%2C+and+Hermann+Ney%2E+2012%2E+Lstm+neural+networks+for+language+modeling%2E+In+Thirteenth+annual+conference+of+the+international+speech+communication+association%2E)
34. Nenad Tomasev, Milos Radovanovic, Dunja Mladenic, and Mirjana Ivanovic. 2013. The role of hubness in clustering high-dimensional data. IEEE transactions on knowledge and data engineering, 26(3):739–751. [find](https://scholar.google.com/scholar?q=Nenad+Tomasev%2C+Milos+Radovanovic%2C+Dunja+Mladenic%2C+and+Mirjana+Ivanovic%2E+2013%2E+The+role+of+hubness+in+clustering+high%2Ddimensional+data%2E+IEEE+transactions+on+knowledge+and+data+engineering%2C+26%283%29%3A739%E2%80%9375)
35. Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. 2017. [Attention is all you need](https://md.research.elamur.ai/free/en/papers/vaswani-2017-attention-all-need/). In Proceedings of NeurIPS.
36. Zhilin Yang, Zihang Dai, Yiming Yang, Jaime Carbonell, Russ R Salakhutdinov, and Quoc V Le. [find](https://scholar.google.com/scholar?q=Zhilin+Yang%2C+Zihang+Dai%2C+Yiming+Yang%2C+Jaime+Carbonell%2C+Russ+R+Salakhutdinov%2C+and+Quoc+V+Le%2E)

*Updated 24 October 2026*