Fusion-in-Decoder and Reading Many Passages

The Fusion-in-Decoder reader of Izacard and Grave, which encodes each retrieved passage separately with the question and lets the decoder attend to all of them at once, and what it costs to read many passages. The cost of the encoder is derived for separate and concatenated passages, with their difference proved to be 2ℓk(k−1)L²m multiply-adds and evaluated for T5-Base and T5-Large; the decoder's share is derived and compared with a measured split; the operational intensity of cross-attention is shown to be about one multiply-add per number read, which is why decoding is slow; and the reader is proved to ignore the order of its passages while giving a duplicated passage twice the attention mass. The reported scaling with the number of passages, the distillation of the reader's attention into the retriever, and Atlas are given in outline from their papers. Five worked problems cover the cost by hand, the order and duplicates, the memory read per decoding step, the value of the reader's own selection, and a distillation target.

Izacard and Grave (2021a) trained a reader to answer the questions of Natural Questions and TriviaQA from passages that a dense retriever found, and varied how many passages it read. With 10 passages it did well; with 100 it did better, and the paper reports the gain from 10 to 100 as a "6% improvement on TriviaQA and 3.5% improvement on NaturalQuestions" in exact match (§4, Figure 3). By their account, "the performance of most extractive models seems to peak around 10 to 20 passages", and the BERTserini reader of Open-Domain Question Answering shows the same plateau. The new reader read 100 passages of about 100 words each, up to 25,000 word pieces in all once each input is cut to 250. How can a reader use that many passages at once, and what does it cost to do so?

Fusion-in-Decoder (FiD) is an encoder-decoder transformer that reads each retrieved passage separately, together with the question, in its encoder, and combines them only in its decoder, which attends to the encodings of all the passages at once while it writes the answer (Izacard and Grave, 2021a, §3). Its name says where the evidence is fused. The two models of The RAG Models combine passages later still: each passage produces its own prediction, and the predictions are averaged. A third design puts all the passages into one long input. Most of this article is about the difference between these three.

Here is the route. First we recall the encoder-decoder transformer and its cross-attention, the one mechanism through which FiD's passages meet. Then we set out the three ways of reading $k$ passages and prove two properties of FiD: it ignores the order of its passages, and it counts a duplicated passage twice. Next we count the multiply-adds of each design, the decoder's share and the memory each decoding step must read, which explains a measured surprise about where FiD's time goes. Then we report how accuracy grows with the number of passages. Finally we follow two lines that grew from FiD: using the reader's attention to train the retriever, and Atlas, which trains both together. The article assumes the transformer block of Assembling the Transformer Block and the cost of one block derived in Cross-Encoder Re-ranking. The numbers are computed by tools/experiments/rag/fusion-in-decoder.py, in integer arithmetic.

The encoder-decoder transformer

The GPT built in Language Models from Scratch is a decoder alone: one stack of blocks, each position attending only to earlier positions. The original transformer, and the T5 models on which FiD is built, have two stacks (Raffel et al., 2020, §2.1). The encoder reads the whole input with unmasked self-attention, so each input position can attend to every other. The decoder generates the output one token at a time; each of its blocks has a masked self-attention over the output so far, followed by "a standard attention mechanism ... that attends to the output of the encoder", and a feed-forward layer.

That middle layer is cross-attention. Let the encoder's output be a matrix $H$ with one row $\vec{h}_r \in \mathbb{R}^m$ per input position $r$, and let $\vec{u}$ be the decoder's state at the current position. In one head, cross-attention projects $\vec{u}$ to a query $\vec{u}W_Q$, every $\vec{h}_r$ to a key $\vec{h}_r W_K$ and a value $\vec{h}_r W_V$, and returns $$\operatorname{CA}(\vec{u}, H) = \sum_{r} \frac{\exp\!\big(\vec{u} W_Q \cdot \vec{h}_r W_K\big)}{\sum_{r'} \exp\!\big(\vec{u} W_Q \cdot \vec{h}_{r'} W_K\big)}\; \vec{h}_r W_V ,$$ followed by an output projection. It is the attention of Building Self-Attention with the queries taken from one sequence and the keys and values from another. The decoder learns what it needs from the input only through this sum.

T5 replaces absolute position embeddings by relative ones: a scalar that depends on the offset between query and key is added to each attention logit "in the self-attention mechanism", and because "self-attention is order-independent (i.e. it is an operation on sets)" this is the model's only signal of order (§2.1). As T5 describes it, the position term belongs to self-attention, where both positions lie in one sequence; we take it, as that description implies, that cross-attention has none. The sizes we use are T5's: the Base model has 12 blocks in each stack, width $m = 768$, feed-forward width $m_{\mathrm{ff}} = 3{,}072$ and 12 heads, about 220 million parameters (§3.1.1); the Large model has 24 blocks in each, $m = 1{,}024$, $m_{\mathrm{ff}} = 4{,}096$ and 16 heads, about 770 million (§3.7).

