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

研究者发现大语言模型（LLMs）在推理时虽能访问完整搜索历史，但隐式表示的搜索树结构限制了效率。通过引入简单父指针显式表示线性化树结构（LinTree），在Blocks World、Grid Navigation、Sokoban三个经典推理任务上显著提升了任务性能和搜索效率。

LLMs解决复杂推理问题时的轨迹可视为线性化搜索树，理论上能利用全局轨迹做决策，但实验显示仅让LLM访问搜索历史并不能可靠超越仅用局部状态的启发式搜索。核心问题在于推理轨迹中搜索树结构是隐式的，模型需自行推断当前步骤与历史的关系，增加认知负担。

LinTree方法的核心是添加简单父指针显式表示线性化树结构，为每个推理步骤标注其父节点（扩展来源）。此显式表示带来三个好处：清晰的层次结构、高效的状态复用、更好的回溯决策。

在三个测试环境中，LinTree表现显著优于隐式推理模型和LLM启发式引导搜索：任务性能上，Blocks World解决更多复杂实例、导航任务路径更高效、Sokoban策略优化度提升；搜索效率上，减少重复探索、降低回溯认知负担、推理步骤更简洁。

理论意义：LLM推理能力依赖输入信息的结构化表示，呼应认知科学中人类用结构化表征解决问题的研究。方法论启示：1. 不假设更多上下文自动更好；2. 显式结构优于隐式推断；3. 借鉴经典AI结构化表示思想。

局限：限于简单受控环境、父指针需额外实现、开放域有效性待验证。未来方向：探索更丰富结构标注（兄弟节点、子树摘要）、自动学习最优结构表示、应用于更复杂实际任务。