Alien Coding
Thibault Gauthier, Miroslav Olšák, Josef Urban
cs.AI, cs.LG, cs.LO, cs.NE, math.NT
2023-01-27
An NMT model translates OEIS sequences into programs, verified solutions feed back into training: starting from random code, 190 iterations solve 78,118 sequences, 84,587 in total.
The OEIS is an online encyclopedia of integer sequences: 350,000+ entries, each with its terms and a human description, and in about a third of cases a human-written program. The question here is blunt. If a system never sees a line of human code, can it start from random programs and invent generators for these sequences on its own? Automated theorem proving has long focused on loops that learn to guide proof search, while guessing and conjecturing stayed mostly untouched; integer sequences make a clean testbed because any proposed explanation, a program, can be mechanically checked. The same team's earlier system, a tree neural network guided by MCTS, solved 27,987 sequences in 25 iterations. This paper swaps out two core components and pushes the loop much further.
The system runs a three-phase loop: search, check, learn.
The programming language has only 14 tokens, deliberately minimal to avoid human bias, yet Turing-complete thanks to compr, an operator returning the n-th nonnegative integer satisfying a predicate (the µ-operator from recursion theory). Fibonacci is one line, loop2(x+y, x, x, 0, 1); the primes are just a primality predicate fed into compr.
Keeping both the shortest and the fastest solution is the key design choice. A short program can be too slow to verify within the time limit, and an unverifiable program yields no training data. Fast programs, in turn, become building blocks for harder ones, and their best versions keep getting faster over iterations. Late additions: a portfolio of 2-4 models trained on different random subsets, continuous training that reuses the previous iteration's model (over 1.4M steps accumulated), and a switch from a hybrid check to the full slow check.
| Setup | Iterations | Sequences solved |
| Random start | 0 | 3,771 |
| TNN baseline (prior architecture) | 500 | about 5 new per iteration at the end, plateaued |
| nmt0 (single NMT model, 1 month) | 100 | 46,707 |
| nmt1 (model portfolio, 3 months on 4 GPUs) | 190 | 78,118 |
| All runs combined (as of Jan 2023) | — | 84,587 |
Combining models at iteration 21 lifted new solutions per iteration to 687, against 272 for the single model. Switching to the slow check at iteration 159 (45 minutes grows to 6 hours) jumped the per-iteration gain from 178 to 860, mostly programs using compr. At iteration 190, nmt1 still rarely drops below 200 new solutions per iteration, while both the TNN baseline and nmt0 had plateaued.
The generalization test is the most telling. Of the 78,118 solutions, 40,577 sequences have 100 additional terms in their b-files. Among programs that do not time out, 90.57% of the shortest solutions extend correctly, against 77.51% of the fastest; a common failure is leaning on approximations of real numbers such as π. Across all runs the system solved 84,587 sequences, more than three times the 27,987 from the previous work.
This is the learning-search-verification feedback loop demonstrated at scale on a Turing-complete, unbounded task. Self-play environments like Go and Chess cap the expressivity; this language can in principle express arbitrary algorithms.
Every solution is an interpretable symbolic program, mechanically verified. The authors state plainly that the system could not bootstrap itself by directly predicting the next 100 numbers of each sequence; the symbolic form is what makes generalization and self-training possible. The reusable bag of tricks: check every artifact against every target, keep two fitness objectives (short and fast), combine a portfolio of differently trained models with continuous training. The system also grew 20+ definitions of (pseudo-)primes and reinvented pairing functions that pack two variables into one. Honest framing: three months on a 4-GPU server for 78,000 solutions makes this a research apparatus, not a product.
Author-acknowledged: the macro (definition-reuse) experiments are inconclusive, with nmt2 and nmt3 each adding under 2,800 solutions over nmt1, which cuts against DreamCoder-style claims that definitions help; neither run had reached 100 iterations, so that comparison is preliminary. There is no direct comparison with the parallel supervised line of work (test accuracy on 10,000 easy sequences) or with a pretrained-code-model system (11.5% of 10,000 easy sequences); the task settings differ.
Two more caveats from the numbers. "Solved" only means the program reproduces the finite terms listed in the entry; on 100 longer terms, roughly 22% of non-timeout fast solutions disagree, so fitting a prefix is not finding the true explanation. And 84,587 out of 351,663 covers about a quarter of OEIS; the paper does not analyze whether the remaining three quarters are blocked by language expressiveness or by search budget.