LinTree: Improving LLM Reasoning with Explicitly Structured Search Histories

Title: LinTree: Improving LLM Reasoning with Explicitly Structured Search Histories
Authors: Liwei Kang, Yee Whye Teh, Wee Sun Lee
Affiliations: National University of Singapore, University of Oxford
Venue: arXiv:2506.01394
Year: 2026
Pages: 16 (including appendix)
Code URL: Not explicitly mentioned in the paper

1. 研究摘要 (Research Summary)

大型语言模型（Large Language Models, LLMs）在推理任务上的进步，很大程度上依赖于一种核心思想：与其让模型直接输出最终答案，不如引导它生成一系列中间推理步骤，逐步探索、修正并最终抵达正确答案。这一思想催生了 Chain-of-Thought（CoT）提示、自我反思（self-reflection）以及后续诸多变体。然而，当这些中间步骤被视作一个搜索过程时——即模型在思考树的各个分支间探索、回溯、再尝试——一个根本性的理论问题浮现出来：模型真的充分利用了它所拥有的全部搜索历史信息吗？还是说，这些丰富的历史仅仅被当作了一串扁平的文本序列，其内在的树形结构被淹没在自由流动的自然语言之中？

Kang 等人的这项工作正是从这个核心问题出发，提出了一个看似简单却极具洞察力的命题：LLM 推理 traces 中隐含的搜索树结构，只有当它被显式地标注出来时，模型才能真正利用这一结构来提升搜索效率和任务成功率。这一命题的深层意义在于，它挑战了当前 LLM 推理研究中对“trace 条件化”（trace-conditioned reasoning）能力的乐观假设。人们普遍认为，只要模型能访问完整的搜索历史，它就能比仅依赖局部状态信息的传统启发式搜索做出更优的决策——因为模型可以利用一个分支上获得的经验来指导另一个分支的探索，避免重复访问已证明无效的区域，并协调非局部的搜索上下文。然而，Kang 等人的实验揭示了一个令人警醒的事实：在三种受控的搜索环境——Blocks World、Grid Navigation 和 Sokoban——中，仅让模型条件化于完整的搜索 trace 并不足以可靠地超越仅观察当前局部状态的 LLM 启发式搜索基线。也就是说，trace 访问本身并不自动转化为更强的搜索能力。

这一发现构成了本研究的第一个关键贡献：它通过一个精心设计的对照实验，系统地量化了“隐式 trace 条件化”与“局部状态启发式搜索”之间的性能差距，证明了前者在现有的 trace 表示方式下并不具备理论上的压倒性优势。这一结果打破了关于 LLM 推理中历史信息价值的浪漫想象，迫使研究者直面一个更尖锐的问题：为什么丰富的历史信息未能被充分利用？作者给出的诊断是，当搜索 trace 被线性化为一段连续的文本时，底层的树形拓扑结构被丢失了。模型在回溯或切换分支时，虽然可能在文本中写下“让我尝试另一种方法”之类的自然语言提示，但它通常不会显式地指明正在回到哪一个先前的搜索状态。于是，搜索历史中的探索与回溯证据虽然存在，其树形结构却必须被模型从上下文中推断——这对模型而言是一种额外的认知负担，也是一种信息损耗。

基于这一诊断，本研究的第二个核心贡献应运而生：提出一种最小化的 trace 表示修改——parent pointer（父指针）——来显式标注搜索树的拓扑结构。这种被称为 LinTree（Linearized Tree）的表示方法，在每一次搜索扩展时不仅记录动作和结果状态，还显式地标明该扩展是从哪一个已有的前沿状态（frontier state）派生而来。这就像是将一本松散叙述的探索日志改写为一棵带有清晰节点编号和父子关系的序列化搜索树。实验结果表明，在相同的训练数据、相同的监督微调（SFT）和相同的强化学习（GRPO）优化流程下，使用显式树结构的策略（explicit policy）在三个领域均显著优于使用隐式 trace 的策略（implicit policy），无论是在求解成功率还是在搜索扩展次数上。特别是在 Sokoban 这一最具挑战性的领域中，显式策略在引入生成约束后达到了 98.9% 的求解率，与局部状态启发式基线的 99.1% 持平，同时使用的扩展次数却更少（54.70 对 64.08）。

这项研究的影响是深远的。它提醒我们，在 LLM 推理系统的设计中，信息的“可及性”与信息的“可用性”是两个截然不同的概念。仅仅让模型看到搜索历史是不够的；关键在于如何将这些历史组织成模型能够有效利用的结构。LinTree 的提出为这一方向提供了一个简洁而有力的范例，它表明即使在模型规模、训练数据和优化算法保持不变的情况下，仅仅改变 trace 的表示方式就能显著提升性能。这启发了一个更广泛的思考：LLM 推理的改进不仅需要更好的训练目标或更大的模型，还需要更合理的“接口设计”——即推理 traces 与底层计算结构之间的映射方式。对于未来的研究而言，这项工作为探索“结构化监督”（structured supervision）开辟了新的路径，并暗示了在更复杂的开放域推理任务中，显式结构化表示可能同样具有巨大的潜力。

2. 理论框架 (Theoretical Framework)

