Composed Program Induction with Latent Program Lattice

Abstract

Compositional reasoning requires learning structure, inferring programs, and discovering refined primitives. Existing approaches either lack explicit decomposition mechanisms or rely on hand-crafted primitives. We propose the Program Lattice Auto Encoder (PLAE), which learns compositional transformations in a structured latent program space. PLAE trains an encoder where program effects correspond to integer linear combinations of program bases, forming a discrete program lattice. Program induction reduces to solving the Closest Vector Problem (CVP), enabling two complementary inference modes: fast System-1 reasoning via CVP and deliberate System-2 reasoning through stepwise lattice walks with intermediate verification. The framework supports abstraction discovery through lattice reduction, which refines primitive bases to uncover more fundamental components. This work connects neural and symbolic reasoning by providing a mathematically principled framework for compositional domains.