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

1 Introduction

• Minimum distance determines worst-case error-correction capability and enters standard upper bounds on block error probability under maximum-likelihood decoding.Explicit constructions can exceed the Gilbert–Varshamov bound for particular lengths and dimensions, as recorded in CodeTables.Source: §1 · p. 1
• A construction that succeeds for one length and dimension may not work as well for another, motivating adaptation and combination of methods across parameter pairs.Executable proposals can be evaluated and their results used to guide subsequent proposals.Source: §1 · p. 1
• Prior LLM-driven program search paired generated programs with evaluators and candidate databases, while coding-theory work had also evolved priority functions for deletion-correcting codes [WH25].FunSearch and AlphaEvolve applied program evolution to other mathematical and algorithmic problems [N+25].Source: §1 · pp. 1–2
• LINCODEEVOLVE evolves code-construction programs and evaluates their outputs, using verified results to guide later proposals.The framework builds on ShinkaEvolve and uses specialist search islands, shared strategies, and verified codes.Source: §1 · p. 2
• Seven codes improve longstanding lower bounds by one to three units, with derived constructions improving 22 parameter sets at lengths 171–200.The search targets fixed (n, k) pairs with 1 ≤ k ≤ n ≤ 200.Source: §1 · p. 2

Background

• A binary linear [n, k] code is a k-dimensional subspace of F_2^n, and its minimum distance equals the minimum weight among nonzero codewords.The code rate is R = k/n.Source: §2 · p. 2
• Minimum distance guarantees correction of up to floor((d(C) − 1)/2) arbitrary errors, while the Gilbert–Varshamov bound gives an asymptotic rate–distance existence guarantee.For relative distance δ, the stated guarantee applies at rates below 1 − h_2(δ).Source: §2 · p. 2

Record tables and distance certification

• Code tables record best-known lower and upper bounds; improving a lower bound requires a rigorous distance guarantee because failure to find a low-weight word does not certify its absence.Exact certification is computationally challenging; minimum-distance computation is NP-hard.Source: §2 · p. 3

Computer search for record codes

• Record-code searches explore quasi-cyclic families, secondary constructions, and prescribed symmetries, alongside specialized learning-based methods.The paper focuses on improvements to general binary linear-code tables.Source: §2 · p. 3

LLM-driven program evolution

• LLM-driven program evolution generates and evaluates programs in a loop; LINCODEEVOLVE adds a multi-role proposal chain, a helper-free invent operator, and exact certification before archiving.The framework retains ShinkaEvolve components including islands, novelty assessment, prompt evolution, and UCB1-style model selection.Source: §2 · p. 3

Related work

• The paper relates its exact-checker premise to learned constructions and neuro-symbolic provers, and notes that mutation chains can collapse onto a few forms [GSW26].Only exact computations determine a code’s score or stored evidence; program self-reports do not change the score.Source: §2 · pp. 3–4

3 Problem Statement

• For fixed (n, k), the task is to find a generator matrix with distance at least d_LB + 1 when the table entry’s lower bound is below its upper bound.This exceeds the best-known linear code for those parameters.Source: §3 · p. 4
• Among codes with the same minimum distance, the search prefers fewer minimum-weight codewords, denoted by A_d.The number of minimum-weight codewords is called the shell; reaching distance d + 1 requires the weight-≤d codeword count to be zero.Source: §3 · p. 4

4 The LINCODEEVOLVE Framework

• The framework retains ShinkaEvolve’s evolutionary infrastructure and adds code-construction components, with exact evaluation and multiple construction-focused islands.The model parameters remain fixed throughout the search.Source: §4 · p. 4

4.1 Agent-Guided Program Generation

• Discover splits proposal generation into diagnosis, strategy selection, and implementation, while Invent proposes procedures without direct Toolkit access.Proposals receive the parent code and verified evidence; operator probabilities adapt to the parent’s distance and recent outcomes.Source: §4.1 · pp. 5–6
• Programs face format, novelty, and execution checks; only rank-k binary k × n outputs are evaluated, and invalid runs retain the parent’s score without entering the archive.The archive keeps up to 96 programs, one per distinct code.Source: §4.1 · p. 6

4.2 Fitness

• Fitness maximizes (d, −A_d) lexicographically, favoring higher minimum distance and then fewer minimum-weight codewords.At small crossover probability, reducing A_d reduces the leading contribution to undetected-error probability.Source: §4.2 · p. 6

4.3 Initialization: Generation 0

• Generation 0 selects a strong seed from a portfolio of structured code families, using inexpensive estimates to shortlist candidates before exact evaluation.The comparison reports seed results against the Gilbert–Varshamov bound and random full-rank matrices, with exact distances verified by enumeration for k ≤ 30.Source: §4.3 · p. 7

