acceptodds
Under review as a conference paper at ICLR 2027

CostAda: Cost-Calibrated Credit for Budget-Aware LLM Discovery

Abstract

Large language models increasingly support scientific and algorithmic discovery through inference-time search over evaluated candidates. Existing adaptive discovery controllers assign credit based only on score progress, even though prompt length, retries, and guidance calls cause search actions to incur different token costs. Under a fixed search budget, the controller must decide which frontier to develop and whether its gain justifies the realized cost before the budget is exhausted. We prove that, in the worst case, cost-blind control can forfeit all but a vanishing fraction of attainable quality as frontier count and cost heterogeneity grow. To address this limitation, we introduce CostAda, an adaptive controller built on cost-calibrated frontier utility. By valuing progress relative to realized action cost and conditioning credit on the remaining budget, CostAda coordinates local exploration intensity, frontier allocation, and budgeted tactic intervention. Realized action cost and remaining budget therefore shape the search rather than serving only as accounting variables or a stopping rule. Across eight benchmarks with GLM-5 and GPT-5.4, CostAda reaches the strongest baseline's full-budget quality with at most half the budget on thirteen of sixteen benchmark–backbone pairs and achieves the strongest final quality on all sixteen pairs.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
Large Language Models, Scientific Discovery

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_qNbROpenReview ↗
Rating
2
Confidence
1
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper studies LLM-driven evolutionary discovery (AlphaEvolve-style) under a fixed dollar budget. It argues that existing adaptive controllers (AdaEvolve, EvoX) assign credit from score progress alone, ignoring that LLM actions have different realized costs. The proposed controller, CostAda, divides a progress signal by a log-scaled cost factor. It also conditions on the remaining budget: credit shifts from local to global improvement, and the cost penalty strengthens as budget runs out. This credit drives three controls: local exploration intensity, UCB-based frontier allocation, and budget-gated "guide" interventions. A worst-case separation result (Prop. 1) shows cost-blind controllers can lose most attainable value as frontier count and cost ratio grow. Experiments use 8 benchmarks, two backbones (GLM-5 at $1, GPT-5.4 at $5), and 3 seeds. CostAda reports the best mean final quality on all 16 benchmark–backbone pairs, and reaches the strongest baseline's final quality with at most half the budget on 13 of 16.

Critical strengths
  • The problem is practical and timely. Dollar-denominated budgets matter for these systems, and comparing methods at budget cutoffs rather than iteration counts is the right protocol (Fig. 4 shows the same budget yields 53, 60, and 80 iterations across methods).
  • Reporting is thorough: per-cutoff tables, normalized AUC, budget overshoot accounting, a controller trace, fixed constants across benchmarks, and released code.
  • Gains are consistent in direction across both backbones. The independent B=0.5 runs (Table 9) are a good check that the method adapts to the specified budget rather than benefiting from truncation.
