# Autonomous Code Evolution Meets NP-Completeness

arXiv: https://arxiv.org/abs/2509.07367 · HTML: https://mlsanity.com/paper/2509.07367/

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- Placed in Software engineering coding agents, one of 16 directions in LLM agents and tool use.
- Builds on 9 of its 29 references that are in the map.
- First posted on arXiv 9 Sep 2025.

## Placed in

- LLM agents and tool use / [Software engineering coding agents](https://mlsanity.com/agents/software-engineering-coding-agents/)

## Builds on (most cited first, 9 of 9)

- [Gemini 2.5: Pushing the Frontier with Advanced Reasoning, Multimodality, Long Context, and Next Generation Agentic Capabilities](https://mlsanity.com/paper/2507.06261/) (2025)
- [AlphaEvolve: A coding agent for scientific and algorithmic discovery](https://mlsanity.com/paper/2506.13131/) (2025)
- [LLM-SR: Scientific Equation Discovery via Programming with Large Language Models](https://mlsanity.com/paper/2404.18400/) (2024)
- [Symbolic Regression with a Learned Concept Library](https://mlsanity.com/paper/2409.09359/) (2024)
- [AI-assisted coding: Experiments with GPT-4](https://mlsanity.com/paper/2304.13187/) (2023)
- [HeuriGym: An Agentic Benchmark for LLM-Crafted Heuristics in Combinatorial Optimization](https://mlsanity.com/paper/2506.07972/) (2025)
- [DeepSAT: An EDA-Driven Learning Framework for SAT](https://mlsanity.com/paper/2205.13745/) (2022)
- [Clause Vivification by Unit Propagation in CDCL SAT Solvers](https://mlsanity.com/paper/1807.11061/) (2018)
- [Discovering heuristics in a complex SAT solver with large language models](https://mlsanity.com/paper/2507.22876/) (2025)

## Built on by (most cited first, 15 of 15)

- [AIRA_2: Overcoming Bottlenecks in AI Research Agents](https://mlsanity.com/paper/2603.26499/) (2026)
- [Autonomous Evolution of EDA Tools: Multi-Agent Self-Evolved ABC](https://mlsanity.com/paper/2604.15082/) (2026)
- [Agentic Hardware Design as Repository-Level Code Evolution](https://mlsanity.com/paper/2606.28279/) (2026)
- [Magellan: Autonomous Discovery of Novel Compiler Optimization Heuristics with AlphaEvolve](https://mlsanity.com/paper/2601.21096/) (2026)
- [Self-Improvement of Large Language Models: A Technical Overview and Future Outlook](https://mlsanity.com/paper/2603.25681/) (2026)
- [From Heuristic Selection to Automated Algorithm Design: LLMs Benefit from Strong Priors](https://mlsanity.com/paper/2603.02792/) (2026)
- [Contrastive Concept-Tree Search for LLM-Assisted Algorithm Discovery](https://mlsanity.com/paper/2602.03132/) (2026)
- [IC3-Evolve: Proof-/Witness-Gated Offline LLM-Driven Heuristic Evolution for IC3 Hardware Model Checking](https://mlsanity.com/paper/2604.03232/) (2026)
- [Scientific discovery as meta-optimization: a combinatorial optimization case study](https://mlsanity.com/paper/2606.26728/) (2026)
- [TOPCELL: Topology Optimization of Standard Cell via LLMs](https://mlsanity.com/paper/2604.14237/) (2026)
- [Learning to Solve and Optimize by Evolving Code](https://mlsanity.com/paper/2605.31049/) (2026)
- [Simulation-Aware In-Context Policy Improvement for LLM-Aided Analog Layout Refinement](https://mlsanity.com/paper/2608.13767/) (2026)
- [Loreley: Repository-Scale Program Evolution with Quality-Diversity Search](https://mlsanity.com/paper/2608.19703/) (2026)
- [MacroAgent: Regularity-Aware Macro Legalization with LLM-Agent-Designed Contour Algorithms](https://mlsanity.com/paper/2608.24946/) (2026)
- [From Hand-Crafted to LLM-Based Variation Operators in Metaheuristics: A Tutorial](https://mlsanity.com/paper/2609.31649/) (2026)

## Abstract (arXiv)

Large language models (LLMs) have recently shown strong coding abilities, enabling not only static code generation but also iterative code self-evolving through agentic frameworks. Recently, AlphaEvolve citenovikov2025alphaevolve demonstrated that LLM-based coding agents can autonomously improve algorithms and surpass human experts, with scopes limited to isolated kernels spanning hundreds of lines of code. Inspired by AlphaEvolve, we present SATLUTION, the first framework to extend LLM-based code evolution to the full repository scale, encompassing hundreds of files and tens of thousands of lines of C/C++ code. Targeting Boolean Satisfiability (SAT), the canonical NP-complete problem and a cornerstone of both theory and applications. SATLUTION orchestrates LLM agents to directly evolve solver repositories under strict correctness guarantees and distributed runtime feedback, while simultaneously self-evolving its own evolution policies and rules. Starting from SAT Competition 2024 codebases and benchmark, SATLUTION evolved solvers that decisively outperformed the human-designed winners of the SAT Competition 2025, and also surpassed both 2024 and 2025 champions on the 2024 benchmarks.