- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper combines policy-guided search with an explicit Turing-like machine to discover deterministic programs from input–output examples. It learns formally verified programs for string manipulation and binary arithmetic from hundreds of examples, though harder tasks require tailored curricula and operations.
Critical strengths
-
The method returns deterministic programs rather than computations encoded implicitly in neural weights. The paper reports machine-checked Lean 4 correctness proofs, providing stronger evidence of generalization than testing on longer inputs alone.
-
The method discovers arithmetic programs using only hundreds of input–output examples, without requiring execution-trace supervision. This demonstrates a promising way to combine guided search with learning for algorithm discovery.
Critical weaknesses
-
The broad idea of combining learned decision-making with explicit Turing-machine-style computation is already established. For example, Lai et al. (2024), Executing Arithmetic, learn arithmetic execution through explicit machine states and transitions and support composition of learned operators. The submitted paper (this paper) differs by discovering deterministic programs from input–output examples rather than learning to execute predefined algorithms. However, this distinction needs clearer positioning, and combining an explicit machine, policy-guided search, and supervised learning from successful traces does not by itself establish a substantial methodological advance. The paper would benefit from identifying precisely which part of its program-discovery procedure is novel and demonstrating its contribution through targeted ablations.
-
The baseline comparison does not isolate the claimed advantage of nondeterministic search. The main baseline is a non-learning beam hill-climbing procedure over complete deterministic program tables, whereas the proposed method combines learned guidance, incremental table construction, a curriculum. These differences confound the central claim that searching nondeterministic traces is inherently more efficient than searching deterministic programs. A stronger evaluation should include deterministic search with comparable learned guidance, curriculum, and scoring, together with an ablation removing policy learning from the proposed procedure. The historical Neural GPU comparison also measures dataset size under substantially different inductive biases and supervision, so the “200× less data” result alone provides limited evidence of overall superiority.
Lai, Junyu, et al. "Executing arithmetic: Fine-tuning large language models as turing machines." arXiv preprint arXiv:2410.07896 (2024).
Questions for authors
Please refer to my weaknesses.
Thank you for the detailed review and suggestions. We are glad you find the generalization results important and the method promising. We provide our response to both of the weaknesses below.
Positioning. We agree that combining learned components with explicit Turing machine computation is already established (Lai et al., 2024). However, we consider a much more challenging setting than Lai et al. Namely, we consider the discovery setting, where the underlying algorithm must be inferred from I/O examples. Lai et al. considered the strong supervision setting, where the model is given the computational traces of the algorithm it needs to learn. Learning to execute an algorithm from the algorithm's execution data is much easier than discovering the underlying algorithm from I/O examples. Our specific contribution is searching over nondeterministic execution traces and building the deterministic table incrementally, rather than searching over complete tables. We have not claimed novelty for policy-guided search or for learning from successful traces individually.
Isolating the contribution. It is true that no individual component is a unique contribution – it is the combination of all these components that gives us these results. We therefore appreciate the request for ablations, which show the impact of each individual methodological choice. Following your suggestion, we added the following ablations to the revised version of our paper:
In summary, much of the generalization gain is from the shared table representation and the round-robin rollouts, while each of the other components contributes significantly to the correctness of the final programs.
Neural GPU comparison. We agree that this comparison involves different inductive biases and supervision. We revise our claim in Section 5.3 to be: “While we use different inductive biases given by the choice of the machine, and thus cannot conclude overall superiority over the Neural GPU, there is a clear advantage to our method in that we use over 200 times less training data.”
We greatly appreciate your effort to understand the paper. We have incorporated the suggested comments and believe it has significantly improved thanks to your feedback.
References
Lai, Junyu, et al. "Executing arithmetic: Fine-tuning large language models as Turing machines." arXiv preprint arXiv:2410.07896 (2024).