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

# LinTree：通过显式结构化的搜索历史提升大语言模型推理能力

## 摘要

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

## 1 引言

大语言模型展现了卓越的推理能力，这在很大程度上得益于鼓励中间计算的技术，如思维链提示和自我反思[26,16,19,13]。最近的研究进一步指出，推理可以被视为一个在思维树上进行的隐式搜索过程[29,20,11]。模型不是一次性给出答案，而是可以生成中间步骤、尝试不同的方法并修正早期的选择[2,22,3]。这些发展激发了一种基于搜索的推理视角——模型在其思维链中隐式维护着一个树结构。

在这种基于搜索的视角下，推理轨迹可以被视为一棵线性化的搜索树，其中每一步要么扩展现有分支，要么修正之前的选择，要么回到更早的点以探索替代方案[29,20,2]。与传统的启发式引导搜索[8,17]相比，这给LLM带来了一个潜在优势：它不是通过使用局部状态信息对前沿节点进行评分来选择下一个扩展节点，而是基于整个先前的搜索轨迹来生成下一步搜索。借助更丰富的信息，模型原则上可以利用在一个分支上收集的证据来指导另一个分支的选择[23]，避免重复探索早期扩展已证明无效的邻域，并使用局部启发式永远无法看到的非局部上下文来协调搜索。在这种观点下，LLM搜索的优势不仅仅在于它可以搜索和自我反思，还在于它在搜索过程中会以整个搜索历史为条件。

这一框架引出了我们研究的第一个问题：以整个轨迹为条件是否能转化为更强的搜索能力？我们通过比较观察整个搜索轨迹的推理模型与配备了仅看到当前状态和目标的局部状态LLM启发式函数的最佳优先搜索算法来测试这一点。在Blocks World、网格导航和Sokoban三个受控推理环境中，我们发现仅依靠轨迹访问是不够的：推理模型并未可靠地超越局部状态启发式基线。这一结果引发了一个后续问题：为什么轨迹访问没有带来更多帮助？一个解释在于轨迹的呈现方式。虽然推理轨迹可以被视为搜索树的线性化[1,20]，但该树结构通常保持隐式。实际上，当LLM放弃一条推理线并尝试另一条时，轨迹可能包含自然语言线索，如“让我尝试一种不同的方法”[6,2,9,12]，但它通常不会明确标识正在重新访问哪个早期搜索状态。因此，历史记录包含关于探索和回溯的证据，但其树拓扑结构必须从上下文中推断出来[29,2,25]。

这引出了我们的第二个问题：当搜索树结构在训练轨迹中被显式表示时，LLM能否学习到更好的搜索策略？我们通过对轨迹表示进行最小化修改来研究这个问题：比较两种格式，一种格式中每个搜索步骤记录正在扩展的前沿状态，从而暴露树拓扑结构，另一种格式则不记录。两种格式都源自相同的底层搜索，并使用相同的监督式微调（SFT）后接强化学习（RL）流程进行训练，因此它们之间的差异主要反映了暴露树拓扑结构的效果，而非轨迹访问、优化或任务难度方面的差异。直观地说，这将一个松散叙述的推理轨迹转化为一个具有清晰拓扑结构的序列化搜索树，使模型更容易利用可用的历史信息。

我们在三个受控推理环境中实证研究了这些问题：Blocks World[24]、网格导航[15]和Sokoban[5]，在这些环境中搜索树定义明确，并且可以精确测量搜索效率。我们的实验共同检验了以下问题：以整个搜索轨迹为条件是否足以改进对局部状态LLM启发式的搜索，以及显式表示搜索树结构是否能使该轨迹更有用。我们的发现总结如下：

- 尽管LLM推理模型以整个搜索轨迹为条件生成推理步骤，但当树结构保持隐式时，它们并未充分利用这些信息：尽管拥有更多信息，但推理策略并未可靠地超越局部状态启发式基线。
- 使搜索轨迹的树拓扑结构变得显式可以改变这一点：经过相同方式训练后，明确标注搜索树结构的策略在解题率和搜索效率上都优于隐式推理模型和局部启发式模型。

## 2 相关工作

#### 思维链推理与自我反思。
思维链[26,16]提示通过引出最终答案之前的一系列自然语言推理步骤来提高LLM推理能力。后续工作通过问题分解、反思和迭代细化扩展了这一基本范式，使模型能够尝试多种方法、将问题分解为更简单的子问题或修正早期的尝试[19,31,13,22]。这些方法使推理更加灵活，但分支、修正和选择过程通常在生成的文本中保持隐式，而非作为显式的搜索结构来表示。

