advanced generation-grounding 31 min read

Retrieval versus Long Context: Attention Complexity and Positional Bias

If the context window is large enough to hold everything, why retrieve at all? Because attention costs (kL)² — quadratic in the tokens read — and because more context is not better: once the answer is in hand, extra passages are redundant at best and same-sector distractors at worst, so answer quality peaks at the smallest covering context and declines as you stuff the window, while a relevant passage buried in the middle is read at attenuated attention — a soft erasure. The right move is not a bigger window but a better-chosen one.

Part of the Generation & Grounding track · View full curriculum →

Prerequisites: The Retrieval Problem: Relevance, Similarity, and the Geometry of Scores

From “how many bits survive the channel” to “how many tokens should we read”

The previous topic read the retriever as a noisy channel and asked what corruption costs: erase the relevant filing and you lose recall × I(A;D|Q) bits; substitute a distractor and the generator answers confidently wrong. It fixed one retrieved document and measured the damage. This topic varies the other knob — how much you read — and asks what reading costs.

The question is sharp because context windows are now large enough to make retrieval look optional. If the window holds an entire filing, why rank passages at all? Why not concatenate everything and let attention sort it out? The answer has two parts, and they are the two halves of this topic’s title. The first is attention complexity: reading is not free, and its price grows as the square of the tokens read. The second is what we will call, with apologies for the inversion of intuition, the fact that more context is not better — and its companion, positional bias, the empirical observation that even the context you do read is read unevenly. We make all three precise on the same finance geometry the earlier topics built, and we read the whole thing as a single rate–distortion choice: spend rate (compute, tokens) to buy down distortion (answer error), and find where the trade turns against you.

We need one object: the answer the generator forms after reading a set of passages, not a single one.

Definition 1 (The top-k context and its answer posterior).

Fix a query $q$ and a corpus of passages with unit-vector embeddings $d_1, d_2, \dots$ . The retriever ranks them by dual-encoder score $s_j = \langle q, d_j\rangle$ ; the top- $k$ context is the set $\mathcal{C}_k$ of the $k$ highest-scoring passages. The generator reads $\mathcal{C}_k$ under a finite attention budget: nonnegative weights $w_j$ over the context that sum to one,

w_j \;=\; \frac{\exp(s_j/\tau_{\text{attn}})}{\sum_{i\in\mathcal{C}_k}\exp(s_i/\tau_{\text{attn}})}, \qquad \sum_{j\in\mathcal{C}_k} w_j = 1,

and forms its belief over the $K$ candidate answers $a$ , with prototype directions $\mu_a$ , by adding the budget-weighted document evidence to the query’s:

p(a \mid q, \mathcal{C}_k) \;=\; \operatorname{softmax}_a\!\left( \frac{\langle q, \mu_a\rangle \;+\; \sum_{j\in\mathcal{C}_k} w_j\,\langle d_j, \mu_a\rangle}{\tau} \right).

This is the natural multi-document generalization of the PMI topic’s additive-logits posterior: at $k=1$ with weight $1$ it is that topic’s answer_posterior, and at $k=2$ with weights $(1,1)$ it is its answer_posterior_two — the notebook pins both equalities to machine precision. The new ingredient is the unit budget: attention is a finite resource the context competes for. We track three quantities as $k$ grows — the answer quality $Q(k) = \mathbb{E}_q\big[\,p(a^\star \mid q, \mathcal{C}_k)\,\big]$ (the posterior mass on the true answer $a^\star$ ), the set recall $\text{recall}_R(k)$ over the relevant passages, and the precision $|\mathcal{C}_k \cap R|/k$ .

Attention is quadratic: the rate axis

The reason long context is not free is structural. Self-attention compares every token to every other token: for a context of $n$ tokens it forms an $n \times n$ matrix of pairwise scores.

Proposition 1 (The cost of reading is quadratic in the tokens read).

Reading a context of $k$ passages of $L$ tokens each means $n = kL$ tokens, and full self-attention over them costs

\text{cost}(k) \;=\; (kL)^2 \;=\; \Theta(k^2)

floating-point operations for the score matrix. Doubling the context quadruples the compute; reading the whole window of $n$ passages costs $n^2$ times what reading one passage does. This is exact arithmetic — the notebook asserts $\text{cost}(2k)/\text{cost}(k) = 4$ — and it is the rate the long-context option pays.