Critical weaknesses
  1. Theory and method are loosely connected. Prop. 1's cost-aware policy ranks by gain per cost, but CostAda divides by 1 + λᶜ·log(1 + c̃), a much weaker correction. For equal gains, a 6× costlier action gets only ~21% less credit early in the run and ~1.7× less at budget exhaustion, not 6×. The separation also needs large K, while all reported runs use K = 2 (App. C.3). The result itself is close to known bandits-with-knapsacks arguments (App. B).
  2. Cost is not shown to be an informative signal. All modes use the same context structure (App. C.2), so cost may not differ systematically by frontier; the 4–6× variation (Fig. 4) could be output-length or retry noise. No analysis links cost to frontier, mode, or later gain. The gain is also not "more iterations per dollar": EvoX runs more iterations (80 vs. 60, Fig. 4) yet scores lower. Sec. 5.5 credits the largest gain to the new low-yield guide trigger, so intervention timing, not cost-calibrated credit, may drive part of the improvement.
  3. Ablations raise consistency questions.
    • Ablated variants land both far below and well above AdaEvolve (Heilbronn Triangle, GLM-5: 0.0228 / 0.0251 vs. 0.0303; Signal Processing, GLM-5: 0.6851 vs. 0.6393). How does CostAda's scaffold differ from AdaEvolve's?
    • CostAda's ablation-table numbers differ from the main tables except on Signal Processing (e.g., 2.6281 vs. 2.6306; AUC 0.9517 vs. 0.9295), suggesting separate runs.
    • Only 3 of 8 benchmarks are ablated.
  4. Missing baselines. The obvious one is AdaEvolve with reward divided by realized cost. The cited budget-aware discovery methods (Xing et al., 2026; Yang et al., 2026b) are not compared, and cost-aware Bayesian optimization (e.g., EI per unit cost) is not discussed.
  5. Weak statistical support. With 3 seeds and no significance tests, several "wins" fall within one std (e.g., Third Autocorrelation GLM-5: 1.4658 ± 0.0037 vs. 1.4685 ± 0.0014; Circle Packing GPT-5.4: 2.6248 ± 0.0046 vs. 2.6196 ± 0.0030). Some half-budget wins are razor-thin (2.6211 vs. 2.6196). Under GPT-5.4, three tasks account for ~75% of the aggregate margin over AdaEvolve.
  6. Circle Packing reference. Cited work (ShinkaEvolve, TTT-Discover) already reports ~2.635983 for n=26. CostAda's 2.6360 matches this rather than setting a new best. Please report more digits and state whether feasibility is checked exactly or with slack.
  7. Scale and sensitivity. Runs are short (~40–80 iterations). About ten controller constants (Table 4) have no sensitivity analysis or stated selection procedure. Evaluator cost is excluded (App. A).
Questions for authors
  1. How much of realized-cost variance is explained by frontier or sampling mode versus per-call noise? Is cost predictive of subsequent gain?
  2. Can you report AdaEvolve with plain gain-per-cost credit, and a CostAda variant with all budget-aware components removed? How does the latter compare to AdaEvolve?
  3. Why do the CostAda numbers differ between the ablation and main tables for some benchmarks, and how were runs selected?
  4. How does CostAda behave with more frontiers and longer runs (hundreds of iterations)?
  5. Can you add more seeds or significance tests for the main claims?
  6. How were the controller constants chosen, and how sensitive are results to them?
Reviewer_GFBEOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
3(+1)
Read review
Paper summary

This paper proposes CostAda, a budget-aware controller for LLM-based scientific and algorithmic discovery. Instead of assigning credit based solely on score improvements, CostAda incorporates realized action costs and remaining budgets to guide local exploration, frontier allocation, and tactic intervention. The paper provides a worst-case analysis of cost-blind control and evaluates the method on eight benchmarks with two LLM backbones. The results show consistent improvements in solution quality and budget efficiency over AdaEvolve and EvoX.

Critical strengths
  • The paper addresses a practical and important problem in LLM-based discovery. Since search actions can have substantially different costs, incorporating actual resource consumption into search decisions is a meaningful direction, particularly for systems operating under limited inference budgets. 
  • The experimental results are convincing. CostAda achieves the highest mean final quality across all 16 benchmark-backbone settings, and the comparisons are conducted under matched search-side LLM budgets. The budget-performance curves further demonstrate that the method often finds strong solutions earlier than the baselines. 
  • The ablation studies provide useful evidence for the proposed design. Removing cost calibration, remaining-budget conditioning, or intervention gating consistently reduces performance in the tested settings. The additional small-budget experiments and detailed cost accounting also strengthen the empirical evaluation.
Critical weaknesses
  • CostAda largely follows the three-level control structure of AdaEvolve, with local exploration, frontier allocation, and tactic intervention, while incorporating realized action costs and remaining-budget information into the decision rules. Although these modifications are reasonable, most of them take the form of relatively simple reward shaping and budget-dependent heuristics rather than a substantially new optimization mechanism. A natural comparison would be a lightweight cost-aware version of AdaEvolve that simply normalizes progress by realized action cost. Without this baseline, it is difficult to assess whether the additional design complexity of CostAda is necessary. 
  • Proposition 1 establishes that cost-blind controllers can perform arbitrarily poorly in a constructed setting with identical gains and heterogeneous action costs. However, this result primarily motivates the general importance of cost awareness, which is already well established in budget-constrained optimization. It does not characterize the proposed utility function, budget-conditioned UCB allocation, or intervention rules. As a result, the theoretical analysis offers limited insight into why the particular CostAda design should outperform simpler cost-aware alternatives. 
  • While the experiments cover eight benchmarks and two LLM backbones, the evaluation of frontier allocation remains relatively limited. Appendix C.3 indicates that all reported runs use only two frontiers, with no new frontiers introduced during search. This leaves the effectiveness of the allocation mechanism under larger or more dynamic frontier populations insufficiently explored. 
  • The reported efficiency gains are measured using search-side LLM expenditure, excluding evaluator execution costs. This is a reasonable controlled setting, but actual scientific discovery workloads can have substantial and heterogeneous evaluation costs. It remains unclear whether the same budget-allocation behavior would remain effective when these costs dominate. In addition, the implementation of local exploration intensity in skydiscover/search/costada/adaptation.py appears to differ from the formula in Section 4.3, which introduces uncertainty about the exact configuration used for the reported results.
Questions for authors

Please see the Critical Weaknesses section for the main concerns. I would particularly appreciate the authors' clarification on the methodological novelty, the benefits over simpler cost-aware baselines, the connection between the theoretical analysis and the proposed method, the generalizability of the experimental findings, and the implementation inconsistency.

Reviewer_CJPTOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper proposes CostAda, a cost-aware controller for LLM-driven evolutionary search. Instead of crediting search directions by score improvement alone, it credits them by improvement relative to the realized LLM cost, and it adjusts exploration, frontier allocation, and when to request new tactics according to the remaining budget. Methodologically, it is essentially a set of cost-aware modifications to AdaEvolve, which are simple but appear effective. Across eight math and program-optimization benchmarks with two LLM backbones (GLM-5 and GPT-5.4), CostAda achieves the best final quality in all 16 settings, and in 13 of them it matches the strongest baseline's full-budget result using at most half the budget.

Critical strengths

The cost-aware design is well motivated. The paper explicitly incorporates both the cost of each step and the remaining budget into search decisions, rather than treating the budget merely as a stopping criterion. The paper also provides a simple theoretical result demonstrating that cost-agnostic controllers can perform arbitrarily poorly in the worst case. Empirically, the proposed method consistently outperforms the baselines, achieving the best final solution quality across all 16 benchmark–backbone combinations and often matching the strongest baseline with only half the budget.

Critical weaknesses

None

Questions for authors

The paper is interesting, and I have two questions about the design choices that I believe could further strengthen the work. I would be interested to know whether the following extensions would be straightforward to implement or would introduce fundamental challenges.

  1. Anytime / incremental-budget setting. CostAda conditions its decisions on the remaining-budget ratio ρt=1−Ct/B\rho_t = 1-C_t/B, which requires the total budget BB to be specified before the search begins. Appendix G also suggests that the choice of BB can affect performance even at the same cumulative spend. In practice, however, budgets may be allocated incrementally. For example, one might initially spend 11, inspect the results, and then decide to allocate another 1010. Could CostAda support an anytime (or any-budget) variant that continues from its current state without restarting? In particular, would simply increasing BB mid-run, causing ρt\rho_t to jump from nearly 0 back to around 0.9, introduce any issues? Alternatively, could a doubling-trick-style schedule, as commonly used in online learning, be applied? I believe such an extension would substantially improve the method's practicality.

  2. Evaluation cost. The current budget accounts only for search-side LLM calls and excludes the cost of evaluating candidates. However, in many scientific discovery settings, candidate evaluation (e.g., long simulations or wet-lab experiments) can be significantly more expensive than generation or guidance, and its cost may vary across candidates. Appendix A mentions multi-resource budgeting as future work. Could the proposed cost-calibrated credit mechanism be naturally extended by incorporating evaluation costs into ctc_t, or would this require more substantial modifications to the controller, such as estimating evaluation costs before deciding whether to evaluate a candidate?

Comments on the paper

1 comment

Thank you for the additional experiments and clarifications. The new comparisons address several of my experimental concerns and make the results more convincing. I have raised my soundness score to 3, but will keep my overall rating unchanged, as I still have reservations about the methodological novelty.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.