- Rating
- 3(+1)
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This paper studies how truthful auxiliary diagnostic feedback affects LLM agents in algorithm discovery. On 15 tasks from Frontier-CS and Frontier-Eng, auxiliary feedback improves the best score on 5 tasks and lowers it on 8 tasks. By analyzing trajectories on the data-center control task, the authors propose an "exploration cost" mechanism: feedback makes the agent focus on tuning existing rules and do less structural exploration. A Bayesian optimization experiment with auxiliary guidance reproduces this mechanism: moderate guidance helps, too strong guidance gets stuck in a worse region, and stopping the guidance can recover the search. Finally, the authors show "renewed exploration" runs, which remove the feedback after progress stops, and these runs beat the strongest baseline on 4 tasks.
Critical strengths
- The problem is important and it challenges a common assumption. Current agentic discovery systems usually assume that more information from the evaluator is always better. This paper clearly raises and tests the idea that truthful feedback can also hurt, which is directly useful for designing such systems.
- The paper is very transparent and easy to check. The appendix gives run-level results, how the metrics are computed, and code. Because of this, reviewers can re-aggregate the data and check if the conclusions are robust.
Critical weaknesses
- The cross-task evidence is statistically weak. Most tasks only have 3 runs per condition and the results are aggregated by the maximum, and many differences are smaller than the variation between runs in the same condition. OgreSort, Mobile Relay, Max-3-SAT and Temporal smooth control almost cannot tell the two conditions apart. If we use the mean instead, the direction becomes opposite for Beacon String, Defensive Lineup and the DeepSeek data-center experiment. Also, many Frontier-CS diagnostics are almost not related to the objective, so their effect may come from distraction, not from "over-exploiting useful feedback" as the paper claims. So the "5 higher / 8 lower" result is hard to support the main framing of the paper.
- "Renewed exploration" has no control and some key details are missing, but it is presented very prominently. The paper says the feedback is removed when refinements give limited gains, but it does not define this criterion clearly or report at which submission the feedback was actually removed in each run. It also does not say how many times this was tried, or why only 4 of the 8 hurt tasks are reported. Without a paired control from the same switching point, the improvement cannot be attributed to removing the feedback. Some of the gains (Max-Cut +58, Cascading +40) are also smaller than the variation between runs. The emphasis on this part in the abstract and Appendix G is more than what the evidence can support.
Questions for authors
- Can you start from the same switching point and run several paired continuations, with feedback kept and with feedback removed? This is the most direct way to test whether removing feedback causes the recovery.
- Each task only uses one set of auxiliary diagnostics. How were these diagnostics chosen? How much do the paper's conclusions depend on this choice?
- In the renewed exploration trajectories, at which submission was the auxiliary feedback removed? Was this time decided by a predefined rule, or by the researchers after looking at the trajectory?
7 comments
1.2 Paper framing, run counts and run-to-run variation
We agree with the reviewer that the “5 higher / 8 lower” count should not carry the framing on its own, and we will revise the paper to make this clearer. Our intended claim is that feedback is not a free lunch, even when it is truthful and verifiable: it can lower the best solution an agent discovers, and our analyses suggest that it does so by concentrating search. We see this as an existence claim; we do not mean to suggest that feedback hurts on average or on most tasks. This heterogeneity holds across aggregation rules: feedback lowers performance on 6 of 15 tasks by mean and on 8 by best-found score.
Small differences at the frontier are meaningful, and run-to-run spread does not measure them. Progress becomes harder as scores rise: improvements grow rarer and smaller, and even a modest gain over a strong solution can require a hard breakthrough [1, 2, 3, 6] (Section 3). AlphaEvolve [5, Appendix B], for example, improved the best-known bound for Erdős’ minimum overlap problem from 0.380927 to 0.380924, and raised 26-circle packing from about 2.634 to 2.6359. Run-to-run spread instead reflects weak runs: in the original Beacon String runs, one baseline run at 35,840.71 accounts for most of the 4,071.79 spread, while the 968.57 gap lies between the best runs. > We already count OgreSort and Mobile Relay Layout as ties. Even if Max-3-SAT and Temporal smooth control were also treated as ties, the results would be 4 higher / 7 lower / 4 equal, and the heterogeneity remains.
References
[1] Yuksekgonul et al. Learning to discover at test time (TTT-Discover). arXiv:2601.16175, 2026.
[2] Chi et al. Frontier-Eng. arXiv:2604.12290, 2026.
[3] Yan et al. PACEvolve. arXiv:2601.10657, 2026.
[4] Romera-Paredes et al. FunSearch. Nature, 2024.
[5] Novikov et al. AlphaEvolve. arXiv:2506.13131, 2025.
[6] Lange et al. ShinkaEvolve. arXiv:2509.19349, 2025.
[7] Mang et al. FrontierCS. arXiv:2512.15699, 2025.
1.3 Effect may come from distraction, not from "over-exploiting useful feedback"
We thank the reviewer for raising this point. We address it from three angles:
Our study concerns truthful feedback, not feedback selected for alignment. Real evaluators report many behavioral statistics, some closely tied to the objective and some not. We deliberately did not filter diagnostics by their predictive value. We respectully refer the reviewer to our response to Question 2 for further clarification.
Most Frontier-CS diagnostics are related to the objective For each diagnostic, we computed the Spearman correlation with the official score over all valid candidates in our study. Of the 150 diagnostics with a defined correlation, 64 (43%) are strongly aligned (|ρ| > 0.5), and every task has at least three such diagnostics. A further 30 are moderately aligned so 94 (63%) reach |ρ| > 0.3.
| Task | |ρ| > 0.5 | |ρ| > 0.3 |
|---|---|---|
| Polyomino Packing | 6 / 16 | 11 / 16 |
| OgreSort | 12 / 16 | 14 / 16 |
| Rectangle-Free Points | 8 / 16 | 11 / 16 |
| Graph 3-Coloring | 4 / 14 | 8 / 14 |
| Max-3-SAT | 7 / 16 | 9 / 16 |
| Max-Cut | 7 / 16 | 10 / 16 |
| Beacon String | 3 / 10 | 4 / 10 |
| Cascading Flip Schedule | 5 / 16 | 10 / 16 |
| Mobile Relay Layout | 5 / 14 | 8 / 14 |
| Defensive Lineup | 7 / 16 | 9 / 16 |
We acknowledge that some diagnostics relate to the objective less directly than others. What matters for our account is that every panel also contains strongly related diagnostics that agents can act on. Agents can also tell what each diagnostic measures: the task statement given to the agent defines every diagnostic and how it is computed. The placebo control study below answers whether feedback then hurts through distraction or through over-exploitation.
A placebo control isolates the effect of feedback content from additional reading load. Placebo panels match auxiliary feedback in length, format, and statistical structure, including fractions, summary statistics, and extrema. However, their values are generated from a fixed random seed before the experiment, independently of the algorithm's code. Thus, placebo feedback introduces similar reading overhead without providing candidate-specific information. We evaluate five tasks using GPT-5.6 Sol, with 100 submissions and three runs per condition, reporting the best run.
| Task | Score-only | Truthful aux. | Placebo |
|---|---|---|---|
| Data Center | 32.7106 | 32.0897 | 32.6664 |
| MaxCut | 87,485.05 | 87,284.06 | 87,342.21 |
| Beacon String | 39,191.55 | 39,038.48 | 39,183.05 |
| Defensive Lineup | 60,083.03 | 59,901.62 | 60,029.46 |
| Cascading Flip | 77,364.10 | 76,003.72 | 76,721.47 |
Truthful auxiliary feedback yields the lowest best-run score on all five tasks, while placebo feedback consistently falls between score-only and truthful feedback. This pattern suggests that the performance decline is not solely attributable to additional reading load; the information conveyed by truthful feedback also plays a role. Together with our trace analysis below, these findings are consistent with over-exploitation as a potential mechanism.
Trace audit: feedback-induced improvements followed by repeated low-yield refinement. We examined the highest-scoring auxiliary run for each task where feedback reduced the best-found score. In six of the seven runs, a feedback-guided modification first improved the best-so-far score, after which the agent repeatedly refined the same code component. We tracked these revisions over the next 20 submissions.
| Task | Reported diagnostics | Record-improving modification | Same-component revisions / 20 | Further improvement / valid revisions |
|---|---|---|---|---|
| Max-Cut | Transition rates; partition-size imbalance | Structure-aware candidate selection | 7 | 0/6 |
| Defensive Lineup | Identity position fraction; normalized displacement | Risk-aware matching coverage | 7 | 0/7 |
| Topology optimization | Gray fraction; near-binary fraction | Density-filter and update-schedule tuning | 8 | 0/8 |
| Cascading Flip Schedule | Displacement; index jump; ascending adjacency | Frontier tie-breaking policy | 11 | 1/10 |
| Beacon String | Alternating-triple fraction | Euler traversal ordering | 4 | 0/3 |
| JobShop SWV | Machine idle time; maximum utilization | Remaining-work priority parameterization | 17 | 0/15 |
Across these six tasks, repeated same-component revisions rarely produced further improvements (1 out of 49 valid revisions). This pattern suggests that feedback may help identify promising directions initially, but can also encourage prolonged refinement with diminishing returns.
Response to Reviewer au7q - Weakness 1
We thank the reviewer for the thoughtful review. We are glad the reviewer finds the problem important and agrees that more evaluator information is not always better. We also appreciate that the reviewer re-aggregated our data using the released run-level results. Below, we address each point in turn.
Weakness 1: Statistical strength of the cross-task evidence
1.1 Maximum aggregation, and the sign flips under the mean
Best-found score is the standard metric for algorithm discovery. The goal of discovery is to advance the best-known solution, and the field evaluates methods on that basis. Representative systems such as FunSearch [4], AlphaEvolve [5], and TTT-Discover [1] are assessed by the best solutions they find. Both benchmarks used in our study also adopt best-found evaluation: FrontierCS [7, §4.2] reports Score@k (the maximum score over k trials) alongside Avg@k, and Frontier-Eng [2, §2.4] ranks methods by the best feasible score obtained within a fixed interaction budget. Our evaluation follows this convention.
Mean score can misrepresent discovery performance. The mean shows how a typical run performs. In discovery, however, every run consumes search budget, and only the best verified solution is kept and used. A method that lifts weak runs but lowers the best achievable score can therefore raise the mean while producing a worse discovery outcome. This is exactly the pattern behind the sign flips we observe. We therefore use best-found score under matched total search budgets as our primary metric.
All three flips in original runs share one pattern: feedback lifts the worst run and lowers the best. No task flips the other way.
Auxiliary minus baseline.
On all three tasks, excluding the single worst run in each condition reverses the mean advantage.
The mean advantage vanishes after more runs count. The expected best score over k runs links the two metrics: k = 1 gives the mean, and k = all runs gives our reported score. To strengthen the robustness of our findings, we conduct five additional independent runs for Beacon String, Defensive Lineup, and Data-center Control (GPT-5.6 Sol).
Auxiliary minus baseline; expected best over k runs drawn without replacement.
Auxiliary feedback generally becomes less competitive as the run budget increases: it falls behind on Beacon String and Defensive Lineup, and the gap widens on data-center control. Feedback can improve the typical run while worsening the best one, and this is exactly the exploration cost we describe.
Three runs per condition already reveal the effect on the tasks we extended. On Beacon String, Defensive Lineup, and data-center control with GPT-5.6 Sol, the expected best-of-3 gap already has the same sign as the best-of-8 gap, and on the latter two it is close to its eight-run value (−64.81 vs. −62.71; −0.4648 vs. −0.5079). Only 2 of the 30 additional runs surpass the best score from the original three runs under the same condition, and neither changes the ordering: score-only remains higher on all three tasks. Feedback can improve the typical run while worsening the best one, and this is exactly the exploration cost we describe.