Hierarchical Library Learning

45 concepts31 papers1 proposal

Imagine trying to write a complex computer program, discover a law of physics, or plan a long sequence of robotic movements using only the most basic primitives—such as individual bitwise operations, single mathematical symbols, or raw motor voltages. As the target solution grows linearly in length, the search space of possible combinations explodes exponentially. This combinatorial explosion makes direct search for complex concepts computationally intractable.

How do humans bypass this limitation? We do not reason in raw primitives; instead, we build abstractions. We bundle simple steps into a named subroutine, cache it, and then use that subroutine as a single atomic building block to construct even higher-level concepts. This insight forms the foundation of Hierarchical Library Learning, a neurosymbolic paradigm that enables artificial agents to autonomously grow domain-specific languages (DSLs) and solve increasingly complex tasks by treating yesterday's solutions as tomorrow's building blocks.

The Core Mechanism: The Search-and-Compress Loop

At the heart of hierarchical library learning is an iterative loop that alternates between problem-solving and code refactoring. This architecture was formalized in the $EC^2$ framework by Kevin Ellis et al. in Learning Libraries of Subroutines for Neurally-Guided Bayesian Program Induction, and later expanded into a wake-sleep paradigm by Kevin Ellis et al. in DreamCoder: growing generalizable, interpretable knowledge with wake–sleep Bayesian program learning.

The loop operates in three distinct phases:

  1. Search: The system attempts to solve a set of tasks by searching for programs written in its current base language. This search can be guided by neural recognition models, genetic programming, or large language models (LLMs).
  2. Compression: Once a corpus of successful solutions is gathered, a symbolic compression engine analyzes the code. It identifies recurring sub-expressions or structural motifs across different solutions and refactors them into reusable lambda abstractions. As Gabriel Grand et al. demonstrate with the LILO framework in LILO: Learning Interpretable Libraries by Compressing and Documenting Code, this compression reduces the description length of the entire codebase by consolidating redundant logic into a concise set of library functions.
  3. Library Expansion: These newly discovered subroutines are added back into the language as new primitives. Crucially, because the library is hierarchical, new subroutines can be defined in terms of previously learned subroutines, creating a deep vocabulary of abstractions.
   ┌────────────────────────────────────────────────────────┐
   │                                                        │
   ▼                                                        │
[ Search Phase ] ───► [ Successful Programs ] ───► [ Compression Phase ]
   ▲                                                        │
   │                                                        ▼
   └─────────────── [ Expanded Library Primitives ] ────────┘

Why It Works: Shortening the Search Distance

To understand why this loop is so effective, consider the concept of search depth. If a complex concept requires 20 primitive operations to express, a standard search algorithm must explore a tree of depth 20. If the branching factor (the number of available primitives) is $B$, the size of the search space is $B^{20}$, which is completely inaccessible.

However, if the system has already learned and cached intermediate concepts that capture chunks of those operations, the required search depth drops dramatically. In Constructing Deep Concepts through Shallow Search, Bonan Zhao et al. demonstrate that caching successful sub-programs allows cognitive agents to reach deep conceptual insights using only highly restricted, local "shallow searches." By recursively building upon previously validated abstractions, the effective distance to a complex solution is compressed.

This creates a self-reinforcing ratchet effect. As noted by Leopoldo Sarra et al. in Discovering Quantum Circuit Components with Program Synthesis, compressing solutions into reusable components reduces the search depth required for subsequent, more complex tasks. Problems that were previously intractable become reachable within a fixed computational budget because the agent is no longer re-evaluating low-level implementation details from scratch.

Path Dependency and Learning Traps

Because hierarchical library learning relies on building new concepts on top of old ones, the order in which tasks are encountered matters immensely. This phenomenon is known as conceptual bootstrapping.

In a single-author study, Bonan Zhao introduces a computational model using adaptor grammars in A model of conceptual bootstrapping in human cognition, demonstrating that the curriculum fundamentally dictates what is learned. If a system is faced with highly complex data too early, it cannot find any successful solutions to compress, leading to a "learning trap." Conversely, an incremental curriculum allows the system to build a solid foundation of low-level detectors and intermediate subroutines.

This path dependency is a natural consequence of local search. Bonan Zhao et al. expand on this in Local search and the evolution of world models, showing how world models evolve through incremental variation and selective retention, explaining why both human cognition and machine learning systems are sensitive to the historical trajectory of their experiences.

