A frozen translation model can be adapted to a new domain such as law or medicine without any training. You store the model's internal context vectors for every token of in-domain text, together with the token that came next. At translation time you look up the most similar stored contexts and blend their next-token votes with the model's own prediction. This approach, nearest-neighbor machine translation, gains large amounts of BLEU over the unadapted model. Its cost is a datastore with one 1024-dimensional vector per training token, and a lookup over that datastore at every decoding step. Existing compression work treats this as a geometry problem: make the keys shorter, or delete keys that look redundant. The one test of the simplest option, linear PCA, failed badly. Heuristic pruning also costs about a BLEU point in low-redundancy domains at only 10% pruning.
We propose a different target. The blended next-token distribution is what the system actually uses, so compression should preserve that distribution rather than the geometry of the keys. The retrieval distribution is a kernel-smoothed class-probability estimate. Recent kernel thinning theory therefore applies almost directly: it picks representative subsets whose error depends on the spectral decay of the kernel rather than on dimension. Two changes adapt it to translation. First, we thin with a joint kernel over the context vector and the target token. That kernel is block-diagonal by token, which predicts that the datastore is low-rank within each token block even when it is not low-rank globally. This offers an explanation for why global PCA fails. Second, we weight each entry by how much it corrects the base model, so that entries the model already predicts well are cheap to discard. The claim is that this residual-weighted, token-blocked kernel thinning can remove most of a datastore while keeping BLEU close to the full store, including in the Koran and Law domains, where heuristic pruning breaks.
Background and Where the Gap Is
In Nearest Neighbor Machine Translation, the retrieval distribution weights each of the top-$k$ neighbors by $\exp(-\|h-k_j\|^2/T)$ and groups the weights by target token. Here $h$ is the query context vector, $k_j$ a stored key, and $T$ a temperature. The result is then linearly interpolated with the model's softmax using a weight $\lambda$. This paper supplies the mechanism we compress. Up to top-$k$ truncation, the retrieval distribution is a Nadaraya–Watson estimator with a Gaussian kernel and a categorical label. That observation lets thinning theory in. Later work adapts the blending. Adaptive Nearest Neighbor Machine Translation learns how many neighbors to trust. Towards Robust k-Nearest-Neighbor Machine Translation conditions the weight on the base model's confidence and trains against noisy or pruned stores. Both leave the datastore itself untouched, so our work is complementary to them.
Two papers attack the datastore directly, and they motivate and constrain this proposal. Efficient Cluster-Based-Nearest-Neighbor Machine Translation (PCKMT) reports that linear PCA on the keys destroys retrieval. It replaces PCA with a contrastively trained network that maps keys to 64 dimensions, and it prunes by clustering with DBSCAN or BIRCH and subsampling within clusters, guided by perplexity. That pruning loses about 1 BLEU on Koran and Law at 10% pruning. This is the negative result we must explain. Fast Nearest Neighbor Machine Translation restricts search to sentence-specific candidates built from word alignments, and uses product quantization, a generic vector-compression scheme. Bridging the Domain Gaps in Context Representations moves keys with a trained network to repair domain shift. All three change keys or search heuristically. None asks which subset of entries preserves the output distribution.
The method comes from the thinning literature. Low-Rank Thinning shows that kernel halving and Compress produce subsets whose kernel-mean error is governed by the kernel matrix's effective rank. Thinformer applies this to attention: 82.18% ImageNet top-1 against 82.55% for exact attention. Supervised Kernel Thinning shows that for Nadaraya–Watson prediction, inputs and labels must be thinned jointly through a task-specific meta-kernel. Its analysis covers only scalar labels, and none of these papers touch external token datastores, domain shift, or blending with a parametric model. We extend them in exactly these three respects.
Core Claim
Let each datastore entry be $(k_i, y_i)$, with key $k_i$ and target token $y_i$. For a query $h$, the unnormalized retrieval score of token $v$ is a kernel mean over the entries labeled $v$. Preserving every such score for every query is the same as preserving the empirical measure under the joint kernel
$$K\big((k,y),(k',y')\big) = \exp\!\left(-\|k-k'\|^2/T\right)\,\mathbf{1}[y=y'].$$
This kernel matrix is block-diagonal by token, so its effective rank is the sum of per-token effective ranks. Global PCA ignores the blocks: it spends its dimensions separating tokens whose contexts overlap, which is exactly the overlap PCKMT's visualizations show. The per-token blocks may still decay quickly.
Our first claim is diagnostic. Per-token effective rank, measured cheaply by random-feature spectra, should be low even where the global spectrum is flat. It should also predict how compressible each domain is. We expect Koran and Law to have higher per-token rank relative to their size, which would explain why they resist pruning.
The second claim concerns what to preserve. The system outputs $(1-\lambda)P_{LM} + \lambda P_{kNN}$, where $P_{LM}$ is the base model's softmax and $P_{kNN}$ the retrieval distribution. An entry whose token the base model already assigns high probability in its own context contributes little to the final distribution. We therefore thin a weighted measure in which entry $i$ carries weight $w_i = 1 - P_{LM}(y_i \mid c_i)$, the base model's residual error on that entry, floored at a small value to keep coverage. Retained entries store a scalar multiplicity so the kernel means stay calibrated.
By the Low-Rank Thinning analysis, kernel-mean error for thinned subsets decays roughly as $1/n_{out}$ times rank-dependent factors. Uniform subsampling decays only as $1/\sqrt{n_{out}}$. That gap is the source of the expected advantage.
Research Program
The work has three stages.
Diagnosis. For all five domains, we compute global and per-token-block kernel spectra of the key matrices from the WMT'19 German–English model. We test whether PCKMT's PCA failure is reproduced and whether it coincides with a flat global spectrum alongside fast per-token decay. We also measure how per-token rank relates to the BLEU loss from pruning.
Thinning algorithm. We build a categorical, residual-weighted thinner. It runs Compress++ independently within each token block, which parallelizes cleanly and makes the 154M-entry Subtitles store tractable. Weights are handled by residual-proportional stratified resampling before halving. Weighted halving is a known technical risk, and we will compare against weighted kernel herding if resampling proves too noisy. Rare tokens with tiny blocks are kept whole.
Analysis. We derive a bound on the total-variation gap between the full-store and thinned-store final distributions. The bound has three terms: $\lambda$, the per-block kernel-mean error, and a term for top-$k$ truncation, which the theory does not cover and which we will measure empirically.
Baselines
The naive reference points are the unadapted WMT'19 model, which is the "do nothing" option, and the full datastore with vanilla retrieval. The full store is the ceiling we try to approach at a fraction of its size.
The strongest existing competitor is PCKMT from Efficient Cluster-Based-Nearest-Neighbor Machine Translation. It is the only method in the file that prunes kNN-MT datastores with reported numbers. It reports IT BLEU of 47.94 against 47.20 for its adaptive baseline, and Subtitles BLEU of 31.72 at 30% pruning against 31.36 unpruned, together with the roughly 1-BLEU drop on Koran and Law at 10% pruning. To beat it, we must match or exceed its BLEU at equal retained-entry counts, and lose less than half its Koran/Law drop at 10%. We then extend the pruning curve to 50% and 90%, where PCKMT reports no numbers.
We run PCKMT's pruning on our pipeline, with the same base model, datastores, and adaptive-retrieval head. Its clustering and perplexity thresholds get the same number of tuning trials on the development sets as our floor and temperature settings. Because PCKMT also compresses dimensions, we compare two variants: our thinning on full 1024-d keys, and our thinning on its 64-d compact keys. This separates entry selection from key compression.
We also compare against Towards Robust k-Nearest-Neighbor Machine Translation, using its released code (Robust-knn-mt). It reports +4.47 BLEU over adaptive kNN-MT on a 60%-pruned store, so it is the strongest method for tolerating pruning. We compare its robust gating on a randomly pruned store with robust gating on our thinned store, at equal size.
Four further baselines complete the set. Product quantization, as in Fast Nearest Neighbor Machine Translation, is matched at equal bytes rather than equal entries. Uniform random subsampling is the obvious cheap alternative. Per-token k-means prototypes with counts retain one centroid per cluster. Condensed nearest-neighbor editing is classical classification-set reduction.
Two ablations isolate our ingredients. Unweighted joint-kernel thinning isolates the residual weighting. Residual-weighted uniform sampling isolates kernel halving, which is the low-rank ingredient.
Why not just…?
Why not just subsample uniformly? Uniform sampling is unbiased, so at mild pruning rates its variance may be harmless, and in large redundant stores like Subtitles it could match us. The thinning theory predicts the gap widens as the retained fraction shrinks and as per-token rank grows. Our 90% compression runs on Koran and Law are designed to show whether that happens. If uniform sampling ties us there, the low-rank claim fails, and we will report that.
Why not just drop entries the base model already predicts correctly? This is the most serious threat, because it captures the residual idea with a single threshold. It is included as a baseline at equal size. Our hypothesis is that hard thresholding removes entire dense regions, and so breaks kernel means in contexts where the model is confident but wrong. Weighted thinning keeps a calibrated sample there. If hard thresholding matches us, the paper's contribution reduces to the diagnostic and that simple rule, and we will say so.
Why not just use per-token k-means prototypes or PCKMT clustering? Clustering keeps representatives but not kernel-mean fidelity. Centroids lie off the data manifold and shrink the retrieval distribution's spread. PCKMT's own Koran/Law degradation is evidence this falls short in low-redundancy domains. The head-to-head at equal entry counts settles it.
Why not just fine-tune or use a low-rank adapter? Fine-tuned models collapse outside their domain; Six Challenges for Neural Machine Translation reports 3.9 BLEU for a medical model tested on law. Per-domain checkpoints also defeat multi-domain serving. We do not re-litigate this. Our question is how cheap the non-parametric store can be made.
Proposed Experiments and Decisive Checks
We use the Koehn–Knowles German–English multi-domain benchmark (Koran 0.5M, IT 3.6M, Medical 6.9M, Law 19M, Subtitles 154M datastore tokens) with the WMT'19 base model. Metrics are SacreBLEU, datastore bytes, and decoding latency. The most direct fidelity measure is the average total-variation distance between full-store and compressed-store final distributions on held-out decoding steps.
Each method is run at retained fractions of 90%, 50%, 25%, and 10%. The first decisive check is the Koran/Law 10%-pruning point, where PCKMT reports a roughly 1-BLEU loss. The second is the slope of fidelity versus retained size. Thinning should show a steeper log-log decline in total-variation error than uniform sampling if the rank-based rate holds.
The third check tests the diagnostic's predictive power. Per-token effective rank, measured before any pruning, should rank the five domains by their observed BLEU loss under compression. If it does not, the low-rank explanation of PCA's failure is wrong, even if the thinner still works.
References
- Nearest Neighbor Machine Translation
- Adaptive Nearest Neighbor Machine Translation
- Towards Robust k-Nearest-Neighbor Machine Translation
- Efficient Cluster-Based-Nearest-Neighbor Machine Translation
- Fast Nearest Neighbor Machine Translation
- Bridging the Domain Gaps in Context Representations for k-Nearest Neighbor Neural Machine Translation
- Low-Rank Thinning
- Thinformer: Guaranteed Attention Approximation via Low-Rank Thinning
- Supervised Kernel Thinning
- Six Challenges for Neural Machine Translation