acceptodds
Under review as a conference paper at ICLR 2027

Agentic Algorithm Design: LLMs that Propose, Formalise, and Prove Runtime Bounds for Evolutionary Algorithms in Lean

Abstract

LLMs now prove hard theorems in Lean. Can they also design algorithms and prove their correctness and efficiency? LLM-guided design of optimisation heuristics (such as AlphaEvolve) is purely empirical. Automated theorem provers with LLMs prove given statements. So far, there has been little evidence that LLMs can do both: design an algorithm and guarantee its efficiency by a mathematical proof. We present a staged pipeline modelled after research methodology in design and analysis of evolutionary algorithms. The agent proposes black-box optimisation algorithms, and Lean guards filter out flawed designs. The agent then defines a potential function and proves drift bounds that guarantee an expected runtime improvement over the baseline algorithm. At no point in the pipeline are the algorithms compared empirically. The agent generates a black-box optimisation algorithm with expected runtime on a \cycleuncover problem, where the classical (1+1) EA needs runtime . The pipeline also designs and analyses a black-box optimisation algorithm for integer-valued submodular minimisation with expected runtime , and it matches the optimal order on \leadingones. Across 8 problem classes, 12 of 15 runs with frontier models complete the pipeline with a machine-checked expected-runtime bound. An ablation study shows that removing the staging and asking the agent to zero-shot an algorithmic design with a runtime guarantee leads to a copy of the seeded baseline algorithm (random search) or to incomplete proofs. Open-weight models (Goedel-Prover-V2-32B and Gemma 4) did not complete the pipeline. Our study suggests that machine-checked specifications in Lean can replace empirical evaluation in open-ended algorithm discovery. To the best of our knowledge, this is the first example of an automated pipeline that designs efficient black-box optimisation algorithms with machine-checked runtime bounds in Lean.

Primary area:
neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)
Keywords:
black-box optimisation algorithms, Lean, automated heuristic design, machine verified runtime

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_dYrjOpenReview ↗
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
AuthorsOpenReview ↗

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 xx-axis in Figure 3 (was Figure 2 in the original version) by Potential Φ\Phi. 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.

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.

AuthorsOpenReview ↗

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 (n+1)−n(n+1)^{-n}, which is below the 2−n2^{-n} 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.

Reviewer_xHcsOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

The paper proposes a framework for LLM-based design of black-box algorithms for pseudo-Boolean optimisation. The pipeline starts with an initial algorithm and a bound of its runtime, together with some information of the problem in question as a "problem card". The pipeline combines informal stages, where the LLM produces natural-language designs or arguments, and formal stages, where it has to provide a definition or a proof that has to be checked by Lean. At the end of the pipeline, a new design is returned accompanied with an improved bound of its runtime, which is formally verified in Lean by the LLM. This pipeline can be iterated in order to obtain sucessive improvements of the algorithms. The authors apply one iteration of the pipeline (except for the sub-modular minimisation problem, where 5 generations of the pipeline were run) to several problems, obtaining a faster algorithm than the classical (1+1) evolutionary algorithm for one of them and reaching the optimal bounds for other two problems. They also perform an ablation study by using an alternative stageless pipeline and claim that the models cannot produce efficient algorithms this way. Finally, they also test weaker models, which fail to complete the pipeline.

Critical strengths

I find the contributed framework to be of big interest and it looks to have been designed very carefully, modelling the human process of designing optimisation algorithms and analysing them. The alternating informal and formal stages of the pipeline are also interesting: first, a higher degree of freedom is given to the model to come up with a new design or argument in the informal stages; and then it has to try to formalize them in Lean in the formal stages.

Furthermore, I think that this framework has good potential: the authors focus on black-box algorithms for pseudo-Boolean optimization problems in particular, but the pipeline could be easily adapted to use an LLM to design and prove the correctness (and provide machine-checked runtime bounds) of algorithms in other domains.

Critical weaknesses

