acceptodds
Under review as a conference paper at ICLR 2027

LinTree: Improving LLM Reasoning with Explicitly Structured Search Histories

Abstract

Large language models (LLMs) are increasingly used to perform or guide search in domains such as geometry theorem proving, formal proof search, and planning. A growing line of work trains LLMs to carry out the search process autoregressively, conditioning each decision on a trace of previous exploration, including failed attempts and backtracking. Compared with traditional heuristic-guided search, such a policy has a potential advantage: it conditions on the whole search trace rather than only on the current local state. We first examine this potential by comparing trace-conditioned policies against best-first search equipped with an LLM heuristic that only observes the current local state. Across three controlled domains, Blocks World, grid Navigation, and Sokoban, we find that raw access to search history alone is not enough to reliably outperform heuristic search. We then study one possible reason: the search tree structure is only latent in the trace, and when the model backtracks or switches branches, the trace does not explicitly identify which earlier search state is being revisited. We show that adding parent pointers that make this latent structure explicit (LinTree) improves both task performance and search efficiency over implicit policies, and matches the solve rate of LLM-heuristic-guided search while using fewer expansions. These results suggest that, for search problems, making the structure of the search history explicit helps LLMs learn more effective search behavior.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Large Language Models, Planning, Tree Search

Reviews

Among:
Shape:
1234this paper, Bottom 2%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.33 over 3 reviews, above 2% of the others.
Reviewer_EoX6OpenReview ↗
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
  1. How does LinTree differ from the node labeling in Stream of Search?
  2. Does the gain hold against an implicit format that writes the full parent state, or a length-matched one?
  3. How many training seeds were run, and how large is the variance across them?
  4. Are expansions averaged over all instances or only solved ones?
  5. 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.
Reviewer_1v8AOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

LinTree adds explicit parent pointers to serialized search traces and trains LLMs using supervised fine-tuning followed by GRPO with a correctness-and-efficiency reward. Across three planning domains and two model sizes, it improves success and reduces expansions relative to implicit traces; matching the external search baseline on Sokoban requires environment-provided transitions.

Critical strengths
  1. Consistent controlled improvements: Explicit and implicit models use the same underlying demonstrations and training pipeline. After GRPO, parent pointers improve success and reduce expansions across all three domains and both model sizes supporting a useful representation effect.

  2. Informative failure analysis: Table 4 distinguishes transition/tree errors from final-plan extraction errors and shows reductions in both. The constrained Sokoban experiment also usefully exposes the contribution of environment-provided transitions.

Critical weaknesses
  1. Limited differentiation from prior work: Stream of Search already uses hierarchical node identifiers and explicit movements between nodes. LinTree does not compare against that representation under matched training, leaving its contribution beyond an explicit-versus-implicit ablation insufficiently established.

  2. Mechanism and efficiency remain unclear: Navigation’s 5.1-point success gain accompanies a 4.6-point reduction in plan-extraction failures, leaving improved search decisions insufficiently isolated. Efficiency is measured through expansions despite longer annotated steps; total tokens, latency, and model computation are not reported.

Questions for authors
  1. Representation controls: How does LinTree compare with a Stream-of-Search-style format, state IDs without parent pointers, or explicitly repeating the source state, using the same demonstrations and training?

  2. Search versus extraction: Does the advantage persist when both formats receive comparable transition support and use a common final-plan extraction procedure? Please distinguish finding a valid goal path from correctly emitting the final plan.

  3. Efficiency measurement: Are expansion averages computed over all instances or only successful ones, and how are failures counted? Can you report total tokens and latency, including candidate scoring for the external-search baseline?

  4. Training robustness: What variation occurs across independent training seeds? Can you provide quantitative learning curves or ablations supporting the claim that the alternative rewards cause training instability?

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

LinTree introduces explicit parent pointers into language-model search traces and trains models using supervised learning and reinforcement learning. Experiments across three planning domains and two backbones show improved success rates and fewer search expansions. The contribution is a controlled study of how trace representation affects learned search.

Critical strengths

The explicit and implicit representations use matched demonstrations and training settings, supporting the reported effect of parent-pointer annotations.

Improvements across multiple domains and two backbones provide consistent evidence for the method within the evaluated setting.

Critical weaknesses

Limited evidence of algorithmic generalization. The evaluation measures performance within task families used for training. It does not establish cross-domain transfer or extrapolation to substantially larger problems. The results therefore demonstrate successful task-specific adaptation, while the generality of the learned search strategy remains untested.

Missing baselines for model-generated solvers. Prior work demonstrates that pretrained models can synthesize reusable planning programs and construct agent workflows. These approaches provide a concrete alternative to manually specifying the search representation. Their omission leaves the incremental benefit of LinTree’s specialized training unestablished.

Incomplete evaluation of the accuracy–cost trade-off. Search expansions do not measure total computational cost. The evaluation excludes the combined cost of data generation, training, and inference, and does not assess the adaptation effort required for new domains. Consequently, it does not establish whether deployment savings amortize the method-specific setup costs.

Questions for authors

How does LinTree compare with a capable reasoning models prompted to generate, debug, and execute its own planning program?

Does the trained policy transfer to unseen task families or larger problem instances without additional training?

What is the accuracy–cost trade-off against these alternatives when setup and inference costs are included?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.