Clearing the FoG: Training KG Agents to Retrieve the Evidence Behind Their Answers

1 Introduction

• Retrieval-based methods can miss key evidence, while agent-based methods may answer after the first hop; FoG retrieves every supporting triple.The compared methods can all return the correct answer.Source: §1 · p. 1, Figure 2 · p. 2
• Existing KG agents can answer correctly while retrieving only part of the supporting triples, because their training data and rewards focus on answers rather than evidence.Recovering supporting triples after a question is written is costly.Source: §1 · p. 2
• FoG combines evidence-grounded synthesis, a KG interaction agent that records returned triples, and ECPR, which rewards each supporting triple when first retrieved.Synthesis recursively hides explicit entities behind verifiable sub-questions, so each question carries its supporting triples.Source: §1 · p. 2
• FoG’s synthesis supplies dense retrieval rewards without an LLM judge or extra annotation.The supporting triples are embedded in the synthetic questions.Source: §1 · p. 2
• On three benchmarks, 3B–4B FoG agents outperform substantially larger baselines in answer accuracy and evidence coverage, with zero-shot cross-KG transfer.The introduction reports these outcomes as FoG’s benchmark results.Source: §1 · p. 2

Knowledge graph augmented reasoning

• Retrieval-based methods condition LLMs on triples, paths, or subgraphs, while agent-based methods explore KGs iteratively, including through RL-trained agents (Lin et al., 2025).ToG and PoG prompt frozen LLMs; existing agents can answer correctly without retrieving supporting triples.Source: §2 · p. 3

Synthetic data for KGQA

• Synthetic KGQA data has been used for agent training and benchmarking or retriever training, while FoG makes each question evidence supervision.Each synthesized question carries the evidence that defines its reward.Source: §2 · p. 3

Rewards for KG agents

• Most KG-agent RL uses final-answer outcome rewards, while dense process rewards rely on an LLM judge or gold paths and logical forms.FoG derives dense rewards from supporting triples already carried by synthesized questions, without the extra cost of a judge or gold-reference recovery.Source: §2 · p. 3

3 Method

• FoG distinguishes a correct or reached answer from a supported answer, which requires retrieved triples to support the gold answer.Each training question carries gold supporting triples.Source: §3 · p. 3

3.1 Evidence-Grounded Synthesis

• Backward expansion replaces explicit non-answer entities with sub-questions, accumulating supporting triples while preserving the answer and producing 1- to 3-hop questions.Synthesized questions also undergo executability and non-redundancy checks.Source: §3.1 · pp. 3–4

3.2 KG Interaction Agent

• The KG interaction agent uses a multi-turn think–act–observe loop, and its trajectory records the triples returned by KG queries.Its query actions probe relations, expand to neighboring entities, filter entity sets, and combine entity sets.Source: §3.2 · pp. 4–5

3.3 Evidence-Coverage Process Reward

• Outcome rewards credit correct and reached answers, while step-validity rewards successful, correctly formatted actions; neither outcome term checks whether all supporting triples were retrieved.A shortcut can earn full outcome reward despite leaving some gold supporting triples unretrieved.Source: §3.3 · p. 5
• ECPR scores retrieved triples against the gold supporting set and assigns each triple’s credit to the turn that first retrieves it.Repeated retrieval of the same triple earns no additional reward; Proposition 2 states that ECPR is maximized only by supported answers and rewards each triple once.Source: §3.3 · p. 5
• The composite trajectory reward adds outcome, step-validity, and evidence-coverage rewards.The policy is initialized with supervised fine-tuning on teacher demonstrations, then optimized with GRPO using per-turn advantages.Source: §3.3 · p. 5

4. Experiments

• The evaluation covers three Wikidata-based benchmarks, uses answer-accuracy and evidence-coverage metrics, and compares FoG with LLM-reasoning, retrieval-based, and agent-based baselines.Retrieval-based methods are omitted from QALD10-en because its training split has only 387 examples.Source: §4 · p. 5, §4.1 · pp. 5–6

4.2 Main Results (RQ1)

• FoG achieves the best F1 and Hit@1 on all three benchmarks, exceeding KG-R1 by up to +3.73 F1 and +3.92 Hit@1; FoG-3B also exceeds 4B KG-R1 across all three.FoG-4B surpasses GPT-4o-mini agents by at least +7.58 F1 and 7B retrieval-based methods by at least +4.39 F1.Source: Table 1 · p. 6, §4.2 · p. 6

4.3 Ablation Study (RQ2)

• Removing Recpr causes larger drops in Cov than Hit@1, while removing Rstep reduces Hit@1 by 0.45 and 2.35 and Cov by 1.09 and 1.43.Full FoG gains +6.83 and +4.33 Hit@1 over SFT only; RL without Recpr raises Cov by only +2.28 and +1.58. The LLM-as-judge variant remains 4.22 and 5.28 Cov below ECPR.Source: Table 2 · p. 6, §4.3 · p. 7

4.4 Evidence-Grounded Synthesis (RQ3)