The contribution of the paper is a framework that uses LLMs to both design algorithms and prove the correctness of associated runtime bounds in Lean. However, I think I would have liked to find more details about how the different components of the pipeline are formalized in Lean. Although I appreciate the level of detail put in the explanation of black-box optimization algorithms and drift analysis in Section 2, this feels very unbalanced when comparing with the Lean part, since there are almost no details about it in the paper (Section 3 is little more than a paragraph). Explaining more explicitly what exactly has to be proven in Lean in each formal stage of the pipeline would make the whole paper more easily understandable. Also, in line 267 in Section 3, authors say that candidate designs are filtered through formal proof obligations via proof guards. I would have liked to find more details about how these guards filter flawed designs in the paper.

Additionally, I think that the paper would benefit from more careful writing in general, since I found it hard to follow at certain points. In particular, Section 4 would benefit the most from it. Regarding the problems, the way they are presented feels a bit inconsistent and confusing. Sometimes they are presented in a single paragraph and sometimes not, and their names are mentioned for the first time inside the text body for some of them, while for others their names seem to be the title of a subsection. This makes hard even to count how many problems are there, since this is not mentioned in the section's introductory paragraph; the number of problems is only mentioned in the abstract and in the conclusion. This lack of structure also makes it hard to identify how many experiment runs were performed for each of the problems, a number that is not consistent across the different problems. Also, in the entire paper there are concepts that are mentioned directly without previously introducing them (e.g., the (1+1) EA that is mentioned several times, algorithm0 mentioned in line 438, etc.). Apart from the presentation, I have some concerns about the contents of section 4 as well. First, the models used in the staged pipeline for each problem are never mentioned. Theorem 4.1 is stated without proof, so I would have liked to see a short explanation or intuition of it. Regarding the ablation study, the model is now mentioned (Fable 5.1), but it is never said whether it is same as in the staged pipeline. In addition, only two problems are considered (CycleUncover and BandwidthVC), while the staged pipeline was run on 8 problems. The cost of the pipeline is not measured, although it is mentioned that it is high in the conclusion.

Questions for authors

See the implicit questions above, and also the following:

  • The pipeline starts with an initial algorithm and associated runtime bound. Does it check if this bound is indeed correct? What would happen if an algorithm with an incorrect runtime bound is provided?
  • Does the pipeline only use a single model per run? Do you think that it could benefit from using different models in different stages?
  • In the conclusion you mention that only the simplified drift theorem is allowed, therefore multiplicative drift is not allowed. What would be needed to be done to allow multiplicative drift? Do you think that would help to prove stronger bounds?
1 comment
AuthorsOpenReview ↗

What Lean checks, how guards filter designs, and answers to Q1–Q3

We thank the reviewer for the detailed review and for the precise questions, which have helped us improve the paper. We have uploaded a revised PDF which improves the presentation significantly. Numbers below refer to the revised version. Theorem 4.1 is now Theorem F.1 (Appendix F).

What is proven in Lean. Section 3 is now a full description of the pipeline (pages 4-6, subsections 3.1-3.3), and its second paragraph says what Lean checks. There are three kinds of stages, tagged in Table 3: informal stages [I], in which the model writes prose, formal stages [F*] in which the agent provides Lean definitions (the algorithm, the potential, the drift constants and sets), and Lean guards [F-] whose statements are fixed by the pipeline and which the agent must prove about its own definitions. Table 3 (Appendix B) lists every stage with the exact statement and the line of the supplementary pipeline file where its prompt and Lean statements are. For example, Stage 4 (NotRandomSearch) requires a proof that some reachable state queries a point that differs from the uniform random draw. The final runtime theorem is also fixed by the pipeline, and it depends only on Lean's standard axioms. Each pseudocode in Appendix H gives the file and line of the corresponding Lean definition (available on openreview).

How the guards filter flawed designs (line 267). The agent never proves that a design is flawed. When a guard cannot be proved, the stage is retried, and when its attempts are used up the pipeline backtracks to earlier stages, eventually to the design stage where the design can be replaced (Section 3, Appendix D). Appendix I now contains an example (Figure 4(a), annotated). In row 11, the first design for BandwidthVC with flat fitness probed vertex pairs on a fixed schedule and used the fitness only after the last probe. At Stage 5 (Adaptiveness), which requires that the fitness influences later queries, the model reported that the statement is false for this design. The pipeline backtracked five times, back to Stage 1, where a new design mixing probing and solving was proposed. This design passed all remaining stages. Section 4.5 also notes that the zero-shot run on CycleUncover reproduced random search, which Stage 4 (NotRandomSearch) would have rejected.

