EPFL's LinCodeEvolve (Viazovska, Abbe) finds seven record-breaking binary linear codes with LLM-guided program search
On Sept 29, 2026 EPFL researchers Amal Seddas, Vladyslav Shashkov, Maryna Viazovska (Fields Medal 2022) and Emmanuel Abbe posted LinCodeEvolve, an LLM-driven evolutionary program search (built on ShinkaEvolve and EvoTune) that found seven binary linear codes beating the best-known minimum distances in Grassl's CodeTables, e.g. [172,21,66] and [200,21,77]. With standard modifications they improve 22 table entries. Every code was verified by exhaustive enumeration, and the table maintainer checked them. The work applies the FunSearch/AlphaEvolve approach to a classic coding-theory benchmark.
Key facts
- arXiv 2609.37056 [cs.IT], 29 Sep 2026; authors Seddas, Shashkov, Viazovska, Abbe (EPFL)
- Seven new record codes: [172,21,66], [173,20,68], [176,21,68], [181,21,70], [184,21,72], [189,22,72], [200,21,77]; six have concise quasi-cyclic descriptions
- Standard code modifications extend these to 22 improved entries of the binary tables at codetables.de; 'the results have been checked by the maintainer of the code tables and will be incorporated into them'
- Method: an LLM proposes code-construction programs (a chain of oracle, strategist, contract-repair and implementer calls), scored by an exact minimum-distance evaluator; a strategy loop with expert supervision redirects the search when progress plateaus
- Comparison: directly prompting GPT-6 Astra at extra-high reasoning effort gave distance 65 for (172,21) vs 66 from LinCodeEvolve; at (200,21) both reached 77, but LinCodeEvolve's code has 25 minimum-weight codewords vs 75
- Compute: a single 80 GB H100; each experiment took 3–4 hours on average
Science result
- Field
- mathematics / coding theory
- Problem
- Improving best-known lower bounds on the minimum distance of binary linear codes (Grassl's CodeTables)
- Result
- Seven new record binary linear codes (lengths 172–200, dimensions 20–22), improving 22 table entries after standard modifications
- AI system
- LinCodeEvolve, GPT-6 Astra
- Human role
- Human-designed LLM-guided search with expert supervision of strategies; codes verified by exhaustive enumeration
- Verification
- Exhaustive computer verification; checked by the CodeTables maintainer
- Status
- confirmed
What happened
Finding binary linear codes with large minimum distance is a central coding-theory problem, and certifying minimum distance is NP-hard. LinCodeEvolve keeps ShinkaEvolve's island-based archive, novelty judge and model selection. Candidates enter the archive only with an exact certificate (full weight distribution). Among codes with equal distance it prefers fewer minimum-weight codewords.
Why it matters
Viazovska, who solved sphere packing in dimensions 8 and 24, is now co-authoring LLM-search papers. It is another case of FunSearch-style search improving a long-maintained table of records with modest compute (one H100). The authors note that careful prompting of a frontier model (GPT-6 Astra) came close on some parameters, but systematic search did better across many parameter pairs.
Changelog
- 2026-09-30: created (sweep 2026-09-30, arXiv AI-disclosure section)
Related events
- AlphaEvolve: Gemini-powered agent discovers new algorithms ★★★★
- Summer 2026 flood: dozens of named conjectures settled on arXiv with disclosed AI help (July–September catalogue) ★★★★
Sources (2)
- paperarXiv 2609.37056: Evolving Towards Better Codes: LLM-Guided Search for High-Distance Binary Linear Codes
- docsCodeTables.de (Grassl): bounds on linear codes
id: 2026-09-29-lincodeevolve-record-binary-codes · updated 2026-09-30 · open in the interactive timeline