acceptodds
Under review as a conference paper at ICLR 2027

Learning Adaptive Search Guidance for Knowledge Graph Question Answering

Abstract

Knowledge graph question answering (KGQA) requires exploring multi-hop reasoning paths in a combinatorial space, where effective search guidance is crucial for both accuracy and efficiency. Recent MCTS-based KGQA systems often invoke large language models (LLMs) inside the search loop for expansion, simulation, or termination, incurring high cost and unreliability. We propose (-head ecasting for Tree Reasoning), a PUCT-based tree search framework that removes in-loop LLM calls while retaining semantic guidance via a learned forecaster that jointly predicts (i) an action prior (policy), (ii) usefulness for successful search (value), and (iii) a stop probability (stop). TriFOR is pretrained with path supervision, and an optional variant further refines the forecaster by distilling from its own MCTS search trajectories. We also introduce DeepHopQA, a controlled diagnostic benchmark for long-hop KG search that addresses specific limitations of existing benchmarks, including limited long-hop coverage, missing path supervision, and incomplete subgraphs. Across various benchmarks, TriFOR achieves strong accuracy while substantially reducing inference cost.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Knowledge Graph Question Answering (KGQA), PUCT-MCTS, Multi-hop reasoning, LLM, Knowledge-intensive NLP

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_6wRGOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

This work aims to reduce the LLM calls during the search process in multi-hop reasoning for KGQA. TriFOR runs PUCT search over question-specific Freebase subgraphs, guided by a lightweight forecaster. A PLM encoder of path prefixes, a hop-level Transformer and cross-attention to the question form three heads to predict an action prior, a continuation value and a stop probability. The forecaster is pretrained on LLM-validated gold paths. It also introduces DeepHopQA as a synthetic benchmark for multi-hop KGQA, built from CWQ subgraphs with LLM path selection, question generation and validation.

Critical strengths

The motivation of removing in-loop LLM calls from KG tree search is practical and clear, the improvement is also confirmed in the evaluation.

Critical weaknesses
  1. The conceptual novelty is modest, as policy-guided MCTS for graph walking was already introduced by prior works such as M-Walk, which the paper cites only in the appendix. RL-based KG path finding approaches such as DeepPath (Xiong et al., EMNLP 2017), MINERVA (Das et al., ICLR 2018) and MultiHopKG (Lin et al., EMNLP 2018), which includes learned stopping via a NO_OP action, are not discussed. The paper should state precisely what is new relative to these works.

  2. DeepHopQA subgraphs are built by explicitly injecting the gold path and expanding neighbourhoods around gold-path nodes, which can leave structural hints (e.g., density or degree signatures along the gold path) that a learned forecaster trained on the same distribution can exploit.-- this should not be allowed in practice.

Questions for authors

N/A

1 comment

[W1] Distinction from Prior Learned Graph Search Methods

Thank you for highlighting these relevant works. While prior studies have explored reinforcement learning and MCTS for graph traversal, TriFOR differs from prior graph-search methods in objective, supervision, and search guidance. M-Walk combines learned policy and action-value guidance with MCTS for relation-query graph walking, with termination represented as a STOP action. DeepPath$^{[1]}$ learns relational paths through embedding-based reinforcement learning, while MINERVA$^{[2]}$ and MultiHopKG$^{[3]}$ use reinforcement learning to navigate knowledge graphs for relation-query answering.

TriFOR differs in both its learning supervision and its evidence-oriented search objective. Rather than learning graph traversal primarily from reward signals for structured relation queries, TriFOR targets semantically relevant evidence-path retrieval for natural-language KGQA and constructs step-level supervision from LLM-validated gold reasoning paths. Specifically, we jointly train an action prior, a state-level continuation value, and an explicit answer-readiness signal to guide PUCT-based action selection and expansion, leaf evaluation and value-based pruning, and adaptive termination, respectively. By conditioning these complementary forecasts on the natural-language question and partial reasoning path, TriFOR retrieves ranked evidence paths for final LLM answering, replacing repeated in-loop LLM decisions with lightweight forecaster evaluations while retaining a single final-answer LLM call.