Three ways to read $k$ passages

A reader is given a question $q$ and $k$ retrieved passages $p_1, \dots, p_k$.

  1. One at a time, predictions combined. Each passage is read with the question on its own, and the predictions are combined afterward. DrQA compares span scores across paragraphs; RAG-Sequence averages whole-output probabilities with the retriever's weights; RAG-Token averages next-token probabilities. No part of the model ever sees two passages together.
  2. Concatenated. The question and all $k$ passages are joined into one input of about $kL$ tokens, for passages of $L$ tokens. Every token can attend to every other token of every passage, in every layer.
  3. Fusion-in-Decoder. Each passage, with the question, is encoded separately. FiD forms the input question: ... title: ... context: ... for each passage, encodes the $k$ inputs independently, concatenates the $k$ encoder outputs into one matrix of $kL$ rows, and lets the decoder cross-attend to all of them (Izacard and Grave, 2021a, §3).

In symbols, FiD computes $$H_j = \operatorname{Enc}\big(q \oplus p_j\big) \in \mathbb{R}^{L \times m}, \quad j = 1, \dots, k, \qquad H = \begin{bmatrix} H_1 \\ \vdots \\ H_k \end{bmatrix} \in \mathbb{R}^{kL \times m},$$ where $\oplus$ joins the question to the passage, and generates the answer with a decoder whose cross-attention reads $H$. The authors' reason for the design is in one sentence: "Processing passages independently in the encoder allows to scale to large number of contexts, as it only performs self attention over one context at a time", while "processing passages jointly in the decoder allows to better aggregate evidence from multiple passages" (§3).

Two consequences follow directly from the form, and both can be proved.

Proposition 1 (FiD ignores the order of its passages). Assume, as T5's description implies, that cross-attention carries no position term. Then FiD's probability for every output is unchanged by any reordering of its $k$ passages.

Proof. Each $H_j$ depends only on $q$ and $p_j$, since the encoder reads that one input and nothing else; reordering the passages reorders the blocks of $H$ and changes no block. In the decoder, the self-attention and feed-forward layers see only the decoder's own states. The cross-attention output for a state $\vec{u}$ is a sum over the rows of $H$ of a weight times a value, divided by a sum over the rows of $H$ of the same exponentials; each row's term depends on that row and $\vec{u}$ alone. Reordering the blocks permutes the rows, and a sum does not depend on the order of its terms, so every cross-attention output is unchanged. By induction over the decoder's blocks and its output positions, every decoder state is unchanged, and so is every output probability. $\blacksquare$

FiD therefore cannot see the retriever's ranking. The passages arrive in ranked order, but the decoder sees a set; only their content can make one passage count for more than another. A concatenated input, by contrast, puts passages at different offsets from one another, and T5's relative position term in self-attention can make its output depend on their order. Whether and how much a concatenating reader's accuracy depends on where a passage stands is the subject of Assembling the Context.

Proposition 2 (FiD counts a duplicate twice). If one passage appears twice among the $k$, then for any given decoder state its share of the cross-attention sum in every head is larger than if it appeared once, and each head's output moves toward that passage's values.

Proof. Fix the decoder state $\vec u$ and one head. Let $A_j = \sum_{r \in \text{block } j} \exp(\vec{u}W_Q \cdot \vec{h}_r W_K)$ be block $j$'s attention mass, $A = \sum_j A_j$, and $\bar v_1$ block 1's attention-weighted mean value, $\sum_{r \in \text{block } 1} \exp(\vec{u}W_Q \cdot \vec{h}_r W_K)\, \vec h_r W_V / A_1$. With block 1 once, its share of the mass is $A_1/A$ and the output is $\mathrm{CA}_{\text{old}}$. A second copy has rows identical to block 1's (same input, same encoder), so it adds mass $A_1$ and the same values, and the new output is $$\mathrm{CA}_{\text{new}} = \frac{A\, \mathrm{CA}_{\text{old}} + A_1 \bar v_1}{A + A_1} = \frac{A}{A + A_1}\,\mathrm{CA}_{\text{old}} + \frac{A_1}{A + A_1}\,\bar v_1,$$ a point on the segment from the old output toward $\bar v_1$. Block 1's share becomes $2A_1/(A + A_1)$, which exceeds $A_1/A$ whenever $0 < A_1 < A$, since $2A > A + A_1$. $\blacksquare$

