acceptodds
Desk rejected at ICLR 2027

Dep-Search: Learning Dependency-Aware Reasoning Traces with Persistent Memory

Desk rejected at ICLR 2027, so left out of the paper lists and the map.

Abstract

The evolution of agentic systems has increasingly relied on reinforcement learning (RL) and persistent memory mechanisms to enable autonomous decision-making and long-term knowledge retention. Recent advances in agentic RL have demonstrated the potential for agents to learn complex behaviors through interaction with their environments, while persistent memory systems have shown promise in maintaining and reusing accumulated knowledge across multiple tasks. However, existing approaches often struggle with efficiently searching through vast action spaces and managing dependencies between learned behaviors and stored memories. In this work, we introduce Dep-Search, a dependency-aware search framework that integrates agentic RL with persistent memory to enable efficient exploration and knowledge reuse. Dep-Search employs a structured search strategy that explicitly models dependencies between actions and learned experiences, allowing agents to navigate complex state spaces more effectively. The framework leverages persistent memory to maintain and retrieve relevant experiences, while RL components learn to optimize search policies based on dependency relationships. By organizing search around dependency-aware structures, Dep-Search enables agents to accumulate and reuse knowledge across episodes, rather than treating each search instance independently. Experiments on multi-task learning and sequential decision-making benchmarks demonstrate that Dep-Search achieves improved sample efficiency and task performance compared to existing agentic RL methods. Further analyses reveal that the dependency-aware search mechanism leads to more interpretable agent behaviors and effective knowledge transfer through persistent memory. These results highlight the importance of combining structured search strategies with memory mechanisms in advancing the capabilities of agentic RL systems.

Primary area:
generative models
Keywords:
Dependent aware search, agentic search

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_enjEOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper tries to address dependency modeling in multi-hop questions, reuse of retrieved facts, and credit assignment for intermediate search actions. It maps these goals to a QDMR-style dependency graph, a control-token retrieval/memory loop, and a PQPO process-quality advantage. The experiments cover seven QA benchmarks with Qwen3.5-4B and Qwen3.5-9B, reaching average scores of 41.29 and 48.91. Ablations support memory and decomposition, but the three parallel problem lines leave the central research story unfocused.

Critical strengths
  1. The modules form an understandable process. QDMR-style decomposition, topological execution, post-retrieval memory writes, Conclusion compression, and later Memory reads form a complete within-trajectory loop.
  2. The evaluation is broad. Two model sizes, seven datasets, several search-RL baselines, component ablations, and PQPO sensitivity experiments provide a substantial engineering evaluation.
Critical weaknesses
  1. The research question is too broad and the solution lacks a clear priority. Dependency graphs, persistent memory, and PQPO could each support a separate paper, but the main text presents them as parallel contributions. It is therefore difficult to tell whether the real new problem is dependency modeling, memory reuse, or process-level RL.
  2. The central solution is not closed by the experiments, and no anonymous source link is provided. The memory is mainly a bounded recency buffer within a single question trajectory; cross-question persistence appears only as an optional initialization. PQR may also use later trajectory information, while the main results lack clear multi-seed variance and component-level attribution. The paper provides no anonymous source or run-repository link for independently checking training, retrieval, PQR, and baseline reproduction.
Questions for authors
  1. Can you add a true cross-question persistent-memory setting in which earlier questions write memory and later questions read it under no-retrieval or restricted-retrieval budgets, comparing long-term gains, error accumulation, and capacity eviction against clearing memory for every question? If not, should the title and contributions be changed to within-episode memory?
  2. Do q_dec, q_ret, and q_mem require the complete trajectory or final answer to compute? Please give an online definition that does not use future information, report annotation reliability, and compare against reward-only GRPO, fixed process rewards, and alternative weights.
  3. Can you report independent seeds, training data and steps, compute budgets, and per-dataset variance for all major methods, together with baseline-reproduction logs? Please also provide links to anonymous source code, training configurations, and reproduction logs.
Reviewer_GRewOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes Dep-Search, a search-based reasoning framework for multi-hop QA with explicit sub-question dependencies and a writable external memory. To split questions and manage the memory buffer, four control tokens are designed, including Decompose, Retrieve, Memory, and Conclusion. Then the authors propose Process-Quality Policy Optimization to augment GRPO’s trajectory-level advantage with a GAE-based token-level process-quality advantage. Experiments on seven benchmarks with Qwen3.5-4B and Qwen3.5-9B show that Dep-Search outperforms various baselines.

