Five rows can contain five very different budgets

Imagine a lunchbox with room for a fixed volume. The first ranked result is a long chapter. The next three are overlapping passages from that chapter. The fifth is a concise definition from another source. Taking the first five rows can exceed the box, repeat one idea four times, and omit the definition.

A machine reader does not see a result page and decide what to skim. It receives a bounded sequence of tokens. Define each candidate passage $x$ by:

• token cost $c(x)>0$;
• source and stable identity;
• relevance evidence;
• concepts or claims it covers;
• overlap with other candidates;
• structural location and continuation edges; and
• provenance, confidentiality, and settlement labels.

The real constraint is

$$\sum_{x\in S}c(x)\leq B,$$

where $B$ is admitted context budget. A row count is only a proxy when every row has nearly equal cost, which passages rarely do.

Diminishing returns names redundancy

Let $F(S)$ measure the useful evidence covered by a set of passages. If a passage repeats material already selected, its marginal gain should fall. For $A\subseteq B$ and $x\notin B$, require

$$F(A\cup\{x\})-F(A)\geq F(B\cup\{x\})-F(B).$$

This is submodularity: adding $x$ helps no more after the pack already contains more evidence. A simple coverage objective is

$$F(S)=\sum_{u\in U}w_u[\text{some }x\in S\text{ covers }u],$$

where $U$ is a finite set of query-relevant concepts or claims. The first passage covering $u$ earns $w_u$; repetitions earn no additional coverage.

Not every useful objective is submodular. Two passages may be complements: a definition is useless without its worked example, or a pronoun-bearing chunk needs its preceding sentence. Then their joint value can exceed the sum of their separate gains. Represent mandatory structural companions as one atomic candidate or add explicit dependency constraints; do not cite a diminishing- returns theorem after violating its premise.

The famous greedy guarantee has a narrow door

First suppose every candidate has unit cost and the pack may contain at most $K$ candidates. If $F$ is nonnegative, monotone, submodular, and $F(\varnothing)=0$, repeatedly choose the candidate with greatest marginal gain.

Let $S_i$ be the greedy set after $i$ choices and $O$ an optimal set of at most $K$ candidates. Submodularity implies that some remaining member of $O$ has marginal gain at least

$$\frac{F(O)-F(S_i)}{K}.$$

Greedy chooses at least that much, so the remaining gap contracts by at most $1-1/K$ each round. After $K$ rounds,

$$F(S_K)\geq \left(1-\left(1-\frac1K\right)^K\right)F(O) \geq (1-1/e)F(O).$$

That result is not a license for naive token packing. Passage costs vary. The constraint is a knapsack, not a cardinality limit. Sviridenko established a $1-1/e$ approximation for monotone submodular knapsack, but the algorithm uses partial enumeration; merely sorting marginal gain per token does not inherit the theorem.

The practical lesson is honest:

• use the simple greedy theorem when candidates have the declared equal-cost boundary;
• use a knapsack-capable algorithm when its guarantee matters; or
• use bounded density allocation as a heuristic, report no borrowed approximation ratio, and evaluate it against an exact oracle on small packs.

Floors prevent one source from consuming the box

A rank-only fill can spend the whole budget on passages from one document or one provider. Sometimes that is correct. Sometimes the task requires a minimum amount from instructions, evidence, definitions, or current state.

Declare source groups $G_1,\ldots,G_m$ and token floors $f_i$. Admission first checks

$$\sum_i f_i\leq B.$$

If floors exceed the budget, reject the policy before reading candidates. If a group cannot supply its floor, return the unused credit to the common pool and record that the floor was unsatisfied; do not pad with irrelevant text.

After feasible floors, allocate remaining tokens by marginal value per cost, recomputing marginal value after each choice. This waterfilling-like policy has two concrete bounds even when it has no universal quality ratio:

• it never spends more than $B$; and
• no group receives less than its feasible satisfied floor.

Those are resource and fairness bounds, not an optimality theorem. Quality is measured against the evaluator from Chapter 24.

PACK(CANDIDATES, BUDGET, FLOORS)
Input:  bounded CANDIDATES, token BUDGET, feasible group FLOORS
Output: ordered context pack plus settlement receipt

pack ← EMPTY
remaining ← BUDGET
for each group in STABLE-GROUP-ORDER(FLOORS)
    chosen ← BEST-FLOOR-BUNDLE(group, FLOORS[group], remaining)
    pack ← ADD-ATOMIC(pack, chosen)
    remaining ← remaining - COST(chosen)
while EXISTS-FITTING-CANDIDATE(CANDIDATES, pack, remaining)
    next ← MAX-MARGINAL-GAIN-PER-TOKEN(CANDIDATES, pack, remaining)
    pack ← ADD-ATOMIC(pack, next)
    remaining ← remaining - COST(next)
return ORDER-FOR-READING(pack, remaining)

Every loop removes one candidate and remaining budget decreases, so work is bounded by candidate admission and budget. BEST-FLOOR-BUNDLE is itself a bounded solver or an exact small-group enumeration; hiding an unbounded search inside that name would invalidate the resource claim.

Repair fragments before scoring their cost

