{"id":"20c845a5-50f1-4b69-a76d-85da87f2a7ae","arxiv_id":"2608.04333","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"A cost-aware multi-objective bandit framework for LLM configuration evaluation, with a UCB index for online selection and a cost-aware gap-elimination algorithm for Pareto identification, backed by logarithmic and exponential guarantees.","lead":"This paper adds evaluation costs and multiple objectives to the standard bandit framework and proposes two algorithms for choosing LLM configurations under a limited budget. It proves logarithmic budget regret for online selection and exponentially decaying error for Pareto set identification, with experiments on GSM8K and PIQA.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified: the proofs of Theorems 1 and 2 hold up under scrutiny, including the time-uniform Hoeffding bound.","rationale":"I read the paper in good faith and stress-tested the two main theorems. Theorem 1's regret analysis is a standard UCB argument: the uniform concentration event, optimism of the optimal arm, and the per-arm pull bound all check out; the Lipschitz bound on the product hypervolume is correct, and the cost-denominator handling with the lower confidence bound is sound. Corollary 1's conversion from efficiency regret to standard hypervolume regret follows from the optimal benchmark lemma and the optional-sampling identity; the algebra is consistent. Theorem 2 is the most delicate part. The deterministic correctness lemma for the EGE-SR elimination rule appears valid: the dominator-preservation invariant is proved by contradiction with the tie-breaking rule, and the cases cover empirically dominated and empirically Pareto-optimal selected arms. The cost-aware sampling schedule is feasible under budget B by summation by parts and the bound (C_r−C_{r+1})/C_r ≤ 1/(1+(k_r−1)λ), which is correct because the removed cost is at most 1 and the remaining cost is at least (k_r−1)λ. The phase-wise sample lower bound nrγ_(k_r)² ≥ B/(2L_{K,λ}H_{μ,c}) follows from the definition of H_{μ,c}, and the concentration step uses a valid time-uniform Hoeffding inequality. The reader's suspicion about the explicit constant in (9) does not land: a direct Ville-inequality argument gives exactly 2exp(−2Nx²) for two-sided deviations. The reader's weakest assumption about zero classification gaps is a real limitation for the LLM application, but it is explicitly assumed in the theorem and acknowledged by the authors; it does not undermine the theoretical claim conditional on γ_i>0. Thus I find no significant objection, and I would leave the conditional verdict unchanged.","tokens_in":28505,"tokens_out":35677,"duration_ms":374179,"concrete_test":"Independently verify inequality (9) by Monte Carlo: for Bernoulli arms with p=0.5, set N=1000 and x=0.05, and compute over 10^5 seeds the frequency of sup_{n≥1000}|mean_n − 0.5| > 0.05. The bound is 2exp(−2·1000·0.0025) = 2exp(−5) ≈ 0.0135; if the observed frequency exceeds this, (9) and the explicit constant in Theorem 2 would need revision. A complementary analytical check is to re-derive (9) from Ville's inequality on the Hoeffding supermartingale M_n with λ=4x and confirm the exponent is exactly 2Nx² with no extra factor.","verdict_should_be":"UNCHANGED","load_bearing_attack":"I could not identify a load-bearing correctness concern. The central theoretical claims are internally consistent. The time-uniform bound (9) flagged by the reader is actually valid: for rewards in [0,1], Hoeffding's lemma gives E[exp(λ(X−μ))] ≤ exp(λ²/8), so M_n = exp(λ(S_n−nμ) − λ² n/8) is a nonnegative supermartingale. Taking λ = 4x, the event that sup_{n≥N}(mean_n−μ) ≥ x implies M_n ≥ exp(2Nx²), and Ville's inequality yields P ≤ exp(−2Nx²); the two-sided bound adds a factor 2. Applying this to the data-dependent target n_r is legitimate because n_r is deterministically lower-bounded by N = B/(2 L_{K,λ} H_{μ,c} γ_(k_r)²), and the random-time deviation is a subset of the deterministic supremum event. The zero-gap issue is explicitly assumed away by γ_i > 0, and the paper is transparent that real LLM datasets contain near-tied means, using a curated 14-arm subset for exact recovery and F1 on the full sets. This is a stated limitation rather than an internal flaw in the theorem.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces a cost-aware multi-objective bandit formulation for LLM configuration evaluation, where each arm pull yields a vector-valued reward in [0,1]^D and incurs an arm-dependent cost. For online configuration selection, it proposes CoHV-UCB, which selects the arm maximizing an optimistic product-hypervolume divided by a lower confidence bound on cost, and proves an O(Σ_{i≠i*} C^2_{λ,H} log B / Δ_i) bound on hypervolume-efficiency regret (Theorem 1), together with a standard-hypervolume regret corollary (Corollary 1). For fixed-budget Pareto identification, it proposes CoPSI, a successive-elimination algorithm with cost-aware phase targets, and proves an error probability of order exp(-B/(256 L_{K,λ} H_{μ,c})) (Theorem 2). Experiments on GSM8K and PIQA configuration sets compare the methods against cost-insensitive and single-objective baselines; full-set experiments use F1 because of near-tied means, while exact recovery is demonstrated on a curated 14-arm subset.","tokens_in":28692,"tokens_out":25840,"duration_ms":266058,"significance":"If the proofs are correct, this is the first theoretical treatment of cost-aware multi-objective bandits, and the two bounds match the best-known single-objective budgeted rates in their budget and gap dependence. The proofs are standard but careful: Theorem 1 is a clean UCB analysis with a clipped cost LCB and a Lipschitz argument for the product hypervolume; Theorem 2 adapts EGE-SR with a budget-feasible sampling schedule and a time-uniform Hoeffding bound. I checked the time-uniform step flagged in the review: the application to the data-dependent target n_r is legitimate because n_r is deterministically lower-bounded by B/(2 L_{K,λ} H_{μ,c} γ^2_{k_r}), so the random-time deviation is a subset of the deterministic supremum event. The paper is unusually transparent about the main limitation of the Pareto-identification theorem: exact recovery requires strictly positive classification gaps γ_i>0, and the full LLM datasets contain near-tied means, so exact recovery is only demonstrated on a curated 14-arm subset while full sets are evaluated with F1.","major_comments":[],"minor_comments":[{"comment":"The definition of Δ_i^+ contains a stray double plus sign in the expression 'M(j,i) + + (Δ_j^-)^+'; it should read M(j,i)^+ + (Δ_j^-)^+, and the same typo appears in the proof of Lemma 2.","section":"§3.2 and Appendix D"},{"comment":"The relationship among T(B), the while-loop in Algorithm 1, and the possible boundary pull is not stated precisely: as written, Algorithm 1 can perform one evaluation whose cost pushes the cumulative cost above B, whereas R_HV^B sums only over t≤T(B). Please clarify whether n_i(B) counts the boundary pull and state the convention in the theorem.","section":"§4.1 and Theorem 1"},{"comment":"The experimental confidence radii use profiling-calibrated scale factors (s_r=s_c=0.01) that are much smaller than the uncalibrated radius required by Theorem 1 (α≥2); please add a sentence noting that the experiments use calibrated radii and that the theoretical guarantee applies to the uncalibrated choice.","section":"Appendix A"},{"comment":"Several figure captions and axis labels appear as Unicode/encoding artifacts in the manuscript text, with sequences such as '/uni00000013/...' replacing readable labels; these need to be regenerated with a proper text encoding.","section":"Figures"},{"comment":"The main text should state explicitly that the reward vector has D=2 coordinates (accuracy and normalized inverse latency); this detail currently appears only in the appendix.","section":"§5.1"},{"comment":"The claim of matching single-objective budgeted bandits 'in budget and gap dependence' should be qualified as matching up to the problem-dependent constant C_{λ,H}, since the dependence on λ and D enters the stated bound.","section":"Abstract and §1"},{"comment":"The conclusion repeats the future-work item about small or unreliable gaps; given that the full datasets contain near-tied means, this limitation could also be stated in the abstract or introduction for a reader who only sees the headline guarantees.","section":"Conclusion"}],"recommendation":"minor_revision","confidential_remarks":"The paper is technically sound and the central claims are likely correct. The only substantive caveat is the gap between the exact-identification theorem's γ_i>0 assumption and the full LLM datasets, which the authors handle transparently. I recommend a minor revision to tighten the budget-overshoot convention and presentation. The 'first cost-aware multi-objective bandits' claim should be checked against Poon et al. (2025) and Ong et al. (2025), though it appears defensible for the multi-objective setting with theoretical guarantees."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: this is a genuine extension, not a repackaging. The cost-aware combination is new relative to the cited literature — Ding et al. is single-objective, Kone et al. is cost-insensitive — and the cost-aware complexity H_{mu,c} is a reasonable object. The proofs are mostly standard but careful, and the piece I was most suspicious about, the time-uniform Hoeffding bound behind Theorem 2, checks out. The stress-test note is right: applying Ville's inequality to the Hoeffding supermartingale and using the deterministic lower bound on n_r is legitimate. The reader's conditional verdict is sensible but slightly overcautious on that point; the zero-gap issue is the real limitation, and the paper owns it explicitly by assuming gamma_i > 0 and by reporting F1 on the full sets where ties exist.\n\nWhat the paper does well: Theorem 1 is a clean UCB analysis with a cost LCB denominator; the benchmark bound in Lemma 1 and the regret decomposition in Corollary 1 are neat. Theorem 2's elimination argument is more intricate, but the deterministic classification lemma and the budget-feasibility summation-by-parts step are plausible and detailed in the appendix. The experiments are transparent: hyperparameters are selected on a disjoint profiling split, replays are paired, and the full-set results are reported as F1 rather than overclaimed as exact recovery.\n\nSoft spots, in proportion: the online algorithm reduces multi-objective selection to a single scalarized index (hypervolume per cost), so the 'multi-objective' claim is real but less rich than vector-valued regret. The experimental gains over cost-insensitive baselines are modest, especially on GSM8K (0.004 vs 0.006 error for PSI-SR), consistent with the limited cost dispersion in those benchmarks. The 256 constant in Theorem 2 is loose but not a correctness issue. The gamma_i > 0 assumption is genuine, and the paper's own data show near-tied means; the 14-arm curated subset is an honest response, but deployment scenarios with very small gaps would need the approximate F1 treatment rather than the exponential guarantee.\n\nWho it is for: bandit theorists working on budgeted or cost-aware settings, and LLM evaluation researchers who want principled budget allocation across configurations with multiple objectives. It deserves a serious referee: the math is internally consistent, the citation pattern is honest, and the limitations are stated rather than hidden.\n\nMy recommendation: send it to review. Ask a referee to pressure-test the elimination lemma's constants and to push the experiments into the near-zero-gap regime, but this is not a desk-reject paper.","headline":"A solid, honestly-written extension of budgeted bandits to multi-objective evaluation; the flagged Hoeffding concern is not a real flaw, and the zero-gap limitation is assumed away transparently.","tokens_in":29300,"tokens_out":1583,"would_cite":true,"duration_ms":18205,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["62L05","68W27","90C29"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper claims that cost-aware multi-objective bandits can achieve the same logarithmic regret as single-objective budgeted bandits, using a hypervolume-per-cost index and cost-aware Pareto gap elimination.","keywords":["cost-aware multi-armed bandits","multi-objective bandits","hypervolume regret","Pareto set identification","LLM configuration evaluation","budgeted bandits","empirical gap elimination"],"falsifier":"Simulate CoPSI on a valid instance with known strictly positive gaps, for example three arms in two objectives with gaps 0.001 and 0.002 and costs differing by a factor of four, and measure the log misidentification probability over many repetitions at the budget values specified by the theorem; if the empirical error curve does not lie below $2K^2D\\exp(-B/(256L_{K,\\lambda}H_{\\mu,c}))$ at those budgets, the claimed exponential rate fails. Alternatively, run CoPSI on an instance with two arms sharing exactly the same mean vector, where $\\gamma_i = 0$; the paper's own assumption excludes this, and the error probability will remain bounded away from zero no matter the budget, confirming that the guarantee depends on the strictly-positive-gap condition.","tokens_in":28254,"feed_emoji":"🎯","tokens_out":6812,"duration_ms":68388,"temperature":0.7,"pith_summary":"The paper aims to establish that LLM configuration evaluation can be treated as a cost-aware multi-objective bandit problem, and that both online selection and fixed-budget Pareto identification admit algorithms with strong guarantees despite configuration-dependent evaluation costs. For online selection, it proposes CoHV-UCB, which pulls arms by an optimistic hypervolume-per-cost index, and proves hypervolume-efficiency regret of order $O\\left(\\sum_{i\\neq i^*}\\frac{\\log B}{\\Delta_i}\\right)$, retaining the logarithmic budget dependence of single-objective budgeted bandits. For fixed-budget identification, it proposes CoPSI, a cost-aware gap-elimination algorithm whose misidentification probability decays exponentially with the budget at a rate governed by a cost-aware complexity $H_{\\mu,c}$. The framework also connects to concrete LLM configuration choices, where accuracy and efficiency are competing objectives and token costs vary across configurations.","feed_headline":"Cost-aware bandits hit log-budget regret in multi-objective search","feed_subtitle":"New algorithms balance accuracy and token cost, with a regret bound that grows only logarithmically in the evaluation budget.","key_machinery":"The central machinery is the hypervolume-efficiency index for online selection and cost-aware empirical gap elimination for identification. Hypervolume efficiency $\\nu_i = H(\\mu_i)/\\mu^c_i$ converts a vector objective and a scalar cost into a single per-cost utility; CoHV-UCB's optimism step constructs an upper confidence bound on the hypervolume and a lower confidence bound on cost to form an optimistic efficiency index, which is what forces the optimal arm to remain competitive and limits suboptimal pulls to $O(\\log B/\\Delta_i^2)$. For Pareto identification, CoPSI uses empirical pairwise margins $\\hat m_r(i,j)$ and $\\hat M_r(i,j)$ to define a classification gap $\\hat\\gamma_{i,r}$ for each active arm, and its cost-aware sampling target $n_r$ depends on the aggregate cost $C_r$ of the active set; this couples the statistical gap $\\gamma_{(k)}$ to the budget via $H_{\\mu,c} = \\max_A C(A)/\\gamma^2_{(|A|)}$ and makes the exponential error decay follow from Hoeffding concentration at adaptive targets.","core_discovery":"The central claim is that cost awareness and multi-objectivity can be combined without sacrificing classical bandit efficiency. CoHV-UCB defines hypervolume efficiency $\\nu_i = H(\\mu_i)/\\mu^c_i$ as the value of arm $i$ per unit expected cost, builds an optimistic index $H(U_{i,t})/c_{i,t}$ with UCB-adjusted reward coordinates and a lower confidence bound on cost, and shows that the expected number of pulls of any suboptimal arm is $O(\\log B / \\Delta_i^2)$, yielding regret $O\\left(\\sum_{i\\neq i^*} \\frac{\\log B}{\\Delta_i}\\right)$. CoPSI instead allocates samples with a phase-dependent target $n_r = \\lfloor B/(L_{K,\\lambda} C_r)\\rfloor$ that depends on the aggregate cost $C_r$ of the active configuration set, and removes the active arm with the largest empirical classification gap; its error probability is bounded by $2K^2D\\exp(-B/(256L_{K,\\lambda}H_{\\mu,c}))$, where $H_{\\mu,c}$ is the worst-case ratio of active-set cost to squared classification gap. Together these theorems assert that configuration-dependent evaluation costs can be handled with the same logarithmic regret and exponential-error decay as cost-blind or cost-unaware settings, and the experiments on GSM8K and PIQA support that the proposed indices and elimination rules save budget in practice.","pith_inferences":["The hypervolume-per-cost construction could transfer to other resource-constrained multi-objective choice problems, such as prompt routing or model selection in production, where cost is monetary or latency; the paper does not explore this transfer.","Because the fixed-budget theorem assumes known deterministic costs, an untested natural extension is to unknown or random evaluation costs in the identification setting; the paper's stochastic-cost robustness experiment gives preliminary evidence but no theorem.","The near-tied empirical means in the full datasets suggest that exact Pareto set identity is often a knife-edge notion in real LLM evaluation, and an approximate-recovery criterion such as Pareto F1 may be the more operational target; a theory of approximate cost-aware Pareto identification would be a direct follow-up.","The regret bound's dependence on the efficiency gap $\\Delta_i$ implies that near-tied configurations dominate the guarantee, so a practical prefilter that removes nearly equivalent arms could improve allocation, though the paper does not propose such a prefilter."],"forward_implications":["CoHV-UCB gives an online policy for LLM configuration selection that balances accuracy and efficiency, with a regret bound that grows only logarithmically in the evaluation budget, so efficiency regret diminishes quickly as more tokens are spent.","CoPSI gives a principled cost-aware way to decide which configurations to keep evaluating under a fixed budget, and its error probability decays exponentially with the budget at a rate set by a cost-aware complexity measure.","When all evaluation costs are identical, CoPSI's guarantee reduces to the standard fixed-budget Pareto set identification rate, so the new algorithm is a strict generalization of existing methods.","The standard cumulative hypervolume regret also obeys the same $O(\\sum_{i\\neq i^*} \\log B/\\Delta_i)$ bound, so the cost-aware index does not sacrifice the usual multi-objective quality measure.","The complexity $H_{\\mu,c}$ makes the cost of identifying a Pareto front concrete: configurations that are cheap but hard to classify can receive more samples without exceeding the total budget."],"supporting_citations":[{"why":"Supplies the single-objective budgeted bandit baseline whose logarithmic regret and gap dependence CoHV-UCB's bound is designed to match.","marker":"Ding et al. [2013]"},{"why":"Provides the fixed-budget Pareto set identification method and gap construction that CoPSI extends with cost-aware sampling.","marker":"Kone et al. [2024]"},{"why":"Establishes Pareto front identification from stochastic bandit feedback, the identification objective CoPSI addresses under a budget.","marker":"Auer et al. [2016]"},{"why":"Introduces hypervolume scalarization machinery that underlies the hypervolume indicator used in CoHV-UCB.","marker":"Zhang and Golovin [2020]"},{"why":"Develops adaptive gap-elimination algorithms for relaxed fixed-confidence Pareto identification, the lineage from which CoPSI's empirical gap rule is drawn.","marker":"Kone et al. [2023]"}],"fun_headline_variants":["Cost-aware multi-objective bandits: log-budget regret","Log-budget regret for cost-aware bandits in LLM tuning","Budgeted LLM config selection via multi-objective bandits","Cost-aware bandits achieve log-budget regret on LLMs","Pareto identification under budget with cost-aware bandits"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The fixed-budget guarantee for CoPSI requires every configuration to have a strictly positive classification gap $\\gamma_i > 0$, so that exact Pareto identification is statistically well posed; if two arms have identical or arbitrarily close mean reward vectors, the exponential error bound no longer applies, and the experiments resort to a curated 14-arm subset or an approximate F1 score.","fun_headline_variants_meta":{"raw":{"variants":["Cost-aware multi-objective bandits: log-budget regret","Log-budget regret for cost-aware bandits in LLM tuning","Budgeted LLM config selection via multi-objective bandits","Cost-aware bandits achieve log-budget regret on LLMs","Pareto identification under budget with cost-aware bandits"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000716,"raw_usage":{"total_tokens":3314,"prompt_tokens":1140,"completion_tokens":2174,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":756,"completion_tokens_details":{"reasoning_tokens":2088}},"tokens_in":756,"tokens_out":2174,"duration_ms":15213,"temperature":1.0,"reasoning_tokens":2088,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-08T19:35:12.018875+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Simulate CoPSI on a valid instance with known strictly positive gaps, for example three arms in two objectives with gaps 0.001 and 0.002 and costs differing by a factor of four, and measure the log misidentification probability over many repetitions at the budget values specified by the theorem; if the empirical error curve does not lie below $2K^2D\\exp(-B/(256L_{K,\\lambda}H_{\\mu,c}))$ at those budgets, the claimed exponential rate fails. Alternatively, run CoPSI on an instance with two arms sharing exactly the same mean vector, where $\\gamma_i = 0$; the paper's own assumption excludes this, and the error probability will remain bounded away from zero no matter the budget, confirming that the guarantee depends on the strictly-positive-gap condition.","supporting_citations":[{"cited_title":"2013 , booktitle =","cited_arxiv_id":null,"evidence_quote":"Supplies the single-objective budgeted bandit baseline whose logarithmic regret and gap dependence CoHV-UCB's bound is designed to match."}],"review_version":1}