PaperlayerView exact revision on arXiv

Source-linked AI summary

Compositional Chain-of-Relations for Faithful Knowledge Graph Question Answering with Large Language Models

Chenhui Liu, Jianpeng Zhou, Jiahai Wang

arXiv:2608.22762v1cs.AI

TL;DR

Complex KGQA requires both multi-hop candidate retrieval and KG-grounded constraint handling, but existing agent methods prune entities and rely on parametric constraint judgments. CCoR uses relation-centric exploration with main and constraint chains to ground both phases, and experiments across four benchmarks report consistent gains in accuracy, faithfulness, and efficiency, especially for constraint-heavy queries.

  • Problem

    Existing agent-based KGQA methods can discard valid entities through unreliable pruning and leave constraints unverified by resolving them from parametric knowledge.

  • Method

    CCoR uses relation-centric exploration and composes a main retrieval chain with an explicit KG-executed constraint chain.

  • Results

    Experiments on four KGQA benchmarks and multiple LLM backbones consistently improve accuracy, faithfulness, and efficiency, with the most pronounced gains on constraint-heavy queries.

  • Takeaways & Limitations

    CCoR makes constraint handling auditable through executable KG operations while maintaining reliable reasoning across queries of varying complexity.

Abstract

from arXiv · show

Knowledge graph question answering (KGQA) is a key task for evaluating KG-augmented Large Language Models (LLMs), and complex KGQA that requires multi-hop reasoning is especially challenging. Solving a complex query involves two coupled phases: candidate retrieval, which locates answer candidates over the KG, and constraint handling, which filters these candidates against the query constraints. Faithful reasoning requires grounding both phases in the KG. However, existing agent-based methods ground candidate retrieval through entity-centric exploration, while leaving constraint handling to the LLM's internal knowledge, which leads to two critical limitations. (1) Unreliable entity pruning: entity-centric exploration uses entities as search units and must prune them to a fixed-size subset at each hop. Because entity information in KGs is often incomplete and a fixed-size subset cannot retain all valid entities, such pruning inevitably drops valid entities and ultimately leads to wrong answers. (2) Ungrounded constraint handling: query constraints are resolved from the LLM's internal knowledge rather than the KG, leaving the final answers unverifiable and prone to hallucination. To address these limitations, this paper introduces a relation-centric exploration paradigm, which uses relations rather than entities as search units and thus avoids unreliable entity pruning. Built on this paradigm, this paper proposes Compositional Chain-of-Relations (CCoR), a simple and effective framework that grounds both phases in the KG with two relation chains: a main chain for candidate retrieval and a constraint chain that verifies query constraints through explicit KG exploration. Experiments on four KGQA benchmarks show that CCoR consistently improves accuracy, faithfulness, and efficiency over strong baselines, with more pronounced gains on complex queries.

I. INTRODUCTION

Complex KGQA couples candidate retrieval with constraint handling, but existing agent-based methods risk losing valid entities and resolving constraints without KG verification. CCoR addresses both issues through relation-centric exploration and compositional relation chains, improving accuracy, faithfulness, and efficiency across four benchmarks.

  • Complex KGQA requires multi-hop reasoning and constraint handling across coupled candidate-retrieval and filtering phases.
  • Existing agent-based methods suffer unreliable entity pruning and ungrounded constraint handling, which can discard valid paths and permit factual hallucinations.
  • 97 Best Actor Oscar winners pruned to 3 under k=3 leave 94 actors discarded and their exclusive reasoning paths unreachable.
  • CCoR uses relations rather than entities as search units, avoiding intermediate entity pruning during candidate retrieval.
  • CCoR composes a main chain for candidate retrieval with a constraint chain for explicit KG-based constraint execution, grounding both phases.
  • Experiments on WebQSP, CWQ, QALD10, and GrailQA show consistent improvements in accuracy, faithfulness, and efficiency over strong baselines.

II. RELATED WORK

Related work couples LLMs and KGs through tuning, retrieval, or agentic traversal, but each retains important grounding, transfer, or pruning limitations. CCoR replaces entity pruning and implicit constraint judgment with relation-centric, KG-grounded chains.

  • Traditional semantic-parsing and embedding-based approaches rely on predefined schemas or learned representations, limiting flexibility on diverse complex queries.
  • Tuning-based methods internalize KG reasoning but require retraining and resolve constraints implicitly, limiting transfer across KGs and schemas.
  • Retrieval-based methods depend on retrievers that generalize poorly across KG or schema shifts, while final LLM generation remains susceptible to hallucination.
  • Agent-based methods iteratively traverse KGs but still prune valid intermediate entities and resolve constraints with parametric knowledge rather than the KG.
  • CoR uses relations as search units to avoid discarding valid intermediate entities during exploration.
  • CCoR models each constraint as a relation chain grounded over the KG, replacing parametric constraint judgment with explicit KG execution.

