Composed-Program Induction with Latent Program Lattice

Introduction

Compositional reasoning is the process of solving new problems by systematically composing primitive operations into complex transformations. This ability hinges on three key components:

• learning the compositional structure that governs how primitives interact
• inference using this learned structure to generalize from limited examples, and
• abstraction discovery that compresses and refines primitives to accelerate future reasoning.

As the Kaleidoscope Hypothesis (Chollet, 2024) suggests, we focus on realizing the symmetric structure beneath apparent complexity. Building on this view, we propose the Program Lattice Auto Encoder(PLAE). The central idea is to endow the model with a structured latent program space that respects the compositional structure. Drawing on category theory, we design the encoder to be trained to mimic a functor that maps input–output pairs and their transformations into a latent space while preserving their compositional structure. In this space, primitive operations correspond to each latent program basis, and composed programs emerge as integer linear combinations of these bases, forming a latent program lattice. Program induction then reduces to solving a Closest Vector Problem (CVP) (Micciancio and Goldwasser, 2002) which find a vector $v \in L$ such that minimize the distance $\| v - t \|$ where $t \in \R^n$ is arbitrary target vector in lattice $L$. Moreover, abstraction discovery is achieved through lattice reduction (W¨ubben et al., 2011), which refines non-atomic programs into shorter, more orthogonal primitives spanning the same lattice. Lattice program space naturally supports dual-process reasoning (Frankish, 2010). For System-1 inference, PLAE encodes observed input–output pairs, takes their difference as a latent program effect, adds this effect to a new input’s embedding, and decodes—fast, intuitive, approximate. For System-2 inference, PLAE factorizes the same effect into a sequence of basis and executes them stepwise—repeatedly decoding/encoding in a guided “lattice walk” that verifies and refines intermediate states. Both modes arise from the same latent structure, with System-2 improving the basis via lattice reduction and thereby strengthening future System-1 inferences. In this way, PLAE integrates learning, inference, and abstraction into a unified framework for compositional reasoning.

Program Lattice Auto Encoder (PLAE)

Task

Consider a set of m example input-output pairs $T_i = \{ (x_1, y_1), (x_2, y_2), \dots, (x_m, y_m)\}$ where the output object $y$ is generated by applying a consistent program $f_i$ on the corresponding input object $x : \forall (x, y ) \in T_i, f_i(x) = y$. For a new input $x_{m+1}$, the model should predict the corresponding output $y_{m+1}$ that would be generated by applying the same consistent program $f_i$. The program $f_i$ for each task $T_i$ is a composition of programs from a set of $d$ primitive programs $P = \{p_1, p_2, \dots, p_d\}$.

Learning the Compositional Structure (Training)

From given input-output pairs $T_i$, the model can only observe the apparent effect of applying the underlying consistent program. PLAE models this as latent program effect $\mathbf{\Delta}_k$ by embedding each input and output $(x_k, y_k)$ into vectors $(E(x_k), E(y_k))$ with an encoder $E$, and averaging (pair permutation invariant aggregation) the difference vectors.

The underlying programs for the first $d$ tasks are treated as the initial set of primitive programs, and the latent program effects $\bar{\mathbf{\Delta}}_1, \bar{\mathbf{\Delta}}_2, \dots, \bar{\mathbf{\Delta}}_d$ from a latent program basis matrix $B = \begin{bmatrix} \mathbf{p}_1 & \mathbf{p}_2 & \cdots & \mathbf{p}_d\end{bmatrix}$ where $\mathbf{p}_1 = \bar{\mathbf{\Delta}}_1, \mathbf{p}_2 = \bar{\mathbf{\Delta}}_2, \dots, \mathbf{p}_d = \bar{\mathbf{\Delta}}_d$.

Modeling program composition as an integer linear combination of latent program basis, the latent program basis spans a latent program lattice $L$ whose lattice points corresponds to the latent program effects of valid discrete composition of primitive programs.

As a result, an integer vector $\mathbf{z}$ corresponding to a lattice point on this latent program lattice represents how many of each primitive program are composed in the corresponding program.

Since vector addition is commutative while program composition is not, we introduce small perturbations $\varepsilon_{k, t}$ for each basis $\mathbf{p}_k$ at position $t$. These perturbations, bounded by the lattice packing radius, preserve CVP solutions while encoding operation order.

The encoder is parameterized and trained to model the compositional structure as a discrete lattice by minimizing the deviance from the additive structure in latent program space: