# Fast Nearest Neighbor Machine Translation

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

## Key facts

- Cited by 37 papers in the map (data through 14 Oct 2026).
- Builds on 41 of its 54 references that are in the map.
- First posted on arXiv 30 May 2021.

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

- [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)
- [Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks](https://mlsanity.com/paper/2005.11401/) (2020)
- [BART: Denoising Sequence-to-Sequence Pre-training for Natural Language Generation, Translation, and Comprehension](https://mlsanity.com/paper/1910.13461/) (2019)
- [Neural Machine Translation by Jointly Learning to Align and Translate](https://mlsanity.com/paper/1409.0473/) (2014)
- [Sequence to Sequence Learning with Neural Networks](https://mlsanity.com/paper/1409.3215/) (2014)
- [Billion-scale similarity search with GPUs](https://mlsanity.com/paper/1702.08734/) (2017)
- [REALM: Retrieval-Augmented Language Model Pre-Training](https://mlsanity.com/paper/2002.08909/) (2020)
- [A Call for Clarity in Reporting BLEU Scores](https://mlsanity.com/paper/1804.08771/) (2018)
- [fairseq: A Fast, Extensible Toolkit for Sequence Modeling](https://mlsanity.com/paper/1904.01038/) (2019)
- [Multilingual Denoising Pre-training for Neural Machine Translation](https://mlsanity.com/paper/2001.08210/) (2020)
- [Effective Approaches to Attention-based Neural Machine Translation](https://mlsanity.com/paper/1508.04025/) (2015)
- [On Layer Normalization in the Transformer Architecture](https://mlsanity.com/paper/2002.04745/) (2020)
- [Approximate Nearest Neighbor Negative Contrastive Learning for Dense Text Retrieval](https://mlsanity.com/paper/2007.00808/) (2020)
- [Generalization through Memorization: Nearest Neighbor Language Models](https://mlsanity.com/paper/1911.00172/) (2019)
- [Convolutional Sequence to Sequence Learning](https://mlsanity.com/paper/1705.03122/) (2017)
- [Random Feature Attention](https://mlsanity.com/paper/2103.02143/) (2021)
- [Six Challenges for Neural Machine Translation](https://mlsanity.com/paper/1706.03872/) (2017)
- [Learning Deep Transformer Models for Machine Translation](https://mlsanity.com/paper/1906.01787/) (2019)
- [Massively Multilingual Neural Machine Translation in the Wild: Findings and Challenges](https://mlsanity.com/paper/1907.05019/) (2019)
- [Massively Multilingual Neural Machine Translation](https://mlsanity.com/paper/1903.00089/) (2019)
- [Understanding the Difficulty of Training Transformers](https://mlsanity.com/paper/2004.08249/) (2020)
- [Nearest Neighbor Machine Translation](https://mlsanity.com/paper/2010.00710/) (2020)
- [Synthesizer: Rethinking Self-Attention in Transformer Models](https://mlsanity.com/paper/2005.00743/) (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)
- [Transformers without Tears: Improving the Normalization of Self-Attention](https://mlsanity.com/paper/1910.05895/) (2019)
- [Finetuning Pretrained Transformers into RNNs](https://mlsanity.com/paper/2103.13076/) (2021)
- [Pre-training via Paraphrasing](https://mlsanity.com/paper/2006.15020/) (2020)
- [Retrieve and Refine: Improved Sequence Generation Models For Dialogue](https://mlsanity.com/paper/1808.04776/) (2018)

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

- [A Survey on Retrieval-Augmented Text Generation](https://mlsanity.com/paper/2202.01110/) (2022)
- [Efficient Methods for Natural Language Processing: A Survey](https://mlsanity.com/paper/2209.00099/) (2022)
- [PipeRAG: Fast Retrieval-Augmented Generation via Algorithm-System Co-design](https://mlsanity.com/paper/2403.05676/) (2024)
- [GNN-LM: Language Modeling based on Global Contexts via GNN](https://mlsanity.com/paper/2110.08743/) (2021)
- [Goodtriever: Adaptive Toxicity Mitigation with Retrieval-augmented Models](https://mlsanity.com/paper/2310.07589/) (2023)
- [Chameleon: a Heterogeneous and Disaggregated Accelerator System for Retrieval-Augmented Language Models](https://mlsanity.com/paper/2310.09949/) (2023)
- [Chunk-based Nearest Neighbor Machine Translation](https://mlsanity.com/paper/2205.12230/) (2022)
- [Augmenting Large Language Model Translators via Translation Memories](https://mlsanity.com/paper/2305.17367/) (2023)
- [Non-Exchangeable Conformal Language Generation with Nearest Neighbors](https://mlsanity.com/paper/2402.00707/) (2024)
- [Layer-wise Model Pruning based on Mutual Information](https://mlsanity.com/paper/2108.12594/) (2021)
- [Retrosynthesis Prediction with Local Template Retrieval](https://mlsanity.com/paper/2306.04123/) (2023)
- [Towards Robust k-Nearest-Neighbor Machine Translation](https://mlsanity.com/paper/2210.08808/) (2022)
- [Non-Parametric Domain Adaptation for End-to-End Speech Translation](https://mlsanity.com/paper/2205.11211/) (2022)
- [Simple and Scalable Nearest Neighbor Machine Translation](https://mlsanity.com/paper/2302.12188/) (2023)
- [Nearest Neighbor Knowledge Distillation for Neural Machine Translation](https://mlsanity.com/paper/2205.00479/) (2022)
- [Faster Nearest Neighbor Machine Translation](https://mlsanity.com/paper/2112.08152/) (2021)
- [Communication-Efficient Personalized Federated Learning for Speech-to-Text Tasks](https://mlsanity.com/paper/2401.10070/) (2024)
- [Efficient Machine Translation Domain Adaptation](https://mlsanity.com/paper/2204.12608/) (2022)
- [Improving Retrieval Augmented Neural Machine Translation by Controlling Source and Fuzzy-Match Interactions](https://mlsanity.com/paper/2210.05047/) (2022)
- [kNN-NER: Named Entity Recognition with Nearest Neighbor Search](https://mlsanity.com/paper/2203.17103/) (2022)
- [INK: Injecting kNN Knowledge in Nearest Neighbor Machine Translation](https://mlsanity.com/paper/2306.06381/) (2023)
- [GNN-SL: Sequence Labeling Based on Nearest Examples via GNN](https://mlsanity.com/paper/2212.02017/) (2022)
- [Multilingual k-Nearest-Neighbor Machine Translation](https://mlsanity.com/paper/2310.14644/) (2023)
- [Improving Robustness of Retrieval Augmented Translation via Shuffling of Suggestions](https://mlsanity.com/paper/2210.05059/) (2022)
- [Nearest Neighbor Language Models for Stylistic Controllable Generation](https://mlsanity.com/paper/2210.15762/) (2022)
- [Better Datastore, Better Translation: Generating Datastores from Pre-Trained Models for Nearest Neural Machine Translation](https://mlsanity.com/paper/2212.08822/) (2022)
- [Prompting Neural Machine Translation with Translation Memories](https://mlsanity.com/paper/2301.05380/) (2023)
- [Towards Example-Based NMT with Multi-Levenshtein Transformers](https://mlsanity.com/paper/2310.08967/) (2023)
- [N-Gram Nearest Neighbor Machine Translation](https://mlsanity.com/paper/2301.12866/) (2023)
- [Nearest Neighbor Machine Translation is Meta-Optimizer on Output Projection Layer](https://mlsanity.com/paper/2305.13034/) (2023)

## Abstract (arXiv)

Though nearest neighbor Machine Translation (kNN-MT) citepkhandelwal2020nearest has proved to introduce significant performance boosts over standard neural MT systems, it is prohibitively slow since it uses the entire reference corpus as the datastore for the nearest neighbor search. This means each step for each beam in the beam search has to search over the entire reference corpus. kNN-MT is thus two-orders slower than vanilla MT models, making it hard to be applied to real-world applications, especially online services. In this work, we propose Fast kNN-MT to address this issue. Fast kNN-MT constructs a significantly smaller datastore for the nearest neighbor search: for each word in a source sentence, Fast kNN-MT first selects its nearest token-level neighbors, which is limited to tokens that are the same as the query token. Then at each decoding step, in contrast to using the entire corpus as the datastore, the search space is limited to target tokens corresponding to the previously selected reference source tokens. This strategy avoids search through the whole datastore for nearest neighbors and drastically improves decoding efficiency. Without loss of performance, Fast kNN-MT is two-orders faster than kNN-MT, and is only two times slower than the standard NMT model. Fast kNN-MT enables the practical use of kNN-MT systems in real-world MT applications. The code is available at urlhttps://github.com/ShannonAI/fast-knn-nmt