Neural Language Programming Can Generalize Out of Composition

Artificial intelligence systems are showing promise on difficult tasks such as world modeling and abstract reasoning. A central challenge, however, is whether they can reuse what is learned *compositionally*, i.e., combine familiar operations in novel ways to address previously unseen tasks. We refer to this capability as *out-of-composition* (OOC) generalization, where a learner must recover reusable computational structure from input-output observations without access to the generating programs or a predefined executable language. Neural networks can learn directly from input-output observations, but typically represent the underlying computation implicitly and monolithically. Symbolic program synthesis is explicitly compositional, but assumes a predefined language. *Neural Language Programming* (NeuLP) bridges this gap by learning (1) a language consisting of a codebook of vectors that represent abstract operations, (2) an encoder that constructs a sequence out of that codebook based on input-output pairs from the task at hand, and (3) an interpreter that applies the selected sequence to a novel input. The discrete language is amenable to composition as well as search. Learning such a language requires discovering reusable operations without knowing the complexity of the programs that generated the training data or which learned operations can be trusted. NeuLP addresses the former with a program-space self-curriculum that progresses from shorter to longer programs, and the latter with a Bayesian execution-evidence prior that uses successful executions as evidence of operation reliability. Empirically, across four domains spanning list processing, ARC-AGI-style abstract reasoning, image editing, and cellular automata, we show that NeuLP generalizes to unseen recombinations and compositional depth, outperforming neural program synthesis baselines.