# Faster Nearest Neighbor Machine Translation

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 39 of its 49 references that are in the map.
- First posted on arXiv 15 Dec 2021.

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

- [Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks](https://mlsanity.com/paper/2005.11401/) (2020)
- [Neural Machine Translation by Jointly Learning to Align and Translate](https://mlsanity.com/paper/1409.0473/) (2014)
- [Learning Phrase Representations using RNN Encoder-Decoder for Statistical Machine Translation](https://mlsanity.com/paper/1406.1078/) (2014)
- [Sequence to Sequence Learning with Neural Networks](https://mlsanity.com/paper/1409.3215/) (2014)
- [Neural Machine Translation of Rare Words with Subword Units](https://mlsanity.com/paper/1508.07909/) (2015)
- [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)
- [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)
- [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)
- [Diverse Beam Search: Decoding Diverse Solutions from Neural Sequence Models](https://mlsanity.com/paper/1610.02424/) (2016)
- [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)
- [Deep Encoder, Shallow Decoder: Reevaluating Non-autoregressive Machine Translation](https://mlsanity.com/paper/2006.10369/) (2020)
- [Finetuning Pretrained Transformers into RNNs](https://mlsanity.com/paper/2103.13076/) (2021)
- [Pre-training via Paraphrasing](https://mlsanity.com/paper/2006.15020/) (2020)
- [Improving Neural Language Models with a Continuous Cache](https://mlsanity.com/paper/1612.04426/) (2016)
- [Retrieve and Refine: Improved Sequence Generation Models For Dialogue](https://mlsanity.com/paper/1808.04776/) (2018)
- [BertGCN: Transductive Text Classification by Combining GCN and BERT](https://mlsanity.com/paper/2105.05727/) (2021)
- [Guiding Neural Machine Translation with Retrieved Translation Pieces](https://mlsanity.com/paper/1804.02559/) (2018)
- [Augmenting Transformers with KNN-Based Composite Memory for Dialogue](https://mlsanity.com/paper/2004.12744/) (2020)

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

- [Efficient Methods for Natural Language Processing: A Survey](https://mlsanity.com/paper/2209.00099/) (2022)
- [Chunk-based Nearest Neighbor Machine Translation](https://mlsanity.com/paper/2205.12230/) (2022)
- [Nearest Neighbor Knowledge Distillation for Neural Machine Translation](https://mlsanity.com/paper/2205.00479/) (2022)
- [kNN-NER: Named Entity Recognition with Nearest Neighbor Search](https://mlsanity.com/paper/2203.17103/) (2022)
- [GNN-SL: Sequence Labeling Based on Nearest Examples via GNN](https://mlsanity.com/paper/2212.02017/) (2022)
- [Nearest Neighbor Language Models for Stylistic Controllable Generation](https://mlsanity.com/paper/2210.15762/) (2022)
- [Prompting Neural Machine Translation with Translation Memories](https://mlsanity.com/paper/2301.05380/) (2023)
- [Rethinking Translation Memory Augmented Neural Machine Translation](https://mlsanity.com/paper/2306.06948/) (2023)

## Abstract (arXiv)

kNN based neural machine translation (kNN-MT) has achieved state-of-the-art results in a variety of MT tasks. One significant shortcoming of kNN-MT lies in its inefficiency in identifying the k nearest neighbors of the query representation from the entire datastore, which is prohibitively time-intensive when the datastore size is large. In this work, we propose Faster kNN-MT to address this issue. The core idea of Faster kNN-MT is to use a hierarchical clustering strategy to approximate the distance between the query and a data point in the datastore, which is decomposed into two parts: the distance between the query and the center of the cluster that the data point belongs to, and the distance between the data point and the cluster center. We propose practical ways to compute these two parts in a significantly faster manner. Through extensive experiments on different MT benchmarks, we show that Faster kNN-MT is faster than Fast kNN-MT citepmeng2021fast and only slightly (1.2 times) slower than its vanilla counterpart while preserving model performance as kNN-MT. Faster kNN-MT enables the deployment of kNN-MT models on real-world MT services.