III. PRELIMINARY

CCoR represents complex KGQA as compositional KG execution: a main chain constructs candidates, an optional constraint chain filters them, and a shared exploration engine supports iterative search and recovery.

  • The main chain connects topic entities to a candidate answer space, while the constraint chain connects a constraint source to its target for explicit filtering.
  • Constraint-chain execution compositionally filters candidates; without an explicit constraint, the final answer set equals the candidate set.
  • CCoR comprises Main-Chain Exploration, Constraint-Chain Exploration, and a two-layer fallback strategy built on a shared relation-centric engine.
  • The shared engine initializes an empty chain and memory stack, then stores explored branches and alternatives for backtracking.
  • Each exploration iteration performs relation search, relation pruning, memory update, and reasoning.

1) Relation Search:

Relation search explores compact relation space without explicitly instantiating intermediate entities, while scoring, memory, and hierarchical actions guide chain construction and recovery.

  • Relation Search:: Relation search retrieves expandable relation candidates from the KG while treating intermediate entities as implicit variables.
  • Relation Search:: Candidate relations are scored by question alignment, chain consistency, and proximity to likely answer regions before top-ranked relations are retained.
  • Relation Search:: Retained relations form alternative candidate chains stored in a memory stack, prioritizing high-scoring chains while preserving branches for backtracking.
  • Relation Search:: Main-chain reasoning selects Forward, Backtrack, Stop, or Constraint according to chain correctness, completeness, and whether targets reach the answer space.
  • Relation Search:: When the Constraint action is selected, candidate entities are passed to constraint-chain exploration for explicit filtering.

C. Constraint Chain Exploration

Constraint-chain exploration explicitly resolves query constraints through KG exploration, filtering candidate entities without relying solely on the LLM’s internal knowledge.

  • Constraint Chain Exploration: A constraint chain links a constraint source to a constraint target and explicitly filters the current target entities.It is triggered by a Constraint action from main-chain reasoning.
  • Initialization: The agent reformulates the unresolved portion of the question into a standalone constraint query and extracts its constraint source.This query focuses on what the main chain has not addressed.
  • Exploration: Constraint-chain reasoning chooses Forward, Backtrack, or Stop according to chain consistency and whether a valid constraint target is available.Forward extends exploration, Backtrack switches branches, and Stop returns filtered results.
  • Execution: When Stop identifies a constraint target, the system combines the main and constraint chains in one SPARQL query to compute the feasible set.The final answer set is then obtained by explicit filtering.
  • Faithful Constraint Handling: Constraint-chain exploration converts constraint handling from implicit memory-based judgment to explicit KG execution.It reuses the shared relation-centric exploration engine for relation search, pruning, and memory updates.

D. Fallback Mechanism

CCoR adds fallback layers for exploration failures, trading KG grounding for robustness when explicit chain execution cannot be completed.

  • Fallback Mechanism: CCoR activates a two-layer fallback mechanism when complex-query KG exploration fails, with each layer providing a different grounding level.Fallback causes and stages are logged for faithfulness analysis.
  • Layer 1: Global Entity Filtering: If constraint-chain exploration fails after main-chain success, Global Entity Filtering uses the LLM to identify and filter the unresolved constraint.This operates on the candidate set produced by the main chain.
  • Layer 1: Global Entity Filtering: Global Entity Filtering is less faithful but more robust because it uses parametric knowledge for constraints that are difficult to formalize as relation chains.The main-chain candidate set retains partial KG grounding.
  • Layer 2: LLM Direct Generation: If main-chain reasoning fails irrecoverably, CCoR falls back to direct answer generation from the question alone.This final layer provides no KG-grounded evidence.

V. FAITHFULNESS METRICS

