- Rating
- 1
- Confidence
- 4
- Informativeness
- 1
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
The paper trains small LLMs (Qwen3-0.6B and Qwen3.5-4B) with SFT and then GRPO to write out best-first search traces, and evaluates them on Blocks World, 10x10 grid navigation, and 2-box Sokoban. It first shows that such a trace-conditioned policy does not reliably beat best-first search (BFS) guided by a local LLM heuristic. It then adds state identifiers (sid=k) to each trace line, so that every expansion names its parent node, and reports that this explicit format improves solve rate and reduces expansions after GRPO. The paper also proposes a bounded length penalty that ranks every correct trace above every incorrect one.
Critical strengths
- The comparison is well controlled. Both formats come from the same BFS traces and share the same pipeline, so the serialization is the only variable.
- The authors are candid about negative results, for example that trace access alone does not help and that the lexicographic property fails for the expected reward (Appendix F).
- The paper is clearly written, and the failure breakdown in Table 4 is a useful diagnostic.
Critical weaknesses
1. Limited novelty. The contribution is a change to the trace format: adding parent pointers to each line. Explicit node identifiers are the standard way to serialize a search tree, and prior trace-learning work already uses them. For example, Stream of Search (Gandhi et al., 2024) labels nodes in its traces ("Generated Node #0,1", "Moving to Node #0,1"), and its labels even encode the full path from the root. Moreover, the conclusion that writing an intermediate quantity into the trace makes it easier to learn is the scratchpad argument of Nye et al. (2021). The related work also misses methods that already condition search on the whole tree with explicit structure, such as PGTS (Li, 2025, arXiv:2502.06813), which trains a tree-search controller with RL and a search-cost penalty, including on Blocksworld.
2. The implicit baseline is weak. The implicit format (EXPAND ACT a -> s') leaves out the parent state, which any natural trace format would include, so the comparison favors the explicit format by construction. To attribute the gain to tree structure, the paper needs at least three controls: an implicit format that writes the full parent state, a length-matched implicit format (the explicit one adds tokens per step), and the Searchformer and Stream of Search formats.
3. The gains are small and shrink with scale. Blocks World and Navigation are near ceiling, since BFS without RL already solves 99.7% and 100% of instances. At 4B, the explicit format moves Navigation only from 98.8% to 99.6%, and after SFT it even uses more expansions on Blocks World (11.26 vs. 9.67). Only Sokoban shows a clear gap, and it has been simplified to two boxes. This pattern suggests that larger models can infer the parent on their own. Harder instances and generalization to larger problems are not tested.
4. Results come from single training runs. The standard errors are computed over evaluation instances, so they do not reflect variance across training runs. Since GRPO on small models is sensitive to the seed, differences such as 14.80 vs. 14.28 expansions on Navigation could be noise.
5. The comparison with BFS is confounded. The BFS baseline gets next states from the true transition function and avoids revisits with a visited set. In contrast, the trace-conditioned policy has to generate every next state itself, so Section 4 largely tests whether a 0.6B model can simulate the domain, and the finding that "trace access alone is not enough" is unsurprising. Furthermore, the abstract says LinTree matches the BFS solve rate, but in Sokoban this holds only when the environment fills in each resulting state (98.9%); without that, LinTree reaches 89.6% versus 99.1% for BFS. Finally, expansions cost very different amounts in the two approaches (one generated line versus scoring the whole frontier), and the paper reports no token, FLOP, or wall-clock numbers. It is also unclear whether failed searches are counted in the expansion averages.
6. The reward contribution is minor. Proposition 1 follows in two lines from the geometric-series bound, and, as Appendix F admits, the property does not hold for the expected reward that GRPO actually optimizes. The claim that alternative rewards are unstable (Appendix G) comes without training curves.
7. The paper overclaims. The title promises better "LLM reasoning," and the introduction cites AlphaGeometry and Lean. However, every experiment uses small models trained on synthetic traces in three toy domains with compact symbolic states, and it is unclear how parent pointers would carry over to free-form reasoning. Appendix D also shows that Navigation training fails without hand-added BLOCKED entries, so the results depend on other format details as well.
Questions for authors
- How does LinTree differ from the node labeling in Stream of Search?
- Does the gain hold against an implicit format that writes the full parent state, or a length-matched one?
- How many training seeds were run, and how large is the variance across them?
- Are expansions averaged over all instances or only solved ones?
- Does the gap persist on harder instances, such as 4-box Boxoban or larger grids?
Minor Comments
- Table 3 orders the domains differently from Tables 2 and 4.
- The diversity differences in Table 5 (3.99 / 4.11 / 4.19) are small and have no error bars, and more spread does not by itself mean better exploration.
- In Table 4, tree violations for the implicit policy rely on a heuristic parent reconstruction, so they are not directly comparable to the explicit policy's.
Missing References
- Yang Li. Policy Guided Tree Search for Enhanced LLM Reasoning. arXiv:2502.06813, 2025. A learned controller conditions on the full search tree with explicit parent-child structure and is trained with RL under a search-cost penalty, which is directly relevant to Sections 2 and 4.