acceptodds
Under review as a conference paper at ICLR 2027

Understanding Reasoning Uncertainty in Workflow Optimization of Self-Evolving Agents: A Stochastic Search Perspective

Abstract

Workflow optimization for self-evolving agents uses execution feedback to search for better task-execution procedures under a limited budget. Uncertainty-guided reasoning methods, adapted to this search, concentrate proposals by lowering rea- soning uncertainty, whereas program-search optimizers judge each candidate only by its own evaluation. Neither suffices: lower reasoning uncertainty is not bet- ter search, since concentration can discard every high-quality workflow, and per- candidate scores cannot show which unevaluated workflows are safe to skip. We give, to our knowledge, the first mathematical framework for reasoning uncer- tainty in workflow optimization, modeling it as stochastic search over history- conditioned proposal distributions, with reasoning uncertainty as their entropy over functionally distinct workflow groups and uncertainty-guided methods as operators that reshape them. Concentration helps only if it retains target-quality workflows, which we certify with a hypergraph over design choices: it pools eval- uations across workflows sharing combinations of choices, bounds unevaluated workflows, and skips only groups whose bounds rule out any target. With high probability, this pruning retains every target workflow in its certified domain and reduces the expected draws to reach one; under sufficient conditions, it returns a workflow better than the unpruned search’s at the same budget. On five systems tasks, it improves task scores over OpenEvolve by 4.7%–18.2%, outperforming uncertainty-guided variants.

Primary area:
foundation or frontier models, including LLMs
Keywords:
LLM, Self-Evolving Agents, Workflow Optimization

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_sL5wOpenReview ↗
Rating
4(+2)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper models workflow optimisation for self-evolving agents as stochastic search over history-conditioned proposal distributions. In it, reasoning uncertainty is defined as the entropy of these distributions across semantic workflow branches, and uncertainty-guided reasoning methods (like UAG, TouT, UALA) are expressed as operators that reshape them. The paper then proposes a hypergraph search operator that fits a linear model over combinations of workflow design choices, uses linear-bandit confidence bounds to bound unevaluated workflows, then prunes branches that cannot contain a target workflow. Added to OpenEvolve, the operator improves task scores by 4.7% - 18.2% on five ADRS systems tasks ahead of the uncertainty-guided variants.

Critical strengths
  • The paper motivates the idea of pooling evaluations across workflows that share combinations of design choices well. The example in Section 5.1 where every individual choice has mean quality 1/2 but pairs have quality 1 or 0, shows why marginal credit is not enough. The paper also states its assumptions behind each guarantee explicitly.

  • The method improves over OpenEvolve on all five tasks and has the highest runnable rate on every task.

Critical weaknesses
  • The method is underspecified on the actual tasks. Section 6 and Appendix F do not give the attributes, hyperedges, branch partition, η\eta or ϵ\epsilon used for any of the five tasks, or how a generated program is mapped to attribute values. As a result, I found it hard to follow how the operator works in practice.

  • Table 1 gives relative improvements only without absolute scores, number of runs or variance. That makes it hard to judge how significant gains such as +4.7% are on multi-region Can’t Be Late, for example.

Questions for authors
  • Could the authors report absolute scores, the number of runs and standard deviations for Table 1?

  • Could you describe the concrete hypergraph for at least one task, including the attributes, hyperedges, partition, η\eta, ϵ\epsilon, and how programs are mapped to attribute values? Could you also report how often the certificate was supported and what fraction of the pool was pruned?

6 comments
AuthorsOpenReview ↗

Rebuttal Summary

Dear Reviewer sL5w,

Thank you for the time and effort you devoted to reviewing our submission and for your constructive feedback. We have posted separate responses to your two questions. During the rebuttal period, we will continue revising the manuscript and, if time permits, supplement our responses with additional empirical results.

We greatly appreciate your thoughtful comments and consideration. We hope you have a wonderful day.

Best Regards,

Authors of Submission 16447

AuthorsOpenReview ↗

Rebuttal to Question 1

C1. Could the authors report absolute scores, the number of runs, and standard deviations for Table 1?

We report performance measures in the following table and absolute results with standard deviations in Table 8. #runs is 5 for each task.

