Searching Latent Program Spaces

id:: 2411.08706
Authors:: Clément Bonnet, Matthew V Macfarlane
Published:: 2024-11-13
arXiv:: https://arxiv.org/abs/2411.08706
PDF:: https://arxiv.org/pdf/2411.08706
DOI:: N/A
Journal Reference:: N/A
Primary Category:: cs.LG
Categories:: cs.LG, cs.AI
Comment:: Code available at https://github.com/clement-bonnet/lpn
github_url:: _

abstract

Program synthesis methods aim to automatically generate programs restricted to a language that can explain a given specification of input-output pairs. While purely symbolic approaches suffer from a combinatorial search space, recent methods leverage neural networks to learn distributions over program structures to narrow this search space significantly, enabling more efficient search. However, for challenging problems, it remains difficult to train models to perform program synthesis in one shot, making test-time search essential. Most neural methods lack structured search mechanisms during inference, relying instead on stochastic sampling or gradient updates, which can be inefficient. In this work, we propose the Latent Program Network (LPN), a general algorithm for program induction that learns a distribution over latent programs in a continuous space, enabling efficient search and test-time adaptation. We explore how to train these networks to optimize for test-time computation and demonstrate the use of gradient-based search both during training and at test time. We evaluate LPN on ARC-AGI, a program synthesis benchmark that evaluates performance by generalizing programs to new inputs rather than explaining the underlying specification. We show that LPN can generalize beyond its training distribution and adapt to unseen tasks by utilizing test-time computation, outperforming algorithms without test-time adaptation mechanisms.

premise

outline

quotes

notes

summary

1. Brief Overview

This paper introduces the Latent Program Network (LPN), a novel algorithm for program induction that learns a distribution over latent programs in a continuous space, enabling efficient search and test-time adaptation. Unlike previous methods relying on stochastic sampling or gradient updates, LPN incorporates a structured search mechanism during inference, leveraging gradient-based optimization in the latent space to find the latent program that best explains a given specification. The model is evaluated on the ARC-AGI benchmark, demonstrating its ability to generalize beyond its training distribution and adapt to unseen tasks through test-time computation.

2. Key Points

Introduces Latent Program Network (LPN), a novel algorithm for program induction with efficient test-time adaptation.
Utilizes a continuous latent space to represent programs, allowing for efficient gradient-based search during both training and inference.
Employs a novel training objective that prevents the latent space from directly encoding the output, instead focusing on learning the program space itself.
Evaluated on ARC-AGI, outperforming algorithms without test-time adaptation mechanisms and demonstrating strong generalization capabilities.
Does not utilize pre-trained models or synthetic data, showing scalability and applicability to various domains.

3. Notable Quotes

No notable quotes identified.

4. Primary Themes

Program Synthesis: The core focus is on developing more efficient and generalizable methods for automatically generating programs.
Latent Space Representation: The use of a continuous latent space to represent programs is a key innovation, enabling efficient search and adaptation.
Test-Time Adaptation: The paper emphasizes the importance of test-time adaptation mechanisms for handling challenging, out-of-distribution problems.
Generalization: A central theme is the ability of LPN to generalize beyond its training data and adapt to unseen tasks.
Scalability: The method’s independence from pre-trained models and synthetic data highlights its potential for scalability and application to diverse domains.