acceptodds
Under review as a conference paper at ICLR 2027

How Should We Search in Neural Language Spaces? A Study on Test-Time Search

Abstract

Recently, learning neural languages and their interpreters using data has been shown to be effective in generalizing to out-of-distribution tasks. In particular, the structure of neural languages can be leveraged via test-time search in a paradigm like programming by example (PBE). Several existing works use the differentia- bility of neural languages and their interpreters to search the language space in a gradient-guided fashion. We examine existing frameworks and study their effec- tiveness when searching the language space in a policy-guided fashion, where the encoder that induces a program in the neural language to solve a task acts as a policy. We show that frameworks enabling policy-guided search in the language space naturally exhibit length generalization via test-time search. Moreover, our results indicate that, depending on the nature of the neural language and its in- terpreter, using policy-guided search techniques such as Levin Tree Search (LTS) during test time both improves out-of-distribution generalization and requires sig- nificantly less computational overhead.

Primary area:
neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)
Keywords:
Neural Program Synthesis, Neuro-Symbolic Learning, Test-Time Search, Policy-Guided Search

Reviews

Among:
Shape:
1234this paper, Bottom 9%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.50 over 4 reviews, above 9% of the others.
Reviewer_rnxTOpenReview ↗
Rating
1
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies test-time search over the discrete symbolic languages that neural networks learn from data in the programming-by-example setting. It argues that searching the learned language directly in its discrete symbol space is more effective than gradient-based continuous search used in prior work. The paper proposes two components. First, Recurrent Neural Language Interpreter (NLI-R) generates symbols one at a time conditioned on the current execution state, which enables tree search methods such as Levin Tree Search and Beam Search. Second, Greedy Coordinate Update (GCU) is a discrete search procedure that uses gradients only to select which position to edit, and then exhaustively evaluates all candidate symbols at that position. The paper evaluates a range of search techniques across three existing benchmarks (Comp-I, Shift-L, Shift-P) and a newly introduced cellular automata benchmark (Cell-Auto) and demonstrates that discrete search outperforms continuous search in out-of-distribution accuracy.

Critical strengths
  • The paper raises a clear question about whether a language learned through gradients should also be searched with gradients. Table 1 also offers a clean framework for comparing search techniques.
Critical weaknesses
  • The proposed methods seem tailored to the NLI setting, and both are close variants of existing techniques. NLI-R adds execution-guided generation [1] to NLI, and GCU closely resembles HotFlip [2] and GCG [3]. The best results also come from Levin Tree Search and Beam Search, which are applied without modification.
  • It is unclear where the performance gains come from. All experiments use vocabulary filtering, which reduces the vocabulary from 512 to only 2 to 7 symbols, but no results without filtering are reported. LTS uses ϵ=1.0\epsilon = 1.0, which means the inductor is not used as a policy, so its success may come from enumerating short programs rather than from policy guidance.

[1] Chen et al, Execution-Guided Neural Program Synthesis, ICLR 2019
[2] Ebrahimi et al., HotFlip: White-Box Adversarial Examples for Text Classification, ACL 2018
[3] Zou et al., Universal and Transferable Adversarial Attacks on Aligned Language Models, arXiv 2023

Questions for authors
  • How was the vocabulary filtering performed, and how was τ\tau chosen for each benchmark and framework?
  • The paper states that vocabulary filtering is used in all experiments. How was it applied to the gradient-based search methods?
  • Does LTS still outperform a simple baseline that enumerates short programs over the filtered vocabulary, given that ϵ=1.0\epsilon = 1.0?
2 comments

Comment: The proposed methods seem tailored to the NLI setting, and both are close variants of existing techniques. NLI-R adds execution-guided generation [1] to NLI, and GCU closely resembles HotFlip [2] and GCG [3]. The best results also come from Levin Tree Search and Beam Search, which are applied without modification.