One honest caveat belongs here. FlashAttention computes the same attention with tiling and recomputation so that the memory footprint is $O(n)$ rather than $O(n^2)$ — a real and important result. But it does not change the arithmetic: the number of pairwise scores is still $\Theta((kL)^2)$ . When we say attention is quadratic, we mean in FLOPs, and that is the cost that scales the electricity bill and the latency.

More context is not better

The rate axis alone would already argue for reading less. But the deeper result is that reading more does not even buy better answers — often the opposite. We make this concrete on a corpus built to look like the hard case for the claim: sectors of confusable companies (the dense-retrieval geometry), where each company carries several genuinely relevant passages and a shell of same-sector distractor passages that a retriever can easily confuse for relevant. If “more context helps” were going to hold anywhere, it would hold where there are several relevant passages to gather.

context depth k (passages read) = 4 (1024 tokens)

tokens attended (kL)

1024

cost (kL)²

1.05M

× cost vs k = 1

16×

Full self-attention forms a (kL) × (kL) score matrix, so the arithmetic cost is Θ((kL)²) — doubling the context quadruples the compute. Stuffing the whole window (k = 16) costs 256× what reading the answer (k = 1) does. This is the rate the long-context option pays; FlashAttention lowers the memory to O(n) but leaves these FLOPs unchanged.

Finance vMF corpus extended from the dense-retrieval geometry: 16 companies across 4 sectors, 4 relevant passages each (same-sector cosine ≈ 0.60), 32 queries; the answer model is a synthetic softmax stand-in with a finite attention budget (τ = 0.3, τ_attn = 0.45), not an LLM. Queries identify the company (good retrieval, κ = 60). Diminishing returns (imported): a first filing moves belief 0.411 bits, a genuinely novel one 0.247, but a redundant copy only 0.081. Numbers mirror retrieval_vs_long_context.py; the lab recomputes only the quadratic cost and the positional weight.

It does not hold. Panel B traces the quality curve.

Proposition 2 (Answer quality peaks at the smallest covering context (demonstrated)).

On the model of Definition 1, with the answer reliably retrieved (recall@1 $\approx 1$ ), the answer quality $Q(k)$ is maximized at the smallest context that carries the answer and declines monotonically as $k$ grows. Two mechanisms drive the decline:

Redundancy. While the top- $k$ is all-relevant (precision $\approx 1$ ), the extra passages point the same way as the first. A second filing of the same company moves the answer belief almost not at all — the diminishing-returns result the PMI topic proved and this topic imports verbatim: a redundant filing contributes far less belief-movement (in bits) than the first, and far less than a genuinely novel one. So $Q(k)$ is nearly flat over the relevant set, not rising.
Dilution. Once the relevant set is exhausted, the top- $k$ admits same-sector distractors. Under the unit budget they steal attention weight from the relevant passages and add wrong-company evidence, so precision falls, the budget landing on the answer drops, and the answer entropy $H(A \mid \mathcal{C}_k)$ rises toward the prior. Quality declines.

The notebook asserts the curve is non-increasing, that the peak is at $k^\star = 1$ , that stuffing the window costs a real amount of quality, and that the answer entropy rises in lockstep.

This is a demonstrated proposition, not a theorem: it holds for this attention-budget answer model on this synthetic geometry, and the notebook runs it rather than assuming it. What is robust about it is the mechanism — redundancy plus dilution, both of which we can point to in imported, independently established results — and the fact that it survives across random seeds. What is model-dependent is the exact shape.

Why recall is the wrong target

The two arms of Panel B carry a lesson the evaluation layer cannot see. As $k$ grows, recall climbs — by the time the context covers the whole relevant set, recall is one. And precision falls — past the relevant set, every added passage is a distractor. Answer quality follows precision, not recall: it is highest where precision is highest and the context is purest, and it sinks as recall is “completed” by dragging in distractors.

So the instinct to maximize recall@k by enlarging the context is exactly wrong for generation. You do not need to cover the relevant set; you need the answer, and one good passage supplies it. Chasing the last points of recall buys redundancy and then contamination. The metric the retrieval-evaluation layer optimizes — coverage of the relevant set — is not the quantity the generator wants.

Remark (The interior optimum is a poor-retrieval phenomenon).

