An LLM pipeline designed black-box optimisation algorithms and then proved their expected runtime in Lean, hitting O(n^2) where the classical (1+1) EA needs e^(Omega(n)) - with no empirical comparison anywhere in the loop
AspireAI community · arXiv (2610.35595)
Submitted to arXiv on October 26, 2026 as 2610.35595, this paper asks whether an LLM can do both halves of algorithm design: propose an algorithm and prove it is efficient. A staged pipeline modelled on the methodology of evolutionary-algorithm research does exactly that. The agent proposes black-box optimisation algorithms, Lean guards filter out flawed designs, and the agent then defines a potential function and proves drift bounds guaranteeing an expected runtime improvement over the baseline. The authors stress that at no point are the algorithms compared empirically - the guarantee comes from the proof. The reported results are an O(n^2) expected runtime on CycleUncover, where the classical (1+1) EA needs e^(Omega(n)), and a matching optimal O(n^2) order on LeadingOnes, with O(n^(2+2c)) for integer-valued submodular minimisation. Across 8 problem classes, 12 of 15 runs with frontier models completed the pipeline with a machine-checked expected-runtime bound; an ablation showed that removing the staging and asking for a zero-shot design with a runtime guarantee produced a copy of the seeded baseline. Code is promised but not yet published.
Read the story and explore more from the AspireAI community.
Two sparse-autoencoder analyses have resisted scaling: matching semantically similar features across layers, and compressing large feature circuits into interpretable supernodes. This paper argues both are the same underlying problem, estimating semantic distances between SAE features that sit on different activation manifolds. Its representation treats each feature not as a single decoder vector but as an activation-weighted distribution over the hidden states expressing it, projects those distributions into a shared reference space, and compares them with Wasserstein distance. The representation is proved invariant to activation rescaling and stable under perturbation, and recovers true matches under finite-sample margin conditions. Empirically it outperformed decoder-vector and LLM-based baselines and captured subtle functional distinctions between related features, and it compressed large feature circuits into interpretable supernodes automatically. The limitation is that this is interpretability tooling: the paper demonstrates better feature matching and circuit compression, not that downstream interpretability claims become more accurate.