Dispatching the Context Window: Future-Aware Token Budgets for Multi-Hop Retrieval

When a language model answers a question that needs several retrieval steps ("which university did the director of film X attend?"), the evidence from early steps has to stay in the model's prompt until the end. The prompt has a fixed token budget. Systems that shrink retrieved text step by step therefore face the same trap that ride-hailing dispatchers face with taxis. A greedy dispatcher sends each car to the nearest request and ends up with cars stranded in quiet suburbs right before rush hour. A greedy context compressor keeps whatever looks most relevant to the current step. It ends up spending tokens on passages that will not matter later, or it throws away a "bridge" fact that looks irrelevant now but is the only link to the next hop. Once that fact is gone, every later step fails, and no downstream cleverness can recover it.

We propose to manage the context window the way fleet operators manage vehicles. Each retained span of evidence is treated as a resource whose worth depends on where the reasoning chain is going, not only on where it is now. At every hop, a learned per-span value function, combined with an exact budget-constrained selection step, decides which spans to keep in full, keep as a short summary, keep only as a cheap re-expandable pointer, or drop. The value function is trained only from final answer quality. The two-sentence version is this: borrow the value-function-plus-optimizer recipe that freed taxi dispatch from greedy matching, and use it to allocate prompt tokens across retrieval hops. Make the allocation reversible, so an early mistake does not cascade.

Core Claim

The claim is that, under a hard reader budget, most multi-hop failures of iterative compressors come from early-hop allocation decisions rather than from reader reasoning. Two kinds of failure dominate. The first is stranding, where a gold bridge fact was retrieved at some hop but is missing from the final context. The second is crowding, where early verbose evidence leaves too little budget for later hops or for the reader's own answer reasoning. A value function over the retained context state that is trained to predict final F1 should reduce both, and it should beat any scorer that judges spans by relevance to the current hop or to the original question.

The second clause is the falsifiable part. If ranking spans by relevance to the full question captures the same benefit, the idea reduces to better relevance scoring and is not worth the machinery. MuSiQue is the right place to test this. Its construction guarantees that intermediate hops are connected and filters out shortcuts (MuSiQue), so bridge facts there are, by design, often weakly related to the surface question.

Relation to Prior Work

The method comes from spatial resource allocation. NeurADP breaks a fleet-level value function into per-vehicle values. It scores feasible actions with a neural network and hands those scores to an integer program, which yields up to 16% more served requests on Manhattan taxi data. It also learns to "strategically sacrifice" immediate requests. CVNet-style dispatching shows the related hot/cold strategy of declining trips that would strand supply in low-value regions. We reuse the decomposition-plus-solver structure. Spans of evidence play the role of vehicles, and the remaining token budget plays the role of idle fleet capacity.

The file also lists a limitation we expect to inherit. Decomposed values assume individual actions do not drastically shift the global state, and that assumption fails under extreme scarcity. A tight token budget is exactly that regime, so we test it directly rather than assume it away.

The motivating evidence comes from iterative and learned compression. CompAct compresses five documents at a time into a running summary and stops early when it emits a [COMPLETE] token. It gains 7.0 F1 over RECOMP on HotpotQA. However, its drop and stop decisions are hard and judged only against the current state. CORE-RAG trains a compressor with reinforcement learning on downstream exact match and improves Natural Questions EM by 3.3 points at roughly 3% of the tokens, but it compresses a single static pool in one shot. Both show that reader accuracy is the right training signal. Neither prices the future.

PAGE-RAG promotes evidence through a query-local graph under a fixed budget and penalizes distractor "hub" entities. It is extractive over a single candidate pool, so a hop missing from that pool is unrecoverable. Q-RAG is the closest prior work. It casts multi-step retrieval as a Markov decision process and trains embedders with soft Q-learning. That is already "value functions for multi-hop retrieval," so our novelty must lie elsewhere. Q-RAG values which chunk to fetch next, uses dense supporting-fact supervision, and ignores the reader's token capacity. We value what to keep and in what form, under a shared budget, with only final-answer supervision.

Budget-aware generation constrains the design. TALE shows that reasoning length follows prompted budgets until a threshold, below which accuracy collapses and outputs paradoxically grow. Starving the reader's answer-reasoning reserve is therefore itself a stranding failure, so the reserve must be a priced destination in our allocation. INTENT avoids myopic overspending on monetary tool costs with intention-aware world models. It reaches 100% budget feasibility on StableToolBench. It handles API cost, not in-context tokens.

On the cascading-error side, BioMLN avoids cascades by passing soft classifier margins rather than hard labels into joint inference. Our pointer ("stub") action is the language-model analogue of that soft commitment. Before Reasoning Can Fail shows that agents finalize answers from snippets without reading full documents, and that a binary read gate rescues 14.9–19.9 points on such questions. We treat that gate as a fixed constraint and ask the different question of how much to read and keep.

Research Program

The setting is a frozen reader model with a hard total budget $B$ tokens. That budget covers retained evidence plus a reserve for answer reasoning. A fixed retriever runs for up to $T$ hops, and at each hop it proposes candidate passages conditioned on the current context. Every span in the union of retained and newly retrieved spans receives one of four forms: full text, a summary (produced once per span by a fixed summarizer, as in CompAct), a stub of a few tokens naming the passage and its key entity, or dropped.

A stub can be re-expanded to full text at a later hop at the cost of its tokens. This makes early drops reversible. It plays the role that repositioning plays in fleet dispatch, where a car is not lost, only moved.

At hop $t$, the allocation $x$ (one form per span) is chosen by solving

$$\max_{x}\; \sum_{i} v_\theta(i, x_i \mid s_t) \;+\; u_\phi(B - c(x),\, t) \quad \text{s.t.}\quad c(x) \le B,$$

Here $v_\theta(i, x_i \mid s_t)$ is a learned estimate of how much keeping span $i$ in form $x_i$ adds to final answer F1, given the current state $s_t$ (question, retained context, hop index). The term $c(x)$ is the total token cost of the allocation. The function $u_\phi$ is the learned value of leaving the remaining budget free for future hops and the reader's reasoning reserve. Because each span picks one of a few forms with an additive cost, this is a multiple-choice knapsack problem and is solved exactly by dynamic programming in milliseconds. The solver plays the role of NeurADP's integer program.

Training follows approximate dynamic programming. We roll out trajectories with an exploring policy and record final reader F1. Then $v_\theta$ and $u_\phi$ are fitted by temporal-difference regression, bootstrapping the hop-$t$ estimate from the hop-$(t{+}1)$ estimate and the final F1. We start from Monte Carlo returns for stability. We also study a discount $\gamma$ on future value. With $\gamma = 0$ the method becomes the myopic controller, which is our central ablation.

The value networks are small cross-encoders over the span, its form, and a compact encoding of the state. They are trained on HotpotQA and MuSiQue training splits. Supporting-fact labels are used only for analysis, never as training targets.

We will also build the diagnostic that the argument depends on. A failure is classified as stranding (a gold bridge fact appeared at some hop but is absent or only a stub at the end), crowding (the gold fact was never retrieved because the budget hit zero, or the reasoning reserve fell under the TALE breakdown threshold), or reader error (gold facts present in the final context, wrong answer anyway).

Baselines

The naive reference point is full-context ingestion with truncation to $B$. All retrieved passages are concatenated in retrieval order, cut at the budget, and fed to the same frozen reader. The same retriever, hop count, and budget apply everywhere. This shows how much any allocation buys at all. It is expected to be weak at tight budgets, consistent with reader degradation under deeper retrieval (zero-shot reader distraction).

The strongest existing iterative method is CompAct (CompAct). It is run with its released compressor and early-termination tokens on the same retrieval stream, with the running summary capped so its total stays within $B$. Its reported result is a 7.0 F1 gain over RECOMP on HotpotQA. The file gives no absolute CompAct F1 on MuSiQue, so we will rerun it. Beating it means a statistically significant answer-F1 gain at matched average tokens, with the gain concentrated in examples our diagnostic labels as stranding.

The strongest fixed-budget extractive method is PAGE-RAG (PAGE-RAG), applied at every hop over the same candidate pools. It reports boosting SelfRAG Answer F1 on HotpotQA from 62.39 to 69.36 within the same token budget. Because readers and retrievers will differ from that paper, we reproduce rather than copy the number.

CORE-RAG (CORE-RAG) applied independently at each hop is the "learned but myopic" reference. Its reported result is +3.3 EM on Natural Questions at about 3% of tokens. We use the same reader for reward and the same number of training rollouts as our method.

For Q-RAG (Q-RAG, code), the file reports BabiLong and RULER robustness but no HotpotQA or MuSiQue figure. We will run it as the retriever, with greedy truncation to $B$, and also stack our allocator on top of it. The question is whether value-based fetching and value-based keeping are complementary.

Three ablations isolate the key ingredient, and all use the same knapsack solver, forms, and training budget. The first replaces $v_\theta$ with a cross-encoder relevance score against the original question. The second replaces it with relevance against the current sub-question. The third sets $\gamma = 0$. A fourth ablation removes the stub action, which tests whether reversibility rather than valuation carries the gain. Hyperparameters for every method get the same search budget on a held-out development split.

Why not just…?

Why not just feed everything to a long-context model? Because the regime of interest is a hard budget, and the evidence is that more context is often worse even when it fits. CORE-RAG improves exact match by compressing to about 3% of tokens. Reader accuracy falls as retrieval depth grows. Our truncation baseline, plus an untruncated long-context reader run at one generous budget, will show whether the effect holds for current readers. If the untruncated reader matches our method at large $B$, we will report that the contribution is confined to tight budgets.

Why not just score spans by relevance to the whole question and keep the top ones? This is the real threat, and it could plausibly capture most of the future value, because the question mentions the final target. The question-relevance ablation tests exactly this. The proposal stands only if our method wins specifically on examples whose bridge fact has low question relevance, which we stratify by the bridge fact's relevance rank under the baseline scorer, and only if that win is largest on MuSiQue, whose construction removes shortcuts. If the two methods tie, we will conclude that "future value" is mostly question relevance plus reversibility, and report the cheaper method.

Why not just split the budget evenly across hops, or tell the model the budget in the prompt? Even splitting is what CompAct-style capped summaries effectively do. Prompted budgets are known to fail in two ways: they break down below a threshold (TALE), and simple prompting violated hard budgets in up to 32.8% of tasks in INTENT. We include a uniform-split allocator in the same solver. Our crowding diagnostic measures whether its failures come from late-hop starvation, which is what learned allocation should fix.

Why not just make drops reversible, without any learned value? Stubs alone may remove most stranding, which would make the value function unnecessary. The no-value ablation (stubs plus question-relevance scoring) against the no-stub ablation (learned value without stubs) separates the two ingredients. We will report their interaction honestly.

Proposed Experiments

The main evaluation is answer F1 and EM on HotpotQA (distractor and full-wiki settings) and MuSiQue-Ans, plus 2WikiMultiHopQA for transfer. Budgets $B$ are 512, 1k, 2k, and 4k tokens, with up to four hops and one frozen open-weight reader shared by all methods. For MuSiQue, the file's reference points are a best reported Select+Answer F1 of 47.3 and human F1 of 78.0. Alongside answer quality we report average tokens consumed, re-expansion counts, and the disconnected-reasoning score on MuSiQue-Full, to check that gains are not shortcut exploitation.

Three checks decide whether the idea is right. First, the stranding rate under our method should be clearly below that of CompAct and the $\gamma = 0$ ablation. The F1 gap should shrink to near zero on examples where no baseline strands a bridge fact. If gains appear uniformly instead, the stranding story is wrong. Second, the margin over the question-relevance ablation should grow with hop count and be largest on low-relevance bridge facts. Third, the advantage should be largest at the tightest budgets, which mirrors the fleet result that future-aware dispatch matters most under scarcity. If decomposed values break down at 512 tokens, as the scarcity limitation predicts, we will add a pairwise interaction term between spans that share an entity and measure whether it closes the gap.

A final transfer test trains values on HotpotQA and applies them to MuSiQue. This shows whether the value function learned something about chain structure or only about one dataset's retrieval statistics.