• Every retained synthetic question’s supporting triples reproduce its answer under SPARQL, and the redundancy check misses a shortcut in only 1.5% of 200 audited questions.Synth-Only exceeds Train-Only by +3.66, +2.50, and +3.06 Hit@1; mixed data performs best, while Hit@1 improves from 3B to 7B (+12.89, +7.52, and +7.36).Source: §4.4 · p. 7, Table 3 · p. 7

4.5 Analysis of KG Interaction Agent (RQ4)

• On GTSQA, PoG reaches the gold answer on only 35.70% of questions despite 39.33 Hit@1, while KG-R1 leaves 45.95% of supporting triples unretrieved.FoG has the highest Cov and RetQ on both benchmarks, with +3.84 and +4.59 Cov over KG-R1, alongside the highest Hit@1; it leads KG-R1 in all 10 structural groups and is best in 9.Source: Table 4 · p. 7, §4.5 · pp. 7–8, Figure 5 · p. 8

4.6 Analysis of ECPR (RQ5)

• First-match attribution achieves the best Hit@1 and Cov; trajectory-level attribution loses 4.35 Cov, while every-match raises duplicate retrieval from 8.6% to 29.4%.During training, rewards rise while KG turns and response length decline.Source: Table 5 · p. 8, §4.6 · p. 8, Figure 6 · p. 8

4.7 Cross-KG Transfer (RQ6)

• On an unseen KG, FoG reaches 77.2 Hit@1, compared with 82.6–85.7 for methods developed on Freebase; RL with ECPR adds +5.6 Hit@1 over SFT only.Freebase-developed methods are reference points, not matched baselines.Source: Table 6 · p. 8, §4.7 · p. 8

• FoG uses the KG as a source of evidence as well as answers, and improves answer accuracy, evidence coverage, and cross-KG transfer across three KGQA benchmarks.Source: §5 · p. 8

Limitations

• Real-world knowledge graphs may be incomplete, outdated, or noisy, so absent or incorrect evidence can still leave an agent failing despite following the intended evidence path.The paper proposes detecting insufficient on-graph evidence and invoking external retrieval when needed.Source: Limitations · p. 9
• FoG relies on Kimi-K2 for question synthesis and trajectory distillation, leaving synthesis dependent on external teacher generation quality despite symbolic filtering.The authors suggest self-play with graph execution and symbolic filtering as a possible replacement for teacher-driven synthesis.Source: Limitations · p. 9
• FoG caps graph interactions at 10 turns, sufficient for the benchmarks’ 1–4-hop questions but potentially inadequate for more open-ended reasoning requiring longer evidence chains.Extending to such settings requires balancing search depth against error accumulation, noisy observations, and sparser rewards.Source: Limitations · p. 9

Ethical Considerations

• The experiments use public encyclopedic KG data without private or user-generated data; three graduate annotators voluntarily audited evidence paths, with no sensitive content or personal data collected.The work involves no crowdsourcing or user study, and its intended traceability supports human verification rather than replacing it.Source: Ethical Considerations · p. 9

A Proofs

• The proofs model a logical form as a conjunctive query and define support by whether the answer appears among its SPARQL results over a triple set.The proofs also use monotonicity: adding triples cannot remove query answers.Source: A Proofs · p. 13

A.1 Proof of Proposition 1

• Backward expansion preserves the seed answer and accumulates triples sufficient to support the expanded logical form, with each expansion hiding one intermediate entity.The proof establishes this from a verified seed through induction; the accumulated triples need not be the only possible supporting set.Source: §A.1 · p. 13

A.2 Proof of Proposition 2

• Under a feasible evidence-covered trajectory with a correct answer and valid actions, maximizing the composite reward requires retrieved triples that support the answer and penalizes shortcut trajectories.Outcome reward alone can give a shortcut trajectory with a correct answer its maximum reward, whereas the composite reward subtracts at least λ_ecpr for incomplete coverage.Source: §A.2 · pp. 13–14
• The guarantee concerns trajectory-reward maximizers, not whether policy optimization reaches them; full coverage is sufficient but not necessary for a supported answer.When no shortcut trajectory exists, outcome-reward and composite-reward maximizers are already evidence-covered.Source: §A.2 · p. 14

B FoG Algorithm Detail

• The shortest-path check misses a shortcut in 1.5% of candidates while using 5.1 rather than 48.6 SPARQL queries per question.The authors report that the approximation reduces query use by 9.5× and is dominated by SPARQL execution.Source: B FoG Algorithm Detail · p. 14

C.3 Synthesis Cost and Retention

• 67.1% of 20,000 sampled seeds are rejected end-to-end; the 6,588 retained questions require 115,184 teacher calls, about 17.5 per question.Backward expansion accounts for three quarters of the teacher calls.Source: §C.3 · pp. 14–15

C.1 Topic Domains

• 39.7% entertainment leads the domain mix, followed by history 12.6%, society 11.4%, geography 9.6%, transportation 6.6%, sports 6.5%, politics 5.7%, and other 7.9%.The synthetic questions span seven named Wikidata domains.Source: §C.1 · p. 14, Figure 7 · p. 15