Critical strengths
  1. The paper identifies two real limitations of existing search-based reasoning frameworks. Including trajectory-level credit assignment and implicit sub-question dependencies.

  2. The proposed Dep-Search is easy to follow, and the writing is well-structured.

  3. The experimental evaluation is extensive on seven benchmarks.

Critical weaknesses
  1. One of the major problems is the inconsistent results. Fig. 2 (which reports the seven-dataset average) shows the 4B model reaching 47.2 at the default (α, λ_Q), but Table 2 reports 41.29. At the same time, Table 4 (9B on QDMR gets 44.8 for HotpotQA and gets 45.5 for 2WikiMHQA) does not match Table 2 (46.4 and 47.2).

  2. Some technique details are missing. In Eq. (9), how to compute each component’s process quality for the Process-Quality Reward is not clear.

  3. With token-level GAE (γλ_GAE=0.99*0.95≈0.94), credit reaches back only about 16 tokens. Therefore, token-level GAE may need a larger λ_GAE for longer trajectories.

Questions for authors
  1. How is each component of the process-quality vector in Eq. (9) computed? Do you use string matching or an LLM judge?

  2. Removing memory or decomposition hurts single-hop QA as much as multi-hop QA (Table 3). How does this fit the claim that the gains come from dependency modeling?

  3. Does t in Eqs. (13)-(17) index tokens or steps? If tokens, the GAE horizon under γλ_GAE≈0.94 is about 16 tokens.

  4. Why is C_mem set to 20? The paper reports this value but gives no justification and no sensitivity analysis, even though the memory ablation causes the largest drop in Table 3.

Reviewer_jwYCOpenReview ↗
Rating
2
Confidence
2
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

Dep-Search is a multi-hop QA framework with four control actions—decompose, retrieve, memory read, and conclusion-based summarization—that models dependent sub-questions and stores evidence/conclusions as reusable memory. PQPO combines the answer reward with process scores (decomposition, retrieval, memory reuse, efficiency) and mixes trajectory- and token-level advantages. Experiments cover seven QA datasets and two model scales, with baselines, ablations, decomposition comparison, and sensitivity analysis.

Critical strengths
  • Addresses real issues (dependencies, repeated retrieval, evidence reuse) with a coherent design.
  • Explicit actions make reasoning and memory use inspectable.
  • Broad evaluation; reported average gains over HierSearch are 2.24/2.97 points on the 4B/9B models, respectively.
Critical weaknesses
  • Novelty and independent contribution unclear: The distinction from prior work, including process-supervised GRPO, needs clarification. The paper should separate integration from algorithmic novelty and establish PQPO’s gains beyond the added process reward.

  • Definitions insufficient: As written, Eq. (14) uses the same expression as the advantage in Eq. (16) and appears to omit Vold(st)V_{\mathrm{old}}(s_t). Process scores have high-level definitions, but the operational criteria for question coverage, evidence reuse, and successful memory resolution are insufficiently specified.

  • Reliability and mechanism evidence incomplete: Fig. 2 conflicts with the 4B score in Table 2, and some case-study retrieval results contain information that postdates the stated Wikipedia 2018 corpus. Multi-seed variability is not reported. The component ablations and α sweep provide partial evidence, but do not fully disentangle the contributions of dependency structure, memory reuse, and optimization.

Questions for authors
  1. What is PQPO’s actual computation? Does Eq. (14) omit Vold(st)V_{\mathrm{old}}(s_t)? Give the reward/value/advantage flow consistent with the implementation and the operational criteria for question coverage, evidence reuse, and successful memory resolution.
  2. Please reconcile 47.2 in Fig. 2 with 41.29 in Table 2, and explain how 2023–2024 information appears in the case-study retrieval results under Wikipedia 2018. Identify any differing experimental settings or illustrative cases.
  3. How much of the gain comes from the process reward versus PQPO? Beyond the α sweep, compare PQPO with process-supervised GRPO and PPO under the same framework, data, answer/process rewards, and budget; report multi-seed mean and standard deviation, together with the number of seeds.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.