Adaptive Retrieval Routing: Choosing a Strategy per Query

From a binary gate to a choice of effort

The selective-generation topic ended with a decision that had two actions. Given a candidate answer and a score meant to be its probability of correctness, emit it or abstain, cutting at Chow’s threshold $t^\star = 1 - c_{\mathrm{abs}}/c_{\mathrm{err}}$ . That gate is genuinely useful and genuinely limited: it can decline to answer, but it cannot try harder.

Trying harder is what the rest of the stack is for. A query that a single dense retrieval fails on might be answered by iterating — retrieving, reading, reformulating from what was read, retrieving again. A query whose answer the system already holds might need no retrieval at all. These are not refinements of one method; they are different strategies with different prices, and nothing so far decides between them.

So the object changes again. Where the gate chose between answering and declining, a router chooses among strategies, and it has to choose before it knows how any of them will turn out — using only what is visible about the query itself. The decision is now genuinely economic: every arm has a cost, the expensive ones are sometimes worth it, and the entire question is whether you can tell in advance which times those are.

That last clause is where this topic spends most of its honesty. It is easy to show that a router could help. The harder and more useful result is a precise statement of how much it could help at most, and a measurement of how much of that a real one actually collects.

The rule, with more than two actions

Fix a set of arms $a \in \{1, \dots, K\}$ — here: answer from the query alone, retrieve once, or iterate. Each arm applied to query $x$ yields an answer of quality $Q_a(x) \in [0,1]$ and consumes a resource cost $c_a > 0$ . A router is a policy $\pi$ mapping $x$ to an arm, using only a feature vector $\phi(x)$ computable before any retrieval fires. That restriction is not fastidiousness: a feature that requires the retrieved set has already paid the cost the router exists to decide about, and a rule that uses one is a reranker wearing a router’s name.

Theorem 1 (The K-action rule, and Chow's rule as its two-action case).

Let the expected loss of taking arm $a$ on query $x$ be the cost of being wrong plus the cost of the work:

L_a(x) = c_{\mathrm{err}}\big(1 - Q_a(x)\big) + c_a .

Minimizing pointwise over $a$ , and discarding the constant $c_{\mathrm{err}}$ , gives

\pi^\star(x) = \arg\max_a \Big\{ c_{\mathrm{err}}\, \mathbb{E}\big[Q_a \mid \phi(x)\big] - c_a \Big\} = \arg\max_a \Big\{ \mathbb{E}\big[Q_a \mid \phi(x)\big] - \lambda\, c_a \Big\},

writing $\lambda = 1/c_{\mathrm{err}}$ for the price of a unit of retrieval in units of answer quality.

Now take $K = 2$ with the actions emit and abstain. Emitting has quality $s$ , the probability the answer is correct, and no resource cost. Abstaining has quality $0$ and bookkeeping cost $c_{\mathrm{abs}} - c_{\mathrm{err}}$ , which is exactly what makes its loss $c_{\mathrm{err}}(1-0) + (c_{\mathrm{abs}} - c_{\mathrm{err}}) = c_{\mathrm{abs}}$ . The rule then reads

\text{emit} \iff c_{\mathrm{err}}(1 - s) < c_{\mathrm{abs}} \iff s > 1 - \frac{c_{\mathrm{abs}}}{c_{\mathrm{err}}} = t^\star,

which is Chow’s rule. The router does not replace the published gate; it contains it.

That reduction is verified rather than asserted: the notebook computes the $K=2$ rule and the imported chow_decision on the same scores across four cost ratios and requires them to agree on every query. It is worth insisting on, because it fixes what kind of object a router is. It is not a heuristic bolted on top of a retrieval stack. It is the same decision-theoretic argmax the stack already used, with the action set widened from two to three.

What a router can win, at most

Suppose the estimation problem were solved — the router knew each arm’s quality on each query exactly. How much better than a fixed strategy would it be? The answer is clean, and it is the result to carry out of this topic.

Write $U_a(x) = Q_a(x) - \lambda c_a$ for the utility of arm $a$ on query $x$ .

Theorem 2 (The routing gain is a Jensen gap).

Let the oracle be the policy that picks the best arm for each query with perfect foresight, and the best fixed arm be the single arm with the highest average utility:

\mathrm{Oracle} = \mathbb{E}\Big[\max_a U_a(x)\Big], \qquad \mathrm{BestFixed} = \max_a \mathbb{E}\big[U_a(x)\big].

Then

\mathrm{Oracle} - \mathrm{BestFixed} = \mathbb{E}\big[\max_a U_a\big] - \max_a \mathbb{E}\big[U_a\big] \;\ge\; 0 ,

since the maximum of expectations is bounded by the expectation of the maximum. The inequality is strict if and only if $\arg\max_a U_a(x)$ is not almost surely constant.

The corollary is what makes this worth knowing.

Corollary 3 (Routing is worthless when the arms never change places).

If one arm maximizes $U_a(x)$ for almost every $x$ , the gap is zero and no router, however well estimated, beats simply always using that arm. The gain available to routing is not a property of the classifier. It is a property of whether the strategies ever reverse.

This is a sharper claim than the usual argument for adaptive retrieval, which tends to observe that some queries are harder than others and conclude that routing must therefore pay. Heterogeneity in difficulty is not enough. If iterating is better than retrieving once on the hard queries and on the easy ones — merely by a smaller margin — then the ordering never reverses, the gap is zero, and the right system always iterates. What routing needs is heterogeneity in which arm wins, and those are different conditions.

The laboratory’s second panel makes the corollary a thing you can do rather than read. The gap is recomputed in the browser from the per-query quality matrix for any cost weight; toggling the control gives every arm the same per-query signal plus a fixed offset, so the ordering cannot vary, and the gap collapses to exactly zero while the arms remain visibly different from one another.

no retrieval (cost 0)retrieve once (cost 1)iterate (cost 3)

The compositional class is the whole reason a router can exist here. A single retrieval reaches the mentioned company 0 times out of 24 — never — because the bridge filing points mostly at the company it is about, not the one it names; only reformulating off it recovers the second direction. On the easy class all three arms are already right 24/24 of the time, so routing there is purely a question of what you are willing to pay.

72 synthetic finance queries in three classes over one passage set, 36 held out. Arm costs are 0 / 1 / 3 retrievals; the spread is load-bearing, since with costs close together the frontier collapses to a point. Every arm is the same answer model reading different evidence, so a quality difference is attributable to the strategy alone. Numbers mirror adaptive_retrieval_routing.py; Panel B recomputes the entire Jensen decomposition live from the baked per-query matrix. The corpus, the features, and the arm costs were all chosen against this corpus — the transferable claim is the shape of the argument, not these decimals.

The achievable region is a hull

Theorem 1 gives a family of policies indexed by $\lambda$ , not a single policy. Sweeping $\lambda$ from zero upward moves from buying quality at any price to refusing to retrieve at all, and each value yields one deterministic policy and one point in the cost–quality plane.

Proposition 4 (The achievable set is the convex hull of the lambda-indexed policies).

Let $P_\lambda = (\mathbb{E}[c_{\pi_\lambda}], \mathbb{E}[Q_{\pi_\lambda}])$ . Randomizing between two policies with probability $\theta$ and $1-\theta$ produces the corresponding convex combination of their points, because both coordinates are expectations and expectation is linear. Hence every point on the segment joining two achievable points is achievable, the achievable set is $\mathrm{conv}\{P_\lambda\}$ , and its upper-left boundary is concave.

Under a hard budget $\mathbb{E}[c_\pi] \le B$ rather than a price $\lambda$ , the optimum is attained by randomizing between the two adjacent deterministic policies that bracket $B$ — the familiar correspondence between a penalized and a constrained program.

Three frontiers therefore sit one above another: the hull of the fixed arms, which is what is achievable with no features at all; the achievable frontier of a fitted router; and the oracle’s. The vertical distance between the first and the third is the Jensen gap of Theorem 2, and the position of the middle curve is the empirical question.

On the held-out half of this corpus, the oracle reaches mean quality $0.546$ at a mean cost of $1.25$ retrievals, while always iterating — the best fixed arm — reaches only $0.522$ at a cost of $3.0$ . Perfect routing would buy better answers for a little over forty percent of the price. That is the prize. The rest of the topic is about how much of it is collectible.

What a real router collects

Replace $\mathbb{E}[Q_a \mid \phi(x)]$ with an estimate $\widehat{Q}_a(\phi(x))$ fitted on held-aside queries, and the rule becomes $\hat\pi(x) = \arg\max_a \{\widehat{Q}_a(\phi(x)) - \lambda c_a\}$ .

Proposition 5 (Excess loss is controlled by estimation error).

For any $x$ , if $\hat\pi(x) \ne \pi^\star(x)$ then the utility forgone is at most $\sum_a \big| \widehat{Q}_a(\phi(x)) - \mathbb{E}[Q_a \mid \phi(x)] \big|$ , since the chosen arm’s estimated utility was at least the optimal arm’s, and each can be off by at most its own error. Taking expectations bounds the excess loss of $\hat\pi$ over $\pi^\star$ by the summed $L_1$ estimation error across arms.

The router is therefore no better than the calibration of the numbers it compares — precisely the caveat Chow’s rule carried one level down, where the threshold was only as good as the score it cut. And the measurement is unkind. On this corpus the fitted quality model has an expected calibration error of $0.14$ to $0.18$ , and the consequences are visible at every operating point:

At $\lambda = 0.20$ the router gains $+0.043$ over the best fixed arm on held-out queries, which is $58\%$ of the oracle’s $+0.075$ , and a paired $t$ -test puts it at $p = 0.022$ .
At $\lambda = 0.02$ it gains $+0.018$ , about $31\%$ of the available gap — but $p = 0.24$ , so at thirty-six held-out queries this is not distinguishable from zero.
At $\lambda = 0.05$ it gains $+0.002$ : $3.5\%$ of a gap of $+0.062$ , and $p = 0.90$ . The gap is there; the router does not find it.
At $\lambda = 0.10$ it gains $-0.020$ . The oracle would win by $+0.054$ here, and the fitted router loses to always retrieving once.

That last line is the one worth sitting with. A positive Jensen gap is a statement about what perfect foresight would buy. It is not a promise that any realizable rule captures any of it, and at one of four operating points here the realizable rule is worse than not routing at all. A gap that exists is not a gap you can collect.

And in-sample measurement conceals exactly this. At every operating point the router’s gain measured on the queries that fitted it exceeds its gain on held-out queries — which is why the penalty on the quality model is chosen by cross-validation inside the calibration half. Choosing it against the test half would be the same optimism one level up, and would have produced a considerably more flattering set of numbers.

Why the compositional class is the hard part

The three query classes were built to make the arms reverse: a class answerable from the query alone, a class needing one retrieval, and a compositional class whose answer is a company that a bridge filing names rather than describes. On the last of these, a single retrieval reaches the answer in none of the twenty-four cases, and iterating reaches it in fourteen — the reversal Theorem 2 requires.

But the router has to identify that class before retrieving, and the obvious features do not. Entropy of the query-only answer distribution, the nearest-prototype cosine, and the margin between the top two cosines all place the compositional class between the other two rather than apart from them. The reason is geometric and slightly counterintuitive: a compositional query’s closest competitor is not the company it mentions but a neighbor of the company it is about, sitting in the same sector shell. The top-two margin is measuring the wrong pair.

What separates the class is the largest cosine to a prototype outside the sector of the nearest one — a direct measure of whether the query reaches across sectors at all. With the first three features the router collapses to always-retrieving-once at moderate $\lambda$ and gains nothing whatsoever; with the fourth it becomes the imperfect but occasionally useful rule measured above. That feature was chosen against this corpus, and the honest reading is that the transferable claim is Theorem 2 rather than any particular feature set.

§ What to spend on a question about a filing text pdf news

The three classes correspond to three genuinely different questions an analyst asks. What was this company’s reported figure? is answerable from a system that already holds the company’s filings — retrieval adds confidence but not correctness, and on this corpus all three arms answer it correctly every time, so the only question is what you are willing to pay. Which company in this sector is being described? needs one retrieval to resolve among near neighbors. Which counterparty does this filing name, and what is its exposure? cannot be answered by retrieving about the filing’s own subject at all; it requires reading the filing, extracting the named entity, and retrieving again.

A system that always iterates answers all three and pays triple for the first two. A system that never iterates answers the first two and silently fails the third — silently, because it returns a confident answer about the wrong company rather than an error. The router is the mechanism that would charge the third question more than the first, and Theorem 2 is the statement of when that is worth building: not when the questions differ in difficulty, but when they differ in which strategy serves them.

Where this sits

Adaptive-RAG, Self-RAG, and Corrective RAG are routinely presented as three architectures. Read along the axes that matter — how many times retrieval fires, what the retrieval unit is, how a document is represented — they occupy one point, and differ only in where the decision to continue is housed: in a front-door classifier, inside the generator as reflection tokens, or in an external evidence grader. This topic formalizes the first placement, and the analysis is indifferent to which is chosen. Theorem 2 constrains all three equally, because it is a statement about the arms rather than about the mechanism that selects among them.

What is left open is the part this corpus cannot reach. A router that bounded its own regret rather than merely reporting it would need the distribution-free machinery the prerequisite gate used for its threshold, applied now to a comparison among arms rather than to a single cut. And the question of whether the advantage ordering reverses on real corpora — as opposed to on one built so that it does — is an empirical one that a synthetic study is not entitled to answer.

⚠ Rigor flag

Three results here are theorems and one is an observation, and the difference is load-bearing. The $K$ -action rule and its exact reduction to Chow’s gate, the convex hull, and the Jensen gap are proved and verified. What is measured — and what could have come out differently — is whether a realizable router collects the gap. On this corpus it collects $58\%$ of it at one operating point, $3.5\%$ at another, and less than none at a third, where it loses to always retrieving once. Only one of four gains is distinguishable from zero at $n = 36$ . In-sample measurement overstates the gain at every operating point.

The corpus is a designed mechanism study, not a benchmark. The query classes, the arm costs, the mention angle, the concentrations, and the feature set were all chosen against this corpus, and the cross-sector feature exists specifically because the first three features left the router gaining nothing. The arm costs are spread $0 : 1 : 3$ deliberately: with costs clustered the frontier collapses to a point and the whole allocation problem is vacuous, a lesson inherited intact from the capstone’s water-filling. The answer model is a softmax over prototypes, so it can speak to how evidence moves an answer posterior and cannot speak to generation quality, instruction-following, or anything about a real language model’s behavior under a longer context.