PaperlayerView exact revision on arXiv

Source-linked AI summary

Foresight-over-Graph: Reasoning Beyond Local Horizons for Knowledge Base Question Answering

Yang Hong, Yajun Yang, Xin Wang, Liping Jing, Qinghua Hu

arXiv:2610.08388v1cs.CLcs.AI

TL;DR

LLMs can hallucinate on knowledge-intensive questions, and hop-wise pruning can discard answer-critical branches before distant evidence clarifies their value. FoG uses far-to-near feedback and a memory subgraph to guide graph exploration; it outperforms prior methods on WebQSP and CWQ, with a 16.58% gain in Hit on CWQ and reduced LLM calls and token usage.

  • Problem

    LLMs may hallucinate on knowledge-intensive questions, while hop-wise greedy or beam pruning can discard answer-critical branches before distant evidence clarifies their value.

    Source: §1 · pp. 1–2

  • Method

    FoG iteratively builds a question-relevant evidence subgraph, uses far-to-near feedback to guide pruning, and maintains a memory subgraph across exploration.

    Source: §1 · p. 2

  • Results

    FoG outperforms prior methods on WebQSP and CWQ, gaining 16.58% in Hit on CWQ while reducing LLM calls and token usage.

    Source: §1 · p. 2, §6 · p. 9

  • Takeaways & Limitations

    FoG's larger gains on CWQ highlight its effectiveness for compositional questions with larger branching factors.

    Source: §4.2 · p. 6

    Evaluation on two widely used KGQA benchmarks leaves validation on more diverse, domain-specific knowledge graphs, such as medical or legal QA, for future work.

    Source: §6 · p. 9

Abstract

from arXiv · show

Large language models (LLMs) have demonstrated strong capabilities in question answering, yet they still frequently suffer from hallucinations on knowledge-intensive tasks. Knowledge graphs (KGs) provide LLMs with structured, interpretable, and updatable factual grounding, making them a promising external knowledge source for reliable reasoning. However, existing LLM-guided graph reasoning methods typically rely on hop-wise greedy or beam-style pruning during evidence retrieval. Such local decision processes are inherently myopic: evidence that appears weak near the source may become crucial only after deeper graph context is explored, causing answer-critical branches to be discarded prematurely and making the reasoning chain difficult to recover. To address this limitation, we propose Foresight-over-Graph (FoG), a foresight-aware evidence retrieval framework for knowledge base question answering (KBQA). FoG iteratively constructs a question-relevant evidence subgraph and uses far-to-near feedback to guide path exploration, and maintains a compact memory subgraph to support continued exploration. Extensive experiments on widely used KBQA benchmarks demonstrate that FoG achieves state-of-the-art performance, with a particularly large improvement of 16.58% in Hit on CWQ, while also reducing LLM calls and token usage. Our code is available at https://github.com/yhong7/FoG .

1 Introduction

Knowledge graphs can ground LLM answers, but hop-wise pruning may discard answer-critical evidence before distant context reveals its value. FoG uses far-to-near feedback and a memory subgraph to guide exploration, achieving strong benchmark results while reducing LLM calls and token usage.

  • Knowledge graphs offer structured, updatable, interpretable factual grounding for LLM question answering, unlike continual fine-tuning, which is expensive and struggles to track evolving facts.Source: §1 · p. 1
  • Hop-wise greedy or beam pruning can discard answer-relevant relations before distant evidence reveals which branch leads to the answer.Once a critical path is pruned, subsequent exploration cannot recover the missing evidence chain.Source: §1 · p. 2
  • FoG iteratively expands a question-relevant subgraph from source entities, filtering irrelevant triples before further exploration.The process continues until the answer is found.Source: §1 · p. 2
  • FoG combines far-to-near feedback from distant entities with a memory subgraph that preserves high-confidence evidence across iterations.The feedback helps re-score nearby triples, while the LLM uses the refined graph to generate sub-questions for the next search iteration.Source: §1 · p. 2
  • 16.58% in Hit on CWQ; FoG also reduces LLM calls and token usage against existing LLM-guided graph agents.Source: §1 · p. 2

2 Preliminaries