要理解 LinTree 的理论根基，需要追溯 LLM 推理研究从简单的链式思考到搜索树视角的演进脉络。Chain-of-Thought（CoT） prompting 的突破性贡献（Wei et al., 2022）在于揭示了 LLMs 可以通过生成中间推理步骤来显著提升复杂任务的表现。这一发现引发了后续研究的广泛探索：从自我反思（self-reflection）允许模型评估并修正自己的推理（Madaan et al., 2023; Shinn et al., 2023），到问题分解（problem decomposition）将复杂任务拆分为更简单的子问题（Zhou et al., 2022），再到迭代精炼（iterative refinement）让模型在多次尝试中逐步逼近正确答案。这些方法的共同特征是，它们都在扩展推理的“灵活性”——允许模型尝试多种方案、修正早期选择、探索不同路径。然而，一个被长期忽视的理论维度是：这些灵活推理过程中的分支、回溯和选择过程，其底层的树形结构通常被留在生成的文本中，而不是被显式地表示为一种计算结构。

Yao et al. (2023) 的 Tree-of-Thoughts 和 Sel et al. (2023) 的 Algorithm of Thoughts 等研究工作将这一隐含结构部分地揭示出来，将推理过程视为在思想树上的隐式搜索。在这一视角下，一条推理 trace 可以被看作一棵搜索树的线性化（linearization），其中每一步要么扩展现有分支，要么修订先前的选择，要么回到更早的节点以探索替代方案。这种线性化视角为理解 LLM 推理提供了一个强大的分析框架：它将模型从单纯的“文本生成器”重新概念化为一个“搜索代理”（search agent），其生成的文本不仅是表达，更是一种搜索策略的执行记录。

然而，这一理论框架中存在一个关键的张力。传统启发式搜索（如 A* 或 best-first search）的决策依赖于对当前局部状态的评估——通过启发式函数 $h (s)$ 来估计从当前状态 $s$ 到达目标的最优代价。而 LLM 的 trace 条件化推理则拥有一个潜在的优势：在每一步选择下一个扩展时，它条件化于整个先前的搜索 trace，而非仅仅当前状态。理论上，这意味着模型可以访问远为丰富的信息：它可以利用在一条分支上收集的证据来指导另一条分支的决策，可以记住哪些区域已被证明无效，可以协调不同分支之间的搜索上下文。如果这一优势能够被充分发挥，trace 条件化的 LLM 理应成为一个比任何局部状态启发式更强大的搜索代理。

Kang 等人的研究通过严格的实验检验了这一理论预期。他们设计了一个精妙的对照：一方面，训练一个 trace-conditioned reasoning policy，该策略条件化于完整的搜索历史并直接预测下一个搜索步骤；另一方面，运行一个 local-state heuristic-guided best-first search，其中 LLM 仅被用作启发式函数，评估当前候选状态-动作对的优劣，而实际的树搜索由外部算法控制。这一比较的核心在于公平性——两者使用相同的 LLM 骨干（Qwen3-0.6B），接受相同的训练数据，并经过相同的 SFT 和 RL 优化流程。实验结果出人意料：在隐式 trace 表示下，trace 条件化的策略并未可靠地超越局部状态启发式基线。这一发现揭示了一个深刻的理论洞察：信息的可用性（availability）不等于信息的可利用性（exploitability）。当搜索树结构被线性化为一串文本时，模型虽然“看到”了历史，但这些历史中的结构信息——哪些节点是父子关系、哪些分支已被探索、回溯指向哪个节点——被编码为模糊的自然语言线索，需要模型自行推断。这种推断负担削弱了 trace 条件化本应带来的优势。

在这一理论背景下，LinTree 的提出可以被理解为一种**表示学习（representation learning）**的干预：它不是改变模型本身，而是改变信息被呈现给模型的方式。parent pointer 的引入，本质上是在 trace 中为每一个搜索节点赋予一个显式的标识符（state identifier, sid），并在每次扩展时标注该扩展是从哪一个 sid 派生而来。这使得线性化的 trace 被重新嵌入为一个明确的树结构，模型不再需要费力地从文本中推断拓扑关系。从信息论的角度看，这种显式标注减少了模型的条件不确定性：给定当前 trace 和 parent pointer，模型对搜索树的拓扑的信念更加精确。从认知负荷的角度看，它将一项原本需要“阅读理解”才能完成的任务，转化为了一项可以直接“查询”的结构化操作。这一理论视角将 LinTree 置于一个更广泛的范式中：即通过改善推理 traces 与底层计算结构之间的接口，来提升 LLM 作为搜索代理的效率和可靠性。

3. 技术架构 (Technical Architecture)

LinTree 的技术系统围绕一个两阶段训练流水线构建，其核心设计目标是在受控环境中精确地比较不同信息表示方式对搜索性能的影响。整个系统可以看作由三个主要组件协同构成：推理环境（reasoning environments）、策略训练流水线（policy training pipeline）和对比评估框架（comparative evaluation framework）。这些组件之间的交互经过精心设计，以确保任何观察到的性能差异都可以归因于 trace 表示方式的不同，而非数据、模型或优化算法的差异。

系统的输入是三个经典的搜索问题领域：Blocks World、Grid Navigation 和 Sokoban。每个领域的问题实例被文本化为一个固定的提示格式（prompt format），包含初始状态、目标状态以及领域特定的描述。对于 Blocks World，状态被序列化为一个有序的栈列表，例如 "S{ 0:A<B ; 1:C ; 2:D }"，其中每个栈从底到顶书写；动作表示为移动一个顶部块，例如 "B:A->TABLE" 表示将 B 从 A 的顶部移到桌面上。Grid Navigation 在一个 10×10 的二维网格上进行，状态仅记录智能体位置 "A=(r,c)"，动作空间为四个基本移动 U、D、L、R。Sokoban 的状态则包含玩家位置和所有箱子位置，动作同样为四个基本移动。这些状态表示在搜索过程中被动态更新，而环境配置（如网格布局、障碍物位置）始终保留在提示中作为固定上下文。这种设计确保了模型在搜索过程中只需要处理局部变化的状态表示，而全局环境信息则通过提示的持续存在提供背景。

