acceptodds
Under review as a conference paper at ICLR 2027

Feedback Is Not a Free Lunch: The Exploration Cost of Auxiliary Information in Agentic Algorithm Discovery

Abstract

LLM agents discover algorithms by writing programs, testing them, and revising them based on the results. A test gives a score and can also report truthful details about a program’s behavior. We call these extra details auxiliary feedback. They may suggest useful changes, but we find that even truthful feedback is not a free lunch. In a matched study of 15 algorithmic and engineering tasks, adding auxiliary feedback raises the best score found across repeated runs on five tasks, lowers it on eight, and leaves two unchanged. To understand these results, we examine the programs agents try in a data-center control task. For each of five models, the best run with sustained auxiliary feedback earns a lower score and tries fewer new ways of using information to choose control actions than the best run without the extra feedback. We call this the exploration cost of feedback. Diagnostics can help an agent improve a promising idea, but repeatedly following them can leave fewer opportunities to try other ideas. We bridge agentic discovery with auxiliary-guided Bayesian optimization, isolating how guidance strength turns useful feedback into restricted exploration. The signal helps when its influence is moderate, but causes search to miss a better region when its influence is too strong. Removing strong guidance later restores exploration. In four tasks where sustained auxiliary feedback lowered the best score, renewed-exploration runs find solutions exceeding the strongest baseline references. Together, these results suggest that feedback should help agents improve promising ideas while leaving room to explore alternatives.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Agentic Agorithm Discovery, Failure Case Analysis, Exploration–exploitation trade-off, Bayesian 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_au7qOpenReview ↗
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
  1. 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.
  2. 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
  1. 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.
  2. "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
  1. 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.
  2. 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?
  3. 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
AuthorsOpenReview ↗

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.

TaskWorst runBest run
Beacon String+2,504.63−968.57
Defensive Lineup+34.52−62.71
Data-center control (DeepSeek V4 Pro)+2.6187−1.3106

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).

TaskMeanExpected Best-of-3Expected Best-of-5Expected Best-of-8
Beacon String+318.56−474.16−682.84−874.02
Defensive Lineup+296.97−64.81−65.96−62.71
Data-center control (DeepSeek)+0.1919+0.1700−0.2811−1.3106
Data-center control (GPT-5.6 Sol)−0.1748−0.4648−0.5129−0.5079

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.

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 Packing6 / 1611 / 16
OgreSort12 / 1614 / 16
Rectangle-Free Points8 / 1611 / 16
Graph 3-Coloring4 / 148 / 14
Max-3-SAT7 / 169 / 16
Max-Cut7 / 1610 / 16
Beacon String3 / 104 / 10
Cascading Flip Schedule5 / 1610 / 16
Mobile Relay Layout5 / 148 / 14
Defensive Lineup7 / 169 / 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.

TaskScore-onlyTruthful aux.Placebo
Data Center32.710632.089732.6664
MaxCut87,485.0587,284.0687,342.21
Beacon String39,191.5539,038.4839,183.05
Defensive Lineup60,083.0359,901.6260,029.46
Cascading Flip77,364.1076,003.7276,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.

TaskReported diagnosticsRecord-improving modificationSame-component revisions / 20Further improvement / valid revisions
Max-CutTransition rates; partition-size imbalanceStructure-aware candidate selection70/6
Defensive LineupIdentity position fraction; normalized displacementRisk-aware matching coverage70/7
Topology optimizationGray fraction; near-binary fractionDensity-filter and update-schedule tuning80/8
Cascading Flip ScheduleDisplacement; index jump; ascending adjacencyFrontier tie-breaking policy111/10
Beacon StringAlternating-triple fractionEuler traversal ordering40/3
JobShop SWVMachine idle time; maximum utilizationRemaining-work priority parameterization170/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.

Reviewer_j8RYOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2(+1)
Read review
Paper summary

The paper studies what happens when an LLM coding agent doing algorithm discovery receives extra diagnostic information from the evaluator in addition to the score. The comparison covers 15 tasks from Frontier-CS and Frontier-Eng and uses the best score across a few runs with and without the diagnostics. On that basis, the extra feedback helps on 5 tasks and hurts on 8.