The proposition is about one decoder state. After the first cross-attention the two runs' states differ, so it does not say by how much the final output changes, only that the duplicate's attention mass doubles at whatever state the decoder is in.

So FiD reads a multiset, not a set: Proposition 1 says order does not matter, Proposition 2 that multiplicity does. A retriever that returns near-copies of one passage gives that content extra weight in the reader, the effect that Result Diversification works to avoid. The script checks both propositions numerically on a small random cross-attention (seed 20261118): reordering three blocks changes the output by less than $10^{-12}$, while adding a copy of one block moves it by 0.098.

Example (FiD is not the same as concatenation with a mask). "FiD is concatenation with some attention links removed, so it can only be worse." It is concatenation with the links between passages in the encoder removed, which costs expressiveness in the encoder: a word of passage 3 cannot be read in the light of passage 7 until the decoder. But removing them is what makes 100 passages affordable, and the measured result is that the decoder's fusion was enough for FiD-Large to have the best exact match of every system in FiD's Table 1, and FiD-Base the best on Natural Questions and TriviaQA (on SQuAD Open, Path Retriever's 56.5 exact match and 63.8 F1 are above FiD-Base's 53.4 and 60.6). Which of the two designs is more accurate at equal cost is an empirical question, and the papers cited here do not run the concatenating design at 100 passages.

What reading $k$ passages costs

Here is the idea in one sentence: in the encoder, self-attention costs grow with the square of the input's length, so cutting one long input into $k$ short ones divides the attention cost by $k$ and leaves the rest unchanged.

The encoder. Cross-Encoder Re-ranking counts the multiply-adds of one encoder block on $n$ positions: $4nm^2$ for the four projections, $n^2 m$ for the attention scores and $n^2 m$ for the weighted sums of values, and $2 n m\, m_{\mathrm{ff}}$ for the feed-forward layers. With $m_{\mathrm{ff}} = 4m$, as in both T5 sizes, a block costs $12 n m^2 + 2 n^2 m$. (Softmax, normalization and activations add terms linear in $n$, not counted.)

FiD runs the encoder on $k$ inputs of $L$ positions, and the concatenating reader on one input of $kL$ positions. For an encoder of $\ell$ blocks:

$$C_{\text{FiD}} = \ell\, k\, (12 L m^2 + 2 L^2 m), \qquad C_{\text{concat}} = \ell\, (12 kL\, m^2 + 2 k^2 L^2 m).$$

Proposition 3 (the saving). $C_{\text{concat}} - C_{\text{FiD}} = 2\,\ell\, k(k - 1)\, L^2 m$. The projections and feed-forward layers cost the same in both; FiD saves only attention, and its attention cost is $1/k$ of the concatenated one.

Proof. The terms in $m^2$ are $12 \ell k L m^2$ in both. The attention terms are $2\ell k L^2 m$ and $2 \ell k^2 L^2 m$; their difference is $2\ell L^2 m (k^2 - k)$ and their ratio is $k$. $\blacksquare$

At T5-Base sizes and $L = 250$ word pieces (the paper truncates the retrieved passages to 250 word pieces, §4, and we take 250 as the length of each encoder input), one encoder block on one input costs $12 \cdot 250 \cdot 768^2 + 2 \cdot 250^2 \cdot 768 = 1{,}865{,}472{,}000$ multiply-adds, of which attention is 5.1%. For the whole 12-block encoder:

Passages $k$ FiD encoder Concatenated encoder Ratio
1 0.02 × 10¹² 0.02 × 10¹² 1.00
10 0.22 × 10¹² 0.33 × 10¹² 1.46
25 0.56 × 10¹² 1.25 × 10¹² 2.24
50 1.12 × 10¹² 3.94 × 10¹² 3.52
100 2.24 × 10¹² 13.64 × 10¹² 6.09

FiD's cost grows linearly in $k$, as the paper says: "the computation time of the model grows linearly with the number of passages, instead of quadratically" (§3). The concatenated cost grows linearly while the $m^2$ terms dominate and quadratically after; at $k = 100$, attention is 84.4% of the concatenated encoder's cost. For T5-Large, with 24 blocks of width 1,024, the encoders at $k = 100$ cost $7.86 \times 10^{12}$ and $38.27 \times 10^{12}$, a ratio of 4.87; the ratio is smaller because the wider model spends more on its $m^2$ terms.

Memory grows the same way. Each head of each block forms an attention matrix with one entry per pair of positions: $k L^2 = 6{,}250{,}000$ entries at $k = 100$ for FiD, $(kL)^2 = 625{,}000{,}000$ for the concatenated input. A 25,000-token input is also far beyond the sequences of at most 512 tokens on which T5 was pre-trained (Raffel et al., 2020, §3.1.2 and §3.7), whereas each of FiD's inputs is within that length.

