# Path-dependent program induction under resource constraints explains human sequence learning

arXiv: https://arxiv.org/abs/2606.20623 · HTML: https://mlsanity.com/paper/2606.20623/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 80 references that are in the map.
- First posted on arXiv 26 May 2026.

## Builds on (most cited first, 10 of 10)

- [Automatic Differentiation Variational Inference](https://mlsanity.com/paper/1603.00788/) (2016)
- [Top-Down Synthesis for Library Learning](https://mlsanity.com/paper/2211.16605/) (2022)
- [Learning abstract structure for drawing by efficient motor program induction](https://mlsanity.com/paper/2008.03519/) (2020)
- [Exploring the hierarchical structure of human plans via program generation](https://mlsanity.com/paper/2311.18644/) (2023)
- [Map Induction: Compositional spatial submap learning for efficient exploration in novel environments](https://mlsanity.com/paper/2110.12301/) (2021)
- [Compositional diversity in visual concept learning](https://mlsanity.com/paper/2305.19374/) (2023)
- [Harmonizing Program Induction with Rate-Distortion Theory](https://mlsanity.com/paper/2405.05294/) (2024)
- [Sequence Generation using Deep Recurrent Networks and Embeddings: A study case in music](https://mlsanity.com/paper/2012.01231/) (2020)
- [New efficient algorithms for multiple change-point detection with kernels](https://mlsanity.com/paper/1710.04556/) (2017)
- [Program-Based Strategy Induction for Reinforcement Learning](https://mlsanity.com/paper/2402.16668/) (2024)

## Built on by (most cited first, 1 of 1)

- [What Is Worth Representing? Representational Empowerment for Continual Model Construction](https://mlsanity.com/paper/2609.02322/) (2026)

## Abstract (arXiv)

How do people build abstract, reusable knowledge from sequential experience under bounded cognitive resources? To answer this question, we integrate rate-distortion theory with recent advances in program induction to describe how prior knowledge shapes which future structures are cheap to encode and easy to discover. We formalize this in a hierarchical Adaptor Grammar (HAG) with distinct local (within-task) and global (across-task) libraries, governed jointly by constraints on memory and computation. In simulations, HAG achieves better rate-distortion trade-offs and stronger generalization than fixed grammars or shallow chunking methods. In an online melodic sequence-learning experiment, participants' recall errors reflected systematic simplifications and reaction times increased at inferred program boundaries. Trial-by-trial fits further showed that hierarchical libraries best explained individual differences in both recall and out-of-sample continuation choices, outperforming all alternative models. These findings cast structured learning as bounded program induction in which the order of experience shapes future abstractions a learner builds.