A high-scoring passage may begin mid-sentence, with “this result” or “therefore” pointing outside the chunk. Feeding it cheaply is not efficient if the evidence cannot be interpreted.

Each candidate declares structural edges to its heading, preceding definition, or continuation. The packer can:

• expand backward to the nearest self-contained boundary;
• attach a small authored or extracted heading;
• join a required neighbor as one atomic bundle; or
• reject the candidate when repair exceeds the remaining budget.

Cost is computed after repair. Scoring a 90-token fragment and later expanding it to 400 tokens overdraws the knapsack.

Expansion trades precision for context. It is not automatically good. Evaluate headless-chunk comprehension and false-positive exposure on held-out tasks, and cap every expansion by nodes, tokens, and structural distance.

Deduplicate sections and their continuations

A whole section and two passages from that section may all rank highly. Stable source spans reveal overlap before tokens are copied. Exact overlap can be removed canonically; near-duplicate passages require a declared similarity rule with a threshold and an explanation.

Maximal marginal relevance offers a practical family: balance query relevance against similarity to already selected items. It is a heuristic objective, not proof that “diverse” means useful. Two passages can use different words while making the same claim, or share words while providing complementary evidence.

Preserve the reason for removal in the receipt:

• exact duplicate identity;
• contained source span;
• overlapping repaired bundle;
• near-duplicate under a named policy; or
• budget exclusion.

“Not selected” otherwise conflates low value, redundancy, and lack of space.

Order after selection is a separate decision

The set objective chooses what fits. A machine receives a sequence. Ordering can preserve document structure, place definitions before uses, group claims with citations, or follow decreasing relevance. These policies are not equivalent.

Represent prerequisite edges among selected bundles and produce a stable topological order. If the edges cycle, the candidates were not independently admissible; collapse the cycle into one atomic unit or remove a low-marginal bundle. Never break a semantic dependency merely to preserve original rank.

The final pack carries delimiters, source identities, titles, locations, settlement, and access labels. It does not flatten several documents into an anonymous block whose claims can no longer be attributed.

Partiality remains visible to the consumer

A pack can be partial because candidate generation was capped, a provider was unavailable, a floor was unsatisfied, expansion exceeded its bound, or the token budget excluded useful evidence. Record each cause.

The consumer must be able to distinguish:

• no relevant evidence exists in the searched universe;
• relevant evidence existed but did not fit;
• a source was not searched or did not settle; and
• evidence was withheld by an access boundary.

These outcomes may all produce the same number of tokens. They do not support the same conclusion.

Evaluate the pack, not its elegance

Use the pinned evaluator from Chapter 24. Compare at least:

• positional truncation;
• relevance-per-token packing;
• redundancy-aware packing;
• floor-reserved packing; and
• a small exact knapsack oracle where candidate counts permit it.

Measure task-specific correctness, citation support, hard-negative inclusion, coverage of required concepts, duplicate-token fraction, unusable headless chunks, unused budget, source-floor satisfaction, and latency. Pair every quality metric with an independent harm guard.

Evaluate on held-out query families and budget sizes. A policy tuned at 8,000 tokens can fail at 800 because floors dominate; a policy tuned on long articles can waste budget on short commands. Publish a curve over budgets, not one victory at one context size.

Negative results

Lessons

• For a machine reader, the real top-k bound is admitted tokens.
• Context selection is a constrained allocation problem, not row truncation.
• Submodularity models diminishing value from repeated evidence.
• Simple greedy earns $1-1/e$ under monotone unit-cost cardinality assumptions; token knapsack requires stronger machinery for that guarantee.
• Floors reserve feasible minimum representation without proving quality.
• Structural repair happens before cost admission.
• Exact and near-duplicate removal need stable identities and named policies.
• Set selection and reading order are separate algorithms.
• Provenance, confidentiality, and settlement survive packing.
• Quality is measured across budgets and held-out tasks, not chosen by taste.

Practice

1. Pack five passages with unequal costs under a 100-token budget using rank, relevance-per-token, and redundancy-aware policies; compare the evidence.
2. Prove the greedy cardinality gap contraction for $K=3$.
3. Construct a knapsack counterexample where density greedy misses a better combination.
4. Define an atomic repair bundle for a pronoun-bearing passage and account for its full cost.
5. Design feasible floors for three sources and specify what happens when one source is unavailable.
6. Give a selected set whose reading order must differ from relevance order.
7. Extend a query receipt with duplicate-removal and budget-exclusion reasons.

References

1. Herbert A. Simon. “Designing Organizations for an Information-Rich World.” In Computers, Communications, and the Public Interest, Johns Hopkins Press, 1971.
2. G. L. Nemhauser, L. A. Wolsey, and M. L. Fisher. “An Analysis of Approximations for Maximizing Submodular Set Functions—I.” Mathematical Programming 14, 1978.
3. Maxim Sviridenko. “A Note on Maximizing a Submodular Set Function Subject to a Knapsack Constraint.” Operations Research Letters 32.1, 2004.
4. Jade Goldstein and Jaime Carbonell. “Summarization: (1) Using MMR for Diversity-Based Reranking and (2) Evaluating Summaries.” TIPSTER, 1998.