Symbolic metaprogram search improves learning efficiency and explains rule learning in humans

Joshua Rule, Steven T. Piantadosi, Andrew Cropper, Kevin Ellis, Maxwell Nye, Joshua B. TenenbaumNature Communications 2024 · DOI

Abstract

Throughout their lives, humans seem to learn a variety of rules for things like applying category labels, following procedures, and explaining causal relationships. These rules are often algorithmically rich but are nonetheless acquired with minimal data and computation. Symbolic models based on program learning successfully explain rule-learning in many domains, but performance degrades quickly as program complexity increases. It remains unclear how to scale symbolic rule-learning methods to model human performance in challenging domains. Here we show that symbolic search over the space of metaprograms-programs that revise programs-dramatically improves learning efficiency. On a behavioral benchmark of 100 algorithmically rich rules, this approach fits human learning more accurately than alternative models while also using orders of magnitude less search. The computation required to match median human performance is consistent with conservative estimates of human thinking time. Our results suggest that metaprogram-like representations may help human learners to efficiently acquire rules.

Introduction

Humans possess a remarkable ability to learn complex, algorithmic rules from just a few examples. In contrast, traditional symbolic AI models often struggle with the "combinatorial explosion" of search when faced with high-complexity rules. This paper addresses the Hard Problem of Search: program induction—finding a snippet of code to explain data—becomes exponentially more difficult as program length increases. While symbolic models offer interpretability and data efficiency, they lack the scalability to match human performance within a realistic computational budget. The authors introduce the MetaProgram Learner (MPL) to bridge this gap by searching for metaprograms—programs that construct or revise other programs—rather than searching for final rules directly.

Methods

The MetaProgram Learner (MPL) shifts the search space from object-level programs to metaprograms. Instead of basic operators, MPL utilizes metaprimitives that represent higher-order reasoning strategies.

Overview of the MetaProgram Learner (MPL) framework, illustrating metaprimitives like AntiUnify and Recurse.

Key components include:

  • Metaprimitives: Operators such as AntiUnify (abstracting common structures across examples) and Recurse (decomposing problems recursively) allow the model to "evolve" solutions.
  • Bayesian Inference: MPL employs Markov Chain Monte Carlo (MCMC) to sample from a posterior distribution, balancing metaprogram simplicity (prior) with data fit (likelihood).
  • Benchmark: The model was evaluated on a new behavioral benchmark of 100 algorithmically rich list-processing functions. Human data from 389 participants established the ground truth for learning difficulty and accuracy.

Results

The researchers compared MPL against several baselines, including object-level search (Fleet), exhaustive search (Enumerate), Inductive Logic Programming (Metagol), and neural models (RobustFill, Codex).

Comparison of learning curves across different models. MPL matches human performance (shaded gray area) more efficiently than baselines.
  • Accuracy and Efficiency: Both MPL and Fleet (at 500k search steps) matched human accuracy. However, when the search budget was limited to a "human-scale" of 5,000 steps, MPL retained over 84% of its performance, while Fleet's performance collapsed. This budget fits within the timeframe of human thought (seconds to minutes).
  • Human Fit: MPL’s learning curves closely mirrored human behavior, particularly in identifying "hard" problems where humans also struggle, such as complex recursion without clear structural cues.
  • Reasoning vs. Guessing: By treating reasoning as a first-class citizen, MPL prunes the search space effectively. For instance, AntiUnify allows the model to ignore branches that do not match observed data patterns.
  • LLM Performance: While OpenAI’s Codex succeeded on simpler tasks, it failed to match human performance on algorithmically rich rules, highlighting a deficiency in deep symbolic reasoning compared to humans.

Discussion

MPL demonstrates that metaprogramming can significantly improve search efficiency in symbolic AI, aligning model performance with human cognitive constraints. However, the model's success relies on a predefined library of metaprimitives. Future research should explore how these reasoning strategies are acquired and whether this framework scales to other domains like visual concept learning or causal physics. Integrating neural "intuition" to guide metaprogram proposals and enabling the model to discover new metaprimitives ("learning to learn") represent promising future directions.

Summary updated

Abstract

Throughout their lives, humans seem to learn a variety of rules for things like applying category labels, following procedures, and explaining causal relationships. These rules are often algorithmically rich but are nonetheless acquired with minimal data and computation. Symbolic models based on program learning successfully explain rule-learning in many domains, but performance degrades quickly as program complexity increases. It remains unclear how to scale symbolic rule-learning methods to model human performance in challenging domains. Here we show that symbolic search over the space of metaprograms-programs that revise programs-dramatically improves learning efficiency. On a behavioral benchmark of 100 algorithmically rich rules, this approach fits human learning more accurately than alternative models while also using orders of magnitude less search. The computation required to match median human performance is consistent with conservative estimates of human thinking time. Our results suggest that metaprogram-like representations may help human learners to efficiently acquire rules.
BibTeX
@inproceedings{rule2024symbolic,
  author = {Joshua Rule and Steven T. Piantadosi and Andrew Cropper and Kevin Ellis and Maxwell Nye and Joshua B. Tenenbaum},
  title = {{Symbolic metaprogram search improves learning efficiency and explains rule learning in humans}},
  booktitle = {Nature Communications},
  year = {2024},
  doi = {10.1038/s41467-024-50966-x},
}
Figure