Coding Agents for Coding Theory

Abraham Yeung

cs.ITSep 30, 2026

Coding Agents for Coding Theory

Authors: Abraham Yeung

Organizations: Stanford University

Abstract

We spent five weeks using an LLM coding agent on open problems in coding theory: finding large sets of four-letter words, such as DNA barcodes, that stay far apart in edit distance. The agent wrote the verifiers and search code; a human chose the problem and set the verification protocol. Restricting the search to codes with a prescribed symmetry, a classical technique, shrank the problem about fourfold and raised the best known code of length 6 and minimum edit distance 3 from 114 to 120 words ( $E_4(6,3) \geq 120$ ). The same pipeline improved twelve further lower bounds at lengths 6 to 9 and distances 3 to 6. We give the failures equal space. Our own search stopped at 116 and recorded the last symmetry class as topping out at 112; a second agent session, running the same search with a better operator, found the 120. A later verdict that the method did not carry over to length 7 was wrong for the same reason, and an earlier instance cost three weeks. Each time, an intermediate result was written down, never rechecked, and treated as a fact that ruled out further search. Checking final outputs, as our protocol required, does not catch such errors.

Figures & tables

	the three runs				operator vs. budget
	run	core-min	best	calib.	budget	calib.
1	original operator	0 6	100	0 99	00 6 (broken op.)	0 99
2	repaired operator	60	112	110	00 6	109
3	later sweep, same op.	20	116	109	0 15	109
					0 20	109
					0 60	110

Table 1: Calibration across three runs, and (right) the compute-response of the repaired operator, nearly flat over

6

–

60

core-min; the

150

row is our earlier raw-graph local search, for reference only.

cell	published	new lower bound	class	orbits	seeds
$E_{4}(6,3)$	114–176	120	$V_{4}$ (free)	1021	8/96 at 1 min
$E_{4}(7,3)$	356–614	364	$C_{3}\times C_{2}$	2218	2/26 at 2 min
$E_{4}(6,4)$	28–32	30	diagonal, order 4, optimum	518	3/3 at 26 s
$E_{4}(7,4)$	65–128	72	diagonal, order 8	1277	11/11 at 1–2 min
$E_{4}(8,3)$	1132–2340	1148	$V_{4}$ (free)	16381	1/20 at 10 min
$E_{4}(9,3)$	3451–9360	3760	diagonal $C_{4}$ (free)	65531	ReduMIS, 2/7 at 15–30 min

Table 2: Every lower bound this project improved, with a symmetry class containing the record (Appendix C gives each code’s full stabiliser), the usable-orbit count of that class, and how many seeds at the stated budget reached the value (C operator unless marked ReduMIS). The four bounds above the rule were improved first; the rest came from the same pipeline extended further, with

n\geq 8

built by a C orbit-graph builder validated edge-for-edge against the Python one. Four values are class optima as reported by exact solvers (

(6,4)

by MaxSAT, the others by maximum clique of the compatibility graph); none has a checked certificate.

Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

Decision or component	Source
Problem: open cells of the quaternary edit-metric table	Human
Protocol: verifier-first rules and escalation order	Human
Redirects between sessions	Human
Prescribed-symmetry search, a classical method [ 4 ]	Agent, within the protocol’s escalation order, which as shipped lists it second; we cannot date that entry against the agent’s first use
Verifiers, search code, orbit-graph builders, and C implementations of the ARW operator and NuMVC	Agent
Recorded conclusions, including the $112$ ceiling and “did not transfer”	Agent

Appendix

Table 3

Figure 1: When each record was set, by calendar day, from the dated entries in the project notes ( notes/sota.md , in the supplement). This is calendar time, not machine time: run records lack consistent timestamps and compute fields, so they cannot be placed on a machine-time axis. (a) Our

E_{4}(6,3)

records against the published

114

; the vertical line marks the sweep of Section 5 . (b) Cells where we held a bound above the published one, at the end of each day. Twelve of the thirteen records date from the last two days, once the ARW operator and the C orbit-graph builder were in place.

Explore similar work

Evolving Towards Better Codes: LLM-Guided Search for High-Distance Binary Linear Codes
Sep 29, 2026Amal Seddas, Vladyslav Shashkov, Maryna Viazovska +1Evolutionary Search Source-Channel Coding
EPFL
Evolutionary Discovery of Bivariate Bicycle Codes with LLM-Guided Search
Jun 1, 2026Juan Cruz-Benito, Andrew W. Cross, David Kremer +1Quantum Error Correction Quantum Annealing
IBM Research, IBM T. J. Watson Research Center, NY, USA
Multi-agent discovery of practical quantum LDPC codes
Aug 10, 2026Dongheng Qian, Tianyi LiQuantum Error Correction Source-Channel Coding
State Key Laboratory of Surface Physics and Department of Physics, Fudan University, Shanghai 200433, China · Shanghai Research Center for Quantum Sciences, Shanghai 201315, China · University of Wisconsin–Madison, Madison, Wisconsin 53706, USA

Sep 29, 2026, cs.ITJ/K move · Enter open · S save

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

Amal Seddas, Vladyslav Shashkov, Maryna Viazovska, Emmanuel Abbe

EPFL

Evolutionary Search Source-Channel Coding Bits Code Optimization Alphaevolve

Open paper AskPDF arXiv

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 LinCodeEvolve, 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. LinCodeEvolve discovers seven record-breaking codes,

[172,21,66]

[173,20,68]

[176,21,68]

[181,21,70]

[184,21,72]

[189,22,72]

and

[200,21,77]

, six of which have concise quasi-cyclic descriptions. With standard code modification techniques, they improve

22

entries of the tables. Every code is verified by exhaustive enumeration. These results suggest that LLM-guided search can help find improved codes and complement existing methods in coding theory.

Abstract

Explore similar work

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

Evolutionary Discovery of Bivariate Bicycle Codes with LLM-Guided Search

Multi-agent discovery of practical quantum LDPC codes