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
cs.AI
2026-08-21
Routing as Pandora's Box: cheap kNN always runs; costly scores fire only when VoI covers cost. Three domains track exhaustive scoring; EmbedLLM 0.386 vs 2.356 for g-only.
Standard model routing scores each candidate on a prompt and picks the highest expected return. Those scores come from embedding neighbors, a fine-tuned judge, a partial chain-of-thought, or a retrieval pass. None of that is free. Prior routing papers treat value estimation as a costless input with a fixed error profile.
This Google DeepMind paper asks the step before routing: when is a better score worth paying for.
Each specialist is a box in Weitzman's 1979 search problem. A cheap estimator \(f\) always runs: embed the prompt, take cosine neighbors in a calibration set, and average their rewards. The expensive estimator \(g\) is the act of opening the box. What you see inside differs by domain.
Calibration MSE: Math 0.154 vs 0.096, RAG 0.175 vs 0.109, EmbedLLM 0.266 vs 0.198. Gemini API list prices give cost ratios \(cg/cf\) of 5.8, >7000, and 1.6. Retrieval is why RAG looks extreme.
A Gaussian signal model turns the open-or-skip decision into a closed form. \(f\) supplies a conditional mean and residual variance for \(g\). The reservation price is the outside option that makes expected upside equal inspection cost. Open boxes in descending reservation price; stop when the best seen value beats every remaining reservation price.
They also run the non-obligatory variant, where a sealed box can be chosen. The fully adaptive policy is NP-hard, so they use a committing policy: hold out one box, search the rest with obligatory inspection, and pick the holdout with 100 Monte Carlo draws. On EmbedLLM the boxes are correlated, so after each opening they update remaining reservation prices with a multivariate Gaussian posterior.
Pandora's Bidder is the decentralized version. The platform posts the best competing \(g\) as a price. The strategic specialist decides whether to pay for its own \(g\) before taking or declining the query. Value of information peaks when the posted price sits near its mean, which yields a closed interval: refine only inside that interval.
The headline metric is routing regret plus inspection cost, averaged over a sweep of \(cg\). Regret is the gap between the chosen specialist's realized reward and the hindsight-best specialist.
| Method | MATH total | RAG total | EmbedLLM total |
| f-only | 0.117 | 0.150 | 0.393 |
| g-only | 0.128 | 0.141 | 2.356 |
| Top-2 | 0.128 | 0.146 | 0.438 |
| Margin-\(N{pr}\) | 0.105 | 0.128 | 0.389 |
| Pandora's Router | 0.105 | 0.118 | 0.386 |
Pandora's Router has the lowest average total on all three domains. It spends the same inspection budget as Margin, but spends it on high-reservation boxes: 0.118 vs 0.128 on RAG. MATH has only two targets, so the budget almost determines regret and the two methods tie. On EmbedLLM, g-only is crushed by a hundred-plus inspections (2.356); Pandora holds inspection cost at 0.075 and totals 0.386.
When \(cg\) is tiny, almost every box opens and quality tracks g-only. At \(cg=0.1\) nothing opens and the policy collapses to f-only. In between it tracks the lower envelope of those two extremes. On the bidder side, accurate competing estimates let value-of-information bidding track that same envelope. Noisy competing estimates let the strategic specialist refuse unprofitable queries: its surplus rises, allocative efficiency falls.
In production, the expensive part of routing is often the lookup, the partial rollout, or the judge used to decide. The paper gives a computable stopping rule: if value of information does not cover cost, do not inspect. Deployment still needs a calibration set for the Gaussian mean and variance. This is a clean framing and a gradual improvement, not a new product.
Gaussians miss heavy tails and multimodality. A non-Gaussian fit in the appendix did not improve routing. The two-estimator restriction (\(f\) vs \(g\)) is narrower than a real tool stack. The auction is a single-stage leave-one-out with no foresight about later bids. When rivals estimate badly, local surplus can hurt global welfare.
Table 2 averages over \(cg\). Pointwise, many edges over Margin fail a paired bootstrap at \(p<0.05\). MATH barely asks more than "inspect twice or zero times." The EmbedLLM correlation fix is a mean-field heuristic without an approximation ratio.