Section 4. Section 4 is now "Experiments and Results". It starts with the experimental setup: 21 runs on 8 problem classes, what is measured for each run, why some problems have several runs (anonymised card, extra lemma, flat fitness, different model, second session), with their rows in Table 1, the models and two backends. Each subsection covers one type of problem and refers to the rows with runs. Table 1 (now in the main text, page 7) gives the model used for every run. Terms are now defined on first use: the (1+1) EA is spelled out and its pseudocode is in the appendix, and algorithm0 has been replaced by "the seeded random search".

Intuition for Theorem 4.1 (now F.1). Section 4.2 now provides a proof idea with the main proof in the appendix.

Ablation. Both zero-shot runs (rows 16 and 18) use Fable 5.1, the same model as the staged runs on these problems (rows 6 and 11-13), so the difference is not due to the model. We restricted the zero-shot ablation to CycleUncover and BandwidthVC because of the cost of the runs: CycleUncover is the new problem, and BandwidthVC is a graph problem on which the staged pipeline completed.

Cost. Table 1 now reports the output tokens of every run (41k to 1.1M for the Claude runs). Appendix I gives the number of attempts per stage and the share of wall-clock time per stage (the drift and runtime stages take 53%). The open-weight runs each ran for 21-46 hours and generated 25-124M output tokens without completing (Appendix H.1).

Q1: Is the seed's runtime bound checked? Yes. A seed must come with a Lean proof of its runtime bound, so an incorrect bound cannot be supplied (the pipeline would not accept the seed). All experiments use the default seed, random search, whose bound O(2n)O(2^n) is machine-checked (Section 3). The improved bound of the output is therefore a machine-checked theorem in Lean.

Q2: One model per run? Yes, each run (row of Table 1) is driven by a single model. The open-weight runs (rows 19-21) already split the roles: Goedel-Prover-V2-32B for the formal stages and Gemma 4 for the prose stages (Appendix D). Combining a strong informal designer with a specialised prover is a natural extension, which we plan to study.

Q3: Multiplicative drift. The pipeline could have been based on the multiplicative drift theorem which is already proved in the latest version of our Lean library. For certain problems, such as Onemax, this would probably give easier proofs. However, the additive drift theorem is in fact more general and versatile than the multiplicative (which is a corollary to the additive drift theorem).

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

This paper proposes a new pipeline that leverages LLMs and Lean for algorithm design. The pipeline generates algorithms, constructs potential functions, and formally verifies bounds on the algorithms' expected oracle-query complexity. The authors evaluate the pipeline on several problems and also introduce a new problem, CycleUncover, to test the pipeline's performance on a problem not previously studied in the literature.

Critical strengths
  • As claimed in the paper, the combination of algorithm design and Lean-verified runtime analysis appears to be novel, and this reviewer believes it has potential. Designing the overall pipeline does not seem trivial, and this reviewer appreciates the authors' efforts.
  • This paper also provides promising experimental results on several problems, including OneMax, LeadingOnes, Jump, vertex cover, and submodular minimization.
  • In addition to testing the pipeline on well-known problems, the authors introduce a new problem, CycleUncover. They show that the algorithm generated by their pipeline achieves an O(n2)O(n^2) expected runtime bound, while Theorem 4.1 establishes that the standard (1+1)(1+1) EA requires eΩ(n)e^{\Omega(n)} expected runtime.
Critical weaknesses

This reviewer believes the biggest weakness of this paper is its presentation and organization.

  • Overall layout of the paper is hard to follow.

    • There are paragraphs that would be better divided, for example, the paragraphs in the Introduction and Related Work, while this reviewer believes the most problematic one is the paragraph in Appendix A. Although this paragraph is in the appendix, its content is not minor. To the best of this reviewer's understanding, it is actually an explanation of the proposed pipeline, which is the main contribution of this paper.
    • There are also some places where itemization could be helpful, such as the contributions paragraph and Corollary 2.1.
  • Important content is hidden in the appendix.

    • While layout could be considered relatively minor, this reviewer thinks the bigger problem is that various important contents are hidden in the appendix. To the best of this reviewer's understanding, the most important contributions of this paper are the pipeline that the authors introduced and its related experimental results. The section that takes the role of formally introducing the pipeline in the main text is Section 3, but it is surprisingly short. The explanation of the pipeline is partially scattered throughout the Introduction and Section 2, which is hard to follow. The main explanation of the pipeline is provided in Appendix A, and it is difficult to read, as previously mentioned.
    • Another main contribution would be the experimental results, but there is no table or figure that summarizes the results in the main text. The table related to the experimental results is Table 1, and it is at the end of the appendix. To the best of this reviewer's understanding, the fact that the algorithm generated by the proposed pipeline has an O(n2)O(n^2) expected runtime bound for CycleUncover is something worth emphasizing, but it is hidden in inline text and Table 1.
    • Meanwhile, Section 1 is the Introduction, and the role of Section 2 is, to the best of this reviewer's understanding, close to that of preliminaries, but the authors spend approximately four pages on these sections while putting important content in the appendix.
Questions for authors

This reviewer understands that the role of CycleUncover is to provide a new problem for testing the proposed pipeline, and that this role is important. However, this reviewer would like to know whether there is any further justification for choosing CycleUncover beyond its novelty. Could the authors share their thoughts on how representative CycleUncover is as a benchmark for the proposed pipeline and whether the results might generalize to other settings?

2 comments
AuthorsOpenReview ↗

Pipeline and results moved to the main text, CycleUncover made prominent

We thank the reviewer for the careful reading and for the constructive and concrete suggestions on presentation. We agree that the submitted version hid parts of the contributions in the appendix. We have uploaded a revised PDF which reorganises the paper following your advise. Section numbers below refer to the revised version. The (1+1) EA lower bound (submitted Theorem 4.1) is now Theorem F.1 in Appendix F.

Pipeline in the main text. The detailed description of the pipeline (previously Appendix A) is now in Section 3 (pages 4--6). It has three subsections that follow Figure 1: 3.1 Algorithm design (Stages 0--8), 3.2 Potential function (Stages 9a--9f) and 3.3 Drift certifications and runtime bound (Stages 10a--10j). Each stage starts with its number and name, and related stages form short paragraphs. Table 3 (Appendix B) lists all 28 stages with the exact statement the agent must prove and its location in the supplementary Lean files which can be downloaded from openreview.

Results in the main text. Table 1 on page 7 now gives an overview of all runs, with columns for the problem, model, pipeline variant, number of generations, the synthesised algorithm, whether the pipeline completed, the order of the proven runtime bound, the output tokens and the lines of Lean code. Section 4 opens with an experimental setup paragraph and is divided into subsections by problem type, each stating the rows of Table 1 it covers.

CycleUncover. To further highlight this result, the problem now has its own subsection (4.2, "A new problem with hidden structure"), with the problem definition and the synthesised algorithm in Figure 2 on page 8, an explanation of why the (1+1) EA is trapped, and the measured runtimes: the synthesised algorithm uses on average 2.7⋅1052.7\cdot 10^5 queries for instance size n=320n=320, whereas the (1+1) EA solves none of the 30 instances with n≥24n \geq 24 within 10710^7 queries (Figure 6, Appendix J).

Layout. The contributions are now an itemised list in Section 1, and the conditions of Corollary 2.1 are numbered (1)--(3) and referred to by number in the pipeline stages. The long paragraphs in the Introduction and Related work (now Section 1.1) have been split. Sections 1 and 2 have been shortened from about four pages to about three, to make room for Sections 3 and 4.

Question: how representative is CycleUncover? CycleUncover was not chosen as a typical benchmark problem but as a deliberately adversarial one. It is solvable in polynomial time, but the (1+1) EA needs exponential time (Theorem F.1). We designed it for this study, so no runtime analysis of it could have appeared in the models' training data. The agent therefore cannot succeed by restating a known analysis, and has to find and exploit the hidden structure. As proof that the pipeline generalises beyond this problem, the same pipeline, with only the problem card changed, also produced machine-checked bounds for three classical benchmark functions, for vertex cover on graphs of bounded bandwidth, for well-covered vertex cover given as an anonymised card (without the problem name), and for integer-valued submodular minimisation (Table 1). We now mention this in the Conclusion.

