- 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, or 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, , , 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
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.
| Task | Performance measure | Unit reported in Table G |
|---|---|---|
| CBL single | Negative risk-adjusted execution cost: −(mean cost + 0.25 × SD of cost across workloads) | Simulated USD, with the sign reversed |
| CBL multi | Negative mean execution cost: compute the mean cost within each evaluated scenario, then average across scenarios and reverse the sign | Simulated USD, with the sign reversed |
| Expert placement | 0.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 seconds | Dimensionless composite score |
| LLM–SQL reordering | 0.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 seconds | Dimensionless composite score in [0, 1] |
| Transaction scheduling | 1,000,000 / (1 + M), where M is the sum of schedule makespans across the evaluated workloads, measured in simulator time steps | Reciprocal-makespan score, in evaluator points |
Table 8. Absolute mean ± standard deviation.
| Method | CBL single | CBL multi | Expert placement | LLM–SQL | Transaction scheduling |
|---|---|---|---|---|---|
| OpenEvolve | −134.7 ± 2.3 | −81.6 ± 15.1 | 0.160 ± 0.007 | 0.443 ± 0.086 | 4484.3 ± 28.1 |
| +UAG | −134.7 ± 2.6 | −80.9 ± 16.9 | 0.174 ± 0.012 | 0.479 ± 0.108 | 4484.3 ± 32.6 |
| +TouT | −134.7 ± 2.9 | −80.2 ± 17.8 | 0.177 ± 0.012 | 0.478 ± 0.104 | 4627.8 ± 39.4 |
| +UALA | −133.1 ± 3.1 | −80.5 ± 16.8 | 0.168 ± 0.011 | 0.464 ± 0.087 | 4614.3 ± 32.3 |
| +Hypergraph | −128.1 ± 3.5 | −77.8 ± 14.4 | 0.185 ± 0.011 | 0.523 ± 0.096 | 4829.6 ± 65.7 |
Rebuttal to Question 2
C2. Could you describe the concrete hypergraph for at least one task, including the attributes, hyperedges, partition, , , 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 = 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 . With = 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
| Case | Nonempty pool calls | Certificate-supported calls | Mean fraction of pool entries pruned |
|---|---|---|---|
| CBL single | 160 | 160/160 | 112/640 |
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