LinTree: Improving LLM Reasoning with Explicitly Structured Search Histories

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.