We further strengthen the empirical evidence for this design. As reported in Tables R.1–R.2 of our response to Reviewer 5Nm5 [W1, Q1], removing the policy, value, or stop head on DeepHopQA reduces Hits@1 by 12.8, 7.6, and 16.3 percentage points, respectively, using value-threshold termination for the stop-head ablation. Moreover, two comparably trained alternatives, a joint state classifier and a learned STOP-action formulation, remain numerically weaker than TriFOR across WebQSP, CWQ, and DeepHopQA, with differences ranging from 0.7 to 2.5 percentage points.

These results support the benefit of the complementary forecasting signals within TriFOR's lightweight KGQA search framework. We will expand the discussion of these prior approaches in the main manuscript and clarify TriFOR's methodological distinctions and contributions.

[1] Xiong et al. DeepPath: A Reinforcement Learning Method for Knowledge Graph Reasoning. EMNLP, 2017. [2] Das et al. Go for a Walk and Arrive at the Answer: Reasoning Over Paths in Knowledge Bases using Reinforcement Learning. ICLR, 2018. [3] Lin et al. Multi-Hop Knowledge Graph Reasoning with Reward Shaping. EMNLP, 2018.

[W2] Robustness to Gold-Aware Subgraph Construction

Thank you for raising this concern. DeepHopQA guarantees the inclusion of LLM-validated gold reasoning paths to support controlled long-hop evaluation. We agree that this construction could introduce structural cues correlated with the annotated gold paths.

To investigate whether TriFOR's performance depends on these cues, we conducted additional experiments on 1,000 DeepHopQA questions. Specifically, we reconstructed question-specific subgraphs without using annotated gold paths for edge injection or neighborhood expansion and evaluated TriFOR and ReaRev under identical graph conditions. This intervention changes subgraph construction, not the use of gold reasoning paths as training supervision.

Table R.11. Evaluation on gold-blind reconstructed subgraphs. Values indicate TriFOR minus ReaRev Hits@1 (percentage points).

Evaluation settingΔ\Delta H@1 (pp)
Existing checkpoints evaluated on gold-blind subgraphs+10.6
Both models retrained with gold-blind graph construction+5.6

In the first setting, we evaluated the existing checkpoints on reconstructed test subgraphs without gold-path-aware edge injection or expansion. In the second, both methods were retrained using matched gold-blind subgraph conditions. These results show that TriFOR's relative advantage on the reconstructed graphs does not require gold-path-aware test-subgraph construction and persists when both methods are retrained under the same conditions.

We additionally evaluated robustness in increasing graph complexity. As detailed in our response to Reviewer idQ2 [Q6], TriFOR exhibits substantially smaller performance degradation than ReaRev when additional connected distractor edges are introduced.

These comparisons address robustness under reconstructed graphs rather than establishing superiority under every graph construction. Together, they provide evidence that TriFOR remains effective without gold-path-aware test-subgraph construction. We will incorporate these results and clarify the scope of DeepHopQA's controlled evaluation in the revised manuscript.

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

This paper proposes TriFOR, a search-guidance framework for knowledge graph question answering. A lightweight three-head forecaster predicts action priors, continuation values, and stopping probabilities to guide PUCT-based Monte Carlo tree search without in-loop LLM calls. An LLM is retained for final answer generation. The forecaster learns from path-level supervision, while an optional variant, TriFOR+, further refines it through distillation from its own search trajectories. The paper also introduces DeepHopQA, a controlled benchmark for long-hop reasoning.

The authors evaluate TriFOR on WebQSP, CWQ, and DeepHopQA, with supplementary experiments on incomplete knowledge graphs using BRINK-Wikidata5m. They report improved answer accuracy and reduced inference latency. However, incomplete comparisons with relevant methods and limited benchmark coverage make it difficult to establish the contribution and generalizability of the framework.

Critical strengths
  1. Practical improvement in search efficiency. TriFOR uses a lightweight three-head forecaster to guide tree search without in-loop LLM calls, while retaining an LLM for final answer generation. The reported accuracy and latency improvements, supported by forecasting-head ablations and hardware-controlled runtime comparisons, suggest a useful approach to reducing the computational overhead of KGQA.

  2. Controlled investigation of long-hop reasoning. DeepHopQA provides a controlled setting for examining reasoning over longer graph paths. The accompanying human evaluation, shortcut analysis, and sensitivity tests provide useful evidence about benchmark quality. Together with the path-retrieval and search-controller analyses, these experiments help characterize the framework beyond aggregate answer accuracy.

Critical weaknesses
  1. Incomplete comparisons with relevant prior work. The paper neither discusses nor compares against KBQA-o1 (ICML 2025), an important MCTS-based KBQA method. Representative LLM+KG approaches such as ToG and EoG are also missing from the comparisons. Since efficient search for KGQA is central to the proposed contribution, these omissions limit my confidence that the reported results establish a substantial advance over the most relevant existing approaches. Comparisons under comparable experimental settings, or clear explanations of task-formulation differences that prevent meaningful comparisons, are needed.
  2. Limited benchmark coverage and unclear broader applicability. The main KGQA evaluation covers WebQSP, CWQ, and the newly introduced DeepHopQA. Evaluation on additional established benchmarks, such as GrailQA, would provide stronger evidence of compositional and zero-shot generalization. Moreover, WebQSP and CWQ are both based on Freebase, while DeepHopQA uses controlled, question-specific subgraphs. Although the paper includes BRINK-Wikidata5m experiments, the extent to which these establish end-to-end QA effectiveness across different knowledge graphs should be clarified. The method mainly appears to be an efficient adaptation to KGQA; whether it can also benefit domain-specific knowledge graph tasks remains unclear. These limitations make it difficult to assess how broadly the reported gains extend beyond the evaluated settings.
Questions for authors
  1. How does TriFOR compare with KBQA-o1 under comparable datasets, knowledge graph access, and computational budgets? If a direct comparison is inappropriate, what specific differences prevent it?

  2. Could the authors evaluate TriFOR on additional established KGQA benchmarks, such as GrailQA, to assess compositional and zero-shot generalization?

  3. Why are representative LLM+KG methods such as ToG and EoG missing from the comparisons? Could the authors include these methods or explain why meaningful comparisons are not possible?

  4. To what extent do the BRINK-Wikidata5m experiments establish end-to-end QA performance beyond Freebase? When transferring to another knowledge graph or a specialized domain, does TriFOR require new path-level supervision, forecaster retraining, or changes to the search strategy?

  5. What are the training and supervision-generation costs of TriFOR and TriFOR+? How many inference queries are needed for the latency savings to offset these additional costs?

  6. How sensitive is TriFOR to the size and construction of DeepHopQA’s question-specific subgraphs? Does its advantage persist when substantially more irrelevant entities and relations are included?

2 comments

[W1, Q1, Q3] Comparisons with Relevant LLM-Guided KG Search Methods

Thank you for highlighting these related methods. As you pointed out, we agree that ToG is a strong baseline for our method, and we have already included comparison experiments with it in Tables 7 and 18. We provide additional controlled comparisons below.

We evaluated TriFOR and ToG on the full WebQSP and CWQ test sets using Qwen-2.5-14B. For ToG, each method retains its own KG search procedure, while the retrieved evidence is passed to the same final-answer LLM with identical prompting and evaluation settings. For Explore-on-Graph (EoG)[1]^{[1]}, we evaluated a prompt-based variant using the same LLM backbone, without EoG's supervised fine-tuning and reinforcement learning with path-refined rewards.

Table R.6. Full-test comparisons with LLM-guided KG search (Hits@1).

MethodWebQSPCWQ
TriFOR83.062.1
ToG (shared reader)73.056.4
EoG (prompt-based)74.258.8

Under the shared final-answer setting, TriFOR outperforms ToG and the prompt-based EoG variant on both datasets, using one LLM call and 7–9 and 17–21 times fewer tokens, respectively. With ToG's original answering prompt, the two methods achieve comparable accuracy, but our evidence analysis found that approximately 39–63% of ToG's answers were not supported by its explored triples. This further motivates the shared evidence-grounded comparison.

Comparison with KBQA-o1.

We examined KBQA-o1$^{[2]}$, which uses MCTS to guide stepwise logical-form generation through atomic query tools and KB environment interactions. The resulting logical form is executed as a graph query to obtain answer entities. In contrast, TriFOR performs forecast-guided PUCT-MCTS directly over question-specific subgraphs, where states encode the question and a partial reasoning path and actions traverse outgoing KG edges. Thus, the methods operate over different search spaces and produce different outputs: executable logical forms versus retrieved evidence paths.

Consequently, KBQA-o1 is not a drop-in baseline for TriFOR's evidence-path retrieval setting. A controlled comparison would require reproducing KBQA-o1's logical-form generation pipeline and KB query interface, including its separately trained policy and reward models, rather than applying it to our provided question-specific subgraphs. KBQA-o1 reports 60.1 F1 on WebQSP using Qwen-2.5-14B under 100-shot supervision, which does not constitute a matched comparison under our KG access and supervision settings. We will clarify these distinctions in the revised manuscript.

[1] Explore-on-Graph: Incentivizing Autonomous Exploration of Large Language Models on Knowledge Graphs with Path-refined Reward Modeling. ICLR, 2026. [2] KBQA-o1: Agentic Knowledge Base Question Answering with Monte Carlo Tree Search. ICML, 2025.

[W2, Q2] Additional Generalization Evaluation on GrailQA

Thank you for suggesting GrailQA. We extended our evaluation to this benchmark, including its IID, compositional, and zero-shot splits. We trained a GrailQA-specific forecaster and evaluated it on the full set of 6,763 questions.

Table R.7. GrailQA development-set results under the setting with provided seed entities and question-specific subgraphs (H@1).

ModelOverallIIDCompositionalZero-shot
TriFOR (GrailQA-trained)55.165.549.353.0
TriFOR (CWQ-trained, direct transfer)40.842.428.745.1
LLM-only (Qwen-2.5-14B)19.014.112.423.8

The GrailQA-trained forecaster substantially improves over direct CWQ transfer and LLM-only answering, supporting dataset-specific search guidance. We further compared TriFOR on the same ToG-1000 subset.

Table R.8. GrailQA ToG-1000 comparison (H@1). LLM calls and tokens are approximate per-question values.

MethodOverallIIDCompositionalZero-shotLLM callsTokens
TriFOR72.785.069.268.51~950
EoG (prompt-based)75.167.163.182.71~20,000
ToG (native answering)69.864.258.176.3~8~6,000
ToG (shared reader)72.772.559.177.6~8~6,000
KAPING55.8–––1~270
RoG14.6–––2~1,250

On ToG-1000, TriFOR achieves competitive overall accuracy and the highest IID and compositional scores, while requiring substantially fewer tokens than ToG and EoG. Although EoG and ToG perform better on zero-shot questions, one possible explanation is that LLM-guided exploration can leverage pretrained semantic knowledge. We leave further investigation to future work. Overall, these results demonstrate a strong accuracy–efficiency trade-off, particularly for compositional questions. We will clarify that the full GrailQA development set and ToG-1000 are different evaluation populations whose absolute scores are not directly comparable.

[Q4] Scope of BRINK-Wikidata5m and Cross-KG Adaptation

Thank you for this clarification request. We included BRINK-Wikidata5m to examine whether TriFOR's forecast-guided search framework can be adapted beyond Freebase, including settings where direct supporting evidence is missing. In this experiment, the forecaster is trained separately using rule-grounded proof paths from the target benchmark. The adapted configuration uses textualized entity and relation labels, bidirectional search, and direct answer selection from the search tree without an LLM reader.

Importantly, this experiment demonstrates target-KG adaptation rather than zero-shot transfer of an unchanged Freebase-trained model. Applying TriFOR to a new KG requires suitable graph representations and path-level supervision, along with corresponding adjustments to the forecaster and search configuration. We will clarify this distinction and the scope of our cross-KG generalization claims in the revised manuscript.

[Q5] Cost and Amortization

Thank you for raising the question of training costs and amortization. We analyze how TriFOR's one-time forecaster-training cost can be amortized over repeated inference queries by comparing its training time with the per-query inference time of the evaluated baselines.

For a baseline BB, let CsetupC_{\mathrm{setup}} denote the one-time training time and cqueryc_{\mathrm{query}} the per-query inference time. When TriFOR has lower per-query inference time, the break-even query count is

\frac{ \max(0,C_{\mathrm{setup}}^{\mathrm{TriFOR}}-C_{\mathrm{setup}}^{B}) }{ c_{\mathrm{query}}^B-c_{\mathrm{query}}^{\mathrm{TriFOR}} } \right\rceil.$$ **Table R.9.** Estimated break-even inference queries under the evaluated latency-based assumptions. Parentheses indicate the percentage relative to the corresponding training-set size. | Baseline | WebQSP (2,826 train) | CWQ (27,639 train) | DeepHopQA (24,108 train) | |-|-|-|-| | REKG-MCTS | 534 (18.9%) | 1,023 (3.7%) | 1,222 (5.1%) | | RTSoG | 239 (8.5%) | 526 (1.9%) | 739 (3.1%) | REKG-MCTS and RTSoG require no task-specific model training in our evaluated settings, whereas TriFOR incurs an upfront forecaster-training cost. Even assigning zero training cost to these baselines, the estimated break-even points correspond to only **3.7–18.9% of the training-set size against REKG-MCTS and 1.9–8.5% against RTSoG**. These results suggest that TriFOR's training cost can be amortized after a relatively modest number of inference queries compared with the scale of its training data. Compared with directly using shortest paths for supervision, LLM-based path validation may incur additional one-time LLM calls during data preparation. TriFOR further requires only **one LLM call per question**, compared with approximately **15–326 calls** for the evaluated LLM-in-the-loop MCTS baselines. TriFOR+ incurs additional training cost without reducing inference-time LLM calls and is therefore treated as an optional refinement stage rather than an inference-efficiency mechanism. > **[Q6] Robustness to Subgraph Size and Distractor Relations** Thank you for this suggestion. We conducted additional experiments on the DeepHopQA test set to evaluate **robustness to increasing subgraph complexity**. Specifically, we expanded question-specific subgraphs with **additional connected distractor edges**, increasing the number of irrelevant but searchable alternatives encountered during graph traversal. **Table R.10.** Hits@1 (%) under increasing distractor-edge expansion on DeepHopQA. | Graph expansion | TriFOR Hits@1 | ReaRev Hits@1 | |-|-|-| | Original subgraph | 67.2 | 64.6 | | 2× distractor edges | 58.0 | 40.0 | | 4× distractor edges | 45.6 | 19.7 | TriFOR consistently outperforms ReaRev across all evaluated graph settings, with its advantage widening as distractor density increases. Notably, under 4× expansion, TriFOR maintains a 25.9-percentage-point Hits@1 advantage, demonstrating **greater robustness to irrelevant search alternatives** across the full DeepHopQA test set. We additionally examined robustness to gold-path-aware subgraph construction by reconstructing subgraphs without using annotated gold paths, as detailed in our response to **Reviewer 6wRG [W2]**. Together, these experiments provide complementary evidence that **TriFOR's forecast-guided search remains effective under increasing search-space complexity and alternative subgraph construction settings**. We will incorporate these results into the revised manuscript.
Reviewer_5Nm5OpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper introduces TriFOR (Tri-head Forecasting for Tree Reasoning), a forecast-guided PUCT-MCTS framework for knowledge graph question answering. A lightweight forecaster with a shared encoder jointly predicts an action prior, a continuation value, and a stop probability, removing in-loop LLM calls. Offline pretraining uses gold-path prefixes and synthetic corrupted states; TriFOR+ additionally distills MCTS visit distributions and empirical continuation success. The paper also introduces DeepHopQA, a controlled long-hop benchmark with LLM-validated gold reasoning paths and question-specific subgraphs. Evaluation covers QA accuracy, inference latency, and search diagnostics on WebQSP, CWQ, and DeepHopQA, plus a separately trained evaluation on BRINK-Wikidata5m. The reported results support the accuracy and inference-efficiency benefits of the overall system.

Critical strengths

1.A practical improvement in inference efficiency. Replacing internal LLM decisions with lightweight forecasts addresses a real computational bottleneck while maintaining strong QA performance on established benchmarks. The hardware-normalized evaluation demonstrates substantial latency reductions relative to the evaluated LLM-in-the-loop MCTS baselines. This makes the contribution practically valuable beyond its accuracy improvements.

2.A useful controlled setting for long-hop search. DeepHopQA pairs questions with validated reasoning paths and branching, question-specific subgraphs, enabling investigation of search over longer evidence chains. The paper explicitly presents it as a controlled diagnostic benchmark rather than a substitute for naturally occurring KGQA. This framing appropriately bounds its contribution while providing useful supervision for studying long-hop retrieval.

Critical weaknesses

1.The specific contribution of the policy/value/stop decomposition remains insufficiently isolated for long-hop search. The head ablations on WebQSP and CWQ demonstrate that the components are useful within the proposed pipeline. However, these results do not cover DeepHopQA or compare against appropriately trained simpler learned-search variants with equivalent supervision. Since the system combines path supervision, three forecasting heads, and PUCT search, the reported results leave open how much of its long-hop advantage specifically requires the three-head decomposition. Comparisons using equivalent supervision and matched unique-state evaluation budgets would clarify this contribution.

2.The semantic reliability of the supervision proxies remains insufficiently quantified. Offline training treats sampled corrupted off-path states as value/stop negatives, while TriFOR+ measures continuation success through gold-answer hits. These proxies may penalize semantically valid alternative continuations or count answer-reaching trajectories as successful without establishing that their evidence satisfies all question constraints. The concern is not that continuation value should represent exact reachability, but that the impact of these mismatches on pruning and adaptive termination remains unclear. A targeted audit of search-induced states and the jointly retrieved evidence would better distinguish successful answer recovery from semantically justified reasoning.

Questions for authors

1.On DeepHopQA, do the gains persist against appropriately trained simpler learned-search variants using the same validated paths and answer-readiness supervision, at matched unique-state evaluation budgets? What evidence isolates the benefit of the policy/value/stop decomposition itself?

2.For correct final answers, how often do the retrieved evidence paths, considered jointly, satisfy all question constraints? Does an audit of search-induced states identify semantically valid alternative continuations that receive low continuation values or are incorrectly pruned?

3.During TriFOR+ trajectory generation, simulations terminate upon reaching gold answer entities, whereas inference uses learned value and stop signals. How sensitive are the refinement gains to this difference? Do the gains persist when trajectories are generated with the inference-time termination rules, without additional gold-answer-based early stopping, while retaining gold answers for outcome supervision?

3 comments

[W1, Q1] Evaluating the Contribution of the Forecaster Decomposition

Thank you for this suggestion. We distinguish two questions: whether removing a forecasting signal harms the current system, and whether a comparably trained simpler parameterization can provide the same functionality.

While the main paper already reports head ablations on WebQSP and CWQ (Table 3, with detailed results in Appendix Table 25), we extend the same analysis to DeepHopQA to examine the contribution of each forecasting signal under long-hop reasoning.

Table R.1. Head ablations on DeepHopQA.

SettingH@1Δ\Delta H@1 (pp)
Full TriFOR67.2–
Without policy54.4−12.8
Without value59.6−7.6
Without stop (value-threshold termination)50.9−16.3
Without stop (fixed-depth termination)58.7−8.5

Table R.1 shows that the policy, continuation-value, and stopping signals each contribute to effective search, as removing individual heads leads to substantial performance degradation. To examine whether the separate three-head parameterization is necessary, we additionally trained two simpler alternatives separately using the same path-level supervision and answer-readiness information:

  1. Joint Value–Stop Classifier: We retain the policy head but replace the separate value and stop heads with a three-class classifier that distinguishes off-path, useful nonterminal, and answer-ready states. The predicted class probabilities are used to derive continuation-value and stopping scores.
  2. STOP-as-Action Policy: We retain the policy and value heads but replace the separate stop head by adding a learned STOP action to the policy's action space. Search terminates when STOP is selected.

Both alternatives learn when to terminate without relying on fixed-depth stopping. For the joint classifier, the stopping threshold is selected on the validation set, whereas the STOP-action variant terminates through action selection during search. To ensure a fair comparison, all three models use the same upper limit on the number of distinct search states evaluated.

Table R.2. Comparably trained simpler-model ablations. Values indicate changes in Hits@1 (pp) relative to full TriFOR; negative values favor TriFOR.

DatasetJoint Value–Stop ClassifierSTOP-as-Action Policy
WebQSP−2.5−0.8
CWQ−1.2−0.9
DeepHopQA−1.1−0.7

Table R.2 shows a consistent numerical advantage for the explicit three-head decomposition over simpler learned alternatives. Together, these results highlight the benefit of explicitly separating action selection, continuation-value estimation, and adaptive termination, while simpler alternatives remain competitive. We will incorporate these additional comparisons and clarify the contribution in the revised manuscript.

[Q3] TriFOR+ Refinement Without Gold-Answer Early Stopping

Thank you for this question. TriFOR+ generates refinement trajectories using the pretrained TriFOR forecaster, whose stop head has already been trained with offline answer-readiness supervision. We therefore examined whether gold-answer-based early stopping (oracle-stop) is necessary during trajectory generation for TriFOR+ refinement. We compared the original oracle-stop setting with a no-oracle-stop variant that uses the learned stop head under the inference-time termination rules, while retaining gold answers for outcome supervision.

Table R.5. No-oracle-stop minus oracle-stop refinement, Hits@1 differences in percentage points with paired-bootstrap 95% confidence intervals.

Trajectory termination settingWebQSPCWQDeepHopQA
Default thresholds−0.8 [−2.0, +0.4]+0.5 [−0.4, +1.4]−1.2 [−2.5, +0.0]
Validation-selected thresholds+0.7 [−0.4, +1.8]+0.9 [−0.2, +2.1]0.0 [−1.2, +1.2]

Across all three datasets and both threshold settings, removing oracle stopping produces no statistically significant Hits@1 differences. Importantly, the learned stop head already terminates at 98.9%, 98.4%, and 93.8% of visited gold-answer nodes on WebQSP, CWQ, and DeepHopQA, respectively.

We originally used gold-answer-based stopping as a simple rule for training-time trajectory collection, rather than as a necessary component of TriFOR's search. These findings suggest that the learned stop head already handles most of the termination decisions otherwise made by the oracle, explaining the limited sensitivity to its removal. Together with the stop-head ablations in our response in [W1, Q1], these results highlight the contribution of learned termination. We will clarify that oracle stopping was used for simplicity during refinement, while inference relies on the learned stopping mechanism.

[W2, Q2] Reliability of Value Supervision and Search Evidence

Thank you for highlighting the distinction between answer reachability and semantically valid reasoning. We will clarify that reaching a gold-answer entity does not necessarily establish semantic correctness.

Interpretation of hard-negative supervision.

We agree that hard-negative supervision can penalize recoverable prefixes. Our construction prioritizes consistency with validated demonstrations without exhaustively checking whether deviations admit successful continuations. This provides inexpensive search supervision but introduces a trade-off: suppressing unsupported deviations may also discard valid recovery paths. We therefore do not assume that corrupted prefixes are necessarily unrecoverable. The key practical question is whether accounting for their continuation outcomes improves downstream search enough to justify the additional supervision and exploration costs. We investigate this through the following analyses.

Under an undiscounted terminal-success reward, validated successful prefixes have an observed return of 1. Corrupted prefixes receive zero value targets without observed continuation outcomes, while zero stop targets indicate that they are not annotated as answer-ready. Thus, value negatives are contrastive targets, not observed unsuccessful returns.

