LinTree: Enhancing Large Language Model Reasoning Capabilities via Explicitly Structured Search History

Researchers found that while large language models (LLMs) can access complete search history during reasoning, the implicitly represented search tree structure limits their efficiency. By introducing a simple parent pointer to explicitly represent the linearized tree structure (LinTree), task performance and search efficiency are significantly improved on three classic reasoning tasks: Blocks World, Grid Navigation, and Sokoban.

The trajectory of LLMs solving complex reasoning problems can be viewed as a linearized search tree. Theoretically, they can use the global trajectory to make decisions, but experiments show that merely allowing LLMs to access search history does not reliably outperform heuristic search that only uses local states. The core issue is that the search tree structure in the reasoning trajectory is implicit—models need to infer the relationship between the current step and history on their own, increasing cognitive load.

The core of the LinTree method is to add a simple parent pointer to explicitly represent the linearized tree structure, labeling each reasoning step with its parent node (source of expansion). This explicit representation brings three benefits: clear hierarchical structure, efficient state reuse, and better backtracking decisions.

In three test environments, LinTree performed significantly better than implicit reasoning models and LLM heuristic-guided search:

• Task performance: Solved more complex instances in Blocks World, achieved more efficient paths in navigation tasks, and improved strategy optimization in Sokoban;
• Search efficiency: Reduced repeated exploration, lowered cognitive load for backtracking, and made reasoning steps more concise.

Theoretical Significance: LLM reasoning capabilities depend on the structured representation of input information, echoing research in cognitive science on how humans use structured representations to solve problems.

Methodological Insights:

1. Do not assume that more context is automatically better;
2. Explicit structure is superior to implicit inference;
3. Draw on the idea of structured representation from classical AI.

Limitations:

• Restricted to simple controlled environments;
• Parent pointers require additional implementation;
• Effectiveness in open domains remains to be verified.

Future Directions:

• Explore richer structural annotations (sibling nodes, subtree summaries);
• Automatically learn optimal structural representations;
• Apply to more complex real-world tasks.