- Rating
- 2
- Confidence
- 1
- Informativeness
- 1
- Presentation
- 1
- Soundness
- 3
Read review
Paper summary
This paper proposes a multi-stage agentic pipeline that designs improved algorithms and produces proofs of their expected runtime bounds. The pipeline follows a human researcher's process of algorithm design and analysis. The authors report that 12 of 15 frontier-model runs across eight problem classes complete the pipeline with machine-checked bounds.
Critical strengths
This paper tries to build an agentic pipeline which reflects a human researcher's workflow and to equip it with formal math verification to validate the results.
Critical weaknesses
My main concern is the poor presentation. I admit that there is a possibility that I have misjudged this paper because I'm not an expert in TCS or algorithm design, so I set my confidence to 1. However, I think several issues below apply to papers in any field. The authors should make the paper understandable to readers with a general machine learning background.
- The abstract and introduction use technical terms before explaining them, such as “(1+1) EA,” “black-box optimization algorithms,” and “drift.” This makes it hard to understand the contribution of this paper.
- Several descriptions and visualizations are unclear. For example, it is unclear what the x- and y-axes in Figure 1 represent. “Lean guards” also needs a clear definition. The introduction uses vague wording such as “some informal stages” and “some formal stages are gates to filter out flawed designs.” The word “some” is imprecise. The authors should specify which stages they mean. These descriptions confuse readers before reaching the technical details.
- The main text is unbalanced. The pipeline is the main contribution, but Section 3 spends less than half a page explaining it, leaving all the details to the appendix. In contrast, Section 2 spends roughly a page and a half on background information. The Results section contains few numerical results, while the main results tables and figures are placed much later in the appendix. The main text also lacks a clear experimental setup.
I also have two concerns about the technical content in this paper.
- The pipeline validates the results in Lean, but it is unclear how it guarantees that the Lean statements faithfully represent the informal mathematics.
- The ablation study compares the staged pipeline with a one-shot pipeline, but it does not study how each component contributes to the results.
Questions for authors
I have no additional questions.
3 comments
Thank you for the revision and clarification! My concern on the ablation study is not fully addressed. I fully understand that a full ablation study is not feasible due to cost constraints. However, the evidence for the contributions of some components is insufficient to support the authors' conclusions.
-
'An earlier pipeline version without the reachability condition': It is unclear what exactly is meant by "earlier version." I searched the paper and found only three mentions of "earlier versions," which means that more than one earlier version was used in the experiments. It is too vague to understand exactly which version was used.
-
'A Lean guard rejecting a design': A single data point cannot provide meaningful evidence.
Again, a note for the AC: I am not familiar with the field of algorithm design and cannot assess the quality of the final algorithms produced by their pipeline. Please take this into account when making your final decision.
More evidence of guards rejecting designs, and which pipeline version were used in each run
Thank you for the reply. Both points are fair. We have gone through the logs of all runs and the supplementary files to answer them, and we have uploaded a new revision with the results (Appendices B and I).
Which pipeline version. The pipeline file was revised during the
study, and the paper did not say which run used which
revision. Appendix B now does ("Pipeline versions"). All revisions
have the same 28 stages, and the final.lean of every run in the
supplementary material contains the guards exactly as that run had to
prove them. Compared with Table 3, the statements differ in two places
only:
- Row 21 is the only run with weaker guards. It used an early revision of the pipeline
(2 September), in which NotRandomSearch did not require the witness state to be reachable
(line 1588 of
runs/21_OneMax_GoedelProverV2_Gemma4_run3/final.lean; Adaptiveness, line 1636, was also weaker). This is the "earlier version" of our first reply. Both guards were changed after this run, and every other run that reached these stages had to prove the statements of Table 3. - In rows 1, 6, 10, 11 and 12, two of the drift guards (Stages 10h and 10i) are required for all states, not only for reachable ones. This is a stronger requirement.
All other changes between revisions are to the prompts, not to what must be proved.
More than one data point. We agree that discussing more than one example of a backtrack would
be helpful. The experiments contained a large number of backtracks, and some of the evidence for
this was already in the first submission. But we agree that it was not easy to find. Note that
every drop in Figure 4(a) is a backtrack, Figure 5 shows the attempts per stage, and the Lean
files in the supplementary material contain the agent's own analysis of why a design fails
(for row 13, the counterexample is in runs/13_BandwidthVC_Fable51_second_session/final.lean, lines
3139-3226). We have now gone through the logs of every staged run with a frontier model
(rows 1-15), and Appendix I reports the following:
- Six cases, in five runs, where the agent's own answer states that the guard is false for its design and gives a counterexample (table in Appendix I). In rows 12, 13 and 14, the guard that requires an improvement over the seed (Stage 10c) rejected local-search designs for vertex cover: at a cover that is minimal but not minimum, an improving step has probability , which is below the of random search. In row 14 this guard failed 47 times, the pipeline restarted, and the second design passed. In rows 8 and 12, the agent reported that the mass bound of Stage 10h is false for its drift sets. Row 11 is the example we gave before.
- What happened to the rejected designs. Rows 8, 12 and 13 never passed the guard, so no runtime bound was certified for these designs. Rows 11 and 14 completed with a different design.
- All backtracks. 43 backtracks start at a guard, in 14 of the 15 runs and at seven different guards (the counts per guard are in Appendix I).
We also state the limits. A failed guard is a failed proof and does not by itself show a flaw: the open-weight runs (rows 19 and 20) stopped at a guard whose statement is true for their designs. And these are observations from the runs, not a controlled ablation: they show that the guards reject designs in practice, not what the pipeline would produce without a given guard.
Revised presentation, experimental setup in main text, structure revised
We thank the reviewer for the review, and in particular for reading the paper from a machine learning point of view. We agree that the submitted version was hard to follow and have prepared a revised PDF.
Terms defined on first use. Black-box optimisation algorithms and their runtime (the number of queries made before finding the optimum) are now defined in the first contribution in Section 1. The abbreviation (1+1) EA is spelled out as (1+1) Evolutionary Algorithm, and we cite an authorative reference which explains this algorithm. The appendix contains its pseudo-code. The term drift is now explained both informally (how much the algorithm reduces the distance to the optimum per iteration) and formally in Section 2.
Figure 1. This figure should be read as a flow diagram of the pipeline, where arrows represent next steps. The arrows along the left and bottom edges close the loop, feeding the new algorithm as input to the next generation. We have labelled the x-axis in Figure 3 (was Figure 2 in the original version) by Potential Φ. This figure has no y-axis.
Lean guards and "some" stages. We have reorganised and improved the description of the pipeline, including moving parts of the description from the appendix into Section 3. We clarify the three types of stages and connect them to Table 3, which lists every stage: informal stages [I] (where a model writes prose), formal stages [F*] where the agent must provide a Lean definition, and Lean guards marked [F-] where the agent must prove properties about its own design, for example that the algorithm differs from random search. A design whose Lean guard cannot be proved is dropped by the pipeline. Appendix I gives a short worked example of a guard rejecting a design.
Balance of the main text All the description of the pipeline has been moved to an expanded Section 3 (pages 4--6). The introductory section 2 has been shortened. Section 4 explains the experimental setup (problems, runs, models, backends, what is measured), and the table of all runs is now Table 1 in the main text with the model, the proven runtime bound, the output tokens, and the lines of Lean code of every run. Figure 2 shows the CycleUncover problem and the algorithm designed for it. Appendix J adds measured runtimes of all synthesised algorithms (Table 5) and compares the CycleUncover algorithm with the (1+1) EA (Figure 6).
Faithfulness of the Lean statements. The trusted part is small and fixed. The problem card (the Lean definition of the problem class) and the statement of the final runtime theorem are written by us and cannot be changed by the agent; the agent supplies only definitions (algorithms and potentials) and proofs. The drift theorem used in the final step is proven in our Lean library, not assumed, and the final theorems depend only on Lean's standard axioms (propext, Classical.choice, Quot.sound), with no
sorry. What remains outside the formal guarantee is that the problem definition (problem card) correctly encodes the intended optimisation problem. Section 3 states that the user is responsible that the Lean definition faithfully encodes the intended optimisation problem. As an independent check, Appendix J re-implements every synthesised algorithm directly from its Lean definition and measures its runtime (Table 5). For every run with a proven bound, the measured growth is consistent with the bound, and in most runs clearly below it; for example, the CycleUncover algorithm (row 6) stays a factor 4.5--10 below its proven bound for all n up to 320. The re-implementation of row 18, which is the (1+1) EA, gives the same runtimes as our reference implementation of the (1+1) EA.Further ablations. A full ablation that removes one guard at a time would require several runs per guard and problem, which is beyond our budget (each completed run took 144k--1.1M output tokens with commercial frontier models). However, the paper already contains some single component evidence: without the staging, the zero-shot run on CycleUncover reproduced random search, which the NotRandomSearch guard would have rejected (Section 4.5). In one open-weight run, an earlier pipeline version without the reachability condition in NotRandomSearch allowed a random search algorithm to pass through the algorithm stages. Appendix I shows a Lean guard rejecting a design and the pipeline backtracking until a new design passes. The Limitations paragraph notes that a more complete experimental design was not feasible because of the cost of the runs.