Nearest Neighbor Language Models

Retrieval at the level of single tokens. A kNN-LM stores one entry for every position of a text, a vector for the context and the token that came next, and at each step mixes the language model's prediction with a distribution built from the nearest stored contexts. The construction of Khandelwal et al. (2020) is stated in full; the mixed loss is proved convex in the mixing weight, with an exact test for when any mixing helps and a bound by the two models' own losses; the limits of the neighbor distribution in its temperature are derived; and the published results are reported with their tables. A small character-level GPT of the walkthrough's design, trained 30 times on tiny-shakespeare and given a datastore of its whole training text, lowered its validation perplexity from 7.59 to 6.38, mostly at positions whose recent characters occur in the training text. RETRO is described in outline as the chunk-level counterpart. Four worked problems compute a neighbor distribution, an optimal weight, a datastore's size and the temperature limits by hand.

In the last tenth of tiny-shakespeare, the text on which the site's small GPT is validated, a speaker's name begins a new speech: "KATHARIN", and the next character is A. A small character-level model of the walkthrough's design, trained on the first nine tenths, gives that A a probability of 0.0091. Its training text contains the string "KATHARINA" at the head of another speech, and the model's own vector for the validation context lies very close to its vector for that training context. Can a language model improve its predictions by looking up, at each step, the places in a text where it was in a similar state, and what came next there?

It can, and the method that does so is the nearest neighbor language model, or kNN-LM, of Khandelwal, Levy, Jurafsky, Zettlemoyer and Lewis (2020). A kNN-LM keeps a datastore with one entry for every token of a text: the model's vector for the context before the token, and the token itself. At each prediction it finds the stored contexts nearest to the current one, turns their next tokens into a probability distribution, and mixes that distribution with the model's own. No weight of the model changes. In the example, the nearest stored context ends "KATHARIN" followed by A, the neighbor distribution gives A a probability of 0.9993, and the mixture, with the weight 0.65 tuned for this model, gives it 0.6527.

Here is the route. First we state the model exactly. Then we prove three facts about the mixing weight: the mixed loss is convex in it, an exact test says when any mixing helps, and the mixed loss is bounded by the two models' own losses. Next come the limits of the neighbor distribution in its two settings, the cost of a datastore, and the paper's results. The experiment then builds a kNN-LM on the small GPT, 30 times. Finally RETRO, which retrieves chunks of text and reads them with attention, is set beside it as the other end of the design space. The article assumes the transformer of Assembling the Transformer Block, perplexity as defined in Perplexity and Source Coding, and exact and approximate nearest-neighbor search from Nearest Neighbor Search in High Dimensions. The numbers are computed by tools/experiments/rag/nearest-neighbor-language-models.py; the article uses the unit's notation, with capital $P$ for probabilities.

The model

The idea in plain words. A trained language model already maps every context to a vector before it predicts the next token. Run it once over a text and store, for every position, that vector together with the token that actually came next. To predict at a new context, find the stored vectors nearest to its vector and look at what came next after them. Their votes, weighted by closeness, form a second next-token distribution, and the final prediction mixes the two.

The formal version. The notation follows Khandelwal et al. (2020, Section 2), with the unit's capital $P$ for probabilities.

  • A language model gives, for a context $c$ (the tokens before a position), a distribution $P_{\mathrm{LM}}(y \mid c)$ over the next token $y$, and computes on the way a vector $f(c) \in \mathbb{R}^m$. In a Transformer, $f(c)$ can be any intermediate vector at the last position of $c$.
  • A datastore is built from a text collection $\mathcal{D}$ by one forward pass of the trained model: for each training example $(c_i, w_i)$, a context and the token that followed it, store the key $\vec u_i = f(c_i)$ and the value $v_i = w_i$. The datastore is the set $\{(\vec u_i, v_i)\}$, one entry per token of $\mathcal{D}$ (their Equation 1).
  • At a new context $c$, compute $\vec u = f(c)$ and retrieve the set $\mathcal{N}$ of the $k$ entries whose keys are nearest by squared Euclidean distance $d_i = \lvert \vec u - \vec u_i \rvert^2$.
  • The nearest neighbor distribution gives each token the softmax weight of the neighbors that have it as their value (their Equation 2): $$P_{k\mathrm{NN}}(y \mid c) = \frac{\sum_{i \in \mathcal{N}} \mathbf{1}[v_i = y]\, e^{-d_i}}{\sum_{i \in \mathcal{N}} e^{-d_i}}.$$ A token that no neighbor has as its value gets probability 0.
  • The kNN-LM mixes the two with a weight $\lambda \in [0, 1]$ tuned on validation data (their Equation 3): $$P(y \mid c) = \lambda\, P_{k\mathrm{NN}}(y \mid c) + (1 - \lambda)\, P_{\mathrm{LM}}(y \mid c).$$

