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

Introduction

Large language models (LLMs) [39, 9, 40, 41, 26] increasingly answer factual questions from parametric knowledge, but remain difficult to trust on questions that require complex factual reasoning [24, 13, 17, 28]. A correct answer is not necessarily a supported one: the model may answer from memory or surface cues while exposing little about why the answer

holds [14, 2, 25], which is problematic in high-stakes settings such as healthcare and law [3], where users need evidence that they can check [32, 1]. Current LLM answers thus lie in a fog: the answer is visible, yet the evidence behind it remains hidden.

Knowledge graphs (KGs) [27] offer a natural way to clear this fog, since they store facts as verifiable triples. Existing KG-augmented methods follow two paradigms (Figure 2). Retrieval-based methods [21, 18, 22] retrieve triples, paths, or sub-graphs and answer from them. Agent-based methods [34, 5, 19, 15] interact with the KG through a multi-turn “think–act–observe” process, and recent work trains them with reinforcement learning (RL) [19, 6] [33] (Sun et al. 2025).

However, existing KG agents treat the KG only as a source of answers and overlook its role as a source of evidence. An LLM with no KG access can already answer many benchmark questions correctly, and even an RL-trained agent can answer correctly while retrieving only part of the supporting triples. We identify two causes. First, training data carries answers but not evidence: most KGQA datasets annotate answers and at most logical forms [38, 52] (Gu et al. 2021), and recovering the supporting triples afterwards requires enumerating and verifying paths for every question. Second, training rewards check the answer but not the evidence: most rewards score only the final answer or whether the KG returns it [19, 31, 47, 6] (Sun et al. 2025), so a trajectory that reaches the answer through part of the evidence earns as much as one that retrieves all of it. The process rewards that go further depend on an LLM judge or on gold paths recovered for every question [43, 49], both of which are costly. Both causes trace back to one bottleneck: evidence is expensive to recover once a question has been written.

To remove this bottleneck, we propose FoG (Figure 1), a framework that trains KG agents to retrieve the evidence behind their answers. Our key observation is that evidence is hard to recover after a question is written but can be embedded when the question is constructed and then rewarded during training. First, evidence-grounded synthesis recursively hides the explicit entities of a seed question behind verifiable sub-questions, so every question carries its supporting triples. Second, a KG interaction agent answers through multi-turn KG queries and records every triple that the KG returns. Lastly, during RL training, an evidence-coverage process reward (ECPR) gives a dense reward to each turn that first retrieves one of these supporting triples. Our contributions are as follows:

• We distinguish two roles of the KG and show that existing training data and rewards serve it only as a source of answers, not of evidence.

• We propose FoG, which embeds supporting triples into synthetic questions and rewards their retrieval through ECPR, so the dense reward comes from data synthesis with no LLM judge or extra annotation.

• On three benchmarks, 3B–4B FoG agents outperform larger baselines in accuracy and evidence coverage, and transfer zero-shot across KGs.

Related Work

Knowledge graph augmented reasoning. Unlike prompting strategies [46, 45, 50, 16], KG-augmented methods ground reasoning in verifiable triples and follow two paradigms. Retrieval-based methods [21, 18, 22, 23, 12, 20] condition the LLM on triples, paths, or subgraphs retrieved in a single step. Agent-based methods [34, 5, 19, 15] explore the KG iteratively: ToG and PoG prompt a frozen LLM, whereas recent work trains the agent with RL [19, 31, 6, 44, 33] (Sun et al. 2025). However, these agents use the KG only as a source of answers and can answer correctly without retrieving the supporting triples. In this work, we train agents to use it as a source of evidence.

Synthetic data for KGQA. Synthetic data frees KGQA from human annotation, since questions can be generated from the KG and verified by execution. It provides questions for agent training [47] and for benchmarking and retriever training [53, 4]. However, these pipelines treat it as extra examples to train or evaluate on. In this work, we treat it as a source of supervision: every synthesized question carries the evidence that defines its reward.

Rewards for KG agents. RL lets a KG agent learn its retrieval policy from interaction with the KG. Most work trains from outcome rewards on the final answer with rule-based terms for valid interaction [19, 31, 6, 44, 33, 35] (Sun et al. 2025). Because outcome rewards are sparse, later work adds dense process rewards, obtained from an LLM judge [43] or from gold paths and logical forms [49, 11, 37]. However, both sources are costly: a judge must score every rollout, and gold references must be annotated or recovered for every question. In this work, the process reward comes from data synthesis: every synthesized question already carries its supporting triples, which provide a dense reward at no extra cost.

Method

In this section, we introduce FoG, as shown in Figure 3, including evidence-grounded synthesis, a KG interaction agent, and ECPR.

Evidence-Grounded Synthesis

Seed question construction

To obtain complex questions that carry their supporting evidence, we propose evidence-grounded synthesis that includes seed question construction, backward expansion, and quality control. All roles use the teacher Kimi-K2 [39].

Seed question construction. We sample a size-bounded subgraph $\mathcal{G}_{\mathrm{sub}}$ from Wikidata around a seed entity $v_{\mathrm{seed}}$ of moderate degree. The teacher generates a 1-hop question whose answer is $v_{\mathrm{seed}}$:

where $\pi_{\mathrm{gen}}$ is the teacher model, $Q^{(1)}$ the seed question, $\ell^{(1)}$ its logical form, and $\mathcal{S}^{(1)}$ its supporting triples. The seed is retained only if every triple in $\mathcal{S}^{(1)}$ exists in $\mathcal{G}_{\mathrm{sub}}$ and $\ell^{(1)}$ executes over the global KG with $v_{\mathrm{seed}}$ in its result set.

Backward expansion. Given a verified question $Q^{(n)}$ with logical form $\ell^{(n)}$, answer $y=v_{\mathrm{seed}}$, and supporting triples $\mathcal{S}^{(n)}$, we replace an explicit non-answer entity $u$ in $Q^{(n)}$ with a sub-question $\widetilde{Q}$ whose answer is exactly $u$:

where $\widetilde{\mathcal{S}}$ are the supporting triples of $\widetilde{Q}$, drawn from the incoming neighborhood of $u$, and $\ell^{(n+1)}$ is the expanded logical form. Each expansion turns an explicit entity into a hidden intermediate variable, and the accumulated triples still support the answer. Thus $N \in\{0, 1, 2\}$ expansions yield 1- to 3-hop questions, where $N = 0$ keeps the seed. Expansion uses a ReAct agent (Yao et al. [51]) that retrieves the neighborhood of $u$, selects triples, writes $\widetilde{Q}$, and verifies it; on failure, it reselects triples or the entity.

Proposition 1. Backward expansion preserves the answer and yields triples that support it.

Proof. We provide experimental results in § 4.4 and proofs in Appendix § 8.§ 1.

Quality control. Each synthesized question must further pass two symbolic checks, which keep the answer specific and every topic entity necessary.

(a) Executability. Let $\mathcal{Y}^{(n)} = \operatorname{SPARQL}(\ell^{(n)},\mathcal{T})$ be the result set of the candidate question. We retain it only if the target answer is included and the result set is not overly broad, i.e., $y \in\mathcal{Y}^{(n)}$ and

for a maximum answer-set size $K_{\mathrm{ans}}$.

KG Interaction Agent

To make the evidence retrieved for an answer explicit, we develop a KG interaction agent that solves each question through a multi-turn think–act–observe loop with the action space

where think performs internal reasoning, kg-query interacts with the KG, and answer emits the final prediction. The kg-query action is instantiated with seven atomic operations that probe the relations of an entity, expand to its

(b) Non-redundancy. Let $E_q$ be the topic entities of the question. We extract a shortest supporting path for each $e \in E_q$ and discard the question if a proper subset yields an equally specific answer set:

where $\mathcal{Y}^{(n)}_Z$ is the answer set of the query built only from the paths of $Z$ (Appendix § 9).

The triples accumulated for a final question $q$ are its gold supporting triples $\mathcal{S}^*_{q}$, and we report the distribution of query-graph types (Dutt et al. [8]) in Appendix § 10.§ 2. neighboring entities, filter an entity set, and combine entity sets (Appendix § 11). Every trajectory thus records the returned triples $\mathcal{T}(\tau)$, the only evidence that FoG rewards and evaluates.

Evidence-Coverage Process Reward

To train the agent to retrieve this evidence, we propose a training scheme with outcome and step-validity rewards, the evidence-coverage process reward, and turn-level policy optimization.

Outcome and step-validity rewards. We define the outcome reward of a trajectory as

where the first term rewards a correct answer and the second a reached answer. Neither term checks whether the answer is supported: a shortcut trajectory, which outputs and even reaches the gold answer while leaving some of the supporting triples $S_q^*$ unretrieved, still earns the full outcome reward.

To stabilize graph interaction, each turn also earns a step-validity reward $r_t^{\mathrm{step}}=\lambda_{\mathrm{step}}v_t$, where $v_t=1$ if action $a_t$ follows the required format and executes successfully, and $v_t=0$ otherwise. The trajectory-level term is the average

Evidence-coverage process reward. Unlike the terms above, which treat the KG only as a source of answers, the Evidence-Coverage Process Reward (ECPR) scores the trajectory against the gold supporting triples $S_q^*$ provided by synthesis. We define the evidence coverage of a trajectory as

where $\mathcal{T}(\tau)$ are all triples retrieved along $\tau$, so a triple that the agent recalls from memory without retrieving it earns no reward. We call $\tau$ evidence-covered if $\operatorname{Cov}(\tau,S_q^*)=1$, and set $R_{\mathrm{ecpr}}(\tau)=\lambda_{\mathrm{ecpr}}\cdot\operatorname{Cov}(\tau,S_q^*)$. For dense credit assignment, first-match attribution assigns each gold triple to the step that first retrieves it:

where $\sum_t r_t^{\mathrm{ecpr}}=R_{\mathrm{ecpr}}(\tau)$, so repeated retrieval of the same triple earns no additional reward. The composite reward of a trajectory is $R(\tau)=R_{\mathrm{out}}(\tau)+R_{\mathrm{step}}(\tau)+R_{\mathrm{ecpr}}(\tau)$. We set $\lambda_{\mathrm{f1}}=0.7$, $\lambda_{\mathrm{ret}}=0.3$, $\lambda_{\mathrm{step}}=0.5$, and $\lambda_{\mathrm{ecpr}}=1$.

Proof. We provide experimental results in § 4.3 and § 4.6 and proofs in Appendix § 8.§ 2.

Turn-level policy optimization. Following prior RL-trained KG agents (Song et al., [31]; Chen et al., [6]; Sun et al., 2025), the policy $\pi_\theta$ is first initialized by supervised fine-tuning (SFT) on demonstration trajectories that a teacher model produces for the synthesized and training questions, minimizing the negative log-likelihood of the teacher actions. We then optimize it with Group Relative Policy Optimization (GRPO) (Shao et al., [29]) and, following KG-R1 (Lin et al., [19]), compute the advantage per turn. For each question $q$, the policy samples $N$ trajectories $\{\tau_i\}_{i=1}^{N}$, and turn $t$ of $\tau_i$ receives the return

i.e., the shared outcome reward plus the process rewards earned by this turn. The advantage $\hat{A}_{i,t}=(G_{i,t}-\mu_q)/(\sigma_q+\delta)$ is normalized with the mean $\mu_q$ and standard deviation $\sigma_q$ of the returns over all turns of the $N$ trajectories. A turn that first retrieves gold evidence therefore receives a higher advantage than the other turns. The policy then maximizes the clipped GRPO objective with these advantages, regularized toward the SFT model (Appendix § 15).

Experiments

This section presents the experimental setup, main results, and analysis. We answer the following research questions (RQs): RQ1: Does FoG outperform other methods in answer accuracy? RQ2: Does each component of FoG work? RQ3: Does evidence-grounded synthesis provide valid evidence and better training data? RQ4: Does the KG interaction agent retrieve the evidence behind its answers? RQ5: How does the design of ECPR affect evidence coverage? RQ6: Does FoG transfer to a KG unseen during training?

Experimental Setup

Datasets. We evaluate on three Wikidata-based KGQA benchmarks, WikiWebQuestions (Xu et al., [48]), QALD10-en (Usbeck et al., [42]), and GT-SQA (Cattaneo et al., [4]), and use WebQSP (Yih et al., [52]) over Freebase for cross-KG transfer. The synthetic questions do not overlap with the test sets (Appendices § 10.§ 4 and § 12).

Category	Methods	Backbone	WikiWebQuestions F1	WikiWebQuestions Hit@1	QALD10-en F1	QALD10-en Hit@1	GTSQA F1	GTSQA Hit@1
LLM Reasoning	IO Prompt ([40])	Qwen2.5-7B-Instruct	28.24	44.43	11.05	12.30	9.62	10.23
LLM Reasoning	IO Prompt ([26])	GPT-4o-mini	40.31	68.10	15.34	18.78	15.37	16.46
LLM Reasoning	CoT ([46])	GPT-4o-mini	41.66	58.42	22.68	26.81	18.87	20.12
LLM Reasoning	Self-Consistency ([45])	GPT-4o-mini	46.34	65.20	24.27	28.57	19.07	20.21
LLM Reasoning	IO Prompt ([7])	DeepSeek-V3	42.36	59.89	18.97	21.77	24.77	26.20
LLM Reasoning	CoT ([46])	DeepSeek-V3	45.91	64.60	19.02	25.28	27.66	29.41
LLM Reasoning	Self-Consistency ([45])	DeepSeek-V3	49.72	66.79	26.25	29.97	33.59	35.82
Retrieval-based	RoG ([21])	Qwen2.5-7B-Instruct	53.27	68.71	–	–	41.10	42.48
Retrieval-based	SubGraphRAG-100 ([18])	Qwen2.5-7B-Instruct	56.84	72.36	–	–	44.27	45.93
Retrieval-based	GCR ([22])	GPT-4o-mini	55.33	71.27	–	–	32.61	37.48
Agent-based	ToG ([34])	GPT-4o-mini	58.55	72.75	30.63	32.18	41.08	42.36
Agent-based	PoG ([5])	GPT-4o-mini	57.32	71.89	30.68	34.07	37.77	39.33
Agent-based	KG-R1 ([19])	Qwen3-4B-Instruct	64.49	73.01	44.07	45.41	46.14	47.73
Agent-based	FoG-3B	Qwen2.5-3B-Instruct	66.28	75.43	45.63	48.92	48.25	49.20
Agent-based	FoG-4B	Qwen3-4B-Instruct	66.41	76.93	47.80	49.01	48.66	50.52

Baselines. We compare FoG against LLM reasoning (IO Prompt, CoT ([46]), Self-Consistency ([45])), retrieval-based (RoG ([21]), SubGraphRAG ([18]), GCR ([22])), and agent-based (ToG ([34]), PoG ([5]), KG-R1 ([19])) methods. Retrieval-based methods require dataset-specific fine-tuning and are omitted from QALD10-en, whose training split has only 387 examples (Appendix § 14).

Evaluation Metrics. We report Hit@1 and token-level F1 for answer accuracy. For evidence coverage, we report Cov, the fraction of gold supporting triples retrieved along the trajectory, and RetQ, the fraction of questions whose gold answer is returned by a KG query. GTSQA provides gold supporting triples natively, and we construct them for WikiWebQuestions with an LLM verifier that agrees with human annotators on 93.0% of 200 audited paths (Appendices § 13.§ 1, § 13.§ 2, and § 13.§ 3).

Implementation Details. We train FoG on Qwen2.5-3B-Instruct and Qwen3-4B-Instruct with LoRA-based SFT followed by GRPO, sampling $N=4$ trajectories of at most 10 KG turns per question for 450 steps. All methods are evaluated with a single inference run per question (Appendix § 15).

Main Results (RQ1)

As shown in Table 1, we compare FoG with all baselines in answer accuracy.

