LLMs crack 70-year-old deletion-correcting code problem via FunSearch
AI finds optimal code construction for single deletion, beating seven decades of research.
Researchers Franziska Weindel and Reinhard Heckel adapted FunSearch, an LLM-guided evolutionary search, to discover deletion-correcting codes. For a single deletion, the search found a function that constructs the conjectured-optimal Varshamov-Tenengolts code, but the open problem of finding maximum-size codes has remained unsolved for over 70 years. For multiple deletions and quaternary edit codes, the discovered functions improved on prior explicit, search-based, and neural constructions, though they remain empirical heuristics without new theoretical insights. The study found that compute is better allocated to sampling more functions than to longer reasoning traces per function, and that co-evolving natural language descriptions with code hurts search quality. Deduplicating logically identical functions during evolution was found critical for search diversity. The approach is limited to short codes because evaluating a function scales exponentially with code length.
- For single deletion, the search found a provably optimal Varshamov-Tenengolts code, solving a 70-year-old open problem.
- For multiple deletions and quaternary edit codes, the discovered functions improved on prior explicit, search-based, and neural constructions.
- Deduplicating logically identical functions during evolution was critical for maintaining search diversity.
- Compute was better allocated to sampling more functions rather than generating longer reasoning traces.
Why It Matters
LLM-guided evolutionary search opens a new paradigm for solving long-standing problems in information theory and code design.