arXiv CSopen access

SCOPE: Cost-Efficient Model Selection for Compound AI Systems under Quality Constraints

arXiv:2606.00774v1 [cs.DB] 30 May 2026

SCOPE: Cost-Efficient Model Selection for Compound AI Systems under Quality Constraints Yiqian Huang

Shiqi Zhang∗

National University of Singapore Singapore [email protected]

National University of Singapore Singapore PyroWis AI Singapore [email protected]

Tianyuan Jin

Xiaokui Xiao

The Hong Kong University of Science and Technology (Guangzhou) China [email protected]

National University of Singapore Singapore [email protected]

Abstract A compound AI system consists of multiple LLM modules, together handling complex and multi-step tasks that exceed the capabilities of a single model. Existing systems often use a single expensive LLM across all modules to improve the result quality of the whole system. However, this configuration incurs prohibitive costs, particularly for data management and analytics tasks at scale, such as data manipulation. To this end, we formalize the problem of constrained LLM selection for compound AI systems, leveraging the diverse pricing and capabilities of different LLMs to achieve competitive quality at lower cost. Given a query dataset and a user-specified quality threshold, we aim to select an LLM for each module to minimize the system’s average cost while ensuring that overall quality meets the required threshold. To solve this problem, we propose SCOPE, a cost-efficient optimization algorithm. Unlike existing approaches that rely on expensive dataset-level evaluations, SCOPE exploits per-query results to rapidly estimate the system’s cost and quality, and constructs confidence bounds to guide the search for promising LLM combinations. Furthermore, SCOPE provides theoretical guarantees for meeting the quality threshold and achieving nearoptimal average cost. We evaluate SCOPE against 7 baselines on three data processing tasks, demonstrating that it outperforms all baselines. Under the same search budget and quality constraint, it finds solutions with up to 20× lower cost than the best competitor during the search and achieves up to 6× lower final cost in the returned solution. ACM Reference Format: Yiqian Huang, Shiqi Zhang, Tianyuan Jin, and Xiaokui Xiao. 2026. SCOPE: Cost-Efficient Model Selection for Compound AI Systems under Quality Constraints. In Proceedings of the 32nd ACM SIGKDD Conference on Knowledge Discovery and Data Mining V.2 (KDD ’26), August 09–13, 2026, ∗ Corresponding author.

This work is licensed under a Creative Commons Attribution 4.0 International License. KDD ’26, Jeju Island, Republic of Korea © 2026 Copyright held by the owner/author(s). ACM ISBN 979-8-4007-2259-2/2026/08 https://doi.org/10.1145/3770855.3818067

Jeju Island, Republic of Korea. ACM, New York, NY, USA, 16 pages. https: //doi.org/10.1145/3770855.3818067

1

Introduction

A compound AI system is a multi-module system in which each module is implemented by a specific agent powered by a large language model (LLM). The system as a whole processes complex and multi-step tasks beyond the capability of any single model and thus finds applications in many scenarios, such as question answering [11], software development [9], and data processing [22, 23]. To ensure high result quality, existing compound AI systems typically use a state-of-the-art LLM for every module and emphasize frontier system design. However, more advanced LLMs typically incur higher inference costs. This monetary overhead becomes prohibitive for tasks that require digesting large volumes of data, which is common in the data management and analytics area [15]. To exemplify, in data imputation, which fills missing entries in a table based on observed values, employing the flagship GPT-5.2 [20] across all modules of UniDM [23] costs around $180, 000 on a dataset with one million rows, each containing ten entities with rich semantic value spaces. To mitigate this immense overhead, we formalize a new problem, constrained LLM selection for compound AI systems, which shifts the goal from quality alone to explicitly accounting for cost. Given an 𝑁 -module compound AI system, a candidate LLM set, a query dataset, and a quality threshold, this problem aims to assign a specific LLM to each module to minimize the system’s average cost over the dataset while ensuring that the average quality meets the threshold. This formulation exploits the cost–quality Pareto frontier observed in modern LLMs [34], where models exhibit diverse pricing and complementary capabilities, creating a rich search space for optimization. By aligning model capabilities with the varying complexity of module-specific tasks, constrained LLM selection for compound AI systems admits solutions that achieve high quality at significantly lower cost. Solving this problem remains challenging, since one must carefully balance cost and quality, using only limited observations of the system’s performance on the given dataset. A natural approach is to treat the system as a black box and apply generic constrained

KDD ’26, August 09–13, 2026, Jeju Island, Republic of Korea

optimization methods, such as Bayesian optimization [29, 30] and bandit algorithms [28, 31]. Specifically, these solutions search over possible LLM assignments without knowing the system’s internal structure, yet they fail to guarantee convergence to a near-optimal assignment that satisfies the quality constraint at minimum cost. Moreover, they require a prohibitive number of trials, each of which executes the system on the entire dataset, often incurring search costs that even exceed the potential savings. Recently, compoundAI-specific methods [3, 25] attempt to accelerate the search by making strong structural assumptions. For instance, Abacus [25] assumes independence between modules to estimate total cost and quality, while LLMSelector [3] relies on monotonicity, assuming that upgrading a module’s model always improves global quality. Unfortunately, these assumptions rarely hold in practice. Relying on ad-hoc heuristics without theoretical guarantees, these methods often fail to strictly satisfy the quality threshold. To bridge this gap, we propose SCOPE, a cost-efficient optimization algorithm with rigorous theoretical guarantees. In contrast to existing methods that rely on coarse-grained dataset-level evaluations, SCOPE uses a query-level search strategy. Specifically, it treats individual query evaluations as atomic observations to iteratively tighten statistically valid confidence bounds on both cost and quality. The query-level granularity allows the algorithm to quickly prune suboptimal LLM assignments without full-dataset evaluations, while the confidence bounds guide the search toward near-optimal solutions in a principled way. To the best of our knowledge, SCOPE is the first to provide theoretical guarantees for this noisy constrained optimization problem, ensuring that the returned solution simultaneously (i) satisfies the quality threshold with high probability and (ii) has a cost that converges to the optimum as the search budget increases. In experiments, we extensively evaluate SCOPE against seven competitors across three distinct data processing tasks involving compound AI systems. Our evaluation spans a massive search space of tens of candidate models and millions of potential LLM assignments. Notably, SCOPE strictly satisfies the quality constraint while reducing average costs by over 20× compared to the best competing baseline. Even at the maximum budget, it achieves a 6× cost reduction. Furthermore, on test-time datasets, SCOPE demonstrates robust generalization, attaining an average cost of 2–5% of a high-quality reference configuration while maintaining competitive average quality. To summarize, we make the following contributions in this work: • We formalize constrained LLM selection for compound AI systems as a constrained optimization problem (Section 2). • We propose SCOPE, a cost-efficient optimization algorithm that reduces the search cost (Section 3). • We provide theoretical guarantees on both the cost and the quality of the solution returned by SCOPE (Section 4). • We conduct experiments showing that SCOPE outperforms existing methods (Section 6).

2 Preliminaries 2.1 Problem Formulation Compound AI system. Consider a query dataset Q (where |Q| = 𝑄), a set of candidate LLMs M (where |M| = 𝑀), and a compound

Yiqian Huang, Shiqi Zhang, Tianyuan Jin, and Xiaokui Xiao

Table 1: Frequently used notations. Notation

Description

𝑁 M, 𝑀 Q, 𝑄 𝜽, Θ ℓ𝑠 (𝜽, 𝑞) ℓ𝑐 (𝜽, 𝑞) 𝑠 (𝜽 ), 𝑐 (𝜽 ) 𝑔 (𝜽 ) ℓ𝑔 (𝜽, 𝑞) 𝑦𝑐,𝑡 , 𝑦𝑔,𝑡

The number of modules in the system. The candidate LLM set with | M | = 𝑀. The query dataset with | Q | = 𝑄. A configuration 𝜽 = [𝜃 1 , . . . , 𝜃 𝑁 ] from Θ = M 𝑁 . Query-wise quality of 𝜽 and 𝑞. Query-wise cost of 𝜽 and 𝑞. Average quality and average cost of 𝜽 . Constraint function (= 𝑠 0 − 𝑠 (𝜽 ) ). Query-wise constraint function (= 𝑠 0 − ℓ𝑠 (𝜽, 𝑞) ). The observations made by an algorithm at time 𝑡 .

AI system consisting of 𝑁 modules, each integrated with an LLM. A configuration is defined as a vector 𝜽 = [𝜃 1, . . . , 𝜃 𝑁 ], where each 𝜃 𝑖 ∈ M denotes the LLM selected for the 𝑖-th module. The configuration space is denoted by Θ = M 𝑁 , representing the set of all possible configurations. For a configuration 𝜽 ∈ Θ and a query 𝑞 ∈ Q, system execution is measured by two metrics: • ℓ𝑠 (𝜽, 𝑞) ∈ [0, 1], the expected quality (e.g., accuracy) of the system’s output on query 𝑞 under configuration 𝜽 ; • ℓ𝑐 (𝜽, 𝑞) ∈ [𝐶 min, 𝐶 max ], the corresponding expected monetary cost, bounded by known limits 𝐶 min and 𝐶 max . We focus on the average quality and average cost over the dataset Q, which are defined, respectively, as 1 ∑︁ 1 ∑︁ ℓ𝑐 (𝜽, 𝑞), 𝑠 (𝜽 ) = ℓ𝑠 (𝜽, 𝑞). 𝑐 (𝜽 ) = 𝑄 𝑄 𝑞∈ Q

𝑞∈ Q

In practice, users typically begin with a reference configuration 𝜽 0 (e.g., employing a powerful LLM for all modules), which yields high quality 𝑠 (𝜽 0 ) but incurs a high cost. Given 𝜖 ∈ (0, 1) specifying the maximum allowable quality degradation, we define the quality threshold as 𝑠 0 = (1 − 𝜖) · 𝑠 (𝜽 0 ). Let 𝑔(𝜽 ) = 𝑠 0 − 𝑠 (𝜽 ) and ℓ𝑔 (𝜽, 𝑞) = 𝑠 0 − ℓ𝑠 (𝜽, 𝑞) for each 𝑞 ∈ Q. We define constrained LLM selection for compound AI systems as follows. Problem 1 (Constrained LLM Selection for Compound AI Systems). Given an 𝑁 -module compound AI system, a dataset Q, a configuration space Θ = M 𝑁 , and a reference configuration 𝜽 0 ∈ Θ with known quality 𝑠 (𝜽 0 ), the objective is to find a configuration that minimizes the average cost while satisfying the quality constraint: 𝜽 ★ ∈ argmin 𝑐 (𝜽 ).

(1)

𝜽 ∈Θ: 𝑔 (𝜽 ) ≤0

A configuration 𝜽 ∈ Θ is called feasible if it satisfies 𝑔(𝜽 ) ≤ 0. By definition, 𝜽 ★ exists since at least one configuration 𝜽 0 is feasible. Notations. Throughout this paper, we denote [𝑛] = {1, . . . , 𝑛} and N = {0, 1, . . . }. A boldface lowercase letter 𝒙 represents a vector, and a boldface uppercase letter 𝑿 represents a matrix, where (𝑿 )𝑎,𝑏 denotes the value in its 𝑎-th row and 𝑏-th column. An algorithm for Problem 1 runs over discrete time steps 𝑡 ∈ N. At each time 𝑡, it selects a pair (𝜽𝑡 , 𝑞𝑡 ) ∈ Θ × Q to evaluate (hereafter, to observe) and receives a pair of noisy observations of ℓ𝑐 (𝜽𝑡 , 𝑞𝑡 ) and ℓ𝑔 (𝜽𝑡 , 𝑞𝑡 ), denoted by (𝑦𝑐,𝑡 , 𝑦𝑔,𝑡 ). Table 1 summarizes frequently used notations.

SCOPE: Cost-Efficient Model Selection for Compound AI Systems under Quality Constraints

2.2

Existing Solutions

Problem 1 is challenging because both 𝑐 and 𝑔 are expensive blackbox functions that do not admit closed-form expressions. A natural baseline is to cast it as a generic constrained optimization problem, where one has access only to noisy observations (i.e., values with random noise) of 𝑐 (𝜽 ) and 𝑔(𝜽 ). Under this framing, one could apply sequential search methods for constrained optimization, such as constrained Bayesian optimization, among others [28–31, 35]. Generic optimization approaches. Generic optimization methods, such as Bayesian optimization (BO) [29, 30] and bandit algorithms [28, 31, 35], have been used to tune compound AI systems for cost or quality [8, 14, 21], and can be rigorously extended to handle the quality constraint. In the unconstrained setting, these methods come with theoretical guarantees in terms of regret, which quantify how quickly the returned configuration approaches the optimal configuration. Such guarantees typically rely on standard assumptions: informally, similar configurations yield similar function values, so that past evaluations can generalize to unobserved configurations. Compound-AI-specific approaches. Other recent methods aim to improve empirical search efficiency by making extra assumptions about the compound AI system, rather than treating it as a pure black box. For example, Abacus [25], the optimizer used by Palimpzest [16], estimates 𝑐 (·) and 𝑠 (·) by assuming independence across modules and employing additive or multiplicative estimators. LLMSelector [3] assumes that quality is monotonically non-decreasing when upgrading LLMs according to a fixed ranking, and accordingly proposes a round-robin procedure that updates one module at a time. LLAMBO [17] treats the LLM itself as an estimation model, using its internal knowledge and the observation history to predict the cost and quality of unseen configurations. Limitations. Existing approaches have two main limitations in the noisy constrained setting [29, 31]. First, it is hard for them to guarantee correctness and effectiveness at the same time. Here, correctness means the returned solution 𝜽 out is feasible, i.e., 𝑔(𝜽 out ) ≤ 0, and effectiveness means its cost is close to the best feasible value, i.e., 𝑐 (𝜽 out ) ≈ 𝑐 (𝜽 ★). For instance, methods such as CONFIG [31] prioritize effectiveness but risk violating correctness, while SafeOpt [28] ensures correctness but often converges to suboptimal solutions. While recent work on constrained expected improvement (cEI) [29], a variant of constrained BO, theoretically addresses both, it relies on a noiseless assumption (i.e., without random noise) that does not hold for stochastic LLM outputs. Second, existing approaches remain cost-inefficient as they do not fully exploit query-level signals ℓ𝑐 and ℓ𝑔 . By treating average cost and average quality as pure black-box functions, these methods must evaluate configurations on the entire dataset Q to obtain an observed signal for average cost or quality. As shown in Section 6, fully evaluating an infeasible configuration with 𝑄 = 500 can cost around $12, whereas analyzing just a few queries using ℓ𝑐 and ℓ𝑔 could reveal infeasibility immediately. Yet, it remains an open problem to exploit query-level signals without compromising theoretical guarantees. These limitations motivate a principled solution that addresses Problem 1 by integrating rigorous guarantees with a cost-efficient, query-level evaluation scheme.

KDD ’26, August 09–13, 2026, Jeju Island, Republic of Korea

Algorithm 1: SCOPE (Λ, 𝛿, 𝛼, 𝜃 base ) Input: Budget Λ > 0, failure probability 𝛿 ∈ (0, 1), parameter 𝛼 ∈ (0, 1/2), base model 𝜃 base ∈ M Output: Returned solution 𝜽 out , stopping time 𝜏 𝑡0 1 𝑡 0 , {𝜽𝑖 , 𝑞𝑖 , 𝑦𝑐,𝑖 , 𝑦𝑔,𝑖 }𝑖=1 ← Calibrate(𝜃 base ) (Algorithm 2); 2 Define 𝐿𝜁 ,𝑡 , 𝑈𝜁 ,𝑡 ← (4) for 𝑡 ∈ N, 𝜁 ∈ {𝑐, 𝑔}; 3 𝑡 ← 𝑡 0 , 𝜽 out ← 𝜽 0 , 𝑈 out ← 𝑈𝑐,𝑡 0 (𝜽 0 ); 4 for 𝑖 = 1, 2, . . . do 5 𝜽 cand ← argmin 𝐿𝑐,𝑡 (𝜽 ); 𝜽 ∈Θ:𝐿𝑔,𝑡 (𝜽 ) ≤ −𝑖 −𝛼 Sort Q as {𝑞 (1) , . . . , 𝑞 (𝑄 ) } by decreasing 𝜑𝑖 (𝑞) in (9);

6

