LinTree：利用显式结构化搜索历史改进LLM推理

大语言模型（LLM）常通过生成探索并修改部分解的中间轨迹来求解推理问题。从搜索视角看，这些轨迹可视为线性化的搜索树：模型扩展某个部分解，失败时将其放弃，并回溯尝试其他方案。与传统启发式引导的搜索相比，这类策略有一个潜在优势：它以整个搜索轨迹为条件，而非仅以当前局部状态为条件。我们首先通过将轨迹条件化的推理策略与配备仅观察当前局部状态的LLM启发式的最佳优先搜索进行比较，检验LLM是否利用了这一优势。在Blocks World、网格Navigation与Sokoban三个受控推理环境中，我们发现仅靠原始访问搜索历史并不足以稳定超越启发式搜索。随后我们研究一个可能的原因：在LLM推理轨迹中，底层搜索树只是被隐式表示，当模型回溯或切换分支时，轨迹并未显式指明正在重访哪个更早的搜索状态。我们证明，添加简单的父指针以显式表示线性化树（LinTree）结构，相对隐式推理模型与LLM启发式引导搜索，同时提升了任务性能与搜索效率。这些结果表明，当搜索历史的树结构被显式化时它才最有用，这为LLM推理中更具结构感知的表示提供了动机。