The authors then look at the programs agents write in the data-center control task. With diagnostics, agents spend more submissions tuning carbon-intensity thresholds and add fewer new dependencies between inputs and actions. The authors call this the "exploration cost" of feedback.

A 2D Bayesian optimization toy reproduces the pattern. There, the auxiliary signal is mixed into EI with a weight λ: moderate weights help, large weights trap the search in a broad but worse basin, and switching back to plain EI recovers. Finally, turning the diagnostics off partway through a run beats the best baseline on four tasks.

Critical strengths

The question itself is the main strength. Adding more evaluator diagnostics is close to a default in AlphaEvolve/OpenEvolve-style loops. The paper makes a reasonable case that this is not automatically beneficial when the goal is the best solution found within a budget rather than per-step improvement. I think the community would benefit from a clear answer.

The trace analysis on data-center control is also done carefully. It uses AST-based detection of threshold-only edits and static tracing of which inputs feed which actions. Others could reuse this instrumentation, and releasing the traces helps.

Critical weaknesses
  1. The headline result depends on how runs are summarized. The "5 higher / 8 lower / 2 equal" count uses the maximum over 3 runs (Frontier-CS) or 5–8 runs (Frontier-Eng). Many of the differences are tiny compared with the spread between runs:

    • Max-3-SAT is 98,946.608 vs. 98,946.432.
    • Cascading Flip differs by about 64, while the three baseline runs alone range from ~74.6k to ~77.4k.

    I went through the run-level results (Tables 5, 7, 8) and compared means instead. By my count, it comes out roughly 8 higher / 6 lower. Beacon String, Defensive Lineup and the DeepSeek data-center runs all flip sign.

    The data-center case matters most, because the mechanism analysis is built on it. With 8 runs per condition, the averages are essentially the same (≈22.3 vs. ≈22.5), and the two worst runs (9.8 and 9.6) are both in the baseline.

    I understand why best-found score is the natural objective for discovery. But estimating a maximum from three runs of a very noisy process cannot separate the two conditions. As it stands, I read the evidence as:

    • clear gains on a couple of tasks (UAV inspection, polyomino packing);
    • a clear drop on Gemini data-center and a small but consistent drop on topology optimization;
    • no detectable difference on most of the rest.

    That is a much weaker statement than the abstract makes.

  2. I am not convinced the proposed mechanism is the right one. The diagnostics are designed per task by the authors, and some have little to do with the objective, e.g., "adjacent name-length transitions" for Defensive Lineup and "true-index centroid" for Max-3-SAT.

    More importantly, in the Appendix D traces the agents seem to start optimizing the diagnostics themselves:

    • In topology optimization, the agent tries to remove checkerboarding and islands and ends up damaging the load-bearing structure.
    • In Cascading Flip, it works to preserve a "favored structural statistic" after score gains have stopped.
    • In JobShop, the reported idle time drives further priority-weight tweaks.

    To me, this looks more like the agent treating the displayed statistics as secondary targets than like a budget-limited exploration/exploitation trade-off. The two explanations predict different things:

    • whether the harm shrinks with a larger budget;
    • whether a diagnostic that is well aligned with the score still narrows the search.

    The BO toy does not separate them either. Its auxiliary signal is constructed to weight the worse basin as much as the better one, so it is misaligned by design. And the benefit of decaying the guidance is essentially what πBO (which the paper cites) already motivates.

    The correlation in Fig. 1(b) is also partly built in. A threshold-only edit can never add a new action–information pair, so within 100 submissions, more refinements mechanically leave room for fewer new pairs.

Questions for authors
  1. How many runs are behind each entry of Table 1(b)? Could you report means or medians, or a bootstrapped expected best-of-k, alongside the maximum for all 15 tasks? If most tasks turn out to be indistinguishable, I think the framing of the paper needs to change, and this would affect my score the most.

  2. On the tasks where feedback helped (polyomino, UAV), do you see the same shift toward threshold refinement and fewer new dependencies?

    • If yes, the mechanism does not explain why feedback helps on some tasks and hurts on others.
    • If no, what distinguishes those diagnostics?
