When Does Context Selection Need Lookahead? Tree Search for Complementary, Not Redundant, Evidence

Retrieval-augmented language models answer questions by pasting a handful of retrieved passages into their prompt. Standard retrievers score each passage on its own, so the top of the list often holds near-duplicates. These waste the limited prompt space and miss the other facets of a complex question. Two families of fixes exist. Diversity methods such as maximal marginal relevance and determinantal point processes pick passages greedily, one at a time, penalizing overlap with what is already chosen. Tree-search methods, chiefly Monte Carlo Tree Search (MCTS: an algorithm that explores a tree of sequential choices by simulating many partial paths and backing their scores up the tree), look ahead over whole sets and orderings of passages. This note argues that the two families solve different problems, and that the field has been conflating them.

The claim is this. Redundancy is a "diminishing returns" property: a passage is worth less once its facts are already covered. Greedy selection is provably near-optimal for objectives of that kind. Tree search should therefore add little when the only problem is redundancy. Its value lies in the opposite regime, complementarity, where a passage is worthless alone but decisive in combination with another. A multi-hop bridge document is the typical case: it looks irrelevant to the question until the document naming the bridge entity is also in the context. We propose to build an MCTS context selector whose reward is joint sub-question coverage of the selected set. We will measure, per query, how far that reward departs from diminishing returns, and test whether the gains of tree search over greedy selection concentrate exactly where that departure is large. If they do, the result explains when the extra computation of tree search is worth paying, and it supplies a cheap gate for invoking search only on those queries.

Core Claim

Let $U(S)$ be the utility of a passage set $S$ for a query, defined as the fraction of the query's sub-questions that can be answered from $S$ taken together. For each query we measure a complementarity score:

$$ \gamma = \min_{S,\,A} \frac{\sum_{a \in A} \big[U(S \cup \{a\}) - U(S)\big]}{U(S \cup A) - U(S)}. $$

Here $S$ is a partial selection and $A$ is a small set of added passages. The score $\gamma$ compares the summed individual gains of the passages in $A$ with their joint gain. A value $\gamma \ge 1$ means diminishing returns (pure redundancy structure). A value $\gamma \ll 1$ means the passages are worth much more together than apart. Greedy selection's approximation guarantee weakens as $\gamma$ falls; the standard $(1-1/e)$ bound for diminishing-returns objectives generalizes to one that decays with this ratio. That decay motivates the prediction. The hypothesis is that the gain of MCTS over greedy selection under the same $U$ and the same budget is near zero on high-$\gamma$ queries and grows as $\gamma$ drops.

This differs from the closest existing system in three ways. CARROT, in CORAG, already runs MCTS over combinations and orderings of pre-retrieved chunks under a token budget. It explicitly targets redundancy and the fact that adding chunks can hurt, and it scores simulated sets with re-ranker scores. We differ first in the reward: set-level joint coverage rather than re-ranker scores. CRUX shows that pointwise re-rankers fall into a "redundancy trap", which directly contradicts CARROT's reliance on them as a simulation proxy. We differ second in the action space, which can issue new retrievals targeted at uncovered sub-questions rather than only permuting a fixed pool. The third and main difference is that we treat "when does search beat greedy" as the scientific question, rather than presenting tree search as uniformly better.

Research Program

The selector has three parts.

The first part is the utility model. Following the CRUX recipe, each query is decomposed into sub-questions. On multi-hop data these come from gold supporting-fact structure where available, and otherwise from an LLM. A small cross-encoder is trained to predict whether a sub-question is answerable from a concatenated passage set. Because it reads the set jointly, it can register that a bridge passage becomes useful only next to its partner, which a pointwise scorer cannot. Every call to this model is cached and counted as the unit of search budget.

The second part is the search. States are ordered partial contexts. There are three kinds of action: add a passage from the candidate pool; issue a follow-up retrieval using the text of the lowest-covered sub-question as the query, which adds new candidates; and stop. The reward is $U$ at termination minus a per-token cost. Stopping when marginal coverage turns negative addresses the non-monotonic context utility noted by CARROT, RCR, and MCTS-RAG. The follow-up-retrieval action responds to the concern in Graph-Based Algorithms for Diverse Similarity Search that a redundant initial pool caps anything done afterward. It does this without requiring FREESON's static prefix-tree corpus index (FREESON).

The third part is the gate. Computing $\gamma$ exactly is expensive. We will train a lightweight predictor of $\gamma$ from the query and the first-stage candidates, supervised by estimates of $\gamma$ obtained through sampling on training queries. At inference the predictor routes high-$\gamma$ queries to greedy selection and low-$\gamma$ queries to MCTS.

The analysis is the centerpiece. For every query in every benchmark we record $\gamma$ and the coverage and answer accuracy of each selector at equal budget. We then plot the gain of MCTS over greedy selection against $\gamma$.

Baselines

The naive reference is pointwise top-$k$: a first-stage dense retriever plus a cross-encoder re-ranker, truncated to the same token budget. CRUX shows that this reference degrades coverage, and every method must clear it.

Maximal marginal relevance and greedy DPP re-ranking, following DPP-R, are the strongest cheap diversity baselines. DPP-R reports 58.8% Top-10 MRECALL on AmbigQA-Dev against 48.2% for JPR. They are run on the identical candidate pool, with $\lambda$ and kernel weights tuned on the same dev split we use for our own hyperparameters.

JPR (Joint Passage Ranking) is the strongest learned set-aware re-ranker on multi-answer data. It reports 56.7% MRECALL@5 on WebQSP against 40.2% for an independent re-ranker. We use its released TreeDecode setup where available.

RCR (Reinforcing Compositional Retrieval) is the strongest learned sequential policy without backtracking. It reports 59.64% on GeoQuery Template 1 against 40.36% for BM25. We retrain its tri-encoder on our training splits with the coverage reward so that it optimizes the same objective.

CARROT is the closest MCTS competitor. Its paper reports "up to a 30% improvement" in ROUGE-1, ROUGE-L, and F1, but we found no per-dataset number on Lacuna. We therefore reimplement it with its re-ranker-score reward under our budget.

Two ablations isolate our ingredients. The first is greedy and beam selection using exactly our $U$. This is the key control: it separates "better objective" from "lookahead." The second is our MCTS with CARROT's re-ranker reward, which separates "lookahead" from "better objective." All searchers receive the same number of utility-model calls, from 1× to 32× the greedy count. Beating a baseline means higher coverage and answer F1 at matched calls and matched tokens, with a paired bootstrap interval excluding zero. For the headline claim, the result must also show a significant negative slope of gain against $\gamma$.

Why not just…?

Why not just use greedy DPP or MMR? For redundancy alone, we expect greedy to be as good as search, and the proposal predicts this outright. On AmbigQA, whose multiple answers are largely parallel and redundant, a tie with DPP-R would count as confirmation, not failure. Greedy cannot pick a passage whose value appears only after its partner is chosen. The HotpotQA bridge subset (42% of questions per HotpotQA) versus its comparison and intersection questions provides a natural contrast for testing this.

Why not just run beam search over the same utility, as in Determinantal Beam Search? This is the real threat. DetBS shows that diversity-aware beams are cheap and effective. A width-$b$ beam may already capture two-step complementarity. The equal-budget beam ablation settles it. If beam matches MCTS across all $\gamma$, we will report that the operative ingredient is shallow lookahead rather than Monte Carlo exploration, and ship the gated beam version. The $\gamma$ analysis and the gate survive either way.

Why not just train a sequential policy like RCR with the coverage reward? A trained policy amortizes search into one forward pass per step. RCR itself notes compounding errors from irreversible early choices, and its performance peaks near four steps. Retraining it on our reward and comparing on low-$\gamma$ queries tests whether amortization recovers what backtracking finds. If it does, the right product is distilling MCTS traces into RCR, which we would then test.

Why not just diversify upstream with retriever portfolios or diverse graph indexes? Retriever Portfolios (average EM 0.464 versus 0.356 for nearest-neighbor on Gemma-3-27B-IT) and diverse DiskANN search improve the candidate pool cheaply. They are complementary to our method rather than competing with it, since they fix redundancy in the pool, not complementarity in the selection. We will run our selector on top of a portfolio pool to check that the low-$\gamma$ gains persist.

Proposed Experiments

The benchmarks span the $\gamma$ spectrum. AmbigQA and WebQSP are expected to be mostly redundancy-driven. HotpotQA (distractor and full-wiki), 2WikiMultiHopQA, and MuSiQue are expected to be complementarity-driven. CRUX-DUC and CRUX-Multi-News test long-form coverage.

The metrics are MRECALL@$k$ on the multi-answer sets, CRUX Coverage, $\alpha$-nDCG, and Density on CRUX, and EM/F1 with a fixed reader on the multi-hop sets. CRUX reports a Kendall's $\tau \approx 0.7$–$0.8$ between its Coverage metric and long-form generation quality, which justifies using coverage as the search target.

The first decisive check is the gain-versus-$\gamma$ curve. The hypothesis fails if MCTS beats greedy under the same $U$ by similar margins on AmbigQA and on MuSiQue. The second check compares the CARROT-reward and coverage-reward variants on CRUX, which tests directly whether the contradiction between CRUX and CARROT matters for search quality. The third check is the gated system's accuracy–compute frontier against always-search and never-search. Success is matching always-search accuracy at a fraction of its utility-model calls. The fourth check isolates the follow-up-retrieval action: it should matter most on full-wiki HotpotQA, where the initial pool is weakest.