Alexandre Belloni, Yan Chen, Yehua Wei
arXiv 5 Jun 2026 · Artificial Intelligence
arXiv:2606.07392 · PDF · DOI · OpenAlex · Extracted main text
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(\sqrt T)$ cumulative regret over a horizon of $T$ periods.
appendix boundary found by none_found · 100% of the source is main text. Read the extracted text to check this.
The works this paper leans on most, across its whole bibliography — not restricted to papers in our corpus. Ranked by composite intensity, which combines how often a work is mentioned, how many sections mention it, and how much of that falls in the main text rather than the appendix.
| Reference | Intensity | Mentions | Sections | Main text | |
|---|---|---|---|---|---|
| 1 | Chen, Lingjiao and Zaharia, Matei and Zou, James (2025) FrugalGPT: How to Use Large Language Models While Reducing Cost and Improving Performance | 1.000 | 7 | 3 | 100% |
| 2 | Filippi, Sarah and Cappe, Olivier and Garivier, Aurélien and Szepesv… (2010) Parametric bandits: The generalized linear case | 1.000 | 7 | 3 | 100% |
| 3 | Abbasi-Yadkori, Yasin and Pál, Dávid and Szepesvári, Csaba (2011) Improved algorithms for linear stochastic bandits | 0.928 | 4 | 3 | 100% |
| 4 | Weitzman, Martin L (1979) OPTIMAL SEARCH FOR THE BEST ALTERNATIVE. | 0.928 | 4 | 3 | 100% |
| 5 | Atsidakou, Alexia and Caramanis, Constantine and Gergatsouli, Evange… (2024) Contextual pandora’s box | 0.874 | 8 | 2 | 100% |
| 6 | Gupta, Neha and Narasimhan, Harikrishna and Jitkrittum, Wittawat and… (2024) Language model cascades: Token-level uncertainty and beyond | 0.585 | 3 | 1 | 100% |
| 7 | Yue, Murong and Zhao, Jie and Zhang, Min and Du, Liang and Yao, Ziyu (2024) Large Language Model Cascades with Mixture of Thought Representations for Cost-Efficient Reasoning | 0.585 | 3 | 1 | 100% |
| 8 | Freedman, David A (1975) On tail probabilities for martingales | 0.511 | 2 | 1 | 100% |
| 9 | Gergatsouli, Evangelia and Tzamos, Christos (2022) Online learning for min sum set cover and pandora’s box | 0.511 | 2 | 1 | 100% |
| 10 | Lee, Junghyun and Yun, Se-Young and Jun, Kwang-Sung (2024) A Unified Confidence Sequence for Generalized Linear Models, with Applications to Bandits | 0.511 | 2 | 1 | 100% |
Showing the top 10 of 72 scored citations.