Although value-head labels are binary, the BCE objective admits a probabilistic interpretation. Considering the expected value-head BCE loss alone over sampled validated prefixes and corruptions, its optimal unconstrained predictor estimates P(Yref=1∣s)P(Y_{\mathrm{ref}}=1\mid s), where YrefY_{\mathrm{ref}} indicates that a state was sampled as a validated prefix. This probability reflects the training distribution, not semantic validity or policy-dependent continuation success.

Our pairwise-ranking objective complements this interpretation. Let gθ(s)=logit⁡(Vθ(s))g_\theta(s)=\operatorname{logit}(V_\theta(s)) denote the value logit, and define

ℓPR(s+,s−)=log⁡(1+exp⁡(gθ(s−)−gθ(s+))).\ell_{\mathrm{PR}}(s^+,s^-) = \log (1+\exp(g_\theta(s^-) - g_\theta(s^+)) ).

For pairs sampled from the training comparison distribution,

\le \frac{\mathbb E[\ell_{\mathrm{PR}}(s^+,s^-)]}{\log 2}.$$ This bounds misranking probability for sampled pairs, while positive-prefix BCE additionally discourages pruning validated paths. **Empirical validation.** **Table R.3.** Corrupted-prefix and search diagnostics (%). | Diagnostic | WebQSP | CWQ | DeepHopQA | |-|-|-|-| | Corrupted prefixes with bounded answer reachability | 13.6 | 44.8 | 22.0 | | Corrupted prefixes with an LLM-assessed valid answer-reaching path | 10.3 | 6.4 | 3.0 | | Value-pruned states on annotated gold paths | 1.5 | 0.3 | 0.1 | | Correct answers with a gold path in top-20 evidence | 88.2 | 80.7 | 90.8 | The second row combines bounded reachability with LLM-assessed path validity among reachable prefixes (76.0%, 14.2%, and 13.5%). Thus, graph-theoretic reachability overestimates observed valid alternatives. The last two rows use all value-pruned states and correctly answered questions as denominators, respectively. **Joint evidence support.** An LLM judge assessed whether the top-20 retrieved paths jointly satisfy all question constraints. For correct answers, it accepted 76.0%, 65.6%, and 90.2% of evidence sets on WebQSP, CWQ, and DeepHopQA, versus 2.8%, 1.9%, and 0.7% for answer-removed controls. These results complement the gold-path inclusion statistics in Table R.3. Disabling value-based pruning did not significantly improve Hits@1 but increased evaluated states by up to 263%. Together with the low proportion of annotated gold-path states among pruned states, this supports pruning efficiency without a detected aggregate accuracy penalty. **Soft-value target.** We compared hard-negative supervision with **rollout-derived soft-value targets**. For each corrupted prefix, we sampled multiple continuations using the pretrained TriFOR policy and used the fraction reaching a gold-answer entity as its soft target. We then retrained the value head using these targets. These **soft targets approximate answer-reaching probabilities** under the fixed pretrained policy. **Table R.4.** Soft-label minus hard-label supervision; paired-bootstrap 95% confidence intervals for differences in percentage points. | Metric | WebQSP | CWQ | |-|-|-| | $\Delta$ Hits@1 (pp) | +0.5 [−0.2, +1.2] | −0.6 [−1.5, +0.4] | | $\Delta$ Answer Hit@20 (pp) | +0.1 [−0.5, +0.6] | −2.0 [−2.7, −1.3] | | Evaluated states per question (soft / hard) | 95 / 93 | 466 / 146 | The variants show similar value-ranking AUROC (0.914 vs. 0.919). Soft targets yield no detected Hits@1 advantage while substantially increasing evaluated states on CWQ. These findings support **hard-negative supervision as an efficient search-guidance surrogate** under the evaluated conditions. We will clarify these findings in the revised manuscript.

Thank you for the detailed rebuttal. After carefully reading the response and the other reviews, my concern about the contribution’s scope remains. The method seems better framed as an efficient search accelerator guided by a proxy objective than as validated multi-hop reasoning, a distinction the current framing could make clearer. I will keep my score there but would be fine with rejection.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.