训练流水线的核心是两阶段优化：监督微调（SFT） followed by 强化学习（GRPO）。在 SFT 阶段，作者首先使用基于规则的启发式函数（rule-based heuristic）在三个领域中运行最佳优先搜索（best-first search），生成高质量的搜索 traces。这些 traces 不仅包含成功路径，还包含回溯、分支探索和失败尝试，因此真实反映了搜索过程中的完整行为。每个 SFT 样本由一个提示和一个补全组成：提示包含问题实例的配置，补全包含两个部分——思考过程（即搜索 trace）和最终计划（从搜索 trace 中提取的到达目标的动作序列）。模型被训练为同时生成这两部分。这里的关键工程决策是，SFT 数据来源于规则启发式搜索，而非人工标注或简单最优路径。这确保了模型在初始阶段就接触到“搜索行为”的示范，包括如何探索、如何回溯、如何评估不同分支。

在强化学习阶段，作者采用 GRPO（Group Relative Policy Optimization）来进一步优化策略。奖励函数的设计体现了对搜索效率和正确性的双重关注：

R (τ) = 1 [valid (τ) \land correct (τ)] (1 - λ \sum_{t = 0}^{N_{\exp} (τ) - 1} γ^{t})

其中 $1 [valid (τ) \land correct (τ)]$ 是一个二元指示函数，当搜索 trace $τ$ 有效且最终计划正确时取值为 1，否则为 0。 $N_{\exp} (τ)$ 表示 trace 中的搜索扩展次数。参数 $0 < γ < 1$ 是几何衰减因子， $λ$ 是惩罚尺度。每一额外扩展会从正确性奖励中减去一个折扣项，因此更短的正确 traces 获得更高的回报。选择 $λ < 1 - γ$ 确保每个正确 trace 仍获得正奖励，从而始终优于任何错误 trace。在实际实验中， $λ = 0.005$ 和 $γ = 0.99$ 。GRPO 每组采样 $N = 8$ 条 rollouts，运行 1 个 epoch，学习率为 $1 \times 10^{- 5}$ 。所有训练在单张 NVIDIA H100 GPU 上完成。这一奖励设计的精妙之处在于，它将搜索效率直接转化为可优化的奖励信号，而不仅仅是要求模型“找到答案”。

与 trace 条件化策略形成对照的是局部状态 LLM 启发式系统。该系统采用一个经典的外部搜索控制器（如 Algorithm 1 所示的 best-first tree search）维护搜索树，而 LLM 仅被调用为启发式函数 $h_{θ} (s, a, g)$ ，为每个候选的（状态, 动作）对评分。具体来说，在每次扩展时，对于前沿（frontier）上的每个候选状态-动作对，LLM 接收当前状态 $s$ 、候选动作 $a$ 和目标 $g$ 作为输入，输出一个启发式值（通过额外的 MLP 头部获得）。外部搜索算法选择启发式值最低的候选（或从 softmax 分布中采样），应用动作获得新状态，并将其作为子节点加入搜索树。这一过程的数学表达为：

π_{θ} (c ∣ C) = \frac{\exp (- h_{θ} (c))}{\sum_{c^{'} \in C} \exp (- h_{θ} (c^{'}))}

其中 $C$ 是前沿候选集， $c$ 是被选中的候选。策略梯度为：

\nabla_{θ} J (θ) = \frac{1}{N} \sum_{i = 1}^{N} \sum_{t = 0}^{T_{i} - 1} A_{i} \nabla_{θ} \log π_{θ} (c_{i, t} ∣ C_{i, t})

其中 $A_{i} = \frac{r_{i} - μ}{σ + ϵ}$ 是标准化优势， $μ$ 和 $σ$ 是 $N$ 条 traces 奖励的均值和标准差。这一局部状态启发式系统同样经过 SFT 和 RL 两阶段训练，使用与 trace 条件化策略完全相同的数据和优化设置，从而确保了比较的公平性。所有基线（包括 BFS with rule-based heuristic、BFS with RL-trained heuristic、SFT-implicit、GRPO-implicit 等）都在这一统一的框架下进行评估，其搜索预算在 RL 训练时为 500 次扩展，在评估时为 200 次扩展。

LinTree 表示本身的技术改动极其简洁，却极具针对性。在隐式格式中，每次扩展写作：

EXPAND ACT {action} -> {resulting state}

而在显式（LinTree）格式中，每次扩展写作：

EXPAND sid={parent_id} ACT {action} -> sid={new_id} {resulting state}

这里 sid 是 state identifier 的缩写，每个被访问的状态都被赋予一个唯一标识符。parent_id 指明了当前扩展是从哪一个已有状态派生而来，而 new_id 则为新到达的状态分配一个新标识。这种改动在信息内容上并不增加新的搜索行为——两者都来源于相同的底层搜索 traces——它仅仅改变了这些行为在文本中被编码的方式。然而，正是这种“结构显式化”使得模型能够更可靠地追踪搜索树、识别回溯点、以及从 traces 中提取最终计划。值得注意的是，在 Navigation 领域中，作者还发现了一个关键的实现细节：对于走入墙壁的无效动作（BLOCKED），trace 中必须显式记录这些失败的尝试，而非静默剪枝。这是因为基于曼哈顿距离的启发式会给出一个强烈的方向偏好，如果失败的候选被静默移除，模型看到的扩展顺序将不再与启发式的排序一致，从而增加了学习难度。这一细节反映了作者在技术实现上的深度思考和对学习动态的敏锐洞察。

