- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This paper investigates how search agents can organize intermediate information during the search process and effectively distribute the reward for the final answer across the various steps taken. The authors propose TDS, a framework consisting of two components: a table-driven search structure that stores subproblems, parent nodes, subproblem answers, and evidence summaries; and an asymmetric credit-gating mechanism that determines how credit is assigned along a search trajectory by generating intermediate answers to the original problem based on the current table. Experiments were conducted using two different models across a variety of single-hop and multi-hop datasets.
Critical strengths
- The research problem is significant; the issue of credit assignment in multi-turn search has long been a topic of great research value within the context of search agents.
- The methodology is presented in a clear and easy-to-understand manner, and the design of the asymmetric credit gating system is reasonably sound.
Critical weaknesses
- The most central issue is the boundary of credit assignment. The authors make a strong assumption that when the model can answer correctly based on the intermediate materials, the preceding sequence is considered sufficient to answer the question. However, there may be the following cases: 1) The model may happen to infer the correct answer from its parametric memory, especially since the test sets are common Wikipedia-based datasets (e.g., HotpotQA and 2Wiki). This does not mean that the previous materials are sufficient. 2) The model's own answering ability may be limited or its responses may fluctuate, causing it to produce a wrong answer even when the materials are actually sufficient. Since the method generates an intermediate answer based on the intermediate materials, this extra step may also introduce or accumulate errors. 3) The paper uses EM as the metric. This metric only checks whether the predicted answer exactly matches the reference answer, and cannot determine whether the answer is semantically correct, which further increases the possibility of error accumulation.
- The innovation of this method appears limited, as tree-based search structures have already been explored in previous research. Furthermore, the use of intermediate answers / search materials and EM to determine search boundaries has also been addressed in some existing literature. The authors should better clarify the novelty of the proposed method.
Questions for authors
See Weaknesses.
6 comments
Q1 (2/2)
(b) Answering ability and output variability. Table R3 compares the TDS boundary with the ds4.1f boundary. For most trajectories with a passing check, they coincide or differ by one round. A failed interim check does not by itself trigger gating. When no interim check passes, Eq. (7) reduces to ungated advantage allocation. Greedy decoding makes interim checking deterministic for a given table. Table R4 applies the ds4.1f criterion uniformly to all methods, including baselines without interim checks. Among trajectories with incorrect final answers, TDS has the smallest proportion in which the ds4.1f boundary was reached.
Table R3. TDS boundary versus ds4.1f boundary (%)
| Trajectory group | Share within outcome | Same round or both absent | 1-round gap | ≥2-round gap | TDS boundary only | ds4.1f boundary only |
|---|---|---|---|---|---|---|
| Correct, passed | 88.9 | 81.4 | 7.0 | 1.7 | 9.9 | — |
| Correct, not passed | 11.1 | 29.1 | — | — | — | 70.9 |
| Incorrect, passed | 15.3 | 62.2 | 8.9 | 2.4 | 26.6 | — |
| Incorrect, not passed | 84.7 | 84.8 | — | — | — | 15.2 |
Table R4. Existence of a ds4.1f boundary before finalization (%)
| Final outcome | ds4.1f boundary | Tree-GRPO | MemSearcher | TDS | TDS w/o Gate |
|---|---|---|---|---|---|
| Correct | Exists | 88.8 | 83.9 | 88.0 | 87.6 |
| Correct | Absent (deduction A) | 11.2 | 16.1 | 12.0 | 12.4 |
| Incorrect | Exists | 28.8 | 26.4 | 24.1 | 27.6 |
| Incorrect | Absent | 71.2 | 73.6 | 75.9 | 72.4 |
(c) Additional step and error accumulation. As described in Section 3.3, the planner generates an interim answer from the current table and continues searching without adding that answer to it. Gating retains or zeros the outcome advantage assigned to each step. Among trajectories with a passing check but an incorrect final answer, Table R2 shows that 52.2% contain critical errors after the boundary, without critical errors before it. Failure-side gating protects these prefixes from negative credit.
(d) EM evaluation. A semantically correct interim answer can fail an exact-match check, delaying or preventing the TDS boundary. If no interim check passes, the trajectory receives ungated credit assignment. We reassessed the seven-benchmark results under the same evidence and reasoning criteria. Among originally EM-correct trajectories, deduction A identifies answers produced without ever reaching sufficient evidence, while deduction B identifies additional answers relying on uncorrected critical reasoning errors. Among originally EM-incorrect trajectories, we first exclude cases that fail the same evidence or reasoning criteria, then restore semantically correct answers missed by exact matching as C.
Table R5a. Conditional rates of deductions and restorations (%).
| Method | A: Insufficient evidence | B: Critical errors | C: Semantic EM misses |
|---|---|---|---|
| TDS | 12.0 | 2.4 | 14.7 |
| TDS w/o Gate | 12.4 | 2.8 | 14.4 |
| Tree-GRPO | 11.2 | 3.6 | 14.5 |
| MemSearcher | 16.1 | 4.0 | 15.2 |
Table R5b. Reassessed seven-benchmark macro-average EM (%).
| Method | Original EM | After A and B | Adjusted EM (after C) |
|---|---|---|---|
| TDS | 40.2 | 34.4 | 43.2 |
| TDS w/o Gate | 38.0 | 32.3 | 41.2 |
| Tree-GRPO | 38.0 | 32.4 | 41.5 |
| MemSearcher | 37.2 | 29.7 | 39.3 |
Based on unrounded values, TDS's advantage over its ungated variant changes from 2.17 to 2.05 EM points after reassessment.
Q2 (1/2)
Thank you for pointing out that the novelty of our work was not presented clearly enough. In the paper, the motivation underlying our contributions is spread across the individual design choices. We clarify the common idea behind them here.
Our premise is that the ability to understand and use task structure is essential for small models to organize multi-step actions and make progress on complex agentic tasks. Search presents a particular challenge. As evidence accumulates, relationships among subproblems become clearer, while each result changes what still needs to be resolved. Task structure must therefore develop as search proceeds, rather than be fully specified at the outset. Yet enabling small models to construct and exploit such structures remains difficult. As noted by the authors of ToR and ProbTree, their methods depend heavily on the reasoning abilities of larger models and are much less effective with smaller ones. How to train small models to acquire this capability in search remains largely unexplored.
The central insight of TDS is a shift in perspective: the policy should construct the task structure, and the ability to do so can be learned. Both design choices in TDS follow from this insight. Tree structures and interim answers have appeared in prior work, but sharing these components does not mean addressing the same problem. Grouping TDS with those methods solely because these components already exist overlooks the essential differences: learning to construct task structure and using it to assign credit in accordance with the final objective.
1. Tree-structured Search
A common blind spot of earlier tree-based methods is that task-structure construction remains outside the learned policy. This takes three forms.
- Sampling-defined structure. In Tree-GRPO, each node is a complete interaction step, and branches represent alternative continuations sampled from the same history (Sec. 2). The tree is produced by resampling during training to organize comparisons. The policy never decides where to branch.
- Procedure-defined structure. ToR expands its tree through prompting and prunes it with fixed rules at inference time, without training. Its quality depends on the model's existing reasoning ability as well as the prompts and rules.
- Predefined decomposition. ProbTree and RT-RAG decompose a question through prompting before solving it, then follow that decomposition. ProbTree keeps the structure fixed during execution, while RT-RAG only adjusts it according to predefined rules.
All these methods use trees, but none trains the policy itself to construct the task tree (Table R13).
Table R13. Sources and uses of tree structure
| Method | How structure is built | Information available to policy | Is construction learned? |
|---|---|---|---|
| Tree-GRPO | Resampling during training | Its own path | No |
| ToR | Prompted expansion and rule-based pruning at inference | Its own path | No |
| ProbTree, RT-RAG | Prompted decomposition before solving | Its subtree | No |
| TDS | Built incrementally by the policy | Full table | Yes |
We place task-structure construction under the policy's control. At each round, the TDS planner reads the full table and decides which node to extend, which subproblems to propose, and when to finalize. These decisions are optimized through training, and the table serves as the shared interface for training and inference (Sec. 3.2). The structure guides subsequent search decisions, while learning shapes how it grows. Constructing the task structure thus becomes part of the learned search capability. The ablations in Table 2 support this design. Replacing the table with chronological text substantially lowers average EM, while removing parent links also degrades multi-hop performance.
Q1 (1/2)
Thank you for carefully examining our credit-assignment boundary. Your central question is whether the first passing interim check reliably identifies when the retrieved evidence becomes sufficient to answer the original question. You raise four concerns. (a) The model may answer from parametric memory, especially on Wikipedia-based datasets such as HotpotQA and 2Wiki. (b) Limited answering ability and output variability may lead to incorrect answers despite sufficient evidence. (c) Generating interim answers may introduce and accumulate errors. (d) Exact match (EM) may miss semantically correct answers and amplify these problems.
In the 3B setting, we used ds4.1f to analyze trajectories for all 51,713 test questions across seven benchmarks to address these questions. Our main findings are as follows.
(a) Parametric memory. The original Instruct model, two baselines, and the TDS planner all achieve around 13% no-retrieval accuracy, with little change after training. During training, an interim check only determines how the outcome advantage is allocated across
expandsteps. Its answer is not reused byfinalize. TDS also leads on MuSiQue and Bamboogle, where no-retrieval accuracy is around 2%.(b) Answering ability and output variability. Among trajectories with a correct final answer and a passing check, the TDS and ds4.1f boundaries fall within one round of each other in 88.5% of cases. All methods sometimes produce incorrect final answers after reaching a boundary identified by ds4.1f, but this occurs least often for TDS.
(c) Additional step and error accumulation. Interim answers are used only for checking and never written to the table. The final answer is generated independently, so an incorrect interim answer does not enter subsequent search context. An incorrectly placed boundary can affect which steps receive the outcome advantage. Tables R2–R5 examine this issue and its impact on the conclusions.
(d) EM evaluation. After excluding EM-correct answers for which ds4.1f finds no sufficient-evidence boundary or identifies uncorrected critical errors, and restoring semantically correct answers missed by EM, TDS still achieves the highest score. Gating improves the adjusted score by 2.1 percentage points, close to the original 2.2-point gain.
Setup. We compare two ways of locating the search boundary. The TDS boundary is the round of the planner's first passing interim EM check, as defined in Eq. (6). The ds4.1f boundary is the first round at which ds4.1f judges the table to contain sufficient evidence to answer the original question. Standard evaluation involves neither interim checks nor credit gating. For this diagnostic analysis, we generated interim answers from the recorded tables without changing search trajectories or final predictions. The ds4.1f criterion applies to TDS and all baselines. It also assesses uncorrected critical reasoning errors around the boundary.
(a) Parametric memory. Table R1 shows similar patterns of no-retrieval accuracy across the four models. As you noted, accuracy is above average on 2Wiki and HotpotQA and lowest on MuSiQue and Bamboogle. A memory-based passing interim check can change the allocation of the outcome advantage, but the interim answer is not reused as the final answer. In Table R2, ds4.1f finds that sufficient evidence has not yet been reached at the TDS boundary for 14.3% of trajectories with both a passing check and a correct final answer. Cases where ds4.1f finds no boundary at all are covered by deduction A in Table R5.
Table R1. No-retrieval accuracy of 3B models (EM, %)
Table R2. ds4.1f assessment of TDS trajectories around the TDS boundary (%)