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

Researchers developed a hierarchical Adaptor Grammar (HAG) model that explains how humans learn abstract patterns from sequential experiences under cognitive constraints. The framework combines rate-distortion theory with program induction to show that learning order influences which abstractions are discovered, with experimental validation from melodic sequence learning tasks demonstrating superior generalization and fit compared to alternative models.

This research addresses a fundamental question in cognitive science: how bounded human minds extract and generalize knowledge from experience. The hierarchical Adaptor Grammar framework bridges theoretical computer science and human cognition by formalizing the intuition that cognitive constraints shape learning trajectories. Rather than treating learning as unlimited optimization, HAG models realistic memory and computational tradeoffs that force prioritization of which patterns to encode.

The work extends prior research in program induction and chunking theory by introducing path-dependency—the critical insight that the sequence of experiences determines which future abstractions become learnable. This explains why human knowledge appears structured and reusable despite resource limitations. The dual-library architecture separating local task-specific learning from global cross-task abstraction mirrors observed human cognition.

Experimental validation through melodic sequence learning provides compelling evidence. Participants' recall errors reflected systematic simplifications predicted by the model, and reaction time increases at program boundaries matched theoretical predictions. Individual differences in learning patterns were better explained by hierarchical libraries than fixed grammars or alternative chunking approaches, suggesting the model captures genuine mechanisms of human learning.

This research has applications across cognitive AI, education, and human-computer interaction. Understanding how bounded learners extract abstractions could improve AI systems designed to learn like humans, optimize educational sequencing for students, and inform interface design. The path-dependent nature of learning has implications for how curricula structure material and how users should be introduced to complex systems.

• →Hierarchical Adaptor Grammar successfully models human learning as bounded program induction constrained by memory and computation
• →Learning order influences which abstractions humans discover, making the discovery process path-dependent rather than optimal
• →Dual-library architecture separating local and global knowledge better explains human generalization than fixed or shallow models
• →Experimental participants' errors and reaction times matched HAG predictions, validating the theoretical framework empirically
• →The framework applies beyond melodic learning to general structured knowledge acquisition under cognitive constraints