C.2 Query-Graph Topologies

• 67.6% of the 6,588 retained questions have multi-branch graphs; 35.1%, 40.0%, and 24.9% have 1, 2, and 3 hops.The most frequent types are the three-branch star (1)(1)(1) at 18.38% and the 3-hop chain (3) at 16.48%.Source: §C.2 · p. 14, Table 7 · p. 15

C.4 Data Leakage Check

• The leakage check encodes each question with BGE-M3 and compares every test question with its most similar synthetic question using cosine similarity.Source: §C.4 · p. 15
• All test-question similarities stay below 0.85; none exceed 0.75 on QALD10-en or WikiWebQuestions, and 6 GTSQA questions (0.37%) fall in 0.80–0.85.Source: §C.4 · p. 15

D KG Interaction Operations

• The KG query action comprises seven operations in four categories: relation search, neighborhood expansion, constraint filtering, and set combination.Table 9 lists each operation’s name, description, input parameters, and output.Source: D KG Interaction Operations · p. 15

E Benchmark Datasets

• Four benchmarks cover Wikidata and Freebase: WikiWebQuestions, QALD10-en, and GTSQA use Wikidata, while WebQSP is reserved for cross-KG transfer.WikiWebQuestions contains real-world questions; QALD10-en has 394 expert-written test questions with multi-hop and qualifier constraints; GTSQA includes gold answer subgraphs and query-graph isomorphism labels.Source: E Benchmark Datasets · p. 15
• WikiWebQuestions was ported from WebQuestions and re-annotated with SPARQL queries over Wikidata.Source: E Benchmark Datasets · p. 15
• WebQSP is sourced from Freebase and used only to evaluate zero-shot transfer across knowledge graphs.Source: E Benchmark Datasets · p. 15

F.1 Evaluation Metrics

• Hit@1 measures normalized exact-answer correctness, while token-level F1 measures overlap between predicted and gold answer tokens.Source: §F.1 · pp. 15–16
• Cov measures the fraction of gold supporting triples retrieved, while RetQ checks whether a gold answer appears among KG-query results.Source: §F.1 · p. 16

F.2 Gold Supporting Triples

• For WikiWebQuestions, gold triples are built by enumerating topic-to-answer paths and using an LLM verifier to retain paths supporting all question constraints.GTSQA supplies gold answer subgraphs natively; the WikiWebQuestions gold paths are distinct from synthesis triples used for training supervision.Source: §F.2 · p. 16

F.3 Human Validation of Constructed Paths

• Human review found Fleiss’ κ = 0.91 and 93.0% agreement with the verifier, whose precision was 0.94 and recall was 0.92.The validation sampled 200 paths, split evenly between verifier-accepted and verifier-rejected candidates; Table 10 shows representative rejected paths.Source: §F.3 · pp. 16–17, Table 10 · p. 17

G Baseline Details

• The nine representative baselines span KG-free reasoning, retrieval methods, and KG agents, including IO Prompt, RoG, SubGraphRAG, GCR, ToG, PoG, and KG-R1.IO Prompt answers from parametric knowledge; retrieval and agent baselines use different KG access strategies.Source: G Baseline Details · p. 17
• FoG and KG-R1 use the same Wikidata training data, while RoG, SubGraphRAG, and GCR are retrained on each Wikidata benchmark because their supervision is dataset-specific.All methods use identical evaluation conditions and a single inference run per question, without multi-run aggregation.Source: G Baseline Details · p. 17

H Hyperparameter Settings

• RL samples four trajectories per question with at most ten KG turns; turn-level returns credit process rewards to the turn that receives them.The policy uses KL regularization against the SFT model, and the reward coefficients are listed in Table 13.Source: H Hyperparameter Settings · pp. 17–18, Table 13 · p. 18

I Case Study

• In the case study, FoG retrieves the complete evidence chain in nine KG turns, whereas ToG retrieves one relevant triple and PoG leaves bridge evidence missing.All three methods predict the correct answer, but their trajectories differ in how much of the evidence chain they recover.Source: I Case Study · p. 18, Table 14 · p. 20, Table 15 · p. 21

J.1 Seed Question Generation Prompt

• The seed-generation prompt asks a teacher to produce a question, logical form, and supporting triples from a sampled subgraph.Source: §J.1 · p. 18, Table 17 · p. 22

J.2 Backward Expansion Prompt

• The backward-expansion prompt selects an anchor entity, retrieves its neighborhood, generates a sub-question answered by the anchor, and verifies the result, retrying on failure.Source: §J.2 · p. 18, Table 18 · p. 23

J.3 Trajectory Distillation Prompt

• For SFT distillation, the teacher is instructed to explore only through provided tools and answer with entities appearing in tool responses.Source: §J.3 · p. 19, Table 19 · p. 24

J.4 Agent Prompt

• The FoG agent prompt directs analysis, KG-operation calls, and answers grounded in returned triples.Source: §J.4 · p. 19, Table 20 · p. 25