4. 实验评估 (Experimental Evaluation)

LinTree 的实验设计遵循了一个清晰的科学发现叙事：首先检验一个理论假设，当假设被否定时追问原因，然后提出并验证一个改进方案。这一叙事脉络贯穿了三个受控搜索领域的全部实验结果，使论文的阅读体验如同跟随作者一同经历了一场从困惑到顿悟的研究旅程。

实验的第一个阶段聚焦于核心问题：trace 条件化是否优于局部状态启发式？为此，作者构建了一个包含五种方法的比较矩阵：BFS（Pretrained）——使用基于规则的启发式运行最佳优先搜索；BFS（RL）——经过强化学习优化的 LLM 启发式搜索；SFT-implicit——在隐式 traces 上监督微调的 trace 条件化策略；GRPO-implicit——在隐式 traces 上进一步经过 GRPO 优化的策略；以及 GRPO-explicit（在后续阶段引入）。表 2 汇总了这些方法的性能对比，其结果揭示了一个与直觉相悖的模式：在 Blocks World 中，GRPO-implicit 的求解率为 97.3%，低于 BFS（RL）的 99.8%，扩展次数为 8.25，略优于 BFS（RL）的 8.56；在 Navigation 中，GRPO-implicit 的求解率仅为 94.9%，远低于 BFS（RL）的 100.0%，扩展次数为 14.80，略优于 BFS（RL）的 16.99；在 Sokoban 中，差距更为明显：GRPO-implicit 的求解率仅 85.9%，而 BFS（RL）高达 99.1%，扩展次数为 63.54 对 64.08，优势微弱。

Method	Blocks World Success↑	Blocks World Expansions↓	Navigation Success↑	Navigation Expansions↓	Sokoban Success↑	Sokoban Expansions↓
BFS (Pretrained)	99.7 ± 0.17	9.54 ± 0.31	100.0 ± 0.00	20.27 ± 0.42	94.9 ± 0.70	73.21 ± 2.11
BFS (RL)	99.8 ± 0.14	8.56 ± 0.18	100.0 ± 0.00	16.99 ± 0.37	99.1 ± 0.30	64.08 ± 1.86
SFT-implicit	90.0 ± 0.95	9.12 ± 0.16	90.6 ± 0.92	15.39 ± 0.18	74.8 ± 1.37	68.24 ± 7.70
GRPO-implicit	97.3 ± 0.51	8.25 ± 0.14	94.9 ± 0.70	14.80 ± 0.16	85.9 ± 1.10	63.54 ± 4.12

Table 2: Policies with versus without access to the search trace, evaluated on the three reasoning domains. Lower is better for expansions. Subscripts show standard errors.

这一结果表明，尽管 GRPO-implicit 在搜索效率上有时能略胜 BFS（RL）一筹，但其求解成功率在所有三个领域都明显落后，尤其是在 Sokoban 中差距高达 13.2 个百分点。这说明，在隐式 trace 条件下，模型并未充分发挥其访问完整搜索历史的理论优势。一个可能的解释是，SFT-implicit 阶段从规则启发式 traces 中学习的搜索行为本身就存在模仿误差，而 GRPO 虽然改善了策略，但隐式表示的信息瓶颈限制了其进一步提升的空间。换言之，模型在隐式 traces 中“读”到了历史，但无法 reliably 地“理解”这些历史所编码的树形结构。

实验的第二个阶段引入 LinTree 的显式表示，并系统地比较了四个策略：SFT-implicit、SFT-explicit、GRPO-implicit 和 GRPO-explicit。表 3 呈现了这些结果的详细对比，揭示了一个引人注目的发现：在 SFT 阶段，显式标注已经带来了显著的性能提升。在 Blocks World 中，SFT-explicit 的求解率（89.6%）与 SFT-implicit（90.0%）基本持平，但在 Navigation 中从 90.6% 提升至 95.2%，在 Sokoban 中从 74.8% 大幅提升至 85.6%。这表明，显式树结构主要提升了模型在模仿学习阶段恢复有效搜索行为的能力，特别是在更复杂的领域中。然而，在搜索效率方面，SFT-explicit 在 Blocks World 和 Navigation 中与 SFT-implicit 相近或略差，在 Sokoban 中甚至使用了更多扩展（73.26 对 68.24），说明显式结构在初始阶段主要帮助的是“学对”而非“学优”。

Method	Training	Blocks World Success↑	Blocks World Expansions↓	Sokoban Success↑	Sokoban Expansions↓	Navigation Success↑	Navigation Expansions↓
No parent pointer	SFT	90.0 ± 0.95	9.12 ± 0.16	74.8 ± 1.37	68.24 ± 7.70	90.6 ± 0.92	15.39 ± 0.18
With parent pointer	SFT	89.6 ± 0.97	9.06 ± 0.45	85.6 ± 1.11	73.26 ± 5.88	95.2 ± 0.68	15.63 ± 0.18
No parent pointer	GRPO	97.3 ± 0.51	8.25 ± 0.14	85.9 ± 1.10	63.54 ± 4.12	94.9 ± 0.70	14.80 ± 0.16
With parent pointer	GRPO	100.0 ± 0.00	7.31 ± 0.08	89.6 ± 0.97	52.82 ± 3.35	100.0 ± 0.00	14.28 ± 0.12
With parent pointer	GRPO + gen. constraint	—	—	98.9 ± 0.33	54.70 ± 4.62	—	—
—	BFS (pretrained)	99.7 ± 0.17	9.54 ± 0.31	94.9 ± 0.70	73.21 ± 2.11	100.0 ± 0.00	20.27 ± 0.42
—	BFS (RL)	99.8 ± 0.14	8.56 ± 0.18	99.1 ± 0.30	64.08 ± 1.86	100.0 ± 0.00	16.99 ± 0.37

Table 3: Implicit versus explicit trace annotations on controlled reasoning domains. Lower is better for expansions. Subscripts show standard errors computed over evaluation instances.

真正的突破发生在 GRPO 阶段。从 SFT 显式检查点初始化后，GRPO-explicit 在所有三个领域都全面超越了 GRPO-implicit：在 Blocks World 中，求解率从 97.3% 提升至 100.0%，扩展次数从 8.25 降至 7.31；在 Navigation 中，求解率从 94.9% 提升至 100.0%，扩展次数从 14.80 降至 14.28；在 Sokoban 中，求解率从 85.9% 提升至 89.6%，扩展次数从 63.54 大幅降至 52.82。更值得注意的是，在引入生成约束（generation constraint）以防止模型生成无效动作（如撞墙或推箱子到被占据的格子）后，GRPO-explicit 在 Sokoban 中的求解率跃升至 98.9%，与 BFS（RL）的 99.1% 几乎持平，而扩展次数（54.70）仍然低于 BFS（RL）的 64.08。这一结果意味着，在相同的“环境知识”条件下（局部启发式通过外部转移函数获得完美的环境知识，而显式 trace 策略通过生成约束模拟这一知识），LinTree 表示不仅达到了相当的求解率，还实现了更高的搜索效率。

从实验设计的角度看，这些比较具有高度的内部效度。由于隐式策略和显式策略是在完全相同的底层搜索 traces、相同的模型骨干（Qwen3-0.6B）、相同的训练数据（20K SFT 实例和 20K RL 实例）、相同的学习率（ $1 \times 10^{- 5}$ ）、相同的训练 epoch 数（SFT 4 epoch，GRPO 1 epoch）以及相同的 GPU 硬件（单张 NVIDIA H100）上训练的，观察到的性能差异几乎可以完全归因于 trace 表示方式的不同。这种严格的控制使得作者的结论具有很强的说服力：不是模型不够好，也不是数据不够多，而是信息的表示方式不够友好。

