LinTree: Improving LLM Reasoning with Explicitly Structured Search Histories

• URL: http://arxiv.org/abs/2605.31492v1
• Date: Fri, 29 May 2026 16:13:19 GMT
• Title: LinTree: Improving LLM Reasoning with Explicitly Structured Search Histories
• Abstract summary: Large language models (LLMs) often solve reasoning problems by generating intermediate traces that explore and revise partial solutions.<n>From a search perspective, these traces can be viewed as linearized search trees, where the model extends a partial solution and backtracks to try alternatives.<n>We show that adding simple parent pointers to explicitly represent the linearized tree (LinTree) structure improves both task efficiency relative to implicit reasoning models and LLM-heuristic-guided search.
• Score: 38.39348916777905
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: 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.

Related papers

• TsuGO: Probing Search Efficiency in LLM Reasoning via Go Life-and-Death Problems [18.691569868742754]
  We introduce TsuGO, a process-level reasoning benchmark for evaluating Search Efficiency in LLM reasoning through Go life-and-death problems.<n>These problems provide closed and verifiable solution spaces with an inherent adversarial structure, making candidate generation, response checking, branch comparison, and backtracking necessary parts of reasoning rather than incidental trace patterns.<n>By constraining the solution space, TsuGO disentangles domain knowledge from search organization, parses CoT into a structured search tree, and reports Search Efficiency together with Token Efficiency and other diagnostic metrics and visualizations.
  arXiv  Detail & Related papers  (2026-08-13T13:24:47Z)
• Transformers in the Dark: Navigating Unknown Search Spaces via Bandit Feedback [22.721204992834092]
  We show that Transformers are theoretically expressive enough to implement distinct search strategies and can be trained from scratch to approximate those strategies.<n>Our Transformer models exhibit the possibility of generalizing to unseen conditions such as longer horizons or deeper trees.
  arXiv  Detail & Related papers  (2026-03-25T19:50:32Z)
• LLM-First Search: Self-Guided Exploration of the Solution Space [29.780554400938335]
  Large Language Models (LLMs) have demonstrated remarkable improvements in reasoning and planning through increased test-time compute.<n>We propose textbfLLM-First Search (LFS), a novel textitLLM Self-Guided Search method.
  arXiv  Detail & Related papers  (2025-06-05T16:27:49Z)
• ReSearch: Learning to Reason with Search for LLMs via Reinforcement Learning [74.65632662894086]
  We propose ReSearch, a framework that trains LLMs to Reason with Search via reinforcement learning.<n>Our approach treats search operations as integral components of the reasoning chain, where when and how to perform searches is guided by text-based thinking.<n>Analysis reveals that ReSearch naturally elicits advanced reasoning capabilities such as reflection and self-correction.
  arXiv  Detail & Related papers  (2025-03-25T09:00:58Z)
• Search-R1: Training LLMs to Reason and Leverage Search Engines with Reinforcement Learning [50.419872452397684]
  Search-R1 is an extension of reinforcement learning for reasoning frameworks.<n>It generates search queries during step-by-step reasoning with real-time retrieval.<n>It improves performance by 41% (Qwen2.5-7B) and 20% (Qwen2.5-3B) over various RAG baselines.
  arXiv  Detail & Related papers  (2025-03-12T16:26:39Z)
• Don't Get Lost in the Trees: Streamlining LLM Reasoning by Overcoming Tree Search Exploration Pitfalls [83.89771461061903]
  Recent advancements in tree search algorithms guided by verifiers have significantly enhanced the reasoning capabilities of large language models (LLMs)<n>Recent advancements in tree search algorithms guided by verifiers have significantly enhanced the reasoning capabilities of large language models (LLMs)<n>We identify two key challenges contributing to this inefficiency: $textitover-exploration$ due to redundant states with semantically equivalent content, and $textitunder-exploration$ caused by high variance in verifier scoring.<n>We propose FETCH, a flexible, plug-and-play system compatible with various tree search algorithms.
  arXiv  Detail & Related papers  (2025-02-16T16:12:01Z)
• Uncertainty-Guided Likelihood Tree Search [37.25859935454988]
  Tree search is a fundamental tool for planning, as many sequential decision-making problems can be framed as searching over tree-structured spaces.<n>We propose an uncertainty-guided tree search algorithm for settings where the reward function is a log-likelihood function of the paths.
  arXiv  Detail & Related papers  (2024-07-04T14:08:50Z)
• LiteSearch: Efficacious Tree Search for LLM [70.29796112457662]
  This study introduces a novel guided tree search algorithm with dynamic node selection and node-level exploration budget. Experiments conducted on the GSM8K and TabMWP datasets demonstrate that our approach enjoys significantly lower computational costs compared to baseline methods.
  arXiv  Detail & Related papers  (2024-06-29T05:14:04Z)
• RoT: Enhancing Large Language Models with Reflection on Search Trees [41.67536806038573]
  We introduce Reflection on search Trees (RoT), an LLM reflection framework designed to improve the performance of tree-search-based prompting methods. It uses a strong LLM to summarize guidelines from previous tree search experiences to enhance the ability of a weak LLM. We propose a novel state selection method, which identifies the critical information from historical search processes to help RoT generate more specific and meaningful guidelines.
  arXiv  Detail & Related papers  (2024-04-08T12:31:23Z)
• Autonomous Tree-search Ability of Large Language Models [58.68735916408101]
  Large Language Models have excelled in remarkable reasoning capabilities with advanced prompting techniques. Recent works propose to utilize external programs to define search logic, such that LLMs can perform passive tree search to solve more challenging reasoning tasks. We propose a new concept called autonomous tree-search ability of LLM, which can automatically generate a response containing search trajectories for the correct answer.
  arXiv  Detail & Related papers  (2023-10-14T14:14:38Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.