Online Pandora's Box for Contextual LLM Cascading

Scientific Impact Assessment

Core Contribution

This paper formulates LLM cascading as an online contextual Pandora's Box problem with a novel two-phase structure: a query phase (which APIs to call and when to stop) and a selection phase (which generated output to deploy). The key structural novelty is the output-mediated feedback: querying a box reveals a stochastic output-cost pair rather than directly revealing a reward, and the downstream reward is observed only for the selected output. This departs from classical Pandora's Box formulations where opening a box directly reveals its value.

The paper's main algorithmic contribution is the COSMOS policy, which combines GMM-type estimation of contextual reservation indices (parameterized as generalized linear functions of context features) with UCB-style confidence bounds. Rather than estimating the full conditional output distributions of each API, the approach directly models and learns the Weitzman reservation indices—a practically motivated and theoretically elegant shortcut that avoids the curse of dimensionality in distribution estimation.

Methodological Rigor

The theoretical analysis is thorough and well-structured. Several aspects deserve highlight:

1. Regret Decomposition (Theorem 1): Under optimism, the per-period regret cleanly separates into reward estimation error (for selected outputs only) and index estimation errors (for queried APIs only). This decomposition is both intuitive and technically powerful, enabling separate treatment of the two learning challenges.

2. M-estimation approach for indices: The paper avoids standard GMM curvature requirements by formulating index estimation as M-estimation, where the loss function's first-order condition recovers the moment equation. Lemma 1 establishes population curvature that depends on the prediction error $\psi (x{)}^{\mathrm{\top }}(\rho -{\rho }_a)\backslash psi(x)^\backslash top(\backslash rho\; -\; \backslash rho\_a)$ rather than requiring full-rank identification of the parameter vector—a meaningful relaxation.

3. Known vs. Unknown Reward: The staged presentation (Section 4 for known reward, Section 5 for unknown) is pedagogically effective. The unknown-reward case introduces genuine technical challenges: the plug-in perturbation (Lemma 4) creates a mismatch between selected outputs (informing reward learning) and queried outputs (entering index estimation), necessitating Assumption 5 (anti-concentration of reward features).

4. Regret bound: The final $\tilde{O}([d+A(p_A+\sqrt{d{p}_A})]\sqrt{T})\backslash tilde\{O\}([d\; +\; A(p\_A\; +\; \backslash sqrt\{dp\_A\})]\backslash sqrt\{T\})$ bound is dimension-dependent but achieves the optimal $\sqrt{T}\backslash sqrt\{T\}$ rate. This improves upon the $\tilde{O}(T^{5\mathrm{/}6})\backslash tilde\{O\}(T^\{5/6\})$ rate of Atsidakou et al. (2024) for contextual Pandora's Box, though under stronger regularity assumptions (Assumption 2).

Potential Impact

Practical relevance: The LLM cascading motivation is timely and commercially significant. Organizations managing portfolios of LLM APIs face exactly this cost-quality tradeoff, and the paper provides a principled framework with formal guarantees. The model naturally captures token-based pricing (Remark 1) and the shared reward structure across APIs.

Theoretical contributions: The paper bridges several literatures—Pandora's Box, contextual bandits, GMM estimation—in a non-trivial way. The output-mediated feedback structure is a genuine modeling innovation that could influence future work on sequential search with intermediate observations. The connection between Weitzman indices and GMM moment conditions opens new directions for index-based learning in sequential decision problems.

Limitations of practical applicability: The generalized linear parametric assumptions on both the reward function and reservation indices may be restrictive in practice, where LLM output quality and costs may exhibit complex, non-linear context dependencies. The paper acknowledges this and suggests neural extensions as future work.

Timeliness & Relevance

The paper addresses a pressing need in the rapidly growing LLM deployment ecosystem. As organizations increasingly use multiple LLM APIs with heterogeneous cost-quality profiles, principled approaches to adaptive API selection become critical. The formulation captures a real operational decision that existing heuristic cascading methods (FrugalGPT, etc.) address without formal guarantees.

Strengths

1. Clean problem formulation that captures the essential structure of LLM cascading while remaining analytically tractable.

2. Direct index modeling avoids estimating full output distributions—a significant practical and theoretical advantage.

3. Self-correcting exploration: The regret decomposition ensures that frequently queried boxes have shrinking confidence radii, while infrequently queried boxes contribute negligibly to regret.

4. Comprehensive analysis covering both known and unknown reward regimes, with clear identification of where each assumption is needed.

5. The example in Section 2.1 effectively demonstrates why a one-shot API-as-arm bandit formulation incurs linear regret, justifying the sequential search framework.

Limitations

1. Assumption 2 (local mass around reservation thresholds) is non-trivial and may not hold when some APIs consistently dominate others across all contexts, as the probability mass above the reservation index could vanish.

2. Assumption 5 (anti-concentration) is somewhat restrictive—the authors acknowledge it fails for predictable contexts with certain feature structures (Remark 4).

3. No experiments: The paper is purely theoretical. Empirical validation on real LLM cascading scenarios would substantially strengthen the contribution and help assess the practical relevance of the parametric assumptions.

4. Single query per box per period: The restriction that each API is queried at most once per request, while consistent with existing cascading literature, limits applicability to settings where re-querying (e.g., with different prompts) might be valuable.

5. Dimension dependence: The $A\cdot p_{A}A\; \backslash cdot\; p\_A$ factor in the regret bound could be large when managing many APIs with high-dimensional context features.

Overall Assessment

This is a well-executed theoretical paper that establishes a novel and well-motivated connection between LLM cascading and online contextual Pandora's Box problems. The technical contributions—particularly the regret decomposition under optimism and the GMM-based index learning approach—are solid and could influence both the Pandora's Box and LLM systems literatures. The absence of empirical validation is a notable gap, but the theoretical foundations are rigorous and the problem formulation is compelling.