The paper introduces Knowledge-Grounded Rate to measure grounding strength, using shared evidence-source categories and weighted credit for full or partial KG support.

  • Motivation: Answer correctness alone cannot distinguish explicit KG reasoning from parametric memory recall, motivating dedicated faithfulness metrics.The metrics characterize how methods ground answers in external knowledge graphs.
  • Grounding States: Each evaluation sample receives a grounding-source state based on the evidence used to produce its final answer.The states represent decreasing levels of KG grounding.
  • Grounding States: The structured state means the final answer comes entirely from explicit KG execution, while synthesis uses partial KG results and parametric reasoning.These definitions are method-agnostic across KG-augmented LLM methods.
  • CCoR Grounding States: For CCoR, structured, synthesis, and parametric states correspond respectively to no fallback, Layer 1 fallback, and Layer 2 fallback.The states connect operational fallback behavior to faithfulness evaluation.
  • Knowledge-Grounded Rate: KGR assigns weights of 1.0, 0.5, and 0 to structured, synthesis, and parametric answers, respectively, and averages them across samples.The weighted formulation distinguishes partial from full grounding.

B. Faithful-F1

Faithful-F1 is designed to evaluate answer correctness together with KG grounding, while the experiments compare CCoR across diverse KGQA datasets and baseline families.

  • Faithful-F1: Faithful-F1 combines F1-Score and KGR to jointly evaluate answer correctness and reasoning faithfulness.It is intended to better characterize faithful complex-KGQA performance.
  • Datasets: The evaluation covers WebQSP, CWQ, GrailQA, and QALD10-EN across Freebase and Wikidata.Table II reports main-chain depth and constraint presence where annotations are available.
  • Dataset Characteristics: CWQ emphasizes multi-hop constrained queries, whereas WebQSP is comparatively straightforward with mostly one- or two-hop unconstrained questions.CWQ includes many three-or-more-hop questions and constrained examples.
  • Dataset Characteristics: GrailQA is constraint-rich despite mostly single-hop reasoning, while QALD10-EN emphasizes compositional reasoning with diverse constraint types.QALD10-EN lacks parseable SPARQL annotations for depth and constraint statistics.
  • Baselines: CCoR is compared with tuning-based, retrieval-based, and agent-based baselines, including methods that retrieve KG evidence or interactively explore KGs.The baseline set includes both training-dependent and training-free approaches.

C. Implementation Details

The implementation evaluates CCoR with multiple LLM backbones, controlled agent settings, shared knowledge graphs, and metrics covering both answer correctness and reasoning faithfulness.

  • Model configuration: CCoR and key baselines are evaluated with GPT-3.5-turbo, GPT-4.1-mini, and DeepSeek-V3.1, while GPT-5.4-mini is used for complex-query evaluation.All models use temperature 0.01 for deterministic reasoning.
  • Agent settings: Agent-based methods use top-k pruning with k = 3 and maximum reasoning depths of 3 hops on most datasets and 4 hops on CWQ.The configured datasets are WebQSP, QALD10, GrailQA, and CWQ.
  • Knowledge graph resources: All methods use the official Freebase snapshot or Wikidata SPARQL endpoint, with the same knowledge graph for fair comparison.Freebase follows the ToG setup, while Wikidata uses its official endpoint.
  • Evaluation metrics: The evaluation reports Hits@1, Precision, Recall, and F1 for answer correctness, alongside KGR and FF1 for reasoning faithfulness.KGR measures weighted grounding, while FF1 combines answer correctness with grounding.

E. Main Results

Across four benchmarks and multiple comparison groups, CCoR delivers strong accuracy and grounding, with its largest gains on constraint-heavy queries and without task-specific training.

  • Accuracy evaluation: CCoR achieves the best accuracy on CWQ and QALD10, while remaining strongest among training-free methods on WebQSP and GrailQA.On WebQSP and GrailQA, it is only marginally behind the best supervised-training methods.
  • Accuracy evaluation: CCoR performs strongly on both Freebase and Wikidata benchmarks, indicating transfer across heterogeneous knowledge graphs.The benchmarks include WebQSP, CWQ, and GrailQA on Freebase, plus QALD10 on Wikidata.
  • Accuracy evaluation: CCoR remains competitive without training, whereas Pangu’s advantage depends on task-specific fine-tuning and disappears when supervision is reduced.Pangu drops from 81.7 F1 to 62.7 in the 100-shot setting and 56.3 in the 10-shot setting on GrailQA.
  • Accuracy evaluation: 3.4 Hits@1 and 1.3 F1 are CCoR’s improvements over RoG on CWQ, while it is only marginally behind retrieval-based methods on WebQSP.The comparison is between training-free CCoR and supervised-trained retrieval methods.
  • Accuracy evaluation: 66.0 Hits@1 versus 63.2 for PoG is CCoR’s result on CWQ, with the largest agent-based gain occurring on the constraint-heavy benchmark.CCoR attains the best Hits@1 and F1 across all four benchmarks within the agent-based group.
  • Accuracy evaluation: CCoR’s relation-centric exploration and KG-grounded constraint handling distinguish it from entity-centric ToG and PoG.The comparison attributes the difference to shifting the search unit from entities to relations and grounding constraints in the KG.
  • Faithfulness evaluation: CCoR’s KGR and FF1 expose grounding differences that answer correctness alone misses, including zero grounding for KG-inaccessible prompt-based agents.IO-Prompt and CoT-Prompt retain non-trivial F1 but have KGR and FF1 of 0.0.
  • Performance on complex query: 68.4 Hits@1, 38.6 FF1, and 61.9 KGR are achieved by CCoR on constraint-heavy CWQ under GPT-4.1-mini, exceeding PoG’s corresponding 54.2, 18.8, and 36.4.The reported separation is largest for KGR.

