acceptodds
Withdrawn from ICLR 2027

Evolving Towards Better Codes: LLM-Guided Search for High-Distance Binary Linear Codes

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

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 , 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. discovers seven record-breaking codes, , , , , , and , six of which have concise quasi-cyclic descriptions. With standard code modification techniques, they improve entries of the tables. Every code is verified by exhaustive enumeration; the results have been checked by the maintainer of the code tables and will be incorporated into them. These results suggest that LLM-guided search can help find improved codes and complement existing methods in coding theory.

Primary area:
neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)
Keywords:
Evolutionary Search, Large Language Models, Information Theory, Quasi-Cyclic Codes, Algebraic geometry codes

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_GiQ5OpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

The paper investigates whether LLM evolutionary search, supported by human expert input and an exact evaluator, can find improved solutions to a specific mathematical problem: constructing binary linear codes with high minimum distance. The proposed framework combines LLM-generated search programs, established construction strategies, and verified evaluation feedback. It discovers seven codes that improve previously known lower bounds, yielding improvements to 22 table entries through standard code modifications. The paper also compares the framework with directly prompting a strong LLM on two target parameter pairs.

Critical strengths

New constructions that improve existing records. The strongest contribution is the discovery of seven codes that improve previously known minimum-distance bounds, with additional improvements obtained through standard modifications. These are concrete mathematical results whose correctness can be checked independently. The reported exact verification and independent checking by the CodeTables maintainer strengthen confidence in the contribution.

Critical weaknesses
  1. The contribution of the framework’s individual components is unclear. The method includes multiple agent roles, specialized search islands, a large hand-written strategy toolkit, construction-based initialization, secondary fitness criteria, and human intervention. Without appropriate ablations or comparisons against simpler alternatives, it is difficult to determine which components are responsible for the improvements. In particular, the experiments do not separate the benefit of the proposed LLM orchestration from that of expert-selected targets, strong starting constructions, and existing search strategies. This limits the methodological insight provided by the paper.

  2. The comparison with direct prompting is insufficient to establish an advantage. The comparison covers only two target parameter pairs. The framework improves minimum distance from 65 to 66 on one target and matches distance 77 on the other, while obtaining fewer minimum-weight codewords. These results are encouraging, but provide limited evidence of a consistent advantage over direct prompting. Moreover, the baseline protocol is insufficiently specified: it is unclear whether direct prompting received comparable mathematical hints, initial constructions, tool access, human assistance, or computational budgets. Consequently, the observed differences cannot confidently be attributed to the proposed search framework.

Questions for authors
  1. Clarification: What exactly was the direct-prompting protocol? Please specify the prompts, mathematical hints, starting constructions, available tools, and human feedback, and explain how these compare with the assistance provided to LinCodeEvolve.

  2. Clarification: What were the budgets and stopping criteria for each approach, including model calls, computational evaluation, and repeated attempts? Were the reported direct-prompting results the best of multiple attempts, and are repeated-run results available for either approach?

  3. Additional evidence: Can the authors provide ablations or controlled comparisons that isolate the benefit of the proposed framework beyond expert initialization and the strategy toolkit? Particularly informative comparisons would include toolkit-only search and the underlying evolutionary framework without the added agent roles and specialized islands.

1 comment

Dear Reviewer,

Thank you very much for your insightful feedback. On behalf of all the authors, we truly appreciate the time and effort you dedicated to evaluating our work. Your comments have pinpointed important questions to address. In order to address the major revisions, we have decided to withdraw our paper. We are grateful for your guidance, which will strengthen the paper's final version.

Reviewer_SspGOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper describes an evolutionary coding framework designed for discovering new linear codes. The framework builds off an existing evolutionary system called ShinkaEvolve. The paper first introduces the problem of finding linear codes for pairs (n,k)(n,k) where nn is the ambient dimension and kk is the subspace which defines the code. The actual problem involves finding a generator matrix GG that maps messages into this subspace. A linear code is evaluated based on the minimum distance between the codes for a pair of distinct elements. A code with a larger minimum distance is considered better. The paper then discusses some modifications that were made to ShinkaEvolve to make it better align with this problem. This includes expanding the role of the agent responsible for proposing new codes to a team that includes: the oracle, strategist, contract repairer, and implementer. The system also puts more stringent requirements on what can go into the solution archive. The paper ends by summarizing the results which include new lower bounds in several instances. The paper also describes a case where the system matched the dd value of a known bound, but found a simpler and more interpretable construction.

Critical strengths
  • The paper describes real mathematical discoveries: Unlike some papers in AI for math, this work presents a system that produced real discoveries. As noted below, the work explains these results in an accessible way so that the ICLR audience will be able to appreciate them. The reviewer also valued the description of a certain solution that LinCodeEvolve found whose dd value matches the current record but is notably simpler. AI systems infrequently find solutions simpler than their human discovered counterparts, so this was interesting to see.
  • Clarity: This paper is well-written and informative. The reviewer enjoyed learning about linear codes and methods that are used to find them. The work should be accessible to most of ICLR’s participants. This problem may be a good candidate for explorations by others in the community.
