用大模型引导搜索，找到最优删错码构造函数。
LLM-Guided Search for Deletion-Correcting Codes
- 用大模型引导进化搜索，自动发现删错码构造函数。
- 对单删错码，找到可证明最优的Varshamov-Tenengolts码构造方法。
- 适合对编码理论与智能搜索交叉研究者参考。
寻找最大规模的删错码是超过70年的开放问题，即使对于单个删除也未解决。我们采用大语言模型（LLM）引导的进化搜索方法FunSearch，用于发现短码长下构造删错码的函数。对于单个删除，搜索发现的函数可证明构造出猜想最优的Varshamov-Tenengolts码。对于多重删除及四元编辑码，所发现的函数优于以往显式、搜索和神经方法，但仍是经验启发式，缺乏新理论洞察。我们研究了LLM引导进化搜索的设计选择，发现计算资源应优先分配给更多函数采样而非更长推理路径；同时发现代码与自然语言描述协同进化会降低搜索质量。我们提出在进化中去重逻辑相同的函数，这对保持搜索多样性至关重要。结果表明LLM引导进化搜索在信息论与编码设计中的潜力，这是该方法首次应用于纠错码构造。然而，当前函数评估复杂度随码长呈指数增长，限制了其仅适用于短码。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。