Path-dependent program induction under resource constraints explains human sequence learning
For cognitive scientists and AI researchers, this work provides a principled account of how resource constraints shape human sequence learning and abstraction.
The authors integrated rate-distortion theory with program induction to model how humans build abstract knowledge from sequences under cognitive constraints. Their hierarchical Adaptor Grammar (HAG) outperformed alternative models in simulations and a melodic sequence-learning experiment, explaining recall errors and reaction times.
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.