for 𝑗 = 1, . . . , 𝑄 do 𝑡 ← 𝑡 + 1; Observe at (𝜽 cand, 𝑞 ( 𝑗 ) ) to obtain (𝑦𝑐,𝑡 , 𝑦𝑔,𝑡 ); if 𝑈𝑐,𝑡 (𝜽 cand ) ≤ 𝑈 out and min{𝑈𝑔,𝑡 (𝜽 cand ), 𝑈𝑔,𝑡 −1 (𝜽 cand )} ≤ 0 then 𝑈 out ← 𝑈𝑐,𝑡 (𝜽 cand ); 𝜽 out ← 𝜽 cand ; Í𝑡 if 𝑡 ′ =1 𝑦𝑐,𝑡 ′ > Λ then break all loops; if 𝐿𝑔,𝑡 (𝜽 cand ) > 0 or 𝐿𝑐,𝑡 (𝜽 cand ) > 𝑈 out then break the 𝑗-loop;

7 8 9 10

11 12 13 14

15

return (𝜽 out, 𝜏 ← 𝑡)

3

SCOPE

We propose Sequential Confidence-bound-based Optimization via Partial Evaluation (SCOPE), which solves Problem 1 with guarantees of correctness and effectiveness. When 𝑄 = 1, SCOPE also applies to generic noisy constrained optimization.

3.1

Main Procedure

At the core of SCOPE are carefully designed confidence bounds for the cost 𝑐 (·) and the constraint 𝑔(·). Given a failure probability 𝛿 ∈ (0, 1), for time 𝑡 ∈ N, configuration 𝜽 ∈ Θ, and function 𝜁 ∈ {𝑐, 𝑔}, SCOPE maintains lower and upper bounds 𝐿𝜁 ,𝑡 (𝜽 ) and 𝑈𝜁 ,𝑡 (𝜽 ) such that they enclose the true function values with probability at least 1 − 𝛿:   Pr ∀𝜁 , 𝑡, 𝜽 : 𝐿𝜁 ,𝑡 (𝜽 ) ≤ 𝜁 (𝜽 ) ≤ 𝑈𝜁 ,𝑡 (𝜽 ) ≥ 1 − 𝛿.

(2)

Building on these bounds, SCOPE proceeds in iterations. In each iteration 𝑖 ∈ {1, 2, . . . }, SCOPE selects a candidate configuration 𝜽 cand that is promising under the current bounds and then evaluates 𝜽 cand sequentially on queries in Q until the search budget is exhausted. Notably, the guarantees of SCOPE are ensured by two key mechanisms. (1) Candidate selection: In iteration 𝑖, it selects 𝜽 cand using a dynamic constraint 𝐿𝑔,𝑡 (𝜽 ) ≤ −𝑖 −𝛼 , where 𝛼 ∈ (0, 1/2) is a fixed parameter, to filter out candidates that are likely infeasible. Among the remaining candidates, 𝜽 cand is chosen greedily by minimizing the cost lower bound 𝐿𝑐,𝑡 (𝜽 ). (2) Sequential query evaluation: After selecting 𝜽 cand , SCOPE evaluates it on queries 𝑞 (1) , . . . , 𝑞 (𝑄 ) ∈ Q in decreasing order of

KDD ’26, August 09–13, 2026, Jeju Island, Republic of Korea

a score 𝜑𝑖 (𝑞). This score is defined to quantify how much information we gain from evaluating 𝑞 and, in turn, to tighten the bounds for both 𝑐 and 𝑔 using as few observations as possible. In addition, the cost efficiency of SCOPE hinges on two further design choices that exploit query-level signals. (3) Bound calibration: During initialization, SCOPE invokes a subroutine, Calibrate, which calibrates accurate confidence bounds within a small initial budget. (4) Pruning mechanism: SCOPE incorporates a pruning mechanism enabled by the sequential, query-level evaluation. As the bounds are updated, it stops evaluating 𝜽 cand early once 𝜽 cand appears infeasible (i.e., 𝐿𝑔,𝑡 (𝜽 cand ) > 0) or cannot improve on the current best solution in terms of cost. Algorithm 1 gives the pseudocode of SCOPE; we defer the description of Calibrate to Section 3.2 and defer the definition of 𝐿𝜁 ,𝑡 , 𝑈𝜁 ,𝑡 , and 𝜑𝑖 to Section 3.3. It takes four additional inputs: a search budget Λ > 0 which limits the cumulative monetary cost of observing 𝑦𝑐,𝑡 over time, a failure probability 𝛿 ∈ (0, 1) used in the confidence bounds, a trade-off parameter 𝛼 ∈ (0, 1/2), and a base model 𝜃 base ∈ M, which represents a user-chosen cost-efficient LLM used by the Calibrate subroutine. In Line 1, the algorithm first invokes Calibrate with parameter 𝜃 base , which performs 𝑡 0 initial observations, and sets 𝑡 ← 𝑡 0 . In Lines 2–3, the algorithm initializes the confidence bounds 𝐿𝜁 ,𝑡 and 𝑈𝜁 ,𝑡 , the current best configuration 𝜽 out ← 𝜽 0 , and the current best upper bound 𝑈 out . After initialization, at each outer loop 𝑖 (Line 4), SCOPE selects a configuration 𝜽 cand according to the selection criterion in Line 5. Subsequently, the queries in Q are ordered as 𝑞 (1) , . . . , 𝑞 (𝑄 ) in decreasing order of the query-wise surrogate uncertainty 𝜑𝑖 (𝑞 ( 𝑗 ) ) (Line 6), and are sequentially evaluated with 𝜽 cand in the inner 𝑗-loop (Line 7). At each inner iteration 𝑗, the algorithm increments the time 𝑡 by one and observes (𝜽 cand, 𝑞 ( 𝑗 ) ) to obtain 𝑦𝑐,𝑡 and 𝑦𝑔,𝑡 (Line 9), which in turn refines the confidence bounds at time 𝑡. In Line 10, if 𝑈𝑐,𝑡 (𝜽 cand ) ≤ 𝑈 out and min{𝑈𝑔,𝑡 (𝜽 cand ), 𝑈𝑔,𝑡 −1 (𝜽 cand )} ≤ 0 hold (i.e., 𝜽 cand is certified feasible with high probability at either times), the algorithm updates 𝑈 out and 𝜽 out . Additionally, if the search budget is exhausted, the algorithm breaks out of all loops and terminates (Line 13). Otherwise, 𝜽 cand is subject to early pruning where SCOPE breaks the 𝑗-loop (Line 14) if 𝐿𝑔,𝑡 (𝜽 cand ) > 0 or 𝐿𝑐,𝑡 (𝜽 cand ) > 𝑈 out . Finally, SCOPE returns (𝜽 out, 𝜏) where 𝜏 = 𝑡 represents the stopping time after which it makes no further observations.

3.2

Bound Calibration

To identify the rough scale of confidence bounds for 𝑐 (·) and 𝑔(·), SCOPE invokes a heuristically designed Calibrate subroutine. Calibrate proceeds in a hybrid manner: it first collects observations from a large, diverse pool of configurations using a single query, and then iteratively doubles the size of the query set while halving the configuration pool. As a result, higher-quality configurations receive additional evaluation, until a single remaining configuration in the pool is evaluated on the entire query set. This design is motivated by three empirical observations. First, cost differences are mainly driven by the selected LLMs rather than by which query is executed, since model prices often differ by orders of magnitude. As a result, evaluating many diverse configurations on only a few queries provides early estimates of the cost

Yiqian Huang, Shiqi Zhang, Tianyuan Jin, and Xiaokui Xiao

Algorithm 2: Calibrate (𝜃 base ) Input: Base model 𝜃 base ∈ M Output: Time step 𝑡 0 , history {(𝜽𝑡 , 𝑞𝑡 , 𝑦𝑐,𝑡 , 𝑦𝑔,𝑡 )}𝑡𝑡0=1 1 𝑡 0 ← 0, Θinit ← (3), Q0 ← ∅; (1) , . . . , 𝑞 (𝑄 ) } in a random order; 2 Sort Q as {𝑞 3 for 𝑗 = 1, . . . , ⌈log2 (𝑄 + 1)⌉ do 𝑗 −1 4 Q 𝑗 ← {𝑞 (1) , . . . , 𝑞 (min{2 ,𝑄 } ) }; 5 foreach 𝜽, 𝑞 ∈ Θinit × (Q 𝑗 \ Q 𝑗 −1 ) do 6 𝑡 0 ← 𝑡 0 + 1; 7 Observe at (𝜽, 𝑞) to obtain (𝑦𝑐,𝑡0 , 𝑦𝑔,𝑡0 ); Θinit ← top-⌈|Θinit |/2⌉ configurations in Θinit ranked by Í 𝑆 (𝜽 ), where 𝑆 (𝜽 ) = − 𝑡 ∈ [𝑡0 ]: 𝜽𝑡 =𝜽, 𝑞𝑡 ∈ Q 𝑗 𝑦𝑔,𝑡 ;

8

9

return (𝑡 0, {(𝜽𝑡 , 𝑞𝑡 , 𝑦𝑐,𝑡 , 𝑦𝑔,𝑡 )}𝑡𝑡0=1 )

scale across configurations. Second, evaluating a high-potential configuration on only a few queries is often insufficient, because the query-wise quality ℓ𝑠 (𝜽, 𝑞) can vary significantly across queries 𝑞 ∈ Q. Given a limited search budget Λ, we increase the number of sampled queries only for configurations that appear high-quality, to obtain a reliable estimate of their average quality. Finally, it is often beneficial to choose a lightweight model 𝜃 base and focus on configurations related to this model, thereby saving search cost by avoiding evaluations of configurations that include many expensive models. The detailed pseudocode is shown in Algorithm 2, which takes as input the base model 𝜃 base ∈ M. The subroutine first constructs an initial pool Θinit ⊆ Θ as  Í𝑁 Θinit = [𝜃 1, . . . , 𝜃 𝑁 ] ∈ Θ : 𝑖=1 1{𝜃 𝑖 ≠ 𝜃 base } ≤ 1 , (3) and randomly shuffles Q as {𝑞 (1) , . . . , 𝑞 (𝑄 ) }. Then, it runs for ⌈log2 (𝑄+ 1)⌉ rounds. In round 𝑗, it evaluates each remaining configuration in 𝑗 −1 Θinit on additional queries in Q 𝑗 \Q 𝑗 −1 , where Q 𝑗 = {𝑞 (1) , . . . , 𝑞 (min{2 ,𝑄 } ) }. Afterward, it retains the top half of configurations ranked by their cumulative observed quality over Q 𝑗 and discards the rest. By the final round, the pool is reduced to a single configuration, which has been evaluated on all 𝑄 queries.

3.3

Confidence Bounds

For each 𝜁 ∈ {𝑐, 𝑔}, 𝑡 ∈ N, and 𝜽 ∈ Θ, the confidence bounds in Line 2 are of the following form: 𝐿𝜁 ,𝑡 (𝜽 ) = 𝜇¯𝜁 ,𝑡 (𝜽 ) − 𝛽𝜁 ,𝑡 𝜎¯𝜁 ,𝑡 (𝜽 ), 𝑈𝜁 ,𝑡 (𝜽 ) = 𝜇¯𝜁 ,𝑡 (𝜽 ) + 𝛽𝜁 ,𝑡 𝜎¯𝜁 ,𝑡 (𝜽 ).

(4)

Here, 𝜇¯𝜁 ,𝑡 (𝜽 ) is the surrogate mean estimating 𝜁 (𝜽 ), 𝜎¯𝜁 ,𝑡 (𝜽 ) is the surrogate standard deviation representing the uncertainty in this estimate, and the coefficient 𝛽𝜁 ,𝑡 scales this uncertainty to ensure valid confidence bounds. To instantiate (4), we fix hyperparameters 𝑅𝑐 , 𝑅𝑔 ≥ 0, 𝐵𝑐 , 𝐵𝑔 > 0, and a symmetric positive definite (SPD) kernel function 𝑘 : Θ × Θ → R with 𝑘 (𝜽, 𝜽 ) = 1 for all 𝜽 ∈ Θ. Note that these hyperparameters are used in Assumptions 1–2 (see Section 4.1), under which we derive the guarantees. 𝜇¯𝜁 ,𝑡 (𝜽 ) and 𝜎¯𝜁 ,𝑡 (𝜽 ) are defined based on standard zero-mean Gaussian process (GP) regression with kernel 𝑘, as described below.

SCOPE: Cost-Efficient Model Selection for Compound AI Systems under Quality Constraints

Definition 1 (Zero-mean GP regression [24]). Fix a kernel 𝑘 : Θ × 𝐽 Θ → R and a constant 𝜆 > 0. Given 𝐽 observations {(𝜽 (𝑖 ) , 𝑦 (𝑖 ) )}𝑖=1 (𝑖 ) in an arbitrary order, where 𝑦 is obtained by observing a particular function 𝑓 : Θ → R at 𝜽 (𝑖 ) ∈ Θ, define 𝒚 = [𝑦 (1) , . . . , 𝑦 ( 𝐽 ) ] ⊤,

𝒙 = [𝜽 (1) , . . . , 𝜽 ( 𝐽 ) ],

𝒌𝒙 (𝜽 ) = [𝑘 (𝜽, 𝜽 (1) ), . . . , 𝑘 (𝜽, 𝜽 ( 𝐽 ) )] ⊤, (𝑲𝒙 )𝑎,𝑏 = 𝑘 (𝜽 (𝑎) , 𝜽 (𝑏 ) ),

𝜇ˆ𝒙,𝒚 (𝜽 ) = 𝒌𝒙 (𝜽 ) ⊤ (𝑲𝒙 + 𝜆𝑰 ) −1𝒚, (5)

In particular, if 𝒚 = ∅, then 𝜇ˆ𝒙,𝒚 (𝜽 ) = 0 and 𝜎ˆ𝒙,𝒚 (𝜽 ) 2 = 𝑘 (𝜽, 𝜽 ). For each 𝑡 ∈ N under SCOPE, define J𝑞,𝑡 = { 𝑗 ∈ [𝑡] : 𝑞 𝑗 = 𝑞}, ordered as 𝑗𝑞 (1) < · · · < 𝑗𝑞 (|J𝑞,𝑡 |), and denote 𝐽max,𝑡 = max 𝐽𝑞,𝑡 .

∀𝑡 ∈ N, 𝑦𝑐,𝑡 = ℓ𝑐 (𝜽𝑡 , 𝑞𝑡 ) + 𝜂𝑐,𝑡 ,

𝑦𝑔,𝑡 = ℓ𝑔 (𝜽𝑡 , 𝑞𝑡 ) + 𝜂𝑔,𝑡 ,

(10)

where 𝜂𝑐,𝑡 and 𝜂𝑔,𝑡 are zero-mean random variables. For each 𝜁 ∈ {𝑐, 𝑔}, the sequence {𝜂𝜁 ,𝑡 }𝑡∞=1 is conditionally 𝑅𝜁 -sub-Gaussian, i.e.,
∀𝑡 ∈ N, ∀𝑢 ∈ R, E[exp (𝑢 · 𝜂𝜁 ,𝑡 )|F𝑡 −1 ] ≤ exp (𝑢 2 𝑅𝜁2 )/2 ,

Assumption 2 (Boundedness in RKHS). Let H𝑘 be the reproducing kernel Hilbert space (RKHS) induced by 𝑘, with norm ∥ · ∥ H𝑘 . 1 We assume for each 𝑞 ∈ Q, ∥ℓ𝑐 (·, 𝑞)∥ H𝑘 ≤ 𝐵𝑐 and ∥ℓ𝑔 (·, 𝑞) ∥ H𝑘 ≤ 𝐵𝑔 .

Then, for any 𝜽 ∈ Θ, the zero-mean GP regression defines

𝐽𝑞,𝑡 = |J𝑞,𝑡 |,

Assumption 1 (Sub-Gaussian noise). The observations satisfy

𝑡 −1 . where F𝑡 −1 is the 𝜎-algebra generated by {𝜽𝑖 , 𝑞𝑖 , 𝑦𝑐,𝑖 , 𝑦𝑔,𝑖 }𝑖=1

𝑎, 𝑏 ∈ [𝐽 ].

(𝜎ˆ𝒙,𝒚 (𝜽 )) 2 = 𝑘 (𝜽, 𝜽 ) − 𝒌𝒙 (𝜽 ) ⊤ (𝑲𝒙 + 𝜆𝑰 ) −1 𝒌𝒙 (𝜽 ),

KDD ’26, August 09–13, 2026, Jeju Island, Republic of Korea

(6)

𝑞∈ Q

Interpretation. Regarding Assumption 1, upper bounds for 𝑅𝑐 and 𝑅𝑔 are often available in practice. For example, if system evaluations satisfy 𝑦𝑐,𝑡 ∈ [𝐶 min, 𝐶 max ] and 𝑦𝑔,𝑡 ∈ [𝑠 0 − 1, 𝑠 0 ], a sufficient choice is 𝑅𝑐 = (𝐶 max − 𝐶 min )/2 and 𝑅𝑔 = 1/2. If evaluations are noiseless, it suffices to set any 𝑅𝑐 = 𝑅𝑔 ≥ 0. In Assumption 2, 𝐵𝜁 bounds how similar ℓ𝜁 (𝜽, 𝑞) and ℓ𝜁 (𝜽 ′, 𝑞) are for every 𝑞 ∈ Q, 𝜁 ∈ {𝑐, 𝑔}, and 𝜽, 𝜽 ′ ∈ Θ. In particular, one can infer the following property: √︁ |ℓ𝜁 (𝜽, 𝑞) − ℓ𝜁 (𝜽 ′, 𝑞)| ≤ 𝐵𝜁 2 − 2𝑘 (𝜽, 𝜽 ′ ).

Let 𝒙𝑞,𝑡 = [𝜽 𝑗𝑞 (1) , . . . , 𝜽 𝑗𝑞 ( 𝐽𝑞,𝑡 ) ], 𝒚𝜁 ,𝑞,𝑡 = [𝑦𝜁 ,𝑗𝑞 (1) , . . . , 𝑦𝜁 ,𝑗𝑞 ( 𝐽𝑞,𝑡 ) ] ⊤ if 𝐽𝑞,𝑡 > 0, otherwise 𝒙𝑞,𝑡 = 𝒚𝜁 ,𝑞,𝑡 = ∅. We then define the surrogate mean and standard deviation in (4) as ! ∑︁ 𝜎ˆ𝒙𝑞,𝑡 ,𝒚𝜁 ,𝑞,𝑡 (𝜽 ) 2 ∑︁ 𝜇ˆ𝒙𝑞,𝑡 ,𝒚𝜁 ,𝑞,𝑡 (𝜽 ) 2 , 𝜎¯𝜁 ,𝑡 (𝜽 ) = , 𝜇¯𝜁 ,𝑡 (𝜽 ) = 𝑄 𝑄

Since Θ is finite in Problem 1, for any SPD kernel 𝑘 there exist 𝐵𝑐 , 𝐵𝑔 < ∞ such that Assumption 2 holds. In implementation, this allows us to adopt a commonly used kernel and treat 𝐵𝑐 and 𝐵𝑔 as hyperparameters, following prior work [27, 31].

(7)

Recall that 𝜏 is the stopping time after which the algorithm makes no further observations, and 𝜽 out is the returned configuration. We say the algorithm is 𝛿-correct if Pr[𝑔(𝜽 out ) ≤ 0] ≥ 1 − 𝛿, where the randomness is over the observations. We measure effectiveness by simple regret, defined as SR(𝜏) = 𝑐 (𝜽 out ) − 𝑐 (𝜽 ★), where 𝑐 (𝜽 ★) is the optimal cost defined in (1). The following theorem shows that the confidence bounds hold with high probability. All proofs are provided in Appendix C.

𝑞∈ Q

𝑞∈ Q

where we apply Definition 1 to 𝑓 = ℓ𝜁 (·, 𝑞) with 𝒙𝑞,𝑡 and 𝒚𝜁 ,𝑞,𝑡 for each 𝑞 ∈ Q, and set 𝜆 = max{𝑅𝑐2, 𝑅𝑔2, 10−9 } in Definition 1 for simplicity. The coefficient 𝛽𝜁 ,𝑡 is based on the maximum information gain [27], defined as 𝛾 (𝐽 ) = max𝐴⊆Θ: |𝐴| ≤ 𝐽 12 log det(𝑰 + 𝜆 −1 𝑲𝐴 ), ′

′

where 𝑲𝐴 ∈ R 𝐽 ×𝐽 (𝐽 ′ ≤ 𝐽 ) is defined by (𝑲𝐴 )𝑖,𝑗 = 𝑘 (𝜽 (𝑖 ) , 𝜽 ( 𝑗 ) ), ′ with 𝐴 = {𝜽 (1) , . . . , 𝜽 ( 𝐽 ) } ⊆ Θ in any order. Fix 𝛿 ∈ (0, 1). Given 𝛾 (𝐽 ) and 𝜆 above, we set 𝛽𝜁 ,𝑡 as ! √︂  √︁ 𝑅𝜁 2𝑄  𝛽𝜁 ,𝑡 = 𝑄 · 𝐵𝜁 + √ 2 𝛾 (𝐽max,𝑡 ) + log , (8) 𝛿 𝜆 where 𝐽max,𝑡 is defined in (6). Furthermore, in Line 6 in iteration 𝑖 at time 𝑡, we define 𝜑𝑖 (𝑞) = 𝜎ˆ𝒙𝑞,𝑡 ,𝒚𝑐,𝑞,𝑡 (𝜽 cand ),

(9)

where 𝜎ˆ𝒙𝑞,𝑡 ,𝒚𝑐,𝑞,𝑡 is defined in (7). By definition, one can verify that it also equals 𝜎ˆ𝒙𝑞,𝑡 ,𝒚𝑔,𝑞,𝑡 .

4 Theoretical Analysis 4.1 Assumptions We state the theoretical assumptions under which SCOPE’s guarantees are derived. They extend the standard frequentist setting for generic constrained optimization [2, 6, 27] to 𝑄 ≥ 1. When 𝑄 = 1, they reduce to the standard ones in [27]. These assumptions are parameterized by 𝑅𝑐 , 𝑅𝑔 ≥ 0, 𝐵𝑐 , 𝐵𝑔 > 0, and the SPD kernel 𝑘 with 𝑘 (𝜽, 𝜽 ) = 1 for all 𝜽 ∈ Θ.

4.2

Guarantees

Theorem 4.1. Fix 𝛿 ∈ (0, 1). For any 𝑡 ∈ N, 𝜁 ∈ {𝑐, 𝑔}, and 𝜆 > 0 which is used in Definition 1, let the confidence bounds in (4) be defined using (8) and (7). Under Assumptions 1–2, the resulting bounds satisfy the high-probability event in (2). The next theorem shows that SCOPE is 𝛿-correct and provides an explicit upper bound on SR(𝜏). Theorem 4.2. Fix Λ > 0, 𝛿 ∈ (0, 1), and 𝛼 ∈ (0, 1/2), and let 𝑡 0 be the time returned by Calibrate in Line 1. Under Assumptions 1–2, SCOPE is 𝛿-correct. Moreover, for any 𝜏 returned by SCOPE, with probability at least 1 − 𝛿, the simple regret satisfies SR(𝜏) ≤ √︁

A

(11)

(𝜏 − 𝑡 0 ) − B · (𝜏 − 𝑡 0 ) 2𝛼 − C

whenever 𝑔(𝜽 ★) < 0 and (𝜏 − 𝑡 0 ) − B · (𝜏 − 𝑡 0 ) 2𝛼 − C > 0, where √︁ 2 A = 8𝛽𝑐,𝜏 𝑄 (𝜆 + 1)𝛾 (𝜏), B = 16𝑄 (𝜆 + 1)𝛽𝑔,𝜏 𝛾 (𝜏), C = 𝑄 ⌈(−𝑔(𝜽 ★)) −1/𝛼 ⌉. 1 Concretely, RKHS H is a collection of functions equipped with an inner product 𝑘 ⟨·, ·⟩H𝑘 such that for every 𝜽 ∈ Θ and 𝑓 ∈ H𝑘 , it holds that 𝑘 (𝜽, ·) ∈ H𝑘 and

⟨𝑓 , 𝑘 (𝜽, ·) ⟩H𝑘 = 𝑓 (𝜽 ) . The norm is then ∥ 𝑓 ∥ H𝑘 =

√︃

⟨𝑓 , 𝑓 ⟩H𝑘 .

KDD ’26, August 09–13, 2026, Jeju Island, Republic of Korea

As shown in Theorem 4.2, SR(𝜏) in Algorithm 1 converges at a √ rate of 𝑂 (1/ 𝜏), since Θ is finite and hence 𝛾 (𝜏) is bounded by a constant. The parameter 𝛼 trades off the (𝜏 − 𝑡 0 ) 2𝛼 term against the dependence on 𝑔(𝜽 ★) via C. Since 𝑔(𝜽 ★) is unknown, a convenient choice is to set 𝛼 to a moderate constant, e.g., 1/3. The dependence on 𝑔(𝜽 ★) < 0 is necessary and, as 𝛼 → 1/2, the term (−𝑔(𝜽 ★)) −2 becomes nearly tight, in the sense that it is unavoidable in the worst case for any 𝛿-correct algorithm; see Appendix D for details. Moreover, √ the following corollary translates the 𝜏-based bound into an 𝑂 (1/ Λ) bound in expectation. Corollary 1. Fix 𝛼 ∈ (0, 1/2) and suppose Assumptions 1–2 and 𝑔(𝜽 ★) < 0 hold. For each search budget Λ > 0, let 𝛿 = Λ−2 . Then there exists 𝑚 √︁≥ 2, independent of Λ, such that for all Λ ≥ 𝑚, E[SR(𝜏)] = 𝑂 ( (log Λ)/Λ), where the expectation is over the randomness of the observations and the stopping time 𝜏.

4.3

Computational Complexity

While simple regret captures the main search cost, we also analyze the additional computational cost to assess the practical runtime of SCOPE. In the algorithm, the time and space complexity are dominated by the selection of 𝜽 cand in Line 5. As implied by (7), this step requires computing 𝜇ˆ𝒙𝑞,𝑡 ,𝒚𝜁 ,𝑞,𝑡 and 𝜎ˆ𝒙𝑞,𝑡 ,𝒚𝜁 ,𝑞,𝑡 for all 𝜽 ∈ Θ, 𝜁 ∈ {𝑐, 𝑔}, and 𝑞 ∈ Q at time 𝑡. To compute each 𝜇ˆ• and 𝜎ˆ • , we use standard GP updates as detailed in Chowdhury and Gopalan [6], which costs 𝑂 (𝑡 2 ) time and 𝑂 (𝑡 2 ) space. Therefore, the time Í 2 ) = 𝑂 (𝑄 ·|Θ|·𝐽 2 complexity of Line 5 at time 𝑡 is 𝑂 (|Θ| 𝑞 ∈ Q 𝐽𝑞,𝑡 max,𝑡 ). Summing over 𝑡 ∈ [𝜏], the worst-case total time complexity of SCOPE in terms of 𝜏 is ! 𝜏 ∑︁
2 𝑂 𝑄 · |Θ| · 𝐽max,𝑡 = 𝑂 𝑄 · |Θ| · 𝜏 3 . 𝑡 =1

This is larger than the 𝑂 |Θ| · 𝜏 3 running time of existing BO and bandit approaches [29, 31], due to the query-wise exploitation in SCOPE. In addition, computing 𝛽𝜁 ,𝑡 in (8) also involves 𝛾 (𝐽 ) for all 𝐽 ≤ 𝜏. Since 12 log det(𝑰 + 𝜆 −1 𝑲𝐴 ) is a non-decreasing submodular set function over 𝐴 ⊆ Θ [27], 𝛾 (𝐽 ) can be approximated within a constant factor using a greedy algorithm [19] prior to running SCOPE. Although the obtained value may be slightly larger than the exact 𝛾 (𝐽 ), it does not affect the correctness of Theorems 4.1-4.2, as the confidence bounds become looser but still satisfy (2). For space, standard GP computations imply that calculating the perÍ 2 ) = 𝑂 (𝑄 · 𝜏 2 ), plus 𝑂 (𝜏) to query GP surrogates costs 𝑂 ( 𝑞 ∈ Q 𝐽𝑞,𝜏 store the observation history. Note that the empirical running time can be significantly lower than the above worst-case complexity, as 𝐽max,𝑡 is usually smaller than 𝑡.

5

Additional Related Work

In this section, we review several lines of work that may seem related to ours, and explain how they differ from the setting in constrained LLM selection for compound AI systems. Selecting a single model. A first line of work selects a single model for a single task. For instance, SpareLLM [12] evaluates all candidate LLMs but may stop early based on a quality confidence interval. BARGAIN [33] considers metrics such as accuracy and recall, and proposes finer-grained estimation methods. These methods differ fundamentally from our setting, as they select a single model for an

Yiqian Huang, Shiqi Zhang, Tianyuan Jin, and Xiaokui Xiao

isolated task. In contrast, we select a specific LLM for each module within a compound AI system that handles multi-step tasks. Using multiple models at runtime. Another line of work utilizes multiple LLMs via online routing or cascades, where queries are adaptively forwarded to different models during execution. FrugalGPT [4] invokes models sequentially from cheapest to most expensive, stopping once a learned confidence criterion is met. LLM-Cascade [32] combines lightweight models with a decision mechanism and a stronger fallback model. ThriftLLM [10] selects a subset of LLMs to maximize quality under a cost constraint by aggregating their outputs at runtime. Similarly, the work by Atalar [1] studies model selection along a pipeline with partial feedback using bandit-style algorithms. For a comprehensive survey of using multiple LLMs during execution, we refer readers to Chen et al. [5]. However, these approaches target specific system architectures to enable query-dependent or dynamic routing. In contrast, our work focuses on configuring arbitrary compound AI systems. Furthermore, their objectives differ from ours: we minimize cost subject to a strict quality constraint.

6

Experiments

In this section, we evaluate SCOPE on various tasks with different compound AI systems, addressing the following research questions: • RQ1: How does SCOPE improve correctness, effectiveness, and cost-efficiency compared to baseline approaches? • RQ2: Does the solution returned by SCOPE generalize in testtime deployments? • RQ3: How sensitive is the performance of SCOPE to different kernel and reference configuration settings? We also conduct ablation studies on key components of SCOPE and additional scalability evaluations. Results are presented in Appendix B.

6.1

Experimental Setup

Problem settings. We run experiments on three data management tasks: Text-to-SQL, data transformation, and data imputation. We use the compound AI systems in DIN-SQL [22], UniDM-DT, and UniDM-DI [23] for these tasks, respectively. For each task, we adopt the dataset Q used in the system’s original paper, and set the maximum budget Λmax to approximately match the monetary cost incurred when random search runs for 20 iterations, which is sufficient for most methods to converge to a stable solution. Details are listed in Table 2. In addition, we construct the candidate model set M with 23 models covering a wide range of prices and capabilities, resulting in search spaces containing tens of thousands to millions of configurations. The full LLM list is provided in Appendix A. We set 𝜽 0 to the configuration in which all modules use GPT-5.2, the most expensive model in M, and set 𝜖 = 0.01. We compute each 𝑦𝑔,𝑡 using the standard evaluation metric of the task, i.e., execution accuracy for Text-to-SQL and accuracy for data transformation and data imputation. We compute each 𝑦𝑐,𝑡 as the actual incurred cost in USD. For any configuration 𝜽 reported in our experiments, we estimate 𝑐 (𝜽 ) and 𝑠 (𝜽 ) offline by evaluating 𝜽 on Q multiple times and taking the average; these evaluations are not counted toward the budget of any method.

SCOPE: Cost-Efficient Model Selection for Compound AI Systems under Quality Constraints

KDD ’26, August 09–13, 2026, Jeju Island, Republic of Korea

Table 2: Statistics of tasks, systems, datasets, and search budgets. Scenario Text-to-SQL Data transformation Data imputation

SCOPE

AI system

𝑁

|Θ|

Query dataset (Q)

𝑄

Λmax in USD

Test-time dataset (for RQ2)

DIN-SQL [22] UniDM-DT [23] UniDM-DI [23]

4 5 3

279,841 6,436,343 12,167

BIRD-mini-dev [15] Bing-QueryLogs [7] Restaurant-dev [18]

500 102 156

30.0 5.0 2.0

BIRD-dev (1534 queries) [15] StackOverflow (710 queries) [7] Restaurant-test (86 queries) [18]

cEI

CONFIG

LLAMBO

Best feasible cost

3 × 10 −2

Abacus

LLMSelector

SafeOpt

Best feasible cost

Random

Best feasible cost

3 × 10 −3

3×10 −3 10 −2

10 −3 10 −3

3 × 10 −3

3 × 10 −4 10 −3 3×10 −4 0

10 20 budget in USD

30

10 −4 0

Constraint violation

1

2 3 budget in USD

4

5

0

0.5

1 1.5 budget in USD

2

Constraint violation

Constraint violation

0.4 0.3 0.1 0.2 0.2 0.1

0

0

0 0

10 20 budget in USD (a) Text-to-SQL

30

0

1

2 3 budget in USD

4

5

0

0.5

1 1.5 budget in USD

2

(c) Data imputation

(b) Data transformation

Figure 1: Best feasible cost and average constraint violation across methods, budgets, and tasks. Competitors and configurations. We evaluate SCOPE against seven competitors, divided into two categories as follows. • Generic optimizations: random search (Random), cEI [29], CONFIG [31], and SafeOpt [28]. For these methods, we follow the standard implementations from prior work [31]. • Compound-AI-specific approaches: LLAMBO [17], LLMSelector [3], and Abacus [25]. We make the necessary minimal adaptations to align with the setting in Problem 1; see Appendix A for details. For SCOPE and generic approaches that require an SPD kernel 𝑘, we follow prior work [26] and use the Matérn 5/2 kernel:   √ √ ′ 𝑘 (𝜽, 𝜽 ′ ) = 1 + 5 𝑑 (𝜽, 𝜽 ′ ) + 53 𝑑 (𝜽, 𝜽 ′ ) 2 𝑒 − 5𝑑 (𝜽,𝜽 ) , √︃Í 𝑁 ′ where 𝑑 (𝜽, 𝜽 ′ ) = 𝑖=1 1{𝜃 𝑖 ≠ 𝜃 𝑖 } counts the number of modules ′ on which 𝜽 and 𝜽 choose different LLMs. To ensure a fair comparison, we use the same kernel across these methods, although kernel choices may affect empirical performance. For SCOPE, we set 𝑅𝑐 = 𝑅𝑔 = 10−3 , 𝛿 = 10−4 , 𝛼 = 1/3, and 𝜃 base to Gemini-2.5-flash-lite. We treat 𝐵𝑐 and 𝐵𝑔 as hyperparameters and tune them before the main loop (Line 3 of Algorithm 1), so that Line 5 of Algorithm 1 has at least one eligible configuration when executing for the first time. Evaluation metrics. For each task and search budget Λ ∈ [0, Λmax ], we mainly report metrics for each algorithm’s returned configuration, denoted as 𝜽 out,Λ . To evaluate effectiveness and cost-efficiency, we report the best feasible cost achieved by each algorithm up to

budget Λ, defined as 𝑐 bf (Λ) =

min

Λ′ ≤Λ: 𝑠 (𝜽 out,Λ′ ) ≥𝑠 0

𝑐 (𝜽 out,Λ′ ).

Specifically, effectiveness is represented by how small the best feasible cost is at the maximum budget Λmax . Cost-efficiency means how fast the best feasible cost reduces as the budget increases. For SCOPE and its variants, 𝑐 bf (Λ) = SR(𝜏) + 𝑐 (𝜽 ★) at the returned stopping time 𝜏 corresponding to budget Λ. For other methods, it similarly represents the best cost found up to budget Λ, where infeasible configurations are ruled out. To assess correctness, i.e., whether 𝑠 (𝜽 out ) ≥ 𝑠 0 , we also report the average constraint violation metric [31] up to budget Λ, defined as ∫ Λ max{𝑠0 −𝑠 (𝜽out,𝑢 ),0} 𝑉 (Λ) = Λ1 0 𝑑𝑢, 𝑠0 with 𝑉 (0) = 0. 𝑉 (Λ) measures the extent to which the returned configuration violates the quality constraint, and 𝑉 (Λ) = 0 means that correctness holds at all budgets from 0 to Λ. Since there are finitely many different 𝜽 out,𝑢 , we compute the integral exactly by summing over the corresponding budget intervals. We repeat each experiment three times, each with a fixed random seed, and report the median, minimum, and maximum values. All experiments were conducted on a Linux server equipped with an Intel Xeon(R) Gold 6240 CPU @ 2.60GHz and 377GB of RAM, using multi-threading to maximize throughput when invoking LLMs. The implementations

KDD ’26, August 09–13, 2026, Jeju Island, Republic of Korea

of all algorithms are available at https://github.com/waetr/SCOPELLM-optimizer/.

6.2

Performance Evaluation (RQ1)

In the first set of experiments, we evaluate SCOPE against competitors in the three tasks, varying the search budget Λ ∈ [0, Λmax ]. Figure 1 reports the best feasible cost 𝑐 bf (Λ) and the constraint violation 𝑉 (Λ) of each algorithm. For better visualization, we report only the median of 𝑉 (Λ) for LLMSelector across the three runs, as its maximum (up to 0.64) would dominate most of the figure. Effectiveness and efficiency. As shown in the upper panels of Figure 1, SCOPE consistently outperforms all competitors in terms of the final best feasible cost and how fast the cost converges. Specifically, at the maximum budget Λmax , 𝑐 bf (Λmax ) found by SCOPE is 83.7%, 53.5%, and 21.1% lower than that of the best competitor in Text-to-SQL, data transformation, and data imputation, respectively. Furthermore, across budgets Λ ∈ [0, Λmax ], SCOPE achieves up to 95.5%, 63.1%, and 93.6% lower best feasible cost 𝑐 bf (Λ) than the best competitor in the three tasks, respectively. The lower best feasible cost at Λmax suggests that the candidates 𝜽 cand selected by SCOPE have strong cost and quality under the confidence-bound-based selection criterion. During search, the rapid improvement in 𝑐 bf (Λ) is driven by SCOPE’s exploitation of query-level observations: compared with competitors that rely on dataset-level evaluation and thus must spend a full pass over Q for each configuration, SCOPE can rule out many infeasible or suboptimal candidates after evaluating only a few queries (e.g., in data imputation, we observe that 79% of 𝜽 cand considered by SCOPE are ruled out after evaluating the first 40 queries), saving substantial search budget. In addition, the Calibrate subroutine evaluates many good configurations at a small budget, unlike other competitors that often fail to obtain a good starting point during search. Regarding other competitors, the performance among cEI, CONFIG, LLAMBO, and Abacus varies substantially across different tasks, in contrast to the consistently strong performance of SCOPE. LLMSelector rarely finds a better solution than 𝜽 0 across the three tasks, as it overemphasizes quality while overlooking cost. SafeOpt also performs conservatively, as it enforces that every evaluated configuration must be feasible, which limits exploration of potentially better ones. To summarize, SCOPE is significantly more cost-efficient and effective than all competitors. Correctness. As shown in the lower panels of Figure 1, SCOPE exhibits zero constraint violations 𝑉 (Λ) across all tasks and budgets, aligning with its 𝛿-correctness guarantee in theory. Regarding other methods, SafeOpt also has zero violations and, in theory, ensures correctness under the same assumptions as SCOPE. cEI offers correctness only under a noiseless assumption; nonetheless, it also has zero violations in our experiments. The remaining methods exhibit oscillating or increasing 𝑉 (Λ), often due to the inductive biases of their estimation models, for which correctness guarantees are unknown.

Yiqian Huang, Shiqi Zhang, Tianyuan Jin, and Xiaokui Xiao

6.3

Deployment Performance (RQ2)

In the second set of experiments, we evaluate, on a test-time dataset distinct from Q, the reported configuration at budget Λmax in Figure 1 (i.e., the one achieving the best feasible cost on Q within budget Λmax ). The test-time datasets are listed in Table 2 and have been used as held-out test sets corresponding to Q [23]. Table 3 reports the resulting average cost and average quality on these datasets. Overall, the average costs at test time are within the same order of magnitude as those on Q. In addition, some methods achieve cost reductions while maintaining average quality comparable to the reference configuration 𝜽 0 , demonstrating the presence of configurations with lower cost than the expensive single-model baseline without sacrificing potential quality. Performance of SCOPE. Notably, the configuration found by SCOPE on Q generalizes well: SCOPE attains the lowest average cost among all methods while achieving higher average quality than the reference configuration 𝜽 0 . Concretely, in Text-to-SQL, data transformation, and data imputation, the average costs of SCOPE are only 3%, 5%, and 2% of those of 𝜽 0 , respectively. Furthermore, its average quality improves upon 𝜽 0 by 21%, 5%, and 19%. We attribute this surprising quality improvement to the way SCOPE ensures 𝛿correctness under noisy evaluations. As feasibility must be certified with high probability, SCOPE is less likely to return configurations that sit right near the quality threshold on Q. Instead, it tends to select configurations with a meaningful quality margin (i.e., the part exceeding the quality threshold). Under dataset shift, this margin makes the selected configuration more likely to remain feasible and, in some cases, even to outperform 𝜽 0 in average quality. Performance of other competitors. In contrast to SCOPE, other competitors translate less reliably to test time. They achieve much smaller cost savings and may fail to match the average quality of 𝜽 0 . For example, cEI’s average costs are 13.1×, 13.8×, and 10.2× larger than those of SCOPE across the three tasks. In data transformation, its average quality is 8% lower than that of 𝜽 0 . This reflects the brittleness of its correctness property under a noiseless assumption: by choosing solutions very close to the quality threshold, cEI can overfit to Q rather than yield robust test-time performance. Similarly, CONFIG and LLAMBO exhibit lower average quality than 𝜽 0 in data transformation, as they lack mechanisms to generalize beyond Q. Meanwhile, while SafeOpt maintains feasibility on these datasets, it realizes cost reductions much smaller than SCOPE, similar to its behavior during search. The remaining methods, Abacus and LLMSelector, achieve average quality no worse than that of 𝜽 0 , but still incur average costs at least 6× higher than SCOPE. In sum, SCOPE reduces more cost than other competitors, while delivering improved quality relative to the reference configuration on held-out queries.

6.4

Sensitivity Analysis (RQ3)

In the third set of experiments, we evaluate whether SCOPE’s performance is sensitive to two settings used in the main experiments: the reference configuration 𝜽 0 in the problem definition and the kernel 𝑘 (·, ·) in SCOPE. We use data imputation for illustration and keep the other experiment settings the same as in Section 6.2. We compare the best feasible cost of SCOPE with that of the strongest competitors, cEI and CONFIG, over the search budget Λ.

SCOPE: Cost-Efficient Model Selection for Compound AI Systems under Quality Constraints

KDD ’26, August 09–13, 2026, Jeju Island, Republic of Korea

Table 3: Avg. cost and quality on test-time datasets. The best and second-best values are bold and underlined, respectively. Method

Text-to-SQL (BIRD-dev) Avg. cost (×10−2 ) 2.35 1.05 (45%) 1.41 (60%) 2.35 (100%) 2.35 (100%) 1.60 (68%) 1.73 (74%) 1.04 (44%) 0.08 (3%)

Reference (𝜽 0 ) cEI CONFIG SafeOpt LLAMBO LLMSelector Abacus Random SCOPE (Ours)

SCOPE

cEI

Data transformation (StackOverflow)

Data imputation (Restaurant-test)

Avg. quality

Avg. cost (×10−3 )

Avg. quality

Avg. cost (×10−3 )

Avg. quality

0.34 0.35 (+3%) 0.34 (+0%) 0.34 (+0%) 0.34 (+0%) 0.36 (+6%) 0.35 (+3%) 0.35 (+3%) 0.41 (+21%)

4.38 3.04 (69%) 0.93 (21%) 4.38 (100%) 0.76 (17%) 4.38 (100%) 4.38 (100%) 0.50 (11%) 0.22 (5%)

0.37 0.34 (-8%) 0.24 (-35%) 0.37 (+0%) 0.20 (-46%) 0.37 (+0%) 0.37 (+0%) 0.51 (+38%) 0.39 (+5%)

4.28 1.02 (24%) 0.21 (5%) 1.16 (27%) 0.43 (10%) 4.28 (100%) 0.63 (15%) 1.00 (23%) 0.10 (2%)

0.74 0.87 (+18%) 0.90 (+22%) 0.88 (+19%) 0.87 (+18%) 0.74 (+0%) 0.87 (+18%) 0.88 (+19%) 0.88 (+19%)

Acknowledgments

CONFIG

Best feasible cost

Best feasible cost

This work was supported by the Ministry of Education, Singapore, under Tier-2 Grant MOE-000761-01.

3×10 −3 10 −3

References

10 −3 10 −4 0

1 budget in USD

(a) Changing 𝜽 0

2

0

1 budget in USD

2

(b) Changing 𝑘

Figure 2: Best feasible cost when changing reference configurations and kernels.

Reference configuration. We first replace the default reference configuration with one in which all modules use Claude Haiku 4.5. As shown in Figure 2(a), SCOPE remains effective under this change and attains the lowest best feasible cost once the budget exceeds 1.2 USD. This shows that the improvement of SCOPE is not tied to a specific reference configuration. Kernel. We next replace the Matérn 5/2 kernel with the squared exponential (SE) kernel, defined as 𝑘 (𝜽, 𝜽 ′ ) = exp(−𝑑 (𝜽, 𝜽 ′ ) 2 /2). As shown in Figure 2(b), SCOPE continues to achieve lower best feasible cost than the other kernel-based competitors without intensive kernel tuning. Specifically, at Λmax , the best feasible cost of SCOPE is at most 50% of that of the second-best method. As a practical guideline, one can start with the default Matérn 5/2 kernel and use the SE kernel only if needed.

7

Conclusion

We study constrained LLM selection for compound AI systems. To solve this problem, we propose SCOPE, a search algorithm that exploits query-level partial evaluations and provides highprobability feasibility and simple-regret guarantees. In experiments, SCOPE reduces search cost relative to state-of-the-art baselines while better satisfying the quality constraint across multiple tasks. For future work, we plan to extend SCOPE to richer representations of cost–quality trade-offs, including multi-objective optimization and multiple constraints.

[1] Baran Atalar. 2026. Neural Bandit Based Optimal LLM Selection for Pipeline of Tasks. SIGMETRICS Perform. Eval. Rev. 53, 3 (2026), 15–17. [2] Adam D. Bull. 2011. Convergence Rates of Efficient Global Optimization Algorithms. JMLR 12, 88 (2011), 2879–2904. [3] Lingjiao Chen, Jared Quincy Davis, Boris Hanin, Peter Bailis, Matei Zaharia, James Zou, and Ion Stoica. 2025. Optimizing Model Selection for Compound AI Systems. arXiv:2502.14815 [cs.AI] https://arxiv.org/abs/2502.14815 [4] Lingjiao Chen, Matei Zaharia, and James Zou. 2024. FrugalGPT: How to Use Large Language Models While Reducing Cost and Improving Performance. TMLR (2024). [5] Zhijun Chen, Jingzheng Li, Pengpeng Chen, Zhuoran Li, Kai Sun, Yuankai Luo, Qianren Mao, Dingqi Yang, Hailong Sun, and Philip S. Yu. 2025. Harnessing Multiple Large Language Models: A Survey on LLM Ensemble. arXiv:2502.18036 [cs.CL] https://arxiv.org/abs/2502.18036 [6] Sayak Ray Chowdhury and Aditya Gopalan. 2017. On kernelized multi-armed bandits. In ICML. 844–853. [7] Yeye He, Xu Chu, Kris Ganjam, Yudian Zheng, Vivek Narasayya, and Surajit Chaudhuri. 2018. Transform-data-by-example (TDE): an extensible search engine for data transformations. PVLDB 11, 10 (2018), 1165–1177. [8] Zijian He, Reyna Abhyankar, Vikranth Srivatsa, and Yiying Zhang. 2025. Cognify: Supercharging Gen-AI Workflows with Hierarchical Autotuning. In KDD. 932– 943. [9] Sirui Hong, Mingchen Zhuge, Jonathan Chen, Xiawu Zheng, Yuheng Cheng, Jinlin Wang, Ceyao Zhang, Zili Wang, Steven Ka Shing Yau, Zijuan Lin, Liyang Zhou, Chenyu Ran, Lingfeng Xiao, Chenglin Wu, and Jürgen Schmidhuber. 2024. MetaGPT: Meta Programming for A Multi-Agent Collaborative Framework. In ICLR. [10] Keke Huang, Yimin Shi, Dujian Ding, Yifei Li, Yang Fei, Laks Lakshmanan, and Xiaokui Xiao. 2025. ThriftLLM: On Cost-Effective Selection of Large Language Models for Classification Queries. PVLDB 18, 11 (2025), 4410–4423. [11] Yiqian Huang, Shiqi Zhang, and Xiaokui Xiao. 2025. KET-RAG: A Cost-Efficient Multi-Granular Indexing Framework for Graph-RAG. In KDD. 1003–1012. [12] Saehan Jo and Immanuel Trummer. 2025. SpareLLM: Automatically Selecting Task-Specific Minimum-Cost Large Language Models under Equivalence Constraint. PACMMOD 3, 3 (2025). [13] Emilie Kaufmann, Olivier Cappé, and Aurélien Garivier. 2016. On the complexity of best-arm identification in multi-armed bandit models. JMLR 17, 1 (2016), 1–42. [14] Omar Khattab, Arnav Singhvi, Paridhi Maheshwari, Zhiyuan Zhang, Keshav Santhanam, Sri Vardhamanan A, Saiful Haq, Ashutosh Sharma, Thomas T. Joshi, Hanna Moazam, Heather Miller, Matei Zaharia, and Christopher Potts. 2024. DSPy: Compiling Declarative Language Model Calls into State-of-the-Art Pipelines. In ICLR. [15] Jinyang Li, Binyuan Hui, Ge Qu, Jiaxi Yang, Binhua Li, Bowen Li, Bailin Wang, Bowen Qin, Ruiying Geng, Nan Huo, Xuanhe Zhou, Chenhao Ma, Guoliang Li, Kevin C.C. Chang, Fei Huang, Reynold Cheng, and Yongbin Li. 2023. Can LLM already serve as a database interface? a big bench for large-scale database grounded text-to-SQLs. In NeurIPS. [16] Chunwei Liu, Matthew Russo, Michael Cafarella, Lei Cao, Peter Baile Chen, Zui Chen, Michael Franklin, Tim Kraska, Samuel Madden, Rana Shahout, and Gerardo Vitagliano. 2025. Palimpzest: Optimizing AI-Powered Analytics with Declarative Query Processing. In CIDR.

KDD ’26, August 09–13, 2026, Jeju Island, Republic of Korea

[17] Tennison Liu, Nicolás Astorga, Nabeel Seedat, and Mihaela van der Schaar. 2024. Large Language Models to Enhance Bayesian Optimization. In ICLR. [18] Yinan Mei, Shaoxu Song, Chenguang Fang, Haifeng Yang, Jingyun Fang, and Jiang Long. 2021. Capturing Semantics for Imputation with Pre-trained Language Models. In ICDE. 61–72. [19] George L Nemhauser, Laurence A Wolsey, and Marshall L Fisher. 1978. An analysis of approximations for maximizing submodular set functions—I. Mathematical programming 14, 1 (1978), 265–294. [20] OpenAI. 2025. Update to GPT-5 System Card: GPT-5.2. https://cdn.openai.com/ pdf/3a4153c8-c748-4b71-8e31-aecbde944f8d/oai_5_2_system-card.pdf [21] Krista Opsahl-Ong, Michael J Ryan, Josh Purtell, David Broman, Christopher Potts, Matei Zaharia, and Omar Khattab. 2024. Optimizing Instructions and Demonstrations for Multi-Stage Language Model Programs. In EMNLP, Yaser Al-Onaizan, Mohit Bansal, and Yun-Nung Chen (Eds.). 9340–9366. [22] Mohammadreza Pourreza and Davood Rafiei. 2023. DIN-SQL: Decomposed in-context learning of text-to-sql with self-correction. NeurIPS 36 (2023), 36339– 36348. [23] Yichen Qian, Yongyi He, Rong Zhu, Jintao Huang, Zhijian Ma, Haibin Wang, Yaohua Wang, Xiuyu Sun, Defu Lian, Bolin Ding, et al. 2024. UniDM: A unified framework for data manipulation with large language models. MLSys 6 (2024), 465–482. [24] Carl Edward Rasmussen. 2003. Gaussian processes in machine learning. In Summer school on machine learning. 63–71. [25] Matthew Russo, Sivaprasad Sudhir, Gerardo Vitagliano, Chunwei Liu, Tim Kraska, Samuel Madden, and Michael Cafarella. 2025. Abacus: A Cost-Based Optimizer for Semantic Operator Systems. arXiv:2505.14661 [cs.DB] https://arxiv.org/abs/ 2505.14661 [26] Jasper Snoek, Hugo Larochelle, and Ryan P Adams. 2012. Practical bayesian optimization of machine learning algorithms. NeurIPS 25 (2012). [27] Niranjan Srinivas, Andreas Krause, Sham Kakade, and Matthias Seeger. 2010. Gaussian Process Optimization in the Bandit Setting: No Regret and Experimental Design. In ICML. 1015–1022. [28] Yanan Sui, Alkis Gotovos, Joel Burdick, and Andreas Krause. 2015. Safe Exploration for Optimization with Gaussian Processes. In ICML, Vol. 37. 997–1005. [29] Haowei Wang, Jingyi Wang, Zhongxiang Dai, Nai-Yuan Chiang, Szu Hui Ng, and Cosmin G. Petra. 2025. Convergence Rates of Constrained Expected Improvement. In NeurIPS. [30] Shuhei Watanabe and Frank Hutter. 2023. c-TPE: Tree-structured Parzen Estimator with Inequality Constraints for Expensive Hyperparameter Optimization. In IJCAI. 9 pages. [31] Wenjie Xu, Yuning Jiang, Bratislav Svetozarevic, and Colin Jones. 2023. Constrained efficient global optimization of expensive black-box functions. In International Conference on Machine Learning. PMLR, 38485–38498. [32] Murong Yue, Jie Zhao, Min Zhang, Liang Du, and Ziyu Yao. 2024. Large Language Model Cascades with Mixture of Thought Representations for Cost-Efficient Reasoning. In ICLR. [33] Sepanta Zeighami, Shreya Shankar, and Aditya Parameswaran. 2025. Cut Costs, Not Accuracy: LLM-Powered Data Processing with Guarantees. PACMMOD 3, 6 (2025). [34] Yiqun Zhang, Hao Li, Jianhao Chen, Hangfan Zhang, Peng Ye, Lei Bai, and Shuyue Hu. 2025. Beyond GPT-5: Making LLMs Cheaper and Better via PerformanceEfficiency Optimized Routing. In DAI. 122–129. [35] Xingyu Zhou and Bo Ji. 2022. On kernelized multi-armed bandits with constraints. In NeurIPS.

Yiqian Huang, Shiqi Zhang, Tianyuan Jin, and Xiaokui Xiao

Table 4: Candidate LLMs M (price: USD per 1M tokens). Model GPT-5.2 GPT-5-mini GPT-5-nano GPT-4.1 GPT-4.1 Mini GPT-4.1 Nano Gemini 3 Flash Gemini 2.5 Flash Gemini 2.5 Flash-Lite Gemini 2.0 Flash-Lite Claude Haiku 4.5 Claude Haiku 3.5 Claude Haiku 3 DeepSeek-V3.2 DeepSeek-V3.1-Terminus Qwen3-235B-A22B Qwen3-Next-80B-A3B gemma-3-27b gemma-3-12b gemma-3-4b Mistral-Small-3.2 Mistral-Small-3 Mistral-Nemo

Experiment Details

Candidate LLMs. The candidate LLMs used in the experiments are listed in Table 4. The pricing values are obtained from the official OpenAI, Google, Anthropic, and DeepInfra platforms as of the submission date. According to these platforms, the cost incurred by invoking an LLM equals (# input tokens) × (input price) + (# output tokens) × (output price). Adaptation details. LLAMBO uses natural language instructions to prompt an LLM to emulate the BO process, where each instruction includes metadata about the compound AI system, the dataset, the candidate LLMs, and the past observation history. We adapt the instruction template from the original paper [17] to extend it to the constrained setting. The underlying LLM for estimation is GPT-5.2. LLMSelector [3] maximizes the quality 𝑠 by sequentially updating the LLM configuration starting from a random configuration, without considering cost. In addition, it optionally adopts an

Output Price

$1.75 $0.25 $0.05 $2.00 $0.40 $0.10 $0.50 $0.30 $0.10 $0.08 $1.00 $0.80 $0.25 $0.26 $0.21 $0.07 $0.09 $0.09 $0.04 $0.04 $0.08 $0.05 $0.02

$14.00 $2.00 $0.40 $8.00 $1.60 $0.40 $3.00 $2.50 $0.40 $0.30 $5.00 $4.00 $1.25 $0.39 $0.79 $0.46 $1.10 $0.16 $0.13 $0.08 $0.20 $0.08 $0.04

LLM diagnostician to analyze the intermediate quality of each module to guide the search. We remove this diagnostician since such intermediate quality is unavailable. Abacus conducts a bandit-style sequential search on sampled query subsets of Q, but its core mechanism requires knowing the model-wise quality of each module. To obtain this, in each iteration, we evaluate two configurations, where one is obtained from the other by changing the model choice in the module the algorithm is currently searching over. For random search, we iteratively evaluate a configuration randomly sampled from Θ without replacement on the entire dataset Q until the search budget is exhausted.

B A

Input Price

Ablation and Scalability Studies

In this section, we conduct ablation studies on key components and parameter settings of SCOPE and scalability evaluations on larger datasets. Ablation study. We compare SCOPE with two variants, SCOPERand and SCOPE-Coarse. SCOPE-Rand replaces Θinit in Line 1 of the Calibrate subroutine (Algorithm 2) with a set of configurations sampled uniformly at random from Θ, with the same size as Θinit . SCOPE-Coarse removes Calibrate and Line 14 from Algorithm 1, and sets 𝑡 0 = 0. As a result, neither SCOPE-Rand nor SCOPECoarse requires 𝜃 base as input, and SCOPE-Coarse evaluates the entire dataset in every iteration 𝑖 until the budget is exhausted. Figure 3 reports the best feasible cost 𝑐 bf (Λ) versus the search budget Λ. We also conduct experiments varying other input parameters; across budgets and tasks, all three methods exhibit zero violations, and the output of SCOPE remains unchanged for 𝛼 ∈ [1/5, 1/2 − 10−9 ] and 𝛿 ∈ [10−5, 10−3 ]. As shown by SCOPE-Rand,

SCOPE: Cost-Efficient Model Selection for Compound AI Systems under Quality Constraints

SCOPE Best feasible cost

3 × 10 −2

SCOPE-Rand

KDD ’26, August 09–13, 2026, Jeju Island, Republic of Korea

SCOPE-Coarse Best feasible cost

Best feasible cost

3 × 10 −3

3×10 −3 10 −2

10 −3 10 −3

3 × 10 −3

3 × 10 −4 10 −4

10 −3 3×10 −4 0

10

20 Λ in USD (a) Text-to-SQL

30

0

1

2 3 Λ in USD

4

5

(b) Data transformation

0

0.5

1 1.5 Λ in USD (c) Data imputation

2

Figure 3: Best feasible cost of SCOPE and its variants. SCOPE Abacus

cEI

CONFIG

LLMSelector

LLAMBO

SafeOpt

Random

Best feasible cost

10 −2

over the search budget. At the maximum budget, SCOPE is superior to other competitors in this new task, similar to the trends reflected in the original experiments. Specifically, the best feasible cost of SCOPE is 97% lower than that of the reference configuration, and 50% lower than that of the second-best method, LLAMBO.

C Proofs C.1 Preliminaries of Proofs

10 −3

10 −4 0

2

4 6 budget in USD

8

10

Figure 4: Best feasible cost on entity resolution with 2293 queries. replacing Θinit in (3) with a random configuration makes SCOPERand improve upon 𝜽 0 more slowly than SCOPE at small budgets. For example, in Text-to-SQL, SCOPE reduces 𝑐 bf to 2.6 × 10−3 by Λ = 5.5, whereas SCOPE-Rand first improves upon 𝜽 0 only at Λ = 11.0. This is because the randomly sampled configurations can be more expensive, leading to a higher initialization cost and delaying subsequent search progress in terms of budget. However, after surpassing 𝜽 0 , SCOPE-Rand often converges faster than SCOPE. For instance, in data imputation, SCOPE-Rand reduces the cost to 5.5 × 10−5 before Λ = 0.9, even lower than SCOPE’s best feasible cost at Λmax . To explain, a random configuration set can cover Θ more broadly, which may improve Calibrate over diverse configurations and help identify better candidates, although this advantage is unstable due to sampling randomness. In contrast, SCOPE-Coarse converges much more slowly than SCOPE. For instance, at Λmax , its best feasible cost is about 3 − 5× higher than that of SCOPE, yet still lower than that of cEI, across tasks. While the guarantees in Theorem 4.2 can also apply to SCOPE-Coarse if 𝑄 = 1, SCOPECoarse discards query-level signal exploitation and thus falls back to dataset-level evaluations, inheriting the cost inefficiency of existing competitors. Scalability evaluation. To further validate SCOPE’s performance, we experiment on an additional task, entity resolution, with a 3module UniDM-ER system and dataset Amazon-google-dev of 2293 queries [23]. Figure 4 shows the best feasible cost of each method

Algorithm. Recall that at time 𝑡, the observation history in an 𝑡 , with 𝐻 = ∅. Let F be the algorithm is 𝐻𝑡 = {(𝜽𝑖 , 𝑞𝑖 , 𝑦𝑐,𝑖 , 𝑦𝑔,𝑖 )}𝑖=1 0 𝑡 𝜎-algebra generated by 𝐻𝑡 . We formally define an algorithm 𝜋 (e.g., SCOPE) as a tuple (𝜏, (𝜋𝑡 )𝑡∞=1, 𝜽 out ), where • 𝜏 is a stopping time with respect to the filtration (F𝑡 )𝑡∞=0 ; • (𝜋𝑡 )𝑡∞=1 is a sequence of F𝑡 −1 -measurable mappings. For each 𝑡 ≥ 1, 𝜋𝑡 maps 𝐻𝑡 −1 to a probability distribution over Θ × Q, denoted by 𝜋𝑡 (·|𝐻𝑡 −1 ). At each time 𝑡 (for 1 ≤ 𝑡 ≤ 𝜏), the pair (𝜽𝑡 , 𝑞𝑡 ) is sampled from 𝜋𝑡 (·|𝐻𝑡 −1 ), yielding observations 𝑦𝑐,𝑡 and 𝑦𝑔,𝑡 ; • 𝜽 out ∈ Θ is an F𝜏 -measurable random variable representing the algorithm’s recommendation of the best configuration.

C.2

Proof of Theorem 4.1

We first establish a query-wise confidence bound for each GP (one per query 𝑞 and metric 𝜁 ), and then aggregate across queries to obtain a confidence bound for the dataset-average metric. Recall 𝐽𝑞,𝑡 = |J𝑞,𝑡 | and let 𝑗𝑞 (1) < · · · < 𝑗𝑞 (𝐽 ) be the times when query 𝑞 is evaluated up to time 𝑡. For fixed (𝑞, 𝜁 , 𝑡), define 𝜽 (𝑎) = 𝜽 𝑗𝑞 (𝑎) and 𝑦 (𝑎) = 𝑦𝜁 ,𝑗𝑞 (𝑎) for 𝑎 ∈ [𝐽 ], and let 𝐽 = 𝐽𝑞,𝑡 . We use the following standard kernelized self-normalized inequality (see, e.g., Theorem 1 and Lemma 1 of [6]). Lemma C.1 (Kernelized self-normalization). Let (𝜽 (𝑎) , 𝜂 (𝑎) )𝑎≥1 be a (possibly adaptive) sequence such that 𝜂 (𝑎) is conditionally 𝑅sub-Gaussian w.r.t. the filtration generated by the past. For each 𝐽 ≥ 1, define Φ 𝐽 : R 𝐽 → H𝑘 by Φ 𝐽 𝑒𝑎 = 𝜑 (𝜽 (𝑎) ), 𝑉𝐽 = Φ 𝐽 Φ⊤𝐽 + 𝜆𝐼 H𝑘 , and Í𝐽 𝑆 𝐽 = 𝑎=1 𝜂 (𝑎) 𝜑 (𝜽 (𝑎) ). Then for any 𝛿 ′ ∈ (0, 1), with probability at ′ least 1 − 𝛿 , simultaneously for all 𝐽 ≥ 1, √︂  √︂  1 1 ∥𝑆 𝐽 ∥𝑉 −1 ≤ 𝑅 2 I𝐽 + log ′ ≤ 𝑅 2 𝛾 (𝐽 ) + log ′ , 𝐽 𝛿 𝛿 where I𝐽 = 21 log det(𝐼 + 𝜆 −1 𝐾 𝐽 ) and 𝐾 𝐽 = Φ⊤𝐽 Φ 𝐽 .

KDD ’26, August 09–13, 2026, Jeju Island, Republic of Korea

Yiqian Huang, Shiqi Zhang, Tianyuan Jin, and Xiaokui Xiao

Fix 𝑞 ∈ Q, 𝜁 ∈ {𝑐, 𝑔}. By Assumption 2, ∥𝑓 ∥ H𝑘 ≤ 𝐵𝜁 , where H𝑘 is the corresponding RKHS. Define Φ : R 𝐽 → H𝑘 by Φ𝑒𝑎 = 𝜑 (𝜽 (𝑎) ) and 𝑉 = ΦΦ⊤ + 𝜆𝐼 H𝑘 . Let 𝜂 (𝑎) = 𝑦 (𝑎) − 𝑓 (𝜽 (𝑎) ) and 𝜂 = [𝜂 (1) , . . . , 𝜂 (𝐽 ) ] ⊤ . By Assumption 1, (𝜂 (𝑎) ) are conditionally 𝑅𝜁 -subGaussian. As a standard property of the GP update in Definition 1, for any 𝜽 ∈ Θ, 𝑓 (𝜽 ) − 𝜇ˆ𝜁 ,𝑞,𝑡 (𝜽 ) = 𝜆 ⟨𝑓 , 𝑉 −1𝜑 (𝜽 )⟩ H𝑘 − ⟨𝑆, 𝑉 −1𝜑 (𝜽 )⟩ H𝑘 ,

Averaging over 𝑞 ∈ Q and applying Cauchy–Schwarz,
1 ∑︁ 𝜇ˆ𝜁 ,𝑞,𝑡 (𝜽 ) − ℓ𝜁 (𝜽, 𝑞) 𝜇¯𝜁 ,𝑡 (𝜽 ) − ℓ¯𝜁 (𝜽 ) = 𝑄 𝑞∈ Q

𝛽𝜁 ,𝑡 ∑︁ ≤ √ 𝜎ˆ𝜁 ,𝑞,𝑡 (𝜽 ) 𝑄 𝑄 𝑞∈ Q √︄ ∑︁ 𝛽𝜁 ,𝑡 √︁ · 𝑄 ≤ √ 𝜎ˆ𝜁2,𝑞,𝑡 (𝜽 ) 𝑄𝑄 𝑞∈ Q v u u t ∑︁ 𝜎ˆ 2 (𝜽 ) 𝜁 ,𝑞,𝑡 = 𝛽𝜁 ,𝑡 = 𝛽𝜁 ,𝑡 𝜎¯𝜁 ,𝑡 (𝜽 ). 𝑄2

(12)

Í𝐽 where 𝑆 = 𝑎=1 𝜂 (𝑎) 𝜑 (𝜽 (𝑎) ) = Φ𝜂. Using the Woodbury matrix identity, one can verify the standard equality

𝑞∈ Q

𝜎ˆ𝜁2,𝑞,𝑡 (𝜽 ) = 𝜆 ⟨𝜑 (𝜽 ), 𝑉 −1𝜑 (𝜽 )⟩ H𝑘 .

(13)

√ Equivalently, ∥𝑉 −1/2𝜑 (𝜽 )∥ H𝑘 = 𝜎ˆ𝜁 ,𝑞,𝑡 (𝜽 )/ 𝜆. Next, the first term in (12) is bounded by 𝜆⟨𝑓 , 𝑉 −1𝜑 (𝜽 )⟩ H𝑘 = 𝜆 ⟨𝑉 −1/2 𝑓 , 𝑉 −1/2𝜑 (𝜽 )⟩ H𝑘 √ ≤ 𝜆∥𝑓 ∥ H𝑘 · ∥𝑉 −1/2𝜑 (𝜽 )∥ H𝑘 ≤ 𝐵𝜁 𝜎ˆ𝜁 ,𝑞,𝑡 (𝜽 ),

(14)

where the equality is due to self-adjointness of 𝑉 −1/2 , the first inequality uses Cauchy–Schwarz and 𝑉 ⪰ 𝜆𝐼 H𝑘 , and the second inequality uses (13) and ∥𝑓 ∥ H𝑘 ≤ 𝐵𝜁 . Furthermore, the second term in (12) is bounded by ⟨𝑆, 𝑉 −1𝜑 (𝜽 )⟩ H𝑘 ≤ ∥𝑆 ∥𝑉 −1 · ∥𝑉 −1/2𝜑 (𝜽 )∥ H𝑘 ∥𝑆 ∥𝑉 −1 𝜎ˆ𝜁 ,𝑞,𝑡 (𝜽 ) √ 𝜆 √︂  𝑅𝜁 1 ≤ √ 2 𝛾 (𝐽 ) + log ′ · 𝜎ˆ𝜁 ,𝑞,𝑡 (𝜽 ), 𝛿 𝜆 =

(15)

where the first and last inequalities use Cauchy–Schwarz and Lemma C.1 with parameter 𝛿 ′ ∈ (0, 1), respectively, and the equality is due to (13). Combining (12), (14), and (15) yields

Therefore, with probability at least 1 − 𝛿, simultaneous over all 𝑡 ∈ N, 𝑞 ∈ Q, 𝜽 ∈ Θ, and 𝜁 ∈ {𝑐, 𝑔}, (2) follows immediately from the definitions of 𝐿𝜁 ,𝑡 , 𝑈𝜁 ,𝑡 in (4). □

C.3

Proof of Theorem 4.2

Notations. Let Econf denote the high-probability event in (2), i.e., all confidence intervals are valid. Let (𝜽 out, 𝜏) denote the output of Algorithm 1, where 𝜽 out is measurable w.r.t. the 𝜎-algebra produced by the history {(𝜽𝑡 , 𝑞𝑡 , 𝑦𝑐,𝑡 , 𝑦𝑔,𝑡 )}𝜏𝑡=1 . Accordingly, throughout the proof we analyze the execution restricted to times up to 𝜏. Let 𝐼 be the number of executed rounds (𝑖-loop iterations) whose candidate is evaluated at least once within times {𝑡 0 + 1, . . . , 𝜏 }, indexed by 𝑖 ∈ [𝐼 ] with strictly increasing start times 𝑡 (1) < · · · < (𝑖 ) 𝑡 (𝐼 ) and corresponding candidates 𝜽 cand . Here, 𝑡 (𝑖 ) denotes the value of the global counter 𝑡 at the moment Line 5 is executed in round 𝑖 (before running the 𝑗-loop). Additionally, let 𝑡 (𝐼 +1) = 𝜏. (𝑖 ) By construction, for each 𝑖 ∈ [𝐼 ], we have 𝜽𝑡 ′ = 𝜽 cand for all ′ (𝑖 ) (𝑖+1) 𝑡 ∈ {𝑡 + 1, . . . , 𝑡 }. Define the set of certified-feasible rounds as n o (𝑖 ) Ifeas = 𝑖 ∈ [𝐼 ] : ∃ 𝑡 ∈ [𝑡 (𝑖 ) , 𝑡 (𝑖+1) ], 𝑈𝑔,𝑡 (𝜽 cand )≤0 . For each 𝑖 ∈ Ifeas , define the set of certification-trigger times as n o  (𝑖 ) (𝑖 ) (𝑖 ) Tfeas = 𝑡 ∈ [𝑡 (𝑖 ) + 1, 𝑡 (𝑖+1) ] : min 𝑈𝑔,𝑡 (𝜽 cand ),𝑈𝑔,𝑡 −1 (𝜽 cand ) ≤0 , and define (𝑖 ) (𝑖 ) 𝑡 feas ∈ arg min 𝑈𝑐,𝑡 (𝜽 cand ), (𝑖 )

𝑡 ∈ Tfeas (𝑖 ) breaking ties arbitrarily. Note that for every 𝑖 ∈ Ifeas , Tfeas ≠ ∅:

𝑅𝜁 𝜇ˆ𝜁 ,𝑞,𝑡 (𝜽 ) − ℓ𝜁 (𝜽, 𝑞) ≤ 𝐵𝜁 + √ 𝜆

√︂ 

2 𝛾 (𝐽 ) + log

!

1 𝜎ˆ𝜁 ,𝑞,𝑡 (𝜽 ). 𝛿′

Since 𝐽 = 𝐽𝑞,𝑡 ≤ 𝐽max,𝑡 and 𝛾 (·) is nondecreasing, 𝛾 (𝐽 ) ≤ 𝛾 (𝐽max,𝑡 ), so the same inequality holds after replacing 𝛾 (𝐽 ) by 𝛾 (𝐽max,𝑡 ). As there are 𝑄 choices of 𝑞 and two choices of 𝜁 , we set 𝛿 ′ = 𝛿/(2𝑄) and use union bound. Then, with probability at least 1 − 𝛿, simultaneously for all (𝑡, 𝑞, 𝜽, 𝜁 ), we have 𝑅𝜁 𝜇ˆ𝜁 ,𝑞,𝑡 (𝜽 ) − ℓ𝜁 (𝜽, 𝑞) ≤ 𝐵𝜁 + √ 𝜆 |

√︂ 

2 𝛾 (𝐽max,𝑡 ) + log

2𝑄 

!

𝛿 {z

√ 𝛽𝜁 ,𝑡 / 𝑄

}

𝜎ˆ𝜁 ,𝑞,𝑡 (𝜽 ).

(𝑖 ) if 𝑈𝑔,𝑡 (𝜽 cand ) ≤ 0 holds at some 𝑡 ∈ [𝑡 (𝑖 ) , 𝑡 (𝑖+1) ], then taking 𝑡 ′ = (𝑖 ) max{𝑡, 𝑡 +1} ∈ [𝑡 (𝑖 ) +1, 𝑡 (𝑖+1) ] gives min{𝑈𝑔,𝑡 ′ (·), 𝑈𝑔,𝑡 ′ −1 (·)} ≤ 0, (𝑖 ) hence 𝑡 ′ ∈ Tfeas . Proof of 𝛿-correctness. Initially, 𝑠 (𝜽 out ) = 𝑠 (𝜽 0 ) ≥ 𝑠 0 . Whenever (𝑖 ) 𝜽 out is updated in Line 10, it is set to some candidate 𝜽 cand at a (𝑖 ) (𝑖 ) time 𝑡 such that min{𝑈𝑔,𝑡 (𝜽 cand ), 𝑈𝑔,𝑡 −1 (𝜽 cand )} ≤ 0. Thus either (𝑖 ) (𝑖 ) 𝑈𝑔,𝑡 (𝜽 cand ) ≤ 0 or 𝑈𝑔,𝑡 −1 (𝜽 cand ) ≤ 0. On Econf , in either case we (𝑖 ) (𝑖 ) have 𝑔(𝜽 cand ) ≤ 𝑈𝑔,𝑡 ′ (𝜽 cand ) ≤ 0 for some 𝑡 ′ ∈ {𝑡, 𝑡 − 1}, hence (𝑖 ) 𝑠 (𝜽 cand ) ≥ 𝑠 0 . Therefore 𝑠 (𝜽 out ) ≥ 𝑠 0 holds on Econf , implying that SCOPE is 𝛿-correct. Proof outline for simple regret. We focus on rounds where the selection threshold is small enough that 𝜽 ★ satisfies the constraint in Line 5. For these rounds, the selection rule guarantees that the

SCOPE: Cost-Efficient Model Selection for Compound AI Systems under Quality Constraints

chosen candidate has a cost lower confidence bound no larger than that of 𝜽 ★, so SR can be controlled by the cost confidence width. We then bound SR by the smallest such width among candidates that are eventually certified feasible, and replace this minimum by an average over the certified-feasible rounds, which introduces an inverse dependence on their count. Finally, we lower bound the number of certified-feasible rounds: any round that is not certified feasible must exhibit sufficiently large constraint uncertainty relative to its threshold, while the total accumulated constraint uncertainty is bounded. Combining the two steps yields the stated SR bound. Throughout the proof, we carry out all derivations on the event Econf ; as shown above, Pr[Econf ] ≥ 1 − 𝛿. Specifically, denote Δ★ = 𝑠 (𝜽 ★) −𝑠 0 = −𝑔(𝜽 ★) > 0, and let S = {𝑖 ★, 𝑖 ★ +1, . . . , 𝐼 } ⊆ [𝐼 ], where l
−1/𝛼 m 𝑖 ★ = min{𝑖 ∈ N : Δ𝑖 ≤ Δ★ } = Δ★ .

KDD ’26, August 09–13, 2026, Jeju Island, Republic of Korea

any 𝑖 ∈ Ifeas ∩ S, we have (𝑖 ) 𝐿𝑐,𝑡 (𝑖 ) (𝜽 cand ) ≤ 𝐿𝑐,𝑡 (𝑖 ) (𝜽 ★). (𝑖 ) On Econf , we further bound 𝑐 (𝜽 cand ) − 𝑐 (𝜽 ★) as follows. (𝑖 ) (𝑖 ) 𝑐 (𝜽 cand ) − 𝑐 (𝜽 ★) ≤ 𝑈𝑐,𝑡 (𝑖 ) (𝜽 cand ) − 𝐿𝑐,𝑡 (𝑖 ) (𝜽 ★) (𝑖 ) (𝑖 ) ≤ 𝑈𝑐,𝑡 (𝑖 ) (𝜽 cand ) − 𝐿𝑐,𝑡 (𝑖 ) (𝜽 cand ) (𝑖 ) = 2𝛽𝑐,𝑡 (𝑖 ) 𝜎¯𝑐,𝑡 (𝑖 ) (𝜽 cand ) (𝑖 ) ≤ 2𝛽𝑐,𝜏 𝜎¯𝑐,𝑡 (𝑖 ) (𝜽 cand ).

(18)

Combining (17) and (18) yields that, for every 𝑖 ∈ Ifeas ∩ S, (𝑖 ) 𝑐 (𝜽 out ) − 𝑐 (𝜽 ★) ≤ 4𝛽𝑐,𝜏 𝜎¯𝑐,𝑡 (𝑖 ) (𝜽 cand ).

Taking the minimum over 𝑖 yields 𝑐 (𝜽 out ) − 𝑐 (𝜽 ★) ≤ 4𝛽𝑐,𝜏 ·

(𝑖 ) min 𝜎¯𝑐,𝑡 (𝑖 ) (𝜽 cand ) v tÍ (𝑖 ) ¯ 2 (𝑖 ) (𝜽 cand ) 𝑖 ∈ Ifeas ∩S 𝜎

𝑖 ∈ Ifeas ∩S

Additionally, we assume that 𝜏 is sufficiently large, so that Ifeas ∩ S ≠ ∅.

(♠)

≤ 4𝛽𝑐,𝜏 ·

In particular, this implies that Ifeas ≠ ∅ and S ≠ ∅. We will show at the end of the proof that (♠) is implied by the condition under which (11) is stated. Additionally, we will use the following lemma.

√︄ Í

Since 𝐽max,𝜏 ≤ 𝜏 and 𝛾 (·) is nondecreasing, we have 𝛾 (𝐽max,𝜏 ) ≤ 𝛾 (𝜏). Accordingly, in the sequel we may upper bound any occurrence of 𝛾 (𝐽max,𝜏 ) by 𝛾 (𝜏). Relating 𝜽 out to 𝜽 cand . Let 𝑈 out denote the final value of the variable 𝑈 out upon termination of Algorithm 1. By construction, 𝑈 out is initialized as 𝑈𝑐,𝑡0 (𝜽 0 ) and is updated only when Line 10 holds; hence 𝑈 out is nonincreasing over time. Moreover, whenever round (𝑖 ) 𝑖 triggers the modified update condition at some time 𝑡 ∈ Tfeas , the (𝑖 ) algorithm compares 𝑈𝑐,𝑡 (𝜽 cand ) with the current 𝑈 out and updates 𝑈 out if this value is smaller. Therefore, at termination,

∀𝑖 ∈ Ifeas .

(16)

feas

𝑐 (𝜽 out ) ≤ 𝑈 out (𝑖 ) ≤ 𝑈𝑐,𝑡 (𝑖 ) (𝜽 cand )

(using (16))

feas

√︄ ≤ 4𝛽𝑐,𝜏 ·

4(𝜆 + 1)𝛾 (𝜏) |Ifeas ∩ S|

A = √ √︁ , 𝑄 · |Ifeas ∩ S|

(19)

√︁ where A = 8𝛽𝑐,𝜏 𝑄 (𝜆 + 1)𝛾 (𝜏). Here, the second inequality replaces the minimum with the average, the third inequality uses the Í 2 fact that for each 𝑖 ∈ [𝐼 ], the sum 𝜏𝑡=𝑡0 +1 𝜎¯𝑐,𝑡 −1 (𝜽𝑡 ) contains the term (𝑖 ) 2 2 ¯𝑐,𝑡 𝜎¯𝑐,𝑡 (𝑖 ) (𝜽𝑡 (𝑖 ) +1 ) = 𝜎 (𝑖 ) (𝜽 cand ), and the fourth inequality uses Lemma C.2 with 𝜁 = 𝑐. feas = [𝐼 ] \ I , 𝐼 feas Bounding |Ifeas ∩ S|. Let Ibad feas bad = |Ibad |, and fix feas index 𝑖 ∈ Ibad . On one hand, since round 𝑖 starts, the selection

feas

(𝑖 ) (𝑖 ) = 𝐿𝑔,𝑡 (𝑖 ) (𝜽 cand ) + 2𝛽𝑔,𝑡 (𝑖 ) 𝜎¯𝑔,𝑡 (𝑖 ) (𝜽 cand )

feas

(𝜎¯ is nonincreasing)

feas

(𝑖 ) (𝑖 ) ≤ 𝑐 (𝜽 cand ) + 2𝛽𝑐,𝜏 𝜎¯𝑐,𝑡 (𝑖 ) (𝜽 cand ),

(17)

where the last inequality uses that 𝛽𝑐,𝑡 is nondecreasing in 𝑡. Relating to 𝜽 ★. By definition of S, on Econf , we have 𝐿𝑔,𝑡 (𝑖 ) (𝜽 ★) ≤ −Δ★ ≤ −Δ𝑖 ,

∀𝑡 ∈ [𝑡 (𝑖 ) , 𝑡 (𝑖+1) ].

(𝑖 ) 0 < 𝑈𝑔,𝑡 (𝑖 ) (𝜽 cand )

(𝑖 ) (𝑖 ) ) ≤ 𝑐 (𝜽 cand ) + 2𝛽𝑐,𝑡 (𝑖 ) 𝜎¯𝑐,𝑡 (𝑖 ) (𝜽 cand (𝑖 ) (𝑖 ) ≤ 𝑐 (𝜽 cand ) + 2𝛽𝑐,𝑡 (𝑖 ) 𝜎¯𝑐,𝑡 (𝑖 ) (𝜽 cand )

(𝑖 ) 𝑈𝑔,𝑡 (𝜽 cand ) > 0,

(𝑖 ) In particular, 𝑈𝑔,𝑡 (𝑖 ) (𝜽 cand ) > 0. Therefore,

(𝑖 ) (𝑖 ) ) + 2𝛽𝑐,𝑡 (𝑖 ) 𝜎¯𝑐,𝑡 (𝑖 ) (𝜽 cand ) = 𝐿𝑐,𝑡 (𝑖 ) (𝜽 cand

feas

4(𝜆 + 1)𝛾 (𝐽max,𝜏 ) |Ifeas ∩ S|

(𝑖 ) rule implies 𝐿𝑔,𝑡 (𝑖 ) (𝜽 cand ) ≤ −Δ𝑖 with Δ𝑖 = 𝑖 −𝛼 . On the other hand, because 𝑖 ∉ Ifeas , by definition we have

Fix any 𝑖 ∈ Ifeas . On Econf , we have

feas

|Ifeas ∩ S| √︄

≤ 4𝛽𝑐,𝜏 ·

𝑡 =𝑡 0 +1

feas

𝜏 2 ¯𝑐,𝑡 𝑡 =𝑡 0 +1 𝜎 −1 (𝜽𝑡 )

≤ 4𝛽𝑐,𝜏 ·

Lemma C.2. For any 𝜁 ∈ {𝑐, 𝑔}, 𝜏 ∑︁ 𝜎¯𝜁2,𝑡 −1 (𝜽𝑡 ) ≤ 4(𝜆 + 1)𝛾 (𝐽max,𝜏 ).

(𝑖 ) 𝑈 out ≤ 𝑈𝑐,𝑡 (𝑖 ) (𝜽 cand ),

𝑐,𝑡

|Ifeas ∩ S|

∀𝑖 ∈ S.

In other words, every index 𝑖 ∈ S has sufficiently small Δ𝑖 , so that 𝜽 ★ can be selected by Line 5 at time 𝑡 (𝑖 ) . By the selection rule, for

(𝑖 ) ≤ −Δ𝑖 + 2𝛽𝑔,𝑡 (𝑖 ) 𝜎¯𝑔,𝑡 (𝑖 ) (𝜽 cand ) (𝑖 ) ≤ −Δ𝑖 + 2𝛽𝑔,𝜏 𝜎¯𝑔,𝑡 (𝑖 ) (𝜽 cand ) (𝑖 ) ⇔ 2𝛽𝑔,𝜏 · 𝜎¯𝑔,𝑡 (𝑖 ) (𝜽 cand ) > Δ𝑖 . feas gives Squaring and summing over 𝑖 ∈ Ibad ∑︁ ∑︁ (𝑖 ) 2 2 Δ𝑖2 ≤ 4𝛽𝑔,𝜏 𝜎¯𝑔,𝑡 (𝑖 ) (𝜽 cand ). feas 𝑖 ∈ Ibad

feas 𝑖 ∈ Ibad

KDD ’26, August 09–13, 2026, Jeju Island, Republic of Korea

Yiqian Huang, Shiqi Zhang, Tianyuan Jin, and Xiaokui Xiao

Í (𝑖 ) 2 ) appears in the sum 𝜏𝑡=𝑡0 +1 𝜎¯𝑔,𝑡 As each term 𝜎¯ 2 (𝑖 ) (𝜽 cand −1 (𝜽𝑡 ), 𝑔,𝑡 we apply Lemma C.2 with 𝜁 = 𝑔, which yields ∑︁ 2 Δ𝑖2 ≤ 16(𝜆 + 1)𝛽𝑔,𝜏 𝛾 (𝐽max,𝜏 ). (20)

Since the set has size 𝐽𝑞,𝜏 , we have I (·) ≤ 𝛾 (𝐽𝑞,𝜏 ) ≤ 𝛾 (𝐽max,𝜏 ), and thus 𝐽𝑞,𝜏   ∑︁ log 1 + 𝑣𝑞,𝑟 /𝜆 ≤ 2𝛾 (𝐽max,𝜏 ). (23) 𝑟 =1

feas 𝑖 ∈ Ibad

For the bound on 𝐼 bad , since Δ𝑖 = 𝑖 −𝛼 , we have Δ𝑖2 = 𝑖 −2𝛼 , which Í is nonincreasing in 𝑖. Therefore, the minimum of 𝑖 ∈𝑆 Δ𝑖2 over all 𝑆 ⊆ [𝐼 ] with |𝑆 | = 𝐼 bad is achieved at 𝑆 = {𝐼 − 𝐼 bad + 1, . . . , 𝐼 }. It follows that 𝐼 ∑︁ ∑︁ Δ𝑖2 ≥ 𝑗 −2𝛼 feas 𝑖 ∈ Ibad

𝑗=𝐼 −𝐼 bad +1

≥ 𝐼 bad · 𝐼 −2𝛼 , where the last inequality uses 𝑗 ≤ 𝐼 for all 𝑗 ∈ {𝐼 − 𝐼 bad + 1, . . . , 𝐼 }. Combining this with (20) yields 2 𝐼 bad ≤ 16(𝜆 + 1)𝛽𝑔,𝜏 𝛾 (𝐽max,𝜏 ) · 𝐼 2𝛼 .

(21)

Now we derive a lower bound of |Ifeas ∩ S|. Recall that S = {𝑖 ★, 𝑖 ★ + 1, . . . , 𝐼 } and thus |S| = 𝐼 − 𝑖 ★ + 1. Therefore,

Moreover, for any 𝑥 ∈ [0, 1], log(1 + 𝑥/𝜆) ≥ 𝑥/(𝜆 + 𝑥) ≥ 𝑥/(𝜆 + 1), hence 𝑥 ≤ (𝜆 + 1) log(1 + 𝑥/𝜆). (24) Applying (24) to 𝑥 = 𝑣𝑞,𝑟 and summing, then using (23), gives 𝐽𝑞,𝜏 ∑︁

𝑣𝑞,𝑟 ≤ (𝜆 + 1)

𝑟 =1

𝐽𝑞,𝜏 ∑︁

log(1 + 𝑣𝑞,𝑟 /𝜆) ≤ 2(𝜆 + 1)𝛾 (𝐽max,𝜏 ).

𝑟 =1

Summing over 𝑞 ∈ Q and reindexing by time 𝑡 yields 𝜏 ∑︁ 𝜎ˆ𝜁2,𝑞𝑡 ,𝑡 −1 (𝜽𝑡 ) ≤ 2(𝜆 + 1) 𝑄 𝛾 (𝐽max,𝜏 ).

(25)

𝑡 =1

Bounding the aggregated uncertainty sum. Consider any fixed inner iteration (Lines 7–10) in which the algorithm keeps 𝜽𝑡 = 𝜽 cand for 𝑚 ≤ 𝑄 consecutive times and selects 𝑚 distinct queries. Let the corresponding times be 𝑢 1 < · · · < 𝑢𝑚 and define 𝑣 𝑗 = 𝜎ˆ𝜁2,𝑞𝑢 ,𝑢 𝑗 −1 (𝜽 cand ),

feas |Ifeas ∩ S| = |S| − |Ibad ∩ S|

𝑗 ∈ [𝑚].

𝑗

★

≥ (𝐼 − 𝑖 + 1) − 𝐼 bad 2 ≥ (𝐼 − 𝑖 ★ + 1) − 16(𝜆 + 1)𝛽𝑔,𝜏 𝛾 (𝐽max,𝜏 ) · 𝐼 2𝛼 .

Next, relate 𝐼 and 𝜏 − 𝑡 0 . Each effective round evaluates at most 𝑄 distinct queries, so 𝜏 −𝑡 0 ≤ 𝑄𝐼 and thus 𝐼 ≥ (𝜏 −𝑡 0 )/𝑄. Additionally, each effective round records at least one observation, so 𝐼 ≤ 𝜏 − 𝑡 0 and hence 𝐼 2𝛼 ≤ (𝜏 − 𝑡 0 ) 2𝛼 . Substituting these yields 𝜏 − 𝑡0 2 |Ifeas ∩ S| ≥ − 𝑖 ★ − 16(𝜆 + 1)𝛽𝑔,𝜏 𝛾 (𝐽max,𝜏 ) · (𝜏 − 𝑡 0 ) 2𝛼 𝑄 (𝜏 − 𝑡 0 ) − B · (𝜏 − 𝑡 0 ) 2𝛼 − C ≥ , (22) 𝑄 2 𝛾 (𝐽 ) and C = 𝑄 · 𝑖 ★ . where B = 16𝑄 (𝜆 + 1)𝛽𝑔,𝜏 𝜏 Conclusion. Plugging (22) into (19) gives

SR(𝜏) ≤ √︁

A , (𝜏 − 𝑡 0 ) − B · (𝜏 − 𝑡 0 ) 2𝛼 − C

At time 𝑢 𝑗 −1, for any query 𝑞 not yet selected in this inner iteration, its posterior variance equals its value at the iteration start, because no observation of query 𝑞 has been made. Moreover, by the preordering of 𝑞𝑢 𝑗 via 𝜑𝑖 in (9), this variance is at most 𝑣 𝑗 . For any previously selected query 𝑞𝑢𝑟 with 𝑟 < 𝑗, monotonicity of 𝜎ˆ ·,𝑞,· with respect to time (implied by the GP update rules) implies its variance at time 𝑢 𝑗 − 1 is at most 𝑣𝑟 (which is the variance at time 𝑢𝑟 − 1 before observing 𝑞𝑢𝑟 in this inner iteration). Hence, ∑︁

𝜎ˆ𝜁2,𝑞,𝑢 𝑗 −1 (𝜽 cand ) ≤

𝑗 −1 ∑︁

𝑣𝑟 + (𝑄 − 𝑗 + 1) 𝑣 𝑗 .

𝑟 =1

𝑞∈ Q

Dividing by 𝑄 2 gives an upper bound on 𝜎¯𝜁2,𝑢 𝑗 −1 (𝜽 cand ). Summing over 𝑗 = 1, . . . , 𝑚 and collecting coefficients yields 𝑚 𝑚 ∑︁
1 ∑︁ 𝜎¯𝜁2,𝑢 𝑗 −1 (𝜽 cand ) ≤ 2 (𝑚 − 𝑟 ) + (𝑄 − 𝑟 + 1) 𝑣𝑟 𝑄 𝑗=1 𝑟 =1

which is well-defined whenever (𝜏 − 𝑡 0 ) − B · (𝜏 − 𝑡 0 ) 2𝛼 − C > 0. By (22), this condition implies |Ifeas ∩ S| > 0, i.e., (♠) holds. This completes the proof. □

𝑚

≤

𝑄 + 𝑚 ∑︁ 𝑣𝑟 𝑄 2 𝑟 =1

≤

2 ∑︁ 𝑣𝑟 , 𝑄 𝑟 =1

𝑚

Proof of Lemma C.2. Fix 𝜁 ∈ {𝑐, 𝑔}, and recall that J𝑞,𝑡 = { 𝑗 ∈ [𝑡] : 𝑞 𝑗 = 𝑞} = { 𝑗𝑞 (1), · · · , 𝑗𝑞 (𝐽𝑞,𝑡 )} with 𝐽𝑞,𝑡 = |J𝑞,𝑡 | and 𝑗𝑞 (1) < · · · < 𝑗𝑞 (𝐽𝑞,𝑡 ). We denote the information gain of a configuration set 𝐴 = {𝜽 (1) , . . . , 𝜽 (𝐽 ) } ⊆ Θ, in any order, by I (𝐴) = 12 log det(𝑰 + 𝜆 −1 𝑲𝐴 ). Bounding the sum of query-wise variances. Fix a query 𝑞 ∈ Q and define the evaluation sequence 𝜽𝑞,𝑟 = 𝜽 𝑗𝑞 (𝑟 ) for 𝑟 ∈ [𝐽𝑞,𝜏 ]. Let 𝑣𝑞,𝑟 = 𝜎ˆ𝜁2,𝑞, 𝑗𝑞 (𝑟 ) −1 (𝜽𝑞,𝑟 ),

𝑟 ∈ [𝐽𝑞,𝜏 ].

For the observed configurations {𝜽𝑞,1, . . . , 𝜽𝑞,𝐽𝑞,𝜏 } on query 𝑞, a standard GP determinant identity yields 𝐽𝑞,𝜏   1 ∑︁ I ({𝜽𝑞,1, . . . , 𝜽𝑞,𝐽𝑞,𝜏 }) = log 1 + 𝑣𝑞,𝑟 /𝜆 . 2 𝑟 =1

where the last inequality uses 𝑚 ≤ 𝑄. Summing the above bound Í over all inner iterations, and noting that 𝑚 𝑟 =1 𝑣 𝑟 over all inner Í𝜏 2 iterations equals 𝑡 =𝑡0 +1 𝜎ˆ𝜁 ,𝑞𝑡 ,𝑡 −1 (𝜽𝑡 ), we obtain 𝜏 ∑︁

𝜏 𝜏 2 ∑︁ 2 2 ∑︁ 2 𝜎ˆ𝜁 ,𝑞𝑡 ,𝑡 −1 (𝜽𝑡 ) ≤ 𝜎ˆ (𝜽𝑡 ). 𝑄 𝑡 =𝑡 +1 𝑄 𝑡 =1 𝜁 ,𝑞𝑡 ,𝑡 −1 𝑡 =𝑡 0 +1 0 (26) Combining (26) with (25) yields 𝜏 ∑︁ 𝜎¯𝜁2,𝑡 −1 (𝜽𝑡 ) ≤ 4(𝜆 + 1)𝛾 (𝐽max,𝜏 ).

𝜎¯𝜁2,𝑡 −1 (𝜽𝑡 ) ≤

𝑡 =𝑡 0 +1

This completes the proof.

□

SCOPE: Cost-Efficient Model Selection for Compound AI Systems under Quality Constraints

C.4

Proof of Corollary 1

We first derive a bound that is explicit in both Λ and a failure probability 𝛿 ∈ (0, 1), and then plug in 𝛿 = Λ−2 . Let Δ𝐶 = 𝐶 max − 𝐶 min . Since ℓ𝑐 (𝜽, 𝑞) ∈ [𝐶 min, 𝐶 max ], we have 𝑐 (𝜽 ) ∈ [𝐶 min, 𝐶 max ] for all 𝜽 , and hence SR(𝜏) ≤ Δ𝐶 always. Fix Λ > 0 and 𝛿 ∈ (0, 1), and run SCOPE with failure probability 𝛿, where 𝛽𝜁 ,𝑡 is set equal to the right-hand side of (8). Let Econf be the confidence event used in the proof of Theorem 4.2. As established in that proof, the bound (11) holds on Econf , and Pr[Econf ] ≥ 1 − 𝛿. (27) Because Θ is finite, 𝛾 (𝐽max,𝑡 ) ≤ 𝛾 (|Θ|) and 𝛾 (𝑡) ≤ 𝛾 (|Θ|) for all 𝑡. Since 𝛽𝜁 ,𝑡 is set equal to the right-hand side of (8), for all 𝑡 ∈ N and 𝜁 ∈ {𝑐, 𝑔}, 𝛽𝜁 ,𝑡 ≤ 𝛽¯𝜁 (𝛿), where 𝛽¯𝜁 (𝛿) is defined by replacing 𝛾 (𝐽max,𝑡 ) in (8) with 𝛾 (|Θ|). Since 𝛾 (𝜏) ≤ 𝛾 (|Θ|) and 𝛽𝜁 ,𝜏 ≤ 𝛽¯𝜁 (𝛿), the constants A, B, C in Theorem 4.2 also satisfy the deterministic upper bounds   A ≤ Ā(𝛿), B ≤ B̄(𝛿), C = 𝑄 (−𝑔(𝜽 ★)) −1/𝛼 , where √︁ Ā(𝛿) = 8 𝛽¯𝑐 (𝛿) 𝑄 (𝜆 + 1)𝛾 (|Θ|),

B̄(𝛿) = 16𝑄 (𝜆+1) 𝛽¯𝑔 (𝛿) 2 𝛾 (|Θ|).

We define an explicit 𝑚 1 (𝛿) that ensures the denominator in (11) is at least (𝜏 − 𝑡 0 )/2. Let 𝑚 1 (𝛿) be the smallest integer satisfying nl m o 1 𝑚 1 (𝛿) ≥ max (4B̄(𝛿)) 1−2𝛼 , 4C . (28) Then for any integer 𝑚 ≥ 𝑚 1 (𝛿) we have B̄(𝛿) 𝑚 2𝛼 ≤ 𝑚/4 and C ≤ 𝑚/4, and hence 𝑚 . (29) 𝑚 − B 𝑚 2𝛼 − C ≥ 𝑚 − B̄(𝛿) 𝑚 2𝛼 − C ≥ 2 Therefore, on Econf ∩ {𝜏 − 𝑡 0 ≥ 𝑚 1 (𝛿)}, SR(𝜏) ≤ √︁ ≤ √︁

A

(using Theorem 4.2)

(𝜏 − 𝑡 0 ) − B(𝜏 − 𝑡 0 ) 2𝛼 − C Ā(𝛿)

(since A ≤ Ā(𝛿)) (𝜏 − 𝑡 0 ) − B(𝜏 − 𝑡 0 ) 2𝛼 − C Ā(𝛿) ≤ √︁ (using (29) with 𝑚 = 𝜏 − 𝑡 0 ) (𝜏 − 𝑡 0 )/2 √ 2 Ā(𝛿) ≤ √ . (30) 𝜏 − 𝑡0 Next, we control the probability that the budget-based stopping Í time 𝜏 is small. Recall 𝑦𝑐,𝑡 = ℓ𝑐 (𝜽𝑡 , 𝑞𝑡 ) + 𝜂𝑐,𝑡 and let 𝑀𝑠 = 𝑠𝑡 =1 𝜂𝑐,𝑡 . If 𝑅𝑐 = 0, then 𝑀𝑠 = 0 almost surely for all 𝑠, and the tail probability below is zero whenever 𝑛𝐶 max < Λ. Thus it remains to prove the tail bound when 𝑅𝑐 > 0. Lemma C.3. Assume 𝑅𝑐 > 0. For any integer 𝑛 ≥ 1 and any 𝑥 > 0,     𝑥2 . Pr max 𝑀𝑠 > 𝑥 ≤ exp − 1≤𝑠 ≤𝑛 2𝑛𝑅𝑐2 Since ℓ𝑐 (𝜽𝑡 , 𝑞𝑡 ) ≤ 𝐶 max , for every 𝑠, 𝑠 ∑︁ 𝑡 =1

𝑦𝑐,𝑡 =

𝑠 ∑︁ 𝑡 =1

ℓ𝑐 (𝜽𝑡 , 𝑞𝑡 ) +

𝑠 ∑︁ 𝑡 =1

𝜂𝑐,𝑡 ≤ 𝑠𝐶 max + 𝑀𝑠 .

(31)

KDD ’26, August 09–13, 2026, Jeju Island, Republic of Korea

By Lemma C.3, for any integer 𝑛 ≥ 1 such that Λ > 𝑛𝐶 max , " # 𝑠 ∑︁ Pr[𝜏 ≤ 𝑛] ≤ Pr ∃𝑠 ≤ 𝑛 : 𝑦𝑐,𝑡 > Λ 𝑡 =1



≤ Pr max 𝑀𝑠 > Λ − 𝑛𝐶 max 1≤𝑠 ≤𝑛   (Λ − 𝑛𝐶 max ) 2 ≤ exp − . 2𝑛𝑅𝑐2



(32)

Choose 𝑛 = ⌊Λ/(2𝐶 max )⌋. Then Λ−𝑛𝐶 max ≥ Λ/2 and 𝑛 ≤ Λ/(2𝐶 max ), so (32) yields   Λ 𝐶 max Pr[𝜏 ≤ 𝑛] ≤ exp − . (33) 4𝑅𝑐2 Assume in addition that Λ ≥ 4𝐶 max (𝑡 0 +1). Then 𝑛 = ⌊Λ/(2𝐶 max )⌋ satisfies 𝑛 − 𝑡 0 ≥ Λ/(4𝐶 max ). If also 𝑛 − 𝑡 0 ≥ 𝑚 1 (𝛿), then on Econf ∩ {𝜏 > 𝑛} we have 𝜏 − 𝑡 0 ≥ 𝑛 − 𝑡 0 ≥ 𝑚 1 (𝛿), and hence √ 2 Ā(𝛿) SR(𝜏) ≤ √ (using (30)) 𝜏 − 𝑡0 √ 2 Ā(𝛿) (since 𝜏 > 𝑛) ≤ √ 𝑛 − 𝑡0 √ 2 𝐶 max Ā(𝛿) ≤ . (since 𝑛 − 𝑡 0 ≥ Λ/(4𝐶 max )) √ Λ Taking expectation and using SR(𝜏) ≤ Δ𝐶 , we have E[SR(𝜏)]   𝑐 =E[SR(𝜏) 1{Econf ∩ (𝜏 > 𝑛)}] + E SR(𝜏) 1{Econf ∪ (𝜏 ≤ 𝑛)} √ 2 𝐶 max Ā(𝛿) 𝑐 ≤ + Δ𝐶 Pr[Econf ] + Δ𝐶 Pr[𝜏 ≤ 𝑛] √ Λ √   2 𝐶 max Ā(𝛿) Λ 𝐶 max ≤ , + Δ𝐶 𝛿 + Δ𝐶 exp − √ 4𝑅𝑐2 Λ where the last inequality uses (27) and (33). When 𝑅𝑐 = 0, the exponential term is omitted. This gives an explicit bound in terms of (Λ, 𝛿), provided that Λ ≥ 4𝐶 max (𝑡 0 + 1) and 𝑛 − 𝑡 0 ≥ 𝑚 1 (𝛿). Now set 𝛿 = Λ−2 and restrict to Λ ≥ 2 so that 𝛿 ∈ (0, 1). For all Λ ≥ 2, log(2𝑄/𝛿) ≤ log(2𝑄) + 2 log Λ. Thus there exists a constant 𝐾1 > 0, independent of Λ, such that for all Λ ≥ 2, B̄(Λ−2 ) ≤ 𝐾1 (1 + log Λ). Therefore, by (28), there exist constants 𝐾2, 𝐾3 > 0, independent of Λ, such that for all Λ ≥ 2, 1

𝑚 1 (Λ−2 ) ≤ 𝐾2 (1 + log Λ) 1−2𝛼 + 𝐾3 .

(34)

Since 𝛼 ∈ (0, 1/2) is fixed, there exists an integer 𝑚 2 ≥ 2 such that for all Λ ≥ 𝑚 2 , 1

𝐾2 (1 + log Λ) 1−2𝛼 + 𝐾3 ≤

Λ . 4𝐶 max

Let 𝑚 be any integer satisfying 𝑚 ≥ max{4𝐶 max (𝑡 0 + 1), 𝑚 2 }. Then for all Λ ≥ 𝑚, we have 𝑛 − 𝑡 0 ≥ Λ/(4𝐶 max ) ≥ 𝑚 1 (Λ−2 ) and Λ ≥ 4𝐶 max (𝑡 0 + 1). Applying the explicit (Λ, 𝛿) bound with 𝛿 = Λ−2 yields √   2 𝐶 max Ā(Λ−2 ) Λ 𝐶 max E[SR(𝜏)] ≤ + Δ𝐶 Λ−2 + Δ𝐶 exp − , √ 4𝑅𝑐2 Λ

KDD ’26, August 09–13, 2026, Jeju Island, Republic of Korea

Yiqian Huang, Shiqi Zhang, Tianyuan Jin, and Xiaokui Xiao

−2 where √︁ the exponential term is omitted when 𝑅𝑐 = 0. Finally, Ā(Λ ) = 𝑂 ( log Λ) with a hidden constant independent of Λ, and hence for all Λ ≥ 𝑚, ! √︂ log Λ , E[SR(𝜏)] = 𝑂 Λ

which completes the proof.

□

Proof of Lemma C.3. Fix 𝜆 > 0 and define, for 𝑠 ≥ 0,   𝜆 2 𝑅𝑐2 𝑍𝑠 = exp 𝜆𝑀𝑠 − 𝑠 , with 𝑀0 = 0 and 𝑍 0 = 1. 2

 2 2   𝜆 𝑅𝑐 E exp(𝜆𝜂𝑐,𝑠 ) | F𝑠 −1 ≤ exp , 2 and hence 

𝜆 2 𝑅𝑐2 E[𝑍𝑠 | F𝑠 −1 ] = 𝑍𝑠 −1 · E exp 𝜆𝜂𝑐,𝑠 − 2



 F𝑠 −1 ≤ 𝑍𝑠 −1 .

KL(𝑃 −Δ ∥ 𝑃+Δ ) = E−Δ [𝑁 1 ] · KL(N (Δ, 1) ∥ N (−Δ, 1))

Therefore, {𝑍𝑠 }𝑠 ≥0 is a nonnegative supermartingale with E[𝑍 0 ] = 1. By Ville’s inequality, for any 𝑎 > 0,   E[𝑍 0 ] 1 Pr max 𝑍𝑠 ≥ 𝑎 ≤ = . 1≤𝑠 ≤𝑛 𝑎 𝑎 If max1≤𝑠 ≤𝑛 𝑀𝑠 > 𝑥, then there exists 𝑠 ∈ [𝑛] such that 𝑀𝑠 > 𝑥, and thus     𝜆 2 𝑅𝑐2 𝜆 2 𝑅𝑐2 𝑠 ≥ exp 𝜆𝑥 − 𝑛 . 𝑍𝑠 = exp 𝜆𝑀𝑠 − 2 2 Consequently,      𝜆 2 𝑅𝑐2 Pr max 𝑀𝑠 > 𝑥 ≤ Pr max 𝑍𝑠 ≥ exp 𝜆𝑥 − 𝑛 1≤𝑠 ≤𝑛 1≤𝑠 ≤𝑛 2   𝜆 2 𝑅𝑐2 ≤ exp −𝜆𝑥 + 𝑛 . 2 Optimizing over 𝜆 > 0 by choosing 𝜆 = 𝑥/(𝑛𝑅𝑐2 ) gives     𝑥2 Pr max 𝑀𝑠 > 𝑥 ≤ exp − , 1≤𝑠 ≤𝑛 2𝑛𝑅𝑐2 which completes the proof.

D

□

Tightness Results

To show that the dependence Ω(1/(Δ★) 2 ) cannot be removed from any convergent simple-regret guarantee under Problem 1, where Δ★ = −𝑔(𝜽 ★), we construct a set of counterexamples. Let 𝑄 = 1, Q = {𝑞}, Θ = {𝜽 0, 𝜽 1 }, 𝑠 (𝜽 0 ) = 1, 𝜖 = 1/2, 𝑐 (𝜽 0 ) = 1 and 𝑐 (𝜽 1 ) = 0, so 𝑠 0 = 1/2. For each Δ ∈ (0, 1/2], define two instances IΔ+ : 𝑠 (𝜽 1 ) = 1/2 + Δ,

and in particular, any guarantee of the form E[SR(𝜏)] ≤ 𝜀 with 𝜀 < 1 − 𝛿 requires   (1 − 𝛿 − 𝜀) 2 1 𝜏 ≥ . = Ω (Δ★) 2 (Δ★) 2 Proof. Fix Δ ∈ (0, 1/2] and define the event 𝐴 = {𝜽 out = 𝜽 1 }. On IΔ− , 𝜽 1 is infeasible since 𝑔(𝜽 1 ) = Δ > 0. Therefore, 𝛿-correctness implies Pr IΔ− (𝐴) ≤ 𝛿. Let 𝑃 −Δ and 𝑃+Δ denote the joint laws of the full transcript under Í IΔ− and IΔ+ . Let 𝑁 1 = 𝜏𝑡=1 1{𝜽𝑡 = 𝜽 1 } be the number of evaluations of 𝜽 1 , so 𝑁 1 ≤ 𝜏 almost surely. The two instances differ only in the distribution of 𝑦𝑔,𝑡 when 𝜽𝑡 = 𝜽 1 . Under IΔ− , 𝑦𝑔,𝑡 ∼ N (Δ, 1), while under IΔ+ , 𝑦𝑔,𝑡 ∼ N (−Δ, 1). Using the chain rule for KL divergence under adaptive sampling [13], we have

By Assumption 1, for each 𝑠 ≥ 1,



Theorem D.1. Under the above construction, on IΔ+ the simple regret satisfies √
E[SR(𝜏)] ≥ 1 − 𝛿 − Δ★ 𝜏 + , (35)

IΔ− : 𝑠 (𝜽 1 ) = 1/2 − Δ.

Assume that the observations on 𝑔 satisfy 𝑦𝑔,𝑡 = 𝑔(𝜽𝑡 ) + 𝜂𝑡 with 𝜂𝑡 ∼ N (0, 1), and the observations on 𝑐 satisfy 𝑦𝑐,𝑡 = 𝑐 (𝜽𝑡 ). One can verify that these instances satisfy Assumptions 1–2 with fixed constants. Fix 𝛿 ∈ (0, 1/4) and an integer 𝜏 ∈ N. Let 𝜋 be any adaptive algorithm that makes 𝜏 observations and outputs 𝜽 out ∈ Θ. Assume that for every Δ ∈ (0, 1/2], when the true instance is IΔ− , the algorithm is 𝛿-correct. The impossibility theorem follows.

= E−Δ [𝑁 1 ] · 2Δ2 ≤ 2𝜏Δ2 . Pinsker’s inequality then gives √︁ √ ∥𝑃 −Δ − 𝑃 +Δ ∥ TV ≤ KL(𝑃 −Δ ∥ 𝑃+Δ )/2 ≤ Δ 𝜏 . Therefore √ Pr+ (𝐴) ≤ Pr− (𝐴) + ∥𝑃 −Δ − 𝑃 +Δ ∥ TV ≤ 𝛿 + Δ 𝜏,

IΔ

IΔ

√ 𝑐 + (𝐴 ) ≥ (1 − 𝛿 − Δ 𝜏)

and hence Pr I +. Δ On IΔ+ , 𝜽 1 is feasible and optimal since 𝑐 (𝜽 1 ) = 0 < 𝑐 (𝜽 0 ) = 1, so 𝜽 ★ = 𝜽 1 and Δ★ = −𝑔(𝜽 ★) = Δ. Thus SR(𝜏) = 1 exactly on 𝐴𝑐 , and E[SR(𝜏)] = Pr(𝐴𝑐 ). Substituting Δ★ = Δ yields (35). Rearranging √ (1 − 𝛿 − Δ★ 𝜏)+ ≤ 𝜀 with 𝜀 < 1 − 𝛿 gives the stated necessary condition on 𝜏. □

Related documents

• String Diagrams for Process Mining#978502
• ZigZag Trie: A Novel Index for Contextual Queries#978503
• A Functional Pilot for Certified Freshness-Aware Semantic--Spatial Range Retrieval#978504
• Efficiently Linking Unstructured Data for Multi-step Reasoning#978505