13 comments
AuthorsOpenReview ↗

Response to Reviewer j8RY - Weakness 1

We thank the reviewer for recognizing the importance of our research question and the care and reusability of our data-center trace analysis. We address the reviewer's concerns point by point below.

Weakness 1: Statistical strength and interpretation of the cross-task results

1.1 Sensitivity to maximum versus mean aggregation

Best-found score measures the discovery objective, while the mean measures the performance of a typical run. We appreciate the reviewer’s re-aggregation of the released results and agree that these summaries can yield different orderings. In algorithm discovery, the objective is to obtain the best verified solution within a search budget: all runs consume budget, but only the best solution is retained. Representative systems such as FunSearch [1], AlphaEvolve [2], and TTT-Discover [3] emphasize the best solutions discovered. The benchmarks we use also report best-found performance: FrontierCS [4, §4.2] reports Score@k, and Frontier-Eng [5, §2.4] ranks methods by the best feasible score within a fixed interaction budget. Our primary metric follows this objective, with matched total search budgets between conditions.

The three sign flips identified by the reviewer share a consistent pattern: auxiliary feedback improves the worst observed run but lowers the best observed run. Thus, a higher mean and a lower best-found score can coexist without contradiction.

TaskChange in worst-run scoreChange in best-run score
Beacon String+2,504.63−968.57
Defensive Lineup+34.52−62.71
Data-center control (DeepSeek V4 Pro)+2.6187−1.3106

Auxiliary feedback minus score-only baseline; differences compare the respective minima and maxima, not paired runs.

These results explain why mean aggregation changes the headline count. They also motivate reporting both summaries: the mean describes typical-run performance, whereas best-found score describes the outcome of spending the full discovery budget.

The reviewer’s observation that the two lowest-scoring data-center runs both belong to the baseline is consistent with this pattern: these low-scoring runs pull down the baseline mean, even though the baseline finds the better solution. The nearly equal averages therefore do not capture the difference in best-found discovery performance. Auxiliary feedback improves the worst observed run while lowering the best, illustrating how gains at the lower end can offset a loss at the discovery frontier when results are averaged.

1.2 Reliability with few runs and small score differences

To further examine the three tasks for which the reviewer identified mean-based sign flips, we added five independent runs per condition for Beacon String and Defensive Lineup, and five per condition for data-center control with GPT-5.6 Sol.** The reviewer’s data-center sign flip concerns DeepSeek; the additional GPT-5.6 Sol runs provide a complementary check on the same task. To connect mean and maximum aggregation, we compute the expected best score from a uniformly sampled subset of k observed runs, drawn without replacement. At k = 1, this is the empirical mean; at k = 8, it is the observed maximum over all eight runs. The DeepSeek results below use the existing eight runs per condition.

TaskMean (k = 1)Expected best-of-3Expected best-of-5Best-of-8
Beacon String+318.56−474.16−682.84−874.02
Defensive Lineup+296.97−64.81−65.96−62.71
Data-center control (DeepSeek)+0.1919+0.1700−0.2811−1.3106
Data-center control (GPT-5.6 Sol)−0.1748−0.4648−0.5129−0.5079

Auxiliary feedback minus score-only baseline

The best-found ordering persists after extending the three evaluated settings to eight runs per condition. Only 2 of the 30 additional runs exceed the original three-run best under their respective condition, and neither changes the ordering: score-only remains higher in all three settings. For Beacon String and Defensive Lineup, auxiliary feedback retains a higher mean but falls behind when multiple runs are available. For GPT-5.6 Sol data-center control, the expected best-of-3 gap is already close to the best-of-8 gap.

Small score gains can require substantial search effort. AlphaEvolve [2, Appendix B], for example, improved Erdős’ minimum overlap bound from 0.380927 to 0.380924 and 26-circle packing from about 2.634 to 2.6359. To examine the effort behind our observed gaps, the table traces each winning run from the earlier valid submission closest to the other condition’s best score through its first attainment of the winning score. It reports the score gain and subsequent submissions, including failed evaluations, with a median of 89 submissions across 13 non-tied tasks.

TaskHigher-scoring conditionScore gainSubsequent submissions
Frontier-CS
Polyomino PackingAuxiliary feedback+2,123.351139
Rectangle-Free PointsAuxiliary feedback+319.579228
Graph 3-ColoringAuxiliary feedback+221.347157
Max-3-SATBaseline+0.71665
Max-CutBaseline+191.777238
Beacon StringBaseline+1,018.222127
Cascading Flip ScheduleBaseline+63.638405
Defensive LineupBaseline+60.67374
Frontier-Eng
Data-center controlBaseline+1.214143
Temporal smooth controlAuxiliary feedback+0.0000565030
JobShop SWVBaseline+0.024211
Topology optimizationBaseline+1.226523
UAV inspectionAuxiliary feedback+25.792589

The two tasks highlighted by the reviewer illustrate this distinction particularly clearly. On Max-3-SAT, the winning run made 65 further submissions after reaching 98,945.892, close to the other condition’s best of 98,946.432, before first attaining 98,946.608. On Cascading Flip Schedule, it made 405 further submissions after reaching 77,364.035, already almost identical to the other condition’s best of 77,363.995, before attaining 77,427.673. Thus, the small final gaps correspond to improvements reached after substantial continued search in the observed trajectories. The smaller absolute counts on Frontier-Eng should also be read in context: these runs have a total budget of only 100 submissions. These traces show why numerical proximity alone is insufficient to dismiss the discovery phenomenon.

1.3 Paper framing (Weakness 1 and Question 1)

We appreciate the reviewer clarifying their main concern. Given its importance and close connection to Weakness 1, we address the framing aspect of Question 1 here and discuss the run counts and additional statistical summaries in question part.

We agree that the “5 higher / 8 lower / 2 equal” count should not carry the paper’s framing on its own. Our intended claim is an existence claim: even truthful, verifiable auxiliary feedback can lower the best solution found within a fixed search budget. Our analyses suggest search concentration as a possible explanation for this phenomenon. We do not intend to claim that feedback is harmful on average or reliably harmful on most tasks.

The reviewer’s observations of clear gains on some tasks, declines on others, and unresolved differences on many tasks are consistent with this more focused claim. We will revise the abstract and corresponding discussion to distinguish observed score orderings from statistically established effects. The main contribution is the evidence that more evaluator information need not improve discovery, together with an analysis of how it can change the search process—not a universal ranking of the two feedback conditions.

References

[1] Romera-Paredes et al. FunSearch. Nature, 2024.

[2] Novikov et al. AlphaEvolve. arXiv:2506.13131, 2025.

[3] Yuksekgonul et al. Learning to discover at test time (TTT-Discover). arXiv:2601.16175, 2026.

[4] M. Mang et al. FrontierCS. arXiv:2512.15699, 2025.

[5] Chi et al. Frontier-Eng. arXiv:2604.12290, 2026.

Reviewer_bLs2OpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper asks whether giving LLM coding agents truthful diagnostics beyond the score, which it calls auxiliary feedback, actually helps them discover better algorithms. Comparing runs with and without such feedback on algorithmic and engineering tasks, the authors find that it helps on some tasks and hurts on others. They attribute the losses to an exploration cost, where agents keep refining what the diagnostics point to instead of trying new ideas, and support this with code-trace analysis and a toy Bayesian-optimization model. They also show that dropping the feedback partway through a run can restore exploration.

Critical strengths
  1. The question is a good one and the setup is fair. Both conditions use the same model, harness, evaluator and budget, and the diagnostics come from a fixed analyzer the agent can't read or edit. Even with the statistical problems below, there are clear cases in both directions (Graph 3-Coloring and UAV inspection get better, while Topology optimization and data-center control with two of the models get worse). That's enough to show that adding more truthful information to an AlphaEvolve-style loop isn't automatically free, which matters to anyone building these systems.

  2. The trace analysis is a nice, reusable tool. Comparing consecutive programs by AST to separate "tuning existing thresholds" from "trying new dependencies" turns exploration vs. exploitation into something you can actually count. In data-center control it tells a readable story: the feedback is about carbon-intensity actions, and agents that get it spend more time tuning carbon-intensity thresholds, lead early, and then fall behind.