Answer: Yes, our work builds on existing work, as we pointed out in our paper. Our contribution is to show an effective way of searching in program latent spaces. Contrary to what previous work was using, we present evidence that we should be searching with discrete search algorithms, instead of gradient-based ones.

Comment: It is unclear where the performance gains come from. All experiments use vocabulary filtering, which reduces the vocabulary from 512 to only 2 to 7 symbols, but no results without filtering are reported. LTS uses epsilon of 1.0, which means the inductor is not used as a policy, so its success may come from enumerating short programs rather than from policy guidance.

Answer: The inductor contributes the pruning set, while BFS enumerates compositions of the retained symbols.

Question: How was the vocabulary filtering performed, and how was tau chosen for each benchmark and framework?

Answer: For each checkpoint, τ\tau thresholds symbol usage in programs that solve ID tasks, yielding a fixed vocabulary used across search methods. This is done for both NLI and NLI-R.

Question: The paper states that vocabulary filtering is used in all experiments. How was it applied to the gradient-based search methods?

Answer: For Gradient Search and its variants, the continuous embeddings are updated during search exactly as in the unfiltered setting. Filtering only changes which symbols are executed along the program rollout: in the unfiltered setting, the highest-probability symbol is selected from the full vocabulary, whereas in the filtered setting it is selected from the vocabulary retained after filtering, where probabilities are re-weighted.

Question: Does LTS still outperform a simple baseline that enumerates short programs over the filtered vocabulary, given that epsilon is 1.0?

Answer: At ϵ=1\epsilon=1, the reported method is itself breadth-first enumeration over the filtered vocabulary, up to ordering within each depth.

Thank you for the response. However, the scope of this paper is too narrow and my main concerns remain unaddressed. Therefore, I will keep my score.

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

This paper studies neural program generation in a toy setting. They show that discrete search methods like beam search or levin tree search outperform continuous time gradient based methods.

Critical strengths

None

Critical weaknesses

I don't quite get the motivation of this paper. The introduction starts by saying program induction offers a compelling route to out of distribution generalization. However what kind of out of distribution generalization is this talking about and over what domain?

The experiments also seem to be ran over contrived toy settings with no connection to any practical or pertinent subfields of machine learning. It seems RQ1 and RQ2 are only answered in this contrived scenario.

Questions for authors

Could you better motivate why the results here are interesting beyond the toy setting proposed in the paper?

1 comment

Question: Could you better motivate why the results here are interesting beyond the toy setting proposed in the paper?

Answer: We are dealing with the lack of ability of current neural models to generalize out of distribution. Our work focus on the test-time search component. Despite the benchmarks being simple, they are already challenging for the problem we are setting ourselves to solve: learn a neural language from examples alone. What we hope to see is that more research in this area will allow us to scale to more interesting problems.

Reviewer_VJeHOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies how to conduct test-time search in neural language space. Previous work such as NLI searched these languages by using gradients to update continuous representations of candidate programs. This paper extends searching methods to discrete ones, and introduces Greedy Coordinate Update, which edits program symbols directly. And the paper proposes NLI-R, which generates program symbols in an autoregressive way, enabling Beam search and LTS to apply on program prefixes. The experiments compare gradient search (w/w.o. early stop), GCU, and sample-and-vote on both NLI and NLI-R, and also evaluate beam search and LTS on NLI-R. Across four program-induction benchmarks, the authors conclude that discrete search generally achieves higher out-of-distribution accuracy with fewer measured FLOPs than gradient search. Among which NLI-R with LTS attains near-perfect accuracy on all four benchmarks, while NLI-R generally shows a better accuracy–compute trade-off than NLI.

Critical strengths
  1. The paper compares a range of search methods on NLI and NLI-R, including gradient search and tree search, and reports both OOD accuracy and accuracy-compute trade-offs on four benchmarks. These methods and experiments provide useful empirical evidence on test time search in neural language space.
  2. The paper introduces NLI-R with autoregressive symbol generation, making prefix-based search methods applicable to the neural language space. Under the reported hyperparameters, NLI-R shows better performance and accuracy-compute trade-off compared to NLI in majority cases.
