Learning Program Synthesis for Integer Sequences from Scratch

Thibault Gauthier, Josef UrbanAAAI 2023 · DOI

Abstract

Researchers have developed a self-learning system that synthesizes programs for integer sequences from scratch, without any human-written training examples. By combining a tree search with a policy-guided neural network, the system "rediscovered" programs for nearly 28,000 sequences in the On-Line Encyclopedia of Integer Sequences (OEIS), including complex formulas for primes and Catalan numbers.

Introduction

Mathematics is fundamentally the study of patterns, with integer sequences—such as the Fibonacci sequence or the primes—serving as the bedrock of these patterns. The On-Line Encyclopedia of Integer Sequences (OEIS) is a massive repository containing over 350,000 such sequences. While many have known formulas, discovering a concise, computational "explanation" for a new sequence remains a significant challenge for both human mathematicians and automated systems.

Traditional program synthesis—the automatic generation of code to satisfy a specification—typically relies on large datasets of human-written code. This research introduces a system that tackles the challenge of learning from scratch. The goal is to build a system that starts with zero knowledge of how to solve these sequences and iteratively teaches itself by exploring a simple programming language.

Methodology

The researchers developed a self-learning loop consisting of three primary phases: Generation, Testing, and Training.

The Domain-Specific Language (DSL)

The system operates within a simple DSL containing basic arithmetic operations (+, -, *, div, mod) and higher-order constructs like loop, loop2 (for recurrence), and compr (a set-comprehension-like operator). This language is Turing-complete, allowing for the representation of complex mathematical logic. Programs are represented in Reverse Polish Notation (RPN), which simplifies the stack-based execution model.

To navigate the vast search space of possible programs, the system uses a Tree Neural Network (TNN) to decide which operator to add next. TNNs are uniquely suited for this task as they can process the tree-like structure of mathematical expressions directly. The search process is visualized as a tree where each node represents a partial program state.

Figure 2: Illustration of the program construction process as a tree search, where each node represents a partial program state.

Hindsight Experience Replay and Occam’s Razor

A key innovation is the use of Hindsight Experience Replay. If the system attempts to solve Sequence A but generates Sequence B instead, it records this as a "success" for Sequence B. This maximizes the utility of every search attempt. Furthermore, the system applies Occam’s Razor by always selecting the smallest program that solves a given sequence, favoring simple, generalizable explanations over complex, "overfitted" ones.

Key Results and Insights

The system demonstrated a remarkable ability to bootstrap mathematical knowledge from initial randomness. In its first iteration ("Generation 0"), it found only 993 solutions. However, by training on these initial successes, the neural network learned statistical correlations that allowed it to find over 8,000 more in the subsequent iteration.

Figure 4: The cumulative number of unique OEIS sequences solved increases significantly across successive generations of self-learning.

By the end of the full-scale run, the system synthesized programs for 27,987 sequences. Notably, it "rediscovered" complex mathematical concepts, such as a variation of Wilson’s Theorem for identifying primes and efficient linear-time algorithms for Fibonacci numbers.

Generalization and Efficiency

The synthesized programs showed high predictive power: over 92% correctly predicted the next 100 terms of their respective sequences, despite being trained only on the initial segments. Remarkably, the entire process required less than 100 CPU days and used no GPUs, highlighting its efficiency compared to large-scale Transformer-based models.

Discussion and Future Work

While successful, the system faces computational limits; some complex programs (like prime generators) were synthesized but exceeded execution time limits during testing. Future improvements could involve integrating automated theorem provers to formally verify that a synthesized program matches the official mathematical definition of a sequence, moving beyond empirical testing. Additionally, expanding the search bias to handle logic beyond primitive recursion remains an open challenge for future research.

Summary updated

BibTeX
@inproceedings{gauthier2023learning,
  author = {Thibault Gauthier and Josef Urban},
  title = {{Learning Program Synthesis for Integer Sequences from Scratch}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.1609/aaai.v37i6.25930},
}
Figure