Thank you for your thorough responses and revisions. I have raised my rating accordingly.

Comments on the paper

3 comments
AuthorsOpenReview ↗

Summary of revision

We thank the three reviews for their useful reviews. All three found the submitted version hard to read, with important contributions in the appendix. We agree with this criticism and have prepared a revised PDF following the reviewers' advise. No technical claim was disputed, and the proven results are unchanged.

The main changes are

  • Pipeline moved to the main text Section 3 now gives a much more detailed description of the pipeline, with one subsection per overall phase. Furthermore, every stage is named and cross-linked with Table 3 (Appendix B), which also provides pointers to the Lean statements in the supplementary files (available via openreview).

  • Results in the main text We provide a more detail detailed description of the experimental setup. Table 1 now shows all runs numbered by rows for easier cross-checking with the main text. Each row states the model used, the proven bound, the number of output tokens, and the number of lines of Lean code produced (which is available in the supplementary files).

  • CycleUncover is now more prominent.

  • Terms are defined when they are first used, e.g., black-box algorithms, drift, (1+1) EA, etc.

  • Layout (x76C). The contributions are an itemised list, and long paragraphs in the Introduction and Related work have been split. Sections 1 and 2 are shorter to make room for Sections 3 and 4.

  • How the guards filter designs (xHcs). Appendix I gives a worked example from the pipeline logs: in row 11, the guard Adaptiveness could not be proved for the first design, and the pipeline backtracked to the design stage, where a new design was proposed and passed all remaining stages (Figure 4(a)).

  • Supporting measurements (new, Appendix J). As an independent check, every synthesised algorithm was transcribed from its Lean definition and run. For every run with a proven bound, the measured growth is consistent with the bound (Table 5). On CycleUncover, the synthesised algorithm needs 2.7⋅1052.7\cdot 10^5 queries on average at n=320n = 320, while the (1+1) EA solves none of 30 instances with n≥24n \geq 24 within 10710^7 queries (Figure 6). These measurements support the proven results, they are not new claims.

One correction. The submitted abstract and conclusion accidentally said that the agent "matches the optimal order O(n2)O(n^2)" on LeadingOnes. This is wrong: in the black-box model of the paper, the optimal order for LeadingOnes is Θ(nlog⁡log⁡n)\Theta(n \log \log n), and O(n2)O(n^2) is the order of the (1+1) EA and other typical EAs. The revision says "matches the classical order O(n2)O(n^2)". The proven bound itself is unchanged.

Because of the reorganisation, the numbering of sections, appendices, figures and tables has changed; the reviewer-specific replies give the new locations. The supplementary material is unchanged.

Dear authors and reviewers,

The author-reviewer discussion period closes on November 18 (AoE). Please engage in response periods so that we have our issues discussed thoroughly.

AC

AuthorsOpenReview ↗

Status of the discussion

Dear area chair,

Thank you for sending the reminder. We uploaded a revised PDF version on November 12th, posted a summary of the revisions, and addressed all of the reviewers' points. We have not yet received a response from the reviewers. In case it is helpful, here is an overview of the status of the paper as we see it:

Shared concern: presentation All three reviewers commented on the same aspects: the details of the pipeline and the results were in the appendix, and some terms were used before they were defined. In the revised PDF version, we have moved the pipeline to Section 3 of the main text. We have also moved Table 1 (summary of results) to the start of Section 4, and terms are defined when they are first used.

Technical content No reviewer disputed a technical claim. We have responded individually to all questions posed by the reviewers.

Changes to claims The proven results are unchanged. We corrected one wording error in the abstract and conclusion (LeadingOnes: "classical order" vs "optimal order"), as disclosed in the summary of revisions. The new appendix J reports measurements that support the proven claims.

We are unaware of any open points. We would be grateful if the revised PDF and our responses could be considered in the discussion.

Thank you again for handling the submission.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.