PaperlayerView exact revision on arXiv

Source-linked AI summary

Coding Agents for Coding Theory

Abraham Yeung

arXiv:2609.39081v1cs.ITcs.AIcs.LGmath.IT

TL;DR

Finding large edit-distance-separated sets of four-letter words is a hard combinatorial search problem, and final-output verification does not catch incorrect intermediate conclusions. This paper uses an LLM coding agent with prescribed-symmetry search and reports improved coding-theory lower bounds, including a length-6 code of 120 words.

  • Problem

    Finding large sets of four-letter words with large minimum edit distance requires searching a difficult combinatorial space, while intermediate search conclusions can go unchecked.

    Source: §1 · p. 1

  • Method

    An LLM coding agent implemented verifiers and search code, while humans set the protocol; the search used prescribed symmetry and independent verification.

    Source: §1 · p. 1, §2 · p. 2

  • Results

    120 words raise the length-6, distance-3 quaternary-code lower bound from 114, and twelve further lower bounds improved at lengths 6–9 and distances up to 6.

    Source: §1 · p. 1

  • Takeaways & Limitations

    Verifier-first checks of final outputs do not catch intermediate-state errors that can steer later search away from improvements.

    Source: §7 · p. 5

    This is one project in one problem family with one supervisor and no cross-project comparison, and the authors cannot isolate the agent’s contribution from a conventional pipeline.

    Source: §6 · p. 5

Abstract

from arXiv · show

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.

1 Introduction

A five-week project used an LLM coding agent to improve coding-theory bounds, while revealing that unverified intermediate conclusions can redirect a search and conceal improvements. Its length-6 code raises the reported lower bound from 114 to 120, with further bounds improved and final constructions independently checked.

Motivation

  • The project shows that checking final constructions does not verify intermediate search conclusions, which can hide genuine improvements for weeks.The project gave the failures equal space because they inform how an agent should be supervised.Source: §1 · p. 1

The results

  • 120 words raise the length-6, distance-3 quaternary-code lower bound from 114, the earlier lower bound, and exceed the recent LLM-guided search’s 113.The code is a single-edit-correcting DNA barcode set, found by searching Klein-four-group-invariant codes on a 4096-vertex confusability graph.Source: §1 · p. 1
  • Twelve further lower bounds improved at lengths 6–9 and distances up to 6, and fresh-process reimplementations verified minimum distance 3 with no colliding edit-balls.The confusability graph was differentially tested on all 8,386,560 vertex pairs and reproduced published entries.Source: §1 · p. 1

2 Setup

The project formulated edit-distance code search as a maximum-independent-set problem and used an agent to implement verifiers and search code under a human-set protocol. That protocol checked outputs, but intermediate-state errors remained consequential.

Problem formulation

  • At length 6 and distance 3, maximizing code size is maximum independent set on a 4096-vertex confusability graph with 392,358 edges; ReduMIS plateaus at 113.Adjacent vertices represent words whose edit distance is less than the required minimum.Source: §2 · p. 2

Agent and protocol

  • The agent implemented verifiers and search code and drove off-the-shelf solvers, while a human chose the problem, set the protocol, and redirected sessions.The verifier-first protocol required independent representations, corrupted-object tests before search, reproduction of known values, and fresh-process re-verification of saved bounds.Source: §2 · p. 2

Related work

  • Output checks miss errors in intermediate summaries and state, the failure that cost the project three weeks.Standard known-answer, metamorphic, and differential tests were applied to outputs, not that intermediate state.Source: §2 · p. 2

3 What worked

Prescribed symmetry reduced the search space, but the initial sweep missed a 120-word code because its sampling and operator were inadequate. Calibration checks and compute-aware comparisons offer ways to detect some weak searches, but not all.

Prescribed symmetry

  • Prescribed automorphism search reduces the length-6 search from 4096 words to 1021 usable orbits in each of three free order-4 classes, whose invariant code sizes are multiples of four.Thus there is no invariant code size between 116 and 120 in those classes.Source: §3 · p. 2

What our search missed

  • The stronger ARW operator found 120 in two of six seeds on the same orbit graph, while the original four-seed sweep’s claim that the class topped out at 112 was wrong.The original operator later returned 116 on five of ten seeds; the stronger operator reached 116 on every seed and 120 on two.Source: §3 · pp. 2–3

Instance reduction

  • The orbit reduction lifted all three tested operators to 116, but reaching 120 required a stronger operator on the reduced instance; operator rankings changed at lengths 8 and 9.At length 8 ReduMIS reached 1124–1132 against the C operator’s 1148; at length 9 it reached 3760 against 3724.Source: §3 · p. 3

Calibration cells

  • A calibration cell can expose a broken solver, but the winning-class sweep passed calibration despite being under-budgeted.The unrestricted problem served as the reference; a separate sweep scored 99 where 113 was attainable and was discarded.Source: §3 · p. 3

Decision rule

  • Judging a run against a compute-response curve avoids a fixed cutoff, but the example curve used four runs, two sharing configurations with runs being judged.The repaired operator scored 109 at six core-minutes and 110 at sixty, so tenfold more compute bought one codeword.Source: §3 · p. 3

Cheaper calibration variant

  • Conjugate subgroups define isomorphic problems that must have equal optima, so disagreement across those cells flags a solver issue without requiring a known answer.One run returned 88, 87, 86, 84, 88, and 83 across six isomorphic problems in one class.Source: §3 · p. 3

4 Where it did not work

The apparent failure to transfer prescribed-symmetry search to length 7 was overturned by further runs, and the pipeline also improved bounds at other distances. Construction and certification tools played different roles.

Length 7

  • On the same orbit graphs, the C operator returned 358 on both ten-minute order-6 seeds previously giving 355, and 359 in the reversal-only class; three further fifteen-minute order-6 seeds all gave 355.Source: §4 · p. 4

Other distances

  • The general-distance pipeline reproduced four published cells exactly, found 30 for E4(6, 4) and 72 for E4(7, 4), and extended to lengths 7–9 and distances up to 6.The winning symmetry class differed by cell; NuMVC trailed the other two operators throughout.Source: §4 · p. 4

SAT and ILP

  • Heuristic local search built every construction, while formal methods produced every checked certificate; the four Table 2 class optima lacked checked certificates.SAT returned UNKNOWN on known-feasible instances, and the ILP produced unconverged incumbents for these cells.Source: §4 · p. 4, Table 2 · p. 4

5 The most expensive error

A sweep presented 112 as the best code across all subgroups, but its search omitted classes and its summary hid unproven results. Rechecking later exposed errors that had narrowed the search and delayed the 120-word bound.

5 The most expensive error

  • 112 was reported as the best code across all subgroups, although the search covered only product-form classes and skipped 15 of 60 parameterisation cells.A later 116-word code belonged to a diagonal class the parameterisation could not express.Source: §5 · p. 4
  • 100, 92, and 8 were reported for conjugate cells despite unproven MILP incumbents; the A4-invariant optimum is 112, but the claim of searching all subgroups was false.A conjugacy check would have flagged the spread, but its warning was absent from the human-readable summary.Source: §5 · pp. 4–5
  • Rechecking settled conclusions and recording unproven solver output as unknown are proposed fixes; the protocol had no such rule until 7 September.The first correction was also incomplete: it enumerated 30 of 33 classes and was caught by separate review sessions.Source: §5 · p. 5

6 Limitations

The paper is a single case study, and its controls do not isolate the agent’s contribution from conventional search. Its run records and calibration evidence are limited, and the reported bounds remain unverified heuristic claims.

6 Limitations

  • The study covers one project, problem family, and human supervisor, with no cross-project comparison or clean separation of agent contribution from conventional search.Only the operator comparison and NuMVC run serve as controls; the key algorithmic components predate LLMs.Source: §6 · p. 5
  • About 130 core-hours were recorded on one laptop, but session counts, API costs, human redirects, and intermediate conclusions were not logged.The calibration rule has no fixed tolerance, has only been tried on Table 1 runs, and the proposed remedies are untested.Source: §6 · p. 5
  • Every result is an improved lower bound, no upper bound changed, and the incumbents are unverified heuristic claims whose codeword lists were not published.The logs are self-reported, though the supplement includes the codes, verifiers, defective sweep, protocol, and run records.Source: §6 · p. 5

7 Conclusion

The bounds come from classical prescribed-automorphism search, while the paper’s AI-methodology contribution is its analysis of how recorded conclusions hid results. The authors argue that final-output verification misses intermediate state that directs later search.

7 Conclusion

  • The mathematics producing the bounds is classical prescribed-automorphism search, and the strongest operator and symmetry class varied across (n, d).The free action fixed sizes at multiples of four without causing the escape from the incumbent.Source: §7 · p. 5
  • Three recorded conclusions were never rechecked and hid answers: dropped solver status, a four-seed result treated as a class limit, and a mistaken transfer verdict attributed to the method.The last verdict was a property of the operator.Source: §7 · p. 5
  • Final-output verification catches errors in outputs, not intermediate state that determines which outputs to pursue; the authors expect this gap to matter more as agents run longer.The failure analysis, rather than a new algorithmic component, is the stated AI-methodology contribution.Source: §7 · p. 5

A Who proposed what

The project notes assign problem choice and protocol to the human, while the agent handled implementation and search; an independent second session found the 120-word code.

A Who proposed what

  • The human chose the open cells and set the verifier-first protocol, then redirected work between sessions.The agent worked within the protocol’s escalation order, though the notes cannot date its first use of prescribed symmetry against the protocol entry.Source: A Who proposed what · p. 6
  • The main agent wrote verifiers, search code, orbit-graph builders, and C implementations of ARW and NuMVC, and recorded conclusions including the 112 ceiling and “did not transfer.”The notes attribute the prescribed-symmetry search to the agent within the human-set protocol.Source: A Who proposed what · p. 6
  • The paper’s own ARW implementation on the n = 6 orbit graph found 120, while its first correction enumerated only 30 of 33 classes.A DRAT proof showed that the A4-invariant optimum is 112.Source: A Who proposed what · p. 6

B Timeline

Figure 1 dates records by calendar day, not machine time. It shows the E4(6,3) record trajectory and daily held-bound cells, with most records arriving in the final two days.

  • Twelve of thirteen records date from the last two days, after the ARW operator and C orbit-graph builder were in place.Source: Figure 1 · p. 7
  • Panel (a) compares E4(6,3) records with the published 114 and marks the Section 5 sweep.Source: Figure 1 · p. 7
  • Panel (b) tracks, at each day's end, cells where the held bound exceeded the published one.The timeline uses calendar dates because run records lack consistent timestamps and compute fields.Source: Figure 1 · p. 7

C The thirteen codes

The section lists thirteen codes, including E4(6,3) ≥120, and states that each list was re-verified from the definition in a fresh process.

Loading 2609.39081v1…