acceptodds
Under review as a conference paper at ICLR 2027

TDS: A Table-Driven Parallel Multi-Agent Search System with Asymmetric Credit Gating

Abstract

Agentic search answers a complex question by decomposing it into subproblems and gathering evidence over successive steps. Supervision comes from a single signal, the reference answer to the original question, while the intermediate subproblems carry no labels of their own. Learning from this supervision raises two questions. The first concerns how to organize intermediate results, which requires balancing sufficient evidence against concise records while maintaining a consistent search structure during training and inference. The second concerns assigning credit to intermediate decisions in multi-agent search, where value-based advantages depend on accurate state-value estimates across diverse search states, group-relative advantages do not distinguish steps, penalizing useful ones and reinforcing unnecessary ones, and dense supervision from reward models or LLM graders requires extra models or annotations and inherits the graders' biases. To address these two questions, we present TDS (Table-driven Dual-tier Search), a multi-agent search system that pairs a table-driven search structure with asymmetric credit gating. The structure is a global table of subproblem nodes, shared by training and inference, through which a planner and parallel executors coordinate. Each node keeps a subproblem's answer and a concise evidence summary written by an executor, so the planner can build on any completed result without carrying the search history, and independent subproblems are solved in parallel. We train the executor first, then freeze it and train the planner with the gate. During training, the planner is prompted after each expansion to answer the original question from the current table, and the first answer that matches the reference marks the steps that sufficed. Successful trajectories then reinforce only these steps rather than later unnecessary expansions, and failed trajectories no longer penalize them, which yields step-level credit without a critic or a grader. Under a common training and evaluation protocol, TDS improves seven-benchmark macro-average exact match over the strongest baseline at each scale by 2.2 percentage points (5.7% relative) with Qwen2.5-3B-Instruct and by 1.9 percentage points (4.4% relative) with Qwen2.5-7B-Instruct. Ablations confirm that both the table structure and the asymmetric gate contribute to these gains.

Primary area:
reinforcement learning
Keywords:
Agentic search, Multi-agent systems, Reinforcement learning, Credit assignment

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_PzohOpenReview ↗
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
  1. 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.
  2. 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
  1. 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.
  2. 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

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 expand steps. Its answer is not reused by finalize. 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, %)

ModelNQTriviaQAPopQAHotpotQA2WikiMuSiQueBamboogleAvg.
Base Instruct11.028.410.515.923.22.02.413.3
Tree-GRPO9.426.310.415.224.42.12.112.8
MemSearcher11.329.310.815.525.62.02.113.8
TDS planner10.828.210.214.524.42.12.213.2

Table R2. ds4.1f assessment of TDS trajectories around the TDS boundary (%)

Final outcomeds4.1f boundary not yet reachedCritical error before boundaryNo error before, error afterNo error before or after
Correct14.31.53.680.6
Incorrect34.31.952.211.6

(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 groupShare within outcomeSame round or both absent1-round gap≥2-round gapTDS boundary onlyds4.1f boundary only
Correct, passed88.981.47.01.79.9—
Correct, not passed11.129.1———70.9
Incorrect, passed15.362.28.92.426.6—
Incorrect, not passed84.784.8———15.2

Table R4. Existence of a ds4.1f boundary before finalization (%)

Final outcomeds4.1f boundaryTree-GRPOMemSearcherTDSTDS w/o Gate
CorrectExists88.883.988.087.6
CorrectAbsent (deduction A)11.216.112.012.4
IncorrectExists28.826.424.127.6
IncorrectAbsent71.273.675.972.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 (%).

MethodA: Insufficient evidenceB: Critical errorsC: Semantic EM misses
TDS12.02.414.7
TDS w/o Gate12.42.814.4
Tree-GRPO11.23.614.5
MemSearcher16.14.015.2

Table R5b. Reassessed seven-benchmark macro-average EM (%).

MethodOriginal EMAfter A and BAdjusted EM (after C)
TDS40.234.443.2
TDS w/o Gate38.032.341.2
Tree-GRPO38.032.441.5
MemSearcher37.229.739.3

Based on unrounded values, TDS's advantage over its ungated variant changes from 2.17 to 2.05 EM points after reassessment.

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

MethodHow structure is builtInformation available to policyIs construction learned?
Tree-GRPOResampling during trainingIts own pathNo
ToRPrompted expansion and rule-based pruning at inferenceIts own pathNo
ProbTree, RT-RAGPrompted decomposition before solvingIts subtreeNo
TDSBuilt incrementally by the policyFull tableYes

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.

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

This paper proposes TDS (Table-driven Dual-tier Search), a multi-agent reinforcement learning framework for open-domain question answering. TDS addresses two challenges in agentic search under outcome-only supervision: organizing intermediate search history and assigning step-level credit without a learned critic or external reward model. First, TDS structures the search state as a global table of subproblem nodes containing parent links, short answers, and concise evidence summaries; a high-level planner proposes up to three parallel subproblems per round, which are solved independently by a pretrained and frozen low-level executor. Second, during GRPO training of the planner, TDS prompts the planner after each expansion round to greedily generate an interim answer to the original question. Using the first expansion step whose interim answer matches the ground truth as a boundary, an asymmetric credit gate reinforces only the prefix up to that step on successful trajectories while shielding that prefix from negative advantages on failed trajectories. Experiments across seven single-hop and multi-hop QA benchmarks on Qwen2.5-3B and 7B backbones show consistent exact-match improvements over several agentic search baselines.

Critical strengths
  1. The combination of a structured global table with dual-tier parallel execution is clean and well-suited for multi-hop QA. Storing explicit parent links alongside short answers and brief evidence summaries prevents raw retrieved passages from flooding the planner's context while keeping training and inference interfaces identical. The ablations in Table 2 clearly demonstrate that both the tabular node representation and the evidence summaries are critical to performance.

  2. The asymmetric credit gating mechanism is a simple and clever way to obtain step-level credit from outcome-only supervision without training a unstable value critic (as nicely diagnosed by the near-zero explained variance of PPO in Figure 4a). The ablation comparing success-side-only and failure-side-only gating provides a clear explanation of why shielding good prefixes on failed trajectories is necessary to balance suppressing redundant post-pass expansions.

Critical weaknesses
  1. Using exact match of an interim greedy answer as a binary proxy for "sufficient evidence collected" is vulnerable to false positives from lucky guesses or parametric memory, particularly on comparison or yes/no questions. For instance, on binary comparison questions like the one in Figure 2(a) ("Which film has the director who died later, Seven Samurai or One Hundred Nails?"), if the planner has only retrieved evidence for one entity at step t=1, a forced interim answer still has a 50% chance of guessing the right title. Whenever an interim check passes prematurely on incomplete evidence, Eq. (7) zeros out positive credit for the subsequent expansion step t=2 that was actually needed to verify the second entity. Moreover, generating an extra greedy response from the planner after every expansion round across all M=5 rollouts adds non-trivial forward-pass overhead during training.

  2. There is a resource and retrieval-budget asymmetry between TDS and several baselines, and direct comparisons against alternative step-level credit assignment methods are missing. Under the shared 4-round limit with 3 passages per query (Appendix A.3), single-agent baselines such as Search-R1 and MemSearcher can issue only 1 query (3 passages) per round—and MemSearcher was reduced from 10 passages per query in its original setup to 3—whereas TDS can propose up to B=3 parallel subproblems (up to 9 passages) per round while utilizing two separate 3B/7B models (a frozen executor pretrained for 150 steps plus a planner trained for 662 steps). In addition, while the paper motivates asymmetric credit gating against recent critic-free intermediate credit methods that also rely solely on reference answers (such as likelihood-based reward shaping in TIPS and IGPO), none of these step-level credit assignment baselines are compared in Tables 1 or 2.

Questions for authors
  1. On binary comparison or yes/no questions in HotpotQA and 2WikiMultiHopQA, how often does the interim greedy check pass at step t=1 before both entities have been queried? Does this cause the planner to stop expanding prematurely on multi-hop questions?

  2. In Figure 3(b), TDS averages around 1.8–2.0 search queries per question, and in Figure 4(d) the mean tree depth converges to ~1.38. How does TDS compare against Search-R1 and MemSearcher when the total number of search queries (or retrieved passages) per question is strictly matched at inference time, or when a single model shares weights between the planner and executor roles?

  3. How does asymmetric credit gating compare empirically against reference-answer likelihood shaping methods (such as TIPS or IGPO) when applied to the exact same TDS table-driven architecture?

4 comments
AuthorsOpenReview ↗

W1Q1 (1/2)

Thank you for highlighting the risk that greedy interim answers may pass EM checks before sufficient evidence has been retrieved, particularly for binary comparisons and yes/no questions. We examine no-retrieval accuracy, the first passing check against an independent evidence assessment, and evidence sufficiency before finalization.

In the 3B setting, we used ds4.1f to analyze trajectories for all 51,713 test questions across seven benchmarks to address these questions

(a) No-retrieval answering. We used DeepSeek V4.1 Flash (ds4.1f) to classify all 19,981 questions in HotpotQA and 2Wiki. Binary comparisons and yes/no questions account for 18.3% and 46.0% of the respective benchmarks. Table R10 reports no-retrieval EM for four 3B models. Their similar results show that correct answers from guessing or parametric knowledge are a shared risk.

Table R10. No-retrieval EM by question type (%).

BenchmarkModel / countComparisonYes/noOtherOverall
HotpotQAQuestions (%)882 (11.9%)472 (6.4%)6,051 (81.7%)7,405
Base Instruct46.565.57.615.9
Tree-GRPO45.562.77.115.2
MemSearcher46.965.57.015.5
TDS planner47.164.65.914.5
2WikiQuestions (%)4,496 (35.8%)1,295 (10.3%)6,785 (54.0%)12,576
Base Instruct52.430.02.623.2
Tree-GRPO52.328.35.224.4
MemSearcher52.330.27.125.6
TDS planner52.429.94.824.4

(b) Premature checks and retrieved evidence. The TDS boundary is the first round whose greedy interim answer passes EM verification (Eq. 6). The independent ds4.1f boundary is the first round at which the retrieved evidence suffices to answer the original question. Among final-correct TDS trajectories with a passing interim check, 14.3% have not reached the ds4.1f boundary at the TDS boundary. This directly identifies cases of premature verification.

We further assessed whether sufficient evidence had been reached before finalization, applying the same ds4.1f criterion to all methods. Tables R11 and R4 report the four multi-hop benchmarks and all seven benchmarks, respectively. Percentages are computed separately within each method's final-correct and final-incorrect trajectories.

Table R11. Evidence sufficiency on four multi-hop benchmarks (%).

Final outcomeEvidenceTree-GRPOMemSearcherTDSTDS w/o Gate
CorrectReached82.484.083.483.3
CorrectNot reached17.716.016.616.8
IncorrectReached30.229.629.129.5
IncorrectNot reached69.870.570.970.5

Table R4. Evidence sufficiency across seven benchmarks (%).

Final outcomeEvidenceTree-GRPOMemSearcherTDSTDS w/o Gate
CorrectReached88.883.988.087.6
CorrectNot reached (A)11.216.112.012.4
IncorrectReached28.826.424.127.6
IncorrectNot reached71.273.675.972.4

On the four multi-hop benchmarks, 16.6% of TDS's correct trajectories never reached sufficient evidence, compared with 16.8% without gating, 17.7% for Tree-GRPO, and 16.0% for MemSearcher. Thus, gating does not increase the share of correct predictions obtained without sufficient retrieved evidence relative to its ungated variant.

The interim answers used in this diagnostic were generated from saved evaluation states, without changing the original search trajectories or final predictions.

AuthorsOpenReview ↗

W1Q1 (2/2)

(c) Further expansion and reassessed scores. A passing interim check does not force the planner to finalize. Gating changes training-time credit assignment, while regular inference does not run interim checks. On successful trajectories, expand steps after the first passing check receive zero advantage rather than positive credit, while finalize retains its outcome advantage. On failed trajectories, expansions before the boundary are protected from negative advantage, whereas later expansions retain it.

The ablation in Table 2 demonstrates why both sides of the gate are needed. Success-side gating alone reduces the four-multi-hop average EM from 32.8% (no gating) to 27.4%. With both sides, it rises to 34.7%. Relative to no gating, HotpotQA improves from 38.4% to 40.5%, and 2Wiki from 37.4% to 39.4%. The concern about suppressing positive credit is reflected in the success-side-only ablation, while the complete asymmetric gate improves multi-hop performance.

We further reassessed the seven-benchmark results using consistent evidence and reasoning criteria. Among originally EM-correct trajectories, deduction A identifies answers produced without sufficient retrieved evidence, and deduction B identifies additional answers relying on uncorrected critical errors. Among originally EM-incorrect trajectories, we first exclude cases with insufficient evidence or uncorrected critical errors, then identify semantically correct answers missed by exact matching as addition C.

Table R5a. Conditional rates of deductions and restorations (3B, %).

MethodA: Insufficient evidenceB: Critical errorsC: Semantic EM misses
TDS12.02.414.7
TDS w/o Gate12.42.814.4
Tree-GRPO11.23.614.5
MemSearcher16.14.015.2

A and B are shares of originally EM-correct trajectories, with B excluding cases already counted in A. C is the equivalent share of originally EM-incorrect answers eligible for restoration under the same evidence and reasoning criteria, converted from macro-averaged EM points.

We then remove A and B from the originally correct predictions and restore C from the originally incorrect predictions. Table R5b reports the resulting seven-benchmark macro-average EM.

Table R5b. Reassessed seven-benchmark macro-average EM (3B, %).

MethodOriginal EMAfter A and BAdjusted EM
TDS40.234.443.2
TDS w/o Gate38.032.341.2
Tree-GRPO38.032.441.5
MemSearcher37.229.739.3

Based on unrounded values, TDS's advantage over its ungated variant changes from 2.17 to 2.05 EM points after reassessment. The performance gain therefore remains after accounting for insufficient evidence, critical errors, and semantic mismatches.

(d) Training cost. With the unified backend (see our response to reviewer i9Rc, W2/Q2), 3B planner training takes 50.7 hours, and executor pretraining takes 6.6 hours. Interim-answer generation costs approximately 3.5 hours, or 7% of planner training, and is included in that total. Interim checking is disabled during regular inference.

Response to W2 and Q2: Retrieval Budget and Model Resources

Thank you for raising the question of retrieval-budget fairness and the resource cost of TDS's separate planner and executor.

(a) Unified retrieval cap. We re-evaluated the methods across all 51,713 questions in seven benchmarks, limiting each question to at most three retrieval queries, with at most three passages returned per query. The cap applies to the total number of queries, including TDS's parallel subquestions.

Table R12 shows that TDS retains the highest seven-benchmark macro-average EM at 37.9%, outperforming MemSearcher by 1.1 EM points under the same cap. The difference between TDS and MemSearcher narrows from 3.1 points in the original setting, indicating that the additional retrieval budget accounts for part of the performance gap, while TDS remains ahead under the constrained setting.

Table R12. Seven-benchmark macro-average EM under a unified retrieval cap (3B, %).

MethodOriginal settingAt most 3 queries
TDS40.237.9
MemSearcher37.236.8
Tree-GRPO38.035.6

The capped Tree-GRPO evaluation used an earlier Base checkpoint, so its two columns are not a within-checkpoint before/after comparison.

(b) Planner and executor resources. TDS uses separate models for planning and subquestion execution. The executor is pretrained for 150 steps on a single-hop subset of NQ and then frozen, providing a stable execution policy during planner training.

We include the executor's pretraining cost in the end-to-end comparison. With the unified backend, 3B executor pretraining takes 6.6 hours, planner training takes 50.7 hours, and total TDS training takes 57.3 hours, equal to MemSearcher's 57.3 hours. Full evaluation takes 4.4 hours for TDS and 5.1 hours for MemSearcher. The complete training and inference comparison, including Tree-GRPO and Dr. MAS, is provided in our response to reviewer i9Rc (W2/Q2).

(c) Comparison with reference answer likelihood shaping (Q3). Because our available compute resources during the rebuttal were limited, we prioritized benchmarking under a unified backend, repeated runs across multiple seeds, and evidence audits across all 51,713 trajectories, and were unable to complete direct empirical runs of TIPS and IGPO on the TDS architecture. We have provided a detailed conceptual comparison in Table R14 (in our response to Reviewer Pzoh), explaining that unlike TIPS and IGPO, TDS introduces no separate process reward and instead uses interim checks solely to gate the final outcome advantage asymmetrically.

We will add the results under the unified retrieval cap, clarify the separate model roles, and include the direct empirical comparison with TIPS and IGPO in the revised manuscript.

AuthorsOpenReview ↗

We Would Appreciate Your Consideration of Our Responses

Thank you for your careful review and valuable feedback. We have provided point-by-point responses to your comments, including additional analyses, experimental results, and clarifications addressing the main concerns. We would greatly appreciate it if you could review our responses at your convenience. Should you have any further questions or suggestions, we would be happy to provide additional clarification. Thank you again for your time and consideration.

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

TDS combines a table-based search architecture with asymmetric credit gating for multi-agent question answering. A planner expands a dependency-aware table of subproblems, while a pretrained and subsequently frozen executor retrieves evidence and returns answers and summaries. During planner training, interim answers identify the first search prefix that passes the reference-answer check. Successful trajectories reinforce this prefix, while failed trajectories protect it from negative outcome credit. Experiments cover seven QA benchmarks at two model scales.

Critical strengths
  1. The architecture provides a clear interface for retaining evidence and dependencies across rounds while executing independent subproblems in parallel. The table, summary, and parent-link ablations help identify which representation choices contribute to performance.

  2. The gating rule is simple and uses existing answer supervision without a separate learned critic or process-reward model. The two-sided gating ablation and post-pass expansion analysis provide useful evidence beyond the main benchmark improvements.

Critical weaknesses
  1. A first passing interim answer is a proxy for prefix sufficiency, rather than a direct assessment of the contribution of individual search steps. A correct answer could arise from parametric knowledge or an incidental match, and earlier unnecessary expansions still receive positive credit. The current analysis does not quantify how often the boundary reflects genuinely useful retrieved evidence.

  2. The main improvements over the strongest baselines are modest enough that variability and resource matching matter. The shared update counts and per-call limits do not equalize total computation: TDS includes executor pretraining and interim-answer generation, and the methods use different rollout structures. Appendix C provides a useful comparison with Dr. MAS, but does not establish the accuracy-cost trade-off against all strongest baselines.

Questions for authors
  1. How frequently does the planner answer correctly before any expansion, and how often does the first passing interim answer cease to be correct at subsequent checks? Would accounting for these cases change the gating benefit?

  2. Could you provide repeated-run uncertainty and an accuracy-versus-total-training-cost comparison with Tree-GRPO and MemSearcher, including executor pretraining, interim checks, and retrieval costs?

6 comments
AuthorsOpenReview ↗

W1Q1 (1/2)

Thank you for examining whether the first passing interim check identifies a search prefix supported by retrieved evidence. You ask (a) how often the planner can answer before expansion through parametric memory or chance, (b) whether this boundary reflects sufficient evidence and still rewards redundant expansions, (c) whether later interim checks can fail, and (d) whether these effects change the gains from gating.

We used ds4.1f to analyze 51,713 test trajectories across seven benchmarks at 3B and examined subsequent checks after the first pass. The results address these concerns.

(a) Parametric memory. TDS achieves 13.2% no-retrieval accuracy, comparable to the original model and two baselines, yet leads on MuSiQue and Bamboogle, where this accuracy is around 2%.

(b) Retrieved evidence. Among trajectories with a passing check and a correct final answer, 85.7% have sufficient evidence at the TDS boundary according to ds4.1f, and 88.5% have TDS and ds4.1f boundaries within one round. Credit for early exploration balances learning to explore against finer step-level attribution.

(c) Later checks. Of trajectories continuing after the first pass, 12.1% with correct final answers and 87.7% with incorrect final answers fail at least one later check. The boundary is fixed at the first pass, while the final outcome determines credit allocation.

(d) Gating gains. After adjusting EM hits for insufficient evidence, reasoning errors, and semantic matches missed by EM, TDS remains highest. The gate adds 2.1 points, close to the original 2.2-point gain.

Setup. We compare two boundaries. The TDS boundary is the first passing interim EM check (Eq. 6). The ds4.1f boundary is the first round at which ds4.1f finds sufficient evidence in the table to answer the original question. For analysis, we divide all methods' trajectories into intermediate and final-answer stages, denoted expand and finalize in TDS. Standard evaluation uses neither interim checks nor gating. We generate diagnostic interim answers from recorded tables, without altering search trajectories or final predictions. ds4.1f applies its evidence criterion across TDS and the baselines and checks for uncorrected critical errors around the boundary.

(a) Parametric memory and pre-expansion answers. Table R1 confirms similar no-retrieval accuracy across models. In training, interim answers are not written to the table or reused by finalize. A memory-based passing check can only change which expand steps receive the outcome advantage.

Table R1. No-retrieval accuracy of 3B models

ModelNQTriviaQAPopQAHotpotQA2WikiMuSiQueBamboogleAvg.
Base Instruct11.028.410.515.923.22.02.413.3
Tree-GRPO9.426.310.415.224.42.12.112.8
MemSearcher11.329.310.815.525.62.02.113.8
TDS planner10.828.210.214.524.42.12.213.2

(b) Boundary agreement and redundant expansions. ds4.1f independently identifies the first round with sufficient evidence. Table R2 analyzes the TDS boundary, and Table R3 compares the two boundaries. Among trajectories with a passing check and a correct final answer, 85.7% have sufficient evidence at the TDS boundary. The boundaries coincide in 81.4% of cases and differ by one round in another 7.0%. In the remainder, the pass may reflect parametric memory or chance. Cases with no ds4.1f boundary are included in deduction A of Table R5.

Table R2. ds4.1f assessment of TDS trajectories around the TDS boundary (%)

Final outcomeds4.1f boundary not yet reachedCritical error before boundaryNo error before, error afterNo error before or after
Correct14.31.53.680.6
Incorrect34.31.952.211.6

Table R3. TDS boundary versus ds4.1f boundary (%)

Trajectory groupShare within outcomeSame round or both absent1-round gap≥2-round gapTDS boundary onlyds4.1f boundary only
Correct, passed88.981.47.01.79.9—
Correct, not passed11.129.1———70.9
Incorrect, passed15.362.28.92.426.6—
Incorrect, not passed84.784.8———15.2

TDS credits the search prefix rather than assessing each expansion separately. Early exploration may not have an individually identifiable contribution, so some redundant steps can receive positive credit. Preserving this signal supports exploration, while gating removes positive credit after the first pass. This is a trade-off between exploration and attribution granularity.

AuthorsOpenReview ↗

W1Q1 (2/2)

(c) Subsequent interim checks. We selected TDS evaluation trajectories whose first diagnostic interim check passed and whose search continued with further expand steps. We generated additional interim answers from the recorded tables after these expansions and evaluated them using the same EM criterion. Trajectories that finalized immediately after the first pass were excluded. These checks did not alter the original trajectories or final predictions.

Table R6 shows that 87.9% of trajectories with correct final answers pass every subsequent check, while 12.1% fail at least once. Among trajectories with incorrect final answers, 87.7% fail at least one later check, whereas 12.3% pass all of them. Subsequent interim-check results thus differ substantially between successful and failed trajectories.

Table R6. Subsequent interim-check outcomes in TDS trajectories continuing after the first pass (%)

Final outcomeAt least one later check failsAll later checks pass
Correct12.187.9
Incorrect87.712.3

These results further motivate outcome-dependent credit assignment. TDS fixes the boundary at the first passing check, while the final outcome determines how credit is allocated. On success, expansions after the boundary receive no positive credit. On failure, the preceding prefix is protected from negative credit.

Table R2 provides complementary evidence. Among trajectories with a passing check but an incorrect final answer, 52.2% contain critical errors after the boundary, with none before it. Failure-side gating protects these earlier prefixes from the penalty associated with final failure.

Table R4 compares all methods using the same ds4.1f boundary criterion. Among trajectories with incorrect final answers, TDS has the lowest proportion in which the boundary was reached. Gating reduces this proportion from 27.6% to 24.1%, while the corresponding proportion among correct trajectories remains comparable to the strongest baseline.

Table R4. Existence of a ds4.1f boundary before finalization (%)

Final outcomeds4.1f boundaryTree-GRPOMemSearcherTDSTDS w/o Gate
CorrectExists88.883.988.087.6
CorrectAbsent (deduction A)11.216.112.012.4
IncorrectExists28.826.424.127.6
IncorrectAbsent71.273.675.972.4

(d) Gating gains after adjustment. 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 (%).

MethodA: Insufficient evidenceB: Critical errorsC: Semantic EM misses
TDS12.02.414.7
TDS w/o Gate12.42.814.4
Tree-GRPO11.23.614.5
MemSearcher16.14.015.2

Table R5b. Reassessed seven-benchmark macro-average EM (%).

MethodOriginal EMAfter A and BAdjusted EM (after C)
TDS40.234.443.2
TDS w/o Gate38.032.341.2
Tree-GRPO38.032.441.5
MemSearcher37.229.739.3

Based on unrounded values, TDS's advantage over its ungated variant changes from 2.17 to 2.05 EM points after reassessment.

AuthorsOpenReview ↗

W2Q2 (1/2)

Thank you for highlighting run-to-run variation and computational cost. We repeated TDS, Tree-GRPO, and MemSearcher with two additional random seeds. We also reviewed differences in their training and inference implementations, moved them to a common backend, and remeasured end-to-end runtime.

Repeated runs. The paper reports results from seed 1. Table R7 gives the mean ± standard deviation over seeds 1–3. TDS maintains the highest seven-benchmark average at both 3B and 7B, confirming the main finding across repeated runs.

Table R7. Seven-benchmark EM over three seeds (mean ± SD, %)

ScaleMethodNQTriviaQAPopQAHotpotQA2WikiMuSiQueBamboogleAvg.
3BTree-GRPO40.3±0.459.1±1.138.0±1.137.8±0.537.4±0.415.8±0.238.7±0.538.2±0.3
3BMemSearcher41.6±1.459.0±1.237.9±1.336.6±1.637.3±2.115.2±1.638.1±2.438.0±1.3
3BTDS42.8±0.859.7±0.441.0±0.840.8±0.739.7±0.717.7±0.541.9±1.240.5±0.6
7BTree-GRPO47.0±0.562.0±1.541.8±1.641.9±0.743.0±0.420.4±0.142.7±1.242.7±0.4
7BMemSearcher47.6±2.461.0±2.042.7±2.341.2±3.043.1±3.417.3±3.044.5±3.642.5±2.2
7BTDS47.7±1.562.1±0.944.4±1.443.7±1.244.0±1.321.8±0.945.6±2.444.2±1.1

Unified training and inference backend. Our original experiments reproduced the methods using their respective public codebases, with TDS built on the Dr. MAS framework. We aligned the training data, update budgets, and evaluation protocol, but low-level performance optimizations differed across repositories. A subsequent efficiency review identified discrepancies in computation, caching, and scheduling.

We therefore brought the methods onto a common backend and applied the same optimizations where applicable (https://anonymous.4open.science/r/ICLR27-TDS/). These changes target execution rather than the algorithms. Training objectives, model architectures, sampling settings, search procedures, retrieval configurations, and interaction limits remain unchanged. Search behavior is preserved. Faster execution comes from eliminating redundant computation, data movement, and synchronization, not from reducing the search workload.

Training optimizations:

  • Response-only vocabulary projection. The transformer processes the full context, but the final vocabulary projection runs only at response positions needed for the loss.
  • Shared prefixes within microbatches. Identical token prefixes reuse forward computation, and gradients from all branches flow back through the shared prefix.
  • Compiled operators. Compiling frequently used RMSNorm and MLP components reduces kernel-launch overhead.
  • Parameter residency and gradient synchronization. Reusing loaded parameters across microbatches and synchronizing after gradient accumulation reduces transfers and communication.

Inference optimizations:

  • Weight reuse. Consecutive calls reuse loaded weights until the model version changes.
  • Cross-call KV reuse. Valid prefix caches survive consecutive calls and are invalidated after a weight update.
  • Graph execution and batching. vLLM graph execution, chunked prefill, and a larger token scheduling budget improve request throughput.
  • Avoiding redundant clearing. Skipping unnecessary cache-clearing operations reduces delays between calls.

These improvements particularly reduce repeated weight synchronization and KV-cache reconstruction during role transitions in Dr. MAS and TDS. Each job uses a separate local retrieval service sharing CPU resources under a 224-core cap. For 3B TDS, its retrieval service uses two PPUs and averages 45.9 ms per query over 16 warmed-up requests, including encoding, index search, and document reads. Per-query latency is comparable across methods under the same retrieval configuration.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.