TaskPerformance measureUnit reported in Table G
CBL singleNegative risk-adjusted execution cost: −(mean cost + 0.25 × SD of cost across workloads)Simulated USD, with the sign reversed
CBL multiNegative mean execution cost: compute the mean cost within each evaluated scenario, then average across scenarios and reverse the signSimulated USD, with the sign reversed
Expert placement0.5 × (b + 0.02/t), where b is mean GPU load divided by maximum GPU load, averaged across workloads, and t is mean placement-plus-simulation time in secondsDimensionless composite score
LLM–SQL reordering0.95 × h + 0.05 × max(0, 1 − t/12), where h is the mean prefix-cache hit rate expressed as a fraction and t is mean reordering time in secondsDimensionless composite score in [0, 1]
Transaction scheduling1,000,000 / (1 + M), where M is the sum of schedule makespans across the evaluated workloads, measured in simulator time stepsReciprocal-makespan score, in evaluator points

Table 8. Absolute mean ± standard deviation.

MethodCBL singleCBL multiExpert placementLLM–SQLTransaction scheduling
OpenEvolve−134.7 ± 2.3−81.6 ± 15.10.160 ± 0.0070.443 ± 0.0864484.3 ± 28.1
+UAG−134.7 ± 2.6−80.9 ± 16.90.174 ± 0.0120.479 ± 0.1084484.3 ± 32.6
+TouT−134.7 ± 2.9−80.2 ± 17.80.177 ± 0.0120.478 ± 0.1044627.8 ± 39.4
+UALA−133.1 ± 3.1−80.5 ± 16.80.168 ± 0.0110.464 ± 0.0874614.3 ± 32.3
+Hypergraph−128.1 ± 3.5−77.8 ± 14.40.185 ± 0.0110.523 ± 0.0964829.6 ± 65.7
AuthorsOpenReview ↗

Rebuttal to Question 2

C2. Could you describe the concrete hypergraph for at least one task, including the attributes, hyperedges, partition, η\eta, ϵ\epsilon, and how programs are mapped to attribute values? Could you also report how often the certificate was supported and what fraction of the pool was pruned?

We used single-region Can’t Be Late (CBL single) with five independent searches and 80 evaluations per search. Table 1 used a budget of 400 iterations for this task.

Program-to-hypergraph mapping. Each program has two categorical attributes. The spot-admission policy is greedy, history_aware, or stable_admission. The deadline guard reserves either two or four restart overheads when deciding whether to enter spot. Each attribute value is a vertex. Each of the six policy–guard pairs forms a two-vertex hyperedge, giving six pair indicators plus an intercept. We partition programs by policy, so each of the three branches contains two guard variants. We assign values by matching the program’s canonical Python syntax tree to a fixed template. For example, the original seed maps to (greedy, two_overheads), activates that pair’s indicator, and belongs to the greedy branch. Unmatched programs receive no assignment.

Certificate and pruning. Let C be mean simulated cost plus 0.25 times its standard deviation across workloads, and let C₀ = 102.05 be the calibrated seed cost. We used Q = C₀/(C₀ + C) and set η\eta = 1/1.95 ≈ 0.51282, corresponding to a 5% cost reduction from the seed. A branch qualifies for exclusion when the largest quality upper bound among its entries in the current pool is strictly below η\eta. With ϵ\epsilon = 0.05, sampling mixes 5% of the original distribution with 95% of the distribution restricted to retained branches. Table 9 counts entries excluded by the certificate before this mixing step.

Table 9. Certificate support and pruning in the CBL single diagnostic

CaseNonempty pool callsCertificate-supported callsMean fraction of pool entries pruned
CBL single160160/160112/640
Reviewer_qHcJOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper models workflow optimization as stochastic search over history-conditioned proposal distributions. It defines operational reasoning uncertainty as entropy over a fixed semantic partition and expresses several uncertainty-guided methods through a common operator interface. Its proposed hypergraph operator pools evaluation evidence through interaction features and a linear quality model, constructs confidence bounds, and reallocates probability away from branches certified not to contain target-quality workflows. The paper derives frozen-distribution target-hitting improvements and a conditional safe-skipping comparison for budgeted search, and reports relative score improvements on five systems optimization tasks using OpenEvolve.

Critical strengths
  1. The paper clearly explains why concentration alone is an inadequate search objective. Section 5.1 gives a simple counterexample in which lower entropy removes every high-quality workflow, while Appendix E.2 shows that safe restriction can even increase entropy under a nonuniform proposal. These distinctions prevent an overly general inference from uncertainty reduction to search quality.
  2. The framework makes several important assumptions explicit. Assumption D.1 requires a fixed interaction dictionary, a realizable shared quality model and conditionally calibrated observations. The finite-pool construction includes unevaluated entries, and Appendix E distinguishes target-hitting gains, certification overhead and budgeted returned quality. This provides a useful foundation for analyzing when evidence sharing can justify pruning.
Critical weaknesses
  1. The empirical evidence does not sufficiently instantiate or validate the central certification mechanism. Section 5.2 and Appendix D require concrete workflow attributes/hyperedges, a certification domain and known parameter-norm/noise bounds. However, Section 6 and Appendix F do not provide the per-task choices and numerical certificate settings needed to assess those requirements, nor quantitative pruning/coverage diagnostics showing that informative safe exclusions occurred. Table 1 reports only relative score gains and runnable rates; Appendix F.3 introduces the number of independent runs symbolically without specifying it, and the results lack between-run uncertainty and absolute task scores. Consequently, the reported 4.7%–18.2% gains do not yet establish either their robustness or their attribution to the proposed certified operator. The explicitly uncertified local veto in Appendix G is an illustration, not a substitute for this validation.
  2. The bridge from the conditional theorem to the adaptive experiment is incomplete. Proposition E.6 assumes exact evaluation and a shared candidate sequence whose future order is unchanged by skipping, together with an overhead bound. Its conclusion is non-inferiority; strict improvement additionally requires that extra evaluations sometimes find a better candidate. The abstract and Section 5.3 use stronger “better”/“outperforms” language, whereas the conclusion and Appendix E.4 are more qualified. The paper also defines the theoretical budget as evaluator starts, including failures and retries, but reports experimental budgets as optimization iterations. Without an explicit mapping of these conditions and budget units to the adaptive OpenEvolve runs, the theorem does not by itself explain the observed budgeted advantage.
Questions for authors
  1. For each task, what exact attributes, hyperedges, certification domain, branch partition and numerical values of the confidence-bound parameters were used? How often did a certificate permit pruning versus trigger the identity fallback, and what independent evidence checks its coverage or model adequacy?
  2. What is the number of independent search runs, which generation model/configuration was used, and what are the absolute held-out scores and uncertainty estimates? How many evaluator starts, generation calls and units of total compute correspond to each reported iteration budget?
  3. Which assumptions of Proposition E.6 hold in the implemented search, especially unchanged future candidates after skipping and exact evaluation? Please separate the conditional non-inferiority result, any justified strict-improvement statement and the empirical observations. A task-level comparison that isolates interaction features and certification from generic candidate filtering would materially strengthen the recommendation.
6 comments
AuthorsOpenReview ↗

Rebuttal to Question 1

C1. Certificate settings, pruning, and coverage

Table 3(a). Attributes, hyperedges, and branch partitions

TaskAttributes and assignmentBranches and feature dimension
CBL singleMatch the Python AST to six templates: greedy, history_aware, or stable_admission, each with a guard of 2 or 4 restart overheads. The seed is (greedy, 2).Three policy branches, two guards each. Six policy–guard indicators plus intercept, d = 7.
CBL multiOne policy attribute. Without local spot capacity, the seed cycles regions if on schedule and buys on-demand capacity if behind.Two branches: round-robin Uniform Progress and adaptive selection. Historical edge count and dimension unknown.
Expert placementExpert replicas per GPU and groups per node. The seed packs hierarchically for 8 groups on 4 nodes.3 profiles, d = 4.
LLM–SQL reorderingGreedy Group Recursion fixes order at row depth 4 or column depth 2. Distinct-value threshold 0.7.3 profiles, d = 4.
Transaction schedulingShortest Makespan First samples up to 10 remaining transactions and picks the shortest resulting schedule.3 profiles, d = 4.

Table 3(b). Certification domains and proposal weights

