acceptodds
Under review as a conference paper at ICLR 2027

Neural Language Programming Can Generalize Out of Composition

Abstract

Artificial intelligence systems are showing promise on difficult tasks such as world modeling and abstract reasoning. A central challenge, however, is whether they can reuse what is learned *compositionally*, i.e., combine familiar operations in novel ways to address previously unseen tasks. We refer to this capability as *out-of-composition* (OOC) generalization, where a learner must recover reusable computational structure from input-output observations without access to the generating programs or a predefined executable language. Neural networks can learn directly from input-output observations, but typically represent the underlying computation implicitly and monolithically. Symbolic program synthesis is explicitly compositional, but assumes a predefined language. *Neural Language Programming* (NeuLP) bridges this gap by learning (1) a language consisting of a codebook of vectors that represent abstract operations, (2) an encoder that constructs a sequence out of that codebook based on input-output pairs from the task at hand, and (3) an interpreter that applies the selected sequence to a novel input. The discrete language is amenable to composition as well as search. Learning such a language requires discovering reusable operations without knowing the complexity of the programs that generated the training data or which learned operations can be trusted. NeuLP addresses the former with a program-space self-curriculum that progresses from shorter to longer programs, and the latter with a Bayesian execution-evidence prior that uses successful executions as evidence of operation reliability. Empirically, across four domains spanning list processing, ARC-AGI-style abstract reasoning, image editing, and cellular automata, we show that NeuLP generalizes to unseen recombinations and compositional depth, outperforming neural program synthesis baselines.

Primary area:
neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)
Keywords:
neural program synthesis, compositional generalization, out-of-composition generalization, neural language programming, learned executable languages, differentiable interpreters, continual learning

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_Jp2oOpenReview ↗
Rating
4
Confidence
3
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies out-of-composition (OOC) generalization, where a model solves previously unseen tasks by recombining learned operations in ways that differ from the compositions encountered during training.

To address this problem, the authors propose Neural Language Programming (NeuLP), a framework consisting of three stages:

  1. Language Acquisition: The model jointly learns a discrete neural language, a programmer that predicts sequences of operations, and a differentiable interpreter that executes them. A program-space self-curriculum progressively increases the allowed program length, while a Bayesian execution-evidence prior (BEEP) encourages the discovery of reliable and reusable operations.
  2. Compositional Optimization: With the learned modules frozen, the method employs execution-guided discrete search to discover successful programs for unseen compositions. It also introduces task-free dreaming to generate additional synthetic programs and input-output examples.
  3. Learning from Discovered Programs: The programmer is further trained using the programs discovered in the previous stage, improving its initial program proposals and reducing the need for extensive search. Overall, the framework is designed to first acquire a reusable neural language and subsequently improve its ability to compose the learned operations for OOC generalization.

The authors evaluate NeuLP on four newly proposed compositional benchmarks: Comp-II, CompARC, CompCIFAR, and CompLife. These benchmarks evaluate generalization to unseen recombinations and longer compositions of learned operations. The experimental results demonstrate substantial improvements over existing neural program synthesis approaches, including LPN and NLI.

Critical strengths
  • Clear motivation and well-presented methodology.

The paper is well written and interesting to read. The motivation is particularly compelling, with a clear discussion of the relevant literature and the challenges associated with compositional generalization.

I also appreciate how the methodological choices are closely connected to the identified challenges. Although NeuLP involves a relatively complex three-stage training procedure, each stage serves a clearly motivated purpose, making the overall framework coherent and understandable.

The figures substantially help readers understand the proposed framework, and the extended discussion of related work in the appendix further improves the clarity and readability of the paper.

  • Meaningful problem formulation and benchmark contributions.

The paper addresses OOC generalization, which I consider an important problem deserving further attention. The ability to reuse and compose previously learned operations to solve unseen problems is a meaningful direction for developing more generalizable learning systems.

Additionally, the authors introduce four compositional benchmarks designed to evaluate different aspects of OOC generalization. The distinction between unseen recombinations and increased compositional depth provides a clear and systematic evaluation framework.

Critical weaknesses

I do not identify a clear methodological flaw in the proposed framework or its evaluation under the stated OOC setting. However, I have some reservations regarding its broader applicability and practical significance, in the questions part.

Questions for authors
  • Limited demonstration of applicability beyond controlled compositional domains that can be composed with finite primitives.

The proposed framework, as well as much of the closely related neural program synthesis literature, focuses on domains where target functions can be represented as compositions of reusable operations.

The four proposed benchmarks follow this assumption, with each task generated from sequential compositions of a finite set of underlying primitive operations.

I acknowledge that this is precisely the setting that NeuLP aims to address, and that the controlled benchmarks provide a reasonable evaluation of its stated objective. Therefore, I do not regard their synthetic nature as an inherent weakness.

Nevertheless, I wonder whether the framework can be extended to more practical domains where the underlying computational structure is less explicitly defined or where discovering reusable operations is itself more challenging.

If NeuLP could demonstrate similar compositional generalization in such a domain, I believe its potential impact would be considerably greater. In particular, a practical application where OOC generalization is genuinely necessary would further strengthen the significance of the proposed approach.

1 comment
AuthorsOpenReview ↗

Response to reviewer Jp2o

Thank you for the positive review. We also agree that broader applicability is an important next step.

Question #1. Can NeuLP extend beyond controlled compositional domains to more practical settings?

We see NeuLP as a foundation for neural language program learning in richer real-world settings, rather than a complete solution to practical world modeling in its current form.

The current version makes several simplifying choices that we already discuss in the limitations. The language (library) is a flat finite codebook, and programs are bounded sequences. Both can be extended. A richer library could support more structured operations and stronger regularization over how they are learned and reused. The program representation could also support memory and control flow. For example, branching would require explicit control flow, while memory would allow sequential programs to store and reuse intermediate values. Another option is to have the programmer predict a graph directly.

These are natural extensions of the current framework. The core idea remains the same: learn an executable language from observations, then learn to program with it. We also see practical world-modeling settings as an important direction for future work.

Reviewer_SYhkOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
1
Soundness
2
Read review
Paper summary

The paper defines out-of-composition (OOC) generalization task, where a model sees only the input and output of program demonstrations and needs to learn to abstract compositional components and reuse them to solve unseen tasks. More specifically, it must handle unseen recombinations (Recomb. OOC) and deeper compositions (Length OOC).

The authors propose NeuLP with three learned instruments: a discrete codebook ("neural language"), a non-autoregressive programmer that maps support pairs to a token sequence, and a recurrent differentiable interpreter that executes one token per step.

Training has three stages: stage 1 learns the three instruments, stage 2 improves the programmer, and stage 3 re-trains the programmer on the already discovered programs.

The approach is validated on four synthetic suites.

Critical strengths
  • According to Table 1 and 7, NeuLP leads on Recomb. and Length OOC in every categorical domain, often by wide margins over all baselines.
  • The three-stage training is well-supported by the empirical results. Table 5. and Table 5 results support the central thesis that the language is a reusable, editable artifact.
Critical weaknesses
  • Evaluation is synthetic and possibly favors the method's inductive bias. All domains are straight-line compositions of a small set of primitives with exact-match outputs. This matches NeuLP's sequential grammar by construction.

  • Fairness of the comparison is not well justified. Search budgets and procedures differ across methods (128×100 discrete edits vs 8192×100 gradient steps vs 1024 samples). HRM's zero accuracy on Comp-II also suggests some baselines are under-tuned.

Questions for authors

I find it very hard to understand the experiments part without heavily relying on the appendix content.

  • What is NeuLP's performance without test-time search (Stage-3 zero-shot) in the full Table 1 setting, compared with baselines without search?

  • Can you evaluate on at least one external benchmark e.g. ARC-AGI?

4 comments
AuthorsOpenReview ↗

Response to reviewer SYhk - Part 1/2: Opening and Weaknesses 1-2

Thank you for the review. Given the nine-page limit, we placed much of the experimental analysis in the appendix. Based on the reviewers' feedback, we have added key clarifications to the main text and the additional experimental results to the appendix.

We address your concerns and questions below.

Weakness #1. The benchmarks are synthetic and match NeuLP's sequential inductive bias.

  1. Synthetic benchmarks. We agree that the benchmarks are quite synthetic, but they are closely connected to prior work rather than being constructed only around NeuLP. Comp-II extends the Comp-I benchmark from NLI to a more challenging compositional setting. CompARC and CompCIFAR follow related compositional settings studied in NEO; their datasets were not publicly available, so we constructed our own versions. CompLife was added to move the same question toward repeated dynamical transitions and world-model-like settings.

Another reason for using these controlled benchmarks is to isolate OOC generalization as the main object of study. More realistic domains introduce additional sources of generalization that are difficult to separate from composition itself. We see evaluation on more real-world settings as an important direction for future work.

  1. Sequential inductive bias. We already discuss the limitation of straight-line programs in the paper. Even in this restricted setting, OOC generalization remains challenging for existing baselines, as our results show. Extending NeuLP to more general programs with branching, loops, and recursion is an important direction for future work.

Weakness #2. The baseline comparison uses different search budgets, and HRM has zero Comp-II accuracy.

  1. Search budgets and baseline tuning. Since Comp-II, CompARC, and CompCIFAR follow settings closely related to those studied in NLI, LPN, and NEO, we started from their published architectures and training hyperparameters. We further tuned them for our benchmarks, including adjustments to approximately match parameter counts.

The search budgets are not directly comparable. NLI and LPN use gradient search, while NeuLP makes discrete token edits. In NLI, a gradient step may not change the selected token, whereas each NeuLP edit explicitly replaces one token with another. We therefore retained the published inference budgets: 8192×1008192\times100 for NLI and LPN, and 1024 sampled proposals without edits for NEO-S. NeuLP uses 128×100128\times100, with 64 times fewer search starts than NLI and LPN.

To compare computational cost more directly, we also measured inference time in seconds per OOC episode:

MethodInference budgetComp-IICompARCCompLife
NeuLP128×100128\times1000.75–5.240.01–177.020.01–336.50
NLI8192×1008192\times10050–512,073–2,7371,251–4,035
LPN8192×1008192\times10010.03–10.57521.55–562.151,388.57–1,589.29

Although individual search steps are not directly comparable, the wall-clock results show that NeuLP uses much less inference time than NLI and LPN across all three domains, while achieving higher OOC accuracy.

  1. HRM's zero accuracy on Comp-II. We also tuned Episode Transformer, HRM, and TRM, trying multiple configurations following their published setups. We were surprised by HRM's Comp-II result and investigated it further, but did not obtain nonzero exact-sequence accuracy. Its digit-level accuracy was only 10.22--10.34%, close to chance, so the result is not simply due to the strict exact-match metric. The same HRM implementation performs substantially better on CompARC and CompLife, which are closer to the 2D structured domains used in the original HRM paper (ARC, Sudoku, and mazes). HRM and TRM also use the same Comp-II input adapter and a similar training setup, yet TRM achieves nonzero accuracy.

Further tuning may improve HRM's performance, but NeuLP's advantage does not depend on this one baseline. In Table 1, NeuLP reaches 64.9 ± 2.1% on CompARC length OOC, compared with 29.9 ± 15.5% for the strongest baseline. On CompLife length OOC, the results are 74.0 ± 7.1% versus 3.2 ± 1.3%. These large gaps across multiple baselines and domains suggest that the overall advantage is unlikely to be explained by baseline tuning alone.

AuthorsOpenReview ↗

Response to reviewer SYhk - Part 2/2: Questions 1-2

Question #1. What is NeuLP's performance without test-time search, compared with baselines without search?

We combine NeuLP's Stage-3 zero-shot results from Appendix Table 28 of the submitted manuscript (Table 29 in the revision) with the baseline results in Tables 1 and 7. The NeuLP results include the corrected Comp-II entries noted in our response to Reviewer TV3n.

We also evaluate NLI and LPN without their test-time optimization, using their trained checkpoints. This gives a direct comparison between NeuLP's Stage-3 programmer and all baselines without test-time search.

Categorical domains — exact query accuracy (%), mean ± s.d.:

DomainSplitNeuLP Stage-3 0-shotNLI 0-shotLPN 0-shotEp. TFHRMTRM
Comp-IIRecomb. OOC98.41±2.7598.41 \pm 2.750.00±0.000.00 \pm 0.000.00±0.000.00 \pm 0.0031.8±27.131.8 \pm 27.10.0±0.00.0 \pm 0.011.1±15.311.1 \pm 15.3
Comp-IILength OOC69.44±6.3669.44 \pm 6.360.00±0.000.00 \pm 0.000.00±0.000.00 \pm 0.0010.7±9.310.7 \pm 9.30.0±0.00.0 \pm 0.012.7±17.012.7 \pm 17.0
CompARCRecomb. OOC75.00±3.2175.00 \pm 3.2131.82±7.8731.82 \pm 7.8743.64±6.1043.64 \pm 6.1067.3±3.867.3 \pm 3.818.2±11.118.2 \pm 11.144.5±21.444.5 \pm 21.4
CompARCLength OOC48.33±1.8948.33 \pm 1.892.78±1.642.78 \pm 1.643.07±1.553.07 \pm 1.5521.7±10.221.7 \pm 10.210.9±7.710.9 \pm 7.729.9±15.529.9 \pm 15.5
CompLifeRecomb. OOC48.95±28.0748.95 \pm 28.074.21±3.534.21 \pm 3.537.89±5.267.89 \pm 5.262.6±0.02.6 \pm 0.042.6±10.642.6 \pm 10.649.0±17.249.0 \pm 17.2
CompLifeLength OOC13.60±12.5613.60 \pm 12.560.00±0.000.00 \pm 0.000.00±0.000.00 \pm 0.000.0±0.00.0 \pm 0.00.1±0.20.1 \pm 0.20.1±0.20.1 \pm 0.2

NeuLP reports hard accuracy throughout this table. Without test-time search, NeuLP's Stage-3 zero-shot still leads on five of the six categorical OOC splits and is roughly on par with TRM on CompLife recombination. Notably, HRM and TRM use recursive reasoning at inference time.

CompCIFAR — normalized ℓ1\ell_1 (lower is better):

SplitNeuLP 0-shotNEO
Recomb. OOC0.011±0.002\mathbf{0.011 \pm 0.002}0.113±0.0040.113 \pm 0.004
Length OOC0.014±0.002\mathbf{0.014 \pm 0.002}0.163±0.0090.163 \pm 0.009

The additional OOC zero-shot comparisons are included in Appendix Tables 30 and 31 of the revision.

Question #2. Can you evaluate on an external benchmark such as ARC-AGI?

Our benchmarks build on compositional settings from prior work. Comp-II extends the Comp-I benchmark from NLI to a more challenging compositional setting. CompARC and CompCIFAR closely follow the settings studied in NEO. Since the NEO datasets were not publicly released, we constructed our own versions, which we will release upon acceptance. We also introduced CompLife to study composition over cellular-automaton rules, moving toward dynamical and world-model-like settings.

Beyond these, we have not found an existing PBE benchmark that specifically isolates OOC generalization. If the reviewer is aware of another suitable benchmark, we would welcome the suggestion.

ARC-AGI is certainly an interesting direction, but it involves several forms of generalization beyond OOC. For example, a model may need to apply a familiar operation with an unseen parameter, such as applying recolor(input, 2, 9) after only observing recolor(input, 1, 9) during training. This requires generalizing the operation itself, rather than just recombining learned operations.

There is also a practical difference: NeuLP's Stage 1 requires a larger stream of input-output examples to learn the executable language, while ARC-AGI provides only a few demonstrations per problem and no corresponding task generator. We see extending NeuLP to broader settings such as ARC-AGI as an important direction for future work.

Thank you for the detailed response. The HRM investigation and the zero-shot comparison against baselines without search are helpful. Also the clarification regarding the search budget and wall-clock comparison is straightforward. I also accept the argument about ARC-AGI. However, there are other established compositional benchmarks such as SCAN[1], which cited also cited in the paper, seems a natural test.

I maintain my slightly positive review.

[1]. Lake, Brenden, and Marco Baroni. "Generalization without systematicity: On the compositional skills of sequence-to-sequence recurrent networks." International conference on machine learning. PMLR, 2018.

Thank you for your follow-up and for taking the time to consider our additional experiments and clarifications. We appreciate your thoughtful feedback.

We also agree that SCAN is a relevant benchmark for compositional generalization. While SCAN itself is not a PBE benchmark, it could be adapted to one. This would require careful construction of support/query examples and handling of program equivalence and compositional depth to ensure well-controlled OOC splits, as discussed in Appendix B for our Comp benchmarks. We see this as a useful direction for future work.

Reviewer_TV3nOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

The authors address learning compositional capabilities from input-output pairs using NeuLP, which learns: a vector codebook language of operations, an encoder that reads the i/o pairs and selects a sequence of codebook tokens, and an interpreter that applies the sequences to inputs. Because the primitive functions and the sequence length that generate the i/o pairs are unknown, NeuLP uses a curriculum over program length as well as BEEP. They choose list processing, grid editing, image editing, and cellular automata as domains. They show NeuLP leads to unseen operation recombinations and generalization to higher compositional depth.

NeuLP has three stages: language acquisition, compositional optimization (freeze the encoder, language, interpreter and search/dream; successful trajectories are stored), learning from the dreaming bank (train only the encoder on the bank from stage 2). Note the search from stage 2 is also used at inference time.

Critical strengths
  • The language is learned from only i/o pairs, separating the programmer/encoder, language, and interpreter, strongly motivating the slot curriculum design since the true program length is unknown.

  • Table 6 continual language growth results where "reverse" is learned without forgetting old operations look very strong.

Critical weaknesses
  • Most OOC results seem to depend on search during test-time, e.g. in CompII stage-3 programmer gets 0% on recombination and length OOC whereas with search it gets close to 100% for both.
  • The training setup seems overly complex, given Stage 3 ablation shows little difference (table 27) and stratified directional GCU is within noise of random edits (Table 22). I wonder if stage 1 followed by search at test-time can achieve similar results as the full pipeline.
  • Some baseline comparisons do not get test-time search comparisons. This, in addition to the soft/hard accuracy combinations, make Table 1 hard to read.
  • Stage 2 dreaming/search is able to look at lengths of up to 6, making "length OOC" not truly at unseen depths.
  • Table 2 has "Continuous: 33.33 +/- 57.74", would like to see more seeds here to show gains for finite codebook vs continuous.
  • Would like to see an ablation removing length 1 examples from the curriculum
Questions for authors
  • Would like to see evaluation on lengths higher than 6 since lengths up to 6 can be seen from the search/dreaming bank in Stage 2.
  • Would like to see an ablation showing results without search/dreaming.
  • How does computational cost compare for NeuLP vs other methods? Wall-clock time?
  • "Table 5 compares Stage 1 and Stage 3 on the same CompARC Stage 2 support and query examples; only the programmer checkpoint changes" in Appendix C.5.4, does this mean part of the eval set in Table 5 came from the search bank that was trained on? If so, would like to see results on the evaluation set where tasks from the search bank are removed.
5 comments
AuthorsOpenReview ↗

Response to reviewer TV3n - Part 1/4: Opening and Weaknesses 1-2

Thank you for raising these points. We would first like to clarify two aspects of NeuLP.

  1. Search is part of NeuLP's inference procedure. All methods receive the same support PBE UU and query input xqx_q for each OOC problem. NeuLP searches using only these support examples, without additional supervision. NLI, LPN, and NEO also use the same UU in their test-time inference procedures, while HRM and TRM are trained on these OOC support examples in our evaluation. A central architectural advantage of NeuLP is its learned executable language, which allows the model to either predict a program directly or search over compositions of learned operations. If search solves a length-6 OOC problem, NeuLP has solved it using the same available input-output information.

  2. Stage 3 makes knowledge discovered through search and dreaming reusable. Without Stage 3, successful programs remain isolated search results, and the system may need to search again when encountering the same compositions. Stage 3 trains the programmer on these discoveries, allowing it to solve previously discovered compositions directly and provide better initial proposals for future search. This also supports continual learning: the cycle can be repeated to extend the language while retaining previously learned operations, as demonstrated by our language-growth experiment in Table 6.

Weakness #1. Test-time search appears to account for most OOC performance.

Thank you for catching this. The two Comp-II Stage-3 zero-shot entries in Appendix Table 28 of the submitted manuscript (Table 29 in the revision) were mistakenly left at placeholder values of 0.00%. The correct five-seed results are 98.41 ± 2.75% on recombination OOC and 69.44 ± 6.36% on length OOC. These values have been corrected in Table 29 of the revision.

These Stage-3 zero-shot results show the intended effect of Stage 3: programs discovered through Stage-2 search are learned back into the programmer, so many OOC problems can subsequently be solved without search. Final search further improves the results to 100.00% and 99.87%, respectively.

Weakness #2. It is unclear whether Stage 1 + search is already sufficient.

  1. Stage-3 ablation. As noted in point 2 above, Stage 3 trains the programmer on programs discovered through Stage-2 search. This allows it to solve previously discovered compositions without running search again each time. It also improves future search by providing better initial program proposals.

One challenge is to learn these new programs without forgetting what the programmer already knows. Appendix Table 27 of the submitted manuscript (Table 28 in the revision) examines this aspect of Stage 3. Training only on banked program traces reduces Test I/O accuracy to 13.67%, while adding the BtrainB_{\mathrm{train}} retention branch restores it to 99.81% without reducing bank uptake. Thus, this ablation explains the Stage-3 training design, rather than whether Stage 3 itself is useful.

  1. Stage 1 + search versus Stage 3 + search. We agree with the reviewer’s intuition that Stage 1 + search should already be fairly strong, since by the end of Stage 1 NeuLP has already learned a high-quality neural language. Following your suggestion, we ran a matched Stage-1 + search versus Stage-3 + search comparison on Comp-II and CompARC:
DomainSplitStage 1 + searchStage 3 + search
Comp-IIRecombination95.24±0.0095.24 \pm 0.00100.00±0.00\mathbf{100.00 \pm 0.00}
Comp-IILength62.50±13.0162.50 \pm 13.0187.50±4.17\mathbf{87.50 \pm 4.17}
CompARCRecombination68.18±12.8668.18 \pm 12.8681.82±6.43\mathbf{81.82 \pm 6.43}
CompARCLength55.21±7.3755.21 \pm 7.3763.54±1.47\mathbf{63.54 \pm 1.47}

Values are exact query accuracy (%), mean ± sample s.d. We use a smaller 128×10128\times10 search budget here to keep the comparison sensitive to proposal quality.

The results match our expectation: Stage 1 + search already solves many OOC programs, while Stage 3 further improves the results by learning from the programs discovered in Stage 2 and providing better proposals for subsequent search. This comparison is also included in Appendix Table 32 of the revision.

  1. GCU versus random editing. For Appendix Table 22 of the submitted manuscript (Table 23 in the revision), we agree that stratified directional GCU is not clearly separated from the full random-edit baseline given the variance. Its clearer advantage is over raw gradient-norm and random-coordinate selection, as now clarified in the revision.
AuthorsOpenReview ↗

Response to reviewer TV3n - Part 2/4: Weaknesses 3-6

Weakness #3. Table 1 mixes different search procedures and soft/hard accuracy.

  1. Why some baselines do not use test-time search. LPN and NLI use the test-time optimization procedures from their original papers, while NEO-S uses program sampling. Episode Transformer, HRM, and TRM do not have an explicit executable language to search, so we evaluate them using their native inference procedures. As discussed in point 1 above, the ability to search over learned programs is a key architectural advantage of NeuLP.

  2. Why we report both soft and hard accuracy. For Test I/O, NLI and LPN use soft or continuous latent programs, while Episode Transformer, HRM, and TRM make predictions without a discrete program constraint. We therefore report NeuLP's soft-program accuracy for a fair comparison. We also explicitly point to hard Test I/O accuracy in Appendix Table 29 of the revision (Table 28 in the submission), since we believe it is a better measure of language quality: it tells us whether the learned discrete programs actually work, rather than relying on soft token mixtures.

For OOC, the baselines use their native prediction procedures, while NeuLP reports hard accuracy from discrete program search. NeuLP therefore operates under a stricter constraint but still substantially outperforms the baselines. We have clarified these distinctions in the revised experimental protocol and appendix.

Weakness #4. Stage 2 can already search programs up to length 6.

As discussed in point 1 above, search is part of NeuLP's inference procedure. Stage 1 is trained only on D1--D3 programs, and NeuLP learns a language that allows it to search for longer compositions. If it solves a D6 problem through search, it has solved that problem using only the support PBE and query input available to the other methods, without access to the query target.

That said, we agree that D4--D6 programs are no longer entirely unseen once Stage 2 has searched or dreamed them. Our length-OOC setting is defined relative to Stage-1 training, which contains only D1--D3 programs. We have clarified this distinction in the revised experimental protocol. We address generalization beyond length 6 separately in Question #1 below.

Weakness #5. The continuous-interface ablation has high variance.

We extended this experiment from three to five seeds:

InterfaceSeed 1Seed 2Seed 3Seed 4Seed 5Mean ± SD
Codebook100.0099.3999.80100.00100.0099.84±0.27\mathbf{99.84 \pm 0.27}
Continuous0.00100.000.000.000.0020.00±44.72\mathbf{20.00 \pm 44.72}

The high variance in the original continuous-interface result came from a single successful seed. This pattern persists with five seeds: only one reaches 100%, while the other four remain at 0%. In contrast, the discrete codebook performs consistently well across all five seeds. The additional results further support the advantage of the discrete neural language over the continuous interface. The per-seed results are also included in Appendix Table 17 of the revision.

Weakness #6. What happens if length-1 examples are removed?

We ran this ablation on Comp-II, removing all length-1 training functions while keeping the NeuLP architecture and program-length curriculum unchanged. Across all five seeds:

Training functionsHard Test I/O accuracyReference primitives recovered as single tokens
Length 2--3 only100%0/8

NeuLP can still fit all composite training functions, but does not recover the reference primitives as single tokens. This is consistent with the second limitation discussed in the paper: input-output supervision identifies executable behavior, but not a unique decomposition into primitives. Learned tokens may therefore represent primitives, macros, or behaviorally equivalent alternatives.

For example, if a token mm implements m(x)=b(a(x))m(x)=b(a(x)), then [m][m] and [a,b][a,b] are indistinguishable from endpoint I/O alone. Additional structural priors over the learned language may help resolve this ambiguity, which we view as an important direction for future work.

AuthorsOpenReview ↗

Response to reviewer TV3n - Part 3/4: Questions 1-2

Question #1. Can NeuLP generalize beyond length 6?

Yes. We agree that >6 is the cleanest test of depth generalization beyond anything seen during Stage 2. We extend the evaluation to Comp-II programs of depth 7--12, beyond anything encountered during Stage-2 search or dreaming.

The Stage-3 programmer still predicts at most six tokens. For longer programs, we simply append SKIP tokens to its proposal and allow search over all 12 positions. For example:

  • Programmer proposal: [a, b, c, d, e, f]
  • Search initialization: [a, b, c, d, e, f, SKIP, SKIP, SKIP, SKIP, SKIP, SKIP]

The learned language and interpreter remain frozen, with no additional training on programs beyond depth 6. We use the full 128×100128\times100 search budget.

Comp-II depth 7--12 results (3 seeds):

DepthSolvedMean ± SD
717/1894.44±9.6294.44 \pm 9.62%
813/1872.22±9.6272.22 \pm 9.62%
910/1855.56±9.6255.56 \pm 9.62%
1014/1877.78±25.4677.78 \pm 25.46%
1112/1866.67±16.6766.67 \pm 16.67%
1212/1866.67±16.6766.67 \pm 16.67%
Overall (D7--D12)78/10872.22%

This follows the same principle as the Stage-1 to Stage-2 transition: Stage 1 learns the neural language from D1--D3, and Stage-2 search uses it to solve D4--D6. Here, we simply extend search further to D7--D12 without retraining. As discussed in point 1 above, search is part of NeuLP's inference procedure. The key is learning a neural language that is both high-quality enough to solve these problems and clearly discrete so that we can search over its compositions. These results are included in Appendix Table 34 of the revision.

Question #2. Results without search/dreaming.

Please see the comparison below, taken from Appendix Table 28 of the submitted manuscript (Table 29 in the revision) with the missing Comp-II Stage-3 values corrected (see Weakness #1). Stage-1 zero-shot reports performance without Stage-2 search or dreaming. Stage-3 zero-shot shows the results after the programmer has learned from Stage-2 discoveries. Neither setting uses test-time search.

DomainSplitStage 1 0-shotStage 3 0-shot
Comp-IIRecomb.0.00±0.000.00 \pm 0.0098.41±2.7598.41 \pm 2.75
Comp-IILength0.00±0.000.00 \pm 0.0069.44±6.3669.44 \pm 6.36
CompARCRecomb.13.64±6.4313.64 \pm 6.4375.00±3.2175.00 \pm 3.21
CompARCLength0.83±0.240.83 \pm 0.2448.33±1.8948.33 \pm 1.89
CompLifeRecomb.4.21±2.354.21 \pm 2.3548.95±28.0748.95 \pm 28.07
CompLifeLength0.07±0.150.07 \pm 0.1513.60±12.5613.60 \pm 12.56
CompCIFARRecomb.0.084±0.0090.084 \pm 0.0090.011±0.0020.011 \pm 0.002
CompCIFARLength0.120±0.0050.120 \pm 0.0050.014±0.0020.014 \pm 0.002

Categorical results are exact query accuracy (%); CompCIFAR reports normalized ℓ1\ell_1 (lower is better).

We also report a direct Stage 1 + search versus Stage 3 + search comparison under Weakness #2, addressing whether Stage 1 followed by test-time search is sufficient without Stage-3 learning.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.