Research map / Label-efficient and robust learning / Test-time adaptation
Searching Latent Program Spaces
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes the Latent Program Network (LPN), which learns a continuous latent space of implicit programs and performs gradient-based latent search at test time, evaluated on a pattern task, a string task, and ARC-AGI.
Problem
Program synthesis from input-output examples struggles with huge combinatorial search spaces and requires hand-made DSLs or priors, while in-context neural approaches lack test-time search and specification consistency and scale poorly with specification size.
Approach
Factorize inference into an encoder that maps I/O pairs to a latent program distribution, gradient ascent in that latent space at test time to best explain the examples, and a decoder that executes the refined latent on a new input; trained end-to-end with a reconstruction loss over held-out pairs and a KL term.
Key results
- On ARC-AGI out-of-distribution, LPN goes from 7.75% at 2E+11 FLOPs to 15.5% at 2E+14 FLOPs with test-time latent search, roughly doubling performance.
- On the Pattern task, LPN trained with 1 gradient step reaches 99.5% exact match with 100 test-time gradient steps versus 67.5% for Grad 0 training.
- On the OOD Pattern task, LPN Grad 1 reaches 88.0% with 100 test-time gradient steps while TTT and in-context learning fail (0.3% and 0%).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| increase LPN test-time FLOPs from 2E+11 to 2E+13 | LPN · ARC-AGI out-of-distribution | exact match accuracy: 7.75 -> 15.25 | Helped |
| increase LPN test-time FLOPs from 2E+11 to 2E+15 | LPN · ARC-AGI out-of-distribution | exact match accuracy: 7.75 -> 15.50 | Helped |
| increase TTT test-time FLOPs from 2E+13 to 2E+14 | TTT · ARC-AGI out-of-distribution | exact match accuracy: 13.50 -> 16.00 | Helped |
| train LPN with one latent gradient step rather than no latent optimization (ablation) | LPN · Pattern, 100 inference gradient steps | exact match accuracy: 67.5% -> 99.5% | Helped |
| use gradient ascent rather than sampling-based latent search (ablation) | LPN · Pattern | exact match accuracy | Helped |
| stop the decoder gradient through the latent optimization update (ablation) | LPN · Pattern | exact match accuracy | Helped |
| add one latent gradient step during training (ablation) | LPN · String manipulation test set, 10 inference steps | exact match accuracy: 83.3 (0.8) -> 86.1 (1.5) | Helped |
| increase TTT test-time parameter updates from 0 to 100 (ablation) | TTT · String manipulation test set | exact match accuracy: 78.1 (1.1) -> 11.8 (1.9) | Hurt |
| use one training-time latent gradient step instead of none (ablation) | LPN · Strongly OOD Pattern, 100 inference steps | exact match accuracy: 41.1 (29.6) -> 88.0 (5.3) | Helped |
| initialize gradient search from the encoder rather than the Gaussian prior (ablation) | LPN inference · ARC-AGI evaluation, 400 search steps | exact match accuracy: 10.75% -> 15.50% | Helped |
| use gradient search rather than encoder sampling (ablation) | LPN inference · ARC-AGI evaluation, 400 search steps | exact match accuracy: 10.62% -> 15.50% | Helped |
| replace gradient search with local search from encoder initialization (ablation) | LPN inference · ARC-AGI evaluation, 400 search steps | exact match accuracy: 15.50% -> 10.75% | Hurt |
Surprising findings
- Test-time fine-tuning (TTT) is less prone to overfitting on ARC-AGI than on the pattern task, possibly due to larger model size.
- Repeated encoder sampling gives only marginal gains over a single sample, and gradient search only clearly beats it at larger budgets.
Limitations
- Limited diversity of programs in the training distribution restricts the expressiveness of the latent space.
- Compositional generalization is not robust; some composition cases fail even with latent search.
- Only standard first-order optimizers are used for latent search; evolution strategies and discrete program representations are left to future work.
Experimental setup
Datasets: re-arc Pattern task (synthetic) String manipulation synthetic task
Benchmarks: ARC-AGI 2024 evaluation set ARC-AGI training set (in-distribution) Pattern task String manipulation task
Metrics: exact match accuracy top-2 accuracy
Baselines: In-context learning transformer Test-time training (TTT) CodeIt Mirchandani et al. (ARC LLM approach) CodeT5 text-davinci
Builds on: test-time training Neural Processes LEAPS CodeIt MAML
Closest papers by meaning
- Latent Programmer: Discrete Latent Codes for Program Synthesis (ICML 2021 · similarity 0.88)
- Gradient-Based Program Synthesis with Neurally Interpreted Languages (ICLR 2026 · similarity 0.88)
- ExeDec: Execution Decomposition for Compositional Generalization in Neural Program Synthesis (ICLR 2024 · similarity 0.85)
- Program Synthesis via Test-Time Transduction (NeurIPS 2025 · similarity 0.85)
- HYSYNTH: Context-Free LLM Approximation for Guiding Program Synthesis (NeurIPS 2024 · similarity 0.84)
- ConceptSearch: Towards Efficient Program Search Using LLMs for Abstraction and Reasoning Corpus (ARC) (AAAI 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.