Paper deep dive
Pandora's AI Model Routing Box: Efficient Allocation with Costly Value Estimation
Adam Fisch, Shubhendu Trivedi, Fantine Huot, William W. Cohen, Michael Kaisers, Mirella Lapata, Kate Larson, Jacob Eisenstein
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 94%
Last extracted: 8/25/2026, 6:37:40 AM
Summary
This paper introduces 'Pandora's Router' and 'Pandora's Bidder', frameworks for allocating AI queries to specialized models by treating value estimation as a costly inspection problem analogous to the classical Pandora's Box problem. The centralized Router uses closed-form value-of-information expressions under a Gaussian signal model to decide whether to query expensive, accurate estimators or rely on cheap, noisy ones. The decentralized Bidder allows specialists to independently assess their value before accepting a query. Experiments across mathematical reasoning, retrieval-augmented generation, and multi-LLM benchmarks demonstrate that these methods achieve routing quality comparable to exhaustive estimation while significantly reducing computational costs.
Entities (9)
Relation Signals (5)
Adam Fisch → affiliatedwith → Google DeepMind
confidence 95% · Adam Fisch... Google DeepMind
Pandora's Router → solves → Pandora's Box
confidence 95% · We formalize this tradeoff as an instance of Pandora's Box... We call the centralized policy Pandora's Router.
Pandora's Router → evaluatedon → EmbedLLM
confidence 90% · Experiments across three domains---a standard multi-LLM benchmark... show that Pandora's Router matches the routing quality
Pandora's Router → evaluatedon → MATH
confidence 90% · Experiments across three domains... LLMs with variable inference-time reasoning... evaluate on a corpus... spanning MATH
Pandora's Bidder → extends → Pandora's Router
confidence 90% · We extend this to a decentralized setting, Pandora's Bidder
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Heterogeneous AI systems composed of multiple models, architectures, harnesses, or inference-time settings can improve quality and efficiency by routing queries to the specialist who can answer most effectively at the lowest cost. Routing requires estimating each specialist's expected return, but this value estimation has a cost. Cheap estimators (e.g., embedding-based predictors) are fast but noisy, while accurate estimators (e.g., fine-tuned models with access to retrieval results or partial reasoning traces) are expensive. We formalize this tradeoff as an instance of Pandora's Box, the classical problem of optimal search with costly inspection. Under a Gaussian signal model, the resulting policies have closed-form value-of-information expressions that determine, for each specialist and input, whether refining the value estimate is worth its cost. We call the centralized policy Pandora's Router. We extend this to a decentralized setting, Pandora's Bidder, where specialists independently decide whether to invest in self-assessment before accepting an offered price to claim a query. Experiments across three domains---a standard multi-LLM benchmark, retrieval-augmented specialists, and LLMs with variable inference-time reasoning---show that Pandora's Router matches the routing quality of exhaustive estimation, while querying the expensive estimator far less often. In the decentralized setting, value-of-information reasoning improves allocative efficiency when competing estimates are accurate; when competing estimates are noisy, however, it can increase the strategic specialist's utility at the expense of others.
Tags
Links
- Source: https://arxiv.org/abs/2608.20316v2
- Canonical: https://arxiv.org/abs/2608.20316v2
Trouble viewing inline? Open PDF directly →
Full Text
93,559 characters extracted from source content.
Expand or collapse full text
Pandora’s AI Model Routing Box: Efficient Allocation with Costly Value Estimation Adam Fisch∗, Shubhendu Trivedi, Fantine Huot, William W. Cohen, Michael Kaisers, Mirella Lapata, Kate Larson, Jacob Eisenstein∗ Google DeepMind Abstract Heterogeneous AI systems composed of multiple models, architectures, harnesses, or inference-time settings can improve quality and efficiency by routing queries to the specialist who can answer most effectively at the lowest cost. Routing requires estimating each specialist’s expected return, but this value estimation has a cost. Cheap estimators (e.g., embedding-based predictors) are fast but noisy, while accurate estimators (e.g., fine-tuned models with access to retrieval results or partial reasoning traces) are expensive. We formalize this tradeoff as an instance of Pandora’s Box, the classical problem of optimal search with costly inspection. Under a Gaussian signal model, the resulting policies have closed-form value-of-information expressions that determine, for each specialist and input, whether refining the value estimate is worth its cost. We call the centralized policy Pandora’s Router. We extend this to a decentralized setting, Pandora’s Bidder, where specialists independently decide whether to invest in self-assessment before accepting an offered price to claim a query. Experiments across three domains—a standard multi-LLM benchmark, retrieval-augmented specialists, and LLMs with variable inference-time reasoning—show that Pandora’s Router matches the routing quality of exhaustive estimation, while querying the expensive estimator far less often. In the decentralized setting, value-of-information reasoning improves allocative efficiency when competing estimates are accurate; when competing estimates are noisy, however, it can increase the strategic specialist’s utility at the expense of others. 1 Introduction AI model providers now often offer heterogeneous model families spanning a wide range of costs and capabilities: small and fast models for simple prompts, large and expensive ones for complex tasks, and augmented variants with tools, retrieval, or extended reasoning for more specialized tasks. This raises the question of how to allocate each input to the model best suited for it, for a given level of cost sensitivity. This is the routing problem, and a growing body of work addresses it by estimating each model’s expected return on the input and selecting the maximizer (24; 43; 13). But value estimation is neither free nor particularly easy. An embedding-based predictor is cheap but noisy; a fine-tuned scoring model is more accurate but more expensive; and computing partial solutions, executing tool calls, or running retrieval pipelines can be more expensive still. The routing decision itself thus involves a cost-accuracy tradeoff, which is typically ignored. We explore this tradeoff, asking: when is it worth paying for a better value estimate? The question has a clean analogy to the Pandora’s Box problem from search theory (47). Pandora is presented with M boxes, each with a hidden value which is known to her only in distribution. For a cost cmc_m she can open any box m and observe its value. At any point, she can stop searching and claim the best value seen thus far. Her goal is to maximize the difference between the value obtained minus the costs paid. 47 showed that the optimal policy has a remarkably simple structure, based on computing, for each box, its reservation price—the outside-option value at which the expected benefit of opening the box balances out the cost of opening it. Once these prices are calculated, Pandora opens the boxes in descending order of their reservation prices, stopping when she has found a value that exceeds the maximum of the reservation prices of the remaining unopened boxes. In this paper, we cast routing with costly value estimation as an instance of Pandora’s Box. Here, each specialist can be viewed as a box. The router always has access to a cheap value estimate fm(x)f_m(x), and can optionally pay cmc_m to query a more accurate but costly estimate gm(x)g_m(x); i.e., pay to "open the box", and gain more information about the quality of specialist m. The question of which estimates to compute, and when to stop computing and commit to a specialist, is the same as Pandora’s problem. Under a Gaussian signal model for the relationship between f and g, the reservation prices and the associated value-of-information expressions have closed forms. To allow Pandora to select a box without making any queries to g, we consider the non-obligatory variant of the Pandora’s Box problem, in which she can select a box that she has not opened (10; 2). Next, we consider the generalization from routing to decentralized forms of prompt allocation. In a routing system, a single centralized router controls all value estimation. In practice, however, the specialists themselves may be better positioned to estimate their own value. For example, a retrieval-augmented specialist has access to its own corpus, and can measure how relevant it is to the query; a math specialist can start to reason about or plan what computations will be required; a domain expert can know its own performance on internal benchmarks. None of these resources need be available to the router, and in some scenarios, specialists might even want to conceal information such as whether there are matches to a query in a private retrieval corpus. With this in mind, we extend the concept of value estimation for routing, to value estimation for bidding, where decentralized agents learn how to leverage costly value estimation when claiming queries, in a way that maximizes their profit. Concretely, we propose Pandora’s Bidder: each specialist faces a posted price—the current best competing offer—and must decide whether to invest in a more accurate self-assessment before claiming the query. This corresponds to a single stage of the ascending-price mechanism with costly preference elicitation studied by 38; analyzing this simple setting isolates core components of decentralized prompt allocation under private value estimation with profit incentives. Core contributions of this work As AI systems with diverse capabilities proliferate, reasoning about the economics of model selection becomes increasingly relevant. To our knowledge, this is the first paper to explicitly connect model routing with the classical Pandora’s Box problem from economics and operations research. Specifically, this paper makes three main contributions: • We formalize model routing with costly value estimation as an instance of Pandora’s Box with non-obligatory inspection (10), yielding a reservation-price-based policy. Under a Gaussian signal model, this policy has a closed form that is straightforward to compute (§4). • We extend to a decentralized setting where specialists use value-of-information reasoning to decide whether to refine their self-assessments before accepting a posted price (§5). • We evaluate both frameworks (see Figure 1) across three domains: a multi-LLM routing benchmark (EmbedLLM), retrieval-augmented specialists for factoid QA, and inference-time computation for mathematical reasoning. In each setting, we find that both Pandora’s Router and Pandora’s Bidder are able to gracefully trade-off expensive and cheap estimates to achieve strong allocative performance relative to baselines across a range of estimation costs. 1Prompt x Find the remainder when 71037^103 is divided by 1313. 2Cheap screeningSpecialist 11f1(x)f_1(x): modest priorSpecialist 22f2(x)f_2(x): promising prior⋮ MMfM(x)f_M(x): modest prior All specialists get an initial cheap, noisy value estimate fm(x)f_m(x). 3Reservation prices Solve for the reservation price umrsvu_m^rsv, g|f[(gm(x)−umrsv)+]=cm _g|f\! [(g_m(x)-u_m^rsv)^+ ]=c_m, where • gm(x)g_m(x) is a more accurate but costly value estimate; • cmc_m is the cost of querying gmg_m. Pandora estimates the value of information for running each expensive value estimator gmg_m. 4AllocationPandora’s RouterCentralized policy Inspect specialists gm(x)g_m(x) in reservation-price order, stopping when no remaining query is worth its cost. Choose the maximizer of the observed gmg_m. Pandora’s BidderDecentralized policy The high bidder is selected in an auction. Each specialist refines its own value estimate only when the market price makes inspection worthwhile. The same principle yields both a centralized and decentralized policy. Figure 1: Overview of the Pandora framework. The system balances cheap screening and costly reasoning for routing. (1) A concrete prompt x is received. (2) Multiple specialists m∈1,…,Mm∈\1,…,M\ generate cheap, noisy value estimates fm(x)f_m(x). (3) The system computes reservation prices that quantify the expected value-of-information for querying a more costly and accurate value estimate gm(x)g_m(x), e.g., by running the specialist for a few reasoning tokens and checking if it is on the right track. (4) This unified principle supports allocation by centralized routing and decentralized auctions. 2 Setting We begin with a more precise introduction to the problem of efficient allocation with costly value estimation. Suppose that a router must assign each prompt to the best specialist, but estimating specialist quality is itself costly. We assume that each specialist m has a cheap value estimate fm(x)f_m(x) by default, while a more accurate but expensive estimate gm(x)g_m(x) can be queried selectively; we make these estimators concrete in Section 2.1. The goal is to maximize the expected reward of the selected specialist minus total estimation cost by deciding which expensive estimates gm(x)g_m(x) are worth computing. Formally, let X∈X be a random input prompt, and let x denote a realization. Conditional on the input X=xX=x, specialist m samples an output Ym∼Pm(⋅∣x)Y_m P_m(· x), Ym∈Y_m , and receives a cost-adjusted reward Rm(x,Ym)R_m(x,Y_m). For notational convenience, we will write the cost-adjusted reward Rm(x,Ym)R_m(x,Y_m) simply as RmR_m. The reward may combine, for example, the graded quality of the output with the cost of producing it (which could be the inference cost, or API fees for tools called), and is a random variable through both the randomness of YmY_m and any noise in the evaluation itself (e.g., from a human annotator). The input-specific oracle routing problem is to select the specialist that maximizes the conditional expected reward, that is, m^(x)∈argmaxmρm(x), m(x)∈ _m _m(x), with ρm(x):=[Rm∣X=x]. _m(x):=E[R_m X=x]. However, since the true reward is typically not available at routing time, the router must instead apply a value estimator to predict it, and then pick the best specialist based on their estimated values. Of course, there are many ways to do value estimation, and these estimators may themselves incur widely varying computational costs. At one extreme, a cheap value estimate could just be a constant, such as the average cost-adjusted reward on a calibration set (and not conditional on x). At the other extreme, we might actually materialize the candidate output Ym=yY_m=y for each model m, and then score y with an estimate of RmR_m (with an LLM-based auto-rater for example, if RmR_m involves a human judgment), or even observe RmR_m directly (if the reward is a known function of y). In practice, a straightforward approach to value estimation is to apply a trained model to the text of the prompt, or its embedding (24; 32; 37, inter alia). These estimators can move along a cost-accuracy curve depending on their complexity, or depending on any other auxiliary input information that is gathered by the estimator (e.g., by invoking tools or computing partial solutions, such as plans (50; 31)). We denote the additional information revealed from such a costly inspection of specialist m by ZmZ_m. Note that the costly information ZmZ_m need not be private to the specialist—it may simply reflect additional computation applied to the prompt, such as from using a more expressive encoder. Under this view, the routing process separates naturally into two phases: gathering information and making a final choice. We consider a minimal setting in which there are just two available value estimators: fmf_m (cheap) and gmg_m (costly), with costs cf<cgc_f<c_g, respectively. For simplicity, we set cf=0c_f=0, so that fmf_m is always computed. We will use uppercase letters for the corresponding random variables. Let Fm=fm(X)F_m=f_m(X) be the cheap estimate for the specialist m,m, and let =(F1,…,FM).F=(F_1,…,F_M). Inspecting specialist m reveals the costly information ZmZ_m needed to compute the refined estimate Gm=gm(X,Zm)G_m=g_m(X,Z_m); a process we simply call querying gmg_m. We denote the cost of this process as cgc_g. For the additional cost of GmG_m to be justified, it should be more accurate, in the sense that on calibration data we have [(Rm−Gm)2]<[(Rm−Fm)2].E[(R_m-G_m)^2]<E[(R_m-F_m)^2]. The router must dynamically decide which specialists to inspect (by querying gmg_m) in order to maximize the expected reward of the final assignment, minus the total cost of the realized GmG_m estimates. To make things more concrete before presenting our efficient routing algorithms, we now describe three real-world domains where the two-tier estimation between fmf_m versus gmg_m arises organically, each with a qualitatively different source of costly information that is useful for deciding the best allocation. 2.1 Experimental domains and value estimators We explore several empirical settings, each featuring different types of specialists and value estimators. In all cases, the cheap estimator f embeds the prompt with a pretrained encoder, retrieves the k nearest prompts from a calibration set (measured by cosine similarity in embedding space), and returns the average reward of the retrieved neighbors as the value estimate. The costly estimator is then constructed by fine-tuning a small language model encoder to predict the reward from a tailored, domain-specific input context. We describe these below. Note that in each domain, we partition the data into three splits: training (for fitting value estimators), calibration (for estimating the value-of-information model parameters in Sections 4 and 5), and test. Table 1 reports the MSE of each estimator on held-out calibration data. Additional dataset and implementation details are included in Appendix B. MATH: Inference-time scaling in mathematical reasoning tasks. In inference-time scaling, extended reasoning improves accuracy on hard problems but increases latency and cost. The costly estimator g treats the early tokens of a reasoning trace as private information: it receives the prompt along with the first t tokens of a model’s chain-of-thought, effectively peeking at a partial solution to judge whether the model’s reasoning looks promising before committing to it. This is passed with the prompt to a small language model (Gemini 2.5 Flash-Lite) with a regression loss to predict the specialist’s reward directly from the prompt text. The router chooses between Gemma3-4B (16) (low-cost) and Gemini-3.1-Flash-Lite (18) (cost 0.660.66, so that Rm=Ym is correct−0.66R_m=1\Y_m is correct\-0.66). This high cost is chosen so that it is beneficial to route to Gemini only when confident that it can answer correctly and Gemma cannot. We evaluate on a corpus of 16,512 mathematical problems spanning MATH (22), Omni-Math (15), AIME (34; 20), and HMMT (19). RAG: Retrieval-augmented generation with specialized corpora. In retrieval-augmented generation (30, RAG;), retrieval results can improve answer quality but incur costs from retrieval computation, longer contexts, and potentially licensing fees for specialized corpora. The costly estimator g runs retrieval and passes the results alongside the prompt to a language model fine-tuned with a regression loss, as in Math. Notably, the retrieval results themselves do carry some signal: if the retrieved documents are relevant to the query, the specialist is more likely to answer correctly, whereas irrelevant retrievals may hurt. The router selects between three specialists: a low-cost model with no retrieval (the costly estimator g here is just the more expensive LLM-based estimator), a Wikipedia RAG model, and a PubMed RAG model, where the RAG models each incur a cost of 0.050.05 (again, subtracted from correctness in RmR_m). Prompts are a mixture of general-knowledge factoid questions and biomedical questions, following the same experimental setup as 12. EmbedLLM: Large-scale language model selection. Finally, we consider EmbedLLM (52), a standard routing benchmark without auxiliary information, where the value of costly estimation comes purely from spending more compute to better distinguish among a large pool of candidates. As above, g is a fine-tuned language model; even without private information, this is more expensive at inference time than the KNN baseline, but is significantly more accurate than the KNN baseline, since the model can learn prompt-level features that the embedding space misses. EmbedLLM incorporates more than 100 open-weights models as routing targets; following 26, we assign each model a cost proportional to its parameter count. Queries are drawn from standard benchmarks like MMLU (21) and GSM8K (5). Setting Estimator MSE cg/cfc_g/c_f Description MATH f: KNN .154.154 5.85.8 k-nearest neighbors on prompt embeddings g: SFT-CoT-2020 .096.096 Fine-tuned transformer on prompt + first 2020 tokens of the model’s chain-of-thought (CoT) reasoning trace RAG f: KNN .175.175 >7000>7000 k-nearest neighbors on prompt embeddings g: SFT-retrievals .109.109 Fine-tuned transformer on prompt + retrieval results EmbedLLM f: KNN .266.266 1.61.6 k-nearest neighbors on prompt embeddings g: SFT-prompt .198.198 Fine-tuned transformer on prompt Table 1: Value estimators across experimental domains. The cheap estimator f is always computed; the costly estimator g is queried selectively. The mean-squared error (MSE) is measured on a held-out calibration set. The cost ratios cg/cfc_g/c_f are discussed in Section 2.2 and derived in Section D.3. While the MATH and RAG settings have only two and three target models to choose from respectively, both routing and efficient value estimation are still challenging and important problems even when the number of target models is small. The strongest frontier models can be up to five times as expensive as cheaper models from the same provider,11 1 Compare, e.g. Fable 5 vs Sonnet 5 at https://platform.claude.com/docs/en/about-claude/pricing (retrieved August 13, 2026). so there are strong financial incentives to reserve the most expensive models for situations where they yield meaningful improvements. Similarly, as shown in Table 1, more computationally-intensive value estimation strategies can yield significant improvements, but at high cost. The difficulty of the information acquisition problem depends not primarily on the number of targets, but on how discriminable the options are: we can have many options, but this doesn’t matter if there is always a clear best box to use based on cheap signals alone; or we can have a few boxes that are hard to choose between, and it is expensive to know more. We picked experimental settings that try to cover key aspects of each of these considerations. 2.2 Value estimator costs To estimate monetary costs for the value estimators in Table 1, we use prices from https://ai.google.dev/gemini-api/docs/pricing (retrieved August 1, 2026), because it offers a single source of prices for LLM inference, embedding, and retrieval. The resulting estimates are meant only to show that approaches to value estimation can incur vastly different costs; we do not claim that these specific prices are optimal or even typical. Because the cost-accuracy tradeoff is a user characteristic rather than an objectively-measurable property of the domain or method, we focus on the ratio between the prices of f and g. Please see Section D.3 for the derivation of these ratios. 3 Preliminaries: The Pandora’s Box Problem We begin by briefly reviewing the Pandora’s Box problem (47), which we will connect to model routing and model bidding in the following sections. In the Pandora’s Box problem, a decision-maker (i.e., Pandora) is presented with M options, called “boxes”, each with an unknown reward (but with known distribution). For a price she can inspect any box to observe its reward, and at any time she can terminate the search and take the best reward that she has observed. The optimal policy depends on a mathematical object called the reservation price, which is a single scalar that encodes the value of inspecting a box. The reservation prices alone can be used to construct a simple, but optimal, priority-based search. Notably, this optimal search must be sequential, as the information acquired so far will help determine whether the remaining inspections still justify their cost. To gain intuition for the reservation price, suppose Pandora has already found a box with value v for the input x, and must decide whether to open box m, whose hidden value is yet unknown, but known to be drawn from a distribution Pm(⋅∣x)P_m(· x). If Pandora opens the box and finds Vm>vV_m>v, she takes VmV_m; otherwise, if Vm<vV_m<v, she keeps v. Given an inspection cost of cmc_m, her expected payoff at this step from opening the box is therefore [maxv,Vm]−cmE[ \v,V_m\]-c_m; the payoff for not opening m is v. The net value is [(Vm−v)+]−cmE[(V_m-v)^+]-c_m, which is positive when the expected upside exceeds the cost. The reservation price umrsvu^rsv_m, defined by 47, is the outside-option value at which this net value is exactly zero: [(Vm−umrsv)+]=cm.E[(V_m-u^rsv_m)^+]=c_m. (1) When the current best value v exceeds umrsvu^rsv_m, the cost of opening box m outweighs the expected gain. The resulting decision rule is therefore quite simple: we open box m if v<umrsvv<u^rsv_m, and skip it otherwise. The full selection strategy, however, requires more than a single “open-or-skip” decision. Pandora must sequence her inspections, since each opened box updates the current best value v, which in turn changes. She may also skip inspection entirely: if the prior PmP_m strongly favors box m, she can save cmc_m and commit sight-unseen. These choices define the two classical variants of the problem. Pandora-OI (obligatory inspection). In the obligatory-inspection variant, Pandora must open every box she eventually selects. This is the classical Pandora’s Box setting, and admits a simple solution. Specifically, 47 showed that reservation prices alone determine the optimal policy: initialize a best-seen value v∗:=−∞v^*:=-∞, open boxes in descending order of umrsvu^rsv_m, and stop as soon as v∗v^* exceeds the highest remaining reservation price. The box that yielded v∗v^* is selected. The remaining boxes can be safely ignored because v∗>umrsvv^*>u^rsv_m implies [(Vm−v∗)+]<cmE[(V_m-v^*)^+]<c_m, by the definition of umrsvu^rsv_m. Pandora-NI (non-obligatory inspection). When inspection is non-obligatory, Pandora may select any unopened box, committing to it without paying the inspection cost, but accepting the risk that its realized value may disappoint (10). The optimal adaptive policy for this variant is NP-hard (14), so we use a tractable restriction to committing policies (2). A committing policy designates a single box m as “held out”: this box will not be opened, but may be selected as the final choice. The remaining M−1M-1 boxes are searched via Pandora-OI, with the held-out box providing the initial outside option.22 2 The value of the best committing policy that holds out multiple boxes cannot exceed that of the best single-box policy (2), so it suffices to evaluate all M single-holdout policies, in addition to the obligatory inspection policy (no holdouts). These M + 1 policies are compared by simulating their performance via MC sampling. To use an unopened box as an outside option, we need to assign it a deterministic value. We use the backup price umbackupu^backup_m, which like the reservation price in Equation 1, is defined as the solution to: [(umbackup−Vm)+]=cm.E[(u^backup_m-V_m)^+]=c_m. (2) Note that the backup price is related to, but different from, the reservation price. The reservation price is the outside option that makes Pandora indifferent to inspecting a box or skipping it; the backup price is the outside option that makes Pandora indifferent to committing to the sealed box sight-unseen versus paying to inspect it. Any opened box must exceed this threshold to justify discarding the sealed option. The relationship between the backup price and the reservation price depends on the expected shortfall below the mean of the held-out box, specifically, umbackup≤umrsvu^backup_m≤ u^rsv_m if and only if cm≤[([Vm]−Vm)+]c_m [(E[V_m]-V_m)^+]. For costs exceeding this threshold (very expensive boxes), the inequality reverses. The algorithm proceeds as follows. For each candidate holdout m∈0,1,…,Mm∈\0,1,…,M\, define the expected payoff of the committing policy that reserves box m: νm=[Vm^−∑j∈Omcj], _m=E\! [V_ m- _j∈ O_mc_j ], (3) where Vm^V_ m is the value of the (random) box that the committing policy selects, and OmO_m is the (random) set of boxes opened by Pandora-OI on 1,…,M∖m\1,…,M\ \m\ with initial outside option v∗=umbackupv^*=u^backup_m. The case m=0m=0 corresponds to running Pandora-OI on all M boxes with no holdout (u0backup=−∞u^backup_0=-∞). Because the held-out box is unobserved, we estimate νm _m via Monte Carlo (MC) samples V~m∼Pm(⋅∣x) V_m P_m(· x); we denote the MC estimate ν^m ν_m. We select m∗m^* that maximizes ν^m ν_m, using S=100S=100 samples.33 3 Pilot experiments showed similar results with S=30S=30, with performance degrading significantly only at S=10S=10. We chose S=100S=100 because the overall computational costs of this operation are cheap relative to value estimation itself. At test time, we run Pandora-OI on 1,…,M∖m∗\1,…,M\ \m^*\ with initial value v∗=um∗backupv^*=u^backup_m^*, opening the actual boxes. We default to m∗m^* if we open no boxes or if no realized value clears um∗backupu_m^*^backup; otherwise, we select the best opened box.44 4 As a small technical detail, 2 use the expected value of the heldout box as the initial value v∗v^*, rather than our choice of the backup price, which, empirically, we found to perform slightly better. See Section D.5. 4 Pandora’s Router A value-based router tries to select the specialist with the highest expected return. We connect routing to Pandora’s Box by treating each specialist as a box and the costly value estimate as the value revealed by opening that box. One subtlety is that the box value is not the realized downstream reward RmR_m itself. The router never observes RmR_m before choosing a specialist. The relevant decision value is thus the expected reward conditional on the information the router can acquire. In practice, our learned costly estimate GmG_m is a learned plug-in approximation to this posterior decision value, and our proxy objective is to find the specialist for which GmG_m is largest. In Proposition 1 and Corollary 1 (Appendix A), we show that this is equivalent in expectation to optimizing RmR_m, assuming conditional independence. Gaussian signal model. The Pandora’s Box algorithm requires an estimate of the distribution of the box values. We model the distribution of GmG_m conditional on the cheap estimates as Gm∣=∼(μm,σm2),μm=hm()G_m =f\; \;N\! ( _m,\; _m^2 ), _m=h_m(f) (4) where f collects the realized cheap estimates (f1(x),…,fM(x))(f_1(x),…,f_M(x)) for all specialists and μm _m is a function hm(⋅)h_m(·) of this vector, where hmh_m and σm2 _m^2 are estimated on calibration data. The choice of hmh_m is flexible; we explore both gradient boosted decision trees and linear regression depending on the domain (see Appendix C). μm _m captures the predictable component of gmg_m given f, and σm _m captures the residual uncertainty, which is approximated as normally distributed per Equation 4. Under this model, the value of opening box m against an outside option v is the expectation of a Gaussian censored at v: [(Gm−v)+]=(μm−v)Φ(αm)+σmϕ(αm),E[(G_m-v)^+]=( _m-v)\, ( _m)+ _m\,φ( _m), (5) with αm=(μm−v)/σm _m=( _m-v)/ _m, and Φ and ϕφ the standard normal CDF and PDF. The reservation price umrsvu^rsv_m satisfies [(Gm−umrsv)+]=cmE[(G_m-u^rsv_m)^+]=c_m and can be obtained by simple root-finding on Equation 5. Of course, while convenient, the Gaussian model is only an approximation, and real box values are rarely strictly Gaussian. We also explore a non-Gaussian signal model in Section D.6 (for an alternative model based on Gaussian processes, see 48), but find that while it is possible to improve fit to the empirical distribution, it does not yield an improvement in overall routing success and inspection cost. An extension for handling correlated values. In routing, the Pandora-OI and Pandora-NI policies described above must contend with an additional complication: the hidden values of the boxes are not independent. For some difficult prompts, all specialist scores GmG_m will tend to fall below the prediction μm _m; for easy prompts, they will cluster above it. This correlation is particularly strong in the EmbedLLM domain, where there are >100>100 routing targets, some of which are extremely similar (e.g., different fine-tunings of the same base model). To handle this, we propose a heuristic approximation that recomputes reservation prices at each step of the sequential policy (inspired by 17, and also similar to the Gaussian process updates in 48). On calibration data we estimate the parameters of a multivariate Gaussian model ∼(μ,Σ).G (μ, ). After each box is opened, we condition on the observed values observedG_observed and compute P(unobserved∣,observed)P(G_unobserved ,G_observed) via the standard multivariate Gaussian posterior. We then make a mean-field approximation to this posterior, yielding updated marginal distributions for each remaining box, from which we recompute the reservation prices. The sequential policy then proceeds as before with these new parameters. Algorithm 1 Pandora’s Router (with non-obligatory inspection) 1: Cheap value estimates =(f1(x),…,fM(x))f=(f_1(x),…,f_M(x)), multi-variate Gaussian signal model parameters (h,Σ)(h, ), costs cm\c_m\, number of Monte Carlo samples S. 2: Compute predicted means μm←h()m _m← h(f)_m for all m 3: Compute reservation prices umrsvu^rsv_m via root-finding on Equation 1 4: Compute backup prices umbackupu^backup_m for all m via root-finding on Equation 2 5: for each candidate held-out box m=0,1,…,Mm=0,1,…,M do 6: // Note: m=0m=0 corresponds to Pandora-OI on 1,…,M\1,…,M\ with u0backup=−∞.u_0^backup=-∞. 7: // ν^m ν_m is an MC estimate of the expected committing-policy payoff νm _m (Equation 3). 8: Estimate ν^m ν_m by running Pandora-OI on 1,…,M∖m\1,…,M\ \m\ with initial value v∗=umbackupv^*=u^backup_m, averaged over S samples of realized ~=(G~1,…,G~M) G=( G_1,…, G_M) where ~∼(μ,Σ) G (μ, ). 9: Select held-out box m∗=argmaxmν^m^*= _m ν_m 10: Run Pandora-OI on 1,…,M∖m∗\1,…,M\ \m^*\ with initial value v∗=um∗backupv^*=u^backup_m^*, using actual g-queries 11: if no boxes were opened or the best realized value ≤um∗backup≤ u^backup_m^* then 12: return sealed holdout m∗m^* 13: else 14: return the best opened box Experimental setup. We evaluate Pandora’s Router on the three domains described in §2.1 (MATH, RAG, and EmbedLLM), and compare with the following methods: • f-only: Route using the cheap estimator fmf_m only (never opening any box). • g-always: Route using the expensive estimator gmg_m only (always opening all boxes). • Top-2: Always queries gmg_m for the two models with highest fmf_m (open the two expected best boxes). • Coin Flip: Query gmg_m with probability 12 12; route to the maximum observed (randomly open boxes). We also evaluate two ablations that use the same inspection budget selected by Pandora’s Router, but use different methods to decide which boxes to open (that is, instead of reservation prices). Specifically, we first run Pandora’s Router to count how many times, NprN_pr, in total gmg_m was queried over a test set (in hindsight), and then reallocate those NprN_pr inspections according to the following rules: • Random-prN_ pr: A simple control where gmg_m is randomly queried up to NprN_pr times over the entire test set; for every example we route to the best candidate among the randomly inspected options. We route to argmaxmfm _mf_m as a default if no inspections were made for that example. • Margin-prN_ pr: An uncertainty-based heuristic that queries gmg_m for specialists whose f-scores are close to being best: letting m′=argmaxjfjm = _jf_j, if fm′−fmf_m -f_m is small, we inspect both gmg_m and gm′g_m . Again, we inspect gmg_m for at most NprN_pr specialists over the entire test set, and route to m′m as a default. The primary metric is regret ++ inspection cost: routing regret (the gap between the selected specialist’s true, realized reward and the oracle best specialist in hindsight) plus the total cost of all g-queries. Although our method generalizes to heterogeneous costs, for simplicity we use a uniform inspection cost cm=cgc_m=c_g ∀m∈1,…,M∀ m∈\1,…,M\, and sweep cgc_g to trace out the cost versus performance frontier. Method MATH RAG EmbedLLM Regret Cost Total Regret Cost Total Regret Cost Total f-only 0.117 0.000 0.117 0.150 0.000 0.150 0.393 0.000 0.393 g-only 0.090 0.038 0.128 0.084 0.057 0.141 0.370 1.986 2.356 Top-22 0.090 0.038 0.128 0.107 0.038 0.146 0.402 0.036 0.438 Coin Flip 0.107 0.019 0.127 0.122 0.029 0.151 0.398 0.992 1.390 Random-NprN_pr 0.164 0.011 0.175 0.135 0.027 0.162 0.363 0.075 0.438 Margin-NprN_pr 0.094 0.011 0.105 0.101 0.027 0.128 0.314 0.075 0.389 Pandora’s Router 0.094 0.011 0.105 0.091 0.027 0.118 0.311 0.075 0.386 Table 2: Routing evaluation results averaged across query costs cgc_g. Lower is better on all metrics; the lowest average regret + cost measured per setting is bolded. See Section D.4 in the Appendix for a breakdown of results per cost level cgc_g, together with paired statistical significance tests. Results. Results for the full set of baselines are shown in Table 2 for all three datasets, averaging over all values of cgc_g (see Section D.4 for results per cgc_g; the values tested correspond to those in Figure 2). Pandora’s Router is reliably the best. The two inspection ablations, Margin-NprN_pr and Random-NprN_pr, borrow the query budget from Pandora’s Router, but achieve higher regret because they do not use the budget as effectively. Differences in particular between Margin-NprN_pr, which is the most competitive comparison, and Pandora’s Router at each specific cost level are shown in Figure 2 (for clarity in the figure, we compare Pandora’s Router with f-only, g-only, and the margin baseline). Pandora minimizes regret plus inspection cost at nearly all cost levels cgc_g, in all settings. When the cost of g is low, Pandora’s Router queries it for nearly every specialist, and all methods except f-only (which never queries g) perform similarly. As cgc_g increases, the g-always baseline continues to make a fixed number of queries regardless of cost, while f-only still never queries at all. Pandora’s Router interpolates between these extremes, querying g only when the value of information exceeds the cost. As a result, the total regret + inspection cost of Pandora’s Router tracks the lower envelope of the baselines across the full cgc_g range. 10−310^-310−210^-210−110^-19⋅10−29· 10^-20.10.10.110.110.120.120.130.13cgc_gRegret + Inspection CostMATH10−310^-310−210^-210−110^-10.10.10.150.150.20.2cgc_gRAG10−510^-510−410^-410−310^-310−210^-210−110^-10.380.380.40.40.420.420.440.44cgc_gEmbedLLM2 Figure 2: Routing performance on the MATH, RAG, and EmbedLLM domains for varying costs of querying g, with f=KNN3f=KNN_3. The ideal value estimation policy would minimize regret + inspection cost at every cost level. Pandora’s Router achieves near-minimal total cost across the full range of cgc_g (where cm=cgc_m=c_g for all m), querying g frequently when it is cheap and rarely when it is expensive. As a secondary analysis, Figure 6 in Section D.3 shows the cost-performance tradeoff offered by Pandora’s Router, in terms of monetary costs and routing regret. The costs are computed from the Gemini API prices described in Section 2.2. When cg=0.001c_g=0.001, we are in a setting in which users are eager to pay for queries that improve routing; here Pandora’s Router obtains regret that almost matches g-only, while incurring much lower inspection costs. When cg=0.1c_g=0.1, we are in a setting in which users are unwilling to pay for queries to g; here Pandora’s Router never queries g, and routing performance and cost match the f-only baseline. These tradeoffs are dynamically navigated by Pandora’s Router. Note that in the MATH experiment the aggregate results for Pandora’s Router and Margin-NprN_pr are nearly identical. Since there are only two routing targets, regret is determined largely by the decision about how many g values to query: with two queries, both methods always select the g-maximizer; with zero queries both methods almost always select the f-maximizer (except in rare cases where the reserve price ordering is different from the ordering of f). Because Margin-NprN_pr inherits the query budget (NprN_pr) from Pandora’s Router, it is unsurprising that its overall performance is very similar. 5 Pandora’s Bidder We now derive a simple but interesting extension of Pandora’s Router to a decentralized setting in which the specialists control their own value estimates, and use them to participate in a marketplace. Pandora’s Router assumes that a single decision-maker controls which boxes to open and which specialist to select. In many settings, however, the specialists themselves are better positioned to estimate their own value: a retrieval-augmented specialist has access to its own corpus, a math specialist can execute partial computations, and a domain expert may have proprietary benchmarks. None of these resources need be visible to a centralized router. Decentralization also has a number of practical advantages: new specialists can join without retraining the routing model, and the cost of value estimation is borne by the specialists rather than the platform. As an alternative to a centralized router, consider a market-based mechanism where each specialist can purchase the right to answer a query. We formalize this via a posted-price mechanism corresponding to a single stage of the ascending-price framework with costly preference elicitation studied by 38. We consider a leave-one-out setting with a single strategic specialist. A platform collects nonstrategic value estimates from M−1M-1 specialists and posts the best estimate as the price at which the remaining specialist can claim the query. The strategic specialist must then apply the same value-of-information (VoI) reasoning from Pandora’s Router to decide whether this price is worth accepting, and whether or not to pay to observe a refined estimate before making this decision. Concretely, for a given query x, the platform solicits GjG_j from each of the M−1M-1 nonstrategic specialists and sets the posted price as p=maxj≠mGjp= _j≠ mG_j. Note that the platform could incorporate a markup to extract profit, but here we simply use the best competing estimate. The strategic specialist m then faces a decision: accept the price (winning the right to answer the query, instead of the platform’s choice), or decline (in which case the platform routes to the specialist that set the price). Specialist m begins with only the cheap estimate, which yields a predicted mean μm(x)=h()m _m(x)=h(f)_m for GmG_m, as in Equation 4. The expected gain from paying cmc_m to observe GmG_m before responding to the price p is VoI(p)=[(Gm−p)+]−(μm−p)+.VoI(p)=E[(G_m-p)^+]-( _m-p)^+. (6) This is the difference in expected profit between deciding after observing GmG_m and deciding based only on μm _m. The structure mirrors the reservation price computation for Pandora’s Router in §4, but with the price p playing the role of the outside option. When p is low relative to μm _m, the specialist can confidently accept based on f alone; when p is high, the specialist can confidently decline. The value of information peaks when p is close to μm _m and the correct action is uncertain. The condition VoI(p)=cmVoI(p)=c_m defines an interval [plo,phi][p_lo,p_hi] within which it is worth paying for the refined estimate (38). Using the same Gaussian model as in Equations 4 and 5, the boundaries satisfy (μm−p)Φ(αm)+σmϕ(αm)=cm+(μm−p)+( _m-p)\, ( _m)+ _m\,φ( _m)=c_m+( _m-p)^+ (7) with αm=(μm−p)/σm _m=( _m-p)/ _m, and Φ and ϕφ the standard normal CDF and PDF. Like the reservation price, these values are obtained via standard root-finding techniques. The resulting bidding strategy pays cmc_m to observe GmG_m when plo≤p≤phip_lo≤ p≤ p_hi, accepting if Gm>pG_m>p. Outside this interval, refinement is not worth it: the specialist simply accepts if p<plop<p_lo and declines if p>phip>p_hi. 10−210^-210−110^-10.050.050.060.060.070.07Surplus RegretMATH10−210^-210−110^-10.080.080.10.10.120.12RAG10−510^-510−410^-410−310^-310−210^-210−110^-10.070.070.0750.0750.080.08EmbedLLM10−210^-210−110^-10.030.030.040.040.050.05cgc_gEfficiency Regret10−210^-210−110^-10.040.040.050.050.060.06cgc_g10−510^-510−410^-410−310^-310−210^-210−110^-10.050.050.060.060.070.07cgc_g7 Figure 3: Results for the posted-price auction across the three experimental domains for varying refinement cost cgc_g. The VoI-based bidding strategy interpolates between querying g when cheap and declining when expensive, while static baselines either over-invest or under-invest in refinement. Experimental setup. We evaluate Pandora’s Bidder in a leave-one-out setting across the three domains from Section 2.1. For each query, one specialist is designated as the strategic bidder; the remaining M−1M-1 specialists submit their g estimates nonstrategically, and the platform posts the best as the price via p=maxj≠mGjp= _j≠ mG_j. The strategic bidder then applies the VoI-based acceptance strategy above. We rotate the held-out specialist across all M models and report the average. As in the centralized routing experiments, we sweep over cgc_g to trace out the cost versus performance frontier.We measure two quantities: (1) specialist surplus, which is Rm−pR_m-p when the strategic specialist m accepts the price and 00 when it declines, as well as any incurred estimation costs; and (2) allocative efficiency, which is the true reward Rm^R_ m of the winning specialist (m if it accepts, otherwise the platform-chosen specialist), minus the m’s estimation costs. We exclude competitors’ estimation costs; by treating their g estimates as given, we isolate the contribution of the VoI-based policy. We compare against the gg-always baseline (the bidder always pays for g) and the ff-only baseline (the bidder always decides based on f). For both metrics, we measure the regret versus an oracle that knows GmG_m for free. Results. Figure 3 plots allocative efficiency and bidder surplus for different cgc_g. Pandora’s Bidder closely tracks the lower envelope of the regret of the two baselines across the full cgc_g range. When cgc_g is low, the bidder frequently refines its estimate, winning queries where it holds a true advantage. As cgc_g increases, the bidder selectively defaults to the cheap estimate or declines the price, avoiding the cost collapse of the g-always baseline. The f-only baseline, conversely, leaves efficiency on the table at low costs by never investing in refinement. With decentralization, however, maximizing local surplus does not always lead to better overall allocative efficiency. For example, when the price is inaccurate (set using the cheap estimate f rather than g for the M−1M-1 competitors) the strategic bidder captures higher surplus at the cost of overall allocative efficiency (see additional results in Section D.2). Overpriced queries offer insufficient expected profit to incentivize the bidder; declining them protects the bidder’s surplus but assigns the input to a less capable specialist. This tension is absent in the centralized setting, where the router internalizes all costs and optimizes global welfare directly. Extending Pandora’s Bidder to multi-round ascending-price mechanisms (38) may recover some of this efficiency loss. 6 Related Work Information value theory. Many scenarios require agents to decide whether to spend effort learning more about the world or to exploit what they already know. An early formalization of this decision problem is information value theory (23), which provides the general framework for Equations (1) and (6). Bayesian Q Learning is an application of information value theory that quantifies the downstream value of actions that increase the precision of the agent’s beliefs about state-action values (8). While similar in spirit, the core ideas of Bayesian Q Learning cannot easily be applied to model routing because state-action pairs cannot be visited more than once; in this work, however, we show that the form of the model routing decision problem admits specialized efficient algorithms based on Pandora’s Box (formalized as Pandora’s Router in Section 4). LLM routing. Routing user inputs within a collection of language models has been proposed as a way to reduce costs while maintaining high accuracy (4) and to leverage complementary capabilities of heterogenous models (43). There are now several routing benchmarks (24; 13, e.g.,), of which we use EmbedLLM (52). Most routing approaches require predicting the answer quality for each model on a given input, using pointwise (26) or pairwise (37) data. In all of this prior work, value estimation is treated as a cost-free operation with a fixed error profile. Our contribution in Pandora’s Router in Section 4 is to treat value estimation as a decision involving a cost-performance tradeoff of its own. Adaptive retrieval and tool use. Closely related to routing is the decision of whether to invoke external tools or retrievers. Adaptive RAG frameworks (25) dynamically adjust retrieval strategies depending on the query complexity to save computational costs. Similarly, recent evaluations of adaptive retrieval (35) highlight the tension between using internal LLM uncertainty estimation vs. lightweight external heuristics. We formalize this exact tradeoff—that is, deciding whether to spend computational power on self-assessment or tool-planning—through a value-of-information perspective that is both theoretically principled and empirically effective. Pandora’s Box and optimal search. Prior work on sequential search with costly inspection is reviewed in §3. The Pandora’s Box problem is also used as a motivating framework for LLM reasoning about cost-uncertainty tradeoffs by 9, as well as by 48 for cost-aware Bayesian optimization in which the reservation price (for obligatory inspection) is used to drive an acquisition function. In contrast, we instantiate the non-obligatory variant of the Pandora’s Box algorithm to drive LLM routing specifically, and we derive closed-form value-of-information expressions under a practical Gaussian signal model that make our algorithm simple to implement and execute. On a more technical level, we focus on a committing policy approximation to the non-obligatory inspection variant of the Pandora’s Box problem (2). Another class of approximations uses randomization (1; 42), which we may consider in future work. Decentralized AI and multi-agent systems. Decentralized coordination through market mechanisms has a long history in AI, from ContractNet (7), which introduced negotiation-based task allocation, to AgentNet (49), which builds dynamic graph topologies between LLM agents. Our work on Pandora’s Bidder in Section 5 is most informed by auction-based approaches, which were applied to ContractNet by 40 and linked to decentralized RL by 3. The combination of auctions with cost-accuracy tradeoffs in value estimation is generally intractable, but 38 offers empirically-validated heuristics. For a survey on the problem of delegation between AI components, see 46. Auctions and related mechanisms have received increasing attention as an approach for decentralized orchestration of LLMs (11; 6; 51; 45; 36), but these frameworks generally assume that agents know their own valuations a priori, while we describe how agents can reason about costly value estimation when they are unknown. 7 Conclusion Value-based routing is a natural approach to optimizing the allocation of computing power to AI model inputs. We have argued that value estimation itself brings cost-accuracy tradeoffs, and we show how the Pandora’s Box problem offers a unified framework for value-based routing under heterogeneous value estimators. We also extend the framework to a decentralized setting, in which specialists reason about the value of information in an auction-based allocation mechanism. Limitations. Several limitations suggest promising directions for future work. The Gaussian signal model, while tractable, may not capture the heavy tails or multimodality present in some domains (see Section D.6 for coverage statistics and a pilot study of a non-Gaussian signal model). The two-estimator restriction (f and g) could be relaxed to chains or trees of estimators with varying performance tradeoffs. And the myopic VoI computation in the leave-one-out auction does not account for strategic anticipation of future bids; an extension to a multi-round ascending-price auction (38) is a natural next step. Furthermore, as discussed in Section 5, when bidding against weaker adversaries that place poor bids, Pandora’s Bidder can improve its own utility at the expense of the overall welfare. Acknowledgements We thank Alekh Agarwal, Jonathan Berant, and Ian Gemp for helpful research discussions, and Chris Dyer and Artem Sokolov for helpful comments and feedback on the manuscript. This research also benefited from early-stage discussions with Will Dabney. References Beyhaghi and Cai (2023) H. Beyhaghi and L. Cai Pandora’s problem with nonobligatory inspection: optimal structure and a PTAS. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, p. 803–816. Cited by: §6. Beyhaghi and Kleinberg (2019) H. Beyhaghi and R. Kleinberg Pandora’s problem with nonobligatory inspection. In Proceedings of the 2019 ACM Conference on Economics and Computation, p. 131–132. Cited by: Figure 7, §D.5, §1, §3, §6, footnote 2, footnote 4. Chang et al. (2020) M. Chang, S. Kaushik, S. M. Weinberg, T. Griffiths, and S. Levine Decentralized reinforcement learning: global decision-making via local economic transactions. In International Conference on Machine Learning, p. 1437–1447. Cited by: §6. Chen et al. (2023) L. Chen, M. Zaharia, and J. Zou FrugalGPT: how to use large language models while reducing cost and improving performance. arXiv preprint arXiv:2305.05176. Cited by: §6. Cobbe et al. (2021) K. Cobbe, V. Kosaraju, M. Bavarian, M. Chen, H. Jun, L. Kaiser, M. Plappert, J. Tworek, J. Hilton, R. Nakano, et al. Training verifiers to solve math word problems. arXiv preprint arXiv:2110.14168. Cited by: Appendix B, §2.1. Collina et al. (2025) N. Collina, S. Goel, A. Roth, E. Ryu, and M. Shi Emergent alignment via competition. arXiv preprint arXiv:2509.15090. Cited by: §6. Davis and Smith (1983) R. Davis and R. G. Smith Negotiation as a metaphor for distributed problem solving. Artificial Intelligence 20 (1), p. 63–109. Cited by: §6. Dearden et al. (1998) R. Dearden, N. Friedman, S. Russell, et al. Bayesian q-learning. Aaai/iaai 1998, p. 761–768. Cited by: §6. Ding et al. (2026) W. Ding, N. Tomlin, and G. Durrett Calibrate-then-act: cost-aware exploration in LLM agents. arXiv preprint arXiv:2602.16699. Cited by: §6. Doval (2018) L. Doval Whether or not to open Pandora’s box. Journal of Economic Theory 175, p. 127–158. Cited by: 1st item, §1, §3. Dütting et al. (2024) P. Dütting, V. Mirrokni, R. P. Leme, H. Xu, and S. Zuo Mechanism design for large language models. In Proceedings of the ACM Web Conference 2024, Cited by: §6. Eisenstein et al. (2025) J. Eisenstein, R. Aghajani, A. Fisch, D. Dua, F. Huot, M. Lapata, V. Zayats, and J. Berant Don’t lie to your friends: learning what you know from collaborative self-play. arXiv preprint arXiv:2503.14481. Cited by: Appendix B, §2.1. Feng et al. (2026) S. Feng, Y. Bai, Z. Yang, Y. Wang, Z. Tan, J. Yan, Z. Lei, W. Ding, W. Shi, H. Wang, et al. MoCo: a one-stop shop for model collaboration research. arXiv preprint arXiv:2601.21257. Cited by: §1, §6. Fu et al. (2023) H. Fu, J. Li, and D. Liu Pandora box problem with nonobligatory inspection: hardness and approximation scheme. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, p. 789–802. Cited by: §3. Gao et al. (2025) B. Gao, F. Song, Z. Yang, Z. Cai, Y. Miao, Q. Dong, L. Li, C. Ma, L. Chen, R. Xu, Z. Tang, B. Wang, D. Zan, S. Quan, G. Zhang, L. Sha, Y. Zhang, X. Ren, T. Liu, and B. Chang Omni-math: A universal olympiad level mathematic benchmark for large language models. In The Thirteenth International Conference on Learning Representations, ICLR 2025, Singapore, April 24-28, 2025, External Links: Link Cited by: Appendix B, §2.1. Gemma Team et al. (2025) Gemma Team, A. Kamath, J. Ferret, S. Pathak, N. Vieillard, R. Merhej, S. Perrin, T. Matejovicova, A. Ramé, M. Rivière, L. Rouillard, T. Mesnard, G. Cideron, J. Grill, S. Ramos, E. Yvinec, M. Casbon, E. Pot, I. Penchev, G. Liu, F. Visin, K. Kenealy, L. Beyer, X. Zhai, A. Tsitsulin, R. Busa-Fekete, A. Feng, N. Sachdeva, B. Coleman, Y. Gao, B. Mustafa, I. Barr, E. Parisotto, D. Tian, M. Eyal, C. Cherry, J. Peter, D. Sinopalnikov, S. Bhupatiraju, R. Agarwal, M. Kazemi, D. Malkin, R. Kumar, D. Vilar, I. Brusilovsky, J. Luo, A. Steiner, A. Friesen, A. Sharma, A. Sharma, A. M. Gilady, A. Goedeckemeyer, A. Saade, A. Feng, A. Kolesnikov, A. Bendebury, A. Abdagic, A. Vadi, A. György, A. S. Pinto, A. Das, A. Bapna, A. Miech, A. Yang, A. Paterson, A. Shenoy, A. Chakrabarti, B. Piot, B. Wu, B. Shahriari, B. Petrini, C. Chen, C. L. Lan, C. A. Choquette-Choo, C. Carey, C. Brick, D. Deutsch, D. Eisenbud, D. Cattle, D. Cheng, D. Paparas, D. S. Sreepathihalli, D. Reid, D. Tran, D. Zelle, E. Noland, E. Huizenga, E. Kharitonov, F. Liu, G. Amirkhanyan, G. Cameron, H. Hashemi, H. Klimczak-Plucińska, H. Singh, H. Mehta, H. T. Lehri, H. Hazimeh, I. Ballantyne, I. Szpektor, I. Nardini, J. Pouget-Abadie, J. Chan, J. Stanton, J. Wieting, J. Lai, J. Orbay, J. Fernandez, J. Newlan, J. Ji, J. Singh, K. Black, K. Yu, K. Hui, K. Vodrahalli, K. Greff, L. Qiu, M. Valentine, M. Coelho, M. Ritter, M. Hoffman, M. Watson, M. Chaturvedi, M. Moynihan, M. Ma, N. Babar, N. Noy, N. Byrd, N. Roy, N. Momchev, N. Chauhan, N. Sachdeva, O. Bunyan, P. Botarda, P. Caron, P. K. Rubenstein, P. Culliton, P. Schmid, P. G. Sessa, P. Xu, P. Stanczyk, P. Tafti, R. Shivanna, R. Wu, R. Pan, R. Rokni, R. Willoughby, R. Vallu, R. Mullins, S. Jerome, S. Smoot, S. Girgin, S. Iqbal, S. Reddy, S. Sheth, S. Põder, S. Bhatnagar, S. R. Panyam, S. Eiger, S. Zhang, T. Liu, T. Yacovone, T. Liechty, U. Kalra, U. Evci, V. Misra, V. Roseberry, V. Feinberg, V. Kolesnikov, W. Han, W. Kwon, X. Chen, Y. Chow, Y. Zhu, Z. Wei, Z. Egyed, V. Cotruta, M. Giang, P. Kirk, A. Rao, K. Black, N. Babar, J. Lo, E. Moreira, L. G. Martins, O. Sanseviero, L. Gonzalez, Z. Gleicher, T. Warkentin, V. Mirrokni, E. Senter, E. Collins, J. Barral, Z. Ghahramani, R. Hadsell, Y. Matias, D. Sculley, S. Petrov, N. Fiedel, N. Shazeer, O. Vinyals, J. Dean, D. Hassabis, K. Kavukcuoglu, C. Farabet, E. Buchatskaya, J. Alayrac, R. Anil, Dmitry, Lepikhin, S. Borgeaud, O. Bachem, A. Joulin, A. Andreev, C. Hardin, R. Dadashi, and L. Hussenot Gemma 3 technical report. External Links: 2503.19786, Link Cited by: §2.1. Gergatsouli and Tzamos (2023) E. Gergatsouli and C. Tzamos Weitzman’s rule for Pandora’s box with correlations. Advances in Neural Information Processing Systems 36, p. 12644–12664. Cited by: §4. Google DeepMind (2026) Google DeepMind External Links: Link Cited by: §2.1. [19] Harvard-MIT Mathematics Tournament HMMT past problems and solutions. Note: https://w.hmmt.org/Accessed: 2026-04-22 Cited by: Appendix B, §2.1. He et al. (2024) C. He, R. Luo, Y. Bai, S. Hu, Z. L. Thai, J. Shen, J. Hu, X. Han, Y. Huang, Y. Zhang, J. Liu, L. Qi, Z. Liu, and M. Sun OlympiadBench: a challenging benchmark for promoting AGI with olympiad-level bilingual multimodal scientific problems. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics, Cited by: Appendix B, §2.1. Hendrycks et al. (2020) D. Hendrycks, C. Burns, S. Basart, A. Zou, M. Mazeika, D. Song, and J. Steinhardt Measuring massive multitask language understanding. arXiv preprint arXiv:2009.03300. Cited by: Appendix B, §2.1. Hendrycks et al. (2021) D. Hendrycks, C. Burns, S. Kadavath, A. Arora, S. Basart, E. Tang, D. Song, and J. Steinhardt Measuring mathematical problem solving with the MATH dataset. In Proceedings of the Neural Information Processing Systems Track on Datasets and Benchmarks 1, NeurIPS Datasets and Benchmarks 2021, J. Vanschoren and S. Yeung (Eds.), External Links: Link Cited by: Appendix B, §2.1. Howard (1966) R. A. Howard Information value theory. IEEE Transactions on systems science and cybernetics 2 (1), p. 22–26. Cited by: §6. Hu et al. (2024) Q. J. Hu, J. Bieker, X. Li, N. Jiang, B. Keigwin, G. Ranganath, K. Keutzer, and S. K. Upadhyay RouterBench: a benchmark for multi-LLM routing system. In International Conference on Machine Learning, Cited by: §1, §2, §6. Jeong et al. (2024) S. Jeong, J. Baek, S. Cho, S. J. Hwang, and J. Park Adaptive-RAG: learning to adapt retrieval-augmented large language models through question complexity. In Proceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers), K. Duh, H. Gomez, and S. Bethard (Eds.), p. 7036–7050. External Links: Link, Document Cited by: §6. Jitkrittum et al. (2025) W. Jitkrittum, H. Narasimhan, A. S. Rawat, J. Juneja, C. Wang, Z. Wang, A. Go, C. Lee, P. Shenoy, R. Panigrahy, et al. Universal model routing for efficient LLM inference. arXiv preprint arXiv:2502.08773. Cited by: Appendix B, §2.1, §6. Krithara et al. (2023) A. Krithara, A. Nentidis, K. Bougiatiotis, and G. Paliouras BioASQ-qa: a manually curated corpus for biomedical question answering. Scientific Data 10 (1), p. 170. Cited by: Appendix B. Kwiatkowski et al. (2019) T. Kwiatkowski, J. Palomaki, O. Redfield, M. Collins, A. Parikh, C. Alberti, D. Epstein, I. Polosukhin, J. Devlin, K. Lee, K. Toutanova, L. Jones, M. Kelcey, M. Chang, A. M. Dai, J. Uszkoreit, Q. Le, and S. Petrov Natural questions: a benchmark for question answering research. Transactions of the Association for Computational Linguistics 7, p. 452–466. External Links: Link, Document Cited by: Appendix B. Lee et al. (2025) J. Lee, F. Chen, S. Dua, D. Cer, M. Shanbhogue, I. Naim, G. H. Ábrego, Z. Li, K. Chen, H. S. Vera, et al. Gemini embedding: generalizable embeddings from gemini. arXiv preprint arXiv:2503.07891. Cited by: §C.1. Lewis et al. (2020) P. Lewis, E. Perez, A. Piktus, F. Petroni, V. Karpukhin, N. Goyal, H. Küttler, M. Lewis, W. Yih, T. Rocktäschel, et al. Retrieval-augmented generation for knowledge-intensive NLP tasks. Advances in neural information processing systems 33, p. 9459–9474. Cited by: §2.1. Liang et al. (2025) A. Liang, J. Berant, A. Fisch, A. Goyal, K. Krishna, and J. Eisenstein Plantain: plan-answer interleaved reasoning. arXiv preprint arXiv:2512.03176. Cited by: §2. Lu et al. (2024) K. Lu, H. Yuan, R. Lin, J. Lin, Z. Yuan, C. Zhou, and J. Zhou Routing to the expert: efficient reward-guided ensemble of large language models. In Proceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers), K. Duh, H. Gomez, and S. Bethard (Eds.), Mexico City, Mexico, p. 1964–1974. External Links: Link, Document Cited by: §2. Mallen et al. (2023) A. Mallen, A. Asai, V. Zhong, R. Das, D. Khashabi, and H. Hajishirzi When not to trust language models: investigating effectiveness of parametric and non-parametric memories. In Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), A. Rogers, J. Boyd-Graber, and N. Okazaki (Eds.), Toronto, Canada, p. 9802–9822. External Links: Link, Document Cited by: Appendix B. [34] Mathematical Association of America American invitational mathematics examination (AIME). Note: https://maa.org/math-competitions/amc-1012Accessed: 2026-04-22 Cited by: Appendix B, §2.1. Moskvoretskii et al. (2025) V. Moskvoretskii, M. Marina, M. Salnikov, N. Ivanov, S. Pletenev, D. Galimzianova, N. Krayko, V. Konovalov, I. Nikishina, and A. Panchenko Adaptive retrieval without self-knowledge? bringing uncertainty back home. In Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), p. 6355–6384. External Links: Link, Document, ISBN 979-8-89176-251-0 Cited by: §6. Nourzad et al. (2025) N. Nourzad, H. Yang, S. Chen, and C. Joe-Wong DR. WELL: Dynamic reasoning and learning with symbolic world model for embodied llm-based multi-agent collaboration. CoRR abs/2511.04646. External Links: Document, 2511.04646 Cited by: §6. Ong et al. (2025) I. Ong, A. Almahairi, V. Wu, W. Chiang, T. Wu, J. E. Gonzalez, M. W. Kadous, and I. Stoica RouteLLM: learning to route LLMs from preference data. In The Thirteenth International Conference on Learning Representations, External Links: Link Cited by: §2, §6. Parkes (2005) D. C. Parkes Auction design with costly preference elicitation. Annals of Mathematics and Artificial Intelligence 44 (3), p. 269–302. Cited by: §1, §5, §5, §5, §6, §7. Rein et al. (2023) D. Rein, B. L. Hou, A. C. Stickland, J. Petty, R. Y. Pang, J. Dirani, J. Michael, and S. R. Bowman Gpqa: a graduate-level google-proof q&a benchmark. arXiv preprint arXiv:2311.12022. Cited by: Appendix B. Sandholm (1993) T. Sandholm An implementation of the contract net protocol based on marginal cost calculations. In AAAI, Vol. 93, p. 256–262. Cited by: §6. Sciavolino et al. (2021) C. Sciavolino, Z. Zhong, J. Lee, and D. Chen Simple entity-centric questions challenge dense retrievers. In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, M. Moens, X. Huang, L. Specia, and S. W. Yih (Eds.), Online and Punta Cana, Dominican Republic, p. 6138–6148. External Links: Link, Document Cited by: Appendix B. Scully and Doval (2024) Z. Scully and L. Doval Local hedging approximately solves pandora’s box problems with nonobligatory inspection. arXiv preprint arXiv:2410.19011. Cited by: §6. Shnitzer et al. (2023) T. Shnitzer, A. Ou, M. Silva, K. Soule, Y. Sun, J. Solomon, N. Thompson, and M. Yurochkin Large language model routing with benchmark datasets. arXiv preprint arXiv:2309.15789. Cited by: §1, §6. Sun et al. (2024) K. Sun, Y. Xu, H. Zha, Y. Liu, and X. L. Dong Head-to-tail: how knowledgeable are large language models (LLMs)? A.K.A. will LLMs replace knowledge graphs?. In Proceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers), K. Duh, H. Gomez, and S. Bethard (Eds.), Mexico City, Mexico, p. 311–325. External Links: Link Cited by: Appendix B. Tarasova et al. (2025) E. Tarasova, V. Erofeeva, O. Granichin, and K. Chernikov Decentralized adaptive task allocation for dynamic multi-agent systems. Scientific Reports 15 (1), p. 39226. Cited by: §6. Tomašev et al. (2026) N. Tomašev, M. Franklin, and S. Osindero Intelligent AI delegation. arXiv preprint arXiv:2602.11865. Cited by: §6. Weitzman (1979) M. L. Weitzman Optimal search for the best alternative. Econometrica 47 (3), p. 641–654. Cited by: §1, §3, §3, §3. Xie et al. (2024) Q. Xie, R. Astudillo, P. I. Frazier, Z. Scully, and A. Terenin Cost-aware bayesian optimization via the pandora’s box gittins index. Advances in Neural Information Processing Systems 37, p. 115523–115562. Cited by: §4, §4, §6. Yang et al. (2025) Y. Yang, H. Chai, S. Shao, Y. Song, S. Qi, R. Rui, and W. Zhang AgentNet: Decentralized evolutionary coordination for LLM-based multi-agent systems. In Advances in Neural Information Processing Systems, Cited by: §6. Yao et al. (2022) S. Yao, J. Zhao, D. Yu, N. Du, I. Shafran, K. R. Narasimhan, and Y. Cao React: synergizing reasoning and acting in language models. In The Eleventh International Conference on Learning Representations, Cited by: §2. Zhao et al. (2025) C. Zhao, Q. Hu, S. Song, D. Chen, Z. Han, J. Xu, and B. Zheng LLM-auction: generative auction towards llm-native advertising. ArXiv abs/2512.10551. Cited by: §6. Zhuang et al. (2025) R. Zhuang, T. Wu, Z. Wen, A. Li, J. Jiao, and K. Ramchandran EmbedLLM: learning compact representations of large language models. In The Thirteenth International Conference on Learning Representations, Cited by: Appendix B, §2.1, §6. Appendix A Pandora’s Routing Objective In Section 4, we connect routing to Pandora’s Box by treating each specialist as a box and the costly value estimate as the value revealed by opening that box. The revealed value, however, is not RmR_m itself, but GmG_m, which is the costly, more accurate estimate of RmR_m. In this section we formally justify the objective of searching for the maximum value of GmG_m when RmR_m is unknown. Let ℐ0I_0 denote the zero-cost information available before any costly queries, including the prompt and the cheap estimates F. Inspecting specialist m reveals costly information ZmZ_m at cost cmc_m. In the ideal calibrated case, the value revealed by opening box m is Gm⋆=[Rm∣ℐ0,Zm].G_m =E[R_m _0,Z_m]. (8) Thus Gm⋆G_m is the posterior decision value of specialist m after ZmZ_m has been acquired. Admissible Policies. We restrict attention to sequential policies that only use information that has actually been observed. Let ℱ0=ℐ0F_0=I_0 be the zero-cost information state, and let O0=∅O_0= be the set of opened specialists. At each step t, a policy either stops, or selects an unopened specialist At+1∈ℳ∖OtA_t+1 O_t to inspect. The stopping decision and the choice of At+1A_t+1 are required to be ℱtF_t-measurable. If At+1A_t+1 is inspected, the policy pays cost cAt+1c_A_t+1, observes ZAt+1Z_A_t+1, and the state updates to Ot+1=Ot∪At+1,ℱt+1=ℱt∨σ(At+1,ZAt+1).O_t+1=O_t∪\A_t+1\, _t+1=F_t σ(A_t+1,Z_A_t+1). where σ(At+1,ZAt+1)σ(A_t+1,Z_A_t+1) denotes the sigma algebra generated by At+1A_t+1 and ZAt+1Z_A_t+1. Let τ be the stopping time, O=OτO=O_τ the final opened set, and CO=∑i∈OciC_O= _i∈ Oc_i the total inspection cost. The final selected specialist M M must be measurable with respect to the terminal information ℱτF_τ. We call such a policy admissible. In the obligatory-inspection case we require M^∈O M∈ O almost surely; in the non-obligatory case, M M may also be unopened. Remark 1. Here ℐ0I_0 should be interpreted as the information available at zero computational cost. Costly computations are represented by ZmZ_m and are not included in the information state until specialist m is inspected, even when they are deterministic functions of the prompt. Proposition 1 (Opened-value reduction). Suppose the collection (Rm,Zm)m=1M\(R_m,Z_m)\_m=1^M is conditionally independent given ℐ0I_0. Let Π be any admissible policy that opens a random set O, incurs cost CO=∑i∈OciC_O= _i∈ Oc_i, and selects an opened specialist M^∈O M∈ O almost surely. Define Gm⋆=[Rm∣ℐ0,Zm].G_m =E[R_m _0,Z_m]. Then [RM^−CO]=[GM^⋆−CO].E[R_ M-C_O]=E[G_ M -C_O]. Consequently, among policies that select opened specialists, maximizing expected realized reward is equivalent to maximizing the opened posterior decision value net of inspection costs. Proof. By admissibility, M M and COC_O are ℱτF_τ-measurable. Hence the tower property gives [RM^−CO]=[[RM^∣ℱτ]−CO].E[R_ M-C_O]=E\! [E[R_ M _τ]-C_O ]. Because M M is ℱτF_τ-measurable, [RM^∣ℱτ]=∑m=1MM^=m[Rm∣ℱτ].E[R_ M _τ]= _m=1^M1\ M=m\E[R_m _τ]. On the event M^=m\ M=m\, the specialist m has been opened, so ℱτF_τ contains ZmZ_m. The remaining terminal information consists of zero-cost information and signals from other opened specialists, together with decisions that are measurable functions of those observed signals. Conditional independence implies that this additional information does not change the posterior mean of RmR_m once (ℐ0,Zm)(I_0,Z_m) is known. Therefore [Rm∣ℱτ]=[Rm∣ℐ0,Zm]=Gm⋆E[R_m _τ]=E[R_m _0,Z_m]=G_m on the event that m has been opened. Substituting this into the previous equation yields [RM^∣ℱτ]=GM^⋆,E[R_ M _τ]=G_ M , and therefore [RM^−CO]=[GM^⋆−CO].E[R_ M-C_O]=E[G_ M -C_O]. ∎ Corollary 1 (Sealed value of an unopened specialist). Let ℋH be any information state generated by an admissible policy before specialist m has been opened. Define the value that would be revealed by opening m at this information state as Gm|ℋ⋆=[Rm∣ℋ,Zm].G_m =E[R_m ,Z_m]. If specialist m is selected without being opened, then its decision value is [Rm∣ℋ]=[Gm|ℋ⋆∣ℋ].E[R_m ]=E[G_m ]. Thus an unopened specialist is evaluated by the posterior expectation of the value that would have been revealed by opening it. Proof. This is the tower property: [Gm|ℋ⋆∣ℋ]=[[Rm∣ℋ,Zm]∣ℋ]=[Rm∣ℋ].E[G_m ]=E\! [E[R_m ,Z_m] ]=E[R_m ]. ∎ Proposition 1 explains why opened boxes can be searched using posterior decision values rather than realized rewards. Corollary 1 explains the corresponding role of unopened boxes in the non-obligatory inspection variant: an unopened specialist is a sealed outside option, whose value is the current posterior expectation of the value that opening would reveal. The backup-price construction in Pandora-NI is a way to compare this sealed option against the opened values of the other boxes. The proposition and corollary are exact for the ideal posterior values. In practice, we do not observe Gm⋆G_m directly. Our costly estimator returns a learned score Gm=gm(X,Zm),G_m=g_m(X,Z_m), which we use as a plug-in approximation to Gm⋆G_m . If gmg_m were trained by squared loss with unlimited data and sufficient model capacity, its population regression target would be the conditional mean in Equation 8. With finite data and a restricted model class, GmG_m is only an approximation. The Pandora reduction should therefore be read as exact for calibrated posterior decision values, and approximate when implemented with learned scores. The empirical question is whether the learned GmG_m is accurate and calibrated enough to improve routing decisions for the original reward objective. Appendix B Dataset Details MATH. For this evaluation, we compile a diverse corpus of mathematical problems spanning multiple levels of difficulty. This includes the standard Hendrycks MATH dataset (22), which provides roughly 1250012500 problems across seven mathematical domains. We also incorporate the Omni-Math dataset (15), an Olympiad-level benchmark designed to assess advanced reasoning capabilities. From this dataset, we utilize a subset of 1625 hard problems, filtered by problems which have between zero and 16 derivation steps. Furthermore, we include 969 American Invitational Mathematics Examination (AIME) problems (34; 20), filtered to preclude any overlap with the MATH dataset, alongside 1419 problems from the Harvard-MIT Mathematics Tournament (HMMT) (19) (filtered to avoid overlap with Omni-Math). For the MATH dataset, we retain its standard 5000-problem test split. The remaining datasets are divided using a balanced 50/50 train-test split, resulting in a final aggregate corpus of 9504 training and 7008 testing examples. Prompts are shown in Appendix C.2. RAG. Our RAG evaluation setting builds on prior work that combines two retrieval specialists (Wikipedia and PubMed) along with a low-cost model without retrieval (12). Following prior work, we train and evaluate on a collection of factoid questions from PopQA (33), Entity Questions (41), Natural Questions (28), and BioASQ (27). We use 18661 questions for training, 1600 for test, and 400 for calibration, drawing an equal proportion from each of the four datasets. We use the same retrieval pipelines as 12, and generate responses using Gemini-3.1-Flash-Lite. Prompts are shown in Appendix C.2. We use 4 few-shot examples per dataset (16 total) in order to prompt the LLM to generate answers in the right format. The responses are judged for correctness against the ground-truth answers given in each dataset. For each question, we sample 88 responses and score each for correctness. The reward is the average correctness score, less a constant cost penalty of 0.050.05 for systems that use retrieval (i.e., Wikipedia and Pubmed specialists). This cost value was chosen to make the routing problem non-trivial (i.e., the model without retrieval can compete when retrieval is not necessary). To avoid false negatives inherent in exact string matching, we use Gemini-3.1-Flash as an LLM-as-a-judge using the same annotation prompt as 44 (Appendix A.1, Prompt 2), which was measured to have very strong agreement with human judgements (98%98\%). EmbedLLM. The EmbedLLM dataset is composed of questions from benchmarks such as GPQA (39), GSM8K (5), and MMLU (21), along with the scores from 123 models (52). We use this dataset without modification. Following 26, we set the model costs to be a linear multiple of the number of parameters. Specifically we apply a cost of 1 per trillion parameters, so that, e.g., Qwen-1.5-7B-Chat has a cost of .00772.00772 and Qwen-1.5-32B-chat has a cost of .0325.0325. Seven models were excluded because the parameter count could not be determined (e.g., Claude). We use 16756 prompts for training, 2436 for test, and 609 for calibration. Appendix C Implementation details C.1 Value estimators We give additional details for the value estimators fmf_m and gmg_m described in Section 2.1. Embedding-based estimation (KNN). The cheap value estimator computes an embedding e(x)e(x) of the prompt and retrieves the k nearest neighbors k(x)N_k(x) from a calibration set, returning: fmKNN(x)=1k∑x′∈k(x)Rm(x′),f_m^KNN(x)= 1k _x _k(x)R_m(x ), (9) where proximity is measured by cosine similarity in the embedding space. This estimator is fast but limited to patterns that are visible in the embedding space. We use Gemini Embedding 2 (29) as our embedder, and use k=3k=3 for the KNN computation. Fine-tuned estimation (SFT). A small language model hθh_θ is fine-tuned with a regression loss to predict the cost-adjusted reward from an input context zm(x)z_m(x): min∑(x,m)θ(hθ(zm(x))−Rm(x))2. _θ _(x,m) (h_θ(z_m(x))-R_m(x) )^2. (10) The context zm(x)z_m(x) can be the prompt alone (SFT-prompt), the prompt with retrieval results (SFT-retrievals), or the prompt with partial reasoning traces (SFT-CoT-k). We use Gemini-2.5-Flash-Lite as the base model for fine-tuning. Targets are real-valued. Prompts are shown in Appendix C.2. C.2 Prompts Math task: prompt with reasoning. Solve the following math problem. Show your work step-by-step, explaining your reasoning clearly. After your reasoning, provide the final answer enclosed in tags. Problem: problem Step-by-step solution: ⟨ here⟩ The final answer is answer. Math task: SFT value estimator prompt using CoT. Question: question Chain-of-Thought: CoT text Specialist: specialist Based on the question and the chain of thought, will the specialist answer correctly? (Predict 1.0 for yes, 0.0 for no) RAG task: QA prompt with retrievals. You are a helpful agent whose job is to answer a question. Your answers should be short. For example, if the question is “What is the capital of France?”, please answer “Paris”, and not “Paris is the capital of France”. If you are asked a yes/no question, you may only answer “yes” or “no”. To help you answer the question correctly, you will be given verified information from corpus. The verified information may not be necessary, and you can directly answer the question if you are confident that you have the correct answer. The verified information may also not be relevant or sufficient to answer the question. You should still always respond with your best guess. few_shot_examples QUESTION: question retrievals QUESTION: question ANSWER: RAG task: standard prompt without retrievals. You are a helpful agent whose job is to answer a question. Your answers should be short. For example, if the question is “What is the capital of France?”, please answer “Paris”, and not “Paris is the capital of France”. If you are asked a yes/no question, you may only answer “yes” or “no”. few_shot_examples QUESTION: question ANSWER: RAG task: SFT value estimator prompt using retrievals. INSTRUCTIONS: Your task is to predict how likely it is that a language model with capability correctly answers the following question. QUESTION: question INFORMATION: Here are the retrieved passages that the language model will have access to: 1. Title: title_1 Passage: passage_1 2. Title: title_2 Passage: passage_2 … QUESTION: question RESPONSE: RAG task: SFT value estimator prompt without retrievals. INSTRUCTIONS: Your task is to predict how likely it is that a language model with capability correctly answers the following question. QUESTION: question RESPONSE: EmbedLLM: SFT value estimator prompt (no additional info). INSTRUCTIONS: Your task is to predict how likely it is that the model actor gives a satisfactory response to the following prompt. PROMPT: prompt How likely is it? C.3 Experiment compute resources Much of our work is based on pre-computed outputs from existing models (e.g., the EmbedLLM data). The main exception is in value estimation, for which we finetuned small Transformer-based encoders ourselves, and inference for the RAG and math domains. Specifically, in the evaluation on the math domain, where we made 15k calls to the Gemini-2.5-Flash-Lite and Gemma3-4B models to compute answers, where the models are served on a TPU cluster with 32 TPUs. This process took less than 1 hour. For the RAG domain, we made ∼ 500k calls to Gemini-2.5-Flash-Lite to generate 8 responses per question per retrieval setting, and then another ∼ 500k calls to Gemini-2.5-Flash to score all the responses for correctness. We also fine-tuned small Transformers as value estimators for each setting, requiring 1-3 hours of training time. The training time was higher for the math domain, needing up to 6 hours, while running on 64 Google TPUs utilizing up to 436.69 GiB of Memory. The Pandora’s box algorithm itself was run on CPU at minimal cost. Appendix D Supplemental Results D.1 Number of queries Figure 4 shows the number of queries executed by each algorithm. Note that Pandora-OI, the obligatory-inspection variant, must always execute at least one query. At higher costs, most of the savings for Pandora-NI derives from identifying prompts for which it is not necessary to query g. 10−310^-310−210^-210−110^-1001122CostNum QueriesMATH10−310^-310−210^-210−110^-100112233CostRAG10−510^-510−410^-410−310^-310−210^-210−110^-110010^010110^110210^2CostEmbedLLM7 Figure 4: Number of queries to g during model routing. D.2 Auctions against weak opponents In Section 5, the leave-one-out auction computes a posted price from the costly value estimates gj≠mg_j≠ m. Since the optimal value-of-information-based strategy for the strategic specialist m depends on the price it faces (i.e., if it is in the interval [plo,phi][p_lo,p_hi]), changing the posted price will also affect the total allocative efficiency and the specialist’s surplus. In particular, we will see that when the price does not accurately represent the true value of the best competing specialist, the strategic specialist can exploit this the maximize its own profit at the expense of the overall allocative efficiency of the joint system. Figure 5 shows what happens if the posted prices are computed from the weak estimator fmf_m instead. In both the RAG and EmbedLLM settings, efficiency regret actually increases, even while individual surplus regret improves at most cost levels. This indicates that the leave-one-out bidder is able to improve its individual utility at the expense of overall welfare, by exploiting poor bids from the other participants. This can happen both when the posted price is too low (the specialist will accept the price, even though a competitor might be better), or when the posted price is too high (the specialist will decline the price, even though it is better than all competitors). 10−210^-210−110^-10.050.050.060.06Surplus RegretMATH10−210^-210−110^-10.10.10.150.15RAG10−510^-510−410^-410−310^-310−210^-210−110^-10.090.090.0950.0950.10.1EmbedLLM10−210^-210−110^-10.020.020.0250.0250.030.03cgc_gEfficiency Regret10−210^-210−110^-10.0550.0550.060.060.0650.0650.070.07cgc_g10−510^-510−410^-410−310^-310−210^-210−110^-10.040.040.060.060.080.080.10.10.120.12cgc_g7 Figure 5: Specialist surplus regret and total allocative efficiency regret of the posted-price auction, when bidding against opponents who have access only to f, rather than g as in Figure 3. D.3 Monetary costs for value functions As noted in Section 2.2, we estimate monetary costs from prices listed at https://ai.google.dev/gemini-api/docs/pricing (retrieved August 1, 2026). In all evaluations, the f value estimator is a small MLP applied to a question embedding. The MLP itself is very cheap to run, and can be assumed to be cost-free. The embedding costs $0.20 per million tokens, and this can be amortized across target models, although to be conservative about cg/cfc_g/c_f, we do not account for this amortization here. The g value estimators are priced as follows: • SFT-CoT-20, used in the MATH domain, requires running the target model LLM reasoning process for 20 tokens. The cheapest frontier LLM (Gemini 3.5 flash-lite) costs $2.50 per million output tokens, and $0.25 per million input tokens. In the MATH domain, there are approximately 43 tokens per question. This gives cf≈8.6×10−6c_f≈ 8.6× 10^-6 and cg≈2.5×20×10−6=5×10−5c_g≈ 2.5× 20× 10^-6=5× 10^-5, yielding cg/cf≈5.8.c_g/c_f≈ 5.8. • SFT-retrievals, used in the RAG domain, requires running retrieval, which costs 1.4×10−21.4× 10^-2 per model evaluation. At 10.110.1 tokens per question in the RAG domain, we have cf≈10.1×.2×10−6≈2×10−6.c_f≈ 10.1×.2× 10^-6≈ 2× 10^-6. We conservatively estimate cg/cf>7000.c_g/c_f>7000. • SFT-prompt, used in EmbedLLM, requires LLM inference to generate a single token. As above, this costs 2.5×10−62.5× 10^-6 per output token and 2.5×10−72.5× 10^-7 per input token; the f estimator costs 2×10−72× 10^-7 per input token. At 126126 tokens per query, this yields a ratio of cg/cf≈1.6.c_g/c_f≈ 1.6. However, this does not account for amortization of the embedding cost cfc_f across target models, which would be most significant in this domain because it has the largest number of models. 101.510^1.510210^20.090.090.10.10.110.11Inspection cost ($/1M queries)Routing RegretMATH10−210^-210−110^-110010^010110^110210^20.080.080.10.10.120.120.140.14Inspection cost ($/1K queries)RAG100.510^0.50.370.370.380.380.390.39Inspection cost ($/1K queries)EmbedLLM6 Figure 6: Routing performance versus monetary inspection cost, as estimated in Section D.3. D.4 Numerical results and significance tests Numerical results and significance tests for the routing evaluations are shown in Tables 3, 4, and 5. In each table, bold indicates the lowest regret + inspection cost, asterisk indicates a statistically significant improvement over all alternatives at p<.05p<.05 by a paired bootstrap test. These results present a consistent picture: Pandora’s router is in the argmin of regret at nearly every cost level. At low costs, it matches g-always; at high costs it matches f-only; at intermediate costs, it often offers the best regret, although this difference is usually not statistically significant with respect to all alternatives. Cost f-only g-only Top-22 Coin Flip Random-NprN_pr Margin-NprN_pr Pandora’s Router 1.5e-03 0.117 0.093 0.093 0.109 0.194 0.093 0.095 2.1e-03 0.117 0.094 0.094 0.109 0.193 0.097 0.096 3.2e-03 0.117 0.096 0.096 0.110 0.198 0.098 0.098 4.6e-03 0.117 0.099 0.099 0.112 0.197 0.099 0.099 6.8e-03 0.117 0.104 0.104 0.114 0.193 0.101 0.101 1.0e-02 0.117 0.110 0.110 0.117 0.199 0.104* 0.107 1.5e-02 0.117 0.119 0.119 0.122 0.175 0.108* 0.113 2.2e-02 0.117 0.133 0.133 0.129 0.177 0.113 0.111 3.2e-02 0.117 0.153 0.153 0.139 0.147 0.112 0.111 4.6e-02 0.117 0.183 0.183 0.154 0.130 0.113 0.113 6.8e-02 0.117 0.226 0.226 0.176 0.117 0.117 0.109* Table 3: Numerical results on MATH routing. Bold indicates lowest regret + inspection cost, asterisk indicates significance at p<.05p<.05 (paired bootstrap). Cost f-only g-only Top-22 Coin Flip Random-NprN_pr Margin-NprN_pr Pandora’s Router 1.5e-03 0.150 0.088 0.110 0.124 0.129 0.100 0.090 2.1e-03 0.150 0.090 0.112 0.125 0.134 0.103 0.090 3.2e-03 0.150 0.093 0.114 0.127 0.146 0.110 0.092 4.6e-03 0.150 0.098 0.117 0.129 0.155 0.113 0.098 6.8e-03 0.150 0.104 0.121 0.132 0.155 0.119 0.104 1.0e-02 0.150 0.114 0.127 0.137 0.170 0.124 0.110 1.5e-02 0.150 0.128 0.137 0.144 0.182 0.134 0.122 2.2e-02 0.150 0.148 0.150 0.155 0.198 0.143 0.136 3.2e-02 0.150 0.178 0.171 0.170 0.196 0.154 0.144 4.6e-02 0.150* 0.223 0.200 0.192 0.167 0.155 0.157 6.8e-02 0.150 0.288 0.244 0.225 0.150 0.150 0.155 Table 4: Numerical results on RAG routing. Bold indicates lowest regret + inspection cost, asterisk indicates significance at p<.05p<.05 (paired bootstrap). Cost f-only g-only Top-22 Coin Flip Random-NprN_pr Margin-NprN_pr Pandora’s Router 1.0e-05 0.393 0.371 0.402 0.398 0.412 0.377 0.372 1.0e-04 0.393 0.381 0.402 0.403 0.421 0.377 0.372 3.0e-04 0.393 0.403 0.403 0.414 0.436 0.378 0.374 1.0e-03 0.393 0.480 0.404 0.453 0.454 0.387 0.382 3.0e-03 0.393 0.700 0.408 0.563 0.469 0.398 0.390 1.0e-02 0.393 1.470 0.422 0.947 0.484 0.403 0.399 3.0e-02 0.393* 3.670 0.462 2.047 0.439 0.401 0.405 1.0e-01 0.393 11.370 0.602 5.894 0.393 0.393 0.395 3.0e-01 0.393 33.370 1.002 16.887 0.393 0.393 0.391 Table 5: Numerical results on EmbedLLM routing. Bold indicates lowest regret + inspection cost, asterisk indicates significance at p<.05p<.05 (paired bootstrap). D.5 Alternative algorithm We build on prior work on non-obligatory inspection 2, which differs slightly from Algorithm 1: instead of using umbackupu^backup_m in lines 6, 8, and 9, they use μm. _m. In low-cost settings, we have umbackup<E[Vm]=μm,u^backup_m<E[V_m]= _m, which means that in these settings, our variant of the algorithm is less likely to commit to non-inspection and is therefore more aligned with Pandora-OI. In high-cost settings, umbackup>E[Vm]=μm,u^backup_m>E[V_m]= _m, which means that in these settings, our variant is more likely to commit to non-inspection and is therefore more similar to g-always. Empirically, our variant is slightly superior to the original algorithm, as shown in Figure 7. 10−2.510^-2.510−210^-210−1.510^-1.50.10.10.110.110.120.120.130.13CostRegret + Inspection Costmath10−210^-210−1.510^-1.50.10.10.120.120.140.140.160.160.180.18CostRAG10−510^-510−410^-410−310^-310−210^-210−110^-10.380.380.40.40.420.420.440.44Costembedllm7 Figure 7: Evaluation of the 2 algorithm, which uses μm _m instead of umbackupu^backup_m for evaluating committing policies. D.6 Non-Gaussian signal models Our implementation models Gm|=G_m =f as a conditional Gaussian, but real value distributions are bounded in [0,1][0,1], so a Gaussian may not be an appropriate model. For this reason, we also experimented using KNN on the vector of f-scores to estimate local conditional mean and local standard deviation directly from the neighborhood of f. For K=16K=16 this indeed improved calibration metrics somewhat: empirical coverage of the ±1σ± 1σ interval ranged between 58.7% (RAG) – 78.1% (MATH) for Gaussian, and 63.0% (RAG) – 74.8% (MATH) for KNN (theoretical target: 68.27%68.27\%). For the ±2σ± 2σ interval, the range was 89.8%89.8\% (RAG) – 94.5%94.5\% (EmbedLLM) for the Gaussian signal model, and 91.2%91.2\% (MATH) – 94.7%94.7\% (EmbedLLM) for KNN (theoretical target: 95.45%95.45\%). We apply this signal model to the routing task, with results shown in Table 6. Despite the better calibration of the KNN signal model, we did not see a significant improvement in regret + cost. For this reason, we focus on the Gaussian signal model in the main implementation. Setting Method Gaussian KNN Regret + Cost Queries Regret + Cost Queries MATH Pandora’s Router 0.1049 0.58 0.1090 0.78 RAG Pandora’s Router 0.1181 1.40 0.1218 1.22 EmbedLLM Pandora’s Router 0.3867 3.71 0.3913 0.40 Table 6: Comparison between Gaussian and KNN approximations for Pandora’s Router.