LinTree: Improving LLM Reasoning with Explicitly Structured Search Histories

Researchers demonstrate that Large Language Models improve their reasoning performance when search histories are explicitly structured with parent pointers (LinTree), rather than implicitly represented. The finding suggests that LLMs benefit from tree-aware representations during problem-solving, outperforming both implicit trace-based reasoning and traditional heuristic-guided search across multiple domains.

LinTree addresses a fundamental inefficiency in how LLMs currently approach complex reasoning tasks. When language models solve problems requiring step-by-step exploration, they generate traces of their reasoning process that represent search trees in linearized form. The research reveals that simply having access to this historical context doesn't automatically translate to better performance—the key insight is structural clarity. By explicitly marking parent-child relationships through pointer annotations, the model gains a clearer mental model of which decision branches it has explored and where to backtrack when solutions fail.

This work emerges from growing recognition that transformer architectures process information fundamentally differently than symbolic search algorithms. Traditional heuristic search operates with explicit state representations and branching logic, while LLMs generate token sequences that must implicitly encode these computational patterns. The LinTree approach bridges this gap by making the underlying tree structure explicit without requiring architectural changes, enabling existing models to leverage search history more effectively.

The implications extend across domains where LLMs handle planning and reasoning—from code generation to scientific problem-solving. Better structured reasoning capabilities could reduce computational waste from redundant exploration and improve success rates on complex multi-step tasks. For AI researchers and practitioners building reasoning systems, this suggests that prompt engineering and representation design matter as much as model scale.

Future work should explore whether these principles scale to open-ended reasoning where search trees become exponentially larger, and whether hybrid approaches combining explicit structure with learned heuristics yield further gains.

• →Explicit tree structure via parent pointers (LinTree) significantly improves LLM reasoning performance over implicit search traces
• →Raw access to search history alone is insufficient—structural representation determines whether LLMs effectively use prior exploration data
• →LinTree outperforms both trace-conditioned baselines and LLM-guided heuristic search across Blocks World, grid navigation, and Sokoban
• →Structure-aware representations for LLM reasoning could reduce computational inefficiency and improve success rates on complex planning tasks
• →Results suggest that prompt design and explicit problem structure matter as much as model capacity for reasoning tasks