Per Kristian Lehre’s pipeline uses Lean to prove runtime bounds for proposed algorithms

Per Kristian Lehre’s pipeline uses Lean to prove runtime bounds for proposed algorithms

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?

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.