Critical weaknesses
  • What is the machine learning contribution?: To this reviewer, the reason to publish a work like this at ICLR is that it contains content that informs on the practice of machine learning. If the primary contribution of the work is the mathematical discovery, then perhaps a math journal is a better venue. This paper is not simply a description of applying ShinkaEvolve to a specific problem. As noted above, LinCodeEvovle contains some modifications aimed at making it better aligned with the problem of discovering linear codes. However, these modifications seemed somewhat minor from this reviewer’s perspective. More importantly, there is no evidence that they actually changed the performance of the method on the task since (to this reviewer’s memory), LinCodeEvolve was not directly compared against ShinkaEvolve. A broader analysis of the system level additions would help strengthen the applicability to ICLR (the comparison is a nice element of this already in the work). Another option would be including more analysis of LinCodeEvolve performance for the purpose of better understanding coding agents and what they are capable of.
  • Better understanding the approach: Related to the point above, the paper is missing some basic information about how LinCodeEvolve actually performs. This reviewer, for instance, would have been interested in understanding the average number of iterations before the optimal solution was found, the cost, the underlying LLM(s) that were used, how many different problems LinCodeEvolve was evaluated against, etc. This will help us to better understanding how hard this task actually was.

Nitpicks:

  • It appears a citation is missing on line 307.
Questions for authors
  • What is “rbouwer zimmeand alh”?
  • What LLMs were used to make these discoveries?
  • How many iterations were required on average?
  • What was the cost of a single run?
  • Would the authors expect this system to continue to perform well for larger values of nn? Beyond looking for places where human found codes seem to have plateaued, what are signs that an (n,k)(n,k) is an especially good candidate for LinCodeEvolve?
1 comment

Dear Reviewer,

Thank you very much for your insightful feedback. On behalf of all the authors, we truly appreciate the time and effort you dedicated to evaluating our work. Your comments have pinpointed important questions to address. In order to address the major revisions, we have decided to withdraw our paper. We are grateful for your guidance, which will strengthen the paper's final version.

Reviewer_wKgvOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper explores how evolutionary program search driven by LLMs can improve the best-known bounds for binary linear codes. The authors build on the EvoTune evolutionary framework and the ShinkaEvolve codebase, and introduce LINCODEEVOLVE. LINCODEEVOLVE evolves code-construction programs against an exact minimum-distance evaluator. Then, a strategy loop combines diversity-driven search and expert supervision. The approach found 7 record-breaking codes, and they improve upon 22 entries in the tables in the database of best-known lower and upper bounds on the minimum distance of linear codes.

Critical strengths
  • A number of results that outperform the currently known best results.
Critical weaknesses
  • Limited novelty. The paper seems to rely heavily on known approaches/frameworks. Better discussion and statements about novelty/differentation would help.

  • Considering that the core contribution of the paper is a framework, I am missing more details about it.

Questions for authors

Since the core contribution is a framework, could you discuss in more detail what the differences from related work are? Are there similar approaches that are done for the same problem? The related work discusses mostly older work, while newer work seems to concentrate on specific code families. But that does not mean those approaches would not work for general binary codes?

Why did you select the range for k, n \leq 200? Are those values practically relevant or just allow enumeration to check the solution?

The paper states "Two things change. The single proposal call becomes a chain of oracle, strategist, contract repair and implementer, with a helper-free invent operator as control. And nothing enters the archive without an exact certificate (Section 4)." I believe more details are needed, as from this, it is not easy to understand the novelty.

"To construct this base, we evaluated a diverse portfolio of structured code families, including design-based, quasi-cyclic, and algebraic constructions." This is not enough detail to allow this work to be reproduced. Moreover, will the framework be published (I miss a clear statement about this).

It is a library of 87 hand-written functions -> again, missing details on who created this, where it is available, and what exactly it contains. This is important, as without information like this, we cannot assess how well the framework works vs. how good the information it used is (or, to say it differently, with the diverse portfolio of code families, hand-written functions, etc., maybe other approaches would also find the same solutions?)

what is genetic population search?

We chose these parameters outside the evolutionary loop by examining the code tables, the constructions behind their lower bounds, and the cost of computing the minimum distance. -> too vague to allow proper understanding or reproducibility

Regarding number theoretic hint: is this really new finding or known fact? Moreover, could the framework find equally good solutions without hints? Could other approaches find equally good solutions if they also used this hint?

I miss some ablations where we can clearly see the contribution of different parts of the framework.

Minor details: represented . -> extra space

using rbouwer zimmeand alh.-> what is this?

[citation needed], and the -> broken reference

183 Such -> missing full stop

1 comment

Dear Reviewer,

Thank you very much for your insightful feedback. On behalf of all the authors, we truly appreciate the time and effort you dedicated to evaluating our work. Your comments have pinpointed important questions to address. In order to address the major revisions, we have decided to withdraw our paper. We are grateful for your guidance, which will strengthen the paper's final version.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.