Nearest-neighbor translation makes a frozen translation model speak a new domain, such as legal or medical text, without retraining. It stores the model's internal states for every token of a domain corpus. At each output step it looks up the most similar stored states and blends the words they point to into the model's own prediction. The catch is speed: one search over millions of vectors at every generated token makes decoding far slower than the network itself. The fastest fixes avoid the big search. For each input sentence they find a handful of similar reference sentences and build a tiny throwaway datastore from them, called a micro-datastore. Searching that is almost free. These fixes work when the test sentence closely resembles something in the corpus. They lose their benefit when it does not, because the useful matches are often single phrases buried in sentences that no sentence-level search would rank highly.
We propose to make the cheap search the default and the expensive search the exception, decided one token at a time. The decoder always queries the micro-datastore first. A small gate reads how good those neighbors look: how far away they are, whether they agree on the next word, and how confident the base model already is. From that it chooses one of three actions: trust the micro-datastore, escalate this one token to a compressed global index of the whole corpus, or ignore retrieval for this token. The same gate sets the mixing weight separately for each tier, because distances in a small, freshly computed store and distances in a quantized global index are on different scales. The claim is that full-index translation quality can be kept at close to micro-datastore speed, because only the minority of tokens whose fragments the sentence filter missed need the global search.
Core Claim and What Is New
Two families of work currently sit on opposite sides of a trade-off. Sentence-subset methods build a per-input micro-datastore. Subset Retrieval Nearest Neighbor Machine Translation retrieves similar source sentences with a sentence encoder and searches a quantized subset, reporting a 132.2x speedup over vanilla nearest-neighbor translation on WMT'19 German-English. Simple and Scalable Nearest Neighbor Machine Translation (SK-MT) uses BM25 plus edit-distance reranking to encode the top few reference sentences on the fly, reaching 90% of plain translation speed. Its authors state plainly that the method yields little to no gain when test sentences lack global similarity to the corpus, as on WMT'14. These two papers motivate the proposal: they show that most of the value lives in a few references, and that the sentence filter is the single point of failure.
The other family keeps the global index but makes it cheaper or skips it. Efficient Cluster-Based-Nearest-Neighbor Machine Translation compresses keys from 1024 to 64 dimensions with a small contrastively trained network and prunes clusters. Efficient k-Nearest-Neighbor Machine Translation with Dynamic Retrieval trains a classifier on base-model signals to skip searches. Efficient Nearest Neighbor Language Models found retrieval helps only 39% of the time on WikiText-103. These papers supply our methods: the compressed index becomes our second tier, and their skip features seed our gate. Their skip decisions, however, are made blind. They predict whether a search will help before seeing any neighbors.
What is new is that our escalation decision is made after a nearly free look at real neighbors, and that it chooses between two stores rather than between searching and not searching. Gap 3 in our research file notes that nobody falls back from the micro-datastore to a global index. A naive version of that fallback would decide per sentence, using the retrieval score. We argue the decision must be per token, because a well-matched sentence can still contain uncovered terms, and a poorly matched sentence can still share a key phrase. The sentence-level version is a central ablation, not a straw man.
Mechanism
At step $t$ the frozen model produces hidden state $h_t$ and distribution $P_{MT}$. The micro-datastore returns neighbors with distances. From these we compute a short feature vector $z_t$. It holds the nearest normalized distance, the fraction of the top-$k$ neighbors that share the majority target word, the sentence-retrieval score of the reference those neighbors came from, the base model's top-1 probability, and the decoding position (which Gao et al. found predicts retrieval utility). A two-layer gate maps $z_t$ to a choice among micro, global, and none, and to a mixing weight for the chosen tier:
$$P(w) = (1-\lambda_{\tau}(z_t))\,P_{MT}(w) + \lambda_{\tau}(z_t)\,P_{\tau}(w),\qquad \tau \in \{\text{micro},\text{global}\}$$
Here $P_\tau$ is the neighbor distribution from tier $\tau$, with its own temperature, and $\lambda_\tau$ is set to zero when the gate chooses "none." Expected per-token search cost is roughly the micro-search cost plus the escalation rate times the global-search cost. Speed therefore depends almost entirely on how often the gate escalates, and we report that rate everywhere.
The global tier is built once, offline, by running the frozen model over the corpus. Its keys are compressed with product quantization as in knn-seq: Efficient, Extensible kNN-MT Framework, or with the compact network of Wang et al. as a variant. The global tier involves no gradient updates to the translation model, so swapping a domain still means swapping files.
The gate is the only trained component. To preserve that property, its features are normalized per store, and we test whether a gate trained on one domain transfers to the others unchanged. If the gate needs per-domain training to work, the proposal loses much of its appeal, and the experiments are designed to reveal that.
Research Program
The work has three parts. First, a diagnostic study measures, per domain and per token, how often the micro-datastore lacks a correct neighbor that the full index has. This quantity directly bounds what escalation can recover. If it is near zero on IT, Medical, and Law, the idea has little room there, and we will say so. Second, we build the two-tier decoder in kNN-BOX (kNN-BOX: A Unified Framework for Nearest Neighbor Generation), whose separate datastore, retriever, and combiner modules make the tiers straightforward to compose. We use knn-seq for the quantized global index. Third, we study calibration across tiers, the question raised in Gap 1. Quantized distances do not share the temperature appropriate for exact micro-store distances, so we compare one shared mixing weight against tier-specific weights.
Baselines
The do-nothing reference is the frozen general-domain model with no retrieval. In the file, it scores 38.3 BLEU on IT (Nearest Neighbor Machine Translation), 40.3 on Medical (knn-seq), and 45.5 on Law (kNN-BOX). The quality ceiling is vanilla nearest-neighbor translation over the full uncompressed index. It reaches 45.99 BLEU on IT (Bridging the Domain Gaps in Context Representations for k-Nearest Neighbor Neural Machine Translation) and 55.2 on Medical (knn-seq). kNN-BOX reports Law rising from 45.5 to 63.6 with its augmentation, and adaptive nearest-neighbor translation reports 47.20 on IT (Efficient Cluster-Based-Nearest-Neighbor Machine Translation). The file has no full-index BLEU for Koran or Subtitles that we can use directly as a ceiling, so we will rerun every system ourselves rather than quote mismatched numbers.
The strongest speed competitor is SK-MT. It builds micro-datastores with no index at all, reports +1.0 BLEU over vanilla nearest-neighbor translation on Law, and runs at 90% of plain translation speed, so it is our own first tier run alone. Subset kNN-MT is the second subset competitor. Beating SK-MT means matching its speed within a stated margin, which we fix at no worse than 80% of plain translation speed, while closing at least half of any BLEU gap between SK-MT and the full index on each domain. It also means beating SK-MT clearly on the low-overlap bins described below.
The strongest global-index competitor is dynamic retrieval (kNN-MT-DR) run on top of the compressed global index. This is the obvious "stack existing tricks" system. Gao et al. report 1002 versus 478 tokens per second on Subtitles at batch size 128, with 41.83 average BLEU, a 0.74 drop from vanilla. We also run the cluster-compressed global index of Wang et al. alone, which reports 47.94 BLEU on IT.
All systems share the same base model, the same datastore text, the same index type wherever an index is used, the same hardware and batch sizes, and the same dev-set tuning budget for temperatures, $k$, and thresholds.
Three ablations isolate the key ingredient. Sentence-level escalation uses the global index for the whole sentence when its best retrieval score falls below a tuned threshold, and the micro-datastore otherwise. Always-union merges micro and global neighbors at every token. A single shared mixing weight replaces the tier-specific ones.
Why not just…?
Why not just retrieve more reference sentences in SK-MT? Raising the number of encoded references enlarges the micro-datastore. But each reference requires a forward pass at decode time, so cost grows linearly. More references also cannot recover fragments that sentence-level ranking never surfaces, because these come from sentences with low overall similarity, which is exactly the failure Dai et al. report on WMT'14. We sweep the number of references to 64 and plot BLEU against speed. If that curve reaches the full-index quality as cheaply as escalation does, our method is unnecessary.
Why not just fall back per sentence when the retrieval score is low? This is the most serious threat. It is trivial to build and may capture most of the benefit if missed fragments cluster in low-similarity sentences. Our diagnostic study measures exactly this: what share of tokens that need the global index fall inside high-scoring sentences. The sentence-level ablation runs on identical indices. If per-token escalation does not beat it on the low-overlap bins at matched escalation cost, we will report the simpler system as the recommendation.
Why not just run dynamic skipping over a compressed global index and drop micro-datastores? That stack already exists in pieces, with skip rates near 50%. Every query it does make still pays global-search cost, and its skip decision cannot see neighbor quality. Escalation should win when most useful tokens are covered by the micro-store. On redundant, high-volume domains like Subtitles, skipping over the global index may be just as good, and we expect the comparison to depend on the domain.
Why not just distill the datastore into adapters? Domain-Aware k-Nearest-Neighbor Knowledge Distillation for Machine Translation and INK: Injecting kNN Knowledge in Nearest Neighbor Machine Translation remove retrieval latency entirely. But they require retraining for each domain, and INK's training takes 3x to 4x longer. INK also reports a hybrid gap: keeping the datastore at inference still helps. Distillation also gives up the instant deletion property shown by SILO Language Models. We include INK's reported operating point as a speed reference but treat it as solving a different problem, since our system must keep domains swappable.
Proposed Experiments and Decisive Checks
We evaluate German-English translation on the IT, Medical, Law, Koran, and Subtitles domains, plus WMT'19 and WMT'14. We report BLEU and COMET, tokens per second at fixed batch sizes, escalation rate, and peak memory. Koran matters because it has low redundancy, and the file reports that pruning only 10% of it costs about one BLEU point. WMT'14 is a sanity case: the file reports little to no gain for any nearest-neighbor method there, so the correct behavior is for the gate to abstain and run at near-base speed, not to improve BLEU. For each domain test set we also bin sentences by their top BM25 score into quintiles. The decisive result lives in the bottom two quintiles, where SK-MT should fall toward the base model and escalation should track the full index.
The first decisive check is the diagnostic coverage gap. If the micro-datastore misses fewer than a few percent of the useful neighbors that the full index finds on every domain, the project shrinks to a negative result about sentence filtering's sufficiency, which is still worth reporting. The second is the per-token versus per-sentence ablation at matched escalation rates. The third is gate transfer: we train the gate on IT and run it unchanged on Law, Medical, and Koran, and the method keeps its zero-training swap property only if that transfer loses little against a per-domain gate. The fourth is calibration: tier-specific mixing weights should beat a shared weight mainly on escalated tokens, which would confirm that quantized global distances need their own scale.
References
- Subset Retrieval Nearest Neighbor Machine Translation
- Simple and Scalable Nearest Neighbor Machine Translation
- Efficient Cluster-Based-Nearest-Neighbor Machine Translation
- Efficient k-Nearest-Neighbor Machine Translation with Dynamic Retrieval
- Efficient Nearest Neighbor Language Models
- knn-seq: Efficient, Extensible kNN-MT Framework
- kNN-BOX: A Unified Framework for Nearest Neighbor Generation
- Nearest Neighbor Machine Translation
- Bridging the Domain Gaps in Context Representations for k-Nearest Neighbor Neural Machine Translation
- Domain-Aware k-Nearest-Neighbor Knowledge Distillation for Machine Translation
- INK: Injecting kNN Knowledge in Nearest Neighbor Machine Translation
- SILO Language Models: Isolating Legal Risk In a Nonparametric Datastore