Simplicity Bias for Generalizable Program Synthesis

21 concepts12 papers1 proposal

When we ask an AI or an automated synthesizer to generate code from a few examples, we run into a fundamental challenge: code is incredibly expressive. If a synthesis engine is given complete freedom, it will often find a convoluted, overly specific program that perfectly satisfies the provided test cases but fails completely on unseen data.

In program synthesis, this is known as the overfitting problem. To solve it, researchers across various domains have converged on a powerful idea: enforcing a strict simplicity bias. By forcing the synthesis engine to find the most compact, parsimonious program possible, we turn syntactic minimality into a highly effective regularizer.

The Overfitting Paradox: More is Less

In traditional machine learning, overfitting happens when a model has too many parameters and memorizes noise. In program synthesis, a parallel and often more severe paradox occurs. As Padhi et al. demonstrated, providing a synthesizer with a more expressive grammar can actually cause it to fail on problems it could previously solve. This happens because an unconstrained search space allows the tool to find "spurious" programs—complex, messy solutions that satisfy the immediate constraints through arbitrary case-splitting or hardcoded logic rather than discovering the true underlying algorithm.

Without an explicit preference for simplicity, synthesizers naturally generate code that deviates from human intent. For instance, in sketch-based program synthesis for object-oriented languages, Jeon et al. observed that incorporating a minimization function is essential to prevent the solver from constructing overly complex state machines that only fit specific behavioral requirements.

Why Syntactic Minimality Drives Generalization

Why does minimizing the number of instructions, lines, or nodes in a program guarantee better generalization? The answer lies in the principle of parsimony, or Occam's Razor.

A short program has a limited "information budget." It simply does not have enough syntactic space to build an exhaustive lookup table or chain together dozens of highly specific conditional branches. To satisfy the input-output constraints within a tight structural budget, the synthesizer is forced to discard superficial patterns and uncover the fundamental generative logic of the problem.

Given Examples: In: 2 -> Out: 4 | In: 3 -> Out: 9

Spurious Overfitted Program (High Complexity):
if input == 2: return 4
elif input == 3: return 9
else: return input + 2  # Fails on unseen data!

Parsimonious Program (Low Complexity):
return input ** 2       # Generalizes perfectly!

This correlation between minimality and generalization holds true across vastly different algorithmic benchmarks. For example, Ferreira et al. showed that by optimizing for minimal syntactic complexity, a system can successfully transition from merely replaying specific execution traces to generating fully generalized automation scripts without requiring negative examples. Similarly, when synthesizing mathematical formulas for infinite integer sequences from scratch, Gauthier et al. found that prioritizing the shortest symbolic representation significantly increases the likelihood that the program correctly predicts unseen terms in the sequence.

Algorithmic Frameworks for Simplicity

Researchers implement this simplicity bias using several distinct mathematical and structural strategies:

1. Minimum Description Length (MDL)

The MDL principle states that the best explanation for a set of data is the one that minimizes the size of the theory plus the size of the data encoded by that theory. In data management, Jin et al. utilize MDL to guide the selection of regular expression transformations, ensuring the synthesized logic generalizes cleanly across distinct data clusters. When reverse-engineering database updates between unaligned table snapshots, Fink et al. apply MDL to penalize exhaustive lookup tables in favor of compact mathematical or logical rules that compress the differences between data states.

2. Bayesian Parsimony Priors

When data is sparse, a simplicity prior can guide a system to learn foundational rules. Ellis et al. combined Bayesian inference with symbolic synthesis to automatically discover the underlying grammar rules of human languages. By using the length of a symbolic program as a proxy for its complexity, their framework penalizes memorized solutions and successfully induces generative, interpretable linguistic theories from only a handful of words.

3. Grammar-Based and Structural Regularization

Instead of filtering out complex programs after they are generated, synthesizers can bake simplicity directly into the search space. The Hybrid Enumeration technique by Padhi et al. forces the synthesizer to exhaustively search through restricted, simpler subgrammars before it is allowed to consider more expressive components. In neuro-symbolic learning from video data, Dang-Nhu incorporated a simplicity prior directly into the symbolic search to penalize complex control structures like loops or conditional branches, ensuring the generated programs remain robust in unseen environments.

If finding any valid program is hard, finding the shortest valid program is even harder. Synthesizers cannot simply look at a program and know if a simpler one exists without searching. To make this computationally tractable, modern frameworks leverage specialized search heuristics:

  • Stochastic Stepping Stones: Rosin developed a delayed-acceptance hillclimbing technique for low-level assembly programs. By constantly biasing the stochastic search toward smaller instruction sequences, the framework bypasses deceptive local optima and leverages parsimony to discover complex looping algorithms (like Comb Sort) from minimal input-output examples.
  • Learning from Partial Solutions: The PROBE system, introduced by Barke et al., learns a probabilistic model of code during the bottom-up enumerative search process. By actively rewarding syntactic patterns found in minimal partial solutions, it avoids unnecessary case-splitting and generates cleaner, more readable code.
  • Few-Shot and Unsupervised Adaptation: A strict simplicity bias is a critical requirement when learning from extreme scarcity. In few-shot semantic parsing, Dan et al. demonstrated that forcing the synthesizer to find the shortest possible logical sub-program allows a model to generalize a novel concept from a single user example. Taking this to the extreme, Segovia-Aguas et al. showed that minimizing the number of program lines allows an off-the-shelf classical planner to automatically discover the underlying logical structures of entire planning domains, effectively framing unsupervised clustering as a minimalist program synthesis task.

By treating code length and syntactic structure not just as stylistic preferences, but as fundamental constraints on information capacity, these diverse frameworks demonstrate that the simplest program is almost always the right one.

Key Foundational Work

JSKETCH: Sketching for Java (2015) — contributed 2 concept elements to this direction.
Unsupervised Classification of Planning Instances (2017) — contributed 2 concept elements to this direction.
History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 12 papers
  2. Version 1 · 2026-10-04 · 26 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_minimum_description_length_principle_min_65b667e8,
  title = {minimum description length principle (minimal program synthesis)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/minimum-description-length-principle-minimal-program-synthesis/rdr_65b667e841be4c8d88d6eb8fe874991f},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 2, frozen text):

@misc{lacuna_minimum_description_length_principle_min_65b667e8_v2,
  title = {minimum description length principle (minimal program synthesis)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/minimum-description-length-principle-minimal-program-synthesis/rdr_65b667e841be4c8d88d6eb8fe874991f/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-21},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake