LinTree: Improving LLM Reasoning with Explicitly St...

LinTree: Improving LLM Reasoning with Explicitly St... | AI Research

Key Takeaways

LinTree: Improving LLM Reasoning with Explicitly Structured Search Histories Large language models (LLMs) often solve complex problems by generating a sequen...
Large language models (LLMs) often solve reasoning problems by generating intermediate traces that explore and revise partial solutions.
From a search perspective, these traces can be viewed as linearized search trees, where the model extends a partial solution, abandons it when it fails, and backtracks to try alternatives.
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 test whether LLMs utilize this advantage by comparing trace-conditioned reasoning policies against best-first search equipped with an LLM heuristic that only observes the current local state.

Paper AbstractExpand

Large language models (LLMs) often solve reasoning problems by generating intermediate traces that explore and revise partial solutions. From a search perspective, these traces can be viewed as linearized search trees, where the model extends a partial solution, abandons it when it fails, and backtracks to try alternatives. 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 test whether LLMs utilize this advantage by comparing trace-conditioned reasoning policies against best-first search equipped with an LLM heuristic that only observes the current local state. Across three controlled reasoning environments, 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: in LLM reasoning traces, the underlying search tree is only implicitly represented, 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 simple parent pointers to explicitly represent the linearized tree (LinTree) structure improves both task performance and search efficiency relative to implicit reasoning models and LLM-heuristic-guided search. These results suggest that search history becomes most useful when its tree structure is made explicit, motivating more structure-aware representations for LLM reasoning.

LinTree: Improving LLM Reasoning with Explicitly Structured Search Histories
Large language models (LLMs) often solve complex problems by generating a sequence of thoughts, effectively performing an internal search. While these models can backtrack and revise their work, their reasoning traces are typically written as a flat, linear stream of text. This paper investigates whether LLMs can perform better if they are explicitly shown the underlying "tree" structure of their search process—identifying exactly which previous state they are returning to when they backtrack—rather than leaving that structure implicit.

The Limits of Implicit Search

When an LLM generates a reasoning trace, it acts like a search algorithm exploring a tree of possibilities. However, because the model usually just writes out its steps in a single line, the "topology" of the search—the connections between branches and the specific points of origin—is hidden. The researchers tested whether simply having access to the full history of a search is enough to outperform traditional search methods that use a local heuristic (a "guide" that only looks at the current state). They found that raw access to the history is not enough; without an explicit structure, the model struggles to effectively utilize the information it has already gathered.

Introducing LinTree

To address this, the researchers developed LinTree. Instead of a standard, unstructured reasoning trace, LinTree adds "parent pointers" to the model's output. These pointers explicitly label the search tree, allowing the model to clearly identify which earlier state it is revisiting when it decides to try a different approach. By turning a loosely narrated reasoning trace into a serialized, structured tree, the model can better understand its own exploration process.

Performance and Efficiency

The researchers evaluated this approach across three reasoning environments: Blocks World, grid Navigation, and Sokoban. They compared the performance of models using implicit traces against those using the explicit LinTree structure. Their results showed that when the tree topology is made explicit, the model significantly outperforms both implicit reasoning models and standard heuristic-guided search. By making the search history easier to interpret, the model achieves both higher success rates and greater search efficiency, suggesting that the way reasoning traces are represented is just as important as the model's ability to generate them.

Implications for Future Reasoning

The findings suggest that the current way we prompt or train LLMs to "think" may be missing a key component: structure. Because the model's reasoning is essentially a search process, providing it with a representation that reflects that search structure helps it navigate complex problems more effectively. This work highlights that for LLMs to reach their full potential in reasoning tasks, we should move toward more structure-aware representations that make the logic of their search process transparent.