The preliminaries represent structured knowledge as a directed multirelational graph and define KBQA as predicting answers supported by a compact evidence subgraph.

  • A structured knowledge base is represented as a multirelational directed graph of subject-relation-object triples.Source: §2 · pp. 2–3
  • Each triple states that a relation holds between a subject entity and an object entity, providing an explicit, interpretable substrate for multi-hop evidence retrieval.Source: §2 · p. 3
  • KBQA predicts an answer set from a question, knowledge base, and source entities, with a compact evidence subgraph supporting the prediction.Source: §2 · p. 3

3 Method

FoG builds a compact question-relevant subgraph, sends distant evidence back toward source-side candidates, and retains useful evidence across iterative exploration.

3.1 Foresight Subgraph Expansion

  • FoG encodes triples with question-conditioned attention, decomposes the query into sub-questions, and scores frontier triples against pooled sub-goals and structural context during bounded BFS expansion.The scorer retains triples above an expansion threshold.Source: §3.1 · p. 3

3.2 Foresight Feedback Propagation

  • On inward-directed subgraphs, FoG propagates messages from farther nodes toward seeds, updates target states, then re-scores edges to select high-confidence potential evidence.Nodes are updated in decreasing order of their distance from the source.Source: §3.2 · p. 4

3.3 Memory Subgraph Management

  • Persistent memory retains high-confidence evidence; below-threshold triples may reappear after redirected sub-questions, while absorbed triples avoid redundant expansion and rejected triples stay masked.A compact potential subgraph is exposed to the LLM rather than the entire expanded region.Source: §3.3 · p. 5

3.4 Complexity Analysis

  • Graph-side costs scale as O(LtMd^2) for encoding, O(S(M+|E|)d^2) for scoring, and O(Lm(|E|+|V|)d^2) for propagation.M is the number of candidate triples scored during expansion; S is the number of sub-questions.Source: §3.4 · p. 5
  • Table 1 reports benchmark results for FoG and prior methods on WebQSP and CWQ, including FoG rows for GPT-4o-mini, GPT-4o, and GPT-4.The supplied table text does not identify metric labels or cell-to-metric mappings.Source: Table 1 · p. 6

4 Experiments

FoG is evaluated on WebQSP and CWQ using 19 baselines, with a three-hop budget and retrieval thresholds. Across the experiments, the results examine benchmark performance, component contributions, efficiency, retrieval trade-offs, and failure modes.

4.2 Main Results

  • FoG improves relative Hit@1 over the strongest baselines by 1.02% on WebQSP and 16.58% on CWQ, without task-specific fine-tuning.The larger CWQ gain is associated with compositional questions and larger branching factors.Source: §4.2 · p. 6

4.3 Ablation Study

  • FoG’s three modules work best in combination; removing feedback propagation causes the largest degradation, while memory matters particularly on CWQ.Removing foresight expansion also causes consistent drops.Source: §4.3 · p. 7, Table 2 · p. 7
  • FoG consistently outperforms other baselines across LLaMA-7B, GPT-4o-mini, and GPT-4 backbones, with gains on most metrics.Stronger sub-question LLMs generally improve performance, but lightweight models remain competitive across benchmarks.Source: §4.3 · pp. 7–8, Figure 4 · p. 7
  • Replacing FFP with a standard undirected GNN underperforms on both benchmarks, as generic neighborhood aggregation is insufficient for foresight-aware pruning.FFP sends distant frontier signals back to source-side candidates.Source: §4.3 · p. 7, Table 3 · p. 7

4.4 Efficiency Analysis

  • FoG uses roughly R+1 LLM calls per question, independent of beam width K, and reduces token use by not sending all candidate triples to the LLM.The added graph-side computation is described as lightweight and parallelizable, with minor overhead compared with LLM inference.Source: §4.4 · p. 8, Table 4 · p. 8

4.5 Knowledge Retrieval Capacity

  • Higher thresholds improve Pprune but can reduce Revid; at moderate thresholds, Hpath remains high while A1shot falls more quickly, especially on CWQ.The study sweeps thresholds from 0.05 to 0.90 on WebQSP and CWQ.Source: §4.5 · p. 8, Figure 5 · p. 8

