Learning Adaptive Search Guidance for Knowledge Graph Question Answering

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 $\text{TriFOR}$ ($\text{Tri}$-head $\text{For}$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.