arXiv cs.AIMonday · June 1, 2026FREE

LinTree: Improving LLM Reasoning with Explicitly Structured Search Histories

Published on arXiv on June 1, 2026, the paper "LinTree: Improving LLM Reasoning with Explicitly Structured Search Histories" investigates how large language models (LLMs) utilize their intermediate reasoning traces for problem-solving. LLMs typically generate these traces as linearized search trees, where they explore and revise partial solutions. A key challenge identified is that the underlying search tree is only implicitly represented within these traces, making it difficult for the model to explicitly identify which earlier search state is being revisited when backtracking or switching branches. This implicit representation hinders the LLM's ability to fully leverage its entire search history. The researchers initially compared trace-conditioned reasoning policies against a 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—the study found that raw access to search history alone was not enough to reliably outperform heuristic search. This indicated that LLMs struggle to infer the tree structure from a linear trace. LinTree proposes to explicitly structure these search histories, providing the model with a clear representation of the search tree. This explicit structuring is designed to enable LLMs to more effectively utilize their comprehensive search traces, thereby enhancing their reasoning capabilities and leading to improved problem-solving performance compared to relying on implicit traces or local heuristics.