Critical weaknesses
  1. Section 3.2 states that “Both use an ϵ\epsilon-mixture of the inductor and the uniform distribution over VV, which follows the uniform policy with probability ϵ\epsilon and the inductor otherwise.” While in Table 6, the hyperparameters of policy mixing of LTS are ϵ=1.0\epsilon=1.0 on all four benchmarks. Thus, under the paper's previous definition, the policy degenerates into a uniform distribution and the learned inductor does not provide policy guidance for prioritizing node expansions.

  2. This paper evaluates all methods after vocabulary filtering, which may have different impact on search methods. For example, larger vocabulary may cause the search space of LTS with ϵ=1.0\epsilon=1.0 to grow rapidly. What's more, the definition of τ\tau is still not clear enough, and the authors didn't show how and why they chose these different τ\tau values in the main experiments.

Questions for authors
  1. Section 3.2 defines ϵ\epsilon as the weight of the uniform policy, but Table 6 reports ϵ=1.0\epsilon=1.0 for LTS. Is this the value used in the implementation? If so, could you report LTS accuracy for several ϵ<1\epsilon<1 values on the same settings? This would help clarify whether the inductor improves search.
  2. Table 7 reports different filtering thresholds and effective vocabulary sizes for NLI and NLI-R. How were the reported τ\tau values selected? How do you distinguish the effect of NLI-R's design from the effect of these different search-space sizes on the accuracy-compute comparison in Figure 5? Would you please show some results with larger vocabulary size to assess the robustness of your work?
1 comment

Comment: Section 3.2 states that “Both use an episilon-mixture of the inductor and the uniform distribution over V, which follows the uniform policy with probability and the inductor otherwise.” While in Table 6, the hyperparameters of policy mixing of LTS are on all four benchmarks. Thus, under the paper's previous definition, the policy degenerates into a uniform distribution and the learned inductor does not provide policy guidance for prioritizing node expansions.

Answer: Correct: ϵ=1\epsilon=1 gives breadth-first expansion over the retained symbols. We have replaced the LTS presentation with BFS and clarified that learned information enters through vocabulary pruning, which remains active at ϵ=1\epsilon=1.

Comment: This paper evaluates all methods after vocabulary filtering, which may have different impact on search methods. For example, larger vocabulary may cause the search space of LTS with to grow rapidly. What's more, the definition of is still not clear enough, and the authors didn't show how and why they chose these different values in the main experiments.

Answer: We made the definition of vocabulary filtering clear in the main text. App. D now contains details and reasoning on the selection rule we followed for τ\tau. We chose the values that will let the framework retain it's ability to solve in-distribution tasks while allowing us to prune symbols that are not helpful in solving out-of-distribution tasks.

Question: Section 3.2 defines as the weight of the uniform policy, but Table 6 reports epsilon=1.0 for LTS. Is this the value used in the implementation? If so, could you report LTS accuracy for several values on the same settings? This would help clarify whether the inductor improves search.

Answer: Yes, ϵ=1\epsilon=1 was used on all four benchmarks, giving BFS over the filtered vocabulary. We now make this explicit; we do not report an ϵ\epsilon sweep or claim a benefit from learned expansion rankings.

Comment: Table 7 reports different filtering thresholds and effective vocabulary sizes for NLI and NLI-R. How were the reported tau values selected? How do you distinguish the effect of NLI-R's design from the effect of these different search-space sizes on the accuracy-compute comparison in Figure 5? Would you please show some results with larger vocabulary size to assess the robustness of your work?

Answer: We clarified about the selection rule for filtering threshold in App. D. The choice of filtering threshold was done by balancing the aggressive pruning and in-distribution performance of either frameworks. We have added an ablation on using filtered vocabularies versus unfiltered vocabularies across various domains and various difficulties. We show that performing policy-based action-pruning helps not only with the search performance but also with the computation as well.

Reviewer_fSFSOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper investigates how to perform test-time program search in learned neural language spaces. The authors argue that, although neural languages are learned in a differentiable, continuous fashion, searching the resulting language discretely can be more effective.

The paper makes two primary contributions:

  1. Discrete search over learned programs. The authors introduce GCU, which uses gradients to identify a program position to modify but evaluates discrete token replacements directly.
  2. Autoregressive neural language induction. The authors introduce NLI-R, an autoregressive variant of Neural Language Interpreter (NLI), which generates symbols conditioned on intermediate execution states and enables prefix-based search algorithms, including beam search and Levin Tree Search (LTS).

However, the empirical results do not support the paper's claim.

Critical strengths

Important and well-motivated research question. The distinction between how a neural language is learned and how it should be searched is conceptually meaningful. The paper challenges the assumption that differentiable representations must necessarily be learned via gradient descent.

Critical weaknesses
  • The effectiveness of learned policy-guided search is not demonstrated. The paper emphasizes policy-guided search as a key contribution; however, the best LTS configuration ignores the policy entirely. Table 6 sets the policy mixing ε = 1.0 for LTS, meaning that a uniform policy entirely replaces the learned policy.
  • Vocabulary filtering shrinks the search space to a few hundred programs, which undermines the central claims. Per Table 7, all experiments search a filtered vocabulary of only 2–7 tokens out of K = 512. This reduction changes the computational difficulty of the search problem substantially.
Questions for authors

Beyond the key problems stated in the weakness (which authors should address first):

Could the authors provide a controlled comparison between NLI and NLI-R using matched program lengths (4 vs. 8) and comparable vocabulary filtering? This would help clarify whether the improvements arise from autoregressive generation or from differences in the effective search spaces.

2 comments

Comment: The effectiveness of learned policy-guided search is not demonstrated. The paper emphasizes policy-guided search as a key contribution; however, the best LTS configuration ignores the policy entirely. Table 6 sets the policy mixing ε = 1.0 for LTS, meaning that a uniform policy entirely replaces the learned policy.

Answer: We agree that ϵ=1\epsilon=1 removes learned probability rankings, but the inductor still supplies the vocabulary filter through successful ID programs. We now describe this configuration as BFS with policy-derived action pruning.

Comment: Vocabulary filtering shrinks the search space to a few hundred programs, which undermines the central claims. Per Table 7, all experiments search a filtered vocabulary of only 2–7 tokens out of K = 512. This reduction changes the computational difficulty of the search problem substantially.

Answer: Vocabulary pruning is central to the evaluated setting: successful ID programs define an expert policy's allowed symbols. All search methods share this restriction within each checkpoint, and we have scoped our claims to the filtered languages.

Question: Could the authors provide a controlled comparison between NLI and NLI-R using matched program lengths (4 vs. 8) and comparable vocabulary filtering? This would help clarify whether the improvements arise from autoregressive generation or from differences in the effective search spaces.

Answer: The experiments are controlled for Comp-I, Shift-P and Cell-Auto. Shift-L is the only benchmark we have not controlled for program length. The process of filtering the vocabulary is dependent on the learned policy and data, so it could vary from one run to another. The size of the vocabulary is comparable across the methods, differing by 1 symbol.

Thank you for the clarification. However, the response does not directly address my concern. I will retain my current score.

Comments on the paper

1 comment

We thank the reviewers for identifying an ambiguity in our description of the policy's role. With ϵ=1\epsilon=1, the reported Levin Tree Search configuration performs breadth-first search over a fixed, pruned action set. We have therefore revised the paper to describe the method as action-pruned BFS, retaining the connection to Levin Tree Search only in related work. The learned inductor (and thus policy) contributes through successful in-distribution programs used to construct the vocabulary filter, which defines the allowed actions for both NLI and NLI-R; its relative probabilities do not order BFS expansions. This revision clarifies the evaluated algorithm without changing the reported results.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.