4.4 Specialised Islands

• Eight islands begin with prompts centered on different construction approaches; two additional roles are cold-start construction and Toolkit-independent invention.Programs migrate every six generations, and a new island is seeded from an archived program after six generations without score improvement.Source: §4.4 · pp. 7–8

4.5 The Toolkit

• The Toolkit supplies 87 hand-written construction and search functions that generated programs can combine, while rejecting programs that merely call one strategy.Its functions span search heuristics and algebraic constructions, organized into six family cores.Source: §4.5 · p. 8

5.1 Choosing Target Parameters (n, k): Human Intuition

• Targets were chosen outside the search loop using open bounds as an initial filter, distance plateaus, and factorization hints for quasi-cyclic starting points.The authors note that a large bound gap can reflect a loose upper bound rather than a weak construction.Source: §5.1 · pp. 8–9

5.2 New Records

• Seven new codes improve CodeTables lower bounds, and explicit derivations extend improvements to 22 entries, with gains up to three.The gains are measured against the previous lower bounds in the 25 September 2026 CodeTables snapshot.Source: §5.2 · p. 9, Table 2 · p. 9
• The reported minimum distances were verified with SageMath and Magma, and the constructions were independently checked and accepted for CodeTables.The live tables had not yet been updated; the comparisons use the bounds listed on 24 September 2026.Source: §5.2 · p. 9

5.3 Structural Advantages of Our Codes

• A pure double-circulant [50, 25, 10] construction matches the best-known lower bound, illustrating that the search can find concise, reproducible codes without improving distance.Its generator matrix is [I25 | A], with A a 25 × 25 circulant matrix.Source: §5.3 · p. 9
• At (n, k) = (172, 21), LinCodeEvolve reaches distance 66 from a quasi-cyclic [170, 21, 64] core, versus distance 65 for the best directly prompted code in the comparison.The construction adds two coordinates using Construction X.Source: §5.3 · pp. 9–10
• Figure 3 covers lengths 171–191, encoding minimum distance and gain in its cells and identifying parent codes by outlines; the length-200 construction is outside its range.Source: §5.2 · p. 9, Figure 3 · p. 10
• At (200, 21), both approaches reach distance 77, but the LinCodeEvolve code has fewer codewords of weight at most 78 and yields a parity extension with 264 minimum-weight codewords versus 303.The two codes are inequivalent and have different weight distributions.Source: §5.3 · p. 10
• The framework preserves verified candidates and uses exact evaluations to guide proposals, providing a systematic search process across parameter pairs without a new prompt for each target.Source: §5.3 · p. 10

6 Conclusion

• Seven parent codes extend through code modification techniques to improvements for 22 parameter pairs.The approach is limited to binary codes in this work; q-ary use requires an exact minimum-distance evaluator over Fq, with feasible dimensions correspondingly smaller because evaluation scales as q^k rather than 2^k.Source: §6 · p. 10
• Evaluation time scales exponentially with code dimension, although longer codes remain inexpensive to evaluate when k is fixed.CodeTables’ binary entries currently stop at length 256, making it harder to determine whether a longer code beats the best-known code of the same length and dimension.Source: §6 · p. 10

7 Resource usage

• Each experiment took 3–4 hours on average using a single 80GB H100.The hardware was on the server of EPFL’s Mathematical Data Science laboratory.Source: §7 · p. 11

9 LLM Usage Statement

• LLMs assisted with writing, framework ideation, citation discovery, and manuscript drafting, while authors verified citations and reviewed and revised drafted sections.The authors state they did not use LLMs to generate ideas or strategies for applying the framework beyond the framework itself.Source: §9 · p. 11

A Explicit constructions

• Over F2, the construction uses a divisor h of x^m − 1 of degree k, g = (x^m − 1)/h, and polynomials f1 = 1, f2, …, fℓ to form a quasi-cyclic code of length mℓ, index ℓ, and dimension k.Source: A Explicit constructions · p. 14
• Tail coordinates are inner products ⟨ci, r⟩, where r is derived from b modulo x^5 − 1 and each pattern ci is printed as a bit string.Source: A Explicit constructions · p. 14
• A_77 = 25, versus A_77 = 75 for the [200, 21, 77] code obtained by direct prompting.Source: A Explicit constructions · p. 16
• For the [50, 25] double-circulant code, the generator matrix is [I25 | A], with A’s first row given by the coefficient vector of f2.Source: A Explicit constructions · p. 16
• For [50, 25], d = 10 is the best-known minimum distance, and A_10 = 125.Source: A Explicit constructions · p. 16

• For each improved entry, Table 3 reports the prior best minimum distance, the released code’s minimum distance, and its minimum-weight-codeword count A_d.Source: Table 3 · p. 17