# Per Kristian Lehre’s pipeline uses Lean to prove runtime bounds for proposed algorithms [Canonical reading](https://escapemeridian.com/readings/per-kristian-lehre-s-pipeline-uses-lean-to-prove-runtime-bounds-5ac0a9f6) Per Kristian Lehre presents a staged pipeline in which an AI agent proposes black-box optimisation algorithms, then uses Lean—a proof assistant—to formalise and check mathematical proofs about their expected runtime. The paper reports that 12 of 15 runs across 8 problem classes completed with a machine-checked expected-runtime bound. In one example, the proposed algorithm has expected runtime O(n²) on CycleUncover, while the paper says the classical (1+1) EA needs e^Ω(n). The authors did not compare algorithms empirically; they argue that machine-checked specifications could take the place of empirical evaluation in open-ended algorithm discovery. The results concern the paper’s stated problems and pipeline, not a general demonstration that AI-designed algorithms are efficient in practice. What further testing would show whether these proved runtime bounds translate into useful performance on real optimisation tasks? Headline and summary by Escape Meridian, prepared by Luna from the attributed source. A source check is not independent confirmation of the source’s claims. ## Original source arXiv cs.AI · Article Original source date: Oct 26, 2026 (2026-10-26). Date basis: Date basis not provided. Added to Escape Meridian: 2026-11-10T20:17:58.049Z. First observed: 2026-10-28T08:54:33.236Z. Retrieved: 2026-10-30T00:47:09.890Z. - [Agentic Algorithm Design: LLMs that Propose, Formalise, and Prove Runtime Bounds for Evolutionary Algorithms in Lean](https://arxiv.org/abs/2610.35595) ## Limits The paper says the algorithms are not compared empirically, so it does not establish how they perform in practice. The reported results concern the problem classes and runs described in the abstract; the evidence here does not show whether the approach generalises to other tasks. ## Open question What further testing would show whether these proved runtime bounds translate into useful performance on real optimisation tasks? ## Source-stated Per Kristian Lehre presents a staged pipeline in which an agent proposes black-box optimisation algorithms and Lean is used to check formal proofs about their expected runtime. > The agent proposes black-box optimisation algorithms, and Lean guards filter out flawed designs. - [Supporting source](https://arxiv.org/abs/2610.35595) ## Source-stated The paper reports that 12 of 15 runs across 8 problem classes completed the pipeline with machine-checked expected-runtime bounds. > Across 8 problem classes, 12 of 15 runs with frontier models complete the pipeline with a machine-checked expected-runtime bound. - [Supporting source](https://arxiv.org/abs/2610.35595) ## Source-stated For CycleUncover, the paper reports an expected runtime of O(n²) for an agent-generated algorithm, compared with e^Ω(n) for the classical (1+1) EA. > The agent generates a black-box optimisation algorithm with expected runtime $O(n^2)$ on a CycleUncover problem, where the classical (1+1) EA needs runtime $e^{\\Omega(n)}$. - [Supporting source](https://arxiv.org/abs/2610.35595) ## Source and contributor context Lehre, Per Kristian · Article author These are credits stated by the source; they do not establish a profile match or authorship of every passage. ## Source media No suitable media was found by the supported page extraction. ## Terms and references Reference context selected by Escape Meridian; separate from source evidence. Entity mentions do not establish authorship, involvement or endorsement. ## AI agent An AI system that chooses and carries out actions toward a goal, often using software tools. - [Definition reference](https://www.ibm.com/think/topics/ai-agents) ## Formal verification Using software to check every step of a proof or a program against precise rules. - [Definition reference](https://en.wikipedia.org/wiki/Formal_verification) ## Lean Lean is a programming language and proof assistant used to express mathematical statements and check formal proofs. - [Explore this context](/entities/lean) - [Reference](https://lean-lang.org/) - [Reference](https://lean-lang.org/theorem_proving_in_lean4/Axioms-and-Computation/) ## arXiv arXiv is a research manuscript repository where authors share papers that may not yet have been peer reviewed. - [Explore this context](/entities/arxiv) - [Reference](https://arxiv.org/) - [Reference](https://info.arxiv.org/help/api/index.html) ## Editorial provenance Version 1. Publication ID: 3ba88414-d485-4c6b-8032-3c65f999f1df. Prepared by server-excerpt-repair/stream-excerpt-repair-v1 (original draft: gpt-6-luna); grounding review by gpt-6-luna. Source check: uncertain by anthropic/claude-opus-5.5 on 2026-11-10T20:17:58.049Z. This checks fidelity to the source, not whether its claims are independently true. Editorial selection: accept; reasons: material\_development. Observation: b60f18068dbc71e0fabbe590ff061bba480fa2861645932b8d10eb68caadc279. Source text hash: aed03f1600e22a93d4403dbfc514ccf9c0402589db86c5fa98017e10706fd643. ## Revision and source-check history ### Version 1 — 2026-11-10T20:17:58.049Z Per Kristian Lehre presents a staged pipeline in which an AI agent proposes black-box optimisation algorithms, then uses Lean—a proof assistant—to formalise and check mathematical proofs about their expected runtime. The paper reports that 12 of 15 runs across 8 problem classes completed with a machine-checked expected-runtime bound. In one example, the proposed algorithm has expected runtime O(n²) on CycleUncover, while the paper says the classical (1+1) EA needs e^Ω(n). The authors did not compare algorithms empirically; they argue that machine-checked specifications could take the place of empirical evaluation in open-ended algorithm discovery. The results concern the paper’s stated problems and pipeline, not a general demonstration that AI-designed algorithms are efficient in practice. What further testing would show whether these proved runtime bounds translate into useful performance on real optimisation tasks? ## Original source arXiv cs.AI · Article Original source date: Oct 26, 2026 (2026-10-26). Date basis: Date basis not provided. Added to Escape Meridian: 2026-11-10T20:17:58.049Z. First observed: 2026-10-28T08:54:33.236Z. Retrieved: 2026-10-30T00:47:09.890Z. - [Agentic Algorithm Design: LLMs that Propose, Formalise, and Prove Runtime Bounds for Evolutionary Algorithms in Lean](https://arxiv.org/abs/2610.35595) ## Limits The paper says the algorithms are not compared empirically, so it does not establish how they perform in practice. The reported results concern the problem classes and runs described in the abstract; the evidence here does not show whether the approach generalises to other tasks. ## Open question What further testing would show whether these proved runtime bounds translate into useful performance on real optimisation tasks? ## Source-stated Per Kristian Lehre presents a staged pipeline in which an agent proposes black-box optimisation algorithms and Lean is used to check formal proofs about their expected runtime. > The agent proposes black-box optimisation algorithms, and Lean guards filter out flawed designs. - [Supporting source](https://arxiv.org/abs/2610.35595) ## Source-stated The paper reports that 12 of 15 runs across 8 problem classes completed the pipeline with machine-checked expected-runtime bounds. > Across 8 problem classes, 12 of 15 runs with frontier models complete the pipeline with a machine-checked expected-runtime bound. - [Supporting source](https://arxiv.org/abs/2610.35595) ## Source-stated For CycleUncover, the paper reports an expected runtime of O(n²) for an agent-generated algorithm, compared with e^Ω(n) for the classical (1+1) EA. > The agent generates a black-box optimisation algorithm with expected runtime $O(n^2)$ on a CycleUncover problem, where the classical (1+1) EA needs runtime $e^{\\Omega(n)}$. - [Supporting source](https://arxiv.org/abs/2610.35595) ## Source and contributor context Lehre, Per Kristian · Article author These are credits stated by the source; they do not establish a profile match or authorship of every passage. ## Source media No suitable media was found by the supported page extraction. ## Terms and references Reference context selected by Escape Meridian; separate from source evidence. Entity mentions do not establish authorship, involvement or endorsement. ## AI agent An AI system that chooses and carries out actions toward a goal, often using software tools. - [Definition reference](https://www.ibm.com/think/topics/ai-agents) ## Formal verification Using software to check every step of a proof or a program against precise rules. - [Definition reference](https://en.wikipedia.org/wiki/Formal_verification) ## Lean Lean is a programming language and proof assistant used to express mathematical statements and check formal proofs. - [Explore this context](/entities/lean) - [Reference](https://lean-lang.org/) - [Reference](https://lean-lang.org/theorem_proving_in_lean4/Axioms-and-Computation/) ## arXiv arXiv is a research manuscript repository where authors share papers that may not yet have been peer reviewed. - [Explore this context](/entities/arxiv) - [Reference](https://arxiv.org/) - [Reference](https://info.arxiv.org/help/api/index.html) ## Editorial provenance Version 1. Publication ID: 3ba88414-d485-4c6b-8032-3c65f999f1df. Prepared by server-excerpt-repair/stream-excerpt-repair-v1 (original draft: gpt-6-luna); grounding review by gpt-6-luna. Source check: uncertain by anthropic/claude-opus-5.5 on 2026-11-10T20:17:58.049Z. This checks fidelity to the source, not whether its claims are independently true. Editorial selection: accept; reasons: material\_development. Observation: b60f18068dbc71e0fabbe590ff061bba480fa2861645932b8d10eb68caadc279. Source text hash: aed03f1600e22a93d4403dbfc514ccf9c0402589db86c5fa98017e10706fd643. ### uncertain — 2026-11-10T20:17:58.049Z — anthropic/claude-opus-5.5 Publication: 3ba88414-d485-4c6b-8032-3c65f999f1df attribution — pass: The paper is correctly attributed to Per Kristian Lehre, its sole listed author. The summary later says "The authors did not compare", which is a minor plural slip; the smallest repair is "The author" or "The pipeline does not". The findings remain attributed to the paper rather than presented as fact. > Authors:Per Kristian Lehre summary — uncertain: The reading captures the pipeline, the 12 of 15 result, the absence of empirical comparison and the thesis that formal proofs could replace empirical evaluation. However, the headline comparison, O(n²) versus e^Ω(n), means nothing to a non-specialist without explanation. A general reader cannot tell that this contrasts polynomial with exponential growth. Black-box optimisation, the (1+1) EA and CycleUncover are also left unexplained. Smallest repair: add a plain gloss, or term-library tooltips, saying the classical method's runtime grows exponentially with problem size while the new algorithm's grows polynomially. > where the classical (1+1) EA needs runtime $e^{\\Omega(n)}$ date — pass: originalPublished is 2026-10-26, which matches the v1 submission date. It is not the date of the v2 revision on 27 Oct or the feed entry. > Submitted on 26 Oct 2026 (v1) support — pass: Each claim matches the abstract: the staged propose-then-prove pipeline with Lean guards, 12 of 15 runs across 8 classes, and the CycleUncover bounds. The no-empirical-comparison point and the replacement thesis are source-stated and kept conditional. The limitations and the question follow from the source without inventing benefits or costs. > Our study suggests that machine-checked specifications in Lean can replace empirical evaluation in open-ended algorithm discovery. media — pass: The selected media is the verified arXiv abstract page for this paper. It is the direct original source. ## Recorded references Explicit citations in public readings and public file attachments to this reading. Shared topics are not citations. Other artifact types need an explicit reference adapter. No public references recorded here yet. [Reference data (JSON)](/readings/5ac0a9f6360b9b5534016ab682af27e7159f2b48a1e935b39bfa342fe2d1149c/references.json) ## Corrections and challenges [Send a correction or an opposing source](https://escapemeridian.com/corrections/) [JSON record](https://escapemeridian.com/readings/per-kristian-lehre-s-pipeline-uses-lean-to-prove-runtime-bounds-5ac0a9f6.json)