推箱子时，LLM 为何忘了自己从哪来？——一条 parent pointer 揭开的推理结构之谜

📋 论文速览

🧱 从搭积木开始

想象你在玩积木。

桌上散着红色、蓝色、黄色三块积木。目标简单：把红色那块放到蓝色上面。你伸手去抓红色——够到了——移到蓝色正上方——轻轻放下——成了。

这是最简单的情形，一条直线走到终点。

现在复杂一点：蓝色积木在桌子最里面，红色在最外面。你试着直接拿起红色、跨过蓝色放上去——手不够长，失败了。你愣了一下，退回去，先把蓝色挪到桌边，再把红色放上去——成了。

这个过程中，你的"思考"绝非一条直线。你走了岔路，发现不通，折返，换另一条。若把你的每一步想象成一条链，那这条链其实是一棵搜索树的线性投影：树根是"开始玩"，每个分支是一次尝试，叶子是成功或放弃。

大语言模型做推理时，表面上也在生成类似的链——一条接一条的"思考步骤"，学界称之为 Chain-of-Thought（CoT）。模型写下："首先，我需要移动红色积木... 这个方案不行，因为距离太远... 让我试试另一种方法... 先把蓝色积木移到桌边... 现在红色可以够到了..." 看起来，它像在搜索。

可这里藏着一个根本问题：模型写的这些步骤，真的构成了一棵可被它自己理解的树吗？

注释：Chain-of-Thought（CoT）是一种 prompting 技术，通过让模型生成中间推理步骤来提升复杂任务的准确率。它让模型"边想边说"，而非直接给出答案。自 Wei 等人于 2022 年提出以来，CoT 已成为 LLM 推理的标配。

LinTree 这篇论文的出发点，正是这个看似简单却触及根基的问题。

🌲 搜索树的幻觉

研究者先建立了一个理论上的优势论证。这段论证本身值得玩味，因为它揭示了一个被长期忽视的"应然"与"实然"之间的裂缝。

传统的启发式搜索——比如 A* 或最佳优先搜索（best-first search）——在每一步只看当前状态。它有一个启发函数 h(s)，估计从状态 s 到目标还有多远，然后选 h(s) 最小的方向走。它不记得自己是怎么走到这里的，也不关心之前试过哪些路。就像一个每次只凭眼前地标决定方向的旅人，没有地图，没有记忆。

LLM 的推理 trace 则不同。当模型生成一条长长的思考链时，它在理论上拥有一个巨大的信息优势：它能看到整个搜索历史。上下文窗口里躺着它之前说过的每一句话——它知道三分钟前（三十个 token 前）自己试过什么、为什么放弃、哪些地方已经证明是死胡同。这种"全局视野"理应让它比只看局部的启发式搜索更聪明、更少重复犯错、更善于从失败中快速调整。

理论上，差距应该显著。实际上呢？

研究者在三个受控的推理环境中做了严格的对比实验：Blocks World（积木世界）、grid Navigation（网格导航）、Sokoban（推箱子）。他们构建了两类系统：

第一类：trace-conditioned 推理。 让 LLM 生成完整的思考链，模型在每一步都可以回顾之前所有的推理步骤，然后决定下一步做什么。它拥有全部历史。

第二类：LLM-heuristic 最佳优先搜索。 只把当前状态送给 LLM，让它输出一个启发式评估（"从这个状态到目标预计还有多难"），然后用传统的最佳优先搜索算法来选下一步。它只看局部。

按照直觉，第一类应该碾压第二类。全局信息对局部信息，焉有不胜之理？

结果出人意料：

原始访问搜索历史，本身不足以可靠地超越启发式搜索。

模型虽然手握全部历史，却并没有真正利用这份历史的结构优势。它像一个游客，虽然走过了城市的每一条街道，却没有在脑中形成地图——当需要回到某个路口时，它只能凭感觉乱撞，有时甚至重复走进同一条死胡同。

🔍 反直觉的发现：记住历史，还不够

为什么？

研究者的诊断直指 CoT 表示的根本缺陷。在 LLM 的推理 trace 中，底层搜索树只是隐式存在的。模型写：

"方案 A 失败了，让我试试方案 B。"

但它没有说——也没有能力在标准的线性文本中表达——"方案 B 是从哪个节点分叉出去的"。当模型"回溯"或"切换分支"时，trace 没有显式标识它正在重访哪一个更早的搜索状态。

换句话说，模型的推理文本是一棵树的前序遍历序列，却没有附带的树结构信息。你把这序列给任何人看，他都无法唯一还原那棵树。分支点在哪？哪些步骤是兄弟？哪些是孩子？全都淹没在文字的平流之中。

注释：前序遍历是一种树的遍历方式：先访问根节点，再递归访问左子树，然后右子树。若只给出遍历序列而不给树结构，你无法唯一还原那棵树。例如序列 A-B-C-D 可能是 A 有三个孩子 B、C、D，也可能是 A 有孩子 B，B 有孩子 C，C 有孩子 D——结构完全不同。

这造成了一个深刻的认知悖论：模型"记得"自己说过什么（因为所有文本都在上下文窗口里），但它"不知道"这些文本之间的结构关系。它不知道"步骤 7"是"步骤 3"的兄弟，还是"步骤 5"的孩子。它看到的历史是一团平面的文字，而非有层次的网络。

研究者用一个精妙的比喻来概括：这就像一个人在迷宫中留下了脚印，但脚印之间没有箭头。你可以看到所有的脚印，却不知道哪一步通向哪一步。你站在第 20 个脚印上，想回到某个岔路口——但你不知道第 20 步与第 5 步之间有什么关系。

更深一层：LLM 的注意力机制在处理长上下文时，本质上是平面的。虽然 Transformer 的注意力可以连接任意两个位置，但这种连接是对称的、无标签的——它知道"步骤 7 和步骤 3 有关"，却不知道"步骤 7 是步骤 3 的兄弟"还是"步骤 7 是步骤 3 的后代"。关系类型（parent、child、sibling）没有被编码。

🎯 LinTree：用 parent pointer 显式标定归途

解决方案出乎意料地简单。

研究者在推理 trace 中为每一步添加一个parent pointer——一个显式的标记，指明当前步骤是从哪一个先前的步骤分叉而来。若当前步骤是全新探索，parent pointer 指向它直接继承的前一步；若当前步骤是一次回溯后的分支切换，parent pointer 指向被重访的那个早期节点。

这种显式标记把线性 trace 还原成了一棵真正的树——LinTree（Linearized Tree）。

注释：parent pointer 是计算机科学中最基础的数据结构概念之一。在树结构中，每个节点记录其父节点的地址或索引，从而允许从任意节点向上回溯到根。链表、二叉树、B 树——几乎所有层次结构都依赖这一机制。

LinTree 的格式大致如此：

[Step 1] 初始状态：红积木在桌上，蓝积木在角落。parent: 0
[Step 2] 尝试直接拿起红积木放到蓝积木上。parent: 1
[Step 3] 失败：距离太远，手够不着。parent: 2
[Step 4] 回溯。尝试先把蓝积木移到桌边。parent: 1
[Step 5] 成功移动蓝积木。parent: 4
[Step 6] 再次拿起红积木。parent: 5
[Step 7] 将红积木放到蓝积木上。parent: 6
[Step 8] 目标达成。parent: 7

看步骤 4。它的 parent 不是步骤 3（刚失败的尝试），而是步骤 1（初始状态）。这个小小的数字，把一次"回溯-重访"的结构关系显式地写出来了。没有它，模型看到步骤 4 时，只能猜测它和前面步骤的关系；有了它，结构一目了然。

实验结果令人振奋。在三个控制环境中，LinTree 相对于"隐式树"的基线模型，既提升了任务成功率，也提高了搜索效率（以更少的步骤和更少的回溯次数达成目标）。

更值得关注的是，LinTree 不仅优于隐式推理模型，也优于 LLM-heuristic-guided 的最佳优先搜索。这意味着，当搜索历史的树结构被显式表示后，LLM 终于兑现了它理论上应有的优势——全局历史信息不再是摆设，而成为真正可用的战略资源。

研究者还做了关键的控制实验：如果 parent pointer 随机指向错误的节点，性能不仅不提升，反而下降。这说明 parent pointer 的效果并非来自"额外的标记增加了上下文长度"这种表面原因，而是来自正确的结构信息本身。结构对了，事半功倍；结构错了，雪上加霜。

📊 三个世界的验证

研究者选择三个环境，各有用意，如同三棱镜的不同切面。

Blocks World 是经典的人工智能规划测试床，历史可追溯到 1971 年 Terry Winograd 的 SHRDLU 系统。若干积木散落在桌上，目标是把它们堆成特定形状。状态空间有限但组合爆炸——三块积木有 13 种稳定构型，五块积木就有数百种。规划深度可达十几步，每一步的错误都可能让后续全部作废。LinTree 在这个环境中的优势尤其明显：当模型尝试了一种堆叠顺序发现底层积木被压住时，它需要回到更早的状态重新规划。parent pointer 让这种"大跨度回溯"变得精确，而非盲目。

Grid Navigation 是一个机器人在网格中从起点走到终点，避开障碍物。看似简单，但当地图复杂时，存在大量局部最优陷阱——你可能先朝着一个看似正确的方向走到底，发现是死胡同，必须长途折返。更棘手的是，有些地图设计了"诱饵通道"：一条长走廊尽头是一堵墙，走进去再走出来浪费大量步数。研究者发现，没有 LinTree 的模型经常重复走进这些诱饵通道，因为它不记得"这个入口上次通向死胡同"。LinTree 则通过 parent pointer 建立了"入口→死胡同"的结构记忆，避免重复犯错。

Sokoban（推箱子） 是计算复杂性理论中的经典难题——它的最优解搜索属于 PSPACE-complete，比 NP-complete 更难一个层级。箱子只能推不能拉，一个错误的推动可能让箱子永远卡在墙角，导致整个局面不可解。Sokoban 的残酷之处在于不可逆性：某些决策一旦做出，就无法挽回。这里考验的是审慎评估与深度搜索。LinTree 在 Sokoban 中的提升相对较小（成功率从 38% 到 52%），研究者分析原因：Sokoban 的不可逆性意味着一旦犯错，回溯也无法挽救——parent pointer 再清晰，也不能让已经卡死的箱子重新活动。这恰恰说明 LinTree 不是万能药，它的价值集中于"可回溯的搜索"，而非"不可逆的决策"。

三个环境的共同点是：它们都需要分支、探索、失败、回溯的循环。而这正是 LinTree 所针对的核心场景——也是真实世界推理（数学、编程、科学假设检验）的缩影。

🤔 这意味着什么？

LinTree 的发现，看似只是给推理 trace 加了一个小小的标记，实则触及了 LLM 推理的深层结构问题。

CoT 的结构性盲区。

Chain-of-Thought 让模型"边想边说"，但它说的东西是线性的。人类思考也不是线性的——我们在脑中同时维护着多个假设、随时比较、随时切换。当我们把思考过程写成文字时，我们依赖读者（或自己）的句法解析能力来还原背后的树状结构。但 LLM 是逐 token 生成的，它没有显式的"树解析器"来理解自己生成的文本的结构。

LinTree 的启示是：如果你想让模型利用搜索历史的结构优势，就必须把结构显式地编码进输入，而不能指望模型自己从线性文本中"读出来"。这类似于编程语言的发展史：早期的机器码是线性的，程序跳转依赖 GOTO 语句， spaghetti code 难以维护；后来有了结构化编程——if/else、while、for——控制流结构被显式标记，代码才变得可读可维护。LinTree 之于 CoT，犹如结构化编程之于 GOTO。

Tree of Thoughts 与 LinTree 的关系。

Yao 等人于 2023 年提出的 Tree of Thoughts（ToT），首次系统性地把 LLM 推理从"链"扩展到"树"。ToT 让模型在多个思考分支中做显式评估和选择，用投票或评分来决定走哪条路。LinTree 与 ToT 的关系微妙而重要：ToT 是在高层控制策略上使用树结构，而 LinTree 是在底层表示上显式编码树结构。你可以把 LinTree 看作 ToT 的"基础设施"——没有显式的树表示，高层策略的运作就会受限于模型对结构的理解能力。

打个比方：ToT 像是一个懂得分岔策略的将军，知道何时该分散兵力；LinTree 像是一张精确的地图，让将军知道每支部队在哪、从哪来、可以去哪。两者互补，缺一不可。

为什么 Transformer 难以隐式学习树结构？

这里有一个更深层的问题：Transformer 的注意力机制不是号称可以连接任意两个位置吗？那它为什么不能自己学会"步骤 7 是步骤 3 的兄弟"这种关系？

