Llm guided search finds better binary linear codes with higher error resistance
Evolving Towards Better Codes: LLM-Guided Search for High-Distance Binary Linear Codes
Information TheoryArtificial IntelligenceNeural and Evolutionary Computing
Summary
Finding the best binary linear codes is a hard challenge important for reliable communication. The authors combined evolutionary computer programs with large language models (LLMs) to search for better codes. Their system, LinCodeEvolve, found several new codes that improve known limits for code length, data size, and error resistance. These codes were thoroughly checked using exact methods to confirm their quality. This work shows how AI tools can help discover improved codes to make data transmission more efficient and reliable.
What this means in practice
- •For data transmission engineers: Implement codes with higher error correction to improve communication system reliability.
- •For storage system designers: Use discovered codes to enhance data integrity in memory and storage devices.
Authors
Amal Seddas, Vladyslav Shashkov, Maryna Viazovska, Emmanuel Abbe
Abstract
Evolutionary program search driven by large language models (LLMs) has produced record-breaking constructions for open problems in combinatorics and beyond. We apply this approach to the longstanding problem of improving the best-known bounds for binary linear codes. Building on the EvoTune evolutionary framework and the ShinkaEvolve codebase, we introduce LinCodeEvolve, which evolves code-construction programs against an exact minimum-distance evaluator. A strategy loop combines diversity-driven search and expert supervision: when progress plateaus, new strategies are used to redirect the search. LinCodeEvolve discovers seven record-breaking codes, $[172,21,66]$, $[173,20,68]$, $[176,21,68]$, $[181,21,70]$, $[184,21,72]$, $[189,22,72]$ and $[200,21,77]$, six of which have concise quasi-cyclic descriptions. With standard code modification techniques, they improve $22$ entries of the tables. Every code is verified by exhaustive enumeration. These results suggest that LLM-guided search can help find improved codes and complement existing methods in coding theory.