Comparison across methods. FoG achieves the best F1 and Hit@1 on all three benchmarks, exceeding the strongest baseline KG-R1 by up to +3.73 F1 and +3.92 Hit@1. As KG-R1 is also RL-trained on the same Qwen3-4B backbone, this indicates that training an agent to retrieve evidence also makes its answers more accurate.

Comparison across backbones. FoG-3B still exceeds the 4B KG-R1 on all three benchmarks, and FoG-4B surpasses GPT-4o-mini agents by at least +7.58 F1 and 7B retrieval-based methods by at least +4.39 F1. This suggests that how an agent is trained to retrieve matters more than its backbone size.

Ablation Study (RQ2)

As shown in Table 2, we ablate the training stages and reward terms on the two benchmarks with gold supporting triples, under the same backbone, SFT checkpoint, RL data, and rollout budget, so the variants differ only in the reward.

Variants	WikiWebQuestions F1	WikiWebQuestions Hit@1	WikiWebQuestions RetQ	WikiWebQuestions Cov	GTSQA F1	GTSQA Hit@1	GTSQA RetQ	GTSQA Cov
SFT only	$59.95\pm0.18$	$70.10\pm0.24$	$79.42\pm0.31$	$70.63\pm0.29$	$44.73\pm0.22$	$46.19\pm0.27$	$58.47\pm0.33$	$49.85\pm0.30$
SFT + RL w/o $R_{\mathrm{ecpr}}$	$63.87\pm0.44$	$74.35\pm0.53$	$83.17\pm0.49$	$72.91\pm0.56$	$46.02\pm0.49$	$46.97\pm0.56$	$61.02\pm0.52$	$51.43\pm0.58$
SFT + RL w/o $R_{\mathrm{step}}$	$65.02\pm0.33$	$76.48\pm0.40$	$85.62\pm0.38$	$77.25\pm0.42$	$47.96\pm0.39$	$48.17\pm0.47$	$63.18\pm0.44$	$57.21\pm0.46$
SFT + RL, $R_{\mathrm{ecpr}}\to$ LLM-as-judge	$64.95\pm0.39$	$75.41\pm0.51$	$84.03\pm0.45$	$74.12\pm0.50$	$46.88\pm0.43$	$48.25\pm0.52$	$62.24\pm0.48$	$53.36\pm0.51$
SFT + RL (full FoG)	$66.41\pm0.27$	$76.93\pm0.38$	$86.35\pm0.35$	$78.34\pm0.37$	$48.66\pm0.34$	$50.52\pm0.41$	$65.34\pm0.39$	$58.64\pm0.40$

Impact of RL. Full FoG improves over SFT only by +6.83 and +4.33 Hit@1, but RL without $R_{\mathrm{ecpr}}$ raises Cov by only +2.28 and +1.58. This is because the outcome reward is paid in full once the answer is reached, whatever evidence is retrieved.

Impact of $R_{\mathrm{ecpr}}$. Removing $R_{\mathrm{ecpr}}$ causes the largest drop among the reward terms, and Cov drops more (5.43 and 7.21) than Hit@1 (2.58 and 3.55). As both variants share the data and the SFT checkpoint, this confirms that the coverage gain comes from the reward itself.

Impact of $R_{\mathrm{step}}$. Removing $R_{\mathrm{step}}$ lowers Hit@1 by 0.45 and 2.35 but Cov by only 1.09 and 1.43, indicating that step validity keeps the interaction executable but does not drive coverage.

ECPR vs. LLM-as-judge. An LLM-as-judge score of the reasoning process (Wang and Yu [43]) raises Cov by only 1.21 and 1.93 over no process supervision and stays 4.22 and 5.28 below ECPR. This suggests that judging how plausible the reasoning reads is a weaker signal than ECPR.

Evidence-Grounded Synthesis (RQ3)

As shown in Table 3 and Figure 4, we fix a budget of 6,588 SFT questions and vary the data source (Train-Only, Synth-Only, or a mix of both), and apply the same SFT data to three backbone scales.

Data Source	WikiWebQuestions	WikiWebQuestions	QALD10-en	QALD10-en	GTSQA	GTSQA
	F1	Hit@1	F1	Hit@1	F1	Hit@1
Train-Only	53.58	64.51	36.94	37.86	41.33	41.52
Synth-Only	57.84	68.17	39.52	40.36	43.21	44.58
Mixed	59.95	70.10	41.38	42.31	44.73	46.19

Validity of embedded evidence. The supporting triples of every retained question reproduce its answer under SPARQL execution, and the redundancy check misses a shortcut in only 1.5% of 200 audited questions. This confirms that the embedded triples are a valid reward target without annotation.

Synthetic vs. original data. Synth-Only outperforms Train-Only by +3.66, +2.50, and +3.06 Hit@1 with no in-domain question, indicating that questions built by backward expansion transfer to human-written benchmarks. Mixed performs best, so the two sources are complementary (Appendix § 10.§ 3).

Performance across model scales. Hit@1 improves steadily from 3B to 7B (+12.89, +7.52, and +7.36), indicating that the synthetic data is not backbone-specific.

Analysis of KG Interaction Agent (RQ4)

As shown in Table 4 and Figure 5, we examine how much evidence agent-based methods retrieve.

Methods	WikiWebQuestions	WikiWebQuestions	WikiWebQuestions	GTSQA	GTSQA	GTSQA
	Hit@1	RetQ	Cov	Hit@1	RetQ	Cov
PoG	71.89	75.66	69.85	39.33	35.70	25.38
ToG	72.75	73.53	68.79	42.36	50.99	37.34
KG-R1	73.01	82.28	74.50	47.73	61.41	54.05
FoG-4B	76.93	86.35	78.34	50.52	65.34	58.64

Answers without evidence. On GTSQA, PoG attains 39.33 Hit@1 but reaches the gold answer on only 35.70% of questions, so at least 9.2% of its correct answers never appear in any KG observation, and the RL-trained KG-R1 still leaves 45.95% of the supporting triples unretrieved. Neither prompting nor outcome rewards thus make an agent use the KG as a source of evidence.

Evidence coverage. FoG attains the highest Cov and RetQ on both benchmarks (+3.84 and +4.59 Cov over KG-R1) together with the highest Hit@1, indicating that evidence coverage does not come at the cost of answer accuracy (Appendix § 16).

Performance under structural complexity. FoG leads KG-R1 on all 10 groups and is the best method on 9. Its margin over KG-R1 grows from +1.4 Hit@1 on (1) to +5.0 on (3) and +6.0 on the more branched (3)(1), questions that depend on more supporting triples. This suggests that the more evidence an answer requires, the more the agent benefits from rewards for retrieving it, although the margin narrows to +2.0 on (4).

Analysis of ECPR (RQ5)

As shown in Table 5 and Figure 6, we compare first-match with trajectory-level attribution, which credits coverage to the final turn, and every-match attribution, which rewards every retrieval.

Credit assignment	Hit@1	Cov	Dup. rate
Trajectory-level	46.69	54.29	11.8%
Every-match	47.01	52.21	29.4%
First-match (ours)	50.52	58.64	8.6%

Comparison across attribution strategies. First-match achieves the best Hit@1 and Cov. Trajectory-level attribution loses 4.35 Cov, as turns that retrieve evidence earn the same return as the others. Every-match raises the duplicate-retrieval rate from 8.6% to 29.4% and falls below trajectory-level in Cov, as it rewards re-querying known evidence. This indicates that dense credit must pay each triple once, or it rewards redundant retrieval rather than coverage.

Training dynamics. Rewards rise during RL while KG turns and response length decline, indicating that the agent learns a precise retrieval policy that covers more evidence with fewer queries.

Cross-KG Transfer (RQ6)

As shown in Table 6, we evaluate the frozen FoG zero-shot on WebQSP over a Freebase backend.

Method	Train KG	Backbone	WebQSP train	WebQSP Hit@1
ToG ([34])	None	GPT-4	No	82.6
RoG ([21])	Freebase	LLaMA2-Chat-7B	Yes	85.7
KG-R1 ([19])	Freebase	Qwen2.5-3B-Instruct	Yes	82.8
FoG SFT-only	Wikidata	Qwen3-4B-Instruct	No	71.6
FoG full	Wikidata	Qwen3-4B-Instruct	No	77.2

Zero-shot transfer. FoG reaches 77.2 Hit@1 on an unseen KG, close to the methods developed on Freebase (82.6–85.7), and RL with ECPR contributes +5.6 Hit@1 over SFT only. This suggests that ECPR teaches the habit of retrieving evidence before answering, not the relations of one schema.

Conclusion

In this work, we present FoG, a framework that trains KG agents to retrieve the evidence behind their answers. By introducing evidence-grounded synthesis, a KG interaction agent, and an evidence-coverage process reward, FoG uses the KG as a source of evidence rather than only as a source of answers. Experiments on three KGQA benchmarks demonstrate consistent improvements in answer accuracy, evidence coverage, and cross-KG transfer.

Limitations

KG completeness and freshness. FoG uses Wikidata triples as verifiable references for evidence-covered supervision, but real-world knowledge graphs may be incomplete, outdated, or noisy. When the required evidence is absent or incorrect in the graph, the agent may still fail despite following the intended evidence path. A natural extension is to equip the agent with a mechanism for detecting insufficient on-graph evidence and invoking external retrieval when needed.

Dependence on teacher models. Like other KG agents distilled from teacher trajectories [6, 33], FoG currently relies on an external teacher LLM (Kimi-K2) for question synthesis and trajectory distillation. Although symbolic checks filter invalid questions and evidence paths, the synthesis process still depends on the generation quality of external teachers. One promising direction is to replace teacher-driven synthesis with self-play, where agents generate, explore, and verify candidate questions through graph execution and symbolic filtering.

Long-horizon graph interaction. FoG caps graph interactions at 10 turns, which is sufficient for the 1–4-hop questions studied in our benchmarks. More open-ended KG reasoning may require longer evidence chains and broader graph exploration. Extending FoG to such settings requires balancing search depth against error accumulation, noisy observations, and sparser rewards.

Ethical Considerations

All experiments use publicly available KGQA datasets derived from Wikidata (CC0), QALD10-en (MIT License), and WikiWebQuestions, GTSQA, and WebQSP (publicly available for research). Backbone models Qwen2.5 and Qwen3 are released under Apache 2.0; GPT-4o-mini, DeepSeek-V3, and the teacher Kimi-K2 are accessed via official APIs under their terms of service. Our use of all existing artifacts is consistent with their intended research purposes. The datasets contain only public encyclopedic facts from structured KG triples, with no private or user-generated data. The only human involvement is the audit of constructed evidence paths (Appendix § 13.§ 3), in which three graduate annotators judged whether a KG path supports its question. The annotators took part voluntarily, the task exposed them to no sensitive content, and no personal data was collected. This work involves no crowdsourcing and no user study. FoG is intended to make the answers of KG agents traceable to retrieved evidence. Since the KG may be outdated or incorrect, this evidence supports human verification rather than replaces it. We foresee no dual-use concerns.

Proofs

Throughout the proofs, a logical form $\ell$ is a conjunctive query: a set of triple patterns over entities and variables with one answer variable, optionally with filters on bound values. For a triple set $S$, SPARQL$(\ell,S)$ is the set of values of the answer variable over all assignments that map every pattern of $\ell$ to a triple in $S$ and satisfy the filters. Such queries are monotone: $S \subseteq S'$ implies $\operatorname{SPARQL}(\ell,S) \subseteq\operatorname{SPARQL}(\ell,S')$. Following Definition 2, $S$ supports $(\ell,y)$ if $y \in\operatorname{SPARQL}(\ell,S)$, and a trajectory $\tau$ is evidence-covered if $\operatorname{Cov}(\tau,S_q^*) = 1$, as defined in Equation (6).

Proof of Proposition 1

Proposition 1. Backward expansion preserves the answer and yields triples that support it.

Proof. We show by induction that, for every $n \ge1$, the triple set $S^{(n)} \subseteq T$ supports $(\ell^{(n)},y)$.

Base case. A seed is retained only if its supporting triples exist in the KG and instantiate $\ell^{(1)}$ with the answer variable bound to $y$. Hence $S^{(1)}$ supports $(\ell^{(1)},y)$ under some assignment $\mu$.

Inductive step. Assume that $S^{(n)}$ supports $(\ell^{(n)},y)$ under an assignment $\mu$. An expansion selects an entity $u$ in $\ell^{(n)}$ and a verified sub-question with logical form $\tilde{\ell}$, answer variable $x$, and triples $\tilde{S} \subseteq T$ that support $(\tilde{\ell},u)$ under an assignment $\tilde{\mu}$ with $\tilde{\mu}(x)=u$. With variables renamed apart, the expanded logical form is

where $[u \mapsto x]$ replaces every occurrence of $u$ with the variable $x$. Consider the assignment $\mu\cup\tilde{\mu}$. Every pattern of $\tilde{\ell}$ is mapped into $\tilde{S}$, and every pattern of $\ell^{(n)}[u \mapsto x]$ is mapped to the same triple of $S^{(n)}$ as under $\mu$, since $\tilde{\mu}(x)=u$. The answer variable is still bound to $y$, which gives

where $S^{(n+1)} = S^{(n)} \cup\tilde{S}$, so $S^{(n+1)}$ supports $(\ell^{(n+1)},y)$. Since $S^{(n+1)} \subseteq T$, monotonicity also gives $y \in\operatorname{SPARQL}(\ell^{(n+1)},T)$, so the answer is preserved over the full KG. Each expansion replaces one entity with a variable, so $N$ expansions hide $N$ intermediate entities.

The proof guarantees that the accumulated triples are sufficient for the answer, not that they are the only triples that support it. In the special case where the sub-question has answers other than $u$, the result set of $\ell^{(n+1)}$ may grow, but the executability check bounds it by $K_{\mathrm{ans}}$.

In conclusion, every expansion keeps $y$ in the result set over the full KG, and the accumulated triples alone support the expanded logical form. Therefore, backward expansion preserves the answer and yields triples that support it.

Proof of Proposition 2

Proposition 2. ECPR is maximized only by supported answers and rewards each triple once.

Proof. Let $R = R_{\mathrm{out}} + R_{\mathrm{step}} + R_{\mathrm{ecpr}}$ be the composite reward with $\lambda_{\mathrm{ecpr}} > 0$, and let $S_q^*$ be the supporting triples of a question $q$, which support $(\ell_q,y_q^*)$ by Proposition 1.

Supported maximizers. Since $F1 \le1$, $R_{\mathrm{step}} \le\lambda_{\mathrm{step}}$, and $\operatorname{Cov} \le1$, the composite reward is bounded as

where equality holds if and only if every term attains its maximum, in particular only if $\operatorname{Cov}(\tau,S_q^*)=1$. Assume that an evidence-covered trajectory with a correct answer and only valid actions is feasible within the turn limit. The bound is then attained, so every trajectory $\tau$ that maximizes $R$ satisfies $S_q^* \subseteq T(\tau)$, and monotonicity gives

which means that the answer of $\tau$ is supported.

For outcome rewards alone, $R_{\mathrm{out}}$ in Equation (5) depends on $\tau$ only through the prediction $\hat{y}$ and the returned entities $\mathcal{E}(\tau)$. A shortcut trajectory $\tau_s$ that predicts and reaches $y_q^*$ with $\operatorname{Cov}(\tau_s,S_q^*) < 1$ therefore attains the maximum $\lambda_{\mathrm{f1}}+\lambda_{\mathrm{ret}}$ of $R_{\mathrm{out}}$. Under the composite reward, it loses at least $\lambda_{\mathrm{ecpr}}(1-\operatorname{Cov}(\tau_s,S_q^*)) > 0$ against the bound and is no longer optimal.

One reward per triple. Let $U_t = \left(\bigcup_{i \le t} \mathcal{T}_i\right) \cap S_q^*$ be the gold triples retrieved up to step $t$, with $U_0 = \varnothing$. The step reward of ECPR is then

where $U_{t-1} \subseteq U_t$, so $r_t^{\mathrm{ecpr}} \ge0$ and the sum over steps telescopes to $\lambda_{\mathrm{ecpr}}\lvert U_T\rvert/\lvert S_q^*\rvert= R_{\mathrm{ecpr}}(\tau)$. If step $t$ returns only triples that were already retrieved, then $U_t=U_{t-1}$ and $r_t^{\mathrm{ecpr}}=0$. In contrast, every-match attribution pays $\lambda_{\mathrm{ecpr}}\lvert T_t \cap S_q^*\rvert/\lvert S_q^*\rvert$ at each step. Repeating a query that returns $m \ge1$ gold triples for $T$ steps thus earns $\lambda_{\mathrm{ecpr}}Tm/|S_q^*|$, which grows with $T$ while the coverage stays at $m/|S_q^*|$.

The statement concerns the maximizers of the trajectory-level reward and does not guarantee that policy optimization reaches them. Covering $S_q^*$ is sufficient but not necessary for a supported answer, since a question may admit other supporting sets. In the special case where no shortcut trajectory exists for the question, the maximizers of $R_{\mathrm{out}}$ are already evidence-covered, so the two rewards share the same maximizers.

In conclusion, the composite reward attains its maximum only when the retrieved triples support the answer, and first-match attribution never pays a triple twice. Therefore, ECPR is maximized only by supported answers and rewards each triple once.

FoG Algorithm Detail

Redundancy Check. To provide a clear overview of the non-redundancy check in § 3.1, we present its procedure in the form of pseudocode. As shown in Algorithm 1, we first build a support graph from the supporting triples and extract the shortest path from each topic entity to the answer node. We then enumerate proper subsets of topic entities in increasing size and execute one SPARQL query per subset. If any subset yields an answer set no larger than that of the full query, the question admits a shortcut and is discarded.

Complexity Analysis. Given a question with $|E_q|$ topic entities and $|S^{(n)}|$ supporting triples, extracting the shortest paths by BFS takes $O(|E_q|\cdot|S^{(n)}|)$ time. The subset enumeration issues at most $2^{|E_q|}-2$ SPARQL queries and stops at the first redundant subset. Using only the shortest path per topic entity is an approximation, which we audit on 200 candidate questions against an exhaustive enumeration of all path combinations under the same hop limit. The shortest-path check misses a shortcut in 1.5% of the candidates, while issuing 5.1 rather than 48.6 SPARQL queries per question.

In summary, the redundancy check is dominated by SPARQL execution, and the shortest-path approximation reduces the number of queries by $9.5\times$ while missing few shortcuts.

Algorithm 1: Redundancy Check

Input: $S^{(n)}$: supporting triples; $E_q$: topic entities; $Y^{(n)}$: full answer set.

Output: Redundancy flag $\mathrm{IsRedundant} \in\{\mathrm{True},\mathrm{False}\}$.

Build an undirected graph $G$ from $S^{(n)}$; label topic-entity nodes with their Wikidata IDs, the answer node with ?answer, and intermediates with fresh variables.

for each $e \in E_q$ do

Compute shortest path $P(e)$ in $G$ from $e$ to the answer node.

Derive SPARQL triple pattern $\phi(e)$ from triples along $P(e)$.

end

for $k=1$ to $|E_q|-1$ do

for each $Z \subseteq E_q$ with $|Z|=k$ do

$Q_Z \gets$ SELECT; ?answer; WHERE; $\{\bigcup_{e\in Z}\phi(e)\}$

Execute $Q_Z$ on the KG $\to$ answer set $\mathcal{Y}^{(n)}_Z$.

if $|\mathcal{Y}^{(n)}_Z| \le|\mathcal{Y}^{(n)}|$ then

return True

end

end

end

return False

Synthetic Data Construction

Topic Domains

As shown in Figure 7, the synthetic questions used for FoG training span seven named Wikidata domains. Entertainment is the largest (39.7%), reflecting the density of film, television, and music entities in Wikidata, followed by history (12.6%), society (11.4%), geography (9.6%), transportation (6.6%), sports (6.5%), and politics (5.7%); the remaining 7.9% fall into other domains.

Query-Graph Topologies

To construct questions with diverse reasoning structures, we label each synthetic question with the isomorphism type of its query graph. As shown in Table 7, the 6,588 questions that pass all checks span nine chain and tree structures from 1 to 3 hops. All verified seeds enter backward expansion, and the 1-hop questions are seeds retained at depth one. Overall, 35.1%, 40.0%, and 24.9% of the questions have 1, 2, and 3 hops. The most frequent types are the three-branch star (1)(1)(1) (18.38%) and the 3-hop chain (3) (16.48%), and 67.6% of the questions have a multi-branch query graph rather than a single chain.

Hops	Isomorphism Type	Questions	Proportion
1 hop	(1)	500	7.59%
1 hop	(1)(1)	600	9.11%
1 hop	(1)(1)(1)	1,211	18.38%
2 hop	(2)	550	8.35%
2 hop	(2)(1)	853	12.95%
2 hop	((1)(1))	700	10.63%
2 hop	(2)(1)(1)	533	8.09%
3 hop	(3)	1,086	16.48%
3 hop	((2)(1))	555	8.42%
Total	-	6,588	100.00%

Synthesis Cost and Retention

As shown in Table 8, we report the candidates retained, the rejection rate, and the teacher calls at each synthesis stage, all of which use the same teacher model, Kimi-K2 Team, [39]. Of 20,000 sampled seed entities, 14,400 yield a verified seed question, 8,784 candidates remain after backward expansion, and 6,588 questions pass all filters, an end-to-end rejection rate of 67.1%. The pipeline uses 115,184 teacher calls, about 17.5 per retained question, and backward expansion accounts for three quarters of them.

Stage	Input	Retained	Rejected	Teacher calls
Seed-question generation	20,000	14,400	28.0%	20,000
Backward expansion	14,400	8,784	39.0%	86,400
Complex-question composition	8,784	6,588	25.0%	8,784
End-to-end	20,000	6,588	67.1%	115,184

Data Leakage Check

To ensure that the synthetic questions do not overlap with the test sets, we encode each question with BGE-M3 and compute the cosine similarity between every test question and its most similar synthetic question. The similarity stays below 0.85

for all test questions. On QALD10-en and WikiWebQuestions, no test question exceeds 0.75, and on GTSQA only 6 questions (0.37%) fall in the 0.80–0.85 range.

KG Interaction Operations

As shown in Table 9, the kg-query action in § 3.2 is instantiated with seven operations in four categories: relation search, neighborhood expansion, constraint filtering, and set combination. The table lists the name, description, input parameters, and output of every operation.

Category	Function	Description	Input Parameters	Output
Relation search	find_outgoing_relations	Given an entity, return all outgoing relations.	entity_name	List of outgoing relations
Relation search	find_incoming_relations	Given an entity, return all incoming relations.	entity_name	List of incoming relations
Neighborhood expansion	get_tail_entities	Follow the relation forward from head to tail.	head_entity_name; relation_name	Set of tail entities
Neighborhood expansion	get_head_entities	Follow the relation backward from tail to head.	tail_entity_name; relation_name	Set of head entities
Constraint filtering	get_entity_by_constraint	Filter the provided entity_set and return the entities satisfying the specified constraint.	entity_set; relation; operator; value	Entity subset
Set combination	intersect	Return the intersection of the given list of entity sets.	entity_set_list	Intersection set
Set combination	union	Return the union of the given list of entity sets.	entity_set_list	Union set

Benchmark Datasets

The benchmarks used for FoG evaluation cover two knowledge graphs, with data sourced as follows:

WikiWebQuestions: Ported from WebQuestions and re-annotated with SPARQL queries over Wikidata Xu et al., [48], consisting of real-world natural language questions.

QALD10-en: Derived from the English subset of the tenth QALD challenge Usbeck et al., [42], the first edition to adopt Wikidata, covering 394 expert-written test questions with multi-hop and qualifier constraints.

GTSQA: Built over Wikidata with 30,144 training and 1,622 test questions Cattaneo et al., [4], each annotated with a gold answer subgraph and a query-graph isomorphism label.

WebQSP: Sourced from Freebase Yih et al., [52] and used only for the zero-shot cross-KG transfer experiment.

Evaluation Details

Evaluation Metrics

We evaluate model performance using four complementary metrics that assess two aspects of KGOQA: answer accuracy (Hit@1 and F1) and evidence coverage (Cov and RetQ).

(i) Hit@1. Hit@1 quantifies whether the predicted answer is correct. For each question, we check whether the normalized prediction matches any gold answer, and then average over all evaluated questions:

where $\hat{y}_i$ and $Y_i^*$ denote the prediction and the gold answer set of the $i$-th question, $\operatorname{norm}(\cdot)$ removes superficial differences such as case and punctuation, and $M$ is the total number of evaluated questions in the benchmark.

(ii) Token-level F1. F1 quantifies the token-level overlap between the predicted and gold answers. For each question, we compute the harmonic mean of token precision and recall, and then average:

where $\operatorname{tokens}(\cdot)$ normalizes each answer in a list, splits it on whitespace, and takes the union of the resulting tokens over the list.

(iii) Evidence Coverage (Cov). Cov quantifies how much of the gold supporting evidence the agent retrieves along its trajectory. For each question, we compute the fraction of gold supporting triples returned by its KG queries, and then average over all questions:

where $\mathcal{T}(\tau_i)$ denotes the set of triples returned by all kg-query actions in the trajectory $\tau_i$, and $S_i^*$ denotes the gold supporting triples of the $i$-th question. This metric reflects whether an answer is backed by the complete evidence path.

(iv) Retrieval Grounding (RetQ). RetQ quantifies whether the gold answer is retrieved from the KG rather than produced from parametric memory. For each question, we check whether any gold answer appears among the entities returned by its KG queries, and then average over all questions:

where $\mathcal{E}(\tau_i)$ denotes the set of entities returned by all KG queries in the trajectory $\tau_i$.

Gold Supporting Triples

The gold supporting triples used for evaluation are distinct from those produced by synthesis, which serve only as ECPR supervision during training. GTSQA provides gold answer subgraphs natively. For WikiWebQuestions, which has no such annotation, we follow EoG [49] and construct them in two stages. We first enumerate candidate paths from each topic entity to each answer entity by BFS under a maximum-hop constraint. An LLM verifier then judges whether each candidate path supports all constraints of the question, and the union of triples on the accepted paths forms the gold supporting triples.

Human Validation of Constructed Paths

To validate the constructed paths independently of the LLM verifier, we sample 200 candidate paths from WikiWebQuestions, 100 accepted and 100 rejected by the verifier. Three graduate annotators independently judge whether each path supports all constraints of its question, without seeing the verifier decision. The annotators reach Fleiss’ $\kappa=$

caption: tbl:10: Representative rejected paths. The verifier checks whether a path covers the semantic constraints of the question, not only whether it reaches a plausible answer entity.

0.91, and the human–verifier agreement is 93.0%, with a verifier precision of 0.94 and a recall of 0.92. Table 10 shows two representative rejected paths.

Baseline Details

We compare FoG against nine representative baselines that cover the LLM reasoning, retrieval-based, and agent-based paradigms:

IO Prompt ([26, 40, 7]) is a KG-free baseline where the LLM directly answers the question from its parametric knowledge. This serves as a lower bound for KG-augmented reasoning.

CoT ([46]) elicits step-by-step reasoning before the final answer, still without any access to the KG.

Self-Consistency ([45]) samples multiple CoT chains and aggregates their answers by majority voting.

RoG ([21]) generates relation paths as plans, retrieves reasoning paths along them, and answers from the retrieved paths.

SubGraphRAG ([18]) retrieves a subgraph with a lightweight MLP that scores triples in parallel, and feeds it to an LLM reader.

GCR ([22]) encodes KG paths into a Trie index and constrains LLM decoding with the graph structure.

ToG ([34]) is a training-free agent that performs beam search over entities and relations through multi-turn KG interaction.

PoG ([5]) decomposes the question into sub-objectives and explores paths with memory updating and self-reflection.

KG-R1 ([19]) trains a single KG agent end-to-end with GRPO under outcome and turn-level action-validity rewards.

Adaptation to Wikidata. RoG, SubGraphRAG, and GCR were proposed on Freebase and rely on dataset-specific supervision, so they cannot be transferred to a new KG without retraining. We therefore retrain each of them on the training split

of every Wikidata benchmark. KG-R1 was also proposed on Freebase. We retrain it on Wikidata with the same training data as FoG.

To ensure fairness, all methods, including FoG, are evaluated under identical conditions with a single inference run per question, and no multi-run aggregation is used. The backbone of each method is listed in Table 1.

Hyperparameter Settings

Supervised Fine-Tuning. For SFT, we adopt LLaMA-Factory ([54]) and apply LoRA to all linear layers. The training trajectories are distilled from the same teacher model used in synthesis, Kimi-K2 ([39]), with the prompt in Table 19. Training runs on a single NVIDIA A100 GPU.

Trajectory distillation Prompt

SYSTEM PROMPT

You are a Knowledge Graph QA Assistant. Your task is to explore the knowledge graph only by calling the provided function tools, and answer questions based on the retrieved triplet information.

Core Principles (Strictly Mandatory): 1. Tool-first. You must call at least one tool before giving any answer. Do not answer from memory or guess. If you have not yet received tool results, your next action must be a tool call, not <answer>. 2. No direct answers. You must not use your own internal knowledge; all information must be obtained from the knowledge graph via function calls. 3. Show reasoning. Before each function call, briefly explain its purpose; after the call, summarize the information obtained. 4. Evidence-based. Text inside <answer> . . . </answer> must be only entity name(s) that appeared in the last relevant tool response(s). 5. Step-by-step exploration. Explore relationships first, then retrieve entities, avoiding blind calls.

Available Functions: {tool_call}

Workflow:

Step 1: Understand the Question. Analyze question type (one-hop, multi-hop, intersection, constraint, hybrid). Identify entities from Entity info. Plan initial exploration.

Step 2: Choose Function Strategy.

• Unknown relations: start with find_outgoing_relations or find_incoming_relations.

• Known relation: use get_tail_entities or get_head_entities.

• “Both A and B” / “satisfies both”: get set A, get set B, then intersect([set_A, set_B]).

• “Among X, which has attribute = value”: get set X, then get_entity_by_constraint.

Step 3: Execute Exploration.

1. Start with the given entity: call find_outgoing_relations or find_incoming_relations. Use entity names from Entity info (no QID); use exact relation names from find_*_relations.

2. Based on question, call get_tail_entities or get_head_entities.

3. For “Both A and B” questions: get set for A, get set for B, then call intersect once.

4. For constraint questions: (a) obtain candidate set; (b) call get_entity_by_constraint(entity_set, relation, "=", value) once.

5. If multi-hop needed, repeat for new entities. Use intersect or union when merging.

Step 4: Generate Answer:

• As soon as a tool returns a result that uniquely answers the question, output <answer>. . . </answer> immediately; do not call more tools.

• Put inside <answer>. . . </answer> only entity name(s) that appeared in tool response(s).

• If max steps are reached without a clear answer: <answer>Cannot find the answer from the knowledge graph.</answer>

USER PROMPT

Question: {question}

Entity info: {entity_info}

Please start by calling tools, then use the observations to decide the next step. Answer only after you have tool evidence.

Reinforcement Learning. For RL, we adopt Verl ([30]) and initialize the policy from the SFT checkpoint. Training runs on a single node with $4 \times$ NVIDIA A100 (40 GB) GPUs, using FSDP with parameter and optimizer CPU offloading, and rollouts are executed with vLLM. For each question, the agent samples $N=4$ trajectories with at most 10 KG interaction turns. KL regularization uses the $k_3$ estimator with coefficient 0.03, anchored to the SFT model. Table 11 and Table 12 summarize the detailed hyperparameter configurations used throughout our experiments, and Table Table 13 lists the coefficients of the composite reward in § 3.3.

Parameter	Value
Fine-tuning method	LoRA
LoRA rank / alpha / dropout	16 / 32 / 0.05
Max sequence length	3,000
Training epochs	3
Per-device batch size	16
Gradient accumulation steps	8
Learning rate	$5 \times10^{-5}$
LR scheduler	Cosine, warmup ratio 0.1
Weight decay	0.01
Gradient clipping	1.0

Parameter	Value
Actor learning rate	$1 \times10^{-6}$
KL loss coefficient	$0.03$ ($\kappa_3$ type)
GRPO rollout $N$	$4$
Max interaction turns per question	$10$
Train batch size	$32$
PPO mini-batch size	$16$
Max prompt length	$4{,}096$
Max response length per step	$8{,}192$
Max observation length	$1{,}024$
Rollout temperature	$0.7$
Total training steps	$450$
Hardware	$4 \times$ NVIDIA A100 (40 GB)

Reward term	Coefficient	Value
Answer F1 ($R_{\mathrm{out}}$)	$\lambda_{\mathrm{f1}}$	$0.7$
Answer retrieval ($R_{\mathrm{out}}$)	$\lambda_{\mathrm{ret}}$	$0.3$
Step validity ($R_{\mathrm{step}}$)	$\lambda_{\mathrm{step}}$	$0.5$
Evidence coverage ($R_{\mathrm{ecpr}}$)	$\lambda_{\mathrm{ecpr}}$	$1.0$

Advantage Computation. The turn-level advantage in § 3.3 is computed as follows. (i) Return. The return $G_{i,t}$ in Equation (8) adds the immediate process rewards of turn $t$ to the outcome reward of the trajectory. We use neither discounting nor a reward-to-go, so the evidence reward of a turn is credited to that turn only. (ii) Normalization. The mean $\mu_q$ and standard deviation $\sigma_q$ are computed over all (trajectory, turn) pairs of the $N$ rollouts of the same question. Trajectories of different lengths need no padding, since each contributes as many returns as it has turns. (iii) Token mask. The advantage of a turn is broadcast to the tokens that the policy generates in that turn, i.e., its reasoning and its tool call or answer. Tool observations are part of the context but are masked out of the policy loss and the KL term. (iv) Objective. The policy maximizes

where $j$ ranges over the $\lvert\tau_i\rvert$ policy-generated tokens, $t(j)$ is the turn of token $j$, $\rho_{i,j}$ is the probability ratio, and $\pi_{\mathrm{ref}}$ is the SFT model. (v) Difference from trajectory-level credit. When the coverage reward is credited only to the final turn, the turns that actually retrieved the evidence receive the same return as the turns that did not, so the update cannot distinguish them. With first-match attribution, two trajectories with the same coverage still produce different per-turn returns, and the advantage concentrates on the queries that first reach gold triples.

Case Study

To better understand how much of the supporting evidence different methods retrieve from the KG, we present a case study on the question: “Which airline flies the Embraer 195 and is based at the airport named after Margaret Kenyatta’s father?” As shown in Table 14, Table 15, and Table 16, this question requires resolving the father, the airport named after him, and the airline that is based there and flies the aircraft. All three methods predict the correct answer, but they differ in how much of the evidence chain they recover.

Question: Which airline flies the Embraer 195 and is based at the airport named after Margaret Kenyatta’s father?

<think>I need to find an airline that satisfies two conditions: 1) flies the Embraer 195, and 2) is based at the airport named after Margaret Kenyatta’s father. Let me start by exploring the relationships around the first given entity to understand what information is stored about Margaret Kenyatta in the knowledge graph.</think>

<kg-query> find_outgoing_relations(entity_name=Margaret Kenyatta) </kg-query>

<information> Outgoing relations for entity Margaret Kenyatta: country of citizenship, father, given name, instance of, mother, occupation, sex or gender......... </information>

<think> The outgoing triple shows that Margaret Kenyatta has a "father" in the knowledge graph. Let me find out who her father is by querying the triple that directly connects Margaret Kenyatta to her father. </think>

<kg-query> get_tail_entities(head_entity_name=Margaret Kenyatta, relation_name=father) </kg-query>

<information> Entities outgoing via relation father from entity Margaret Kenyatta: Jomo Kenyatta.......... </information>

<think> Now I know Jomo Kenyatta is Margaret Kenyatta’s father. Next, I need to find the airport named after Jomo Kenyatta. Let me check what relationships exist for Jomo Kenyatta in the knowledge graph to see if there is an airport named after him. </think>

<kg-query> find_incoming_relations(entity_name=Jomo Kenyatta) </kg-query>

<information> Incoming relations for entity Jomo Kenyatta: father,named after,spouse.......... </information>

<think>I see that some entities have "named after" pointing to Jomo Kenyatta. Let me find out what entities are named after Jomo Kenyatta in the knowledge graph. </think>

<kg-query> get_head_entities(tail_entity_name=Jomo Kenyatta, relation_name=named after) </kg-query>

<information> Entities incoming via relation named after from entity Jomo Kenyatta: Jomo Kenyatta International Airport, Kenyatta International Convention Centre </information>

<think> Great! I found that Jomo Kenyatta International Airport is named after Jomo Kenyatta. Now I need to find which airline is based at Jomo Kenyatta International Airport. Let me check what outgoing relationships exist for Jomo Kenyatta International Airport to see if there is an airline based there. </think>

<kg-query> find_outgoing_relations(entity_name=Jomo Kenyatta International Airport) </kg-query>

<information> Outgoing relations for entity Jomo Kenyatta International Airport: country, instance of, located in the administrative territorial entity, named after......... </information>

<think> I don’t see a direct "airline based at" relationship listed for the airport. Let me check the incoming relationships to see if any airlines have "headquarters location" or similar relationships pointing to this airport. </think>

<kg-query> find_incoming_relations(entity_name=Jomo Kenyatta International Airport). </kg-query>

<information> Incoming relations for entity Jomo Kenyatta International Airport: airline hub </information>

<think> Perfect! I found that some airlines have "airline hub" pointing to Jomo Kenyatta International Airport. Let me find out which airlines have Jomo Kenyatta International Airport as their airline hub. </think>

<kg-query> get_head_entities(tail_entity_name=Jomo Kenyatta International Airport, relation_name=airline hub) </kg-query>

<information> Entities incoming via relation airline hub from entity Jomo Kenyatta International Airport: Kenya Airways </information>

<think> Now I have Kenya Airways as the airline based at Jomo Kenyatta International Airport. Finally, I need to verify that Kenya Airways also flies the Embraer 195. Let me check what aircraft types Kenya Airways operates by looking at its outgoing relationships. </think>

<kg-query> find_outgoing_relations(entity_name=Kenya Airways) </kg-query>

<information> Outgoing relations for entity Kenya Airways: airline alliance, airline hub, country, instance of, item operated .......... </information>

<think> I see that Kenya Airways has "item operated" as an outgoing relationship. Let me find out what items (likely aircraft) Kenya Airways operates. </think>

<kg-query> get_tail_entities(head_entity_name=Kenya Airways, relation_name=item operated) </kg-query>

<information> Entities outgoing via relation item operated from entity Kenya Airways: Boeing 737 Classic,Boeing 737 Next Generation,Boeing 767,Boeing 777,Boeing 787 Dreamliner,Embraer 195 </information>

<think> I now have enough grounded evidence to give the answer. </think>

<answer> ["Kenya Airways"] </answer>

Question	Which airline flies the Embraer 195 and is based at the airport named after Margaret Kenyatta’s father?
Reasoning chains:	Turn 1: ‘Margaret Kenyatta -> father -> Jomo Kenyatta‘; ‘Margaret Kenyatta -> country of citizenship -> Kenya‘; ‘Embraer 195 -> subclass of -> E-Jet‘; ‘Margaret Kenyatta -> occupation -> diplomat‘; ‘Margaret Kenyatta -> occupation -> politician‘;
	Turn 2: ‘Kenya -> named after -> Mount Kenya‘; ‘diplomat -> named after -> Diplomatstaden‘; ‘E-Jet -> manufacturer -> Embraer‘; ‘politician -> category combines topics -> Category:Dutch politicians‘; ‘Jomo Kenyatta -> country of citizenship -> Kenya‘;
	Turn 3: ‘Mount Kenya -> country -> Kenya‘; ‘Embraer -> headquarters location -> São José dos Campos‘; ‘Category:Dutch politicians -> is a list of -> human‘; ‘Kenya -> named after -> Mount Kenya‘; ‘Diplomatstaden -> located in the administrative territorial entity -> Stockholm Municipality‘;
	Turn 4: ‘Kenya -> named after -> Mount Kenya‘; ‘Mount Kenya -> country -> Kenya‘; ‘Kenya -> capital -> Nairobi‘; ‘São José dos Campos -> country -> Brazil‘; ‘São José dos Campos -> located in the administrative territorial entity -> São Paulo‘;
	<answer>First, the airline that flies the Embraer 195 is Kenya Airways. Second, the airport named after Margaret Kenyatta’s father is Jomo Kenyatta International Airport. The answer is {Kenya Airways}</answer>

Question	Which airline flies the Embraer 195 and is based at the airport named after Margaret Kenyatta’s father?
Reasoning chains:	Turn 1: Embraer 195 -> item operated -> Kenya Airways;
	<answer>Kenya Airways operates the Embraer 195 and is based at Jomo Kenyatta International Airport, which is named after Margaret Kenyatta’s father. The answer is {Kenya Airways}</answer>

FoG recovers the complete gold evidence. It issues nine KG turns and grounds each hop in the triples returned by the previous one, so every link of the chain can be read from the trajectory.

In contrast, ToG performs four rounds of beam search but recovers only one relevant triple, missing the links for airport naming and airline hub, so its answer relies mainly on parametric knowledge. PoG answers after a single retrieval step, leaving an evidence chain that cannot be audited from the trajectory. This case highlights the strength of FoG in reaching the answer through evidence that is fully retrieved from the KG.

Prompts Used in FoG

Seed Question Generation Prompt

As shown in Table 17, this prompt is designed for generating seed questions from a sampled subgraph. It guides the teacher to return a question, its logical form, and its supporting triples, which corresponds to $T_{\mathrm{gen}}$ in Equation (1).

Seed Question Generation Prompt

SYSTEM PROMPT

You are a question synthesis expert. You are deeply familiar with the structure of the Wikidata knowledge graph and specialize in constructing questions based on given triple information.

Core Concept Definitions

Three Entity Roles in this task:

• Constraint Entity (Con@). The starting point of the question; an entity the user already knows that must be explicitly mentioned. It anchors the context of the question.

• Intermediate Entity (Mid@). The intermediate node in the reasoning chain, obtained through the first reasoning step from the constraint entity. It connects two reasoning steps and must be inferred by the user, never stated explicitly.

• Answer Entity (Ans@). The endpoint of the reasoning chain and the final answer requested by the user.

Triple Selection Principles

• Subset selection. Select a subset of triples from the given set as the evidence basis. Prefer strong constraints that lead to clear, unambiguous answers.

• Avoid redundancy. If a triple already infers B from A, do not select another path that also infers B (no shortcuts allowed).

• Necessity. Every selected triple must contribute to the reasoning chain; no irrelevant triples are permitted.

Question Design Principles

• Information sources. All information must come exclusively from the selected triples. No external knowledge may be used; the question must be verifiable via a SPARQL query on Wikidata.

• Reasoning forms. The question may adopt single-hop reasoning, multi-hop reasoning, intersection queries, union queries, counting, or reverse reasoning.

• Answer requirements. The answer must be derived entirely from selected triples and directly verifiable via a SPARQL query.

• Path guidelines. A Path is an explanation of the reasoning process, expressed as a reasoning chain describing how the answer is derived.

SPARQL Query Requirements

• The generated SPARQL must be syntactically correct and executable on the Wikidata Query Service (WDQS).

• Query results must accurately correspond to the answer of the question.

• For multi-hop questions, the SPARQL must clearly reflect intermediate variables in the reasoning process.

Entity Usage Rules in Questions

✓ Only constraint entities (question premises) may be explicitly mentioned.

✓ The question must ask for the answer entity (final target).

× The specific name of any intermediate entity must never appear explicitly in the question.

× Intermediate entities must only be implicitly implied through relational wording.

× Avoid redundancy: if the answer can be uniquely determined with fewer triples or entities, the question is redundant and must be revised.

USER PROMPT

Relevant Triple Information:

#{Relevant triple information}

Backward Expansion Prompt

As shown in Table 18, this prompt is used by the backward-expansion agent. The agent is instructed to select an anchor entity, retrieve its neighborhood, generate a sub-question whose answer is the anchor, and verify the result, retrying on failure.

Complex Question Generation Prompt

SYSTEM PROMPT

You are an expert agent specializing in Knowledge Graph Question Answering (KGQA) data synthesis. Select an Anchor Node from a given set of entities and generate a high-quality sub-question that can uniquely identify/locate this anchor entity within the Knowledge Graph.

Standard Operating Procedure:

Step 1 Select an entity as the Anchor Node and call retrieve_entity_neighborhood to fetch its neighboring triples.

Step 2 Call select_triples_and_generate_subquestion to choose relevant triples and generate the sub-question.

Step 3 Call verify_subquestion to validate the accuracy and check for redundancy of the generated question.

Step 4 If validation passes, return the final result in <answer>{. . . }</answer> format. If it fails, return to Step 2 and retry.

Strict Constraints:

Prohibited:

× No shortcuts. Do not skip any steps or generate the final answer directly.

× No tool-less answers. Never return <answer> without having successfully executed the required tool calls.

× No preconceptions. Do not assume or hallucinate knowledge before receiving tool outputs.

× Redundancy rule. If verify_subquestion flags the question as “redundant,” it means the anchor entity can be uniquely identified using fewer triples or fewer entities in the question. You must retry Step 2.

Required:

✓ Sequential execution. Strictly follow the 1 → 2 → 3 → 4 workflow.

✓ Careful observation. Analyze the output of each tool before proceeding to the next step.

✓ Final approval. Only output the final result after verify_subquestion returns a success status.

USER PROMPT

Output Format:

The final answer must be returned as a JSON object wrapped within <answer></answer> tags:

JSON Format

If a question cannot be generated, return: <answer>do not generate question</answer>

Input Entity Information:

Please select one entity from the list below to serve as the Anchor Node (the answer entity) and generate a sub-question for it:

{entity_info}

Trajectory Distillation Prompt

As shown in Table 19, this prompt is used to distill the teacher trajectories for SFT. The teacher is instructed to explore the KG only through the provided tools, explain each call, and answer with entities that appear in the tool responses.

Agent Prompt

As shown in Table 20, this prompt is used by the FoG agent in both training and evaluation. It guides the agent to analyze the question, call the KG operations, and answer from the returned triples.

FoG Training and Evaluation Prompt

SYSTEM PROMPT

You are a knowledge graph question answering assistant. You answer user questions by interacting with a knowledge graph. When a user provides a question and its associated entities, you call tools to query the knowledge graph accordingly. No matter how complex the question is, you will not give up until you believe an answer can be found based on the available information.<br><br>• Comprehensive analysis. Combine external triple information obtained through tools to perform analysis and provide a complete answer.<br>• Working principles. Clearly analyze the problem, select appropriate tools, invoke them to obtain information, and ensure the problem is solved efficiently.

USER PROMPT

<tools> tools definition </tools><br><br>The assistant operates in one or more cycles of (thinking → tool call → tool response), followed by a final (thinking → answer) step. All intermediate processes are enclosed within their respective tags. Multiple thinking steps, tool calls, and responses may appear in sequence.<br><br>Example Response:<br><think> thinking process here </think><br><kg-query>{"name": "tool name", "arguments": {"param": value, ...}}</kg-query><br><information> tool_response here </information><br><br><think> thinking process here </think><br><kg-query> {"name": "another tool name", "arguments": {...}} </kg-query><br><information> tool_response here </information><br>... (more thinking, tool calls, and responses) ...<br><think> thinking process here </think><br><answer> answer here </answer><br><br>User Input:<br>Question: {question}<br>Entity info {entity_name}