Technical Summary: Prospective Compression in Human Abstraction Learning

Problem Statement

The paper addresses a core challenge in program synthesis and cognitive modeling: online library learning. This is the incremental acquisition of reusable abstractions (helpers) under uncertainty about future task demands. Existing computational approaches, such as DreamCoder and Stitch, treat library learning as retrospective compression. These algorithms iteratively discover a library of sub-programs that maximally compress a static corpus of past tasks.

However, the authors argue that real-world learning domains are often non-stationary, where tasks arise from a generative process that evolves over time. In such settings, a learner must decide which abstractions to form based only on tasks seen so far, without knowledge of the full task distribution. The central question is whether human library learning is driven by compressing past data (retrospective) or by anticipating and compressing future tasks (prospective).

Methodology

The Pattern Builder Task (PBT)

To investigate this, the authors utilize the Pattern Builder Task, a visual program synthesis paradigm.

• Domain: Participants reconstruct $10 \times 10$ binary geometric patterns.
• Mechanism: Solutions are expressed as programs composed of a fixed Domain-Specific Language (DSL) containing 6 geometric primitives and 7 transformation operators (3 binary, 4 unary).
• Library Learning: Participants can save any intermediate construction as a "helper." These helpers persist across trials and function as new primitives, allowing for the incremental construction of a reusable library.

Experimental Design

The authors designed two experiments with complementary latent curricula to dissociate between retrospective and prospective compression strategies:

1. Experiment 1 (Sequential Curriculum): Tasks follow an auto-regressive structure where each target is a transformation of a preceding solution. This structure is solvable via retrospective compression, as past solutions directly inform future ones.
2. Experiment 2 (Operator-Group Curriculum): Tasks are organized into groups of four. Within a group, all targets share a common latent sub-program (helper) combined with a fixed set of four distinct operators. Crucially, consecutive trials in a group have low surface similarity, making it difficult to infer the shared structure from immediate past tasks alone. This design requires prospective compression—inferring the latent generative process to anticipate the shared helper for the entire group.

Computational Models

The authors evaluated human behavior against a family of computational models:

1. Baseline (No Library): Exhaustive bottom-up search with no abstraction.
2. Retrospective Compression Models:
   • RC (Retrospective Compression): Greedily selects helpers to maximize compression utility over the corpus of past tasks (similar to DreamCoder).
   • GL (Greedy Library Learning): Selects only the terminal program of the current trial.
   • PL (Probabilistic Library Learning): Stochastically selects sub-programs from the derivation trace.
3. Inductive Bias Models (LLM-based):
   • LLM-PS: Uses a Large Language Model (GPT-5.2) for synthesis based on current task and primitives, capturing structural priors without history.
   • LLM-PS-H: Includes full history of past tasks and solutions in the prompt.
4. Prospective Compression (Normative): A theoretical model that selects helpers to maximize expected compression utility over the entire solution corpus (past and future), conditioned on the observed task distribution.

Metrics

Performance was measured using:

• Step Count: Efficiency of solution construction.
• Library Size: Number of helpers created.
• Corpus Compression Utility: The primary metric, evaluating how well a selected set of $k$ helpers compresses the full (held-out) program corpus, including future tasks.

Key Results

1. Human Efficiency and Library Usage: Participants successfully completed the tasks and consistently created helper libraries. The use of helpers significantly reduced the number of steps required compared to raw primitive solutions, maintaining bounded solution depth even as raw program length grew.
2. Retrospective Models in Experiment 1: In the sequential curriculum, human behavior was well-approximated by the Retrospective Compression (RC) model. Both humans and RC selected helpers that compressed the observed past tasks effectively.
3. Prospective Behavior in Experiment 2: In the operator-group curriculum, retrospective models (RC, GL, PL) and inductive bias models (LLM-PS, LLM-PS-H) failed to select the optimal shared helpers.
   • RC selected helpers that compressed past tasks but missed the latent structure shared across the group.
   • LLM models selected geometrically plausible helpers based on inductive biases but failed to capture the specific shared sub-program required for the group.
   • Human Performance: Human-selected helpers consistently achieved higher corpus compression utility than all computational models in Experiment 2. Human behavior closely tracked the "Oracle" (the optimal set of helpers known with hindsight), indicating that humans successfully inferred the latent generative structure and selected abstractions that would be useful for future tasks.
4. Inadequacy of Existing Accounts: The results demonstrate that human abstraction selection cannot be explained solely by retrospective compression or inductive biases modeled by current LLM-based synthesis.

Key Contributions

1. Experimental Paradigm: The introduction of a controlled paradigm (PBT) with latent curricula specifically designed to dissociate prospective from retrospective compression strategies.
2. Computational Evaluation: A systematic evaluation of a family of models (retrospective compression, inductive bias, and probabilistic strategies) against human behavior in non-stationary settings.
3. Empirical Evidence for Prospective Compression: The first demonstration that human online abstraction learning is driven by prospective compression of the task-generating process. Humans infer latent structure to select abstractions that transfer to future tasks, a capability not captured by existing retrospective algorithms or current LLM-based program synthesis.

Significance and Claims

The paper claims that human abstraction learning is better characterized as prospective compression rather than mere retrospective compression or static inductive bias.

• For Program Synthesis: The authors argue that library learning algorithms must move beyond optimizing for past data compression. To handle non-stationary domains, algorithms should explicitly model the non-stationary task distribution and anticipate future dependencies.
• For Cognitive Science: The findings support the view that abstraction learning is tightly coupled with anticipatory structure modeling. Learners do not just compress experience; they infer how task structures evolve over time to facilitate hierarchical prediction and sequence learning.
• Benchmarking: The Pattern Builder Task is proposed as a candidate benchmark for evaluating prospective abstraction, distinguishing between algorithms that merely solve individual tasks and those that can infer and reuse structure across a temporally evolving task distribution.

The authors remain modest regarding the scope, noting that their study is confined to a constrained visual domain and that future work is needed to formally model the probability distribution of future tasks and perform joint inference over both the library and the latent task-generating process.