大型语言模型 (LLMs) 通常通过生成探索和修改部分解决方案的中间轨迹来解决推理问题。从搜索角度来看,，这些跟踪可以被视为线性化搜索树,，其中模型扩展了部分解决方案,，当失败, 时放弃它, 并回溯以尝试替代方案。与传统的启发式引导搜索,相比，这种策略具有潜在优势:，它以整个搜索轨迹为条件，而不仅仅是当前的局部状态。我们首先通过将跟踪条件推理策略与配备仅观察当前本地状态的 LLM 启发式的最佳优先搜索进行比较来测试 LLM 是否利用了这一优势。在三个受控推理环境, Blocks World, grid Navigation, 和 Sokoban, 中，我们发现仅对搜索历史记录的原始访问不足以可靠地超越启发式搜索。然后，我们研究一个可能的原因: 在 LLM 推理跟踪, 中，底层搜索树仅隐式表示,，并且当模型回溯或切换分支, 时，跟踪不会明确识别正在重新访问哪个较早的搜索状态。我们表明，相对于隐式推理模型和 LLM 启发式引导搜索，添加简单的父指针来显式表示线性化树 (LinTree) 结构可以提高任务性能和搜索效率。这些结果表明，当搜索历史的树结构变得明确时，它就会变得最有用,，从而为 LLM 推理激发更多的结构感知表示。
Large language models (LLMs) often solve reasoning problems by generating intermediate traces that explore and revise partial solutions. From a search perspective, these traces can be viewed as linearized search trees, where the model extends a partial solution, abandons it when it fails, and backtracks to try alternatives. Compared with traditional heuristic-guided search, such a policy has a potential advantage: it conditions on the whole search trace rather than only on the current local state. We first test whether LLMs utilize this advantage by comparing trace-conditioned reasoning policies against best-first search equipped with an LLM heuristic that only observes the current local state. Across three controlled reasoning environments, Blocks World, grid Navigation, and Sokoban, we find that raw access to search history alone is not enough to reliably outperform heuristic search. We then study one possible reason: in LLM reasoning traces, the underlying search tree is only implicitly represented, and when the model backtracks or switches branches, the trace does not explicitly identify which earlier search state is being revisited. We show that adding simple parent pointers to explicitly represent the linearized tree (LinTree) structure improves both task performance and search efficiency relative to implicit reasoning models and LLM-heuristic-guided search. These results suggest that search history becomes most useful when its tree structure is made explicit, motivating more structure-aware representations for LLM reasoning.
科目:人工智能(cs.AI)
Subjects: Artificial Intelligence (cs.AI)