There is one regime where reading more genuinely helps before it hurts: when retrieval is bad. If the query is so ambiguous that the gold passage is often not even rank one (recall@1 well below one), then a context of one passage frequently misses the answer, and enlarging $k$ raises quality until the relevant passages are gathered — after which distractors take over and quality falls again. That is a genuine interior optimum $k^\star > 1$ , the classical recall–precision balance. The lab’s faint dashed curve shows it: under hard retrieval the curve is flatter and lower, with a shallow hump. But it is seed-sensitive — on this geometry it appears for some random draws and not others — so we show it as a contrast and do not assert it. The clean, robust statement is the one above: when retrieval works, the optimum is the smallest covering context, and the right amount of context depends on how good your retriever is.

Lost in the middle: positional bias is a soft erasure

So far every passage in the context has been read on equal footing, weighted only by its relevance. Real transformers do not read that way. The empirical lost-in-the-middle effect (Liu et al., 2024) is that a model uses information best when it sits at the start or end of the context and worst when it is buried in the middle — accuracy as a function of the gold passage’s position is U-shaped.

Proposition 3 (A buried passage is a soft erasure).

Model the positional bias as a multiplier $u(\text{pos})$ on each passage’s attention weight — high at the ends, depressed in the middle (Panel D draws it). Then a relevant passage placed at position $\text{pos}$ contributes its evidence scaled by $u(\text{pos})$ : at the center its effective weight is the smallest, so the answer belief sharpens least. A buried relevant passage behaves like a partial erasure — exactly the binary erasure channel of the previous topic, but graded: the surviving fraction of its bits is $u(\text{pos})$ rather than a hard $0$ or $1$ . Answer quality is therefore U-shaped in the gold’s position: worst when buried, best at the edges. The notebook asserts the middle is strictly worse than either end.

The consequence sharpens the case against stuffing. A long context does not merely cost compute and invite distractors; it actively hides the relevant passage it contains, because the relevant passage is now one of many and likely to land in the low-attention middle. The very act of padding the context degrades the signal it was meant to carry.

The rate–distortion frontier: focused retrieval dominates stuffing

Put the two axes together. The rate is the attention compute $\text{cost}(k) = (kL)^2$ ; the distortion is the residual answer error, which we read off as $1 - Q(k)$ or, in bits, the answer entropy $H(A \mid \mathcal{C}_k)$ . Panel C plots quality against cost. The focused-retrieval point sits up and to the left — low cost, high quality — and the stuff-the-window point sits down and to the right. Between them, the curve only descends: every passage past the optimum costs quadratically more and answers no better.

Proposition 4 (Focused retrieval Pareto-dominates context-stuffing (demonstrated)).

On the model, the smallest covering context attains higher answer quality at a fraction of the attention cost than reading the whole window: it is not dominated on either axis, while stuffing is dominated on both. The notebook asserts that stuffing costs strictly more compute and yields no more quality than the optimum.

This is the rate–distortion reading the previous topic promised, now with a price on the rate. It says the right response to a bigger context window is not to fill it but to choose what goes in it — to spend the budget on a small set of passages that are relevant, non-redundant, and few enough to be read at full attention. That choosing problem — selecting a compact, diverse, high-coverage subset — is the next topic, where the redundancy we saw flatten the quality curve becomes a submodular coverage objective with a provable greedy guarantee.

⚠ Rigor flag

Three honesty notes. First, the quadratic cost is an arithmetic (FLOP) claim: FlashAttention makes attention’s memory linear in $n$ without changing the $\Theta((kL)^2)$ compute. Second, the quality curve, the rate–distortion frontier, and the positional dip are exact for a synthetic von Mises–Fisher softmax answer model with a finite attention budget — every number is exact for the model and illustrative of a real generator, the same stand-in the PMI and noisy-channel topics used and the same caveat they carried. Third, lost-in-the-middle is an empirically observed property of trained transformers (Liu et al., 2024); we bake it in as an assumed rank-dependent discount and trace its consequence, we do not derive it. And the interior optimum $k^\star > 1$ is a poor-retrieval, seed-sensitive phenomenon, shown as a contrast and not asserted — the robust claim is the monotone decline under good retrieval.

What retrieval-versus-long-context trades, in one line

A bigger context window does not relax the retrieval problem; it sharpens it. Attention costs $(kL)^2$ , redundant passages add nothing, distractors dilute, and a buried passage is a soft erasure — so answer quality peaks at the smallest context that carries the answer, and the right move is not a larger window but a better-chosen one.

