Research map / Large language models / Retrieval and knowledge

Reasoning of Large Language Models over Knowledge Graphs with Super-Relations

ICLR 2025 · Large language models › Retrieval and knowledge · approach: Knowledge graph reasoning with LLMs · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes ReKnoS, which reasons over knowledge graphs with super-relations (groups of relations) so an LLM can explore multiple relation paths per step, improving retrieval rate and accuracy with fewer LLM calls.

Problem

LLM-based reasoning over knowledge graphs suffers from a high non-retrieval rate, largely due to greedy search and forward-only reasoning that prunes correct relation paths (misdirection and depth limitation).

Approach

Introduce super-relations (groups of fine-grained relations, e.g., second-level Wikidata relations) as the unit of LLM scoring, so each step keeps many relation paths implicitly; forward and backward reasoning over super-relation search paths, with entity extraction only at the end, expands the search space while keeping the number of LLM calls independent of width N.

Key results

• ReKnoS with GPT-3.5 reaches 71.9% Hits@1 on GrailQA and 81.1% on WebQSP, versus 68.9% and 76.2% for the best baselines (KG-Agent and ToG).
• Averaged over nine datasets, ReKnoS gains 2.92% accuracy with GPT-4o-mini and GPT-3.5 comparisons, per the abstract.
• ReKnoS uses 7.2 LLM calls on WebQSP versus 15.3 for ToG, with the LLM call count independent of search width N.

Measured effects reported in the paper

Surprising findings

• KG-Agent outperforms ReKnoS on SimpleQA and T-REx with GPT-4o-mini, which the authors attribute to GPT-4o-mini's tool-use ability.
• Misdirection accounts for most non-retrieval cases on GrailQA (68.8%) and WebQSP (72.5%), while on CWQ depth limitation is the largest cause (43.1%).

Limitations

• Super-relations rely on a hierarchical relation structure (e.g., Wikidata levels); other KGs require clustering that may not yield coherent super-relations.
• Accuracy gains over strong baselines are modest on some datasets, and GNN-RAG and RoG outperform it on some metrics that require fine-tuning.
• Experiments use black-box LLMs and small-scale open models with a single run for most results.

Experimental setup

Datasets: WebQSP GrailQA CWQ SimpleQA WebQ T-REx zsRE Creak HotpotQA OpenBookQA MetaQA

Benchmarks: WebQSP GrailQA CWQ SimpleQA WebQ T-REx zsRE Creak HotpotQA OBQA MetaQA

Metrics: Hits@1 F1 retrieval rate search space size number of LLM calls

Baselines: IO prompting Chain-of-Thought Self-Consistency StructGPT Think-on-Graph KG-Agent SR UniKGQA RoG GNN-RAG

Builds on: Think-on-Graph StructGPT KG-Agent Chain-of-Thought Self-Consistency

Closest papers by meaning

• Debate on Graph: A Flexible and Reliable Reasoning Framework for Large Language Models (AAAI 2025 · similarity 0.91)
• Reasoning on Graphs: Faithful and Interpretable Large Language Model Reasoning (ICLR 2024 · similarity 0.91)
• Simple is Effective: The Roles of Graphs and Large Language Models in Knowledge-Graph-Based Retrieval-Augmented Generation (ICLR 2025 · similarity 0.91)
• Harnessing Large Language Models for Knowledge Graph Question Answering via Adaptive Multi-Aspect Retrieval-Augmentation (AAAI 2025 · similarity 0.90)
• Talk like a Graph: Encoding Graphs for Large Language Models (ICLR 2024 · similarity 0.90)
• Think-on-Graph 2.0: Deep and Faithful Large Language Model Reasoning with Knowledge-guided Retrieval Augmented Generation (ICLR 2025 · similarity 0.90)