The decoder. Here both designs pay the same, because both decoders cross-attend to all $n = kL$ encoder outputs. Per decoder block, the keys and values of the $n$ encoder outputs are projected once per input, $2 n m^2$ multiply-adds. Then each of the $T$ output steps pays $4m^2$ for its self-attention projections, $2tm$ for self-attention over the $t$ positions generated so far, $2m^2$ for the cross-attention's query and output projections, $2nm$ for the cross-attention scores and weighted sums, and $2m\,m_{\mathrm{ff}} = 8m^2$ for the feed-forward layers. For a short answer the first term dominates. At T5-Base sizes, $k = 100$ and $T = 10$ output tokens, the 12-block decoder costs $0.359 \times 10^{12}$ multiply-adds, of which the key and value projections are $0.354 \times 10^{12}$, or 98.4%.

The decoder is then 13.8% of the total, about one sixth of the encoder (0.161 of it): the leading terms are $2nm^2$ per decoder block against $12nm^2$ per encoder block. De Jong et al. (2023, §2.2) make the same approximation, and their Figure 1, for a FiD model reading 40 passages, gives 86% of the floating-point operations to the encoder and 14% to the decoder. Their setting is "40 passages of 256 tokens and output size of 32 tokens" (§5); with those values and T5-Base sizes our formulas give the encoder $9.18 \times 10^{11}$ and the decoder $1.54 \times 10^{11}$ multiply-adds, a decoder share of 14.4% (the figure does not give the model size; at T5-Large sizes the share is also 14.4%). At this article's setting of 250 tokens and 10 output tokens, 40 passages give 13.9%.

Why the decoder is slow anyway

De Jong et al. (2023) measured something the operation counts do not predict. In the same Figure 1, the decoder took 87% of the inference time, and the encoder 13%. They explain it with the roofline model: a processor can compute far faster than it can fetch numbers from memory, so an operation that performs few multiply-adds per number fetched runs at the speed of memory, not of arithmetic (§2.3).

Proposition 4 (operational intensity at one decoding step). At one decoding step, the cross-attention of one block for one example performs $2nm$ multiply-adds and must read the $2nm$ numbers of that example's keys and values: about one multiply-add per number read, whatever the batch size. A feed-forward layer applied to a batch of $B$ examples performs $2 m\, m_{\mathrm{ff}} B$ multiply-adds and reads its $2 m\, m_{\mathrm{ff}}$ weights once for the whole batch: about $B$ multiply-adds per number read.

Proof. The scores are $n$ dot products of length $m$ between the step's query and the stored keys, $nm$ multiply-adds, and the weighted sum of $n$ values of length $m$ is another $nm$; every key and every value is used exactly once. The keys and values belong to this example's own passages, so no other example of the batch can reuse them. The feed-forward weights are the same for all examples: each weight read is used once per example in the batch, $B$ times in all, plus a number of activation reads proportional to $(m + m_{\mathrm{ff}})B$, which is small beside $2 m\, m_{\mathrm{ff}}$ for moderate $B$. $\blacksquare$

During training, and in the encoder, every position is processed in one pass, so each number fetched is used many times. During generation the decoder runs one step at a time, and at every step each block's cross-attention must fetch all of its $2nm$ keys and values to do one multiply-add with each. At $k = 100$ and 16-bit numbers that is 76.8 MB per block and 921.6 MB for the 12 blocks of T5-Base, per example and per output token. De Jong et al. remove most of it by keeping cross-attention in only some decoder blocks (layer-sparse cross-attention) and by sharing one key and value head across all query heads (multi-query attention), and report decoder inference "orders of magnitude faster" and FiD as a whole about 7 times faster, which let them make the decoder much larger at modest cost (abstract, §1).

How accuracy grows with the number of passages

All numbers in this section are the papers'.

The setting. Izacard and Grave (2021a, §4) used the open versions of Natural Questions, TriviaQA and SQuAD described in Open-Domain Question Answering, over Wikipedia cut into non-overlapping 100-word passages. Passages were retrieved with DPR for Natural Questions and TriviaQA and with BM25 for SQuAD, following DPR's own finding that BM25 retrieved better for SQuAD. The readers were T5-Base and T5-Large, fine-tuned for 10,000 steps with a batch of 64 on 64 GPUs, reading 100 passages in training and at test time, and answering by greedy decoding.

The main results (Table 1, exact match on the test sets; TriviaQA on the open-domain test set and on the hidden test set):

