如果你在做LLM推理或搜索增强的AI系统，这篇论文指出了隐式搜索历史的瓶颈，并提供了一个简单有效的改进方向——显式父指针。做推理模型或规划算法的开发者值得一看。
该论文研究了大型语言模型（LLM）在推理过程中如何利用搜索历史。作者发现，LLM通常将搜索树线性化为中间轨迹，但仅凭隐式表示的历史不足以超越传统启发式搜索。通过引入显式的父指针（LinTree结构），模型能更清晰地回溯和切换分支，从而在Blocks World、网格导航和Sokoban等任务中显著提升性能和搜索效率。这表明，显式化搜索树的树结构能更好地发挥历史信息的优势，为LLM推理提供更结构化的表示方法。
LinTree: Improving LLM Reasoning with Explicitly Structured Search Histories
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.