# LLM-Guided Search for Deletion-Correcting Codes

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 33 of its 85 references that are in the map.
- First posted on arXiv 1 Apr 2025.

## Builds on (most cited first, 30 of 33)

- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [Evaluating Large Language Models Trained on Code](https://mlsanity.com/paper/2107.03374/) (2021)
- [DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning](https://mlsanity.com/paper/2501.12948/) (2025)
- [Competition-Level Code Generation with AlphaCode](https://mlsanity.com/paper/2203.07814/) (2022)
- [Solving Quantitative Reasoning Problems with Language Models](https://mlsanity.com/paper/2206.14858/) (2022)
- [Large Language Models as Optimizers](https://mlsanity.com/paper/2309.03409/) (2023)
- [Eureka: Human-Level Reward Design via Coding Large Language Models](https://mlsanity.com/paper/2310.12931/) (2023)
- [Promptbreeder: Self-Referential Self-Improvement Via Prompt Evolution](https://mlsanity.com/paper/2309.16797/) (2023)
- [StarCoder 2 and The Stack v2: The Next Generation](https://mlsanity.com/paper/2402.19173/) (2024)
- [ReEvo: Large Language Models as Hyper-Heuristics with Reflective Evolution](https://mlsanity.com/paper/2402.01145/) (2024)
- [Evolution of Heuristics: Towards Efficient Automatic Algorithm Design Using Large Language Model](https://mlsanity.com/paper/2401.02051/) (2024)
- [Evolution through Large Models](https://mlsanity.com/paper/2206.08896/) (2022)
- [LLM-SR: Scientific Equation Discovery via Programming with Large Language Models](https://mlsanity.com/paper/2404.18400/) (2024)
- [EvoPrompting: Language Models for Code-Level Neural Architecture Search](https://mlsanity.com/paper/2302.14838/) (2023)
- [Monte Carlo Tree Search for Comprehensive Exploration in LLM-Based Automatic Heuristic Design](https://mlsanity.com/paper/2501.08603/) (2025)
- [LLMatic: Neural Architecture Search via Large Language Models and Quality Diversity Optimization](https://mlsanity.com/paper/2306.01102/) (2023)
- [Can GPT-4 Perform Neural Architecture Search?](https://mlsanity.com/paper/2304.10970/) (2023)
- [HSEvo: Elevating Automatic Heuristic Design with Diversity-Driven Harmony Search and Genetic Algorithm Using LLMs](https://mlsanity.com/paper/2412.14995/) (2024)
- [Large Language Models As Evolution Strategies](https://mlsanity.com/paper/2402.18381/) (2024)
- [Evolving Deeper LLM Thinking](https://mlsanity.com/paper/2501.09891/) (2025)
- [Discovering Preference Optimization Algorithms with and for Large Language Models](https://mlsanity.com/paper/2406.08414/) (2024)
- [What's Wrong with Deep Learning in Tree Search for Combinatorial Optimization](https://mlsanity.com/paper/2201.10494/) (2022)
- [Finding Near-Optimal Independent Sets at Scale](https://mlsanity.com/paper/1509.00764/) (2015)
- [Large Language Model-Based Evolutionary Optimizer: Reasoning with elitism](https://mlsanity.com/paper/2403.02054/) (2024)
- [REvolve: Reward Evolution with Large Language Models using Human Feedback](https://mlsanity.com/paper/2406.01309/) (2024)
- [FunBO: Discovering Acquisition Functions for Bayesian Optimization with FunSearch](https://mlsanity.com/paper/2406.04824/) (2024)
- [Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)](https://mlsanity.com/paper/1412.0348/) (2014)
- [Explicit two-deletion codes with redundancy matching the existential bound](https://mlsanity.com/paper/2007.10592/) (2020)
- [Unrealized Expectations: Comparing AI Methods vs Classical Algorithms for Maximum Independent Set](https://mlsanity.com/paper/2502.03669/) (2025)
- [Efficient Low-Redundancy Codes for Correcting Multiple Deletions](https://mlsanity.com/paper/1507.06175/) (2015)

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

- [Using Reasoning Models to Generate Search Heuristics that Solve Open Instances of Combinatorial Design Problems](https://mlsanity.com/paper/2505.23881/) (2025)
- [Automated Discovery of Improved Constant Weight Binary Codes](https://mlsanity.com/paper/2603.00174/) (2026)
- [Autonomous Discovery of Wireless Communications Algorithms](https://mlsanity.com/paper/2607.17762/) (2026)
- [Evolving Towards Better Codes: LLM-Guided Search for High-Distance Binary Linear Codes](https://mlsanity.com/paper/2609.37056/) (2026)

## Abstract (arXiv)

Finding deletion-correcting codes of maximum size has been an open problem for over 70 years, even for a single deletion. We adapt FunSearch, a large language model (LLM)-guided evolutionary search, to discover functions that construct deletion-correcting codes at short code lengths. For a single deletion, our search finds a function that we prove constructs the conjectured-optimal Varshamov-Tenengolts code. For multiple deletions and quaternary edit codes, the discovered functions improve on prior explicit, search-based, and neural constructions but remain empirical heuristics without new theoretical insights. We study design choices for LLM-guided evolutionary search and find that, for our problem, 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. We propose deduplicating logically identical functions during evolution, which we find critical for search diversity. Our results demonstrate the potential of LLM-guided evolutionary search for information theory and code design and represent the first application of such methods for constructing error-correcting codes. However, in our current formulation, evaluating a function scales exponentially with code length, limiting the approach to short codes.