# Online Pandora's Box for Contextual LLM Cascading

arXiv: https://arxiv.org/abs/2606.07392 · HTML: https://mlsanity.com/paper/2606.07392/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 73 references that are in the map.
- First posted on arXiv 5 Jun 2026.

## Builds on (most cited first, 10 of 10)

- [LLM-Blender: Ensembling Large Language Models with Pairwise Ranking and Generative Fusion](https://mlsanity.com/paper/2306.02561/) (2023)
- [RouterBench: A Benchmark for Multi-LLM Routing System](https://mlsanity.com/paper/2403.12031/) (2024)
- [Language Model Cascades: Token-level uncertainty and beyond](https://mlsanity.com/paper/2404.10136/) (2024)
- [Tryage: Real-time, intelligent Routing of User Prompts to Large Language Models](https://mlsanity.com/paper/2308.11601/) (2023)
- [Online Cascade Learning for Efficient Inference over Streams](https://mlsanity.com/paper/2402.04513/) (2024)
- [Online Scheduling for LLM Inference with KV Cache Constraints](https://mlsanity.com/paper/2502.07115/) (2025)
- [Optimizing LLM Inference: Fluid-Guided Online Scheduling with Memory Constraints](https://mlsanity.com/paper/2504.11320/) (2025)
- [Optimal Bayesian Stopping for Efficient Inference of Consistent LLM Answers](https://mlsanity.com/paper/2602.05395/) (2026)
- [Improved Regret and Contextual Linear Extension for Pandora's Box and Prophet Inequality](https://mlsanity.com/paper/2505.18828/) (2025)
- [Asymptotically Optimal Sequential Testing with Heterogeneous LLMs](https://mlsanity.com/paper/2604.01086/) (2026)

## Built on by (most cited first, 1 of 1)

- [Scores Are Not Decisions: Cost-Aware Stopping for Tool Acquisition in LLM Agents](https://mlsanity.com/paper/2607.27083/) (2026)

## Abstract (arXiv)

Motivated by Large Language Model (LLM) cascading, we propose an online contextual Pandora's Box model for adaptively querying and selecting LLM APIs. In each period, a decision-maker observes a request context and faces a two-phase decision problem. In the query phase, the decision-maker sequentially queries APIs, where each query reveals a generated output and the decision-maker incurs an (output-dependent) cost. In the selection phase, the decision-maker selects one of the generated outputs to deploy and observes only the downstream reward of the deployed output. This output-mediated feedback structure differs from classical online contextual Pandora's Box models, in which opening a box directly reveals its reward. Rather than estimating the full conditional output and cost distributions of each API, we directly model the reservation index and develop a learning approach for the query phase. Specifically, we impose a parametric structure on the contextual reservation index functions induced by the classical Weitzman's policy. Our policy combines generalized method of moments (GMM) type estimation of these reservation indices with UCB-style confidence bounds for both these indices and the shared output-level reward evaluator. Under regularity conditions, we prove that the resulting policy achieves dimension-dependent widetilde O(√ T) cumulative regret over a horizon of T periods.