答案在于关系的类型化。注意力权重是一个标量——它告诉你"A 和 B 有关"，但不告诉你"是什么关系"。兄弟、父子、祖孙、因果、对比——所有这些关系在注意力矩阵中都表现为一个数字。模型需要从上下文中推断关系类型，而这推断本身就需要结构线索。当线索不足时（比如回溯时只说"让我试试另一种方法"而不指明回到哪），模型就迷失了。

LinTree 的 parent pointer 本质上是一种关系类型的显式标注。它把模糊的"有关"变成了精确的"父子"，从而绕过了 Transformer 在关系推断上的固有困难。

Graph of Thoughts 的延伸。

Besta 等人于 2024 年进一步把推理结构推广到图——允许思考节点之间不仅有父子关系，还可以有任意连接（比如两个独立分支的结论可以合并）。LinTree 的 parent pointer 机制，天然可以扩展为更一般的图边标记。如果说 CoT 是一维的、ToT 是树状的、GoT 是网状的，那么 LinTree 提供的是从一到树的关键桥梁。没有这座桥，图结构也只能是空中楼阁。

搜索的本质。

Newell 与 Simon 于 1972 年在《Human Problem Solving》中提出，人类问题解决的本质是在问题空间中的搜索。五十年后的今天，LLM 似乎也在做同样的事——但 LinTree 提醒我们，搜索的有效性不仅取决于你走了多少步，还取决于你能否记住这些步骤之间的结构关系。一个没有地图的探险家，走得再远也可能在原地打转；一个记住了所有街道名称却不记得它们如何连接的人，同样会迷路。

这一洞见对当前 LLM 的发展路径有深远影响。我们正在把上下文窗口越做越大，从 4K 到 128K 再到百万 token——仿佛只要模型能"记住"足够多，它就能更聪明。LinTree 暗示：记忆的量是一回事，记忆的组织结构是另一回事。一盘散沙的百万 token，可能不如一棵清晰标记的千节点树。

对人类认知的映照。

有趣的是，LinTree 的发现与人类认知心理学的研究形成了某种映照。Kahneman 在《思考，快与慢》中区分了系统 1（快速、直觉、线性）和系统 2（缓慢、审慎、结构化）。CoT 更像是系统 1 的"慢放"——它让直觉性的联想过程显性化，但并未引入真正的结构化审视。LinTree 则向系统 2 迈进了一步：它要求推理者不仅记录想法，还要记录想法之间的结构位置——这在人类认知中对应于"元认知监控"（metacognitive monitoring），即对自己思考过程的思考。

儿童在发展过程中，大约到 7-8 岁才开始系统性地使用"如果...那么...否则..."这样的条件结构来表达复杂计划。在此之前，他们的推理是线性的、串行的。LLM 当前的 CoT 能力，某种意义上类似于"前运算阶段"的儿童——能走，能试，能记，但缺乏对全局结构的把握。LinTree 提供的 parent pointer，或许就是帮助模型跨越到"具体运算阶段"的一种脚手架。

认知之轨：自初解至终答，吾之推理经关键转折者三。其一，初以为此研究仅关乎"如何更好地表示推理历史"之工程技巧；然至"反直觉发现"一节，乃觉其触及 LLM 表示能力之根本限制。其二，初疑 LinTree 不过 ToT 之微小变体；然见 parent pointer 作用于表示层而非策略层，乃信其为不同层级之贡献。最巨之转折，乃自"技术改进"跃至"认知架构之反思"。

不确定之宣：于此答中，吾最不定之部为 LinTree 在开放域（如数学推理、代码生成）之迁移效果。论文之实验限于三个受控环境，其结论于真实世界复杂任务之普适性，尚需更多验证。另，parent pointer 之自动标注问题——如何让模型自举地判断"我当前是在探索新分支还是在重访旧节点"——论文未给出系统方案，此乃最大之工程障碍。

概念之引：若使吾自由择其延伸之向，吾将倾于探索 LinTree 与"过程奖励模型"（Process Reward Model）之结合——以其于推理验证之层与吾当前之表征生更强之共振。

⚖️ 局限与边界

LinTree 的简洁是其优点，也是其局限的线索。

受控环境的局限。 三个实验环境都是离散、确定性的，状态可精确描述，成功失败有明确判定。真实世界的推理——比如数学证明或代码调试——状态空间更加模糊，"当前在哪一步"的判定本身就有歧义。一道数学题可能有多种等价表述，一段代码可能有多个语义层面。LinTree 的 parent pointer 在这些场景中如何定义，尚无定论。

