Overview
Production Readiness
0.6
Novelty Score
0.45
Cost Impact Score
0.6
Citation Count
3
Why It Matters For Business
RoK gives domain QA systems more accurate, interpretable answers while cutting LLM calls and API cost by structuring knowledge as ranked KG paths.
Summary TLDR
RoK (Reasoning on Efficient Knowledge Paths) builds short reasoning paths from a knowledge graph and uses chain-of-thought (CoT) to expand question entities. It ranks candidate multi-hop paths with PageRank and supplies the top paths as structured background to an LLM. On three QA sets (medical and WebQuestions subsets), RoK improves entity-match and semantic scores versus vanilla LLMs and prior KG-based prompts while requiring only about three LLM calls per question.
Problem Statement
LLMs hallucinate and struggle on domain-specific multi-hop questions because they lack structured domain context and fine-tuning is costly or unavailable. Prior KG+LLM methods call LLM many times during path selection, which is slow and error-prone when an early path choice is wrong.
Main Contribution
A pipeline (RoK) that expands question entities via LLM chain-of-thought, enumerates multi-hop candidate paths in a knowledge graph, ranks paths with PageRank, and prunes neighbor triples with a single LLM call.
A practical subgraph retrieval method that uses CoT to increase entity linking coverage and PageRank to pick top-N reasoning paths as structured prompts.
Empirical results on GenMedGPT-5k, CMCQA and WebQuestions showing better entity-match and semantic scores than vanilla LLMs and competitive gains versus prior KG-based prompting, using fewer LLM calls (about three).
Key Findings
RoK improves key-entity match accuracy on GenMedGPT-5k to 81.3% from GPT-3.5's 52.6%.
RoK increases answer semantic similarity (BERTScore F1) on GenMedGPT-5k to 0.815 vs GPT-3.5 0.791 and prior MindMap 0.802.
RoK achieves lower (better) GPT-4 average ranking on GenMedGPT-5k (1.53) compared to MindMap (1.94) and GPT-3.5 (3.44).
RoK matches or improves Hits@1 on WebQuestions to 80.5% vs GPT-3.5 68.5%.
RoK reduces LLM call dependency: the paper reports obtaining final results with only three LLM calls per question.
Results
BERTScore F1 (GenMedGPT-5k)
BERTScore F1 (CMCQA)
GPT-4 average ranking (GenMedGPT-5k)
Accuracy
Hits@1 (WebQuestions)
Who Should Care
What To Try In 7 Days
Add a CoT step to expand entities from user questions, then do simple entity linking to your domain KG.
Enumerate short multi-hop paths between linked entities, score nodes with PageRank, and surface top paths as structured context to your LLM.
Replace expensive multi-step LLM path selection with a single LLM pass to filter neighbor triples and one final answer call; measure entity hit rate and API calls.
Optimization Features
Token Efficiency
- Provide compact reasoning paths instead of long document chunks
Inference Optimization
- Reduce LLM calls via structured path selection
Reproducibility
Data Urls
Data Available
Open Source Status
- partial
Risks & Boundaries
Limitations
- Requires a domain knowledge graph with sufficient coverage; missing entities reduce effectiveness.
- PageRank is a heuristic and may prioritize high-degree hub nodes over semantically best paths.
- Evaluation partly relies on GPT-4 as judge, which the authors acknowledge is imperfect.
When Not To Use
- You lack a curated KG for the domain.
- Questions are simple single-hop factual lookups where standard retrieval already suffices.
- You need fully open-domain answers without a domain KG constraint.
Failure Modes
- Entity linking fails or links to wrong KG nodes, producing wrong paths.
- PageRank selects hub-heavy but semantically irrelevant paths.
- LLM misfilters neighbor triples if prompt context is ambiguous, introducing noise into the final prompt.
Core Entities
Models
- GPT-3.5
- GPT-4
- LLAMA2 (mentioned generically)
Metrics
- BERTScore
- GPT-4 average ranking
- Hits@1
- Accuracy
Datasets
- GenMedGPT-5k
- CMCQA
- WebQuestions
- FB15k-237