Nothing is trained. The model's parameters, and therefore its representation $f$, stay exactly as they were; only a datastore is added, which can hold the training text or any other text. The paper's own example (Figure 1) shows the intent: a test context ending "Obama's birthplace is" sits close to training contexts such as "Obama was born in", whose next word was Hawaii, so the neighbors put most of their mass on Hawaii even if the model alone is unsure.

The construction has two predecessors on this site. The vote of the nearest labeled examples is the k-nearest neighbors classifier, here with distance-weighted votes and with the next token as the label. And the mixture is the same linear interpolation as Jelinek-Mercer smoothing in language models for retrieval, with the neighbor distribution in the place of the document model. What is new is where the similarity comes from: not from shared words, but from the model's own vectors, which place contexts close when the model has learned that they lead to similar continuations. Khandelwal et al. put the hypothesis behind the method in one sentence: "the representation learning problem may be easier than the prediction problem" (Section 1).

Two practical choices complete the definition. A temperature $T > 0$ can divide the distances, $e^{-d_i/T}$ in place of $e^{-d_i}$; the paper uses $T = 1$, and this article's experiment tries others, because the scale of the distances depends on the model. And the key $f(c)$ must be chosen. The paper compared vectors from the final layer of its Transformer and found the input to the final feedforward layer, taken after its layer normalization, best (Section 5, Table 5).

Choosing the weight: the loss is convex

The weight $\lambda$ is tuned by trying values on validation text. The question is whether this search can be fooled: could the loss have several valleys, so that a coarse grid finds a poor one? It cannot.

Fix a validation text of $n$ positions. At position $t$ let $a_t = P_{k\mathrm{NN}}(y_t \mid c_t)$ and $b_t = P_{\mathrm{LM}}(y_t \mid c_t)$ be the two models' probabilities of the token that actually came next. The mixed model's average loss in nats (natural logarithms) is $$\mathcal{L}(\lambda) = -\frac{1}{n}\sum_{t=1}^n \ln\big(\lambda a_t + (1-\lambda) b_t\big),$$ and its perplexity is $e^{\mathcal{L}(\lambda)}$, so minimizing one minimizes the other. Assume $b_t > 0$ for every $t$, as for any model with a softmax output.

Proposition 1 (convexity). $\mathcal{L}$ is convex on $[0, 1)$, and strictly convex unless $a_t = b_t$ at every position. Every local minimum is therefore the global minimum, and when the convexity is strict there is exactly one minimizing weight.

Proof. Write $m_t(\lambda) = \lambda a_t + (1 - \lambda) b_t = b_t + \lambda(a_t - b_t)$, which is positive on $[0, 1)$ since $b_t > 0$ and $a_t \ge 0$. Then $$\mathcal{L}'(\lambda) = -\frac1n \sum_t \frac{a_t - b_t}{m_t(\lambda)}, \qquad \mathcal{L}''(\lambda) = \frac1n \sum_t \frac{(a_t - b_t)^2}{m_t(\lambda)^2} \ge 0,$$ with equality only if every $a_t = b_t$. A twice-differentiable function with a nonnegative second derivative on an interval is convex there, and with a positive one strictly convex. For a convex function a local minimum is global; for a strictly convex one the minimizer is unique. $\square$

Proposition 2 (when mixing helps at all). The slope at $\lambda = 0$ is $$\mathcal{L}'(0) = 1 - \frac{1}{n}\sum_{t=1}^n \frac{a_t}{b_t}.$$ So adding a small weight of the neighbor distribution lowers the loss exactly when the average of the ratios $a_t/b_t$ exceeds 1, and by convexity the best weight is then positive. If $a_t = 0$ at even one position, $\mathcal{L}(\lambda) \to \infty$ as $\lambda \to 1$, so the best weight is below 1.

Proof. At $\lambda = 0$, $m_t = b_t$, and $\mathcal{L}'(0) = -\frac1n\sum_t (a_t - b_t)/b_t = -\frac1n\sum_t a_t/b_t + 1$. If $\mathcal{L}'(0) < 0$, the loss decreases just to the right of 0, so the minimum is not at 0; by Proposition 1 it is the unique point where the slope changes sign, or the right end. If some $a_t = 0$, the term $-\ln((1-\lambda) b_t)$ grows without bound as $\lambda \to 1$. $\square$

The ratio $a_t/b_t$ is how many times more likely the neighbors find the true token than the model does. The test does not ask that the neighbors be better on average in log loss; a few positions where the neighbors are many times more confident than the model can carry the average over 1 even if the neighbors are worse at most positions. This is consistent with the paper's qualitative finding that the gains come from "rare patterns" (Section 6), although the paper does not state the ratio test.

Proposition 3 (never worse than the average of the two losses). For every $\lambda \in (0, 1]$, $$\mathcal{L}(\lambda) \le \lambda\, \mathcal{L}_{k\mathrm{NN}} + (1 - \lambda)\, \mathcal{L}_{\mathrm{LM}},$$ where $\mathcal{L}_{k\mathrm{NN}} = -\frac1n\sum_t \ln a_t$ (which is $+\infty$ if some $a_t = 0$) and $\mathcal{L}_{\mathrm{LM}} = -\frac1n \sum_t \ln b_t$ are the two models' own losses. At $\lambda = 0$ the left side is $\mathcal{L}_{\mathrm{LM}}$, which the right side equals if $0 \cdot \mathcal{L}_{k\mathrm{NN}}$ is read as 0.

Proof. The logarithm is concave, so $\ln(\lambda a + (1 - \lambda) b) \ge \lambda \ln a + (1-\lambda)\ln b$ for $a, b > 0$ (Jensen's inequality with two points). If $a_t = 0$ and $\lambda > 0$, the term $\lambda \ln a_t$ is $-\infty$ and the inequality holds trivially. Negate and average over $t$. $\square$

The bound is weak when one model is poor, and the neighbor distribution alone usually is: it gives 0 to every token absent from the $k$ neighbors, so $\mathcal{L}_{k\mathrm{NN}}$ is infinite whenever that happens once. The mixture is what makes the neighbors usable.

What the neighbor weights do: $k$ and the temperature

The neighbor distribution has two settings, the number of neighbors $k$ and the temperature $T$. Their extremes are simple distributions.

Proposition 4 (temperature limits). Fix the $k$ neighbors and their distances, and let $d_{\min}$ be the smallest of them. (a) As $T \to 0$, $P_{k\mathrm{NN}}(y \mid c)$ tends to the share of the neighbors at distance $d_{\min}$ that have value $y$; with a unique nearest neighbor, all mass goes to its value. (b) As $T \to \infty$, it tends to the share of all $k$ neighbors that have value $y$, an unweighted vote.

Proof. Divide the numerator and the denominator by $e^{-d_{\min}/T}$: each weight becomes $e^{-(d_i - d_{\min})/T}$. As $T \to 0$ this tends to 1 for $d_i = d_{\min}$ and to 0 for $d_i > d_{\min}$, which gives (a). As $T \to \infty$ every weight tends to $e^0 = 1$, which gives (b). $\square$

Between the limits the temperature sets how fast the weight falls with distance. Adding the same constant to every $d_i$ changes nothing (the proof divides it out), so what matters is the gaps $d_i - d_{\min}$ among the retrieved neighbors, measured against $T$. That is why $T = 1$ is not a neutral choice: if the neighbors' distances differ from the nearest one's by tens, $T = 1$ is close to the nearest-neighbor limit, and if they differ by hundredths, close to the unweighted vote. The paper's keys were 1,024-dimensional and the experiment's are 64-dimensional, so the same formula can behave differently.

The number of neighbors acts differently. More neighbors can only add tokens to the support of the distribution, and each added neighbor is farther than those before it. In the paper, perplexity on WikiText-103 improved monotonically as $k$ grew to 1,024, and "even a small number of neighbors ($k = 8$)" was enough for a then state-of-the-art result (Section 5, Figure 4).

What it costs

A kNN-LM moves work from training to storage and search. The datastore has one entry per token of its text: a key of $m$ numbers and a value. For WikiText-103, with 103 million training tokens (Section 3) and the paper's 1,024-dimensional keys, full-precision keys of 4 bytes per number would take $103 \times 10^6 \times 1{,}024 \times 4 \approx 4.2 \times 10^{11}$ bytes, about 422 GB. The paper did not store them so for search. It built an index with the FAISS library that learned 4,096 cluster centroids from 1 million sampled keys, stored each key quantized to 64 bytes, and probed 32 clusters per query, which is the inverted file with product quantization of Inverted File Indexes for Vectors and Product Quantization; it then computed the distances of the 1,024 retrieved neighbors with the full-precision keys for WikiText-103, which improved perplexity from 16.5 to 16.06 compared with the quantized distances (Sections 3 and 5). At 64 bytes per key the 103 million keys take about 6.6 GB. Building the index took about two hours on one CPU, and evaluating the validation set with 1,024 neighbors per token about 25 minutes (Section 3, "Computational Cost").

The search is the price of every predicted token. An exact search over all $\lvert \mathcal{D} \rvert$ keys of $m$ numbers costs $\lvert \mathcal{D} \rvert\, m$ multiply-adds per token, which is why the paper's index is approximate. Retrieval-augmented models that retrieve once per question pay a search per question; a kNN-LM pays one per token.

What the paper reported

Khandelwal et al. (2020) applied the kNN-LM to a Transformer language model whose architecture and training they took unchanged from earlier work: 16 layers, 16 attention heads, 1,024-dimensional hidden states, 247 million parameters, reading 3,072 tokens of context on WikiText-103 (Section 3). The datastore was the model's own training text, so the experiment asks whether a model can gain by looking up the very text it was trained on.

Model, WikiText-103 Validation perplexity Test perplexity
Base language model 17.96 18.65
+ kNN-LM 16.06 16.12
+ continuous cache 17.67 18.27
+ kNN-LM + continuous cache 15.81 15.79

(Table 1; medians of three random seeds. The continuous cache retrieves from earlier in the same test document instead of from the training set.) On the Toronto Books Corpus, the kNN-LM lowered test perplexity from 11.89 to 10.89 (Table 2). The best weight was $\lambda = 0.25$ on WikiText-103 (Figure 5).

Three further results bear on retrieval as a substitute for training.

  • More data without training. A model trained on 100 million tokens of Wikipedia (WIKI-100M) and given a datastore of about 3 billion tokens (WIKI-3B) reached a test perplexity of 13.73, against 19.59 for the same model alone and 15.17 for a model trained on all 3 billion tokens (Table 3). Perplexity fell steadily as the datastore grew, and the best $\lambda$ grew with it (Figure 2).
  • Domain adaptation. A model trained on Wikipedia scored 34.84 on the books test set; with a datastore of the books' training text, 20.47; a model trained on books, 11.89 (Table 4). The best weight for this use was $\lambda = 0.65$ (Figure 5).
  • Which vector to use as the key. On WikiText-103 validation: no datastore 17.96; the model's output 17.07; the output after layer normalization 17.01; the input to the final feedforward network after layer normalization 16.06, before it 17.06; the input to the final self-attention after layer normalization 16.76, before it 17.14 (Table 5).

The analysis section adds two controls. Interpolating the Transformer with $n$-gram models instead of the neighbor distribution gained about 0.2 perplexity points; the authors conclude that this "highlights the need to use the learned representation function $f(\cdot)$ to measure similarity between more varied contexts" (Section 6, Figure 7). And a Transformer trained without dropout until it memorized its training set reached a validation perplexity of 28.59; mixed with the original model it gained 0.1 points, against 1.9 for the kNN-LM (Section 6, Figure 8). Explicit memory helped where memorization in the weights did not. The authors' summary of where the neighbors help: "rare patterns", such as "factual knowledge, names, and near-duplicate sentences from the training set" (Section 6).

A kNN-LM on the site's small GPT

The paper's models are far beyond a laptop. The question here is smaller: does the mechanism work on a model of the kind built in Language Models from Scratch, with its own training text as the datastore, and how do the weight, the number of neighbors, the temperature and the size of the datastore behave?

The model. A character-level GPT with the walkthrough's architecture (token and position embeddings, blocks of masked multi-head attention and a four-times-wide ReLU feedforward layer, each with layer normalization before it and dropout, a final layer normalization and a linear output layer), but much smaller than the walkthrough's final model so that 30 copies could be trained on a shared CPU: width 64 instead of 384, 2 blocks instead of 6, 4 heads instead of 6, a context of 32 characters instead of 256, dropout 0.1 instead of 0.2, and 600 steps of Adam (PyTorch's AdamW with weight decay 0, which is the same update) on batches of 64 windows, with a learning rate of 0.003 decayed to 0 along a cosine, where the walkthrough's final settings use a learning rate of 0.0003 with no schedule given. It has 110,145 parameters. The text is tiny-shakespeare, the file of the char-rnn repository (Karpathy, 2015), with the walkthrough's split (Tiny Shakespeare Data Pipeline): the first 1,003,854 characters for training and the last 111,540 for validation. Each of the 30 seeds (0 to 29) sets the initial weights and the sampling of batches.

The reduced model is a weak one. Over all of the validation text its loss is 2.080 nats per character (median over the 30 seeds; quartiles 2.075 and 2.084), a perplexity of 8.01 (7.96 to 8.04). The walkthrough's full model reached 1.48 nats, a perplexity of about 4.4 (Scaling the Shakespeare GPT). The results below are for this small model and are not a prediction for a large one.

The datastore. For each seed, one entry per training position that has a next character, 1,003,853 entries: the key is the 64-dimensional input of the last block's feedforward layer after its layer normalization, the paper's best choice of key, and the value is the next character. Each position is read in a window of 32 characters chosen so that it sees between 17 and 32 characters of context (fewer only at the very start of the text), and validation positions are read the same way.

The evaluation. Every 55th position of the validation text, 2,028 positions, the same for every seed. For each, the 1,024 nearest keys are found by exact search over all 1,003,853 (a brute-force scan, not the paper's approximate index), and the perplexity of the mixture is computed for $\lambda = 0, 0.05, \dots, 0.95$, for $k$ from 1 to 1,024, and for temperatures from $1/4$ to 16. On these positions the model alone has a perplexity of 7.59 (7.55 to 7.65). Every figure is a median over the 30 seeds with the first and third quartiles in parentheses, and every comparison is between settings on the same positions.

The weight. With the paper's settings, $k = 1{,}024$ and $T = 1$, the best weight was 0.65 (the median over seeds; quartiles 0.6125 and 0.65), and it lowered the perplexity from 7.59 to 6.38 (6.26 to 6.49).

Perplexity of the kNN-LM on the 2,028 validation positions against the weight on the neighbor distribution, with k = 1,024 and T = 1, for datastores holding the first 10%, 30% and all of the training text: medians over 30 seeds, with the band between the first and third quartiles; circles mark each curve's minimum, and the vertical axis is cut at 8. Notice that every curve falls from the model's own perplexity at 0, has one minimum as Proposition 1 requires, and rises toward 1 (the grid stops at 0.95), where the positions to which the neighbors give no probability weigh more and more; the larger the datastore, the lower and further right the minimum.
Perplexity of the kNN-LM on the 2,028 validation positions against the weight on the neighbor distribution, with k = 1,024 and T = 1, for datastores holding the first 10%, 30% and all of the training text: medians over 30 seeds, with the band between the first and third quartiles; circles mark each curve's minimum, and the vertical axis is cut at 8. Notice that every curve falls from the model's own perplexity at 0, has one minimum as Proposition 1 requires, and rises toward 1 (the grid stops at 0.95), where the positions to which the neighbors give no probability weigh more and more; the larger the datastore, the lower and further right the minimum.

Proposition 2 can be checked on the data. The mean of the ratios $a_t/b_t$ at $\lambda = 0$ was 2.23 (2.07 to 2.37), above 1 for every seed, so the slope at 0 is negative and the best weight positive, as it was for every seed. At 11 of the 2,028 positions (median over the seeds; quartiles 10 and 13), none of the 1,024 neighbors had the true next character as its value, so $P_{k\mathrm{NN}} = 0$ there, and by Proposition 2 the best weight must be below 1. One such position is inside the speaker name PROSPERO in the validation text: the name does not occur in the training text, so no neighbor can supply its next letter.

Neighbors and temperature.

Neighbors $k$ Temperature $T$ Best weight Perplexity
(model alone) 7.59 (7.55 to 7.65)
1 any 0.15 7.05 (6.93 to 7.12)
4 1 0.30 6.71 (6.57 to 6.80)
16 1 0.45 6.51 (6.34 to 6.59)
64 1 0.60 6.41 (6.29 to 6.50)
256 1 0.60 6.38 (6.26 to 6.49)
1,024 1 0.65 6.38 (6.26 to 6.49)
1,024 1/4 0.40 6.45 (6.33 to 6.55)
1,024 1/2 0.55 6.33 (6.24 to 6.42)
1,024 2 0.70 6.58 (6.46 to 6.63)
1,024 4 0.80 6.82 (6.73 to 6.88)

More neighbors helped, as in the paper's Figure 4, with most of the gain by $k = 64$; with one neighbor the temperature cannot matter, since a single weight always normalizes to 1. The temperature mattered more than $k$ beyond 64: a temperature of $1/2$ was slightly better than the paper's 1, and larger temperatures, which move the distribution toward an unweighted vote of the 1,024 neighbors (Proposition 4), were clearly worse. The keys here are 64-dimensional, and the gaps among the neighbors are small: over the 2,028 positions, the median gap between the squared distances of the nearest and the second neighbor was 0.116, and between the nearest and the eighth 0.62 (medians over the seeds of each seed's median). Measured by the exponential of the weights' entropy, at $T = 1$ the weight is spread over about 76 neighbors at a typical position (about 30 at $T = 1/2$ and 184 at $T = 2$), far from either limit of Proposition 4. The example below, with gaps of 8.7 to 9.3, is a rare near-exact match: a gap of that size between the first two neighbors occurred at about one position in 2,028. Why $1/2$ did best here was not tested. The best weight rose as the neighbor distribution improved, from 0.15 with one neighbor to 0.65 with 1,024.

The size of the datastore. Datastores made of a prefix of the training text, with the same model:

Datastore Entries Best weight Perplexity
first 10% of the training text 100,385 0.15 7.42 (7.36 to 7.46)
first 30% 301,156 0.30 7.18 (7.11 to 7.23)
all of it 1,003,853 0.65 6.38 (6.26 to 6.49)

Perplexity fell, and the best weight rose, as the datastore grew. That is the pattern of the paper's Figure 2, there with datastores of up to 3 billion tokens.

Where the neighbors help. For each evaluation position, the script finds the longest string ending at the true next character (the last characters of the context, then the character itself) that occurs anywhere in the training text. Its median length is 8. The positions split by that length:

Longest match in the training text Positions Loss, model alone (nats) Loss, kNN-LM (nats)
1 to 6 characters 685 2.512 2.477
7 to 9 825 1.901 1.668
10 to 12 365 1.682 1.447
13 or more 153 1.368 1.037

(The kNN-LM uses $k = 1{,}024$, $T = 1$ and each seed's best weight.) Where the training text contains at most six characters ending at the true next character, the neighbors gained 0.035 nats; where it contains 13 or more, 0.331. That resembles, at the scale of characters, the paper's "near-duplicate sentences from the training set": the gain was largest where the text being predicted continues a string the training text already has. The breakdown is a correlation; no $n$-gram model was run here, so it does not show that string matching explains the gain, and the paper's own $n$-gram control suggests it would not explain all of it. The speaker names, which head every speech, did not stand out: in the 261 positions inside a speaker's name the loss fell from 2.283 to 2.165 nats, less than the fall from 1.991 to 1.808 at the other positions.

The example in full. At the position of the opening, seed 0, the eight nearest training contexts and their next characters were:

Squared distance Training context (last characters) Next character
0.279 more than any other. / KATHARIN A
8.947 But hear you. / BARNARDIN E
9.140 and it shall be so. / COMIN I
9.178 back'd with France. / HASTIN G
9.333 men are best inclined. / COMIN I
9.437 I'll ha' thee burnt. / PAULIN A
9.491 'Why to me?' / PAULIN A
9.544 What news? what news? / COMIN I

(The slash marks the line break before the speaker's name.) Every neighbor is a speaker's name that ends in IN at the start of a speech; the model's vector has placed the context among such names. The nearest is the same name at distance 0.279, and the next is at 8.947; with $T = 1$ the nearest's weight exceeds the others' by a factor of about $e^{8.7}$, which is why $P_{k\mathrm{NN}}(A) = 0.9993$. With seed 0's best weight, 0.65, the mixture gives A a probability of $0.65 \times 0.9993 + 0.35 \times 0.0091 = 0.6527$, and the loss at this position falls from $-\ln 0.0091 = 4.70$ nats to $-\ln 0.6527 = 0.427$. A second example is the line "To come to Pad", where the model gives the next character u a probability of 0.0063 and the nearest training context, "To see fair Pad", lifts the neighbor distribution's to 0.9890.

What the experiment shows, and what it does not. On a small character-level model trained 30 times, a datastore of the model's own training text lowered validation perplexity at every setting tried, most where the validation text continues strings that the training text contains, and more as the datastore grew. It does not show that the same holds for a well-trained model: this one is weak (perplexity 8.01 against the full model's 4.4), and a weak model leaves more for the neighbors to supply. The kNN-LM's 6.38 remains well above the 4.4 that the walkthrough reports for its full model without any datastore; that figure is for the whole validation text, but the small model's own perplexity differs between the two sets of positions by far less than the gap (7.59 on these positions, 8.01 on all). And the comparison of temperatures and of numbers of neighbors is for these 64-dimensional keys and this text only.

RETRO: retrieval by chunks, read by the network

A kNN-LM retrieves for every token and adds the result to the output probabilities; the network itself never sees the retrieved text. RETRO (Borgeaud et al., 2022) takes the other choices on both counts. It retrieves text once per chunk of tokens, and the network reads the retrieved text through attention.

In outline (Section 2):

  • The input sequence is split into chunks of 64 tokens. The database stores, for each chunk of its text, a key, the BERT embedding of the chunk averaged over its tokens, and a value, the chunk together with its continuation, the next 64 tokens of the same document. BERT is frozen, so all keys can be computed once.
  • For each input chunk, the nearest database chunks by squared Euclidean distance between those embeddings are retrieved with the approximate search library ScaNN (spelled SCaNN in the paper; its anisotropic quantization is described in Vector Search on Disk and with Filters). The paper reports that this queries its 2-trillion-token database in about 10 ms.
  • The retrieved neighbors are encoded by a non-causal Transformer encoder, and the decoder attends to them through chunked cross-attention: tokens of chunk $u$ attend to the neighbors retrieved for chunk $u - 1$. That keeps the model autoregressive. The first chunk is predicted without retrieval.
  • During training, neighbors from the same document as the training sequence are filtered out, so that the model cannot retrieve the text it is asked to predict.

The paper trained models of 172 million to 7.5 billion parameters, and reports that with a 2-trillion-token database RETRO "obtains comparable performance to GPT-3 and Jurassic-1 on the Pile, despite using 25$\times$ fewer parameters" (Abstract). The authors also measure how much of the gain comes from evaluation text that overlaps the database, and propose an evaluation by degree of overlap (Section 2.6); the gain comes "from both explicit neighbour copying and general knowledge extraction" (Section 1).

The two designs sit at opposite corners of one table. RETRO's own comparison (Table 3) lists the kNN-LM's granularity as the token and its integration as "add to probs", and RETRO's as the chunk and chunked cross-attention. The kNN-LM needs no training and works with any model that exposes a vector; it pays a search per token and cannot use retrieved text that the model would have to read. RETRO needs a network trained, or retrofitted, to read neighbors; it pays a search per 64 tokens, and what it retrieves is text that the network can combine. The models that retrieve passages for a question, the RAG models and Fusion-in-Decoder, are closer to RETRO: passages read by the network, retrieved once per question rather than per chunk.

What is proved here, what is cited, and what the experiment shows

Proved on the page. That the kNN-LM's validation loss is convex in the weight $\lambda$, strictly unless the two models agree everywhere (Proposition 1); that a small weight helps exactly when the average ratio of the neighbor probability to the model probability of the true token exceeds 1, and that one position where the neighbors give the true token nothing forces the best weight below 1 (Proposition 2); that the mixed loss is at most the weighted average of the two models' losses (Proposition 3); that the neighbor distribution tends to the nearest neighbor's value as the temperature goes to 0 and to an unweighted vote as it grows (Proposition 4); the arithmetic of the worked problems.

Cited. The kNN-LM's definition, its key choice, its search setup and costs, and all of its results (Khandelwal et al., 2020); RETRO's design and results (Borgeaud et al., 2022); the source of the text (Karpathy, 2015).

Shown by the experiment. On a small character-level GPT of the walkthrough's design, trained 30 times on tiny-shakespeare, with exact search over a datastore of its own training text: the kNN-LM lowered perplexity on 2,028 validation positions from 7.59 to 6.38 with the paper's settings, the best weight was 0.65, more neighbors and a larger datastore helped, a temperature of $1/2$ did slightly better than 1, and the gain was concentrated at positions whose recent characters continue a string found in the training text. These are observations about one small, weak model and one text.

Worked problems

These problems are posed on small exact cases and on the experiment's datastore; the unit has no course assignments. The script recomputes every number.

Problem 1 (a neighbor distribution by hand). A context has four neighbors at squared distances 1, 1.5, 2 and 4, whose values are e, e, a and e. The language model gives e probability 0.3 and a probability 0.05. Compute $P_{k\mathrm{NN}}$ with $T = 1$ and the kNN-LM's probabilities at $\lambda = 0.25$, and the loss of each model if the next character is e, and if it is a.

The weights are $e^{-1} = 0.3679$, $e^{-1.5} = 0.2231$, $e^{-2} = 0.1353$ and $e^{-4} = 0.0183$, with sum 0.7447. The three neighbors with value e carry $0.3679 + 0.2231 + 0.0183$, so $P_{k\mathrm{NN}}(e) = 0.8183$ and $P_{k\mathrm{NN}}(a) = 0.1353/0.7447 = 0.1817$; every other character gets 0. Mixed: $P(e) = 0.25 \times 0.8183 + 0.75 \times 0.3 = 0.4296$ and $P(a) = 0.25 \times 0.1817 + 0.75 \times 0.05 = 0.0829$. If the next character is e, the loss falls from $-\ln 0.3 = 1.204$ nats to $-\ln 0.4296 = 0.845$; if it is a, from $-\ln 0.05 = 2.996$ to $-\ln 0.0829 = 2.490$. The neighbors raise both, because both are among their values; a character outside them would lose a quarter of its probability.

Problem 2 (the best weight, exactly). A validation text has two positions. At the first the neighbors give the true character probability $a_1 = 0.9$ and the model $b_1 = 0.3$; at the second $a_2 = 0$ and $b_2 = 0.5$. Should the two be mixed, and with what weight?

By Proposition 2, $\mathcal{L}'(0) = 1 - \frac12(0.9/0.3 + 0/0.5) = 1 - 1.5 = -0.5 < 0$, so a positive weight helps, and since $a_2 = 0$ the best weight is below 1. Setting the slope to zero, $\frac{0.6}{0.3 + 0.6\lambda} = \frac{0.5}{0.5 - 0.5\lambda}$, so $0.6(0.5 - 0.5\lambda) = 0.5(0.3 + 0.6\lambda)$, that is $0.3 - 0.3\lambda = 0.15 + 0.3\lambda$, and $\lambda = 1/4$. By Proposition 1 this is the minimum. The loss there is $-\frac12(\ln 0.45 + \ln 0.375) = 0.8897$ nats, a perplexity of 2.434, against 0.9486 and 2.582 for the model alone. The neighbors are useless at the second position, where they give 0, and still worth a quarter of the weight because of the first.

Problem 3 (the size of a datastore). How large is the experiment's datastore with full-precision keys, and what does an exact search cost? Compare WikiText-103.

The training text has 1,003,854 characters, so 1,003,853 positions have a next character. Keys of 64 numbers of 4 bytes take $1{,}003{,}853 \times 64 \times 4 = 257.0$ million bytes, about 257 MB, plus one byte per value. An exact search costs $1{,}003{,}853 \times 64 = 64.2$ million multiply-adds per predicted character, and $7.166$ trillion for all 111,539 positions of the validation text. WikiText-103's 103 million tokens with 1,024-dimensional keys would take $421.9$ GB at full precision, and $6.592$ GB at the paper's 64 bytes per key.

Problem 4 (the temperature). For the neighbors of Problem 1, find $P_{k\mathrm{NN}}(e)$ as $T \to 0$, as $T \to \infty$, at $T = 4$ and at $T = 0.5$.

By Proposition 4, as $T \to 0$ all mass goes to the nearest neighbor, at distance 1, whose value is e: $P_{k\mathrm{NN}}(e) \to 1$. As $T \to \infty$ the weights become equal and $P_{k\mathrm{NN}}(e) \to 3/4$. At $T = 4$ the weights are $e^{-0.25}, e^{-0.375}, e^{-0.5}, e^{-1}$, summing to 2.4405, and $P_{k\mathrm{NN}}(e) = 0.7515$; at $T = 0.5$, $P_{k\mathrm{NN}}(e) = 0.9101$. The values fall between the two limits, closer to the vote when $T$ is large against the distances and closer to the nearest neighbor when it is small; $T = 1$ gave 0.8183.

What we have learned

A language model's own context vectors can serve as the keys of a retrieval index over text, one entry per token, and the next tokens of the nearest stored contexts form a distribution that can be mixed with the model's. Nothing is trained; the datastore can hold the training text or any other. The mixed loss is convex in the weight, so tuning it is safe, and an exact test says when the neighbors help at all: when, on average, they make the true token more likely by a ratio above 1. Khandelwal et al. found that this lowered the perplexity of a large Transformer on WikiText-103 from 18.65 to 16.12, that retrieving from 3 billion tokens beat training on them, and that a datastore of another domain adapted a model to it. On the site's small GPT the same construction lowered perplexity from 7.59 to 6.38, mostly where the text repeats strings of the training text. RETRO takes the opposite choices, retrieving chunks rather than tokens and reading them with attention rather than mixing probabilities.

Both designs retrieve by similarity to what has just been read. The articles that follow retrieve passages for a question and hand them to the model as text: how many passages, in what order and within what budget is the subject of Assembling the Context, and what the unit of retrieval itself should be is the subject of Passages and Chunking.

References

  • Borgeaud, S., Mensch, A., Hoffmann, J., Cai, T., Rutherford, E., Millican, K., van den Driessche, G., Lespiau, J.-B., Damoc, B., Clark, A., et al. (2022). Improving language models by retrieving from trillions of tokens. In Proceedings of the 39th International Conference on Machine Learning, PMLR 162, 2206–2240. arXiv:2112.04426. record
  • Karpathy, A. (2015). char-rnn [Software repository]. https://github.com/karpathy/char-rnn record · 2 pages
  • Khandelwal, U., Levy, O., Jurafsky, D., Zettlemoyer, L., and Lewis, M. (2020). Generalization through memorization: Nearest neighbor language models. In Proceedings of ICLR 2020. arXiv:1911.00172. record