§ How many 10-K passages should the generator read? text pdf

A question about a company’s revenue recognition might be answered by one paragraph of its 10-K. Retrieval returns that paragraph at rank one, plus several more passages from the same filing and a shell of plausible-looking passages from same-sector competitors. The temptation, with a long window, is to pass all of them. The mathematics here says don’t: the first relevant passage already carries the answer; the next few from the same filing are largely redundant; and the same-sector passages — which a retriever scores highly precisely because the companies are comparable — pull the generator toward the wrong company and raise the entropy of its answer, while a buried relevant passage is read at reduced attention. The operating point that minimizes answer error at least cost is a handful of passages, not the whole window — and the discipline of choosing that handful is what the rest of the generation-grounding layer is about.

Connections

the prerequisite framed retrieval as ranking documents by relevance; this topic asks what happens AFTER the ranking — how many of the top-k passages to actually read into the generator — and shows the answer is the smallest context that covers the answer, not the one with the highest recall@k, so a good ranking is necessary but reading all of it is not the-retrieval-problem
the noisy-channel topic spent bits read to buy down answer error and closed on a rate–distortion reading of the recall–precision operating point; this topic puts the quadratic PRICE on those bits — attention cost (kL)² — and shows the rate–distortion optimum is a small focused context, while its lost-in-the-middle pillar is that topic's binary erasure channel applied per rank: a buried passage is a soft erasure retriever-as-noisy-channel
PMI measured the bits a retrieved document adds and proved a redundant second filing adds almost nothing; this topic turns that diminishing-returns curve into the flat left arm of the quality-versus-context curve and imports the very saturation_table that established it, so the redundancy that makes more context useless is the same one PMI quantified in bits pmi-retrieval-value
that topic defined recall@k and precision@k as set-membership estimators; this topic reads them as the two arms of the long-context tradeoff — recall climbs while precision falls as k grows — and shows answer quality tracks precision, not recall, so enlarging the context to raise recall@k degrades the generated answer the metric never sees set-metrics-precision-recall-map-mrr
the dense dual-encoder geometry — sectors of confusable companies at a measured same-sector cosine — is the corpus this topic extends with several relevant passages per company and a same-sector distractor shell, so the dilution that degrades a long context is exactly the same-sector similarity that topic built and the retrieval scores come from its dual_encoder_score dense-retrieval-dual-encoders

References & Further Reading

paper Lost in the Middle: How Language Models Use Long Contexts — Liu, Lin, Hewitt, Paranjape, Bevilacqua, Petroni & Liang (2024) The empirical lost-in-the-middle result: answer accuracy is highest when the relevant passage sits at the start or end of the context and degrades in the middle — the positional-bias pillar's source, modeled here as a rank-dependent discount on the delivered evidence; Transactions of the ACL 12 (2024), preprint arXiv:2307.03172
paper Attention Is All You Need — Vaswani, Shazeer, Parmar, Uszkoreit, Jones, Gomez, Kaiser & Polosukhin (2017) Defines scaled dot-product self-attention, whose pairwise score matrix over n = kL tokens is n×n — the Θ((kL)²) arithmetic cost that is this topic's rate axis; NeurIPS 2017
paper FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness — Dao, Fu, Ermon, Rudra & Ré (2022) The honesty caveat for the rate axis: tiling and recomputation make attention's MEMORY cost O(n) without changing the Θ((kL)²) arithmetic, so 'attention is quadratic' is a FLOP claim, not a memory one; NeurIPS 2022
paper Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks — Lewis, Perez, Piktus, Petroni, Karpukhin, Goyal, Küttler, Lewis, Yih, Rocktäschel, Riedel & Kiela (2020) The retrieve-then-read alternative to context-stuffing whose marginal p(a|q) = Σ_d p(d|q) p(a|q,d) is the answer model the k-sweep generalizes to a finite attention budget over k passages; NeurIPS 2020
book Elements of Information Theory — Cover & Thomas (2006) Rate–distortion theory (Ch. 10) and the mutual-information chain rule behind the diminishing-returns shape of the quality curve; 2nd edition, Wiley
paper A Mathematical Theory of Communication — Shannon (1948) The rate–distortion and entropy framing the cost-versus-quality tradeoff descends from; the answer entropy H(A|context) this topic tracks is Shannon's; Bell System Technical Journal 27 (1948)