Model NQ TriviaQA TriviaQA hidden SQuAD Open EM / F1
DPR 41.5 57.9 – 36.7 / –
RAG 44.5 56.1 68.0 –
T5, closed book 36.6 – 60.5 –
FiD, T5-Base 48.2 65.0 77.1 53.4 / 60.6
FiD, T5-Large 51.4 67.6 80.1 56.7 / 63.2

(FiD's table lists RAG's TriviaQA score as 56.1; the RAG paper's own Table 1 gives 56.8 for RAG-Sequence.) The paper also compares sizes: "the closed book T5 model obtains 36.6% accuracy with 11B parameters, while our approach obtains 44.1% with 770M parameters plus Wikipedia with BM25 retrieval" (§4).

How close is FiD-Large to its retriever's ceiling? FiD is generative, so the extractive bound of Open-Domain Question Answering does not bind it, but the ratio is still informative. DPR's published retrievers put an answer-bearing passage in the top 100 for 85.4% or 86.0% of Natural Questions test questions (Karpukhin et al., 2020, Table 2, single and multi-dataset training). Against either, FiD-Large's 51.4 is a ratio of about 0.60 (0.602 and 0.598), above the 0.49 to 0.53 bracket that the same article computes for DPR's own extractive reader.

More passages at test time. Figure 3 plots exact match on the development sets against the number of passages, from 5 to 100, for FiD-Base. It rises throughout, and "increasing the number of passages from 10 to 100 leads to 6% improvement on TriviaQA and 3.5% improvement on NaturalQuestions" (§4). The authors' interpretation: "this is evidence that sequence-to-sequence models are good at combining informations from multiple passages". The containment curves of the previous article suggest part of the reason, since more passages contain the answer more often; the extractive readers had the same rising containment and did not keep improving.

Training with fewer passages. Training on 100 passages is expensive, so the authors trained with fewer and tested with 100 (Table 2, development sets):

Training passages NQ NQ, then 1,000 steps on 100 TriviaQA TriviaQA, then 1,000 steps on 100
5 37.8 45.0 58.1 64.2
10 42.3 45.3 61.1 63.6
25 45.3 46.0 63.2 64.2
50 45.7 46.0 64.2 64.3
100 46.5 – 64.7 –

A reader trained on 5 passages and tested on 100 scores 37.8 on Natural Questions, 8.7 points below the reader trained on 100. A short fine-tuning on 100 passages recovers most of the gap (45.0), and from 25 or 50 training passages almost all of it: 46.0 against 46.5, "using 147 GPU hours, compared to 425 GPU hours when training on 100 passages" (§4), about 0.35 of the cost.

The reader as a teacher of the retriever

FiD's decoder decides, at every step, how much attention to give each passage. Izacard and Grave (2021b) asked whether those weights could serve as relevance labels for training the retriever, which would remove the need for question-passage pairs.

The signal. For question $q$ and each of its passages $p$, they average the decoder's cross-attention scores "over all the tokens in the input" belonging to $p$, "all the layers and all the heads of the decoder", to obtain one score $\alpha_{q,p}$ (§3.2). A first test supports the idea. Reading DPR's top 100 passages gave 48.2 exact match on Natural Questions; reading DPR's top 10 gave 42.9; reading the 10 of the 100 with the highest attention scores gave 46.8 (§3.2).

The training. The retriever is a bi-encoder whose score $s(q, p)$ is a scaled dot product of BERT embeddings. Both sets of scores are turned into distributions over a question's passages with a softmax, giving the reader's target $\tilde\alpha_{q,p}$ and the retriever's $\tilde P(p \mid q)$, and the retriever is trained to minimize the Kullback-Leibler divergence $\sum_p \tilde\alpha_{q,p} \big(\ln \tilde\alpha_{q,p} - \ln \tilde P(p \mid q)\big)$ of Cross-Entropy and Kullback–Leibler Divergence (§3.4). The steps repeat: train the reader on the current passages, compute its attention scores, train the retriever on them, retrieve new passages (§3.5).

Proposition 5 (the distillation gradient). For a target distribution $g$ over the retrieved passages and a retriever distribution $\pi_j = e^{s_j}/\sum_i e^{s_i}$ over the same passages, $$\frac{\partial}{\partial s_j} \sum_i g_i \big(\ln g_i - \ln \pi_i\big) = \pi_j - g_j .$$

Proof. Only $-\sum_i g_i \ln \pi_i$ depends on the scores, and $\ln \pi_i = s_i - \ln \sum_l e^{s_l}$. Its derivative with respect to $s_j$ is $-\big(g_j - \sum_i g_i \pi_j\big) = \pi_j - g_j$, since $\sum_i g_i = 1$. $\blacksquare$

Gradient descent therefore moves each score in proportion to target minus current probability, the same form as the "posterior minus prior" that The RAG Models derives for the retriever of RAG. The difference is the target: RAG's posterior is the retriever's own prior reweighted by how well each passage explains the answer, whereas distillation takes the reader's attention as the target outright.

The results. Starting from BM25's passages on Natural Questions, the first iteration raised top-20 accuracy from 59.3 to 76.4 and exact match from 41.2 to 46.8; the second reached 80.4 and 47.9; a third did not help (46.2) (Table 1, development set). Starting from DPR's passages and reading with T5-Large, the method reached 54.4 exact match on the Natural Questions test set and 72.5 on TriviaQA (Table 2).

Atlas in outline

Atlas (Izacard et al., 2023) joins the pieces of this unit into one system and asks whether a retrieval-augmented model can learn new tasks from few examples. Its retriever is Contriever, a bi-encoder trained without labels, with average pooling and a dot product; its reader is a T5 model in the FiD arrangement, "since the self-attention in the encoder results in a quadratic complexity with respect to the number of documents" when passages are concatenated instead (§2.1). The two are pre-trained together and then fine-tuned.

The paper compares four losses for training the retriever from the reader (§2.2). Attention distillation is the method of the previous section. EMDR², an earlier method inspired by expectation-maximization, treats the passages as latent variables in the manner of the RAG models. Perplexity distillation trains the retriever toward the distribution that the reader's likelihoods give the passages under a uniform prior, $$g_j = \frac{P_{\mathrm{LM}}(a \mid p_j, q)}{\sum_{i=1}^{k} P_{\mathrm{LM}}(a \mid p_i, q)}, \qquad j = 1, \dots, k,$$ with $a$ the output and $p_j$ the $j$-th of the $k$ retrieved passages (the paper writes documents $d_k$ and $K$ of them), by minimizing the same divergence as above. Leave-one-out perplexity distillation scores each document by how much worse the reader does without it. Jointly training the retriever gave "strong improvements" on the pre-training (masked language modeling) metric, an effect "less marked on 64-shot downstream tasks, and almost non-existent for 1024-shot"; the paper did "not observe significant systematic differences between the different retriever training objectives", and adopted perplexity distillation, as more stable than two of them and cheaper than the fourth (§4.3).

Because the retriever's passage encoder is trained, the index of passage vectors goes stale, as REALM's did. Atlas compares re-encoding the whole index, re-ranking a larger retrieved set with the current encoder, and training only the query encoder (§2.4); for few-shot fine-tuning it trains only the query side (§4.4).

The results that matter here (Table 8, exact match on Natural Questions): trained on 64 examples, the 11-billion-parameter Atlas reached 42.4, 2.8 points above the 39.6 of the 540-billion-parameter PaLM prompted with 64 examples; trained on the full training set it reached 60.4, against 51.4 for FiD and 54.7 listed for FiD with distilled retrieval. (Izacard and Grave's own paper reports 54.4 for that model; Atlas's table does not say where its figure comes from.) With an index of the December 2018 Wikipedia dump only, Atlas-11B reached 64.0 on the full set (Table 19).

The non-parametric memory of Atlas is large: its Wikipedia index holds 37 million passages and its combined index adds 350 million passages from Common Crawl (§4.2). Stored at 16-bit precision, the embeddings need 49 GB of accelerator memory for Wikipedia and 587 GB for the combined index. The paper does not give the arithmetic: 37 million 768-dimensional vectors at 2 bytes would take 56.8 GB, so the index measured may differ from the passage count of §4.2. With product quantization the paper compressed them to 4 GB and 50 GB, about 12.3 and 11.7 times smaller, "with negligible drop in retrieval precision and exact match" for the Wikipedia index and "without serious degradation" for the combined one (§5.2.1, Figure 4).

What is proved, what is cited, what the script computes

Proved here. That FiD's output does not depend on the order of its passages, under the stated assumption about T5's position terms (Proposition 1); that a duplicated passage gets a larger share of the cross-attention sum at any given decoder state, and moves its output toward that passage's values (Proposition 2); the encoder costs of FiD and concatenation and their difference $2\ell k(k-1)L^2 m$, with attention reduced by the factor $k$ and nothing else changed (Proposition 3); the decoder's cost; the operational intensity of cross-attention at a decoding step, about one multiply-add per number read, against $B$ for a feed-forward layer (Proposition 4); and the gradient of the distillation loss, target minus retriever probability with the sign reversed (Proposition 5).

Cited. The architecture, training and every result of FiD (Izacard and Grave, 2021a), of reader-to-retriever distillation (Izacard and Grave, 2021b), of FiDO's measurements (de Jong et al., 2023), of Atlas (Izacard et al., 2023), T5's shapes and position scheme (Raffel et al., 2020), and DPR's top-100 accuracy (Karpukhin et al., 2020), each with its table, figure or section.

Computed by the script. Every cost in the tables and the text, from the formulas proved here and T5's published shapes; the numerical check of Propositions 1 and 2 on a small random cross-attention; and the arithmetic on published results. The costs count multiply-adds of the matrix products only, which is the convention of the cross-encoder article and of de Jong et al.; times on real hardware also depend on memory traffic, as Proposition 4 shows.

Worked problems

The unit has no course assignments; these problems use T5's published shapes, FiD's settings and published results, and the script recomputes each number.

Problem 1 (the encoder by hand). At T5-Base sizes and $L = 250$, how many multiply-adds does FiD's encoder spend on 10 passages, and how many does a concatenating encoder spend on the same 2,500 tokens? How much of the difference is attention?

One block on one input: $12 \cdot 250 \cdot 768^2 = 1{,}769{,}472{,}000$ for the projections and feed-forward layers, plus $2 \cdot 250^2 \cdot 768 = 96{,}000{,}000$ for attention, $1{,}865{,}472{,}000$ in all. FiD: $12 \text{ blocks} \times 10 \times 1{,}865{,}472{,}000 = 0.22 \times 10^{12}$. Concatenated: one block on 2,500 positions is $12 \cdot 2{,}500 \cdot 768^2 + 2 \cdot 2{,}500^2 \cdot 768 = 17{,}694{,}720{,}000 + 9{,}600{,}000{,}000$, and twelve blocks make $0.33 \times 10^{12}$. The difference is all attention, as Proposition 3 says: $2 \cdot 12 \cdot 10 \cdot 9 \cdot 250^2 \cdot 768 = 103{,}680{,}000{,}000$, and indeed $12 \times (9{,}600{,}000{,}000 - 960{,}000{,}000) = 103{,}680{,}000{,}000$. The ratio is 1.46; at 10 passages the saving is real but modest, and it becomes a factor of 6.09 at 100.

Problem 2 (order and duplicates). A retriever returns passages A, B, C to a FiD reader, then on a second run returns C, A, B, and on a third returns A, B, A. Which runs can give different answers?

The first two cannot: by Proposition 1 the reader's output probabilities are the same for any order of the same passages. The third can: it lacks C and holds A twice. Even with C added (A, B, C, A), the output could differ from the first run's, because by Proposition 2 the second copy of A raises A's share of the cross-attention sum at every decoder state. If A is a near-copy rather than an exact copy, the encodings differ slightly and Proposition 2 holds approximately: two passages saying the same thing pull the decoder toward that content about twice as hard. This is one argument for removing near-duplicates before the reader, which a retriever that ranks each passage by its own relevance does not do.

Problem 3 (what a decoding step reads). For T5-Base reading 100 passages of 250 tokens, how many bytes of keys and values must the decoder read at each output step, and how does that compare with the decoder's weights?

The encoder outputs number $n = 25{,}000$. Each block stores keys and values of $n \times m$ numbers each: $2 \times 25{,}000 \times 768 = 38{,}400{,}000$ numbers, 76.8 MB at 2 bytes each, and 921.6 MB for 12 blocks. These are read once per output token, for each example in the batch. The weights of the 12 decoder blocks touched at one step, their projections and feed-forward matrices, are about $12 \times (6 \cdot 768^2 + 2 \cdot 768 \cdot 3{,}072) \times 2 \approx 198$ MB, read once per step for the whole batch. (The output projection to T5's vocabulary of 32,128 word pieces adds about 49 MB.) For a batch of 24 the per-step traffic is about $24 \times 921.6 = 22{,}118$ MB of keys and values against about 248 MB of weights: the passages, not the model, are what the decoder spends its time fetching. That is the bottleneck de Jong et al. measured, and it grows linearly with the number of passages.

Problem 4 (the value of the reader's own choice). In Izacard and Grave's test, cutting from DPR's top 100 passages to its top 10 lowered exact match from 48.2 to 42.9, and cutting to the 10 that the reader attended to most lowered it to 46.8. What share of the loss does the reader's selection avoid, and what does the comparison show about the retriever?

The retriever's selection loses $48.2 - 42.9 = 5.3$ points; the reader's loses $48.2 - 46.8 = 1.4$. The reader's selection avoids $(46.8 - 42.9)/5.3 = 3.9/5.3$, about 74% of the loss. The ten passages the retriever ranked highest are not the ten most useful to the reader, even though both lists come from the same hundred. The reader's attention therefore contains information about relevance that the retriever lacks, which is the premise of distilling it into the retriever.

Problem 5 (a distillation target). Take the running example of The RAG Models: two passages with retriever probabilities $(3/4, 1/4)$ and probabilities of the target output $G_1 = 0.072$ and $G_2 = 0.486$ when the generator reads each (the RAG article's $G_i$). Compute the perplexity-distillation target and the gradient on the score of the second passage, and compare with RAG-Sequence's gradient.

The target normalizes the likelihoods under a uniform prior: $g = (0.072, 0.486)/0.558 = (4/31, 27/31) = (0.129, 0.871)$. By Proposition 5 the gradient of the divergence with respect to $s_2$ is $\pi_2 - g_2 = 0.25 - 0.871 = -0.621$, so gradient descent raises $s_2$ at a rate 0.621. RAG-Sequence's gradient of the log-likelihood is posterior minus prior: the posterior of $p_2$ is $\tfrac14 \cdot 0.486 / 0.1755 = 9/13$, so its gradient is $9/13 - 1/4 = 0.442$, and gradient ascent raises $s_2$ at that rate. Both raise the passage that explains the output, but they aim at different places. Distillation stops when the retriever's distribution equals the normalized likelihoods, $(0.129, 0.871)$; RAG-Sequence's gradient for one example vanishes only when the posterior equals the prior, which with these likelihoods requires all the probability on one passage.

What we have learned

Fusion-in-Decoder reads each passage separately with the question and fuses them in the decoder's cross-attention. The design cuts the encoder's attention cost by the number of passages and leaves everything else unchanged, so the encoder's cost grows linearly with the passages read; at 100 passages a concatenating T5-Base encoder would cost 6.09 times as much. We proved that FiD's output ignores the order of its passages and gives a duplicated passage twice the attention mass. The decoder's arithmetic is about a sixth of the encoder's, but at each output step it must read every passage's keys and values to do one multiply-add with each, which is why decoding dominates its running time. Reported results show accuracy rising with the number of passages up to 100, where extractive readers had stopped improving; in Izacard and Grave's test the reader's attention was a better judge of passages than the retriever, and distilling it into the retriever raised both top-20 accuracy and exact match over two iterations. Atlas, which trains retriever and reader together, found joint training of the retriever helped most on the pre-training metric, less on tasks learned from 64 examples and hardly at all with 1,024.

FiD and RAG retrieve passages and condition a generator on them. The next article, Nearest Neighbor Language Models, retrieves at the other end of the design space: single next tokens, looked up by the context that preceded them.

References

  • de Jong, M., Zemlyanskiy, Y., Ainslie, J., FitzGerald, N., Sanghai, S., Sha, F., and Cohen, W. W. (2023). FiDO: Fusion-in-Decoder optimized for stronger performance and faster inference. In Findings of the Association for Computational Linguistics: ACL 2023, 11534–11547. https://doi.org/10.18653/v1/2023.findings-acl.732. arXiv:2212.08153. record
  • Izacard, G., and Grave, E. (2021a). Leveraging passage retrieval with generative models for open domain question answering. In Proceedings of the 16th Conference of the European Chapter of the Association for Computational Linguistics, 874–880. https://doi.org/10.18653/v1/2021.eacl-main.74. arXiv:2007.01282. record · 2 pages
  • Izacard, G., and Grave, E. (2021b). Distilling knowledge from reader to retriever for question answering. In International Conference on Learning Representations (ICLR 2021). https://openreview.net/forum?id=NTEz-6wysdb. arXiv:2012.04584. record · 2 pages
  • Izacard, G., Lewis, P., Lomeli, M., Hosseini, L., Petroni, F., Schick, T., Dwivedi-Yu, J., Joulin, A., Riedel, S., and Grave, E. (2023). Atlas: Few-shot learning with retrieval augmented language models. Journal of Machine Learning Research, 24(251), 1–43. arXiv:2208.03299. record
  • Karpukhin, V., Oğuz, B., Min, S., Lewis, P., Wu, L., Edunov, S., Chen, D., and Yih, W. (2020). Dense passage retrieval for open-domain question answering. In Proceedings of EMNLP 2020, 6769–6781. https://doi.org/10.18653/v1/2020.emnlp-main.550. arXiv:2004.04906. record · 15 pages
  • Raffel, C., Shazeer, N., Roberts, A., Lee, K., Narang, S., Matena, M., Zhou, Y., Li, W., and Liu, P. J. (2020). Exploring the limits of transfer learning with a unified text-to-text transformer. Journal of Machine Learning Research, 21(140), 1–67. arXiv:1910.10683. record