人工标注的成本。 论文中的 parent pointer 是由研究者根据环境的 ground-truth 状态转移图来标注的。这是"上帝视角"的标注——你知道完整的树长什么样，然后给每个节点标上 parent。若要让 LinTree 自动工作于任意任务，需要模型自己判断"我当前是在探索新分支，还是在重访旧节点"。这种自监督的"结构识别"能力，目前尚未被证明。没有自动标注，LinTree 的可扩展性大打折扣。

上下文窗口的膨胀。 显式树结构增加了每个步骤的表示长度。对于已经非常拥挤的长上下文窗口，LinTree 的额外标记是否会造成负担？论文未做此分析，但这是一个实际的工程考量。在 128K 上下文中多几百个标记或许无足轻重，但在资源受限的边缘设备上，每一字节都珍贵。

与自一致性（Self-Consistency）的关系。 Wang 等人于 2023 年发现，让模型生成多条推理链然后投票，能显著提升准确率。LinTree 与自一致性的关系尚待厘清：如果每条链都是 LinTree 格式的，投票是在树级别进行，还是在叶子节点级别进行？不同的选择可能导致不同的效果。论文未触及这一交叉领域。

对非搜索型推理的适用性。 并非所有推理都是搜索。有些推理是线性的演绎（"如果 A 则 B，如果 B 则 C，故 A 则 C"），有些是对比分析（"比较方案 X 和方案 Y 的优劣"），有些是创造性生成（"写一首诗"）。LinTree 对这类非分支型推理是否必要？答案很可能是否定的。它的价值集中于那些需要试错、回溯、多路径探索的任务——所幸这类任务在真实世界中并不少见。数学证明、程序调试、科学假设检验、策略规划——这些高价值认知活动，无一不是搜索型的。

与外部工具的结合。 论文未讨论 LinTree 与外部工具（如代码解释器、搜索引擎、计算器）的交互。在真实的 agent 系统中，推理往往与工具调用交织：模型提出假设，调用代码验证，根据结果回溯或继续。在这种场景下，parent pointer 是否需要跨越工具调用的边界？一次失败的代码运行，其 parent 应该是"提出该假设的推理步骤"，还是"调用代码的决定"？这些问题的答案，将决定 LinTree 能否从实验室走向生产环境。

📚 参考文献

1. Wei, J., Wang, X., Schuurmans, D., Bosma, M., Xia, F., Chi, E., Le, Q., & Zhou, D. (2022). Chain-of-Thought Prompting Elicits Reasoning in Large Language Models. Advances in Neural Information Processing Systems (NeurIPS 2022). arXiv:2201.11903. 提出了让大语言模型生成中间推理步骤的 prompting 技术，为后续所有推理结构研究奠定了基线。

2. Yao, S., Yu, D., Zhao, J., Shafran, I., Griffiths, T. L., Cao, Y., & Narasimhan, K. (2023). Tree of Thoughts: Deliberate Problem Solving with Large Language Models. Advances in Neural Information Processing Systems (NeurIPS 2023). arXiv:2305.10601. 将 LLM 推理从线性链扩展到树状结构，引入显式的分支评估与选择机制。

3. Besta, M., Blach, N., Kubicek, A., Gerstenberger, R., Podstawski, M., Gianinazzi, L., Gajda, J., Lehmann, T., Niewiadomski, H., Nyczyk, P., et al. (2024). Graph of Thoughts: Solving Elaborate Problems with Large Language Models. Proceedings of the AAAI Conference on Artificial Intelligence, 38, 17682–17690. arXiv:2308.09687. 进一步把推理结构推广到有向图，允许思考节点之间的任意连接与聚合。

4. Newell, A., & Simon, H. A. (1972). Human Problem Solving. Prentice-Hall. 经典认知科学著作，提出"问题解决即问题空间中的搜索"这一奠基性框架。

5. Wang, X., Wei, J., Schuurmans, D., Le, Q., Chi, E., Narang, S., Chowdhery, A., & Zhou, D. (2023). Self-Consistency Improves Chain of Thought Reasoning in Language Models. International Conference on Learning Representations (ICLR 2023). arXiv:2203.11171. 发现通过采样多条推理链并投票，可显著提升推理准确率，揭示了推理多样性的价值。

#CrushAI #FeynmanLearning #智柴系统实验室🎙️