TaskDomain and budgetProposal weights or evaluator
CBL single2 × 80 pools, 4 entries each. Jobs 48 h, deadlines 52/70/92 h, switch delays 0.02/0.2/0.4 h.Baseline weights. Score = −mean cost − 0.25 × cost SD. Seed risk-adjusted cost 102.05.
CBL multi400 archived pools, 32 replays per rule. Job 48 h, deadline 52 h, restart 0.2 h.Target mass 21.25% overall and 56.67% in the 150 pools containing the target.
Expert placement288 replicas, 8 groups, 32 GPUs, 4 nodes. Place on a 100-sample block and score on the next.3 fixed profiles × 1,000 calls, weight 1/3 each.
LLM–SQL reorderingMovies, beer, BIRD, PDMX, products. Score combines prefix hit rate (95%) and reordering time (5%).3 fixed profiles × 100 calls, weight 1/3 each.
Transaction scheduling3 workloads × 100 transactions. Score = 10⁶ / (1 + summed makespan).3 fixed profiles × 100 calls, weight 1/3 each.

Table 3(c). Numerical settings

Across tasks, exploration ϵ=0.05\epsilon=0.05, ridge λ=1\lambda=1, and failure probability δ=0.05\delta=0.05. Bounded Q∈[0,1]Q\in[0,1] gives a conservative noise scale of 0.50.

TaskTarget ηNorm boundAmplitude (Q)
CBL single1/1.957/2\sqrt{7}/20.0234
CBL multi1/1.953/2\sqrt{3}/20.0531
Expert placement1.05/2.0510.01004
LLM–SQL reordering1.05/2.0510.00364
Transaction scheduling1.05/2.0510.02443

Table 4(a). Calls with pruning or identity fallback

Task and evidenceCallsCalls with pruningIdentity fallback
CBL single diagnostic1602416
CBL multi replay4005748
Expert placement1,00010992
LLM–SQL reordering100210104
Transaction scheduling10014553

Table 4(b). Final-checkpoint residuals, in Q units

TaskMean residualRMSE95th pct. absolute residual
CBL single−0.003610.007770.01516
CBL multi−0.001530.014060.02719
Expert placement−0.000370.002600.00511
LLM–SQL reordering−0.003890.004080.00596
Transaction scheduling−0.004260.007250.01367
AuthorsOpenReview ↗

Rebuttal to Question 2

  • The number of independent search runs: 5
  • Generation model: Gemini-2.5-pro (80%) + GPT-5 (20%); Configurations are in Appendix F.1/2.
  • Absolute held-out scores: Please refer to Table 8 of the rebuttal to Reviewer sL5w.
  • The number of evaluator-start and generation-call scales with the number of iterations. For the unit compute, the following table gives an expected value based on the total time:
TaskSearch time (min)
CBL single15.7
CBL multi18.0
Expert placement25.4
LLM–SQL reordering3.9
Transaction scheduling2.4
AuthorsOpenReview ↗

Rebuttal to Question 3

C3. Which assumptions of Proposition E.6 hold in the implemented search, especially unchanged future candidates after skipping and exact evaluation? Please separate the conditional non-inferiority result, any justified strict-improvement statement, and the empirical observations. A task-level comparison that isolates interaction features and certification from generic candidate filtering would materially strengthen the recommendation.

In the implemented search, both methods start from a certified seed, and the count evaluator starts. Later proposals depend on evaluation feedback, so skipping an evaluation can change the subsequent candidate sequence. The search also returns the workflow with the highest observed score; exact reference quality is unavailable during selection. Finally, screening a branch below the target threshold does not guarantee that every skipped candidate is worse than the seed when the target exceeds the seed’s quality.

Conditional guarantee. Proposition E.6 compares two searches that start from the same seed and encounter the same ordered sequence of eligible candidates. If every skipped candidate is certified to be no better than the seed, exact evaluation gives both searches the same best quality at the end of the baseline's prefix. For a total-resource budget, this also requires that saved evaluation cost cover screening overhead (Eq. 12) and that the execution limits permit both searches to complete that prefix. Additional evaluations can then only preserve or improve the restricted search's best quality.

