# Gradient-Based Program Synthesis with Neurally Interpreted Languages

arXiv: https://arxiv.org/abs/2604.18907 · HTML: https://mlsanity.com/paper/2604.18907/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 30 references that are in the map.
- First posted on arXiv 20 Apr 2026.

## Builds on (most cited first, 21 of 21)

- [Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networks](https://mlsanity.com/paper/1703.03400/) (2017)
- [Neural Discrete Representation Learning](https://mlsanity.com/paper/1711.00937/) (2017)
- [Categorical Reparameterization with Gumbel-Softmax](https://mlsanity.com/paper/1611.01144/) (2016)
- [The Concrete Distribution: A Continuous Relaxation of Discrete Random Variables](https://mlsanity.com/paper/1611.00712/) (2016)
- [Recurrent World Models Facilitate Policy Evolution](https://mlsanity.com/paper/1809.01999/) (2018)
- [Neural Processes](https://mlsanity.com/paper/1807.01622/) (2018)
- [DeepCoder: Learning to Write Programs](https://mlsanity.com/paper/1611.01989/) (2016)
- [Neural Programmer-Interpreters](https://mlsanity.com/paper/1511.06279/) (2015)
- [Straightening Out the Straight-Through Estimator: Overcoming Optimization Challenges in Vector Quantized Networks](https://mlsanity.com/paper/2305.08842/) (2023)
- [Linguistic generalization and compositionality in modern artificial neural networks](https://mlsanity.com/paper/1904.00157/) (2019)
- [Robust Training of Vector Quantized Bottleneck Models](https://mlsanity.com/paper/2005.08520/) (2020)
- [Making Neural Programming Architectures Generalize via Recursion](https://mlsanity.com/paper/1704.06611/) (2017)
- [Automatically Composing Representation Transformations as a Means for Generalization](https://mlsanity.com/paper/1807.04640/) (2018)
- [BUSTLE: Bottom-Up Program Synthesis Through Learning-Guided Exploration](https://mlsanity.com/paper/2007.14381/) (2020)
- [Neural Program Meta-Induction](https://mlsanity.com/paper/1710.04157/) (2017)
- [Searching Latent Program Spaces](https://mlsanity.com/paper/2411.08706/) (2024)
- [Just-in-Time Learning for Bottom-Up Enumerative Synthesis](https://mlsanity.com/paper/2010.08663/) (2020)
- [Latent Programmer: Discrete Latent Codes for Program Synthesis](https://mlsanity.com/paper/2012.00377/) (2020)
- [ExeDec: Execution Decomposition for Compositional Generalization in Neural Program Synthesis](https://mlsanity.com/paper/2307.13883/) (2023)
- [Program Synthesis with Best-First Bottom-Up Search](https://mlsanity.com/paper/2310.04327/) (2023)
- [Gradient-Based Program Repair: Fixing Bugs in Continuous Program Spaces](https://mlsanity.com/paper/2505.17703/) (2025)

## Built on by (most cited first, 5 of 5)

- [Learning to Theorize the World from Observation](https://mlsanity.com/paper/2605.03413/) (2026)
- [Latent Programming Horizons in Coding Agents](https://mlsanity.com/paper/2607.05188/) (2026)
- [Compile Once, Differentiate Everywhere: A Differentiable Meta-Circular Interpreter](https://mlsanity.com/paper/2606.09930/) (2026)
- [Differentiate the Evaluator, Not the Program: An Efficient Runtime Representation for Neuro-Symbolic Learning](https://mlsanity.com/paper/2607.03574/) (2026)
- [A Symbolic Neural CPU for Quantization-Simulated Writeback and Interpretable Program Execution](https://mlsanity.com/paper/2607.10021/) (2026)

## Abstract (arXiv)

A central challenge in program induction has long been the trade-off between symbolic and neural approaches. Symbolic methods offer compositional generalisation and data efficiency, yet their scalability is constrained by formalisms such as domain-specific languages (DSLs), which are labour-intensive to create and may not transfer to new domains. In contrast, neural networks flexibly learn from data but tend to generalise poorly in compositional and out-of-distribution settings. We bridge this divide with an instance of a Latent Adaptation Network architecture named Neural Language Interpreter (NLI), which learns its own discrete, symbolic-like programming language end-to-end. NLI autonomously discovers a vocabulary of primitive operations and uses a novel differentiable neural executor to interpret variable-length sequences of these primitives. This allows NLI to represent programs that are not bound to a constant number of computation steps, enabling it to solve more complex problems than those seen during training. To make these discrete, compositional program structures amenable to gradient-based optimisation, we employ the Gumbel-Softmax relaxation, enabling the entire model to be trained end-to-end. Crucially, this same differentiability enables powerful test-time adaptation. At inference, NLI's program inductor provides an initial program guess. This guess is then refined via gradient descent through the neural executor, enabling efficient search for the neural program that best explains the given data. We demonstrate that NLI outperforms in-context learning, test-time training, and continuous latent program networks on tasks that require combinatorial generalisation and rapid adaptation to unseen tasks. Our results establish a new path toward models that combine the compositionality of discrete languages with the gradient-based search and end-to-end learning of neural networks.