4.6 Case study

  • The dominant existing-method failure is multi-hop error accumulation; other types are constraint-composition, candidate-set reasoning, and LLM summarization errors.Early relation or entity mistakes can shift the search frontier and make the correct evidence chain difficult to recover.Source: §4.6 · p. 9
  • FoG uses foresight signals to preserve globally useful branches when local scoring would prune a weak-looking relation several hops from the answer.The case study describes this as mitigating short-sighted exploration and recovering the correct reasoning path.Source: §4.6 · p. 9

5 Related Work

Related work includes graph-evidence retrieval and LLM-guided graph agents, both of which can miss answer-critical branches when decisions are based on local relevance or sequential search. FoG instead evaluates early branches by their potential downstream utility.

5 Related Work

  • Graph-embedding retrieval methods compact graph evidence, but may prune locally ambiguous triples before their downstream value becomes visible.These methods assess whether an edge or triple currently appears relevant rather than whether its branch can lead to the true evidence chain.Source: §5 · p. 9
  • LLM-guided graph agents enable adaptive exploration, but sequential search can make recovery difficult after excluding an answer-critical relation or entering an incorrect branch.The cited agent work includes planning, traversal, verification, and revision over knowledge graphs.Source: §5 · p. 9
  • FoG evaluates early triples by downstream utility, propagating distant relevance back to near-source candidates while maintaining a compact memory subgraph.This contrasts with judging edges only by immediate relevance and is intended to reduce myopic pruning while preserving globally useful evidence.Source: §5 · p. 9

6 Conclusion & Limitation

FoG combines foresight feedback and a memory subgraph manager to preserve useful evidence during multi-hop KBQA, and reports accuracy and efficiency gains on WebQSP and CWQ. Evaluation is limited to two benchmarks; the authors call for validation on more diverse, domain-specific knowledge graphs.

6 Conclusion & Limitation

  • FoG uses foresight feedback and a memory subgraph manager to preserve crucial evidence while exposing compressed subgraphs to the LLM.The authors describe this design as reducing short-sighted pruning in multi-hop KBQA.Source: §6 · p. 9
  • Experiments on WebQSP and CWQ show that FoG outperforms prior methods in accuracy and delivers better efficiency across different LLM backbones.Source: §6 · p. 9
  • Validation is limited to two widely used KGQA benchmarks; the authors identify more diverse, domain-specific graphs such as medical or legal QA as future validation targets.Source: §6 · p. 9

NeurIPS Paper Checklist

The checklist reports that the paper's claims reflect its contributions and scope and records information on experimental details, reproducibility, and other research practices. It points to specific sections for supporting information and reports several affirmative or not-applicable responses.

NeurIPS Paper Checklist

  • The authors state that their main claims reflect the contributions and scope, supported by FoG's design and results on WebQSP and CWQ.Source: NeurIPS Paper Checklist · p. 13
  • The checklist points to Section 6 for limitations and reports that the research followed the NeurIPS Code of Ethics.Source: NeurIPS Paper Checklist · pp. 13, 16
  • The checklist says relevant reproducibility information is in Section 4.1, and the authors report providing code instructions and using publicly available datasets.Source: NeurIPS Paper Checklist · pp. 14–15
  • The authors report describing dataset setups and evaluation metrics in Section 4.1 and averaging experimental results over three runs.Source: NeurIPS Paper Checklist · p. 15
  • The authors direct readers to Section F for societal impacts and state that the paper introduces no new assets and involves no human-subject research.Source: NeurIPS Paper Checklist · pp. 16, 18
  • The checklist says LLMs are core components whose roles are described in Section 3.3, and that the paper includes no theoretical results.Source: NeurIPS Paper Checklist · pp. 14, 19

A Dataset Descriptions

The experiments use two Freebase-based KBQA datasets, WebQSP and CWQ, with different question characteristics and annotations. Freebase is also described as the underlying large-scale knowledge base.

A Dataset Descriptions

  • WebQSP is a Freebase-based KBQA dataset with natural-language questions annotated with semantic parses and answers, designed for semantic parsing and multi-hop QA evaluation.Source: A Dataset Descriptions · p. 19
  • CWQ is a Freebase-based complex question answering dataset whose annotated questions require compositional and multi-hop reasoning.Source: A Dataset Descriptions · p. 19
  • Freebase is a large-scale, collaboratively constructed knowledge base originally developed by Google.Source: A Dataset Descriptions · p. 19

B Baselines

The paper compares FoG with baselines spanning non-LLM, LLM-only, graph-retrieval, and LLM-guided graph-agent approaches. Its prompt appendix describes question decomposition and memory-subgraph management, and includes case-study figures.

B Baselines

  • The comparison covers 19 baselines grouped as non-LLM, LLM-only, RAG-based, and path-search-based methods.Source: B Baselines · p. 19
  • The baseline set includes approaches such as teacher-guided multi-hop reasoning, scalable logical reasoning, sequence generation for KG prediction, and question–relation matching with graph propagation.Source: B Baselines · p. 19
  • LLM-only baselines include zero-shot, few-shot, and chain-of-thought GPT-4o prompting, while graph-oriented methods include retrieval, path search, and planning approaches.Source: B Baselines · p. 20

C LLM Prompt Template

  • Figures 7 and 8 show prompt templates, while Figures 9 and 10 present case studies of existing-method failure modes and FoG's workflow.Source: Figure 7 · p. 21, Figure 8 · p. 21, Figure 9 · p. 22
  • The question-decomposition prompt turns the original query into standalone sub-questions whose answers jointly resolve it, while prohibiting assumptions about missing facts.Source: C LLM Prompt Template · p. 22
  • The memory-management prompt selects relevant KG triples, predicts an answer only from selected triples or leaves it undetermined, and may ask clarification questions.Source: C LLM Prompt Template · p. 22

D Case study

The case study contrasts local hop-wise pruning, which can discard answer-critical edges before distant context is visible, with FoG’s feedback-guided exploration. FoG re-scores nearby triples using distant relevance signals and uses follow-up sub-questions to guide retrieval toward the answer.

  • Local greedy or beam pruning can remove answer-relevant edges that appear weak early, leaving the missing evidence chain unrecoverable and search drifting into irrelevant neighborhoods.Source: D Case study · p. 23
  • FoG propagates question-relevant signals from distant entities toward source-near nodes to re-score triples and prevent incorrect early pruning.Source: D Case study · p. 23
  • FoG incorporates the refined graph into memory and generates follow-up sub-questions to guide subsequent retrieval toward the answer.Source: D Case study · p. 23

E Training Details

The training details describe triple-level supervision for FoG’s foresight scorer, with answer-supporting triples as positives and locally sampled neighboring triples as negative candidates. At inference, the learned scorer is used with feedback propagation and a compact memory subgraph.

Training Evidence

  • Answer-supporting path triples are positive examples, while locally sampled neighboring triples outside those paths are negative candidates for the foresight scorer.Source: E Training Details · p. 24

Local Training Region and Noise Sampling

  • The per-question local training region samples neighboring noise around entities touched by positive evidence, optionally adding preprocessing anchors to the seed set.Source: E Training Details · p. 24
  • For each seed entity, noisy triples are sampled from its one-hop neighborhood in proportion to its participation in positive evidence, with κ = 10 in all experiments.Source: E Training Details · p. 24

Objective and Optimization

  • The scorer predicts whether a triple belongs to an answer-supporting path, and training uses triple-level binary cross-entropy over each question’s local training set.Source: E Training Details · p. 24
  • FoG minimizes the training objective with mini-batch AdamW for five epochs per dataset, keeping the embedding encoder frozen and using dropout at rate 0.1.Source: E Training Details · p. 25

Training and Inference Separation

  • Training labels supervise only the foresight scorer; inference expands the graph with that scorer, applies far-to-near feedback, and maintains a compact memory subgraph for answer generation.Source: E Training Details · p. 25

F Impact Statement

The impact statement presents FoG as a framework for more reliable and efficient reasoning over knowledge graphs while noting that misleading graph facts may be reinforced. It calls for validation, provenance tracking, robustness checks, and human oversight in high-stakes deployment.

  • FoG is framed as supporting LLM agents’ exploration of complex knowledge graphs and reasoning over multi-hop facts with improved reliability and efficiency.Source: F Impact Statement · p. 25
  • Potential applications named include scientific discovery, professional decision support, enterprise knowledge management, and collaborative AI assistants using structured, updatable knowledge.Source: F Impact Statement · p. 25
  • Biased, incomplete, outdated, or adversarial graph facts may be reinforced, motivating validation, provenance tracking, robustness checks, and human oversight in high-stakes use.Source: F Impact Statement · p. 25
Loading 2610.08388v1…