Dep-Search: Learning Dependency-Aware Reasoning Traces with Persistent Memory
Yanming Liu, Xinyue Peng, Zixuan Yan, Yanxin Shen, Wenjie Xu, Yuefeng Huang, Xinyi Wang, Jiannan Cao, Jianwei Yin, Xuhong Zhang · 2026
Read Dep-Search: Learning Dependency-Aware Reasoning Traces with Persistent Memory by Yanming Liu, Xinyue Peng, Zixuan Yan, Yanxin Shen, Wenjie Xu, Yuefeng Huang, Xinyi Wang, Jiannan Cao, Jianwei Yin, Xuhong Zhang (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-18771.txt.
Introduction
Yanming Liu and nine colleagues build Dep-Search, a way for language models to reason through hard asks with the help of search. Such models can call on out-side facts as they work, step by step. The field has grown past plain fetch-and-read plans, in which facts are pulled once and the reply is wrote at once. New plans search in rounds, with each round set by what the last round found.
Those rounds lean on each other: a late search rests on the facts and picks of the rounds ahead of it. If those links are lost, the chain can drift or loop. Dep-Search learns traces that keep the links in view as it goes. It also keeps a store that lasts across rounds, so past finds stay in hand. A chain that minds its own links should reach sounder ends.
Catalog record
| CREATOR | Yanming Liu, Xinyue Peng, Zixuan Yan, Yanxin Shen, Wenjie Xu, Yuefeng Huang, Xinyi Wang, Jiannan Cao, Jianwei Yin, Xuhong Zhang |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 83 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-18771
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Dep-Search: Learning Dependency-Aware Reasoning Traces with Persistent Memory Yanming Liu, Xinyue Peng, Zixuan Yan, Yanxin Shen, Wenjie Xu, Yuefeng Huang, Xinyi Wang, Jiannan Cao, Jianwei Yin, Xuhong Zhang Abstract Large Language Models (LLMs) have demonstrated remarkable capabilities in complex reasoning tasks, particularly when augmented with search mechanisms that enable systematic exploration of external knowledge bases. The field has evolved from traditional retrieval-augmented generation (RAG) frameworks to more sophisticated search-based frameworks that orchestrate multi-step reasoning through explicit search strategies. However, existing search frameworks still rely heavily on implicit natural language reasoning to determine search strategies and how to leverage retrieved information across reasoning steps. This reliance on implicit reasoning creates fundamental challenges for managing dependencies between sub-questions, efficiently reusing previously retrieved knowledge, and learning optimal search strategies through reinforcement learning. To address these limitations, we propose Dep-Search, a dependency-aware search framework that advances beyond existing search frameworks by integrating structured reasoning, retrieval, and persistent memory through GRPO. Dep-Search introduces explicit control mechanisms that enable the model to decompose questions with dependency relationships, retrieve information when needed, access previously stored knowledge from memory, and summarize long reasoning contexts into reusable memory entries. Through extensive experiments on seven diverse question answering datasets, we demonstrate that Dep-Search significantly enhances LLMs’ ability to tackle complex multi-hop reasoning tasks, achieving substantial improvements over strong baselines across different model scales. 1 Introduction Large Language Models (LLMs) have demonstrated remarkable capabilities in complex reasoning tasks, particularly when augmented with search mechanisms that enable systematic exploration of external knowledge bases [ 12 , 7 , 1 ] . The field has evolved from traditional retrieval-augmented generation (RAG) frameworks to more sophisticated search-based frameworks that orchestrate multi-step reasoning through explicit search strategies [ 14 ] . Recent work such as Search-R1 [ 8 ] , DeepResearcher [ 43 ] , Chain-of-Agents [ 13 ] , and Kimi-K2 [ 30 ] have shown that search frameworks can effectively decompose complex questions, retrieve relevant information from multiple sources, and synthesize answers through structured multi-step reasoning [ 33 ] . However, existing search frameworks still rely heavily on implicit natural language reasoning to determine search strategies and how to leverage retrieved information across reasoning steps [ 33 ] . This reliance on implicit reasoning creates fundamental challenges for managing dependencies between sub-questions, efficiently reusing previously retrieved knowledge, and learning optimal search strategies through reinforcement learning [ 44 ] . The fundamental problem lies in the lack of explicit dependency modeling and persistent memory management in current search frameworks. Existing approaches decompose questions into sub-questions but fail to explicitly model dependencies between these sub-questions, leading to inefficient search patterns where the same information may be retrieved multiple times or sub-questions are answered out of dependency order [ 15 ] . Moreover, existing systems treat each reasoning episode independently, discarding valuable knowledge extracted during search that could be reused across questions or even within the same multi-step reasoning process [ 38 ] . This knowledge loss is particularly problematic in complex scenarios where retrieved facts from early steps are needed in later dependent steps, forcing redundant searches and increasing computational costs [ 16 ] . Additionally, training search-based LLMs to learn optimal search strategies remains challenging, as existing reinforcement learning approaches struggle with the sparse reward signals and the need to jointly optimize decomposition, retrieval, memory access, and reasoning behaviors [ 2 ] . To address these limitations, we propose Dep-Search , a dependency aware search framework that advances beyond existing search frameworks by integrating structured reasoning, retrieval, and persistent memory through GRPO. Dep-Search introduces explicit control mechanisms that enable the model to decompose questions with dependency relationships, retrieve information when needed, access previously stored knowledge from memory, and summarize long reasoning contexts into reusable memory entries. By combining dependency aware question decomposition with a persistent memory system and GRPO for trajectory-level learning, Dep-Search ensures that reasoning follows explicit dependency structures, retrieved knowledge is efficiently stored and reused, and the policy learns to optimize the entire search-reasoning-memory pipeline jointly. Unlike existing search frameworks that rely on heuristic search strategies, Dep-Search treats all tokens uniformly in the policy, enabling end-to-end learning of when to decompose, what to retrieve, when to access memory, and how to synthesize final answers, while the explicit memory state provides verifiable knowledge accumulation throughout the reasoning process. Our Contributions. Our contributions are detailed as follows. • We present Dep-Search, a novel framework that formalizes multi-hop reasoning through dependency aware decomposition and explicit control tokens, providing structured reasoning traces and efficient knowledge reuse. • We introduce a persistent memory system that automatically stores summarized facts from searches and enables efficient memory access through embedding-based similarity search, addressing the knowledge loss problem in existing search frameworks. • We demonstrate that QDMR-based decomposition enables adaptive dependency modeling that significantly outperforms sequential decomposition approaches, allowing the model to determine both the number of reasoning steps and their dependency structure dynamically. 2 Related Work 2.1 Agentic Reinforcement Learning Recent advances in agentic reinforcement learning (RL) have explored how LLM-based agents can interact with environments, tools, and external knowledge sources to solve complex tasks through trial-and-error learning [ 24 , 23 , 9 ] . Early work focused on using RL to fine-tune language models on synthetic reasoning tasks or instruction-following benchmarks, typically with short-horizon rewards and limited interaction structure [ 18 , 26 ] . Recent frameworks introduce multi-step decision processes in which the agent can iteratively call tools, plan, and revise its strategy [ 13 , 30 ] . These systems demonstrate that explicit interaction loops and environment feedback can significantly improve the robustness and adaptability of LLMs on complex tasks such as web navigation, code generation, and multi-hop question answering [ 40 , 4 ] . A common theme across these approaches is the use of policy optimization balance exploration and exploitation, such as entropy-balanced objectives that encourage diverse exploration while maintaining exploitation of promising strategies [ 2 ] , and experience replay mechanisms that enable agents to learn from past trajectories more effectively [ 16 ] . The emphasis on trajectory-level learning, where agents learn to optimize sequences of actions rather than individual decisions, enabling better credit assignment and long-term planning in complex multi-step reasoning scenarios. 2.2 Agentic Memory A growing line of work studies how LLM agents can maintain and exploit persistent memory to improve long-term coherence, personalization, and knowledge reuse [ 19 , 37 , 21 ] . Early memory-augmented systems typically log past interactions or retrieved documents in a buffer and naively prepend them to the prompt, which quickly becomes inefficient and noisy as the context grows [ 41 , 3 ] . Subsequent approaches introduce memory retrieval modules based on dense embeddings, enabling agents to select relevant past experiences or facts conditioned on the current query [ 34 , 29 ] . Recent agentic memory frameworks go further by allowing agents to write structured summaries into memory, compressing long trajectories into reusable high-level knowledge that can be recalled [ 35 , 6 , 36 ] . A common evolution across these approaches is the shift from passive memory storage to active memory management, where agents not only retrieve but also strategically write and organize memory content to optimize knowledge reuse