Early work by Steve G. Romaniuk in Learning to Learn: Automatic Adaptation of Learning Bias similarly illustrated that automatically recruiting previously learned features allows a system to adapt its learning bias. This feature reuse produces a counter-intuitive phenomenon: mastering a large, diverse set of problems can actually be faster and more efficient than learning a small subset of those same problems in isolation.

Generalization Across Domains

The power of hierarchical library learning spans a wide array of scientific and engineering domains, proving that the mechanism of "search, compress, and reuse" is a universal tool for complexity management.

Scientific Equation Discovery and Mathematics

In symbolic regression, finding multi-term physical laws is notoriously difficult. Fangzheng Sun et al. develop the Symbolic Physics Learner in Symbolic Physics Learner: Discovering governing equations via Monte Carlo tree search, which extracts successful mathematical sub-expressions and reintroduces them as atomic building blocks to discover complex, multi-term physical equations. Similarly, Yunlun Li et al. introduce RESTART in Robust Equation Structure Learning with Adaptive Refinement, using a persistent library of mathematical motifs to accelerate equation discovery with LLMs. In broader scientific modeling, Jennifer J. Sun et al. highlight in Neurosymbolic Programming for Science how hierarchical primitive discovery allows scientific hypotheses to be represented as interpretable, data-efficient programs.

To prevent search stagnation when discovering new mathematical properties, George Tsoukalas et al. present the FERMAT environment and EvoAbstract algorithm in Learning Interestingness in Automated Mathematical Theory Formation. Their system periodically extracts and names reusable subroutines from successful heuristic programs, preventing performance plateaus and enabling the transition from basic arithmetic operations to sophisticated number-theoretic concepts.

Reinforcement Learning and Robotics

Instead of operating over raw actions or opaque neural policies, agents can distill behavior into symbolic libraries. Manuel Eberhardinger et al. show in Learning of Generalizable and Interpretable Knowledge in Grid-Based Reinforcement Learning Environments that refactoring synthesized programs from agent trajectories uncovers core environmental concepts like spatial relationships. This is echoed by Manuel Eberhardinger et al. in Unveiling the Decision-Making Process in Reinforcement Learning with Genetic Programming, where compressing recurring sub-patterns manages complexity in long-sequence tasks.

In robotics, George Dimitri Konidaris et al. establish a skill-symbol loop in Constructing Abstraction Hierarchies Using a Skill-Symbol Loop, where each new symbolic layer forms a simplified state space that facilitates higher-level skill discovery. For long-horizon robotic tasks, Jesse Zhang et al. introduce the BOSS framework in Bootstrap Your Own Skills: Learning to Solve New Tasks with Large Language Model Guidance, summarizing successful action sequences into higher-level abstractions for autonomous practice.

Interactive Agents and Motor Skills

Hierarchical library learning also powers agents that interact with humans or complex environments. In a single-author paper, Amos Azaria designs LIA in Instructable Intelligent Personal Agent, allowing users to build complex workflows incrementally by referencing previously taught commands as primitive components. To scale up agent capabilities, Jiefu Ou et al. propose WORLDAPIS in WorldAPIs: The World Is Worth How Many APIs? A Thought Experiment, using iterative library bootstrapping to build a massive action vocabulary from web tutorials.

For learning human preferences, Isil Dillig et al. present SYNAPSE in Synapse: Learning Preferential Concepts from Visual Demonstrations, which builds a foundation of reusable predicates to simplify the acquisition of multi-layered user preferences. Finally, in the visual domain, a single-author paper by Lucas Y Tian demonstrates in Learning abstract structure for drawing by efficient motor program induction that compressing simple drawing primitives into complex, reusable motor subroutines enables rapid acquisition of drawing skills for novel shapes.

Key Foundational Work

Learning to Learn: Automatic Adaptation of Learning Bias (1994) — contributed 1 concept elements to this direction.
Verification-based Learning: A Generalized Strategy for Inferring Problem-Reduction Methods (1985) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_hierarchical_library_learning_bb0aed77,
  title = {hierarchical library learning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/hierarchical-library-learning/rdr_bb0aed776ab24befa80d8c42a3ee4f64},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_hierarchical_library_learning_bb0aed77_v1,
  title = {hierarchical library learning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/hierarchical-library-learning/rdr_bb0aed776ab24befa80d8c42a3ee4f64/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake