Machine learning discovers new champion codes
A GPT-2-style Transformer plus genetic search found at least six new F8 champion codes, with 92.4% test accuracy within ±3 distance units.
Key Findings
Methodology
The paper treats a canonical generator matrix as a sequence, trains a stripped-down GPT-2 Transformer to predict minimum Hamming distance, and uses that prediction as the fitness signal for a genetic algorithm. Expensive Brouwer–Zimmermann (BZ) computations are reserved for promising candidates, creating a prediction–evolution–verification pipeline rather than replacing exact mathematics with a black-box estimate.
Key Results
- The F7 dataset contains 2.7 million examples; balancing produced about 550,000 training examples with a 9:1 split. On roughly 61,000 test cases, MAE was 1.05 and 91.6% of predictions fell within ±3 of the true minimum distance. The genetic search rediscovered champion codes reported by Brown and Kasprzyk.
- The F8 dataset contains 1,584,099 codes, trained in two stages using about 300,000 pre-training examples and a 20,000-example balanced stage. Test MAE was 1.21 with 92.4% accuracy within ±3; more than 700 candidate champions were found, including at least six confirmed new codes.
- Against random search, the genetic algorithm achieved up to a twofold reduction in BZ evaluations in intermediate, sparse regions. F8 searches covered dimensions 3–46, although dimension 30 was excluded because full verification exceeded the computational budget.
Significance
This work turns machine learning into a practical code-construction aid. It targets the NP-hard bottleneck of finding high-distance linear codes at fixed length and dimension by reducing the number of candidates requiring exact evaluation. Importantly, the model can generalise across poorly represented dimensions, helping discover new F8 records. The framework is relevant not only to communications and storage but also to Reed–Muller, BCH, algebraic-geometric, and potentially quantum codes.
Technical Contribution
The central engineering contribution is a closed loop: canonical generator matrices are encoded as sequences; masked self-attention aggregates row information; softmax predicts distance classes; and a genetic algorithm applies stochastic universal sampling, crossover, 10% mutation, and elitist retention of 30 individuals. Fitness is 300+dapprox−|kC−k|, with duplicate suppression. Unlike exhaustive or random BZ search, the method concentrates exact computation on model-ranked candidates.
Novelty
The novelty lies not in inventing Transformers or genetic algorithms separately, but in coupling them for structured code discovery and closing the loop with exact BZ verification. This is especially consequential over F8, where prior enumeration became impractical. The study demonstrates that a learned heuristic can navigate sparse, previously unexplored regions while retaining a mathematically checkable final result.
Limitations
- The predictor inherits the coverage and imbalance of its labelled data. Rare classes are difficult: the F8 model shows larger deviations for d=7, 14, 20, 21, and 28, so promising codes may be under-ranked.
- BZ remains the dominant cost. F8 dimension 30 was not fully run, the search used only one main run, and finding a new champion does not establish global optimality or improve theoretical bounds.
Future Work
The authors propose larger and better-balanced datasets, broader hyperparameter searches, mixed cross-entropy/Wasserstein losses, improved field and row encodings, and systematic embedding design. Faster BZ variants and longer staged F8 searches are also needed. Further work should characterise distance distributions at fixed dimension, tune population and crossover strategies, and transfer the framework to other evolvable code families and quantum codes.
AI Executive Summary
Modern communication depends on error-correcting codes, yet finding the best linear code at a fixed block length and dimension is notoriously difficult. The key quantity, minimum Hamming distance, is expensive to compute exactly with the Brouwer–Zimmermann algorithm. Exhaustive enumeration therefore becomes infeasible precisely where new records are most likely to hide.
He and colleagues propose a prediction–evolution–verification framework. A stripped-down GPT-2 Transformer reads rows of a canonical generator matrix and predicts distance classes. A genetic algorithm then evolves lattice-point sets defining generalised toric codes, using predicted distance as fitness. Only promising candidates receive exact BZ or Magma-based verification. On F7, a 2.7-million-example dataset yielded test MAE 1.05 and 91.6% accuracy within ±3. On F8, test MAE was 1.21 and the corresponding accuracy 92.4%.
The method rediscovered known F7 champions and found over 700 F8 candidates, at least six of which are new champion codes. Relative to random search, it reduced BZ evaluations by up to a factor of two in intermediate sparse regimes. Its broader lesson is methodological: machine learning need not replace proof-oriented computation; it can decide where exact computation is most valuable. Limitations remain—imbalanced data, costly verification, one principal F8 run, and no guarantee of global optimality—but the approach offers a scalable route toward automated code discovery.
Deep Analysis
Background
Linear error-correcting codes protect transmitted and stored information; minimum Hamming distance d controls error detection and correction. Generalised toric codes are generated from lattice-point sets over Fq and have block length n=(q−1)^2. Brown–Kasprzyk classified such codes for q≤7, but extension to F8 failed because candidate enumeration and exact distance computation grow rapidly.
Core Problem
For fixed n and dimension k, the goal is to find a code whose d matches or exceeds the best known record. The search space is enormous, many lattice sets define equivalent codes, and BZ distance evaluation is costly. Champion codes are also sparse at intermediate dimensions, making random search inefficient and data-driven prediction difficult.
Innovation
The paper formulates distance prediction as sequence classification and feeds it directly into evolutionary optimisation. The Transformer learns structural correlations between generator matrices and d; the genetic algorithm explores the evolvable parameter space; BZ supplies exact verification. This division preserves mathematical reliability while reducing unnecessary computation, unlike pure enumeration or unfiltered random search.
Methodology
- �� Construction: a lattice set V defines evaluation vectors and a generator matrix G of length n=(q−1)^2.
- �� Data: F7 has 2.7 million examples, balanced to about 550,000; F8 has 1,584,099 examples, with 300,000 for pre-training and 20,000 for the second stage.
- �� Model: a GPT-2-style classifier uses field embeddings, sinusoidal row positions, two masked-attention blocks, feed-forward layers, and softmax distance classes.
- �� Evolution: population 300, 200 selected parents, crossover, 10% mutation, 30 elites, and 200 generations.
- �� Fitness: 300+dapprox−|kC−k|, with duplicate chromosomes penalised.
- �� Verification: direct BZ checks for F7; F8 first uses Magma’s VerifyMinimumDistanceLowerBound, then full BZ evaluation.
Experiments
Both datasets use 9:1 train/test splits. F7 testing covers about 61,000 examples; F8 uses two-stage evaluation. The genetic search targets dimensions k=3–34 over F7, with 757 runs, and k=3–46 over F8, excluding k=30 because of cost. Metrics are ±3 accuracy, MAE, and MSE. Random search is the principal baseline, compared through the number of BZ evaluations needed to reach champions.
Results
F7 training achieved MAE 1.04 and 91.9% ±3 accuracy; test performance was MAE 1.05 and 91.6%. F8 reached training MAE 1.09 and 93.4%, then test MAE 1.21 and 92.4%. Known F7 champions were rediscovered. F8 produced more than 700 candidates and at least six new champions. Genetic search improved BZ efficiency by up to approximately 2× in intermediate regimes.
Applications
The method can support code design for Wi-Fi, LAN, deep-space links, storage, and other systems where block length, dimension, and field are constrained. It requires a canonical representation, an evolvable parameterisation, and an exact verifier. The same pattern could be adapted to Reed–Muller, BCH, algebraic-geometric, and possibly quantum codes.
Limitations & Outlook
Performance depends on balanced labelled data; rare distance classes are poorly represented. Predictions cannot certify distance, so BZ or Magma remains necessary. The F8 study used one main run, omitted dimension 30, and does not prove global optimality. Future work should expand datasets, accelerate BZ, run longer searches, test uncertainty-aware selection, and perform systematic ablations of encodings, losses, and evolutionary parameters.
Plain Language Accessible to non-experts
Imagine a factory making protective packages for fragile information. Every package has a design made from many small parts, and its quality is measured by how much damage it can survive before the message inside becomes ambiguous. There are so many possible designs that testing every package by actually damaging it would take forever.
The researchers first show a learning machine many packages that have already been tested. Like an experienced inspector, it studies the design and estimates which new packages are likely to be strong. The estimate is not a certificate; it is a useful guess. A team of designers then keeps promising designs, combines pieces from two designs, and randomly changes a few pieces to create the next generation.
Only the most promising packages receive the expensive real damage test. The verified results are added to the experience pool. In this way, learning does not replace careful testing—it decides where careful testing is worth spending time. On one field, the predictions were typically about one distance unit away from the truth; on the larger F8 search, the system found at least six previously unknown record designs.
The approach is powerful because it replaces blind trial-and-error with guided exploration. It can still miss an extremely rare excellent design, however, and it cannot promise that the best possible design has been found.
ELI14 Explained like you're 14
Think of error-correcting codes as armor for messages. If a few pixels of a photo, game save, or text message get flipped during transmission, the armor helps recover the original. A stronger code has a larger “distance,” meaning two different messages are harder to confuse. The problem? There are an absurd number of possible codes, so checking them one by one is like testing every game item in existence.
The researchers trained a Transformer, the same broad family of technology behind modern language models, to look at a code’s structure and guess how strong it is. Then a genetic algorithm acts like a gaming team builder: keep strong designs, mix two designs, randomly modify a part, and repeat. Each round tries to create better code designs.
But guesses are not enough. When the model spots a promising candidate, the Brouwer–Zimmermann algorithm performs the serious check. On F7, the model’s average error was only 1.05 distance units, and 91.6% of test guesses were within three units. On F8, 92.4% met that target.
The exciting part is that the search found at least six new champion codes on F8! Still, it is not a cheat code guaranteeing victory. Rare examples can confuse the model, and exact checking remains slow. It is better understood as a smart treasure map: it tells mathematicians where to dig first.
Glossary
Minimum Hamming distance
The smallest number of positions in which any two distinct codewords differ. It determines how many errors a code can detect or correct.
The Transformer predicts d, while BZ verifies it for candidate champions.
Generalised toric code
A linear code constructed from lattice points and evaluations over a finite field. Its block length is n=(q−1)^2.
It is the structured code family used as the experimental testbed.
Transformer
A neural sequence model based on attention, allowing elements to exchange information. Here, matrix rows are treated as a sequence.
A stripped-down GPT-2 architecture predicts distance classes.
Genetic algorithm
An optimisation method inspired by selection, crossover, and mutation. It searches by repeatedly producing and retaining high-fitness candidates.
It evolves lattice-point sets rather than arbitrary generator matrices.
Brouwer–Zimmermann algorithm
An exact algorithm for computing the minimum distance of a linear code. It is reliable but computationally expensive.
It is used to verify candidates selected by the learned model.
Champion code
A linear code whose minimum distance matches or exceeds the best known value for fixed length and dimension.
Discovering such codes is the paper’s principal objective.
Open Questions Unanswered questions from this research
- 1 The distribution of minimum distances at fixed dimension or lattice-set size is unknown. Without it, the true rarity of champions and the optimal sampling policy remain difficult to quantify.
- 2 Sparse training classes can cause the model to under-rank exceptional codes. Active learning, uncertainty estimates, or targeted data generation may be required for reliable extrapolation.
- 3 A discovered champion is not a proof of global optimality. Stronger mathematical bounds, equivalence analysis, and faster exact distance algorithms are still needed.
Applications
Immediate Applications
Communication and storage code design
Coding theorists can train the predictor on an existing code library, evolve candidates under target length and dimension constraints, and use BZ or Magma for certification. The expected benefit is fewer expensive exact distance evaluations during design exploration.
Automated exploration of new code families
Researchers can replace lattice sets with parameters for Reed–Muller, BCH, or algebraic-geometric codes, provided mutations preserve the family and an exact verifier exists. The framework is most useful when exhaustive enumeration is already impractical.
Long-term Vision
Automated discovery of quantum error-correcting codes
If a quantum-code family admits an evolvable parameter space and tractable verification, the same loop could search for high-distance constructions. Major obstacles include quantum-distance computation, equivalence classes, and much higher verification costs.
Abstract
Linear error-correcting codes form the mathematical backbone of modern digital communication and storage systems, but identifying champion linear codes (linear codes achieving or exceeding the best known minimum Hamming distance) remains challenging. By training a transformer to predict the minimum Hamming distance of a class of linear codes and pairing it with a genetic algorithm over the search space, we develop a novel method for discovering champion codes. This model effectively reduces the search space of linear codes needed to achieve champion codes. Our results present the use of this method in the study and construction of error-correcting codes, applicable to codes such as generalised toric, Reed-Muller, Bose-Chaudhuri-Hocquenghem, algebrogeometric, and potentially quantum codes.