Packing the window

Which retrieved chunks fit a token budget, as a knapsack solved greedily and exactly, and where to put them: an illustrative lost-in-the-middle curve and four placements, measured on 200 questions.

Loading the animation…

Concept

Retrieval hands the agent a ranked list; the window takes only so many tokens. Packing decides which chunks go in and in what order. The animation takes one question's 20 reranked candidates (chapter 4), each with a weight (its token count) and a value (the gain nDCG gives its rank, $1/\log_2(i+1)$ : 1 for the top chunk, 0.63 for the second, falling slowly), and fills a budget $B$ three ways:

Top: take chunks in reranked order and skip any that no longer fits. This is what most pipelines do.
Density: the same, but in order of value per token, the textbook greedy approximation to the knapsack. Short, middling chunks jump the queue.
Optimal: dynamic programming over integer budgets finds the set with the most total value. The animation shows it row by row: the best value reachable within $B$ using the first $i$ candidates.

Measured over all 200 questions at $B = 512$ tokens, the answer is in the window for 96.5% of questions with top, 93.5% with density and 94.0% with the optimal packing, even though the optimal set carries the most value (1.955 against 1.920). The knapsack is optimal for the objective it is given, and "sum of rank gains" rewards two mediocre chunks over one excellent one. The value has to be right before the solver matters. At 256 tokens, roughly one chunk, the gap is widest: 89.0% against 81.5% for density. At 1,024 tokens all three find the answer for at least 98.5% of questions.

Where to put it. Liu et al. measured that models use information at the start or the end of a long input better than in the middle (Lost in the Middle, arXiv:2307.03172): accuracy against position is U-shaped. The engine models that as two parabolas, $p =$ 0.75 at the start, 0.55 at the trough, 0.65 at the end (illustrative numbers, not the paper's), and lays the packed set out four ways. At 1,024 tokens with the top packer, the mean $p$ at the answer is 0.670 with ends (best chunk first, second best last, weakest in the middle), 0.667 best-first, 0.607 best-last and 0.551 with the best chunk buried in the middle. With one chunk there is no "where": at 256 tokens every placement is the same.

Maths

With $n$ candidates of integer weights $w_i$ and values $v_i$ , the dynamic programme fills a table $\text{best}[i][c]$ , the most value from the first $i$ candidates within $c$ tokens: $\text{best}[i][c] = \max\big(\text{best}[i-1][c],\ \text{best}[i-1][c - w_i] + v_i\big)$ , in $O(nB)$ time: here $20 \times 1{,}025$ cells for $B = 1{,}024$ . Walking back from $\text{best}[n][B]$ recovers the set. The density greedy has no such guarantee: one long, valuable chunk can lose to several short ones that fill the budget badly.

Placement is a separate choice. If the answer chunk occupies tokens $[a, a + w)$ of a packed context of $T$ tokens, its position is $x = (a + w/2)/T$ , and the chance it is used is $p(x)$ . "Ends" puts the highest-value chunks at the smallest and largest $x$ , where $p$ is highest.

Code

The optimal packer's recurrence, cut from the vendored engine (knapsackTable): each row copies the previous one and takes item $i$ only where that strictly beats leaving it out.

for (let c = w; c <= budget; c++) {
  const t = prev[c - w]! + v;
  if (t > row[c]!) {
    row[c] = t;
    tk[c] = 1;
  }
}