Abstract
Knowledge-Based Question Answering (KBQA) often struggles with multi-hop reasoning due to the exponential growth of the search space, leading most models to impose an arbitrary "maximum hop" limit. We present UHop, a novel framework that reframes relation extraction as a transition-based search with an integrated termination decision. This approach reduces search complexity from exponential to polynomial while enabling "unrestricted" hop counts. Evaluated on standard benchmarks and a 10-hop synthetic dataset, UHop demonstrates superior efficiency and maintains near-perfect accuracy on long-path questions where baseline models collapse.
1. Introduction
In KBQA, systems navigate a Knowledge Graph (KG) from a topic entity to an answer entity. Each link represents a "hop." Traditional relation-chain-based models suffer from two primary issues: the horizon problem, where they cannot answer questions requiring more hops than their hard-coded limit (usually 2 or 3), and computational inefficiency caused by exhaustive searching within those limits. UHop addresses these by allowing the model to dynamically decide the path length and when to stop.
2. The UHop Framework
UHop decomposes the task into iterative subtasks, moving step-by-step through the graph rather than evaluating entire chains at once.
2.1 Transition-Based Search
Instead of predicting an entire chain, UHop performs single-hop relation extraction at each step. It selects the most likely next relation based on the current entity and the question context. By moving step-by-step, UHop shifts the search space complexity from $O(n^L)$ to $O(n \times L)$, where $n$ is the number of relations and $L$ is the path length.
2.2 Comparative Termination Decision
A key innovation is the implicit "stop" signal. UHop compares the score of the current relation to the scores of all potential subsequent relations. If the current step's score is higher, the model terminates, assuming the destination is reached. This eliminates the need for a separate termination classifier and extra parameters.
2.3 Dynamic Question Representation (DQ)
To prevent loops and maintain focus during long walks, UHop employs an attention mechanism that "de-focuses" parts of the question already addressed by previous hops. This prevents the model from re-extracting the same information and helps mitigate error propagation.
3. Experimental Evaluation
UHop was tested on WebQSP (1-2 hops), PathQuestion (2-3 hops), and a synthetic Grid World dataset designed as a "stress test" for long-path reasoning (up to 10 hops).
3.1 Efficiency and Accuracy
On WebQSP, UHop reduced the candidate relation search space by approximately 30% compared to exhaustive methods while matching or exceeding the accuracy of state-of-the-art models like HR-BiLSTM and ABWIM.
3.2 Long-Path Robustness
The Grid World experiments highlighted UHop's primary advantage. As path lengths increased toward 10 hops, traditional models like MINERVA and Neural LP saw their accuracy plummet. In contrast, UHop variants maintained near 100% accuracy across all hop counts, demonstrating its capability for deep graph traversal.
4. Conclusion
UHop provides a scalable and robust solution for multi-hop KBQA by reframing the problem as a transition-based search. Future work includes incorporating beam search to improve performance in noisy, real-world Knowledge Graphs and addressing length-based overfitting during training to ensure correct termination across all question types.
Summary updated