G. Efficiency Study

CCoR reduces API calls and token use on complex queries while remaining comparable on simple ones, and reasoning-depth results identify depth 4 as the best trade-off.

  • LLM call distribution: CCoR consistently issues fewer API calls than ToG and PoG across WebQSP, CWQ, and QALD10.Figure 4 compares per-question call distributions across the three datasets.
  • LLM call distribution: 4.51 calls on WebQSP, 5.51 on QALD10, and 10.20 on CWQ are required by CCoR, below both ToG and PoG on each dataset.On CWQ, CCoR uses about half as many calls despite additionally running constraint-chain exploration.
  • Token consumption: CCoR consumes the fewest tokens on complex CWQ and QALD10 queries, using about 59.2M and 2.5M tokens respectively.On CWQ, this is roughly half of PoG’s 113.2M tokens.
  • Token consumption: On simple WebQSP, CCoR uses slightly more tokens than PoG, with the difference remaining within one million.Few WebQSP queries trigger the constraint chain, limiting its additional cost.
  • Impact of reasoning depth: 84.1% to 100.0% cumulative coverage and 47.8 to 67.0 Hits@1 are obtained as maximum CWQ reasoning depth increases from 2 to 4.At depth 4, F1 and KGR also reach 57.8 and 69.1.
  • Impact of reasoning depth: Depth 5 preserves 100.0% coverage but lowers Hits@1, F1, and KGR to 64.7, 53.9, and 68.2, respectively.The passage attributes the decline to noisy branches without expanded question coverage.

I. Ablation Study

CCoR’s ablations show that explicit constraint-chain exploration is the dominant contributor to accuracy and KG grounding, while relation-level backtracking provides additional robustness. A case study further illustrates that explicit constraint execution can recover the precise constrained answer with substantially fewer calls than entity-centric baselines.

  • Ablation findings: Removing constraint-chain exploration drops KGR from 69.1 to 49.8, showing its central contribution to grounded execution.The ablation replaces explicit KG execution with Global Entity Filtering and observes declines across all three metrics.
  • Ablation findings: Removing relation-level backtracking causes a milder KGR decline to 42.6 because single-branch traversal cannot recover from early relation-selection errors.Backtracking primarily improves robustness during upstream chain construction rather than serving as the main source of grounding.
  • Ablation findings: Removing Global Entity Filtering produces the largest degradation, with KGR dropping sharply to 29.8 when constraint handling is eliminated.The ablation identifies constraint handling as the key bottleneck on CWQ, where constrained questions are prevalent.
  • Case study: On a constrained two-hop CWQ question, CCoR retrieves eight candidate teams at the correct granularity before explicitly filtering them by the fight-song relation.The main chain reaches team entities, while the constraint chain executes the lexical condition over the KG.
  • Case study: Hits@1 of 1 and F1 of 1.00 are achieved in six calls, compared with 30–32 calls for ToG and PoG, which both return the wrong university-level answer.The explicit constraint chain returns only Washington Huskies football, whereas the entity-centric baselines fail to execute the fight-song condition precisely.
  • Overall findings: CCoR consistently improves accuracy, faithfulness, and efficiency across four benchmarks, with the most pronounced gains on constraint-heavy queries.The paper identifies faithfulness improvements, including gains in KGR and FF1, as the framework’s most distinctive advantage.
Loading 2608.22762v1…