- 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 , 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 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 ?
2 comments
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.
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, τ 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, the reported method is itself breadth-first enumeration over the filtered vocabulary, up to ordering within each depth.