Neural Language Interpreter learns a program language and searches it with gradients

The benchmark result that matters is the gap between NLI with gradient search and every other inference path. On the paper's custom programming-by-example suite, NLI Gradient Search reaches 99% OOD accuracy on length extrapolation, 100% on primitive extraction, and 91% on novel composition. Plain NLI reaches 0%, 0%, and 17%; the rest of the neural baselines are also near zero on the shift tasks. 1

That makes the paper's contribution more specific than "a neural model learns programs." The model only generalizes when it searches for a program after the encoder proposes one. NLI turns a discrete, variable-length program representation into a differentiable object, then uses gradient ascent to revise it against the observed input-output examples. The result is a neural-guided search procedure with a learned token vocabulary, not another black-box predictor that happens to emit the right answer.

The paper defines program induction in the programming-by-example setting: infer an unknown program from input-output pairs, then predict the output for a new input. Training and test tasks expose examples, not the underlying program representation. This matters because the model cannot simply copy a symbolic trace or learn a supervised parser for the target DSL. 1

NLI has two learned parts. Its encoder, the program inductor, maps a set of examples to a sequence of distributions over a codebook. Gumbel-Softmax makes those categorical choices trainable while preserving pressure toward discrete tokens. Its decoder, the neural interpreter, consumes one token at a time and recurrently updates an execution state. A dedicated skip token lets the same maximum-length representation express shorter programs. The interpreter therefore executes a sequence rather than collapsing the whole task into one continuous vector. 1

The training loss reinforces this arrangement. NLI leaves one example out of each specification, asks the inferred program to predict it, and adds a differentiable penalty for using too many unique codebook entries in the batch. The penalty is a compression bias, but it is not library learning in the DreamCoder sense. It encourages reuse inside a latent neural vocabulary; it does not extract named functions into a growing symbolic DSL with a Bayesian cost model.

At test time, the encoder supplies an initial program guess. NLI then relaxes the token sequence into continuous embeddings and optimizes those embeddings with gradient ascent on the likelihood of the specification. Temperature annealing gradually sharpens both token selection and execution. Multiple random starts are run in parallel to reduce the chance of settling in a poor local optimum. 1

The paper's shift experiment shows what this buys. During training, the model sees left shifts of lengths 1 through 5. At test time, Shift-L asks for lengths 6 through 10. NLI discovers one token that behaves like a one-step shift and another that behaves like a two-step shift. Gradient search composes them for longer shifts, including an eight-step program, instead of assigning a new opaque code to each length. In Shift-P, the direction is reversed: the model trains on longer shifts and must recover shorter primitives. The same mechanism reaches 100% OOD accuracy there. 1

The selected benchmark results are:

The contrast is unusually clean. Discreteness alone does not explain the result: NLI without search is no better than the other neural variants on the shift tasks. The paper's ablations point to a three-way interaction between discrete inductor tokens, discrete interpreter behavior, and recurrent execution. Removing interpreter-side Gumbel sampling reduces the reported OOD score in the ablation to 5%, while removing inductor-side Gumbel sampling reduces it to 76% from a 97% base in that experiment. 1

The DeepCoder evaluation tests whether the idea survives a more familiar program-synthesis setting. The authors regenerated 11.6 million training tasks and use 10,000 test tasks. NLI and the other neural baselines learn from input-output examples, while the compared neuro-symbolic systems receive ground-truth program representations during training. The paper reports that NLI and LPN outperform earlier Latent Programmer and Transformer-based systems and are competitive with ExeDec, but it also notes that program annotations give the neuro-symbolic baselines an additional training signal. 1

DreamCoder's central loop alternates between solving tasks, extending a symbolic language with reusable abstractions, and training a neural recognition model on imagined and replayed problems. The recognizer guides later symbolic search inside the growing language. 2 NLI keeps the neural guidance idea but changes both sides of the interface: the vocabulary is learned as a latent codebook, and search happens by differentiating through the executor rather than enumerating symbolic programs under a Bayesian prior.

LAPS makes DreamCoder's interface more informed by language. Natural-language annotations guide joint learning of abstractions and neural search heuristics, and the resulting system improves libraries and search even when annotations are absent at test time. 3 NLI has no equivalent semantic naming channel. Its tokens acquire meaning through predictive utility and reuse, so the model can discover compositional behavior without a human-readable description, but the paper does not show that a researcher can inspect or edit those primitives as functions.

Stitch moves in the opposite direction from NLI. It is a symbolic compression system that synthesizes library functions from a corpus of DSL programs, using syntactic pattern matching to prune a top-down search. Its reported advantage over DreamCoder is computational: 3 to 4 orders of magnitude faster and 2 orders of magnitude less memory, with comparable or better compressivity. 4 NLI avoids that symbolic compression problem by placing the vocabulary inside a differentiable model, but it also gives up Stitch's explicit abstraction terms and its direct compression comparison.

LILO combines LLM-guided synthesis with Stitch compression, then adds AutoDoc so learned abstractions receive names and docstrings that can feed back into synthesis. 5 NLI is a cleaner test of whether neural search itself can support systematic recombination. It is also less of a software library: there is no wake-sleep accumulation across a corpus, no symbolic refactoring stage, and no documented API of learned primitives.

This places NLI beside the DreamCoder lineage rather than inside its full loop. DreamCoder, LAPS, Stitch, and LILO treat the library as an explicit object whose growth, compression, or documentation can be inspected. NLI treats the learned language as an internal interface between an example encoder and a recurrent executor, then uses that interface for local optimization at inference. The common idea is reuse; the mechanism and the evidence are different.

The paper is an arXiv preprint submitted on 20 April 2026 and listed as an ICLR 2026 paper. Its results are strong on the constructed compositionality suite, but they do not show that NLI can learn a useful DSL for an open-ended domain, recover abstractions that remain interpretable to humans, or replace symbolic search on large real-world programs. The DeepCoder comparison is also bounded by the supervision mismatch: NLI sees examples only, while some neuro-symbolic baselines see the target program representation. 1

The authors identify three engineering limits. Test-time gradient search is expensive. The current interpreter cannot express parameterized primitives such as add(k), conditional branching, or nonsequential control flow. And longer programs or larger vocabularies may create gradient pathologies, even though those failures were not observed in the reported experiments. 1

The right verdict is therefore narrower than "neural DreamCoder." NLI demonstrates that a model can learn a compact, discrete-like program vocabulary and use differentiable search to recombine it beyond the training distribution. That is a real neural-guidance result, and it answers a weakness visible in pure library-learning extensions: how a learned recognizer might actively reshape search. It does not yet answer DreamCoder's harder question about how reusable, inspectable libraries grow across tasks. The next test would need both: a persistent symbolic or semi-symbolic library and a learned search guide that can use it without turning the abstractions back into uninterpretable latent codes.