Critical weaknesses
  1. The headline win/loss count doesn't hold up once you look at the run-level numbers.
  • Recomputing from the paper's own run tables (Tables 5, 7 and 8), comparing means instead of maxima gives roughly 8 higher / 6 lower instead of 5 higher / 8 lower, and Beacon String, Defensive Lineup and data-center control with DeepSeek V4 Pro flip sign.
  • Some comparisons also have unequal run counts (one baseline run vs. three feedback runs for GPT-5.5 on data-center control), which biases a maximum, and the paper doesn't say why runs are missing.
  • I agree that best-found score is the right target for discovery, but that makes noise control more important, not less. The "it can go either way" message survives; the "it hurts more often than it helps" framing in the abstract doesn't.
  1. The proposed mechanism and the proposed fix aren't really tested causally on agents.
  • The trace evidence is correlational. The pooled numbers are dominated by one model, the per-model results are mixed, the best-run comparisons pick runs by their outcome, and the main correlation is partly built into the definitions: a numerical tweak can't add a new dependency, so more tweaks in a fixed budget automatically leave less room for new dependencies. The text also points to uncertainty estimates in Appendix C that I couldn't find.
  • A simpler explanation isn't ruled out. Many diagnostics look like generic output statistics, so the losses could come from distraction or extra context rather than over-exploiting useful guidance. A placebo condition with irrelevant or shuffled diagnostics, or diagnostics that emphasize something else, would test this directly.
  • The BO model mostly builds in its own conclusion (a proximity signal with equal peaks, a much larger inferior basin, and a guidance weight big enough to dominate the acquisition), and the "bridge" to agents is an identity that holds for any two policies. Also, in BO the best setting is steady moderate guidance, but the only agent intervention tested is strong guidance followed by switching it off.
  • The renewed-exploration results are single runs with an unclear switching rule, and we aren't told how many were tried or what happened on the other tasks where feedback hurt. The data-center "benchmark advance" mostly comes from stronger models, since the paper's own plain baselines already beat the published number.
Questions for authors
  1. Why are some runs missing (one baseline vs. three feedback runs for GPT-5.5 on data-center control, and one vs. two for OgreSort)? Were runs dropped for not finishing, for crashing, or for something else?

  2. Is the agent prompt exactly the same in both conditions apart from the diagnostics? The prompt template mentions processed_feedback, so I'd like to rule out the prompt itself steering attention to the feedback.

  3. For renewed exploration, was the switch point fixed in advance or picked by looking at the trace? How many such runs were done, with which models, and what happened on Max-3-SAT, Beacon String, Defensive Lineup and JobShop?

  4. How many runs per model were used for the cross-model Polyomino results, and how was the correlation "after accounting for model-level differences" computed?

8 comments
AuthorsOpenReview ↗

Response to Reviewer bLs2 - Weakness 1

We thank the reviewer for recognizing the importance of the question we study, the fairness of our experimental setup, and the value of our analysis. We address the reviewer's concerns point by point below.

Weakness 1: Aggregation, statistical robustness, and framing

1.1 Mean versus maximum aggregation

We agree that the mean and the best-found score can produce different orderings. They measure different outcomes. The mean reflects a typical run, whereas the best-found score reflects the strongest solution discovered and ultimately retained. As the reviewer notes, the latter is the relevant target for algorithm discovery.

In the original comparisons, all three sign flips follow the same pattern: auxiliary feedback raises the worst run but lowers the best one.

TaskChange in worst-run scoreChange in best-run score
Beacon String+2,504.63−968.57
Defensive Lineup+34.52−62.71
Data-center control (DeepSeek V4 Pro)+2.6187−1.3106

All differences are auxiliary feedback minus score-only baseline.

A higher mean can therefore coexist with a worse discovery outcome. In all three comparisons, removing only the single worst run from each condition is enough to reverse the mean advantage.

1.2 Run-to-run variation and robustness

To address the reviewer's concerns about sign flips and robustness, we ran five additional independent runs per condition for Beacon String, Defensive Lineup, and data-center control with GPT-5.6 Sol. Each of these comparisons now has eight runs per condition. We also include data-center control with DeepSeek V4 Pro, which already had eight runs per condition. To show how the comparison depends on the run budget, we report the expected best score over kk runs sampled without replacement from the eight available. At k=1k=1, this equals the mean. At k=8k=8, it is the observed maximum.

TaskMeanExpected best-of-3Expected best-of-5Best-of-8
Beacon String+318.56−474.16−682.84−874.02
Defensive Lineup+296.97−64.81−65.96−62.71
Data-center control (DeepSeek V4 Pro)+0.1919+0.1700−0.2811−1.3106
Data-center control (GPT-5.6 Sol)−0.1748−0.4648−0.5129−0.5079

All differences are auxiliary feedback minus score-only baseline.

On Beacon String and Defensive Lineup, the mean advantage reverses as early as best-of-3. On DeepSeek V4 Pro, it reverses at best-of-5. The three extended comparisons added 30 new runs. Only two of them exceeded the previous best score in their condition, and neither changed the ordering: score-only feedback kept the higher best-found score in all three comparisons. These results support the stability of the observed ordering on these tasks. We kindly refer the reviewer to Tables 10 and 13 in the revised appendix for the run-level scores of the additional runs.

1.3 The "hurts more often than helps" framing

We thank the reviewer for raising this point and agree that a best-of-3 comparison can be noisy. As a result, the "5 higher / 8 lower" tally across all comparisons may not be a reliable summary, and we appreciate the opportunity to clarify how our conclusions relate to it.

Our intended claim is narrower than the current wording may suggest. We do not aim to show that auxiliary feedback hurts more often than it helps. Rather, we hope to highlight there exists a counterintuitive failure mode in which truthful, verifiable auxiliary feedback can lower the best solution an agent discovers. One might naturally expect accurate additional information to be at worst harmless, and our results suggest that it may not be a free lunch. We recognize that the "hurts more often than helps" phrasing may overstate our findings. In the revision, we will remove this phrasing from the abstract and introduction, state the claim as described above, and present the 5/8 tally only as a descriptive summary of our experiments.

AuthorsOpenReview ↗

Response to Reviewer bLs2 - Weakness 2

Weakness 2: Insufficient causal validation of the proposed mechanism and intervention

2.1 Correlational trace evidence and causal validation

We agree that the pooled correlation alone cannot establish causation, and we do not use it that way. The refinement–exploration analysis characterizes how a finite search budget is divided: submissions spent refining existing rules are unavailable for exploring new dependencies, and this opportunity cost is part of the phenomenon we study. However, exploration breadth counts distinct dependencies rather than submissions, so the two measures do not obey a fixed-sum constraint: one submission can introduce several dependencies.

Our causal interpretation rests instead on interventions on feedback provision. We combine code-evolution evidence with two additional experiments that vary feedback directly: changing how often it is provided and removing versus retaining it from the same search history.

(1) Code evolution: repeated revision of an initially productive component. We examined the highest-scoring auxiliary run for each task where feedback lowered the best-found score. In six of the seven runs (datacenter control is analyzed in paper), a feedback-guided modification first improved the score, after which the agent kept revising the same code component. The table tracks these revisions over the following 20 submissions.

TaskReported diagnosticsRecord-improving modificationSame-component revisions / 20Further improvement / valid revisions
Max-CutTransition rates; partition-size imbalanceStructure-aware candidate selection70/6
Defensive LineupIdentity position fraction; normalized displacementRisk-aware matching coverage70/7
Topology optimizationGray fraction; near-binary fractionDensity-filter and update-schedule tuning80/8
Cascading Flip ScheduleDisplacement; index jump; ascending adjacencyFrontier tie-breaking policy111/10
Beacon StringAlternating-triple fractionEuler traversal ordering40/3
JobShop SWVMachine idle time; maximum utilizationRemaining-work priority parameterization170/15

Across these six tasks, repeated same-component revisions produce only one further improvement in 49 valid revisions. Agents continue to exploit an initially productive direction after its marginal returns have diminished.

(2) Feedback frequency: intermediate provision outperforms both endpoints (Section 5.1; Appendix C). In data-center control, our main case study, we hold diagnostic content fixed and vary only how often it is provided, with five runs per condition. Conditions are ordered from no auxiliary feedback to feedback after every submission; the mean and range summarize the five run-level best-found scores.

Auxiliary feedback frequencyMean best-found scoreΔ vs. score-onlyMin–Max
None (score-only)32.0082—30.7576–32.7106
Every 5 submissions32.5663+0.558131.5678–33.2223
Every 4 submissions32.6104+0.602232.0170–33.0927
Every 3 submissions32.5962+0.588031.7721–33.0986
Every 2 submissions31.6710−0.337231.1466–32.6553
Every submission31.7203−0.287931.2525–32.2027

Feedback every three to five submissions yields mean best-found scores of 32.57–32.61, exceeding both no feedback (32.01) and feedback every submission (31.72). With frequency as a coarse proxy for guidance strength, this matches the BO finding that moderate guidance helps while excessive guidance constrains discovery.

**(3) Same-history continuation: removing guidance restores progress (Section 6; Appendix F). Across eight tasks, we branch from the same auxiliary-run history at a fixed switch point, removing or retaining subsequent diagnostics. Each condition uses GPT-5.6 Sol with three continuations of 50 additional submissions. The table reports the incumbent at the switch and each condition’s best score across continuations.

TaskSwitch pointScore at switchFeedback removedFeedback kept
Frontier-CS
Max-3-SAT10098,916.7798,947.2598,928.61
Max-Cut10087,284.0687,486.8687,398.05
Beacon String10038,943.9338,975.0339,134.14
Cascading Flip Schedule10077,362.7677,413.5777,410.44
Defensive Lineup10059,991.4560,091.5260,016.36
Frontier-Eng
Data-center control5031.789233.861932.4473
JobShop SWV5089.669292.652491.9634
Topology optimization50−183.9828−180.1611−181.0676

Removing feedback yields the higher best score in seven of eight tasks. Both interventions support the BO-motivated prediction: moderate guidance helps, and relaxing continued guidance enables further discovery while preserving previously acquired experience. Together with the code evolution, they support over-exploitation as an explanation for the exploration cost, without relying on the pooled correlation alone.

2.2 Single-model dominance, mixed per-model results, and outcome-based run selection

The pooled association is robust to excluding any single model. The pooled Spearman correlation between refinement allocation and exploration breadth is −0.817 (95% CI [−0.924, −0.651]). Repeating the analysis after excluding each model in turn yields correlations between −0.900 and −0.752, showing that the negative direction does not depend on any one model. Adjusting for model-level mean ranks also yields a negative point estimate (−0.500). Appendix C.4 reports the corresponding uncertainty intervals and stratified-bootstrap procedure.

The interpretation does not require a uniform response across models. Appendix C explicitly reports the heterogeneous per-model results. This analysis characterizes an aggregate search-allocation pattern, rather than asserting an identical behavioral change in every model. The effect of feedback provision on discovery is tested separately by the feedback-frequency and same-history continuation experiments, which vary feedback directly rather than relying on cross-run correlation.

The best-run selection matches the question this analysis addresses, and these runs exhibit a clear exploration–exploitation contrast. Our reported outcome is the best solution discovered under each feedback condition. We therefore examine the corresponding highest-scoring runs to understand the search trajectories behind the gap between these best-found scores. Across all five models, the best auxiliary run explores fewer new control dependencies and achieves a lower best-found score than its baseline counterpart; in four of the five models, it also allocates more submissions to CI-linked refinement. Thus, the trajectories producing the strongest auxiliary results consistently show narrower exploration, usually accompanied by greater feedback-aligned exploitation. Selecting these runs by their final outcome is appropriate for this question: the analysis concerns how the reported best-found solutions were obtained, rather than the behavior of a typical run.

2.3 Distraction or additional context as an alternative explanation

We added a placebo control to test whether additional reading load alone explains the observed losses. The placebo panels match auxiliary feedback in length, format, and statistical structure, including fractions, summary statistics, and extrema. Their values are generated before the experiment using a fixed random seed, independently of the candidate’s code and evaluation outcomes. They therefore introduce comparable reading overhead without supplying candidate-specific guidance. We compare score-only, truthful auxiliary feedback, and placebo feedback on five tasks using GPT-5.6 Sol, with 100 submissions per run and three runs per condition. Following our best-found-score reporting convention, the table reports the highest score across the three runs; run-level results appear in Appendix B.

TaskScore-onlyTruthful auxiliaryPlacebo
Data-center control32.710632.089732.6664
Max-Cut87,485.0587,284.0687,342.21
Beacon String39,191.5539,038.4839,183.05
Defensive Lineup60,083.0359,901.6260,029.46
Cascading Flip Schedule77,364.1076,003.7276,721.47

Truthful auxiliary feedback yields the lowest best-found score on all five tasks, while placebo feedback falls between score-only and truthful feedback. In data-center control and Beacon String, placebo scores are particularly close to the score-only results despite the additional text. This pattern suggests that reading load alone is insufficient to explain the observed best-found-score differences: the content of the diagnostics also matters.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of Discussion by Authors

Summary of Discussion

We would like to express our sincere gratitude to all reviewers for their time, careful consideration, and thoughtful feedback throughout the review and discussion process. As the discussion phase comes to a close, we would like to provide a concise summary of the key outcomes of the rebuttal and discussion.

  • Overall status. Following the rebuttal, two of the three reviewers now lean toward acceptance: Reviewers au7q and bLs2 both raised their scores from 2 to 3. Reviewer j8RY maintained a score of 2 but acknowledged that our additional experiments and analyses strengthened the soundness of the work. We have also provided additional results addressing j8RY's remaining concerns, which are awaiting further feedback.

  • Key strengths recognized by reviewers. All three reviewers recognized the importance of our central finding: truthful feedback in agentic algorithm discovery is not a free lunch, as valuable guidance can also constrain exploration and limit novel discoveries. They also appreciated the rigor and transparency of our experimental analyses.

  • Common discussion points and our responses

Discussion topicRaised byAdditional evidence and clarifications
Statistical robustness and scope of findingsau7q W1.1–1.2; bLs2 W1.1–1.3; j8RY W1.1–1.3We added 30 runs (8 per condition), confirming stable expected best-of-k ordering from k = 3–5 onward. We also reported means for all 15 tasks and refined the framing to an existence claim.
Mechanisms underlying feedback-induced performance differencesau7q W1.3; bLs2 W2.1–2.4; j8RY W2.1–2.4Three complementary analyses strengthen our findings: (1) Placebo controls: truthful feedback performs worst across all five tasks; (2) Feedback frequency: moderate feedback outperforms both extremes; (3) Objective-aligned diagnostics: performance degradation and late-stage stagnation persist under a 200-submission budget.
Motivation and interpretation of the BO setupbLs2 W2.4; j8RY W2.3We clarified that BO illustrates generally useful guidance, with its predictions further supported by agent experiments on feedback frequency and renewed exploration.
Controlled evaluation of renewed explorationau7q W2; bLs2 W2.5Paired continuations with identical histories and matched budgets show that removing feedback improves best-found scores on 7 of 8 tasks.
  • Further evidence addressing Reviewer j8RY's remaining concerns

    • Over-exploitation vs. diagnostic chasing. We tested closely objective-aligned diagnostics with an extended budget, as suggested by the reviewer. Despite genuine early improvements, performance degradation and prolonged stagnation persist, with agents predominantly making constant-only edits. This suggests that diagnostic chasing can itself be a pathway to over-exploitation, rather than a competing explanation.

    • Sustained refinement also appears where feedback helps. On Polyomino Packing, where feedback is beneficial overall, reducing its frequency yields further improvements and encourages alternative algorithmic strategies. Even when feedback helps, over-reliance on it still leaves better solutions undiscovered.

Overall, we believe the discussion has helped clarify and strengthen our central findings and their implications. We sincerely appreciate the reviewers' thoughtful engagement and thank the Area Chair for their time and consideration. We hope this summary will be helpful in the final assessment of our work.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.