Gradient-Based Program Synthesis with Neurally Interpreted Languages
Authors: Matthew Macfarlane
Clément Bonnet
Herke van Hoof
Levi Lelis
Venue: ICLR 2026 Poster (2026)
Keywords: Meta Learning
Neural Program Synthesis
Neuro-Symbolic Learning
Primary area: neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)

Abstract: 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 labor-intensive to create and may not transfer to new domains. In contrast, neural networks flexibly learn from data but fail to generalise systematically. We bridge this divide with the Neural Language Interpreter (NLI), an architecture that learns its own discrete, symbolic-like programming language end-to-end. NLI autonomously discovers a vocabulary of subsymbolic 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 (LPNs) 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.

Published as a conference paper at ICLR 2026
GRADIENT-BASED PROGRAM SYNTHESIS WITH NEURALLY INTERPRETED LANGUAGES
Matthew V. Macfarlane AMLab, University of Amsterdam ma matthew. v. mm i vive co.coo.uu .uk
Clément Bonnet
Herke van Hoof
AMLab, University of Amsterdam
Levi H. S. Lelis
Department of Computing Science, University of Alberta Alberta Machine Intelligence Institute (Amii), Edmonton, Canada
ABSTRACT
A central challenge in program induction has long been the trade-off between symbolic and neural approaches. Symbolic methods offer compositional gener- alisation and data efficiency, yet their scalability is constrained by formalisms such as domain-specific languages (DSLs), which are labor-intensive create and may not transfer to new domains. In contrast, neural networks flexibly learn from data but fail to generalise systematically. We bridge this divide with the Neural Language Interpreter (NLI), an architecture that learns its own discrete, symbolic-like programming language end-to-end. NLI autonomously discovers a vocabulary of primitive operations and uses novel differentiable neural executor to interpret variable-length sequences of these primitives. This allows NLI to represent programs that are not bound to 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 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 tasks that require combinato- rial generalisation and rapid adaptation to unseen tasks. Our results establish a new path toward models that combine the compositionality of discrete languages with the gradicnt- basee search and end-to-end learning neural networks.
INTRODUCTION
A central challenge in machine learning is the trade-off between symbolic and neural representations. Symbolic approaches often enable strong compositional generalisation (Lake & Baroni] 2018), in some cases from only a few examples (Solar- et al. 2006; Gulwani] 2011). Yet their scalability is constrained by formalisms such as domain-speciff languages, which require human effort to generate, may not transfer to other domains, and are combinatorially expensive search. Neural approaches, by contrast, scale effectively but behave as monolithic models. The knowledge they acquire is entangled within their weights, making it difficult reuse beyond the training distribution, even when generalisation only requires recombining concepts already learned (Baroni 2020).
In the context of program synthesis, we make progress toward bridging this divide with a model that learns its own symbolic representation, end-to-end, directly from data. Specifically, it simultancously learns a domain-specific neural language and a neural interpreter for such a language. Similar
Work completed while visiting student the University of Alberta.

---