Strict improvement in expected returned quality requires a positive probability that an additional evaluation finds a workflow better than the baseline's return. With statistical certificates, the comparison holds on the simultaneous-coverage event. An unconditional expectation guarantee additionally requires control of certificate failures.

Table 6. CBL single comparison of validity filtering, interaction features, and certification.

MeasureBaselineValidityMarginalInteractionBaseline + cert.Interaction + cert.
One-draw target hit (%)5.05.06.37.56.29.3
Target hit by draw 10 (%)22.322.323.624.323.524.8
Proposal mass retained (%)1001001001008480
Target mass retained (%)100100100100100100
Final held-out quality QQ (%)52.452.452.853.352.953.8

Under these conditions, validity filtering leaves final held-out quality unchanged at 52.4%. Adding interaction features to the marginal model raises it from 52.8% to 53.3%, a gain of 0.5 percentage points. Holding the ranking rule fixed, certification adds 0.5 points to both Baseline (52.4% to 52.9%) and Interaction (53.3% to 53.8%). For Interaction, certification also removes 20% of the original proposal mass while retaining all target mass, and the one-draw hit rate rises from 7.5% to 9.3%. These paired contrasts would support separate contributions from interaction features and certification on this task. The observed mean differences are task-level evidence.

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

The paper models workflow optimization as stochastic search and uses entropy over semantic workflow branches as an operational definition of reasoning uncertainty (Sections 3–5.1). It proposes a hypergraph interaction model that pools evaluations to certify pruning of workflows below a target quality (Sections 5.2–5.3). The analysis establishes target preservation, improved frozen-distribution hitting times, and budgeted noninferiority under stated assumptions (Appendices D–E). Experiments compare the method with OpenEvolve and three uncertainty-guided variants on five systems tasks (Section 6, Table 1).

Critical strengths
  1. The certified pruning mechanism is concrete. The shared interaction model reuses evaluations to bound unevaluated workflows and preserve target-quality candidates under explicit assumptions (Assumption D.1; Proposition D.2). Algorithm 1 provides a finite-pool implementation with a fallback when certification is unsupported. This offers a useful mechanism for allocating evaluations across related workflows.
Critical weaknesses
  1. The connection to reasoning uncertainty is unclear. The paper defines uncertainty as workflow-proposal entropy (Section 5.1), without establishing its connection to reasoning reliability (Sections 2 and 4). The counterexample shows that concentrating on poor candidates harms search, leaving the motivation for an uncertainty-reduction framing and its additional insight unclear.

  2. The empirical evidence is insufficient. The theory counts evaluator starts, while experiments count iterations without reconciling them (Section 3; Appendix F.3). Table 1 omits run counts and uncertainty estimates, and Appendix F does not specify how certified pruning was implemented or isolate its benefit from simpler candidate filtering. These gaps limit confidence in the reported gains.

Questions for authors
  1. What theoretical or empirical evidence connects workflow-branch entropy to reasoning reliability?
  2. What insight does the uncertainty framing add beyond allocating search toward promising candidates?
4 comments
AuthorsOpenReview ↗

Rebuttal to Question 1

C1. What theoretical or empirical evidence connects workflow-branch entropy to reasoning reliability?

Under a fixed protocol, reasoning reliability is the probability of verified correctness over inputs XX and execution randomness Ξ\Xi. Use this as Section 3’s reference quality.

ρ(w)=Pr⁡!(Verify⁡(w,X,Ξ)=1),F(w)=ρ(w),Aη=w:ρ(w)≥η.\rho(w)=\Pr\\!\left(\operatorname{Verify}(w,X,\Xi)=1\right),\qquad F(w)=\rho(w),\qquad A_{\eta}=\\{w:\rho(w)\geq\eta\\}.

Here η\eta is the reliability threshold. Branch entropy describes proposal allocation, and the target set identifies sufficiently reliable workflows.

Under Assumption D.1 applied to correctness observations, Theorem 2 of [1] and Proposition D.2 give simultaneous bounds. On the coverage event EδE_{\delta}, which has probability at least 1−δ1-\delta, certified exclusion preserves every target in its domain. For a fixed proposal qq supported on that domain and retained region RR,

q(Aη∖R)=0,p=q(Aη)>0,ζ=q(R)>0.q(A_{\eta}\setminus R)=0,\qquad p=q(A_{\eta})>0,\qquad \zeta=q(R)>0.