为了深入理解显式结构带来的行为变化，作者进一步分析了失败案例和搜索空间的探索模式。表 4 展示了失败案例的分解：在那些模型未能正确求解的实例中，有多少是因为搜索失败（未能找到通往目标的路径），有多少是因为计划提取失败（搜索找到了正确路径但模型未能从 trace 中正确提取）。结果显示，显式策略在所有领域都有更低的计划提取失败率。例如，在 Sokoban 的 GRPO 阶段，GRPO-implicit 的失败案例中有 71.43% 是提取失败，而 GRPO-explicit 仅为 45.46%。这一分析揭示了显式 parent pointer 的一个直接机制优势：它使得模型更容易从自己的搜索 trace 中回溯和重构正确的计划路径。表 5 则展示了在 Navigation 领域中，不同策略对状态空间的探索多样性。作者定义了平均成对距离 $\bar{d} (S) = \frac{1}{| S |^{2}} \sum_{s, s^{'} \in S} d (s, s^{'})$ ，其中 $d (s, s^{'})$ 是网格上两个状态之间的最短路径距离。结果显示，显式策略的平均成对距离最高（4.19），高于隐式策略（4.11）和局部启发式（3.99）。这意味着显式策略在搜索过程中覆盖的状态空间更加分散，更少陷入局部邻域的重复探索。这一发现支持了作者的假设：当模型能够可靠地追踪已探索的树区域时，它更有效地将搜索资源导向未探索的区域，从而提升了整体搜索效率。

Method	Blocks World	Navigation	Sokoban
SFT-implicit	41.44%	96.67%	80.78%
SFT-explicit	26.00%	94.52%	54.17%
GRPO-implicit	74.07%	94.12%	71.43%
GRPO-explicit	N/A	N/A	45.46%

Table 4: Plan-extraction failures among incorrect runs. Each cell reports the fraction of failed cases in which the failing reason is extraction failure. "N/A" indicates that the policy has no failed cases on that domain (100% solve rate).

Method	$\bar{d}$ ↑
BFS (RL)	3.99
GRPO-implicit	4.11
GRPO-explicit	4.19

Table 5: Average pairwise distance of visited states in the search trees produced by different policies on Navigation. Higher values indicate more diverse exploration of the state space.

5. 案例研究 (Case Studies)

虽然 LinTree 论文的正文部分主要集中在统计性的实验对比上，但其附录中提供的具体 trace 示例为理解显式与隐式表示之间的差异提供了极具启发性的微观视角。通过仔细审视这些案例，我们可以更直观地感受到 LinTree 如何在技术实现层面改变了模型与搜索历史的交互方式。

以 Navigation 领域的一个实例为例（见附录 A.2），在隐式格式中，搜索 trace 被记录为一系列连续的扩展和动作：

EXPAND A=(7,6)
EXPAND ACT U -> A=(6,6)
EXPAND ACT U -> A=(5,6)
BLOCKED ACT L -> (5,5) WALL
EXPAND ACT L -> A=(6,5)
BLOCKED ACT U -> (5,5) WALL
EXPAND ACT L -> A=(6,4)
EXPAND ACT U -> A=(5,4)
BLOCKED ACT R -> (5,5) WALL
EXPAND ACT L -> A=(5,3)
EXPAND ACT L -> A=(5,2)
GOAL_REACHED

在这一表示中，模型执行了一个从起点 (7,6) 出发，连续向上两次、向左一次（被墙阻挡）、向左再次、向上（被阻挡）、向左两次、向上、再向左两次的搜索过程。对于人类读者而言，我们可以通过观察状态坐标的变化来推断搜索路径：从 (7,6) 到 (6,6) 到 (5,6)，然后尝试向左失败，回到 (6,6) 再向左到 (6,5)，再尝试向上失败，然后继续向左到 (6,4)，向上到 (5,4)，尝试向右失败，再向左到 (5,3) 和 (5,2) 到达目标。然而，这种推断需要读者在脑海中维护一个隐式的状态地图，并追踪哪些动作是从哪个状态发出的。对于模型来说，这意味着当它在生成第 10 行 "EXPAND ACT L -> A=(5,3)" 时，它必须从上下文中推断出这个向左的动作是从当前状态 (5,4) 发出的，而不是从更早的 (6,4) 或 (6,5)。这种推断在短 trace 中或许可行，但在长而复杂的搜索中极易出错。

相比之下，LinTree 的显式格式将同一搜索过程编码为：

EXPAND sid=0 A=(7,6)
EXPAND sid=0 ACT U -> sid=1 A=(6,6)
EXPAND sid=1 ACT U -> sid=2 A=(5,6)
BLOCKED ACT L -> (5,5) WALL
EXPAND sid=1 ACT L -> sid=3 A=(6,5)
BLOCKED ACT U -> (5,5) WALL
EXPAND sid=3 ACT L -> sid=4 A=(6,4)
EXPAND sid=4 ACT U -> sid=5 A=(5,4)
BLOCKED ACT R -> (5,5) WALL
EXPAND sid=5 ACT L -> sid=6 A=(5,3)
EXPAND sid=6 ACT L -> sid=7 A=(5,2)
GOAL_REACHED

在这一版本中，每个状态都被赋予了一个唯一的 sid（state identifier）。起点 (7,6) 是 sid=0，第一次向上移动到达 (6,6) 被标记为 sid=1，第二次向上到达 (5,6) 是 sid=2。关键的结构性信息在于：当模型在 sid=2 尝试向左（EXPAND sid=2 ACT L）失败被墙阻挡后，下一个成功的扩展是 EXPAND sid=1 ACT L -> sid=3 A=(6,5)——它明确地告诉模型，这个向左的动作是从 sid=1（即状态 (6,6)）发出的，而不是从 sid=2（状态 (5,6)）发出的。这意味着模型在 (5,6) 尝试向左失败后，回溯到了 (6,6)，并从那里尝试了一个不同的方向。在隐式表示中，这种回溯关系必须通过状态坐标的变化来推断；而在显式表示中，它通过 sid=1 被直接标注。

这种显式标注在更复杂的分支场景中尤为重要。以 Sokoban 的一个实例为例（附录 A.3），在隐式格式中，搜索 trace 包含 13 次扩展，其中多次出现状态重复（如 P=(2,5) 在不同位置出现），模型必须推断这些重复是回溯还是循环。而在显式格式中，每次扩展都标注了 parent_id，使得搜索树的拓扑一目了然。例如：

EXPAND sid=0 P=(3,5) B={(2,6),(3,4)}
EXPAND sid=0 ACT U -> sid=1 P=(2,5) B={(2,6),(3,4)}
EXPAND sid=1 ACT R -> sid=2 P=(2,6) B={(2,7),(3,4)}
EXPAND sid=2 ACT U -> sid=3 P=(1,6) B={(2,7),(3,4)}
EXPAND sid=2 ACT D -> sid=4 P=(3,6) B={(2,7),(3,4)}
EXPAND sid=2 ACT L -> sid=5 P=(2,5) B={(2,7),(3,4)}

在这里，从 sid=2（P=(2,6)）出发有三个分支：向上到 sid=3，向下到 sid=4，向左到 sid=5。sid=5 的状态 P=(2,5) 与 sid=1 的状态相同，但 sid=5 的箱子位置不同（B={(2,7),(3,4)} 而非 B={(2,6),(3,4)}），这明确表明 sid=5 是一个新的搜索节点，而不是对 sid=1 的重复访问。在隐式表示中，模型需要记住箱子位置的变化来区分这两个状态；而在显式表示中，sid 本身就区分了它们。这种结构上的清晰性极大地降低了模型的认知负荷，使得模型可以更专注于搜索策略本身，而非从文本中解码搜索树的拓扑。

这些案例所揭示的更深层次的原则是：显式结构不仅仅是一种表示上的便利，它实际上改变了模型可执行的计算操作。在隐式表示中，模型需要“理解”文本才能推断结构；在显式表示中，模型可以“查询”结构。这种从理解到查询的转变，类似于从自然语言描述的数据库模式到 SQL 查询的转变——前者需要解析和推理，后者只需执行。在 LLM 的语境中，这意味着显式结构使得搜索历史的利用变得更加可靠和可预测，从而减少了 compounding error 的累积。

6. 综合价值与局限 (Synthesis — Value and Limitations)

LinTree 这项工作在 LLM 推理研究的版图上占据了一个独特而重要的位置。它既不是关于更大模型的论证，也不是关于新训练算法的宣告，而是关于一个更为基础却长期被忽视的维度——信息表示——对推理能力的决定性影响。这一研究视角的转换本身就具有重要的理论意义：它将讨论从“模型能否做 X”转向了“如何让模型更有效地做 X”，从而开辟了一个介于模型架构与提示工程之间的中间地带。

从理论显著性的角度看，LinTree 的核心贡献在于它提供了一个反直觉的实证发现：在受控环境中，条件化于完整搜索历史的 LLM 策略并不自动优于仅条件化于局部状态的启发式策略。这一发现打破了关于 LLM 推理中“上下文窗口优势”的未经检验的假设，迫使研究者重新思考“更多上下文”与“更好推理”之间的非线性关系。更重要的是，LinTree 通过引入 parent pointer 这一最小化干预，证明了性能差距的主要来源不在于模型能力或训练数据，而在于 trace 的表示方式。这一结论将“表示学习”的概念从传统的向量表示（如嵌入、表征）扩展到了文本表示的领域，暗示了 LLM 的输入格式本身也是一种可优化的超参数。

从实践影响的角度看，LinTree 的启示具有广泛的适用性。任何涉及 LLM 进行多步推理、搜索、规划或探索的应用场景，都可能受益于结构化 traces 的设计。例如，在代码生成中，显式标注调试或回溯的 AST（抽象语法树）节点关系可能帮助模型更可靠地修正代码；在数学证明中，显式标注子目标的依赖关系可能帮助模型更有效地组织证明结构；在对话系统中，显式标注对话树的上下文切换可能帮助模型更准确地追踪讨论主题。然而，将 LinTree 从受控的搜索领域迁移到这些开放域任务并非没有挑战。Parent pointer 的设计在 Blocks World、Navigation 和 Sokoban 中是自然的，因为搜索树的节点和边具有明确的、可离散化的定义。在开放域推理中，什么是“节点”，什么是“边”，如何定义状态标识符，这些都是尚未解决的问题。因此，LinTree 当前更像是一个概念证明，而不是一个即插即用的解决方案。

这项研究最令人信服的方面在于其实验设计的严谨性和控制性。作者 painstakingly 地确保了所有比较方法在数据、模型、训练流程和评估指标上的一致性，使得性能差异几乎完全可归因于 trace 表示。这种实验哲学值得在 LLM 研究中更广泛地推广。此外，论文对失败案例的深入分析（表 4）和对搜索空间探索多样性的量化（表 5）为结论提供了多角度的支撑，而不仅仅是简单的成功率数字。

然而，LinTree 也存在一些诚实的局限性。首先，实验领域的选择——三个完全可观察、确定性、离散动作的搜索环境——虽然为精确控制和可重复性提供了理想条件，但也限制了结论向更复杂现实场景的推广。在部分可观察、随机性、连续动作空间的任务中，搜索树的定义可能不再清晰，parent pointer 的设计将面临根本性挑战。其次，作者在论文末尾明确承认，由于计算资源限制，所有实验仅在 Qwen3-0.6B 这一个基础模型上进行。一个自然的问题是：LinTree 的效益是否随模型规模变化？更大的模型（如 7B、70B 或更大）是否能在隐式 traces 中更好地推断树结构，从而使显式标注的边际收益减小？或者，更大的模型反而能从显式结构中获得更显著的收益，因为它能利用结构进行更复杂的推理？这些问题留给了后续研究。第三，奖励函数的设计虽然巧妙（公式 1），但是否存在更优的效率奖励形式仍值得探索。附录 B 中讨论的两个替代方案（恒定步惩罚和几何衰减）都因训练稳定性问题而被放弃，这表明在强化学习中优化搜索效率仍然是一个微妙的工程问题。最后，LinTree 的显式表示虽然在训练时有效，但在推理时增加了文本生成的长度（每个扩展需要额外的 sid 标注），这可能在计算资源敏感的场景中成为一个实际考量。

从更广阔的学术趋势来看，LinTree 与当前 LLM 研究中对“结构化推理”的日益关注相呼应。无论是 Tree-of-Thoughts 的外部搜索控制器、Graph of Thoughts 的图结构思维，还是近期对 LLM 推理过程显式规划的研究，都指向一个共同方向：让 LLM 的推理过程更结构化、更可解释、更可控。LinTree 的独特之处在于它在模型内部实现了这种结构化，而不依赖外部控制器。这种“内源结构化”与“外源结构化”的对比，为未来的混合架构设计提供了有价值的参考。

7. 延伸阅读与思考 (Further Reading and Reflection)

LinTree 的研究深深植根于近年来 LLM 推理领域的几条并行发展线索，理解这些前驱工作有助于更准确地定位 LinTree 的学术贡献。在 Chain-of-Thought 的奠基性工作方面，Wei et al. (2022) 的原始论文展示了通过少量示例提示来激发中间推理步骤的力量；Nye et al. (2021) 的 Scratchpads 工作则更早地探索了为语言模型提供中间计算空间的概念。这些工作为 LinTree 的 trace 条件化视角提供了基础：如果 LLM 能够通过中间步骤提升推理，那么这些步骤本身就可以被看作一个搜索过程的记录。在自我反思和迭代改进的方向上，Madaan et al. (2023) 的 Self-Refine 和 Shinn et al. (2023) 的 Reflexion 允许模型通过自我评估来修正推理，Chen et al. (2024) 的 Thought Rollback 则探索了动态回溯机制。这些工作与 LinTree 共享一个核心动机：让 LLM 的推理过程更具适应性和容错性。然而，LinTree 的批评性视角在于，这些自适应机制的有效性可能受限于 traces 的表示质量——如果模型无法可靠地从自己的历史中推断结构，那么反思和回溯的效果也会大打折扣。

在外部搜索控制器的谱系中，Yao et al. (2023) 的 Tree-of-Thoughts 是一个关键参照。它将 LLM 包装在一个显式的树搜索算法中，由外部控制器负责扩展、评估和剪枝，而 LLM 仅在局部路径上生成候选。Katz et al. (2024) 的 Thought of Search 和 Hao et al. (2023) 的 Reasoning-as-Planning 延续了这一范式。Mittal et al. (2025) 的 Learning to Search from Demonstration Sequences 则与本研究关系最为密切，它同样关注从演示序列中学习搜索策略，但侧重于局部状态的价值估计。LinTree 的独特贡献在于它比较了外部控制器的局部状态范式与 trace 条件化的全局状态范式，并证明了后者的优势在表示不当的情况下无法发挥。这一比较填补了现有文献中的一个重要空白。

在结构化表示的探索方面，Besta et al. (2024) 的 Graph of Thoughts 将 LLM 的中间思想组织为图结构，使用外部控制器进行管理。Li et al. (2025) 的“LLMs Can Easily Learn to Reason from Demonstrations Structure”进一步强调了推理结构的重要性。LinTree 可以被视为这些思想在具体搜索场景中的一个精简实现：它不是构建一个完整的图或树的外部表示，而是在 LLM 的文本输出中嵌入结构标注，从而在不改变推理流程的情况下提升结构的可利用性。Wang et al. (2025) 的“Don't Get Lost in the Trees”则从反面呼应了 LinTree 的发现，指出过度搜索可能导致 LLM 推理陷入探索陷阱，这暗示了显式结构可能在帮助模型平衡探索与利用方面发挥作用。

展望未来，LinTree 开启了一个充满潜力的研究方向：结构化监督（structured supervision）。当前 LLM 的 SFT 和 RL 训练主要依赖于扁平的文本输出，但 LinTree 的实验表明，在训练数据中注入显式结构信息可以显著提升学习效率。这引出了几个开放问题：是否存在比 parent pointer 更丰富的结构标注（如标注分支类型、回溯原因、启发式估计值）？这些标注是否可以通过自动化方式从现有 traces 中提取或推断？在开放域任务中，如何定义和表示“结构”？例如，在数学推理中，结构可能是子目标之间的依赖图；在科学发现中，结构可能是假设-实验-证据的推理链。探索这些结构表示并将其整合到 LLM 的训练中，可能成为提升推理能力的一条高效路径。

另一个值得探索的方向是 结构化推理与强化学习的深度结合。LinTree 的 GRPO 优化在显式结构的基础上取得了显著进步，但奖励函数仍然相对简单（基于搜索长度）。更复杂的结构感知奖励——例如奖励探索多样性、惩罚循环、鼓励有信息量的分支——可能进一步提升性能。此外，在 RL 中显式利用树结构进行信用分配（credit assignment），例如将成功或失败归因于特定的分支决策，可能比当前的策略梯度方法更有效。

从个人反思的角度，LinTree 最引人深思的方面在于它揭示了 LLM 推理中一个深刻的信息论问题：语言作为推理媒介的表达效率。LLM 的推理能力受限于其将思想编码为文本序列的能力。当思想本身具有复杂的结构（如树、图、递归）时，扁平的文本序列是一种低效的编码方式。LinTree 的 parent pointer 本质上是一种压缩方案——它用更少的文本歧义来编码相同的树结构信息，从而减少了模型解码结构所需的计算。这让人联想到程序语言中括号、缩进和标签的作用：它们不是程序逻辑本身，但极大地提升了逻辑的可读性和可维护性。在 LLM 的语境中，我们或许需要发展一种“推理标注语言”（reasoning markup language），专门用于在 LLM 的文本输出中嵌入计算结构的元信息。LinTree 的 sid 和 parent_id 可以被视为这种语言的极简原型。

这一思路还引发了一个更哲学性的问题：LLM 的“理解”究竟意味着什么？在隐式 traces 中，模型似乎需要“理解”文本才能推断结构；在显式 traces 中，模型似乎可以“查询”结构而不必深度理解。这两种模式之间的差异，或许反映了人类认知中“直觉推理”与“形式化推理”的区别。当我们阅读一段松散叙述的探索过程时，我们需要直觉地把握其结构；当我们阅读一段带编号的树形序列时，我们可以更机械地追踪其关系。LinTree 的发现暗示，对于当前的 LLM 而言，形式化的结构查询可能比直觉的结构推断更可靠。这一观察对于设计面向 LLM 的人机交互界面——包括提示（prompting）范式——具有直接的启示：也许我们应该更积极地在提示中显式标注结构信息，而不是期待模型从自然语言中推断它。这一视角的转换，可能是从“自然语言提示工程”走向“结构化提示工程”的一个关键节点。

Topics: