LinTree: Improving LLM Reasoning with Explicitly Structured Search Histories

📄 arXiv: 2605.31492v1 📥 PDF

作者: Liwei Kang, Yee Whye Teh, Wee Sun Lee

分类: cs.AI

发布日期: 2026-05-29

备注: 16 pages, 3 figures

💡 一句话要点

LinTree：通过显式结构化搜索历史提升LLM推理能力

🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)

关键词: 大型语言模型 推理 搜索 结构化 搜索历史

📋 核心要点

  1. 现有LLM推理方法依赖隐式搜索树，回溯和分支切换时缺乏明确的状态标识，导致推理效率低下。
  2. LinTree通过在LLM推理过程中添加父指针，显式地表示线性化搜索树的结构，从而改进推理。
  3. 实验表明，LinTree在任务性能和搜索效率上优于隐式推理模型和LLM启发式引导搜索。

📝 摘要（中文）

大型语言模型（LLMs）通常通过生成中间推理轨迹来解决推理问题，这些轨迹探索和修改部分解决方案。从搜索的角度来看，这些轨迹可以被视为线性化的搜索树，模型在其中扩展部分解决方案，在失败时放弃它，并回溯以尝试替代方案。与传统启发式引导搜索相比，这种策略具有潜在的优势：它以整个搜索轨迹为条件，而不仅仅是当前的局部状态。我们首先测试LLMs是否利用了这种优势，通过将轨迹条件推理策略与配备LLM启发式的最佳优先搜索进行比较，后者仅观察当前的局部状态。在三个受控推理环境（Blocks World、网格导航和Sokoban）中，我们发现仅原始访问搜索历史不足以可靠地胜过启发式搜索。然后，我们研究了一个可能的原因：在LLM推理轨迹中，底层搜索树仅被隐式表示，并且当模型回溯或切换分支时，轨迹没有明确标识正在重新访问哪个先前的搜索状态。我们表明，添加简单的父指针以显式表示线性化树（LinTree）结构，相对于隐式推理模型和LLM启发式引导搜索，可以提高任务性能和搜索效率。这些结果表明，当搜索历史的树结构变得明确时，它变得最有用，从而激发了LLM推理的更多结构感知表示。

🔬 方法详解

问题定义：论文旨在解决大型语言模型（LLMs）在复杂推理任务中，由于搜索历史的隐式表示而导致的推理效率和性能瓶颈。现有方法，如直接使用LLM生成推理轨迹或结合LLM启发式的搜索算法，未能充分利用完整的搜索历史信息，尤其是在回溯和切换分支时，缺乏对先前状态的明确标识，导致搜索效率降低。

核心思路：论文的核心思路是通过显式地结构化LLM的搜索历史来提升推理能力。具体而言，通过在推理过程中维护一个线性化的搜索树（LinTree），并使用父指针明确地连接每个搜索状态与其父状态，从而使LLM能够更好地理解和利用搜索历史中的信息，提高回溯和分支切换的效率。

技术框架：LinTree方法的核心在于对LLM生成的推理轨迹进行结构化表示。整体流程如下： 1. LLM生成推理步骤，每个步骤代表一个搜索状态。 2. 为每个搜索状态添加一个指向其父状态的指针，构建线性化的搜索树（LinTree）。 3. LLM在生成后续推理步骤时，可以访问整个LinTree结构，从而更好地理解搜索历史，并做出更明智的决策。 4. 在回溯或切换分支时，LLM可以根据父指针快速定位到相应的状态，避免重复探索。

关键创新：LinTree方法的关键创新在于将隐式的LLM搜索历史显式地结构化为树形结构。与传统的LLM推理方法相比，LinTree通过父指针明确地表示了搜索状态之间的关系，从而使LLM能够更好地利用搜索历史信息，提高推理效率和性能。这与仅仅依赖LLM自身记忆或启发式搜索有本质区别。

关键设计：LinTree的关键设计在于父指针的实现和使用。具体而言，每个搜索状态都包含一个指向其父状态的指针，该指针可以是状态的索引或唯一标识符。在LLM生成后续推理步骤时，可以将父状态的信息作为输入，从而使LLM能够更好地理解当前状态与历史状态之间的关系。此外，还可以设计特定的损失函数来鼓励LLM更好地利用LinTree结构，例如，通过惩罚LLM在回溯时未能正确利用父指针的行为。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果表明，LinTree在Blocks World、网格导航和Sokoban三个受控推理环境中，显著优于隐式推理模型和LLM启发式引导搜索。具体而言，LinTree在任务完成率和搜索效率方面均有提升，证明了显式结构化搜索历史的有效性。例如，在Sokoban游戏中，LinTree相比于基线方法，任务完成率提升了约10%-20%。

🎯 应用场景

LinTree方法可应用于各种需要复杂推理和搜索的任务，例如游戏AI、机器人导航、规划问题求解等。通过显式地结构化搜索历史，可以提高LLM在这些任务中的性能和效率，使其能够更好地解决复杂问题。未来，该方法还可以扩展到其他领域，例如知识图谱推理、代码生成等。

📄 摘要（原文）

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.