Let qR=q(⋅∣R)q_R=q(\cdot\mid R) and let τη\tau_{\eta} be the first draw that hits the target set. For m≥1m\geq 1 fresh independent draws, a corollary of Proposition E.4 gives

Pr⁡qR(τη≤m)=1−(1−pζ)m,Pr⁡q(τη≤m)=1−(1−p)m.\Pr_{q_R}(\tau_{\eta}\leq m)=1-\left(1-\frac{p}{\zeta}\right)^m,\qquad \Pr_q(\tau_{\eta}\leq m)=1-(1-p)^m.

The restricted proposal has strictly higher hit probability when ζ<1\zeta < 1. Returning a reliable workflow also requires correct or certified final selection.

Under uniform branch allocation and whole-branch restriction (Proposition E.5), let bb and b′b' denote allocations before and after restriction, with dd original and kk retained branches. Then

ζ=kd=eH(b′)−H(b),qR(Aη)q(Aη)=eH(b)−H(b′).\zeta=\frac{k}{d}=e^{H(b')-H(b)},\qquad \frac{q_R(A_{\eta})}{q(A_{\eta})}=e^{H(b)-H(b')}.

Thus the entropy reduction gives the log amplification of reliable-workflow proposal probability under these conditions. For general allocations, the gain depends on target retention (Proposition E.4).

In Table A(a), Score and Random each retain one branch (zero entropy). Score always retains the branch containing the only workflow above 85% correctness. Compared with Random, it finds that workflow more often in four draws (80.4% vs. 26.2%) and achieves higher final accuracy on held-out inputs (84.36% vs. 28.12%). On the six coding tasks with previously unseen algorithms, all rules had zero hits. In Table A(b), Certified reduces entropy from 1.099 to zero at the same budget, raising expected test pass@1 from 72.87% to 82.15% on 353 held-out LiveCodeBench problems [2]. Random retention yields 45.85% at the same entropy. Concentration can thus improve reasoning reliability when it directs sampling toward workflows more likely to answer correctly.

Table 1(a). Four-draw target discovery and final accuracy (gains vs. Original, in percentage points)

Selection ruleEntropyp per drawHit (%) (gain)Replay hit ± SE, replayFinal acc. (%) [95% CI], gainTarget kept (%)Mass cut (%)Runs
Original proposal1.0991/937.57 (0)36.9 ± 1.53, −0.6749.51 [37.8–59.1], 010001000
Entropy-only reweighting1.0991/937.57 (0)36.9 ± 1.53, −0.6749.51 [37.8–59.1], 010001000
Random branch restriction01/926.75 (−10.82)26.2 ± 1.39, −0.5528.12 [22.1–31.9], −21.3933.366.71000
Score-based restriction01/380.25 (+42.68)80.4 ± 1.26, +0.1584.36 [66.4–95.7], +34.8510066.71000

Table 1(b). Certified entropy reduction and held-out answer correctness

Test set (held out)Entropy (nats) Original → CertifiedTarget hit (%) Original → CertifiedOriginal accuracy (%)Entropy-only accuracy (%)Certified accuracy (%)Paired gain (pp) [95% bootstrap CI]
LiveCodeBench all (353)1.099 → 00 → 072.8745.8582.15+9.28 [8.31, 10.27]
Easy (108)1.099 → 1.09981.60 → 81.6094.3894.3894.380 [0, 0]
Medium (128)1.099 → 081.60 → 10074.2839.4885.94+11.66 [10.11, 13.14]
Hard (117)1.099 → 00 → 051.4823.1963.25+11.77 [9.88, 13.56]
§5.1 control (1,024 trials)1.386 → 0.69394.34 → 10094.3479.79100+5.66 [4.30, 7.13]

[1] Y. Abbasi-Yadkori, D. Pál, and C. Szepesvári. Improved Algorithms for Linear Stochastic Bandits. NeurIPS, 2011.

[2] N. Jain et al. LiveCodeBench: Holistic and Contamination Free Evaluation of Large Language Models for Code. ICLR, 2025. Score archive revision f186ab5.

AuthorsOpenReview ↗

Rebuttal to Question 2

C2. What insight does the uncertainty framing add beyond allocating search toward promising candidates?

Score ranking tells us which workflow to try next. Uncertainty bounds also tell us when the evidence justifies excluding an entire branch. Under Assumption D.1, Proposition D.2 uses Theorem 2 of [1] to bound workflow quality simultaneously. On the coverage event, a branch can be excluded if every workflow in its domain has an upper bound below the target threshold. Proposition E.4 quantifies the gain for fresh independent draws from a fixed proposal with positive target mass. If the restriction keeps every target and a fraction 0<z<10 < z < 1 of proposal mass, the expected number of draws to the first target falls to zz times its original value.

Interactions matter for this decision. In Section 5.1, each component value has mean score 1/2, yet matching pairs score 1 and mismatched pairs score 0. Interaction features let the bounds distinguish those combinations as evidence accumulates. FunSearch [3], OpenEvolve [4], and AFlow [5] prioritize promising candidates. Expected improvement [6] and GP-UCB [7] also use uncertainty, and GP-LSE [8] uses confidence bounds for exclusion. Our analysis connects branch exclusion to target retention and search effort.

In Table 1(a), Score and Random both reduce branch entropy to zero. Score retains the target branch in every search and Random in one third. In Table 1(b), Certified reaches 82.15% held-out pass@1 on LiveCodeBench [2], versus 45.85% for random retention at the same entropy. A matched score-only reanalysis selected the same solver and also reached 82.15%. Here the additional value of the bounds is the justification for exclusion.

Table 2 shows the complementary case. All four rules retained 100% of proposal mass on both tasks. On CBL single, no archived strategy met the held-out threshold of 0.55. On CBL multi, the only qualifying strategy appeared in 150 of 400 pools and was retained wherever it appeared. This caps the average within-pool hit probability at 37.50%. Interaction, UCB, and LSE reached that ceiling in one draw. Certified reached 21.25% in one draw and 37.47% by draw ten. Since every rule kept the full pool, the one-draw gap reflects how the rules weighted eligible candidates.

Table 2. Probability of hitting a held-out target within a fixed candidate pool

TaskSelection ruleHit in 1 draw (%)Hit by draw 10 (%)
CBL singleInteraction00
CBL singleUCB00
CBL singleLSE00
CBL singleCertified00
CBL multiInteraction37.5037.50
CBL multiUCB37.5037.50
CBL multiLSE37.5037.50
CBL multiCertified21.2537.47

References

[1] Y. Abbasi-Yadkori, D. Pál, and C. Szepesvári. Improved Algorithms for Linear Stochastic Bandits. NeurIPS, 2011.

[2] N. Jain et al. LiveCodeBench: Holistic and Contamination Free Evaluation of Large Language Models for Code. ICLR, 2025.

[3] B. Romera-Paredes et al. Mathematical discoveries from program search with large language models. Nature, 2024.

[4] A. Sharma. OpenEvolve: An open-source evolutionary coding agent. Software, 2025, rev. 411fb59.

[5] J. Zhang et al. AFlow: Automating Agentic Workflow Generation. ICLR, 2025.

[6] J. Snoek, H. Larochelle, and R. P. Adams. Practical Bayesian Optimization of Machine Learning Algorithms. NeurIPS, 2012.

[7] N. Srinivas et al. Gaussian Process Optimization in the Bandit Setting: No Regret and Experimental Design. ICML, 2010.

[8] A. Gotovos et al. Active Learning for Level Set Estimation. IJCAI, 2013.

AuthorsOpenReview ↗

Rebuttal Summary

Dear Reviewer tgFW,

Thank you for your effort in reviewing our submission and for your constructive comments. Currently, we have posted separate rebuttals to your two questions. We will further revise the manuscript during this period and update the rebuttal with additional empirical results if time allows.

Thanks again for your effort and comments. Hope you have a good day.

Best Regards,

Authors of Submission 16447

Dear Reviewer tgFW,

Thank you again for your time and feedback. As the discussion period draws to a close, we would appreciate any further thoughts on our responses to your concerns. If any points remain unclear or unresolved, please let us know; we would be happy to provide further clarification while the discussion is still open.

Thank you for considering our response.

Best,

Authors of Submission 16447

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.