Published as a conference paper at ICLR 2026
to traditional handerafted symbolic representations, the learned language enables compositional generalisation. Similar to neural representations, the neural interpreter's 's differentiability allows us to use gradient descent to search the language-induee induced space for solution programs. Recent work, such as Latent Program Networks (LPNNs) (Macfarlane & Bonnet 2024). has explored learning program representations with continuous latent spaces. However, this approach is limited in its ability to generalise by composing learned concepts, which is a key strength of symbolic representations.
Our architecture, the Neural Language Interpreter (NLI), uses encoder-decoder model to discover discrete representations (Jang et al. 2017; Maddison et al. 2016) of programs. To learn a discrete vocabulary that can represent programs in the target domain, we train on programming- beaaamiiinnb-----llleeee (PBE) tasks. During inference, conditioned on specification of examples. NLI's encoder produces a sequence of discrete tokens, as its internal inferred program representation. NI.I's encoder acts as program inductor; the token sequence forms neural program. The decoder serves as neural executor, interpreting the program one token at time, mapping the test input to an output, similar to neural executors used in conditional world models (Ha & Schmidhuber, 2018). Both the encoder and decoder are designed to be fully differentiable, so NLI can be trained end-to-end.
Since the neural executor consumes one token at a time, NLI is not bound to a constant number of computation steps, as in previous approaches such as LPN. The number of steps in NLI's programs can grow with the token length of programs. This is important because it enables NLI to solve problems more challenging than those with constant-time requirements, seen during training. Moreover, since NLI's programs can recombine learned tokens in different ways and at different lengths, we hypothesise that its language supports the combinatorial generalisation lacking in previous approaches.
In addition to the engineering hurdle of designing domain-specifis languages, our work is motivated by the need to bypass the difficult combinatorial search problem inherent program synthesis. Rather than learning external guiding functions for search (Barke et al. 2020 Odena et al. 2022 Ameen
Lelis 2023), guidance is embedded in the language NLT learns. Because the neural exccutor is differentiable, we can search in the space of neural programs with gradient descent. Synthesising neural program with NLI is thus analogous to local search in symbolic spaces (Husien & Schewe 2016), but with the advantage of having gradient signals. Another benefit of learned language is how the search is initialised, which can dramatically affect efficiency (Hoos & Stützle 2004| Sadmine al. 2024). NLI's inductor provides an initial guess for a neural program solution at test time, and the gradient search then refines this guess to find the combination of learned primitives that solves the problem.
In this paper, we introduce the Neural Language Interpreter (NLI), a model that learns its own discrete programming language and differentiable interpreter for executing it. By combining symbolic compositionality with neural end-to-end training and gradient- based program search, NLI addresses the limitations of both paradigms. Across sequence-based compositional benchmarks, NLI achieves strong out-of-distribution accuracy on length extrapolation, primitive extraction, and novel composition tasks, where in-context learning, test-time training, and latent program networks fail. NLI matches or exceeds the performance of neuro-symbolit baselines on DeepCoder, despite training only from ontput examples without ground truth program representations.
2 PROBLEM STATEMENT
We formalize our task as program induction, where the goal is to infer the underlying behaviour of an unknown program p from input-output examples using a model M. Given a set $ = {(1 of input-output pairs generated by p and a new query input In+1, MSS 2n+1) predicts the corresponding output p(z,-1). This aligns with the programming by example (PBE) formalization, where information about program p available only via its outputs. Training tasks are formed by sampling latent program from distribution Piruin over the space of possible programs P. conditional distribution {x: |u+1 P(X|p). (p). This distribution generates inputs relevant to the logic of program p. The first n onput- pairs form the specification S = { p(z,)) from which the model must induce the program's 's logic. The model's objective is to minimise the prediction error between its prediction, 1 M(, 1n+1). J. and the true output p(z.+1), 1. to train the model to generalise
Program specifications are formed from n inputs sampled from the
program execution new input, not merely fit the given pairs. The model has no access to the
2

---

Published as a conference paper at ICLR 2026
program's 's fully observable representation p during training test time. This is vital, tasks often involve latent functions without an observable specification. At test time, the model is evaluated on programs drawn from Piea. which can differ from Prain in order to test for compositional generalisation.
DISCRETE SEQUENTIAL INFERENCE
Existing neural program synthesis methods fail compositional generalisation, struggling to recom- bine learned concepts for novel tasks. The Neural Language Interpreter (NLI) overcomes this by learning a discrete, symbolic-like programming language end-to-end. Programs are variable-length token sequences processed by differentiable neural executor, enabling training input-output examples via Gumbel-Softmad This facilitates efficient, gradient-bar -based search at test time to re- fine initial programs. NLI outperforms baselines tasks requiring combinatorial generalisation, successfully extrapolating program lengths and synthesising novel compositions of learned skills.
3.1 TRAINING OBJECTIVE
We train the encoder-decoder with variational objective inspired by the ELBO. The goal is to reconstruct a program's 's output for query input, conditioned on specification of other input-output pairs from the same program. Formally, the program inductor qa infers latent program representation from the specification, which the neural interpreter po then executes to predict the output for new query. The model is trained end-to-end on specifications of size m, sampled in mini-batches of size B. using a leave-one-out loss: for each pair, NLI induces program from the remaining (S, = S {( }) and maximises the likelihood predicting the held-out pair. The objective is:
pairs
1
((0,0;5)=
Crccon (6, 0; 3b.i Mo St,s) Areg Greg (d;; S).
(I)
where D is the distribution of specifications. This objective has two components: the reconstruction loss (Crecon) and the encoder regularisation loss (Lreg), which explain next.
Reconstruction Loss (Crecon) This term ensures that the latent program is expressive enough to predict the program's output on held-out input. It is defined as the negative log-likelihood of the target output yi given the input and the latent program 2; inferred from the sub-specification S;
Crecoa ( ④b 0: Fz, Vs: S:) log (o 24, Z:). 2, gol. St)-
(2)
Encoder Regularisation Loss (Creg) This regularising loss encourages reuse of tokens in the neural vocabulary of size V. biasing the encoder (via parameters Φ) toward discovering a compositional latent program space. We implement differentiable approximation of the number unique tokens used anywhere in the batch. By penalising programs that use many unique vocabulary entries, fryg promotes generalisation: the model learns build new programs by recombining a compact set of discovered primitives rather than memorising arbitrary token sequences for each task. Here, go (=,,k Sh,i) denotes the probability assigned by the encoder to token & at latent position j for the leave-one-out specification St, This loss biases the encoder toward discovering programs as reusable compositions rather than introducing a unique token for each new program.
N
log(1 - (0 Sbss) ]
Creg (Ø: = Σ
exp ΣΣΣ
3.2 DISCRETE PROGRAM REPRESENTATION LEARNING
The encoder of NLI functions as a program inductor, denoted as go. from which latent program representation (= 2T) is sampled, given specification S; containing input-output examples. This representation, z, a sequence of continuous vectors that serves as a differentiable proxy for sequence of discrete tokens drawn from learned codebook of size K. This codebook includes a dedicated skip token, which functions as a no-op, allowing the model to effectively learn shorter programs by ignoring certain computational steps within the fixed-length sequence T.
3

---

Published as a conference paper at ICLR 2026
For program induction firstly transformer, which denote by the function hgs maps each pair (z), Uy) in a single specification to a sequence of contextual embeddings, E, = h( yj) = (e,,,, Cj.r). These sequences are then aggregated, across the specification, by computing the element-wise arithmetic mean across all n pairs, é - Ej to produce single, permutation cermutatio-invaarian sequence of specification embeddings, = (ē1, E2. ēT). In addition to being permutation invariant, this aggregation method also enables generalisation specification sizes different from those seen during training, as demonstrated in Macfarlane & Bonnet (2024).
To obtain differentiable proxy for discrete program, this sequence of continuous embeddings is projected to the codebook space. shared multi-layer neural network maps each embedding e, to vector of logits, parameterising categorical distribution over the K codebook entries. We then apply the Gumbel-Softmax relaxation to sample a "soft" one-hot vector at each position Ty:
4 + gt
4. = f(e)) E IRK
πI Tee,, Tp 9t) = softmax
E EAR
Tp
where St sample from Gumbel distribution and is the temperature. The final program representation z == (21.-.., 2r) is defined as the continuous approximation a discrete program, which is passed the decoder, and is constructed by taking weighted combination of the codebook embeddings V using these soft vectors:
2t (e,, 9t) 2 (21, zT)
During training, the temperature steadily annealed, progressively improving the approximation of discrete sample from the un-normalised distribution 4.
3.3 RECURRENT NEURAL PROGRAM EXECUTION
common failure point for standard decoders is that they overfit to program lengths and structures seen during training. We implement the neural interpreter recurrent application of an executor network to achieve compositional generalisation. This executor network conditions on the program representation 2 token at time, using shared neural executor de to iteratively update intermediate program state 8t. This sequential execution naturally handles novel combinations of primitives and variable program lengths, forcing the model to learn reusable, abstract building blocks. This approach stands in contrast to methods like LPNs, which are limited to representing entire programs single monolithic embedding.
The execution process is detailed in Algorithm|] 1 An initial state is created by embedding the input query zg. This state then refined over T' steps in a loop, where each step f, the executor da uses the current program token 2n to compute gating mechanism: the probability of the skip token, Iy [rskipiidh idx), is taken from the encoder's output and used to linearly interpolate between the previous state 8:-1 and the newly computed state. This allows the model to effectively ignore an instruction 2,. After the final token processed, the last state is used to generate the output.
updated state. A crucial feature is the skip-token
Algorithm Neural Language Interpreter (Decoder ps)
1: function pyly, x 2, Ta; hi)
2:
(E, d, MLP) +- 0
Unpack implicit parameters from A Embed input
3:
8g + Embed(z; gg E)
4:
for t = 1 T do
5:
k f- d(st-1, 24-1
Transform state Project hidden state to logits
6:
MLP((k))
7:
J. t softmax ((4 + /T)
D Apply Guumbel-Softmax (h, is Gumbel noise)
8:
O: TT ne
> Compute new potential state b Update state with skip-gating
9:
St f Te relskip_idd idx] 1:-1 + (1 nz =r(skip_idx]
end for
11:
ly < MLP(kr)
Generate final output logits
return softmax((,,)
13: end function
4

---

Published as a conference paper at ICLR 2026
Neural Program Search
max log Pyleeain (rrain P1.-. PT)
Perain
Versin
19431 13491
Inductor q
83431
19431)
Interpreter
24139
03142
log
82418
61428
92418
8T429
P6
V
2/
Interpreter pg
Ytest 12737
Interpreter
73721
po(y/ Pi.
24138
Executor
Executer
Executor
03344
Overview of the inference process. The program inductor generates a sequence of latent program tokens conditioned on the specification. Neural Program Search refines this program to better explain the specification, and the neural interpreter then executes the improved program token by token.
Figure 1:
3.4 SEARCHING NEURAL PROGRAMS
key benefit of our model is the ability to refine an initial program prediction at test time using gradient-based search. While the encoder provides a fast first guess, it may not be optimal, especially for outtof-distribution programs. Our search operates not in the discrete space of programs, but in continuous relaxation of the discrete tokens. Because it represents programs sequences of learned primitives, this space can construct entirely new programs of arbitrary length, even those never seen during training. The search, therefore, becomes a process of discovering these novel compositions.
The key benefit of searching in the relaxed representation of discrete tokens is that, like during training, execution remains fully end-to-end differentiable. This allows us use gradient ascent, an efficient optimisation method crucial for navigating the vast combinatorial space of possible programs. The search objective find the latent embeddings that maximise the expected likelihood of the specification data S {Iz }y)}, with the expectation taken over the program and layer Gumbel samples:
arg max
Σ (si.r))sS
log Po(s [zy z(e, Tp. 9), Ta
g gr-Gumeel hv-CGumbel00,1""
To encourage finding strong approximation to a discrete solution, during the optimisation of this objective, we perform temperature annealing of both Tр and ти. The optimisation begins with a high temperature to smooth the landscape and encourage broad exploration. As the search progresses, we gradually lower the temperature, encouraging the discovery of discrete program along with discrete intermediate computation between tokens.
Instead of using single starting point, we initialise the search from multiple locations to better explore the vast program space and avoid getting stuck in local minima. Specifically, initial latent embeddings from a Gaussian distribution, with parameters μ = e,, a. We then perform L steps of gradient ascent in parallel from each of the starting points. This parallel search strategy not only effective for exploration but is also highly scalable, allowing us to leverage multiple hardware devices efficiently.
sample m
Most program induction methods have to contend with the problem of finding many programs that explain given specification. This is considerable concern in both pure parameter-base modelling

---

Published as a conference paper at ICLR 2026
and also latent space optimisation (Macfarlane & Bonnet 2024), where early stopping is often used to limit the chance of converging to programs that do not generalise. In NLI, this is less of a concern as the search space is less flexible than such continuous search spaces, limited to recomposing set of discrete embeddings. Therefore, the risk of overfitting is relatively limited.
4 EXPERIMENTS
We evaluate NLI's compositional generalisation capabilities across custom diagnostic benchmark for compositional generalisation and the compositionality version the DeepCoder benchmark (Balog al. 2016), introduced in (Shi et al. 2023), comparing to range of neural and neuro- symbolic baselines.
Benchmarks The custom suite uses fixed-length sequences (20) and is designed to reveal failure modes in PBE, where models see only input-output pairs. It comprises three splits containing different tasks: Shift-L, training on small sequence shifts k E (1,....5 5) and testing on larger unseen shifts k {6, ..., 10): Shift-P, the inverse, training on large shifts k (7, 8, 9) and testing on smaller ones k E {1, 2, 3); and Comp-I, where models trained on single primitives (e.g.. f(x) or g(x)) must compose them at time (c.g., f()()))). We also explore the compositionality deepcoder dataset that scales the number of primitives and program complexity, see appendix A
Baselines and Models We compare II.I against several strong baselines: In-Context Learning (ICL). Test-Time Training (TTT), Latent Program Networks (LPN), and discrete variant (D-LPN). We evaluate three inference strategies for our model: Base Inference (direct encoder output), Prior Search (sampling from the encoder), and our primary method, Gradient Search, which optimises the program in the latent space.
4.1 COMPOSITIONAL GENERALISATION NEURAL MODELS
Table 1: Performance for different methods and datasets, in the custom suite. We report final accuracy for both in-distribution and out-of-distribution test splits (ID and OOD).
Shift-L
Shift-P
Comp-I
Method
ID
OOD
OOD
ID
OOD
In-Context
1.00
0.00
1.00
0.00
1.00
0.13
TTT
1.00
0.00
1.00
0.00
0.95
0.14
LPN
1.00
0.00
1.00
0.00
1.00
0.18
LPN Gradient Search
1.00
0.03
1.00
0.00
1.00
0.29
D-LPN
1.00
0.02
1.00
0.00
0.99
0.15
D-LPN Gradient Search
1.00
0.01
1.00
0.00
0.99
0.20
NLI
1.00
0.00
1.00
0.00
1.00
0.17
NLI Prior Search
1.00
0.10
1.00
0.00
1.00
0.23
NLI Gradient Search
1.00
0.99
1.00
1.00
1.00
0.91
We train all models for 100k batches of size 512 and evaluate on held-out test splits, in- and out-of- distribution. Due the inference cost differences between NLI and baselines, for completeness, for all baselines we also performed training runs with matched compute by increasing decoder layers, for all baselines; this led to a degradation of in-distribution performance and no generalisation. We report the higher, low inference 2-layer decoder results in table] I
All models achieve near-perfect accuracy on the in-distribution (ID) test sets, demonstrating their ability to solve tasks similar to those seen during training with neural induction. On the more challenging out-oof-dstrribie model fail to generalise. In-Context Learning (ICL) and the Latent Program Network (LPN and D-LPN) show near 0% OOD accuracy on the shift tasks (Shift-L and Shift-P). Search- based LPNs achieve only minor gains on Compose Isolation (Comp-I), but still fail to solve the task. In contrast,
(OOD) splits, however, all baselines and the non-search variants of

---

Published as a conference paper at ICLR 2026
NLI with Gradient Search exhibits strong compositional generalisation across all three benchmarks: on Shift-L (length generalisation) it reaches 99% by extrapolating from small to larger unseen shifts; on Comp-I (composing concepts) it achieves 91% by synthesising programs such (g(2)); and on Shift-P (primitive extraction) it attains a perfect 100% by "decompiling" primitives after training only complex ones. These results confirm that NII achieves systematic generalisation, enabled by gradient-based search, whereas the base encoder and prior search variants have performance in line with In-Context, TTT and LPN baselines, which achieve no generalisation. The learned codes further reveal systematic reuse of primitives. The model consistently represents a single left shift with token 231 and a two-step shift with token 476, constructing larger programs by combining these two building blocks. The OOD case of eight shifts is also expressed mixture of these primitives (found via gradient search), highlighting how generalisation arises from recombination rather than memorisation.
4.1.1 LEARNED PROGRAM REPRESENTATION
We study the task of shifting sequences to the left. During training, the model observes shifts of length I to (inclusive). In principle, the network could learn a separate token for each shift. Instead, it discovers more efficient representation by reusing tokens. Specifically, it learns token (231) that corresponds to a single left shift. By repeating this token, the network composes shifts of lengths 2 and 3. For larger shifts. it introduces a second token (476) corresponding enables the model to combine primitives to generate more complex shifts. For example, shift of 4 is represented as one two-step shift plus two one-step shifts. At test time, when generalising OOD to larger shifts, the model composes primitives in the same manner. For instance, to represent an 8-step shift, it uses four single-shift tokens and two two-shift tokens. This demonstrates both compression (a small set of primitives) and compositionality (systematic reuse of primitives).
two-step shift. This
Learned Program Representations for Shift-I
Ground Truth Program
NLI Program Representation
shift_left(1 (1)
231
shift_left (2)
231
231
shift_lefttt)
231
231
231
shift_left (4)
231
476
231
shitt_left
231
476
476
(8) (OOD)
231
231
231
231
476
476
4.2 UNDERSTANDING THE ORIGINS NLI'S GENERALISATION CAPABILITIES
To investigate the origins of NLI's generalisa- tion, we conduct an ablation study across the datasets in table [T with results shown in fig. The base model achieves nearly perfect OOD ac- curacy (97%), and remove components indi- vidually to assess their importance. Most prove indispensable: dropping recurrent execution or the discreteness of either program or layer repre- sentations collapses OOD accuracy near (1-5%). This shows that discrete programs, dis- crete layer traces, and recurrent dynamics are all essential for generalisation. Dropping the skip token reduces performance to 24%, consistent with the model's ability to learn its own skip, but benefits from a dedicated token for faster, more stable training. We also test the importance of the encoder loss on performance, which results in small drop in performance. The benefit of encoder loss can depend on the type of compo-
gumbel
76%
no encoder loss
0076
no skip token
layer gumbel
5%
discrete layer
5%
no racurrett execution
program 1%
80
100
Test Accuracy (96
Figure 2: Ablations of the NLI base model to iden- tify components critical for OOD generalisation. sitionality that is being tested. For example, it is useful for the type of composition in Shift-P, where
7

---

Published as a conference paper at ICLR 2026
the underlying program primitives need to be represented to compose new programs that shorter than those seen during training. For length generalisation, where primitives that have already been seen need to be combined into longer programs, the encoder loss does not affect performance.
4.3 GUMBEL-SOFTMAN
We also observe in fig. that the Gumbel-Softmax relaxation, used to approximate discrete sampling, major driver of performance. Removing layer-level Gumbel sampling (no layer gumbel) causes near-complete failure on OOD compositional generalisation (dropping to 5%), while removing program-level Gumbel sampling (no program gumbel) reduces performance by 23 percentage points (to 76%). Although the encoder still outputs distribution over a discrete codebook even without Gumbel-Softne Softtaxx, we hypothesise that the network still learn peaked distributions, allowing meaningful discrete representations to emerge naturally and preserving some degree of generalisa- tion. However, explicitly adding the Gumbel-Softmas approximation significantly strengthens this inductive bias, leading to substantially better results.
That said, our approach does not fundamentally depend on Gumbel-Softman any smooth relaxation of discrete sampling could be substituted (e.g., VQ-VAE with the straight-throug! estimator (van den Oord al., 2017)). We chose Gumbel-Softmax primarily for its superior training stability. The straight-through estimator in VQ-VAE is known suffer from biased gradients, codebook collapse (where many codebook entries remain unused, often requiring oversized codebooks or continual pruning) (Huh et al., 2023), and internal covariate shift between encoder outputs and codebook vectors (Lancucki et al. (2020). Gumbel-Softme
is not without pitfalls either; stable training requires careful temperature scheduling. We find that annealing the temperature too quickly leads to severe performance degradation, as shown in our ablation on the Shift-L dataset (appendix C). With a gradual annealing schedule, however, training remains reliable and yields the strong results reported.
4.4 SCALING TEST-TIME PROGRAM SEARCH
100
Rum dharT
To evaluate the effectiveness of our gradient-based search, we analyse how performance scales with the available computational budget at test time. We
Arcurary test wee [9)
2012
6096
benchmark the Comp-I dataset, varying two key
hyperparameters: the number of parallel initialisa- tions, Num starts, and the number of optimisation iterations, Gradient steps. The results, presented in fig. demonstrate a strong and consistent positive correlation between test-time compute and final ac- curacy.
Gradient steps
4.5 DEEPCODER
Figure 3: Performance Compose-I, scaling two axes of test-time compute: gradient steps and number of starts.
To assess the scalability of our approach, we evaluate NLI on the DeepCoder benchmark (Shi et 2023). standard testhed for compositional generalisation in program synthesis.
The DeepCoder dataset consists of short functional programs that manipulate lists of integers using a dedicated domain-specific language (DSL). Each program a straight-line sequence of assignments. Every line defines a new variable by applying exactly one DSL operation to the input(s) or to previously defined variables, and the final variable is the program output.
Dataset overview:
The DSL includes first-order operations (Head, Last, Take, Drop, Access, Minimum, Maximum, Reverse, Sort, Sum, etc.) as well as higher-order functionals (Map, Filter, Count, ZipWith, Scan11) that accept one of small fixed set of lambda expressions (e.g., +1, +2, (-), >0, squaring, etc.).
For example, the program x0 INPUT x1 Map (x2) x0 x2 Filter (>0) xi x3 Sort x2 + x4 Reverse x3 applied to the input list [-2, 5, 0, 3, -1]
yields the sorted positive doubled values [10, 6] as output.
8

---

Published as a conference paper at ICLR 2026
We note that the original training datasets for DeepCoder composition have not been made publie; therefore, data generation was run from scratch to generate datasets of size 1 11.6 million induction tasks, train the neural baselines (NLI, LPN and In-context). Due to the prohibitive costs of the data sampling function, this is less than the 60 million used the original work; however, baselines all achieve competitive performance. We highlight that neuro-symbolic approaches all leverage access to ground-truth programs during training, where NLI and LPN do not require this. However, adding program representations during training can serve powerful training signal for the neural decoders, which are otherwise bottlenecked by the encoder's 's induction capacity. Therefore, for NLI and LPN, we add NLI w/ program and LPN w/ program baselines. These leverage an additional encoder mapping from program representations to latent space, resulting in an additional reconstruction loss, which is simply added to the total loss with equal weight to the standard encoder reconstruction loss. We give complete description of the program encoder and our training procedure in appendix D) In contrast, NLI, along with neural baselines such as LPN, and an In-context baseline, must induce program behaviour solely from input-output pairs. All neural benchmarks were trained for 200k batches of size 512, see appendix for more details. We find that end-to-end neural methods such as
NU
LPN w/ Programs
Transformer Pregram Synthesis Latent Programmer
Programs
In-context
LPN
ExeDec
40
Test Accuracy (16
30-
20-
Length Generalization
Compose Different Concepts
Switch Concept Order
Compose New Operation
Add Operation Functionaliity
Mean Performance
Figure 4: Comparison of fully neural baselines and NLI against neuro-symbolic methods. Neuro- symbolic models (exeDec, Transformer, Latent Programmer) use ground-trute program annotations, while neural models (In-context, LPN, NLI) rely only on input-output pairs.
NLI and LPN substantially outperform earlier Latent Programmer approaches and Transformer-basee program synthesis. Secondly, despite the absence of program supervision, they achieve performance competitive with ExeDec (Shi et al. 2023), highlighting the capacity of neural PBE approaches to autonomously discover structured program representations.
A direct comparison between NIJI and LPN further reveals complementary strengths. NLI generalises more effectively to longer programs and novel concept compositions, which is particular strength of NLI due to its ability compose programs of arbitrary length. In contrast. LPN excels at switching concept order and extending functionality with new operations. These differences suggest that their learned latent structures capture distinct inductive biases, leading to different generalisation behaviours out of distribution.
5 RELATED WORK
Symbolic Program Synthesis. Farly work in program synthesis largely relied symbolic techniques and DSL.s Classical systems, such as those by [Summers) (1977) and and[Gulwani (201T), ) used predefined DSLs with explicit search over symbolic programs. These methods provide interpretability and exactness but suffer from scalability issues, as every new domain requires manual DSL design. Recent neuro-symbolic hybrids, such DeepCoder (Balog al. 2016), combine neural predictor with symbolic search, predicting program components to accelerate search. However, their reliance restricted DSLs limits generalisation beyond the designed primitives.
Neural Program Induction and Meta Learning Neural approaches aim to overcome the brittleness of symbolic methods by learning programs directly from examples. Neural Cerraammm---nnepretttteee

---

Published as a conference paper at ICLR 2026
(Reed & De Freitas 2016) execute programs implicitly with recurrent models, while Devlin et al. (2017) introduced meta-induction for few-shot learning. These models improve adaptability but often tail to generalise compositionally and demand large supervision. ExeDec (Shi et al., 2023) added execution decomposition as an inductive bias, yet still relies on ground-truth decompositions and remains costly. Meta learning advances this by training networks to adapt across task distributions (Finn et al. 2017). a setup closely related to the optimisation considered here.
Latent Representations of Programs. Another line of work introduces latent spaces represent programs more flexibly. ComplLE (Kipt et al., 2018) segments demonstrations into reusable latent codes with Gumbel-Soon Soffmmxx relaxation, showing benefits for imitation learning. The Latent Pro- grammer (Hong et al. (020) extends this idea to discrete latent codes that plan over output examples, using VQ-VAE
VAE style autoencoder with beam search in latent space, see appendix [E] for a discussion on its relation to NLI. Most recently, Latent Program Networks (LPNs) (Mactarlane & Bonnet 2024) proposed continuous latent program representations facilitate test-time search, but the lack of discrete compositional structure hinders combinatorial generalisation.
Compositionality and Generalisation. Compositional generalisation remains a central challenge in neural program synthesis. Lake & Baroni (2018) demonstrated that standard seq2seq models fail to generalise systematically to novel compositions. Approaches such as the Compositional Recursive Learner (CRL) (Chang al. 2019) attempt address this by learning to compose reusable transformations. Similarly, recursion-basee from programming languages handle inputs of greater complexity than those seen during training. While these directions highlight the importance of compositional structure, they either rely on strong supervision achieve only limited scalability.
methods (Cai et al. 2017) leverage inductive biases
Discrete Representation Learning. Discrete latent representations provide a natural way to capture compositional structure and improve interpretability. The Vector- cettor-quantized Variational Autoencoder (VQ-VAE) (van den Oord et al. (017)) exemplifies this approach by learning a finite codebook of tokens, with gradients passed via straight -traightthhrough estimator. complementary method is the Gumbel-Softmax relaxation (Jang et al. 2017). which reparameterizes categorical sampling with a differentiable approximation. Together, these techniques enable end-to-end training with discrete variables while retaining symbolic structure. A practical example arises in hierarchical reinforcement learning, where the options framework (Sutton et al., 1999) defines set of reusable, temporally extended actions that compose into complex behaviours. Such discrete units, whether tokens in generative models or skills in RL, form compact and interpretable building blocks that support compositional generalisation and long-horizon reasoning.
6 CONCLUSION
In this work, we introduced the Neural Language Interpreter (NLI), a novel architecture that bridges the divide between symbolic and neural approaches in program synthesis. By learning discrete, symbolic-like language and a differentiable interpreter, NLI combines the compositional strengths of symbolic systems with the flexibility of neural networks. The model discovers vocabulary of primitive operations and composes them into variable-length programs, refined at test time through efficient gradient-basee based search. Our evaluations show that NLI outperforms existing methods on challenging compositional generalisation tasks, with ablations confirming that the discrete, sequential program representation is key to this success.
Limitations and Future Work: NLI introduces a new paradigm for program induction that demon- strates promising compositional generalisation. While we believe it has strong potential scale to significantly harder problems, the present work is an initial exploration and naturally comes with several limitations that highlight exciting directions for future research. A primary bottleneck is the computational cost of test-time search in the latent representation space; although NI.I proves remarkably robust to overfitting even under constrained search budgets, scaling to more complex tasks will likely require more efficient inference strategies, with evolutionary/lcal search being promising directions. As problem difficulty increases, programs will grow both in length and vocabulary size, potentially leading to vanishing or exploding gradients, which, while not observed in our experiments, could require architectural modifications at scale. The current interpreter also limits expressive power: each layer conditions exactly one token, preventing parameterised primitives (e.g., add (k) for variable k), and execution follows a strictly sequential flow without conditional branching.
10

---

Published as a conference paper at ICLR 2026
ACKNOWLEDGMENTS
We thank François Chollet for early inspirational conversations about the importance of developing a neural program that could handle recurrence and length generalization by design, which gave us inspiration for the final architecture. Thiss research was supported by Canada's 's NSERC and the CIFAR Al Chairs program. Matthew Macfarlane is supported by LIFT project 019.011, which is partly financed by the Dutch Research Council (NWO). This research was supported by Cloud TPUs from Google's s TPU Research Cloud (TRC) and by GPU credits provided by Modal. We also thank the anonymous reviewers for their comments and helpful discussions that improved the final version of the paper

---

Published as a conference paper at ICLR 2026
REFERENCES
Saqib Ameen and Levi H. S. Lelis. Program synthesis with best-first bottom-up search. Journal of Artificial Intelligence Research, 77:127 11100, 2023, doi: 10.1613/jair...44333
Matej Balog, Alexander I. Gaunt, Marc Brockschmidt, Sebastian Nowozin, and Daniel Tarlow. Deepeoder: Learning to write programs. arXiv preprint arXiv:1611.01990 2016.
Shraddha Barke, Hila Peleg, and Nadia Polikarpova. Just-in-time learning for bottom-up enumerative synthesis. In Proceedings of the ACM on Programming Languages, volume 4, pp. 1-29, 2020.
Marco Baroni. Linguistic generalization and compositionality in modern artificial neural networks. Philosophical Trunsactions of the Royal Society 375(1791):20190377 2020.
Jonathon Cai, Richard Shin, and Dawn Song. Making neural programming architectures generalize via recursion. arXiv preprint arXiv:1704.066/1 2017.
Michael Chang, Abhishek Gupta, Sergey Levine, and Thomas L Griffiths. Automatically composing representation transformations as means for generalization. In International Conference on Learning Representations (ICLR), 2019.
Jacob Devlin, Jonathan Uesato, Rishabh Bhupatiraju, Rishabh Singh, Abdel-rahman Mohamed, and Pushmeet Kohli. Neural program meta-induction. In Advances in Neural Information Processing Systems (NeurIPS), 2017.
Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-lcarning for fast adaptation of deep networks. International conference on machine learning. pp. 1126-1135. PMLR, 2017.
Sumit Gulwani. Automating string processing in spreadsheets using input-output examples. ACM Sigplan Notices, 46(1):317-330, 2011.
David Ha and Jürgen Schmidhuber. Recurrent world models facilitate policy evolution. Advances in neural information processing systems, 31, 2018.
Jason Hong. Maxwell Nye, Joshua B Tenenbaum, and Charles Sutton. Latent programmer: Discrete latent codes for program synthesis. In Advances Neural Information Processing Systems (NeurIPS), 2020.
Holger H. Hoos and Thomas Stützle. Stochastic Local Search: Foundations and Applications. Elsevier/Morgan Kaufmann, 2004.
Minyoung Huh, Brian Cheung, Pulkit Agrawal, and Phillip Isola. Straightening out the straight- through estimator: Overcoming optimization challenges in vector quantized networks. In Interna- tional Conference on Machine Learning, pp. 14096 14096-14113. PMLR, 2023.
Idress Husien and Sven Schewe. Program generation using simulated annealing and model checking. In Rocco De Nicola and Eva Kühn (eds.), Software Engineering and Formal Methods, pp. 155-171, 2016. ISBN 378-3-319-41591-
Eric Jang, Shixiang Gu, and Ben Poole. Categorical reparameterization with gumbel-softmax. In International Conference Learning Representations (ICIR), 2017. 2017.
Thomas Kipf, Ethan Li, Hanjun Dai, Zornitsa Kozareva, Jiaming Song, Arvind Neelakantan, and Max Welling, Compile: Compositional imitation learning and execution. International Conference Machine Learning (ICMI.), 2018.
Brenden Lake and Marco Baroni. Generalization without systematicity: On the compositional skills of to-sequence recurrent networks. In International conference on machine learning, pp. 2873-2882, PMLR, 2018.
Adrian Laúcucki, Jan Chorowski, Guillaume Sanchez, Ricard Marxer, Nanxin Chen, Hans JGA Dolfing, Sameer Khurana, Tanel Alumãe, and Antoine Laurent. Robust training of vector quantized bottleneck models. In 2020 International Joint Conference on Neural Networks (IJCNN), pp. 1-7. IEFF, 2020.
12

---

Published as a conference paper at ICLR 2026
Matthew V Macfarlane and Clément Bonnet. Searching latent program spaces. arXiv preprint arXiv22411.8876, 2024.
Chris J Maddison, Andriy Mnih, and Yee Whye Teh. The concrete distribution: A continuous relaxation of discrete random variables. arXiv preprint arXiv:1611.00712 2016.
Augustus Odena, Kensen Shi, David Bieber, Rishabh Singh, Charles Sutton, and Hanjun Dai.
BUSTLE: Bottom-up program synthesis through carning-guider exploration. In International Conference on Learning Representations, 2021.
Scott Reed and Nando De Freitas. Neural programmer-interpreee International Conference on Learning Representations (ICLR), 2016.
Quazi Asif Sadmine, Hendrik Baier, and Levi Lelis. Language models speed up local search for finding programmatic policies. Transactions on Machine Learning Research, 2024. ISSN 2835-8856.
Zhi Shi, Maxwell Nye, Rudy Bunel, Rishabh Singh, Pushmeet Kohli, and Alexander L Gaunt. Exedec: Execution decomposition for compositional generalization in neural program synthesis. In Advances Neural Information Processing Systems (NeurIPS), 2023.
Armando Solar-Lezama, Rodric Rabbah, Rastislav Bodik, and Martin Rinard. Combinatorial sketching for finite programs. In Computer Aided Verification, volume 4144 of Lecture Notes in Computer Science, pp. 404-200. Springer, 2006.
Phillip D Summers. A methodology for lisp program construction from examples. Journal of the ACM (JACM), 24(1):161-17) 1977.
Richard Sutton, Doina Precup, and Satinder Singh. Between mdps and semi-mdps: framework for temporal abstraction in reinforcement learning, Artificial intelligence, 112(1-2):81--11, 1999.
Aaron den Oord, Oriol Vinyals, and Koray Kavukcuoglu. Neural discrete representation learning. In Advances in Neural Information Processing Systems, 2017.
13

---

Published as a conference paper at ICLR 2026
A DATASETS
A.1 COMPOSITIONALITY BENCHMARK
We constructed the Compositionality Benchmark using own sampling and problem synthesis procedures to evaluate distinct facets of compositional reasoning. The benchmark comprises three main tasks designed to probe different dimensions of generalisation. For each task, dataset sizes were chosen to provide a robust training scale and sufficient evaluation coverage. The three splits are:
Permutation Length Generalisation (Shift-I). This task measures extrapolation on parameterized function. The model learns left_ shiff ft (n) operation sequence. Training is restricted to a small, contiguous range of integer shifts, specifically for n E {1,2,3, 4, 4,5). Evaluation is performed on larger, unseen shift values, {6, 7, 10). This measures the model's s ability to generalise beyond the magnitude of parameters observed during training.
2. Sub-Function Extraction (Shift-P). This task tests whether model can infer a general, parameterized function from sparse and non-contiguous examples. The underlying operation is again
shift (n). Training is performed on sparse set of non-adjacent shift values (c.g., n E {5, 7, 9}). Evaluation then probes generalisation to a different, unseen range of values (e.g., n {1, 2, ()), testing whether the model has learned the abstract concept of "shifting by n" rather than memorizing separate programs for each training example.
3. Composition of Primitives (Comp-I). This task evaluates whether model can compose primitive functions has only seen in isolation. The model is provided with a library of over 20 primitive sequence-fo-seqquence operations (e.g., reverse, shi ft_lef___ increment_20 During training, the model only sees programs consisting of a single primitive operation. For evaluation, it must execute programs that are compositions of two more primitives, testing for generalisation from individual operations to novel compositions.
Table 2: Dataset sizes for the Compositionalityy Benchmark.
Split
Size
Train
2,000,000
Test
10,000
A.2 DEFPCODER
We use the DeepCoder domain and adopt the compositional generalisation splits from the ExeDec codebase Shi et al. (2023). Following their Domain-SSecifer Language (DSL. and splitting procedures, we sampled 2, 2,000,000 training tasks and 10,000 test tasks. The five splits are designed to probe different dimensions of compositional generalisation:
1.
Training programs contain 1-4 lines, while test programs have length This evaluates whether models can extrapolate deeper compositions than observed during training Balog et al. (2016).
2. Compose-Diffeerntt Different-Conceppt Operations are partitioned into two groups: (i) all first-order operations plus Map, and (ii) all remaining higher-order operations. Training only composes within a single group. while test programs require mixing across groups. This measures cross-concept compositionality.
3. Switch-CConcpt-Orderr Training tasks always compose operations in fixed group ordering (e.g., first-order + higher-order), while test tasks reverse the ordering. This evaluates whether models can generalise to new sequential structures of concepts.
4. Compose-New-Operatinn The held-out operation is Scanll. Training tasks either use Scanil in isolation (25% of tasks) exclude it entirely, while test tasks require Scanll to be composed with other operations. This probes whether the model can generalise an operator from isolated usage to composed contexts.
14

---

Published as a conference paper at ICLR 2026
5. Apperation-Funccinaali Training only uses Scanll with lambdas (-) and min. Test tasks require Scanll with new lambdas (+), (x), and max. This tests whether models can extend their understanding of known operator by analogy to other operations.
Table 3: Dataset sizes for DeepCoder, generated using the ExeDec repository.
Split
Size
Train
11,600,000
Test 10,000
15

---

Published as a conference paper at ICLR 2026
B HYPERPARAMETERS
Table 4: Model Hyperparameters for NLL The same default configuration was used across all datasets.
Hyperparameter
Shift-L
Shift-P
Compose
DeepCoder
Model Architecture
Model Dimension (dmodel)
128
128
128
128
Number of Heads (Thead)
8
8
Feed-Forward Dimension (dw)
512
512
512
512
Encoder Layers
2
4
Decoder Layers
2
2
Positional Embedding
Sinusoidal 2.0
Sinusoidal 2.0
Sinusoidal 2.0
Sinusoidal 2.0
Gradient Clip Norm
Program Generation
Program Vocabulary Size Program Length (Training)
512
512
512
512
10
10
4
Training
Learning Rate
2c-4
2c-4
2e-4
2e-4
Num Batches
100k
100k
100k
200k
Gumbel-Softmax Sampling (Program)
Use Program Gumbel
True
True
True
True 8.0
Start Temperature
8.0
8.0
8.0
End Temperature
0.5
0.5
0.5
0.5
Anncaling Batches
20,000
20,000
100,000 Exponential False
200,000
Decay Strategy
Exponential False
Exponential False
Exponential
Through Straight-Through
False
Gumbel-Softmax Sampling (Decoder Layer)
Use Layer Gumbel
True
True
True
True
Start Temperature
2.0
2.0
2.0
2.0
End Temperature
0.5
0.5
0.5
0.5
Anncaling Batches
20,000
20,000
100,000
200,000
Decay Strategy
Exponential False
Exponential False
Exponential False
Exponential
Straight-Througe
False
Regularization
Losses
Encoder Loss Coefficient
0.00001
0.00001
0.00001
0.00001
Search
Gradient Steps
100
100
100
100
Number of Initializations
1024
1024
8192
1024
Std for initialisation
7.5
7.5
7.5
7.5
16

---

Published as a conference paper at ICLR 2026
Table 5: Model Hyperparameters for LPN. The same default configuration was used across all
datasets. Hyperparameter
Shift-L
Shift-P
Compose I
DeepCoder
Model Architecture
Model Dimension (dmodel)
512
512
512
512
Number of Heads (Nhead)
8
Feed-Forward Dimension (dr)
512
512
512
512
Encoder Layers
2
2
Decoder Layers
2
2
Use Layer Normalization
True Sinusoidal
True
True
True
Positional Embedding
Sinusoidal
Sinusoidal
Sinusoidal
Dropout Rate
0.0
0.0
0.0
0.0
VAE Beta (3)
0.001
0.001
0.001
0.001
Gradient Clip Norm
2.0
2.0
2.0
2.0
Training
Learning Rate
2e-4 100k
2e-4
2e-4 100k
2e-4
Num Batches
100k
200k
17

---

Published as a conference paper at ICLR 2026
Table 6: Model Hyperparameters for D-LPN. The same default configuration was used across all datasets.
Hyperparameter
Shift-L
Shift-P
Compose I
Model Architecture
Model Dimension (dmodel)
512
512
512
Number of Heads (Nhead)
8
8
8
-erd-Fd Dimension (dR)
512
512
512
Encoder Layers
2
2
2
Decoder Layers
2
2
Use Layer Normalization
True Sinusoidal 0.0
True Sinusoidal 0.0
True
Positional Embedding
Sinusoidal
Dropout Rate
0.0
Gradient Clip Norm
2.0
2.0
2.0
Training
Learning Rate
2e-4 100k
2e-4 100k
2e-4 100k
Num Batches
Gumbel-Softmax Sampling (Program)
Use Program Gumbel
True
True
True
Start Temperature
8.0
8.0
8.0
End Temperature
0.5
0.5
0.5
Annealing Batches
20,000
20,000
100,000
Decay Strategy
Exponential False
Exponential False
Exponential
Straight- Throough
False
Gumbel-Softmax Sampling (Decoder Layer)
Use Layer Gumbel
True
True
True
Start Temperature
2.0
2.0
2.0
End Temperature
0.5
0.5
0.5
Annealing Batches
20,000
20,000
100,000
Decay Strategy
Exponential False
Exponential False
Exponential False
Straight- Thhhugh
18

---

Published as a conference paper at ICLR 2026
Table 7: Model Hyperparameters for In-context. The same default configuration used across all
datasets.
Hyperparameter
Shift-L
Shift-P
Compose I
DeepCoder
Model Architecture
Model Dimension (dmodel)
512
512
512
512
Number of Heads (Nhead)
8
Feed-Forward Dimension (dw)
512
512
512
512
Encoder Layers
2
2
Decoder Layers
2
2
Use Layer Normalization
True Sinusoidal
True Sinusoidal 0.0
True
True
Positional Embedding
Sinusoidal 0.0
Sinusoidal
Dropout Rate
0.0
0.0
Gradient Clip Norm
2.0
2.0
2.0
2.0
Training
Learning Rate
2e-4 100k
2e-4 100k
2e-4 100k
2e-4 200k
Num Batches
19

---

Published as a conference paper at ICLR 2026
C GUMBEL-SOFTMAX TEMPERATURE ANNEALING ABLATION
In this section, we investigate how the base NLI model learns discrete program representations under different Gumbel-Softmax lemperature annealing schedules. Stable training requires careful control of the program- and layer-level temperatures, and here we ablate the effect of the shared annealing duration the Shift-L dataset.
Our model uses two independent Gumbel-Softmax temperatures:
Program temperature (Tprog): controls the discreteness of the tokenised high-level program.
Layer temperature (Nayer): controls the discreteness of per-token execution choices within each layer.
Both temperatures are linearly annealed over the same number of steps (Tprog" 4.0-+0.5, Taaer' 2.0-0..5), after which they are held fixed at 0.5 for the remainder of training. All runs use 100k total training steps and identical hyperparameters, varying only the shared annealing duration.
Table 8: Ablation of the shared Gumbel- temperature annealing duration on Shift-L (in- distribution accuracy; 100k total training steps, averaged over 3 seeds).
Annealing duration
NLI (ID)
1k steps
0.00
5k steps
0.41
10k steps
1.00
20k steps
1.00
50k steps
1.00
100k steps
1.00
Short annealing schedules (1k-5k steps) fail to produce stable discrete program representations. Accuracy increases sharply at 10k steps, after which all longer schedules perform identically. This shows that the model is robust the exact duration once minimal threshold is reached, and that default 20k-step schedule lies well within the stable regime for Shift-L.
20

---

Published as a conference paper at ICLR 2026
D PROGRAM ENCODER
In this section, we describe the program encoder used alongside the input-output (I/O) encoder. The program encoder can be leveraged when data available to provide stronger, more direct training signal to the neural executor. When training relies solely on the I/O encoder, the discrete program latents can become bottlenecked by the encoder's limited inductive capacity, particularly on harder tasks. Providing ground -ouund-truth programs during training alleviates this issue and allows the executor learn the correct program primitives more effectively. Below, we outline the tokenisation scheme, architecture, and training procedure.
D.1 TOKENISATION
Programs are whitespace-tokemie according to the DeepCoder DSL. The full vocabulary contains 153 tokens:
special tokens (PAD, <BOS>, <EOS>, ), 4 structural tokens (=, INPUT, [, }), 15 operations, 19 lambda functions, 10 variable tokens x x0-x9, 9, and integer literals from -50 to 50.
Example
String representation: x0 = INPUT | x1 = Map (+1) x0 | x3 Head x2
x2 Filter (>0) x1
Token sequence (with <BOS> and <BOS>): <BOS> x0 INPUT
x1 Map
(+1) x0
x2 Filter (>0) x1 x3 Head x2 <EOS>
Tokenised sequence (token IDs): 42 4 5 43 18 23
42
3 44 19 33
43 3 45
44 2
D.2 ARCHITECTURE
The program encoder uses the same architecture and hyperparameters as the I/O encoder in all experiments. Both encoders share the same codebook and use Gunbel-Softmax relaxation to produce discrete latent programs.
D.3 TRAINING WITH THE PROGRAM ENCODER
Access to ground-truth programs P allows the model to bypass the inductive bottleneck of the I/O encoder and directly expose the executor correct program structures. We do introduce separate program decoder; instead, both encoders share the neural execution decoder Pa.
During training, the program encoder maps each tokenised program P discrete latents using the shared codebook. The total objective adds an auxiliary reconstruction term weighted by Aprog- which we set 1.0 in all experiments.
Free Li0 + >xpog fepog
To ensure both encoders learn unified latent space, control gradient flow follows. Gradients from Epog update both the program encoder parameters and the executor, whereas gradients from Lio do not update the executor (stop-gradient), forcing the I/O encoder align with the program encoder's s higher-quality latents.
At test time, the program encoder is discarded. Only the trained I/O encoder and executor used for inference and search.
21

---

Published as a conference paper at ICLR 2026
E COMPARISON TO DISCRETE LATENT PROGRAMMER
We compare our model with the Discrete Latent Programmer (DLP) (Hong et al. 2020). which also employs discrete latent codes for program induction. While both approaches share this high-level similarity, they diverge substantially in their architectures, training assumptions, and mechanisms for test-time adaptation. The key differences lie in how programs are executed and how search is performed at inference.
E.I PROGRAM EXECUTION AND SUPERVISION
In our model, program tokens are interpreted by a recurrent neural interpreter that applies each token operation to intermediate state. This sequential execution enables variable-length programs, promotes compositional reuse of learned primitives, and allows the model to be trained end-to-end on raw input-output examples alone. Since outputs be directly compared targets, no ground-truth program annotations are required.
DIP, by contrast, does not include neural interpreter. Its decoder predicts full program sequences from latent codes, and training requires access to the underlying program representations. This reliance on program supervision restricts DLP domains where the generating programs are known and domain domain-specifie language is available, limiting its applicability beyond synthetic benchmarks.
E.2 TEST-TIME PROGRAM SEARCH
further distinction arises in test-time adaptation. Our model exploits the differentiability of the neural interpreter refine latent program embeddings via gradient- based search. This procedure enables efficient adaptation: initial program guesses from the encoder can be continuously optimized to better fit new examples, even when they require novel compositions not during training.
In contrast, DLP performs beam search in the discrete program space. This search is combinatorial, lacks gradient guidance, and cannot refine programs based on execution error. As result, DLP's generalisation is hindered, particularly in out-of-distribution settings where small corrections to predicted program necessary. By enabling gradient-based refinement in relaxed latent space, our model provides a more powerful and adaptive mechanism for program synthesis.
22

---

Published as a conference paper at ICLR 2026
F NLI PROGRAM REPRESENTATIONS
In this section, provide examples of the discrete latent codes discovered by NLI, both for in-distribution programs and for how these primitives are composed by search to generalise out-of- distribution (OOD).
F.1 SHIFT-L
We study the task of shifting sequences to the left. During training, the model observes shifts of length I (inclusive). principle. the network could leam a separate token for each shift. Instead, it discovers more efficient representation by reusing tokens. Specifically, it learns a token (231) that corresponds to a single left shift. By repeating this token, the network composes shifts of lengths and 3. For larger shifts, it introduces second token (476), which corresponds to two-step shift. This enables the model to combine primitives to generate more complex shifts.
For example, a shift of 4 is represented one two-step shift plus two one-step shifts. At test time, when generalising OOD to larger shifts, the model composes primitives the same manner. For instance, to represent an 8-step shift, it uses four single-shift tokens and two two-shift tokens. This demonstrates both compression (a small set of primitives) and compositionality (systematic reuse of primitives).
Example 1: Shift Left by
Task Specification
Input: [8, 2, 5, 9, 1, 6, 3, 4, 7, 0]
Output: [2, 5, 9, 1, 6, 3, 4, 7, 0, 8]
Ground Truth Program: y left_shtt (x, NLI Program Representation: 231
12
13
Example 2: Shift Left by
15
16
Task Specification.
17 Input: [4, 6, 7, 1, 9, 0, 3, 8, 5, 2]
Output: [7, 1, 9, 0, 3, 8, 5, 2, 4, 61
20
Ground Truth Program: y left shift (x, 21
21
NLI Program Representation: 231 231
22
24
25
Example 3: Shift Left by 3
26
Task Specification.
Input: 13, 4, 0,
9, 5,
29
Output: 10, 6, 2, 9, 5, 8, 1, 3, 7, 41
30
31
Ground Truth Program: left_shife (x, 3)
NLI Program Representation: 231 231 231
34
35
36
Example 4: Shift Left by 4
38 Task Specification:
39 Input: [5, 1, 9, 2, 8, 6, 0, 7, 3, 4]
40
Output: [8, 6, 0, 7, 3, 4, 5, 1, 9, 21
Ground Truth Program: left shi (x,
23

---

Published as a conference paper at ICLR 2026
NLI Program Representation: 231 476 231
45
46
Example 5: Shift Left by 5
49
Task Specification:
50
Input: 19, 4, 1, 5, 2, 1, 6, 0, 3, 81
51
Output: 17, 6, 0, 3, 8, 9, 4, 1, 5, 21
53
(x, NLI Program Representation: 231 476 476
Ground Truth Program: y left shi left_shiff
54
55
58
Example (OOD): Shift Left by
59
60
Task Specifi fincificaiio::
Input: [0, 1, 2, 3, 4, 6, 7, 8,
Output: [8, 0, 1,
4, 5, 6,
63
64
Ground Truth Program: - left_ shi (x, 8) NLI Program Representation: 231 231 231 231 476 476
65
Listing I: Learned NLI Program Representations for List Shift Tasks.
24

---

Published as a conference paper at ICLR 2026
G APPENDIX: TOKEN REUSE REGULARISATION LOSS
To bias the model toward learning a compact and reusable set of primitives, we introduce a regularisa- tion term applied the encoder's s output distribution. Since the encoder generates the latent program representation, this regulariser directly shapes the structure of the learned latent space. We refer to this term the token reuse loss. Its role is discourage the encoder from spreading probability mass across too many distinct program tokens within a batch. By promoting reuse, the model is incentivised discover small set of fundamental operations that can recombined to solve broad range of tasks, thereby fostering compositional generalisation.
Formally, the loss is defined as the expected number of unique program tokens used across training batch. Crucially, this expectation can be computed in differentiable form, enabling direct optimisation via gradient descent.
Let P denote the tensor of token probabilities output by the encoder, with dimensions (B, V), where the batch size, N is the program length, and V is the vocabulary size. The probability of token & being chosen at position in sequence is denoted ps,í,t-
To approximate the probability that token never appears in the batch, we make the simplifying assumption that token draws are independent across positions and across examples. Under this assumption, the probability of never selecting token A: is:
B
PPokeen never appears)
Pb.1k))
(4)
For numerical stability, we compute this in log-space:
N log Ptokeen & never appears) = Σ Σ
log(1 pb,
(5)
11
The probability that token appears at least once in the batch is therefore:
Ptooenn k appears) = 1 -
log(1 Ph.i.t)
(6)
By linearity of expectation, the expected number of unique tokens used in the batch is:
Lreuse
P(toeen & appears).
PRACTICAL CONSIDERATIONS
The token reuse loss added to the encoder loss with weight Areuse As batch-level statistic, it can be sensitive batch size and may be unstable for small batches. In practice, we used large batches and did not observe instabilities. Importantly, the loss must not dominate training. We therefore apply very small weight, ensuring that it provides only gentle inductive bias toward compact vocabularies. This prevents collapse into degenerate solutions such as single-token language, which would be too limited to represent complex tasks.
25

---

Published as a conference paper at ICLR 2026
H THE USE OF LARGE LANGUAGE MODELS (LLMS)
In this work, large language models (LLMs) were used solely as a tool for polishing the writing, specifically to remove grammatical and spelling errors. They did not contribute research ideation or any other significant aspects of the paper.
26


Reviews:
[{"review_id": "xasJG4VGyi", "reviewer": "Reviewer_MBC4", "summary": "This paper introduces Neural Language Interpreter (NLI), a neurosymbolic technique for program induction, which is based on having a neural network predict an intermediate program and interpreting it differentiably. Notably, the intermediate program representation is learned, so the architecture isn't fixed to a particular DSL! The predicted program is then refined using a neural executor. The paper then compares NLI to several baselines, establishing its general effectiveness. In particular, the paper emphasizes the ability for compositional generalization, and boasts strong results on OOD-generalization when compared to baselines.", "questions": "The paper makes an argument that the internal representations are more flexible and effective than hand-designed DSLs. Further analysis/experimentation of this point could prove interesting. \n\nWhile an intermediate symbolic program is predicted, it isn't explicitly manipulated like the approaches cited in section 6 paragraph 1 would do. Accordingly, it seems that the overall approach still leans to neural processing. Have the authors considered doing symbolic manipulations of the intermediates? Since the intermediate representation is relaxed, this may not be explicitly possible, but it still seems like this representation could be interpreted/manipulated in some way. For example the analysis in Appendix D is quite interesting, and building on this could be a promising direction for future work.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "The proposed method is original, sound, and well-described. \n\nThe OOD generalization results in Table 1 are compelling.\n\nThe ablation in section 5.2 solidifes the method, giving clear evidence for why it improves better than the baselines.\n\nWhile NLI doesn't outperform every other method on the DeepCoder benchmark, performance is convincing. \n\nComparisons to existing work are done well, and the authors demonstrate a good understanding of the literature.", "weaknesses": "Further explanations of the learned intermediate language and differentiable interpreter would help the paper significantly (e.g. content from Appendix D could be partially reflected earlier in the paper, like in Section 5.1.1). I'd recommend partially using the extra page for camera-ready for this, since a lot of the paper's space is already well-allocated. \n\nCommentary/explanations of DeepCoder benchmark performance would also help. While the results support some scalability, it seems further work might need to be done before the approach scales successfully, especially to more general programs (e.g. arbitrary Python programs). \n\nThe authors self-identified limitations, e.g. parameterized functions in particular (and especially limitations like this which effect expressivity).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "6oS7XD2FTS", "reviewer": "Reviewer_Lj8j", "summary": "The paper considers the program-by-example program synthesis setting. It presents the Neural Language Interpreter (NLI) which is an approach that aims to combine the complimentary strengths of symbolic and neural program synthesis methods. The aim is for NLI to learn its own discrete programming language from the training data.\n\nNLI uses an Encoder-Decoder architecture, where the latent space represents a program and consists of T vectors (representing the maximum program length), where each vectors can be one of K values (representing the number of different symbols in the learned programming language). One of the K values is the “skip” command which allows for the generated program to be of varying length.\nThe encoder maps example input-output pairs to a program, while the decoder sequentially executes the generated program’s commands to make a prediction on a new input.\n\nNLI makes use of the Gumbel-Softmax trick and is trained with a VAE-like objective, where the latent distribution regularization loss (referred to as the encoder loss) is designed to encourage primitives to be reused.\n\nAt test time, the encoder can be used to provide an initial prediction of the target program. Afterwards, due to the differentiability of the decoder, NLI can optimize its program using gradient optimization in order to improve its prediction accuracy.\n\nThe method demonstrates good program length extrapolation and good performance on novel composition tasks.", "questions": "Could ground truth program representations be incorporated into the latent space supervision? Perhaps at a later stage of training?\n\nReconstruction loss: would it not help to also reconstruct all training pairs to make sure the program covers all examples?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Getting around the limitations of symbolic methods, by learning a DSL appears to be a promising direction. The paper represents an important step towards this goal. The method appears to be novel and a creative combination of existing ideas. Apparently novel ideas include: the VAE-like architecture for program synthesis, the discrete program latent space, as well as the test-time gradient optimisation of the initially proposed program.", "weaknesses": "Presentation: There are two important details missing from the main text. First, the encoder loss is not specified in section 4, and only a high-level intuition is provided. This makes it difficult to evaluate whether this is a key part of the method and an important innovation. Second, when discussing the custom suite of benchmarks in section 5, an explanation of the basic operations is missing, making it difficult to evaluate the difficulty of the benchmarks.\n\nWhile the limitations are discussed, a more comprehensive analysis would be beneficial to the paper. Currently, the paper comes across as a proof-of-concept that this is a promising direction, but the lack of clearly outlined limitations, coupled with limited evaluation weakens its broad claims.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "zpI02j5dfJ", "reviewer": "Reviewer_7aj7", "summary": "In this work the authors advance a new program induction framework that involves the synthesis by a transformer of a series of tokens representing a program. The sequence is then put through a Gumble Softmax to enforce its discrete nature and then passed to the decoder, which is a recurrent network that processes each token in the program and evolves a particular state then produces an output. In order to ensure generalization, test time optimization is performed in order to optimize the program to match the given examples. This technique is significantly better than other similar techniques such as TTT or LPN when it comes to generalizing to programs of novel lengths or composing programs together in simple domains, and remains competitive in more realistic settings.", "questions": "Why average across the different input embeddings? This seems to reduce the expressivity of the model.", "limitations": "", "rating": 2, "confidence": 3, "soundness": 2, "presentation": 4, "contribution": 3, "strengths": "The idea of this paper is simple and clear\n\nThe results in Section 5.1 are compelling, and demonstrate that in contexts where generalization is paramount, NLI performs very well, and generates programs that are interpretable.", "weaknesses": "The main weakness of this paper is the fact that NLI’s outperformance of baselines is not demonstrated in any nontrivial domain. Section 5.4 demonstrates that NLI has competitive performance in real settings, but in no setting does it's unique generalization ability as described in Section 5.1 lead to an overall improvement. Ideally, some nontrivial domain or a modification of an existing one should be identified where compositionality and generalization are key so NLI can demonstrate its better performance. (e.g., filter an existing domain’s dataset such that the training dataset contains items of length <k and the test dataset contains items of length >k)\n\nMinor:\n\n334-335: use a term other than baseline performance here, “baseline\" is also what you are using to describe the techniques you compare against.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "RK0vfHcWU2", "reviewer": "Reviewer_xGro", "summary": "This paper introduces the Neural Language Interpreter (NLI), a novel architecture that learns a discrete, symbolic-like programming language and a differentiable interpreter end-to-end. The model is evaluated on several compositional generalization benchmarks and demonstrates strong out-of-distribution performance, particularly when combined with gradient-based search at test time.", "questions": "Are there any influential applications of Gumbel-softmax in any area? Could you give me some examples?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- Neuron-symbolic is an important research area\n- The model shows impressive compositional generalization results\n- Using a neural executor is a nice idea, which is similar to a world model", "weaknesses": "- Gumbel-softmax has been applied to many research areas to publish papers. However, it seems that no influential results have been produced by Gumbel-softmax. I doubt the impact of this paper, too.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)