#### 带外部控制器的LLM推理。
一条密切相关的工作线通过将外部控制器置于LLM周围来使搜索结构显式化。思维树[29]使用外部搜索控制器来扩展、评估和修剪LLM生成的中间思维树，在推理时实现有意识的探索和回溯。LLM-A*[14]使用提示LLM来提出中间路标点，同时由外部A*控制器维护搜索前沿、验证路径有效性并构建最终路径。思维图[1]使用外部控制器将LLM生成的中间思维组织成一个图，并使用提示模块选择放入提示中的思维。LATS[30]和将推理视为规划[7]将预训练的LLM包裹在一个外部的蒙特卡洛树搜索控制器中，在外部维护完整的搜索树，同时每次语言模型调用都以通向所选节点的路径为条件。自评估引导波束搜索[27]使用外部随机波束搜索解码器来维护和修剪部分推理链，其中LLM既提出候选推理步骤，也基于单条推理路径对其逐步正确性进行自我评估。这些方法都使用外部控制器来维护搜索树，而LLM仅在局部视图（当前路径）上被查询，而非基于整个搜索轨迹。我们的工作将这种局部状态LLM使用风格与基于轨迹条件的推理模型进行比较，研究拥有完整搜索历史访问权限的效果。

## 3 推理环境

我们在三个完全可观测的推理领域进行评估：Blocks World[24]、网格导航[15]和Sokoban[5]。这三个领域自然需要搜索，并且可以从强大的启发式函数中受益以提高搜索效率。对于每个领域，我们生成20k实例用于SFT训练，另外20k实例用于RL，以及1k实例用于验证。SFT轨迹使用最佳优先搜索和每个领域的基于规则的启发式函数生成，并且过滤掉SFT轨迹超过16k token的实例。下面我们详细描述每个领域，包括可用的动作集、状态表示和实例生成流程。

#### Blocks World。
方块世界是一个推理问题，智能体必须通过移动顶部没有其他块的方块，将初始堆叠配置转换为目标堆叠配置。我们生成具有三个堆叠、4到10个方块的问题实例。训练和测试数据集中不同方块数量的实例比例按方块数量的平方加权。状态被序列化为有序堆叠列表，例如"S{"0:ATABLE">（将B从A顶部移动到TABLE）。实例通过对初始状态和目标状态进行随机采样并过滤掉可以在4步内解决的实例来生成。我们使用基于规则的启发式函数和最佳优先搜索算法生成用于训练的搜索轨迹。该启发式函数计算状态中"好"方块的数量，如果一个方块已经在目标位置且其下方的每个方块也是"好"的，则该方块被视为"好"。

#### 网格导航。
导航领域要求智能体在10×10的二维网格上从随机选择的起始单元格移动到随机选择的目标单元格，同时避开障碍物。每个网格单元格有35%的概率是障碍物。我们通过在网格中随机采样障碍物来生成实例，并只保留最优路径长度至少为6且最佳优先扩展次数至少为结果规划长度1.3倍的实例。使用LLM推理模型时，完整网格作为输入提示给出，搜索期间状态仅记录智能体位置，写作"A=(r,c)"。动作空间是四个基本方向U、D、L和R。我们使用最佳优先搜索生成SFT轨迹，启发式函数采用到目标位置的曼哈顿距离。此启发式函数在此领域可能具有误导性，因为最小化曼哈顿距离很容易导致死胡同，这为模型学习更强的搜索启发式函数留下了空间。

#### Sokoban。
Sokoban是一个经典游戏，玩家在二维网格中导航，将箱子推到目标格子上。我们使用Boxoban关卡[5]中的未过滤分割进行训练和测试。原始的Boxoban实例各有四个箱子，其搜索可能超过5000次扩展。为了使其对LLM来说可控，我们随机移除每个实例中的两个箱子和目标位置。完整的网格配置，包括初始箱子、墙壁和目标位置，作为提示给出。在搜索期间，状态由玩家位置和箱子位置集合表示，写作"P=(r,c) B={(r,c),...}"。动作空间再次是U、D、L和R，用于移动玩家。我们再次使用最佳优先搜索生成轨迹。启发式函数[10]首先估计每个箱子-目标配对将箱子推到目标所需的移动次数（忽略其他箱子），然后使用箱子和目标之间的最小二分匹配代价作为启发式值。Sokoban是三个领域中最困难的，具有更长的搜索轨迹和更复杂的转换动态，为不同方法提供了具有挑战性的测试平台。

## 4 搜索轨迹访问的效果

我们首先研究拥有搜索轨迹的访问权限是否能使LLM成为更好的搜索智能体。为此，我们将基于轨迹条件的推理策略与局部状态搜索策略进行比较。在基于轨迹条件的情况下，LLM观察完整的搜索轨迹并直接预测下一步搜索。在局部状态的情况下，我们运行一个由启发式函数引导的外部最佳优先搜索算法，该启发式函数使用相同的LLM学习，在扩展时仅观察当前候选状态和目标状态。

### 4.1 基于轨迹条件的LLM推理策略

我们训练一个基于完整搜索历史作为条件、预测下一步搜索的LLM推理策略。搜索轨迹被线性化为一系列扩展，每个搜索步骤使用以下模板编写：
> EXPAND ACT {action} -> {resulting state}
这种序列化方式反映了当前推理轨迹的风格，即模型尝试不同的动作，当一个分支失败时进行回溯，但不明确标注树结构。尽管如此，以先前轨迹为条件，原则上可以使策略利用更多的历史信息。