LogosKG: Hardware-Optimized Scalable and Interpretable Knowledge Graph Retrieval

# LogosKG: Hardware-Optimized Scalable and Interpretable Knowledge Graph Retrieval
Source: [https://arxiv.org/html/2604.18913](https://arxiv.org/html/2604.18913)
He Cheng1,Yifu Wu1,Saksham Khatwani1,2,Maya Kruse1,Dmitriy Dligach3, Timothy A\. Miller4,5,Majid Afshar6,Yanjun Gao1 1LARK Lab, University of Colorado Anschutz,2University of Colorado Boulder, 3Loyola University Chicago,4Harvard Medical School, 5Boston Children’s Hospital,6University of Wisconsin\-Madison \{he\.2\.cheng, yanjun\.gao\}@cuanschutz\.edu

###### Abstract

Knowledge graphs \(KGs\) are increasingly integrated with large language models \(LLMs\) to provide structured, verifiable reasoning\. A core operation in this integration is multi\-hop retrieval, yet existing systems struggle to balance efficiency, scalability, and interpretability\. We introduceLogosKG, a novel, hardware\-aligned framework that enables scalable and interpretablekk\-hop retrieval on large KGs by building on symbolic KG formulations and executing traversal as hardware\-efficient operations over decomposed subject, object, and relation representations\. To scale to billion\-edge graphs,LogosKGintegrates degree\-aware partitioning, cross\-graph routing, and on\-demand caching\. Experiments show substantial efficiency gains over CPU and GPU baselines without loss of retrieval fidelity\. With proven performance in KG retrieval, a downstream two\-round KG\-LLM interaction demonstrates howLogosKGenables large\-scale, evidence\-grounded analysis of how KG topology, such as hop distribution and connectivity, shapes the alignment between structured biomedical knowledge and LLM diagnostic reasoning, thereby opening the door for next\-generation KG\-LLM integration\. The source code is publicly available at[https://github\.com/LARK\-NLP\-Lab/LogosKG](https://github.com/LARK-NLP-Lab/LogosKG), and an online demo is available at[https://lark\-nlp\-lab\-logoskg\.hf\.space/](https://lark-nlp-lab-logoskg.hf.space/)\.

LogosKG: Hardware\-Optimized Scalable and Interpretable Knowledge Graph Retrieval

He Cheng1, Yifu Wu1, Saksham Khatwani1,2, Maya Kruse1, Dmitriy Dligach3,Timothy A\. Miller4,5,Majid Afshar6,Yanjun Gao1††thanks:Corresponding author1LARK Lab, University of Colorado Anschutz,2University of Colorado Boulder,3Loyola University Chicago,4Harvard Medical School,5Boston Children’s Hospital,6University of Wisconsin\-Madison\{he\.2\.cheng, yanjun\.gao\}@cuanschutz\.edu

## 1Introduction

For decades, knowledge graphs \(KGs\) have served as a foundation for structured knowledge representation, linking concepts through relations across domains such as social networks\(Caiet al\.,[2023](https://arxiv.org/html/2604.18913#bib.bib3)\), biomedicine\(Luet al\.,[2025](https://arxiv.org/html/2604.18913#bib.bib2)\), and recommendation systems\(Wanget al\.,[2025a](https://arxiv.org/html/2604.18913#bib.bib1)\)\. With the rise of large language models \(LLMs\), KGs have gained renewed importance as an external symbolic knowledge source that complements LLMs’ statistical reasoning in tasks like retrieval\-augmented generation \(RAG\)\(Liuet al\.,[2025](https://arxiv.org/html/2604.18913#bib.bib4); Sharmaet al\.,[2024](https://arxiv.org/html/2604.18913#bib.bib19)\), knowledge verification\(Phamet al\.,[2025a](https://arxiv.org/html/2604.18913#bib.bib6); Dammuet al\.,[2024](https://arxiv.org/html/2604.18913#bib.bib7)\), and reasoning\(Wanget al\.,[2025b](https://arxiv.org/html/2604.18913#bib.bib5); Wuet al\.,[2025](https://arxiv.org/html/2604.18913#bib.bib8)\)\. In high\-stakes domains such as medical diagnosis, where LLM reliability directly affects patient safety, KGs are increasingly used to ground model predictions in verified biomedical knowledge\(Jiaet al\.,[2024](https://arxiv.org/html/2604.18913#bib.bib40); Zuoet al\.,[2025](https://arxiv.org/html/2604.18913#bib.bib41); Rezaeiet al\.,[2025](https://arxiv.org/html/2604.18913#bib.bib42)\)\.

Table 1:Comparison of retrieval systems and libraries\. Matrix\-based indicates the use of linear\-algebra primitives for retrieval\.Note:Entries reflect the default design under a single\-machine setting\. Scalability indicates the ability to process graphs that exceed single\-machine memory limits\. Unavailable features can be achieved with additional processing, at the cost of time and memory\.![Refer to caption](https://arxiv.org/html/2604.18913v1/LogosKG.png)Figure 1:Overview of the LogosKG retrieval framework\. LogosKG adopts a linear algebra–based retrieval method that supports both small and large KGs\. For large graphs, LogosKG incorporates graph partitioning, cross\-graph routing, and on\-demand caching to enable efficient multi\-hop retrieval across distributed subgraphs\. The retrieved evidence can provide knowledge\-grounded support for medical diagnosis generation\.A fundamental operation of KGs is*multi\-hop retrieval*, which connects distant concepts through intermediate entities and relations\. Traditional graph traversal algorithms such as depth\-first search \(DFS\) and breadth\-first search \(BFS\) can handle small graphs but quickly become infeasible as graph size grows, with cost scaling asO​\(\|V\|\+\|E\|\)O\(\|V\|\+\|E\|\)and reachable entities growing exponentially with hop depth\.Memoryis another major bottleneck: for instance, biomedical KGs used in our experiments \(UMLSBodenreider \([2004](https://arxiv.org/html/2604.18913#bib.bib29)\), 407K nodes, 3\.4M edges; and the100×100\\timeslargerPubMedKGXuet al\.\([2020](https://arxiv.org/html/2604.18913#bib.bib30),[2025](https://arxiv.org/html/2604.18913#bib.bib47)\), 54\.4M nodes, 86\.5M edges\) occupy 1\.5 GB and 23\.5 GB of memory even before traversal\. A two\-hop expansion from a high\-degree concept in UMLS \(on average≈\\approx33k 1\-hop neighbors\) can involve over10910^\{9\}reachable edges, consuming tens of gigabytes of memory to materialize adjacency information\. Such exponential growth in traversal and storage defines thecore systems challengein scaling multi\-hop retrieval, forcing prior work to operate on limited subgraphsGaoet al\.\([2025](https://arxiv.org/html/2604.18913#bib.bib46)\); Changet al\.\([2020](https://arxiv.org/html/2604.18913#bib.bib45)\)\.

Numerous systems have been developed to improve retrieval efficiency \(Table[1](https://arxiv.org/html/2604.18913#S1.T1)\) emphasizing three dimensions: \(1\)matrix\-basedgraph representation replacing pointer\-based data structures with matrix or tensor operations for vectorized computation that maps naturally onto parallel hardware such as multi\-core CPUs or GPUs \(e\.g\., GraphBLAS\-based systems\); \(2\)*scalability*, supported by mechanisms such as graph partitioning to handle billion\-edge graphs \(e\.g\., DGL, PyG\); and \(3\)*path reconstruction*enabling interpretable reasoning by recovering intermediate entities and relations \(e\.g\., Neo4j, TigerGraph\)\. However, most systems optimize only one or two of these aspects and often rely on distributed infrastructures rather than single\-device efficiency\.

Our Approach\.To achieve scalable and interpretable KG retrieval, we presentLogosKG, anovelhardware\-aligned framework that rethinks graph traversal at the system level \(as shown in Figure[1](https://arxiv.org/html/2604.18913#S1.F1)\)\. While symbolic graph reasoning has been explored in prior workCohenet al\.\([2020](https://arxiv.org/html/2604.18913#bib.bib12)\),LogosKGextends this methodology into a unified, end\-to\-end system that makes high\-hop traversal practical on large, densely connected KGs using single\-device hardware, allowing contiguous data layouts and kernel\-level parallelism on CPUs and GPUs\. For large graphs,LogosKGimplements degree\-aware partitioning and cross\-graph routing guided by memory\-locality principles, while on\-demand caching further reduces I/O overhead, achieving𝒪​\(\|ℰ\|​log⁡\|ℰ\|\+\|𝒯\|\)\\mathcal\{O\}\(\|\\mathcal\{E\}\|\\log\|\\mathcal\{E\}\|\+\|\\mathcal\{T\}\|\)complexity \(whereℰ\\mathcal\{E\}is the set of entities and𝒯\\mathcal\{T\}is the set of triples\)\. Finally,LogosKGstores intermediate entities and relations that enable path reconstruction\. Together, these innovations transform a theoretical formulation into a practical and scalable framework for large\-scale KG retrieval\.

We evaluateLogosKGagainst existing libraries and systems \(Table[1](https://arxiv.org/html/2604.18913#S1.T1)\) across retrieval efficiency, scalability, and interpretability\. Experiments focus on large, semantically rich biomedical KGs, which present realistic challenges for dense connectivity, heterogeneous relations, and interpretable reasoning\. Although the experiments use biomedical data,LogosKGis domain\-agnostic and applicable to any large structured graph\.

LogosKGremoves a fundamental system bottleneck in scalable high\-hop retrieval, thereby enabling the study of LLM reasoning over high\-hop KGs, independent of whether downstream selection or reasoning components are learned or nonlearned\. We instantiate this capacity through a systematic study of the KG\-LLM setup for clinical diagnosis prediction, using a two\-round interaction setup to examine how LLM responds to KG structure under increasing hop depths\. We summarize the main contributions of this paper as follows:

- •Scalable system capability for large KG traversal: We presentLogosKG, a hardware\-aligned framework that enables deterministic, interpretable high\-hop retrieval at scale on single\-device hardware \(§[3](https://arxiv.org/html/2604.18913#S3)\)\.
- •Comprehensive system evaluation:We benchmark retrieval fidelity, efficiency, and scalability across CPU and GPU baselines \(§[5](https://arxiv.org/html/2604.18913#S5)\)\.
- •Analysis of KG\-LLM interaction under high\-hop regimes:LeveragingLogosKG, we perform a systematic study of how LLM predictions interact with deep KG structures through a two\-round interaction investigation \(§[6](https://arxiv.org/html/2604.18913#S6)\)\.

LogosKGserves as a general systems backbone for high\-hop KG retrieval and can support both learned and non\-learned refinement and reasoning strategies at scale\. While KG\-LLM interaction is a complex research question in its own right, we include analyses of both non\-learned and learned high\-hop KG\-LLM designs in the Appendix \(§[A\.5](https://arxiv.org/html/2604.18913#A1.SS5)–[A\.7](https://arxiv.org/html/2604.18913#A1.SS7)\), illustrating thatLogosKGmakes such studies feasible\.

## 2Related Work

Existing systems and libraries can be classified by their architecture, ranging from database\-backed engines and computation\-focused libraries to graph analysis tools and GPU\-based frameworks\.Database\-backed enginessuch as Neo4j and TigerGraph\(Deutschet al\.,[2019](https://arxiv.org/html/2604.18913#bib.bib20)\)provide expressive query languages but require significant infrastructure for sharding and incur runtime overhead from query parsing pipelines and transaction logs\.Computation\-focused librariessuch as GraphBLAS\(Kepneret al\.,[2016](https://arxiv.org/html/2604.18913#bib.bib22)\)use sparse matrix operations to make multi\-hop retrieval efficient, yet lack native support for full path reconstruction due to the loss of edge provenance during aggregation\.Graph analysis tools, such as igraph\(Csardi and Nepusz,[2006](https://arxiv.org/html/2604.18913#bib.bib21)\), NetworkX\(Hagberget al\.,[2008](https://arxiv.org/html/2604.18913#bib.bib27)\), and SNAP\(Leskovec and Sosič,[2016](https://arxiv.org/html/2604.18913#bib.bib23)\), offer flexible APIs but rely on memory\-bound pointer\-chasing algorithms that do not scale effectively\. Finally,GPU\-based frameworkssuch as cuGraph, DGL\(Wanget al\.,[2019](https://arxiv.org/html/2604.18913#bib.bib24)\), and PyG\(Fey and Lenssen,[2019](https://arxiv.org/html/2604.18913#bib.bib26)\)enable fast single\-machine computation but prioritize dense tensor\-based training over retrieval; their reliance on classical search backends limits efficiency for multi\-hop reasoning\.

### 2\.1KGs as Verifiers for LLMs

LLMs are prone to hallucinations and unverified claims, motivating research on KG\-based verification and fact\-checking\. Recent methods leverage KGs to ground textual claims in structured evidence and construct multi\-hop reasoning chains that link claims to supporting facts\. Examples include FactKG\(Kimet al\.,[2023](https://arxiv.org/html/2604.18913#bib.bib10)\)and GraphCheck\(Chenet al\.,[2025](https://arxiv.org/html/2604.18913#bib.bib14)\)for long\-context fact\-checking, ClaimVer\(Dammuet al\.,[2024](https://arxiv.org/html/2604.18913#bib.bib7)\)and Verify\-in\-the\-Graph\(Phamet al\.,[2025b](https://arxiv.org/html/2604.18913#bib.bib13)\)for explainable evidence attribution and entity disambiguation, and GraphFC\(Huanget al\.,[2025](https://arxiv.org/html/2604.18913#bib.bib15)\)and FactCheck\(Shamiet al\.,[2025](https://arxiv.org/html/2604.18913#bib.bib16)\)for integrating graph reasoning with LLM\-based verification\. In contrast, our work exposes the raw topology of KGs and reveals a structural gap between symbolic knowledge organization and neural reasoning\.

## 3LogosKG

### 3\.1Problem Statement

Knowledge Graph\.A*KG*is defined as a directed multi\-relational graph

𝒢=\(ℰ,ℛ,𝒯\),\\mathcal\{G\}=\(\\mathcal\{E\},\\mathcal\{R\},\\mathcal\{T\}\),whereℰ\\mathcal\{E\}is the set of entities,ℛ\\mathcal\{R\}is the set of relation types, and𝒯⊆ℰ×ℛ×ℰ\\mathcal\{T\}\\subseteq\\mathcal\{E\}\\times\\mathcal\{R\}\\times\\mathcal\{E\}is the set of observed triples\. Each triple\(es,r,eo\)∈𝒯\(e\_\{s\},r,e\_\{o\}\)\\in\\mathcal\{T\}denotes that subject entityes∈ℰe\_\{s\}\\in\\mathcal\{E\}is linked to object entityeo∈ℰe\_\{o\}\\in\\mathcal\{E\}through relationr∈ℛr\\in\\mathcal\{R\}\.

kk\-hop Retrieval\.Given a query𝐪∈ℰ\\mathbf\{q\}\\in\\mathcal\{E\}consisting of a set of entities, the goal ofkk\-hop retrieval is to identify all entities reachable from anyeq∈𝐪e\_\{q\}\\in\\mathbf\{q\}withinkkrelational steps\. In practice, querying large KGs can be time\-consuming\. The task is to retrievekk\-hop entities in large KGs while keeping query latency as low as possible\.

### 3\.2KGs Decomposition

To support efficientkk\-hop retrieval, a KG could be represented using three sparse incidence matrices encoding subjects, objects, and relations\(Cohenet al\.,[2020](https://arxiv.org/html/2604.18913#bib.bib12)\)\. This decomposition transforms heavy graph traversal into lightweight sparse matrix operations, as shown in Figure[1](https://arxiv.org/html/2604.18913#S1.F1)\.

Subject matrix\.The*subject matrix*𝐒𝐔𝐁∈\{0,1\}\|ℰ\|×\|𝒯\|\\mathbf\{SUB\}\\in\\\{0,1\\\}^\{\|\\mathcal\{E\}\|\\times\|\\mathcal\{T\}\|\}is defined as:

\[𝐒𝐔𝐁\]i,t=\{1,ifeiis the subject oft,0,otherwise\.\[\\mathbf\{SUB\}\]\_\{i,t\}=\\begin\{cases\}1,&\\text\{if $e\_\{i\}$ is the subject of $t$\},\\\\ 0,&\\text\{otherwise\}\.\\end\{cases\}\(1\)
whereeie\_\{i\}denotes an entity andtta triplet, with rows as entities and columns as triplets\.

Object matrix\.The*object matrix*𝐎𝐁𝐉∈\{0,1\}\|𝒯\|×\|ℰ\|\\mathbf\{OBJ\}\\in\\\{0,1\\\}^\{\|\\mathcal\{T\}\|\\times\|\\mathcal\{E\}\|\}is defined as:

\[𝐎𝐁𝐉\]t,j=\{1,ifejis the object oft,0,otherwise\.\[\\mathbf\{OBJ\}\]\_\{t,j\}=\\begin\{cases\}1,&\\text\{if $e\_\{j\}$ is the object of $t$\},\\\\ 0,&\\text\{otherwise\}\.\\end\{cases\}\(2\)
whereeje\_\{j\}is an entity andtta triplet, with rows as triplets and columns as entities\.

Relation matrix\.The*relation matrix*𝐑𝐄𝐋∈\{0,1\}\|𝒯\|×\|ℛ\|\\mathbf\{REL\}\\in\\\{0,1\\\}^\{\|\\mathcal\{T\}\|\\times\|\\mathcal\{R\}\|\}encodes the relation type of each triplet, and is defined as:

\[𝐑𝐄𝐋\]t,r=\{1,iftuses relationr,0,otherwise\.\[\\mathbf\{REL\}\]\_\{t,r\}=\\begin\{cases\}1,&\\text\{if $t$ uses relation $r$\},\\\\ 0,&\\text\{otherwise\}\.\\end\{cases\}\(3\)wherettdenotes a triplet andrra relation type\. Each row corresponds to a triplet and each column to a relation, enabling recovery of relation paths in multi\-hop retrieval\.

### 3\.3Efficient Retrieval

One\-hop retrieval\.Define query vector as𝐪\(0\)∈\{0,1\}1×\|ℰ\|\\mathbf\{q\}^\{\(0\)\}\\in\\\{0,1\\\}^\{1\\times\|\\mathcal\{E\}\|\}, where𝐪\(0\)​\[i\]=1\\mathbf\{q\}^\{\(0\)\}\[i\]=1if entityeie\_\{i\}is included in the query\. Multiplying by𝐒𝐔𝐁\\mathbf\{SUB\}activates the triplets starting from these entities, and multiplying further by𝐎𝐁𝐉\\mathbf\{OBJ\}yields the reachable entities:

𝐪\(0\)⋅𝐒𝐔𝐁\\displaystyle\\mathbf\{q\}^\{\(0\)\}\\cdot\\mathbf\{SUB\}↦𝐭\(1\)​\(active triplets\),\\displaystyle\\;\\mapsto\\;\\mathbf\{t\}^\{\(1\)\}\(\\text\{active triplets\}\),𝐭\(1\)⋅𝐎𝐁𝐉\\displaystyle\\mathbf\{t\}^\{\(1\)\}\\cdot\\mathbf\{OBJ\}↦𝐪\(1\)​\(active entities\)\.\\displaystyle\\;\\mapsto\\;\\mathbf\{q\}^\{\(1\)\}\(\\text\{active entities\}\)\.
Formally,

𝐪\(1\)=𝐪\(0\)⋅𝐒𝐔𝐁⋅𝐎𝐁𝐉\.\\mathbf\{q\}^\{\(1\)\}=\\mathbf\{q\}^\{\(0\)\}\\cdot\\mathbf\{SUB\}\\cdot\\mathbf\{OBJ\}\.\(4\)
Repeating this operationkktimes yieldskk\-hop retrieval, denoted as:𝐪\(k\)=𝐪\(0\)⋅\(𝐒𝐔𝐁⋅𝐎𝐁𝐉\)k\\mathbf\{q\}^\{\(k\)\}=\\mathbf\{q\}^\{\(0\)\}\\cdot\(\\mathbf\{SUB\}\\cdot\\mathbf\{OBJ\}\)^\{k\}, where𝐪\(k\)∈\{0,1\}1×\|ℰ\|\\mathbf\{q\}^\{\(k\)\}\\in\\\{0,1\\\}^\{1\\times\|\\mathcal\{E\}\|\}and nonzero entries indicate the entities reachable exactly atkksteps\.

Path reconstruction\.At any hophh, we retrieve the activated triplets by

𝐭\(h\)=𝐪\(h−1\)⋅𝐒𝐔𝐁\.\\mathbf\{t\}^\{\(h\)\}=\\mathbf\{q\}^\{\(h\-1\)\}\\cdot\\mathbf\{SUB\}\.\(5\)
The set of nonzero indices is

Th=\{t∣𝐭\(h\)​\[t\]=1\}\.T\_\{h\}=\\\{\\,t\\mid\\mathbf\{t\}^\{\(h\)\}\[t\]=1\\,\\\}\.\(6\)
For eacht∈Tht\\in T\_\{h\}, we retrieve the subject entity, object entity, and relation of the triple directly from the incidence matrices:

sh\\displaystyle s\_\{h\}=\{s∣\[𝐒𝐔𝐁\]i,t=1\},\\displaystyle=\\\{\\,s\\mid\[\\mathbf\{SUB\}\]\_\{i,t\}=1\\,\\\},rh\\displaystyle r\_\{h\}=\{r∣\[𝐑𝐄𝐋\]t,r=1\},\\displaystyle=\\\{\\,r\\mid\[\\mathbf\{REL\}\]\_\{t,r\}=1\\,\\\},eh\\displaystyle e\_\{h\}=\{o∣\[𝐎𝐁𝐉\]t,j=1\}\.\\displaystyle=\\\{\\,o\\mid\[\\mathbf\{OBJ\}\]\_\{t,j\}=1\\,\\\}\.\(7\)
We build the pathsh→rhehs\_\{h\}\\xrightarrow\{r\_\{h\}\}e\_\{h\}, and ifehe\_\{h\}also appears as a subject, we extend it at hoph\+1h\{\+\}1\. Repeating this yields complete paths of lengthkk\.

Algorithm 1Cross\-graphkk\-Hop Retrieval with On\-Demand Caching0:Initial query vector

𝐪\(0\)\\mathbf\{q\}^\{\(0\)\}, hop count

kk, subgraphs

\{𝒢i\}i=1M\\\{\\mathcal\{G\}\_\{i\}\\\}\_\{i=1\}^\{M\}with

\(𝐒𝐔𝐁i,𝐎𝐁𝐉i,𝐑𝐄𝐋i\)\(\\mathbf\{SUB\}\_\{i\},\\mathbf\{OBJ\}\_\{i\},\\mathbf\{REL\}\_\{i\}\), metadata

PP, cache

CC
0:Query vector

𝐪\(k\)\\mathbf\{q\}^\{\(k\)\}
1:for

ℓ=0\\ell=0to

k−1k\-1do

2:Route nonzero entries of

𝐪\(ℓ\)\\mathbf\{q\}^\{\(\\ell\)\}to subgraphs via

PP
3:Initialize

𝐪\(ℓ\+1\)←𝟎\\mathbf\{q\}^\{\(\\ell\+1\)\}\\leftarrow\\mathbf\{0\}
4:for allsubgraphs

𝒢i\\mathcal\{G\}\_\{i\}with active entitiesdo

5:Load

𝒢i\\mathcal\{G\}\_\{i\}into cache

CCif absent \(evict LRU if full\)

6:Restrict

𝐪\(ℓ\)\\mathbf\{q\}^\{\(\\ell\)\}to local subvector

𝐪i\(ℓ\)\\mathbf\{q\}^\{\(\\ell\)\}\_\{i\}
7:Compute local update

𝐪i\(ℓ\+1\)=𝐪i\(ℓ\)⋅𝐒𝐔𝐁i⋅𝐎𝐁𝐉i\\mathbf\{q\}^\{\(\\ell\+1\)\}\_\{i\}=\\mathbf\{q\}^\{\(\\ell\)\}\_\{i\}\\cdot\\mathbf\{SUB\}\_\{i\}\\cdot\\mathbf\{OBJ\}\_\{i\}
8:Map

𝐪i\(ℓ\+1\)\\mathbf\{q\}^\{\(\\ell\+1\)\}\_\{i\}back to global indices

9:

𝐪\(ℓ\+1\)←𝐪\(ℓ\+1\)∨𝐪i\(ℓ\+1\)\\mathbf\{q\}^\{\(\\ell\+1\)\}\\leftarrow\\mathbf\{q\}^\{\(\\ell\+1\)\}\\lor\\mathbf\{q\}^\{\(\\ell\+1\)\}\_\{i\}
10:endfor

11:endfor

12:return

𝐪\(k\)\\mathbf\{q\}^\{\(k\)\}

### 3\.4Scalable Retrieval

Large\-scale KGs can contain hundreds of millions or even billions of triplets, making it infeasible to load the entire graph into memory\. To address this, we design a hierarchical system with degree\-aware partitioning, cross\-graph retrieval, and on\-demand caching\. Globally, queries are distributed across subgraphs; locally, retrieval within each subgraph uses sparse matrix operations\.

Specifically, a KG is partitioned into balanced subgraphs, which are processed independently, with a mapping table that tracks each entity’s subgraph assignment\. During retrieval, queries are routed to their respective subgraphs for local multi\-hop retrieval \(§[3\.2](https://arxiv.org/html/2604.18913#S3.SS2)\), and results are merged\. On\-demand caching loads only the required subgraphs into memory, keeping the rest on disk\. This step is the key to efficient retrieval over billion\-scale KG on limited hardware\.

Degree\-aware graph partitioning\.A KG can be partitioned into disjoint subgraphs\{𝒢i=\(ℰi,ℛi,𝒯i\)\}i=1m\\\{\\mathcal\{G\}\_\{i\}=\(\\mathcal\{E\}\_\{i\},\\mathcal\{R\}\_\{i\},\\mathcal\{T\}\_\{i\}\)\\\}\_\{i=1\}^\{m\}, where each𝒢i\\mathcal\{G\}\_\{i\}contains a subset of entities, relations, and triplets\. Subject entities are assigned in a degree\-aware manner so that high\-degree subject entities are distributed evenly, avoiding bottlenecks caused by imbalance\. To preserve KG structures, all triplets sharing the same subject entity are assigned to the same subgraph\. The procedure runs inO​\(\|ℰ\|​log⁡\|ℰ\|\+\|𝒯\|\)O\(\|\\mathcal\{E\}\|\\log\|\\mathcal\{E\}\|\+\|\\mathcal\{T\}\|\)time, including finding relations and sorting entities by degrees inO​\(\|ℰ\|​log⁡\|ℰ\|\+\|𝒯\|\)O\(\|\\mathcal\{E\}\|\\log\|\\mathcal\{E\}\|\+\|\\mathcal\{T\}\|\)time and assigning triplets to subgraphs inO​\(\|𝒯\|\)O\(\|\\mathcal\{T\}\|\)time\. We also maintain a metadata mapP:ℰ→\{1,…,m\}P:\\mathcal\{E\}\\to\\\{1,\\ldots,m\\\}that records the partition assignment of each subject entity for efficient cross\-partition retrieval\. For each subgraph𝒢i\\mathcal\{G\}\_\{i\}, we build local incidence matrices𝐒𝐔𝐁i\\mathbf\{SUB\}\_\{i\},𝐎𝐁𝐉i\\mathbf\{OBJ\}\_\{i\}, and𝐑𝐄𝐋i\\mathbf\{REL\}\_\{i\}to support efficient retrieval within the partition\.

Our framework is not limited to this partitioning algorithm\. In fact, LogosKG can support any partitioning strategy and integrate them with the following cross\-graph routing and on\-demand caching mechanisms, although retrieval latency may vary\.

Cross\-subgraph retrieval\.Given a query entity vector𝐪\(0\)\\mathbf\{q\}^\{\(0\)\}, we first group entities by their assigned subgraphs using the metadata mapPP\. For each subgraph𝒢i\\mathcal\{G\}\_\{i\}, we build a local query vector𝐪i\(0\)\\mathbf\{q\}^\{\(0\)\}\_\{i\}representing the subset of entities assigned to𝒢i\\mathcal\{G\}\_\{i\}\. Retrieval is then carried out independently within each subgraph using its local incidence matrices𝐒𝐔𝐁i\\mathbf\{SUB\}\_\{i\},𝐎𝐁𝐉i\\mathbf\{OBJ\}\_\{i\}, and𝐑𝐄𝐋i\\mathbf\{REL\}\_\{i\}\. For any hopkk, the update step follows the same principle as in the single\-graph case:

𝐭i\(k\)=𝐪i\(k\)⋅𝐒𝐔𝐁i,\\mathbf\{t\}^\{\(k\)\}\_\{i\}=\\mathbf\{q\}^\{\(k\)\}\_\{i\}\\cdot\\mathbf\{SUB\}\_\{i\},\(8\)𝐪i\(k\+1\)=\(𝐪i\(k\)⋅𝐒𝐔𝐁i\)⋅𝐎𝐁𝐉i\.\\mathbf\{q\}^\{\(k\+1\)\}\_\{i\}=\(\\mathbf\{q\}^\{\(k\)\}\_\{i\}\\cdot\\mathbf\{SUB\}\_\{i\}\)\\cdot\\mathbf\{OBJ\}\_\{i\}\.\(9\)Entities𝐪i\(k\+1\)\\mathbf\{q\}^\{\(k\+1\)\}\_\{i\}from all subgraphs are merged into a global query vector𝐪\(k\+1\)\\mathbf\{q\}^\{\(k\+1\)\}, then redistributed for the next hop\. Repeating thiskktimes reconstructs thekk\-hop neighborhood while limiting computation to accessed subgraphs\.

On\-demand caching\.This mechanism makes sure subgraphs are loaded only when required\. It avoids memory blow\-up but introduces additional I/O overhead, since not all subgraphs needed for a query are guaranteed to be in memory\.

An in\-memory cache of fixed capacitynnis implemented and capable of storing at mostnnsubgraphs, managed under a least\-recently\-used \(LRU\) policy\. When a subgraph is requested, it is reused if present in the cache, or otherwise loaded from disk and inserted by evicting the least recently accessed subgraph\. Each subgraph is stored on disk in a sparse format containing the incidence matrices\. Cache hits require only sparse matrix multiplications, while cache misses incur the additional cost of disk I/O\.

Lethhdenote the cache hit rate,τmm\\tau\_\{\\text\{mm\}\}the time for in\-memory sparse matrix multiplication, andτio\\tau\_\{\\text\{io\}\}the average disk load time\. The expected retrieval cost per subgraph is

𝔼​\[τretrieval\]=h⋅τmm\+\(1−h\)⋅\(τmm\+τio\)\.\\mathbb\{E\}\[\\tau\_\{\\text\{retrieval\}\}\]=h\\cdot\\tau\_\{\\text\{mm\}\}\+\(1\-h\)\\cdot\(\\tau\_\{\\text\{mm\}\}\+\\tau\_\{\\text\{io\}\}\)\.\(10\)
We optimize batch processing for better cache efficiency by grouping queries with similar subgraph requirements\. Each query’s subgraphs are identified viaPP, queries are reordered for joint processing, and results are restored afterward\. This improves temporal locality, allowing subgraph reuse and reducing cache misses and I/O overhead\.

Overall pipeline\.The retrieval process begins with an initial query vector𝐪\(0\)\\mathbf\{q\}^\{\(0\)\}\. At each hopkk, we \(i\) map the active entities in𝐪\(h\)\\mathbf\{q\}^\{\(h\)\}to their subgraphs usingPP, \(ii\) perform local retrieval within each subgraph using incidence matrices, \(iii\) merge the local results into the next global query vector𝐪\(h\+1\)\\mathbf\{q\}^\{\(h\+1\)\}, and \(iv\) repeat forkkhops\. The procedure is summarized in Algorithm[1](https://arxiv.org/html/2604.18913#alg1)\.

Implementation DetailsWe implementLogosKGwith three computational backends: Numba, SciPy, and Torch, where the Torch backend supports both CPU and GPU execution\. Experiments were conducted on a HIPAA\-compliant Linux server with Ubuntu 22\.04 system, dual AMD EPYC 9454 48\-Core CPUs \(192 threads\), 256 GB RAM, and two NVIDIA H100 NVL GPUs \(94 GB VRAM each\)\.

Table 2:Retrieval efficiency comparison across hops\. Timeout limits are fixed at 2000, 4000, 6000, 8000, and 10000 ms for 1–5 hops, respectively\. All methods are run under the same CPU workload for fair comparison\. For each hop, the best method is shown in bold and the second\-best is underlined\.FactorValueQT \(ms\)LoadsEvicts*Exp\. 1: hops*\(Numba, cache sizen=16n=16, batch size=50\)hops13410\.90160hops21610\.78160hops36114\.69160hops419592\.08160hops562726\.25160*Exp\. 2: batch size*\(Numba, cache sizen=16n=16, hopsk=2k=2\)batch size1100912\.09120batch size105489\.45160batch size251365\.09160batch size501499\.39160batch size1001444\.68160batch size1501483\.49160*Exp\. 3: cache size*\(Numba, hopsk=2k=2, batch size=50\)cache size1441870\.1930103009cache size2419436\.5929182916cache size4384086\.4226592655cache size8304066\.0019671959cache size164037\.69160*Exp\. 4: backend*\(cache sizen=16n=16, hopsk=2k=2, batch size=50\)backendNumba4143\.16160backendScipy3889\.86160backendTorch\-CPU245311\.21160backendTorch\-GPU6409\.32160

Table 3:Scalability of LogosKG\-Large on the PKG across hops, batch sizes, cache sizes, and backends\.

## 4Dataset and Setup

Our results are organized into two parts: \(1\)LogosKGsystem evaluation, focusing on retrieval accuracy, efficiency, and scalability; and \(2\) an analysis of KG\-LLM interaction in high\-hop KG regimes, using clinical diagnosis prediction as a representative problem domain\.

We examine three biomedical KGs in our experiments:UMLS\(Bodenreider,[2004](https://arxiv.org/html/2604.18913#bib.bib29)\), a large\-scale biomedical ontology comprising 407K nodes and 3\.4M edges across 133 semantic types; thePubMed Knowledge Graph \(PKG\)\(Xuet al\.,[2020](https://arxiv.org/html/2604.18913#bib.bib30),[2025](https://arxiv.org/html/2604.18913#bib.bib47)\), a massive citation network connecting 54\.4M nodes \(including authors, publications, and institutions\) via 86\.5M edges; andPrimeKG\(Chandaket al\.,[2023](https://arxiv.org/html/2604.18913#bib.bib11)\), which integrates 20 high\-quality biomedical resources to describe 17,080 diseases with≈\\approx4M relationships\.

We include two clinical datasets that connect the KGs under study to real\-world diagnostic applications\. ProbSum\(Gaoet al\.,[2023](https://arxiv.org/html/2604.18913#bib.bib32)\)contains de\-identified clinical notes with findings and diagnoses, supplying entity mentions that serve as realistic query inputs for retrieval evaluation\. DDXPlus\(Fansi Tchangoet al\.,[2022](https://arxiv.org/html/2604.18913#bib.bib33)\)offers large\-scale symptom\-diagnosis pairs and is used in the KG\-LLM study to assess how KG structure aligns with LLM\-predicted diagnoses\. Retrieval experiments use UMLS and PKG with ProbSum, while the KG\-LLM case study uses UMLS and PrimeKG with ProbSum and DDXPlus\.

For the second part of the paper where we explore KG\-LLMs, we include the following instruction\-tuned, widely used LLMs: Qwen\-2\.5\-7B\-Instruct\(Qwenet al\.,[2025](https://arxiv.org/html/2604.18913#bib.bib51)\), Llama\-3\.1\-8B\-Instruct\(Dubeyet al\.,[2024](https://arxiv.org/html/2604.18913#bib.bib52)\), GPT 4\.1\(OpenAI,[2025b](https://arxiv.org/html/2604.18913#bib.bib56)\), and GPT\-5\-mini\(OpenAI,[2025a](https://arxiv.org/html/2604.18913#bib.bib57)\)\. We employ GPT\-5\-mini as the LLM\-as\-a\-Judge and for the supplementary experiments detailed in Appendix[A\.6](https://arxiv.org/html/2604.18913#A1.SS6)\. All open\-sourced LLMs are running on the GPU server\. We use GPT\-4\.1 and GPT\-5\-mini via HIPAA\-compliant Microsoft Azure OpenAI endpoint, thereby complying with the ProbSum Data Use Agreement for MIMIC\-III derived contentJohnsonet al\.\([2016](https://arxiv.org/html/2604.18913#bib.bib50)\)\.

## 5LogosKGSystem Evaluation

We evaluate LogosKG and baselines along three dimensions:Accuracymeasures whether retrieved entities match ground truth across hops;Efficiencyis assessed by query time and timeout rates;Scalabilityexamines how performance changes of LogosKG under different settings, evaluating the ability to handle large KGs\.

BaselinesWe compareLogosKGagainst a diverse set of widely used graph retrieval systems, including database engines \(Neo4j\), graph analysis toolkits \(igraph, NetworkX, graph\-tool, SNAP\), matrix\-based libraries \(GraphBLAS and its Python implementation\), and GPU\-accelerated frameworks \(cuGraph, DGL, PyG\)\. Together, these baselines cover the major design paradigms for KG retrieval, allowing comprehensive evaluation of efficiency, scalability, and retrieval fidelity\.

AccuracyOn a set of queries, we compare the retrieved results fromLogosKGfamily with CPU\- and GPU\-based baselines across 1–5 hops\. This result is measured by Jaccard similarity, with 1\.0 denoting exact agreement\. All comparisons yield a perfect Jaccard score of 1\.0, confirming that retrieval is deterministic given the KG structure\. We neglect the detailed results here and present them in Table[4](https://arxiv.org/html/2604.18913#A1.T4)\. This validatesLogosKGas a faithful and reliable replacement for existing engines\.

EfficiencyFor each method, we report the averagequery time \(QT\)across all test samples and thetimeout rate \(TR\)per hop, defined as the proportion of queries exceeding the hop\-specific limit\. QT reflects the latency of a method, while TR captures its responsiveness under practical constraints\. These metrics provide a clear view of efficiency betweenLogosKGand the baselines\.

Table[2](https://arxiv.org/html/2604.18913#S3.T2)reports QT and TR for 1–5 hops\. Classical CPU libraries \(NetworkX, igraph, SNAP, GraphBLAS\) perform well at shallow hops but degrade rapidly with depth\. Neo4j remains slow with consistently high TR\. GPU\-based methods \(graph\-tool, cuGraph, DGL, PyG\) scale roughly linearly: graph\-tool, cuGraph, and DGL show higher latency, while PyG starts lower\. In contrast, theLogosKGfamily scales robustly: Numba and Torch\-GPU remain under 200 ms with zero TR, and partitioned LogosKG\-Large variants maintain moderate TR even at deeper hops\. Torch\-CPU performs poorly due to the lack of dedicated optimization\. Overall,LogosKGachieves efficient and reliable multi\-hop retrieval\.

ScalabilityWe evaluate LogosKG\-Large on the PKG using the degree\-aware partitioning strategy\. Synthetic queries contain 1–20 randomly selected entities and are executed at depths of 1–5 hops\. The cache sizeNNdetermines how many subgraphs remain in memory, while loads and evictions record swaps between disk and memory\. We measure QT under varying hops, batch sizes, cache sizes, and backends\. Cache activities are tracked through the number of loads and evictions\.

As shown in Table[3](https://arxiv.org/html/2604.18913#S3.T3), QT increases with hop count as deeper expansions involve more entities, while larger batches reduce latency due to batch optimization\. Cache size has the largest impact: small caches trigger frequent swaps, increasing latency, whereas larger caches cut these operations and improve QT\. Among backends, Numba, SciPy, and Torch\-GPU are fastest, while Torch\-CPU remains slower due to limited parallelization\.

Overall performanceThese experiments confirm thatLogosKGdelivers deterministic accuracy, strong efficiency across CPU and GPU settings, and scalable performance on billion\-edge graphs, establishing it as a reliable and hardware\-optimized solution for large\-scale KG retrieval\.

## 6Interaction Regimes between High\-Hop KGs and LLM for Diagnosis

![Refer to caption](https://arxiv.org/html/2604.18913v1/table5_visualization.png)Figure 2:Hop\-distance distribution of pair entities for the ProbSum and DDXPlus dataset on UMLS and PrimeKG\.![Refer to caption](https://arxiv.org/html/2604.18913v1/f1_by_hops_zeroshot.png)Figure 3:Performance comparison of KG filtering \(Round 1\) and enhancement \(Round 2\) across varying hop distances \(k=1k=1tok=5k=5\) on ProbSum and DDXPlus datasets using UMLS and PrimeKG\. F1\-score metrics are shown forGPT\-4\.1, Qwen\-2\.5\-7B\-Instruct, and Llama\-3\.1\-8B\-Instructin the zero\-shot setting, with baseline performance included for reference\.![Refer to caption](https://arxiv.org/html/2604.18913v1/pdsqi_umls_3models_shorter.png)Figure 4:PDSQI\-9 comparison for three models on DDXPlus dataset with UMLS \(kk=5\)\. Each subplot displays seven evaluation dimensions comparing Baseline, Round 1 \(KG\-filtered\), and Round 2 \(KG\-enhanced\) approaches\.Existing approaches that integrate KGs with LLMs often restrict reasoning to shallow neighborhoods due to the exponential growth of the search space\. However, many real\-world reasoning tasks require traversing distal, multi\-hop associations that lie beyond these local regions\. In the biomedical KG\-LLM setting, for instance, prior work often stops at 1\-2 hops \(and at most 3 hops\) as the higher\-hop expansion quickly becomes computationally infeasibleGaoet al\.\([2025](https://arxiv.org/html/2604.18913#bib.bib46)\); Zuoet al\.\([2025](https://arxiv.org/html/2604.18913#bib.bib41)\); Jianget al\.\([2024](https://arxiv.org/html/2604.18913#bib.bib60)\)\. Our work deviates from the “learning\-to\-rank" paradigm to explore a structural regime of scalable graph traversal, enabled byLogosKG, which makes high\-hop reasoning systematically accessible to LLMs\. Following prior workGaoet al\.\([2025](https://arxiv.org/html/2604.18913#bib.bib46)\); Zuoet al\.\([2025](https://arxiv.org/html/2604.18913#bib.bib41)\), we use clinical diagnosis as a representative setting to characterize how knowledge graph topology induces distinct interaction regimes between KGs and LLM reasoning\.

Topological landscape\.Figure[2](https://arxiv.org/html/2604.18913#S6.F2)presents hop distribution across the two KGs on the two datasets we are investigating\. On UMLS, gold entities can mostly be found within 1–2 hops, while PrimeKG shows a more long\-tail distribution up to 4–5 hops\. These structural differences directly govern how KG ontologies interact with LLM predictions\.

The precision\-recall tradeoffs\.We adopt a two\-round interaction paradigm to understand the interaction between KG topology and systematic precision\-recall behaviors of LLM\. In Round 1, the KG acts as a structural constraint that eliminates LLM hallucinations\. Because LogosKG can retrieve these neighbors with 100% deterministic fidelity \(J​a​c​c​a​r​d=1\.0Jaccard=1\.0\), the LLM is forced to align its prediction with the medical ontology\. In Round 2,LogosKGprovides the LLM with a long\-tail candidate space that was previously invisible, making the optimal “depth” not a fixed parameter\.

As shown in Figure[3](https://arxiv.org/html/2604.18913#S6.F3), for ProbSum, performance changes are relatively moderate across hop distances, with mostly limited gains from KG filtering and enhancement at early hops\. In contrast, DDXPlus shows much stronger sensitivity to hop expansion: performance generally improves as the hop distance increases, and Round 2 often provides clear gains beyond Round 1, especially with PrimeKG\. Importantly, this pattern holds across all three LLMs, despite differences in absolute performance, indicating that the observed regimes are driven by data and KG structure rather than by model\-specific artifacts\. These regimes are not tied to a particular retrieval implementation; rather, they were previously obscured because learning\-based models and classical graph libraries encounter a computational barrier at high hop distances\. By enabling scalable and deterministic high\-hop traversal,LogosKGserves as astructural backbonethat exposes a broader capability space for KG\-LLM interaction\.

Clinical reasoning quality\.We further compare the diagnoses with and without LogosKG \(kk=5\) using the clinically validated PDSQI\-9 rubric\. PDSQI\-9 is a nine\-criterion framework that evaluates diagnostic documentation along dimensions such as accuracy, comprehensibility, organization, and succinctness, with a HIPAA\-compliant Azure GPT\-5\-mini model serving as the LLM\-as\-a\-JudgeCroxfordet al\.\([2025b](https://arxiv.org/html/2604.18913#bib.bib49),[a](https://arxiv.org/html/2604.18913#bib.bib59)\)\. As shown in Figure[4](https://arxiv.org/html/2604.18913#S6.F4), incorporatingLogosKGleads to consistent improvements across several dimensions, particularly accuracy extractive, organization, comprehensibility, succinctness, and synthesis\. These gains primarily reflect changes in the structure and clarity of diagnostic reasoning rather than raw correctness alone\. By constraining predictions to KG\-supported evidence in Round 1,LogosKGsuppresses unsupported or redundant diagnoses, which directly benefits accuracy extractive, organization, comprehensibility, and succinctness\. Round 2 further improves synthesis by reintroducing clinically relevant conditions that the LLM may omit under unconstrained generation\. Improvements are observed consistently for all models, and are especially pronounced on the DDXPlus dataset, where deeper relational contexts are required\. Full results are provided in Appendix §[A\.4](https://arxiv.org/html/2604.18913#A1.SS4)\.

![Refer to caption](https://arxiv.org/html/2604.18913v1/case_study.png)Figure 5:Illustrative example of theLogosKGtwo\-round prediction pipeline on a clinical case from ProbSum\.\(A\)Clinical input consists of a patient progress note with the gold standard diagnosis\.\(B\)Round 1: The baseline LLM generates differential diagnoses, which are then filtered by validating against KG neighbors retrieved withink=1k=1hop\.\(C\)Round 2: Additional candidate diseases from the KG are presented to the LLM for selection, and the final prediction combines the filtered Round 1 diagnoses with the disease selected in Round 2\.\(D\)Summary table comparing baseline, Round 1 \(KG\-filtered\), Round 2 \(KG\-enhanced\), and gold standard diagnoses\.Additional analysis\.We provide results from fine\-tuned LLMs and similarity\-based refinement built onLogosKGin the Appendix \(Figure[7](https://arxiv.org/html/2604.18913#A1.F7)and Table[6](https://arxiv.org/html/2604.18913#A1.T6)\) for interested readers\. While using LogosKG for high\-hop retrieval followed by a fine\-tuned selector, or even a multi\-agent workflow, is an extension, our focus here is to analyze howLogosKGenables and characterizes the underlying structural interaction regimes because of its efficiency and scalability\.

### 6\.1Case Study of LLM Diagnoses withLogosKGFiltering and Enhancement

Figure[5](https://arxiv.org/html/2604.18913#S6.F5)shows howLogosKGworks in practice on a real clinical case\. The baseline LLM generates five diagnoses from the patient’s progress note, namelyAsthma, Nephrolithiasis, Hyperglycemia, Lactic acidosis, andHypovolemia\. When we filter these with the KG in Round 1,Asthma, HyperglycemiaandLactic acidosisremain, while the others fail to connect to clinical entities extracted from the note withink=1k=1hop\. This strict filtering removes unsupported predictions but also removes potentially relevant diagnoses\.

Round 2 addresses this limitation by finding eleven candidate diseases from the KG based on the patient’s clinical findings\. We then ask the LLM to select the most relevant candidates from this larger set\. The model identifies one important disease:Diabetes\. Notably, this matches well with the gold standard, which includesDKA and newly diagnosed diabetes, even though it does not appear in the baseline prediction\.

The final output combines the Round 1 filtered baseline diagnoses with the disease selected in Round 2, achieving much better coverage than either the baseline alone or the Round 1 result\. This example also illustrates the motivation of proposingLogosKG: KGs can expand the search space beyond what LLMs initially consider, while LLM reasoning helps select which candidates are actually relevant to the patient\.

## 7Conclusion

We presentedLogosKG, which is a hardware\-aligned framework for scalable and interpretable multi\-hop retrieval on large KGs\.LogosKGachieves efficient and deterministic retrieval across billion\-scale graphs\. Our analysis shows that KG topology strongly shapes how structured knowledge interacts with LLM reasoning, positioningLogosKGas both a high\-performance retrieval system and a foundation for future research on KG\-LLM integration\.

## Acknowledgments

This work is supported by U\.S\. National Library of Medicine, National Institute of Health, under award number R00LM014308\.

## Limitations

While LogosKG focuses on efficient multi\-hop retrieval, the current implementation can be further developed to support other types of graph analysis based on similar graph reasoning operations\. Future extensions may explore broader algorithmic capabilities while maintaining efficiency and scalability\. In addition, retrieval from large KGs often produces a substantial number of candidate entities at higher hop distances\. Further work is needed to refine these outputs, for example, by integrating more effective ranking or filtering strategies to highlight the most relevant results\.

Finally,LogosKGserves as a helpful graph retrieval tool, but it does not guarantee consistent performance improvements in every case, as success depends on both the completeness of the KG and the reasoning of the LLM\. In Round 1, we are limited by the graph’s coverage; if the KG lacks evidence for a specific symptom\-diagnosis pair, retrieval offers little benefit\. Similarly, Round 2 relies on the LLM accurately reselecting information\. If the model makes incorrect choices or hallucinates during this step, the potential for improvement is limited by the LLM’s own reasoning capabilities\.

## Ethical Statement

This study does not involve any human subjects\. All datasets and models used, including UMLS, PKG, PrimeKG, ProbSum, and DDXPlus, are publicly available and used strictly for research purposes under their respective data use agreements\. All experiments were conducted on HIPAA\-compliant servers, adhering to institutional and data governance policies\.

## References

- O\. Bodenreider \(2004\)The unified medical language system \(umls\): integrating biomedical terminology\.Nucleic acids research32\(suppl\_1\),pp\. D267–D270\.Cited by:[§1](https://arxiv.org/html/2604.18913#S1.p2.4),[§4](https://arxiv.org/html/2604.18913#S4.p2.1)\.
- X\. Cai, W\. Guo, M\. Zhao, Z\. Cui, and J\. Chen \(2023\)A knowledge graph\-based many\-objective model for explainable social recommendation\.IEEE Transactions on Computational Social Systems10\(6\),pp\. 3021–3030\.Cited by:[§1](https://arxiv.org/html/2604.18913#S1.p1.1)\.
- P\. Chandak, K\. Huang, and M\. Zitnik \(2023\)Building a knowledge graph to enable precision medicine\.Nature Scientific Data\.External Links:[Document](https://dx.doi.org/https%3A//doi.org/10.1038/s41597-023-01960-3),[Link](https://www.nature.com/articles/s41597-023-01960-3)Cited by:[§4](https://arxiv.org/html/2604.18913#S4.p2.1)\.
- D\. Chang, I\. Balažević, C\. Allen, D\. Chawla, C\. Brandt, and R\. A\. Taylor \(2020\)Benchmark and best practices for biomedical knowledge graph embeddings\.InProceedings of the conference\. Association for Computational Linguistics\. Meeting,Vol\.2020,pp\. 167\.Cited by:[§1](https://arxiv.org/html/2604.18913#S1.p2.4)\.
- Y\. Chen, H\. Liu, Y\. Liu, J\. Xie, R\. Yang, H\. Yuan, Y\. Fu, P\. Y\. Zhou, Q\. Chen, J\. Caverlee,et al\.\(2025\)GraphCheck: breaking long\-term text barriers with extracted knowledge graph\-powered fact\-checking\.arXiv preprint arXiv:2502\.16514\.Cited by:[§2\.1](https://arxiv.org/html/2604.18913#S2.SS1.p1.1)\.
- W\. W\. Cohen, H\. Sun, R\. A\. Hofer, and M\. Siegler \(2020\)Scalable neural methods for reasoning with a symbolic knowledge base\.InInternational Conference on Learning Representations,External Links:[Link](https://openreview.net/forum?id=BJlguT4YPr)Cited by:[§1](https://arxiv.org/html/2604.18913#S1.p4.3),[§3\.2](https://arxiv.org/html/2604.18913#S3.SS2.p1.1)\.
- E\. Croxford, Y\. Gao, E\. First, N\. Pellegrino, M\. Schnier, J\. Caskey, M\. Oguss, G\. Wills, G\. Chen, D\. Dligach,et al\.\(2025a\)Evaluating clinical ai summaries with large language models as judges\.npj Digital Medicine8\(1\),pp\. 640\.Cited by:[§6](https://arxiv.org/html/2604.18913#S6.p5.1)\.
- E\. Croxford, Y\. Gao, N\. Pellegrino, K\. Wong, G\. Wills, E\. First, M\. Schnier, K\. Burton, C\. Ebby, J\. Gorski,et al\.\(2025b\)Development and validation of the provider documentation summarization quality instrument for large language models\.Journal of the American Medical Informatics Association32\(6\),pp\. 1050–1060\.Cited by:[§6](https://arxiv.org/html/2604.18913#S6.p5.1)\.
- G\. Csardi and T\. Nepusz \(2006\)The igraph software\.Complex syst1695,pp\. 1–9\.Cited by:[Table 1](https://arxiv.org/html/2604.18913#S1.T1.1.1.6.6.1),[§2](https://arxiv.org/html/2604.18913#S2.p1.1)\.
- P\. P\. S\. Dammu, H\. Naidu, M\. Dewan, Y\. Kim, T\. Roosta, A\. Chadha, and C\. Shah \(2024\)Claimver: explainable claim\-level verification and evidence attribution of text through knowledge graphs\.arXiv preprint arXiv:2403\.09724\.Cited by:[§1](https://arxiv.org/html/2604.18913#S1.p1.1),[§2\.1](https://arxiv.org/html/2604.18913#S2.SS1.p1.1)\.
- A\. Deutsch, Y\. Xu, M\. Wu, and V\. Lee \(2019\)Tigergraph: a native mpp graph database\.arXiv preprint arXiv:1901\.08248\.Cited by:[Table 1](https://arxiv.org/html/2604.18913#S1.T1.1.1.4.4.1),[§2](https://arxiv.org/html/2604.18913#S2.p1.1)\.
- A\. Dubey, A\. Jauhri, A\. Pandey, A\. Kadian, A\. Al\-Dahle, A\. Letman, A\. Mathur, A\. Schelten, A\. Yang, A\. Fan,et al\.\(2024\)The llama 3 herd of models\.arXiv e\-prints,pp\. arXiv–2407\.Cited by:[§4](https://arxiv.org/html/2604.18913#S4.p4.1)\.
- A\. Fansi Tchango, R\. Goel, Z\. Wen, J\. Martel, and J\. Ghosn \(2022\)Ddxplus: a new dataset for automatic medical diagnosis\.Advances in neural information processing systems35,pp\. 31306–31318\.Cited by:[§4](https://arxiv.org/html/2604.18913#S4.p3.1)\.
- M\. Fey and J\. E\. Lenssen \(2019\)Fast graph representation learning with pytorch geometric\.arXiv preprint arXiv:1903\.02428\.Cited by:[Table 1](https://arxiv.org/html/2604.18913#S1.T1.1.1.12.12.1),[§2](https://arxiv.org/html/2604.18913#S2.p1.1)\.
- Y\. Gao, D\. Dligach, T\. Miller, and M\. Afshar \(2023\)Overview of the problem list summarization \(ProbSum\) 2023 shared task on summarizing patients’ active diagnoses and problems from electronic health record progress notes\.InProceedings of the 22nd Workshop on Biomedical Natural Language Processing and BioNLP Shared Tasks,D\. Demner\-fushman, S\. Ananiadou, and K\. Cohen \(Eds\.\),Toronto, Canada,pp\. 461–467\.External Links:[Link](https://aclanthology.org/2023.bionlp-1.43/),[Document](https://dx.doi.org/10.18653/v1/2023.bionlp-1.43)Cited by:[§4](https://arxiv.org/html/2604.18913#S4.p3.1)\.
- Y\. Gao, R\. Li, E\. Croxford, J\. Caskey, B\. W\. Patterson, M\. Churpek, T\. Miller, D\. Dligach, and M\. Afshar \(2025\)Leveraging medical knowledge graphs into large language models for diagnosis prediction: design and application study\.Jmir Ai4,pp\. e58670\.Cited by:[§A\.6](https://arxiv.org/html/2604.18913#A1.SS6.p1.2),[§1](https://arxiv.org/html/2604.18913#S1.p2.4),[§6](https://arxiv.org/html/2604.18913#S6.p1.1)\.
- A\. Hagberg, P\. J\. Swart, and D\. A\. Schult \(2008\)Exploring network structure, dynamics, and function using networkx\.Technical reportLos Alamos National Laboratory \(LANL\), Los Alamos, NM \(United States\)\.Cited by:[Table 1](https://arxiv.org/html/2604.18913#S1.T1.1.1.7.7.1),[§2](https://arxiv.org/html/2604.18913#S2.p1.1)\.
- \[18\]H\. Han, Y\. Wang, H\. Shomer, K\. Guo, J\. Ding, Y\. Lei, M\. Halappanavar, R\. Rossi, S\. Mukherjee, X\. Tang,et al\.Retrieval\-augmented generation with graphs \(graphrag\)\. arxiv 2024\.arXiv preprint arXiv:2501\.00309\.Cited by:[§A\.6](https://arxiv.org/html/2604.18913#A1.SS6.p1.2)\.
- Y\. Huang, R\. Zhang, Z\. Nie, J\. Chen, and X\. Zhang \(2025\)A graph\-based verification framework for fact\-checking\.arXiv preprint arXiv:2503\.07282\.Cited by:[§2\.1](https://arxiv.org/html/2604.18913#S2.SS1.p1.1)\.
- M\. Jia, J\. Duan, Y\. Song, and J\. Wang \(2024\)MedIKAL: integrating knowledge graphs as assistants of llms for enhanced clinical diagnosis on emrs\.arXiv preprint arXiv:2406\.14326\.Cited by:[§1](https://arxiv.org/html/2604.18913#S1.p1.1)\.
- P\. Jiang, C\. Xiao, A\. Cross, and J\. Sun \(2024\)GRAPHCARE: enhancing healthcare predictions with personalized knowledge graphs\.In12th International Conference on Learning Representations, ICLR 2024,Cited by:[§6](https://arxiv.org/html/2604.18913#S6.p1.1)\.
- A\. E\. Johnson, T\. J\. Pollard, L\. Shen, L\. H\. Lehman, M\. Feng, M\. Ghassemi, B\. Moody, P\. Szolovits, L\. Anthony Celi, and R\. G\. Mark \(2016\)MIMIC\-iii, a freely accessible critical care database\.Scientific data3\(1\),pp\. 1–9\.Cited by:[§4](https://arxiv.org/html/2604.18913#S4.p4.1)\.
- J\. Kepner, P\. Aaltonen, D\. A\. Bader, A\. Buluç, F\. Franchetti, J\. R\. Gilbert, D\. Hutchison, M\. Kumar, A\. Lumsdaine, H\. Meyerhenke, S\. McMillan, J\. E\. Moreira, J\. D\. Owens, C\. Yang, M\. Zalewski, and T\. G\. Mattson \(2016\)Mathematical foundations of the graphblas\.InIEEE High Performance Extreme Computing Conference \(HPEC\),External Links:[Document](https://dx.doi.org/10.1109/HPEC.2016.7761646)Cited by:[Table 1](https://arxiv.org/html/2604.18913#S1.T1.1.1.5.5.1),[§2](https://arxiv.org/html/2604.18913#S2.p1.1)\.
- S\. Khatwani, H\. Cheng, M\. Afshar, D\. Dligach, and Y\. Gao \(2025\)Brittleness and promise: knowledge graph based reward modeling for diagnostic reasoning\.arXiv preprint arXiv:2509\.18316\.Cited by:[§A\.7](https://arxiv.org/html/2604.18913#A1.SS7.p2.2)\.
- J\. Kim, S\. Park, Y\. Kwon, Y\. Jo, J\. Thorne, and E\. Choi \(2023\)FactKG: fact verification via reasoning on knowledge graphs\.arXiv preprint arXiv:2305\.06590\.Cited by:[§2\.1](https://arxiv.org/html/2604.18913#S2.SS1.p1.1)\.
- J\. Leskovec and R\. Sosič \(2016\)Snap: a general\-purpose network analysis and graph\-mining library\.ACM Transactions on Intelligent Systems and Technology \(TIST\)8\(1\),pp\. 1–20\.Cited by:[Table 1](https://arxiv.org/html/2604.18913#S1.T1.1.1.9.9.1),[§2](https://arxiv.org/html/2604.18913#S2.p1.1)\.
- H\. Liu, Z\. Wang, X\. Chen, Z\. Li, F\. Xiong, Q\. Yu, and W\. Zhang \(2025\)HopRAG: multi\-hop reasoning for logic\-aware retrieval\-augmented generation\.InFindings of the Association for Computational Linguistics: ACL 2025,W\. Che, J\. Nabende, E\. Shutova, and M\. T\. Pilehvar \(Eds\.\),Vienna, Austria,pp\. 1897–1913\.External Links:[Link](https://aclanthology.org/2025.findings-acl.97/),[Document](https://dx.doi.org/10.18653/v1/2025.findings-acl.97),ISBN 979\-8\-89176\-256\-5Cited by:[§1](https://arxiv.org/html/2604.18913#S1.p1.1)\.
- Y\. Lu, S\. Y\. Goi, X\. Zhao, and J\. Wang \(2025\)Biomedical knowledge graph: a survey of domains, tasks, and real\-world applications\.arXiv preprint arXiv:2501\.11632\.Cited by:[§1](https://arxiv.org/html/2604.18913#S1.p1.1)\.
- Neo4j, Inc\. \(2025\)Neo4j Graph Data Science\.Note:[https://neo4j\.com/product/graph\-data\-science/](https://neo4j.com/product/graph-data-science/)Accessed: 2025\-10\-06Cited by:[Table 1](https://arxiv.org/html/2604.18913#S1.T1.1.1.3.3.1)\.
- OpenAI \(2025a\)GPT\-5 mini model card\.Note:OpenAI Platform DocumentationAccessed: 2026\-01\-05External Links:[Link](https://platform.openai.com/docs/models/gpt-5-mini)Cited by:[§4](https://arxiv.org/html/2604.18913#S4.p4.1)\.
- OpenAI \(2025b\)Introducing gpt\-4\.1\.Note:OpenAI BlogAccessed: 2026\-01\-05External Links:[Link](https://openai.com/index/gpt-4-1/)Cited by:[§4](https://arxiv.org/html/2604.18913#S4.p4.1)\.
- T\. P\. Peixoto \(2014\)The graph\-tool python library\.figshare\.External Links:[Link](http://figshare.com/articles/graph_tool/1164194),[Document](https://dx.doi.org/10.6084/m9.figshare.1164194)Cited by:[Table 1](https://arxiv.org/html/2604.18913#S1.T1.1.1.8.8.1)\.
- H\. Pham, T\. Nguyen, and K\. N\. Bui \(2025a\)Verify\-in\-the\-graph: entity disambiguation enhancement for complex claim verification with interactive graph representation\.InProceedings of the 2025 Conference of the Nations of the Americas Chapter of the Association for Computational Linguistics: Human Language Technologies \(Volume 1: Long Papers\),L\. Chiruzzo, A\. Ritter, and L\. Wang \(Eds\.\),Albuquerque, New Mexico,pp\. 5181–5197\.External Links:[Link](https://aclanthology.org/2025.naacl-long.268/),[Document](https://dx.doi.org/10.18653/v1/2025.naacl-long.268),ISBN 979\-8\-89176\-189\-6Cited by:[§1](https://arxiv.org/html/2604.18913#S1.p1.1)\.
- H\. Pham, T\. Nguyen, and K\. N\. Bui \(2025b\)Verify\-in\-the\-graph: entity disambiguation enhancement for complex claim verification with interactive graph representation\.arXiv preprint arXiv:2505\.22993\.Cited by:[§2\.1](https://arxiv.org/html/2604.18913#S2.SS1.p1.1)\.
- Qwen, :, A\. Yang, B\. Yang, B\. Zhang, B\. Hui, B\. Zheng, B\. Yu, C\. Li, D\. Liu, F\. Huang, H\. Wei, H\. Lin, J\. Yang, J\. Tu, J\. Zhang, J\. Yang, J\. Yang, J\. Zhou, J\. Lin, K\. Dang, K\. Lu, K\. Bao, K\. Yang, L\. Yu, M\. Li, M\. Xue, P\. Zhang, Q\. Zhu, R\. Men, R\. Lin, T\. Li, T\. Tang, T\. Xia, X\. Ren, X\. Ren, Y\. Fan, Y\. Su, Y\. Zhang, Y\. Wan, Y\. Liu, Z\. Cui, Z\. Zhang, and Z\. Qiu \(2025\)Qwen2\.5 technical report\.External Links:2412\.15115,[Link](https://arxiv.org/abs/2412.15115)Cited by:[§4](https://arxiv.org/html/2604.18913#S4.p4.1)\.
- RAPIDS AI \(2025\)cuGraph: RAPIDS GPU Graph Analytics Library\.Note:[https://github\.com/rapidsai/cugraph](https://github.com/rapidsai/cugraph)Accessed: 2025\-10\-06Cited by:[Table 1](https://arxiv.org/html/2604.18913#S1.T1.1.1.10.10.1)\.
- M\. R\. Rezaei, R\. Saadati Fard, J\. Parker, R\. G\. Krishnan, and M\. Lankarany \(2025\)Adaptive knowledge graphs enhance medical question answering: bridging the gap between llms and evolving medical knowledge\.arXiv e\-prints,pp\. arXiv–2502\.Cited by:[§1](https://arxiv.org/html/2604.18913#S1.p1.1)\.
- F\. Shami, S\. Marchesin, and G\. Silvello \(2025\)Fact verification in knowledge graphs using llms\.InProceedings of the 48th International ACM SIGIR Conference on Research and Development in Information Retrieval,pp\. 3985–3989\.Cited by:[§2\.1](https://arxiv.org/html/2604.18913#S2.SS1.p1.1)\.
- K\. Sharma, P\. Kumar, and Y\. Li \(2024\)Og\-rag: ontology\-grounded retrieval\-augmented generation for large language models\.arXiv preprint arXiv:2412\.15235\.Cited by:[§1](https://arxiv.org/html/2604.18913#S1.p1.1)\.
- M\. Wang, D\. Zheng, Z\. Ye, Q\. Gan, M\. Li, X\. Song, J\. Zhou, C\. Ma, L\. Yu, Y\. Gai,et al\.\(2019\)Deep graph library: a graph\-centric, highly\-performant package for graph neural networks\.arXiv preprint arXiv:1909\.01315\.Cited by:[Table 1](https://arxiv.org/html/2604.18913#S1.T1.1.1.11.11.1),[§2](https://arxiv.org/html/2604.18913#S2.p1.1)\.
- S\. Wang, W\. Fan, Y\. Feng, L\. Shanru, X\. Ma, S\. Wang, and D\. Yin \(2025a\)Knowledge graph retrieval\-augmented generation for LLM\-based recommendation\.InProceedings of the 63rd Annual Meeting of the Association for Computational Linguistics \(Volume 1: Long Papers\),W\. Che, J\. Nabende, E\. Shutova, and M\. T\. Pilehvar \(Eds\.\),Vienna, Austria,pp\. 27152–27168\.External Links:[Link](https://aclanthology.org/2025.acl-long.1317/),[Document](https://dx.doi.org/10.18653/v1/2025.acl-long.1317),ISBN 979\-8\-89176\-251\-0Cited by:[§1](https://arxiv.org/html/2604.18913#S1.p1.1)\.
- S\. Wang, J\. Lin, X\. Guo, J\. Shun, J\. Li, and Y\. Zhu \(2025b\)Reasoning of large language models over knowledge graphs with super\-relations\.InThe Thirteenth International Conference on Learning Representations,External Links:[Link](https://openreview.net/forum?id=rTCJ29pkuA)Cited by:[§1](https://arxiv.org/html/2604.18913#S1.p1.1)\.
- R\. Wu, P\. Cai, J\. Mei, L\. Wen, T\. Hu, X\. Yang, D\. Fu, and B\. Shi \(2025\)KG\-traces: enhancing large language models with knowledge graph\-constrained trajectory reasoning and attribution supervision\.arXiv preprint arXiv:2506\.00783\.Cited by:[§1](https://arxiv.org/html/2604.18913#S1.p1.1)\.
- Y\. Xie, H\. Cui, Z\. Zhang, J\. Lu, K\. Shu, F\. Nahab, X\. Hu, and C\. Yang \(2025\)KERAP: a knowledge\-enhanced reasoning approach for accurate zero\-shot diagnosis prediction using multi\-agent llms\.arXiv preprint arXiv:2507\.02773\.Cited by:[§A\.7](https://arxiv.org/html/2604.18913#A1.SS7.p2.2)\.
- J\. Xu, S\. Kim, M\. Song, M\. Jeong, D\. Kim, J\. Kang, J\. F\. Rousseau, X\. Li, W\. Xu, V\. I\. Torvik,et al\.\(2020\)Building a pubmed knowledge graph\.Scientific data7\(1\),pp\. 205\.Cited by:[§1](https://arxiv.org/html/2604.18913#S1.p2.4),[§4](https://arxiv.org/html/2604.18913#S4.p2.1)\.
- J\. Xu, C\. Yu, J\. Xu, V\. I\. Torvik, J\. Kang, M\. Sung, M\. Song, Y\. Bu, and Y\. Ding \(2025\)PubMed knowledge graph 2\.0: connecting papers, patents, and clinical trials in biomedical science\.Scientific Data12\(1\),pp\. 1018\.Cited by:[§1](https://arxiv.org/html/2604.18913#S1.p2.4),[§4](https://arxiv.org/html/2604.18913#S4.p2.1)\.
- X\. Zhao, M\. Blum, F\. Gao, Y\. Chen, B\. Yang, L\. Marquez\-Carpintero, M\. Pina\-Navarro, Y\. Fu, S\. Morikawa, Y\. Iwasawa,et al\.\(2025\)Agentigraph: a multi\-agent knowledge graph framework for interactive, domain\-specific llm chatbots\.InProceedings of the 34th ACM International Conference on Information and Knowledge Management,pp\. 6757–6761\.Cited by:[§A\.7](https://arxiv.org/html/2604.18913#A1.SS7.p2.2)\.
- K\. Zuo, Y\. Jiang, F\. Mo, and P\. Lio \(2025\)Kg4diagnosis: a hierarchical multi\-agent llm framework with knowledge graph enhancement for medical diagnosis\.InAAAI Bridge Program on AI for Medicine and Healthcare,pp\. 195–204\.Cited by:[§A\.7](https://arxiv.org/html/2604.18913#A1.SS7.p2.2),[§1](https://arxiv.org/html/2604.18913#S1.p1.1),[§6](https://arxiv.org/html/2604.18913#S6.p1.1)\.

## Appendix AAppendix

### A\.1Jaccard similarity for LogosKG retrieval fidelity

To evaluate retrieval accuracy, we use the Jaccard similarity:

Jaccard​\(A,B\)=\|RA∩RB\|\|RA∪RB\|,\\mathrm\{Jaccard\}\(A,B\)=\\frac\{\|R\_\{A\}\\cap R\_\{B\}\|\}\{\|R\_\{A\}\\cup R\_\{B\}\|\},whereRAR\_\{A\}andRBR\_\{B\}are the retrieved entity sets from the methodAAand methodBBon the same query\. Higher values indicate stronger agreement \(1\.00 = identical results\)\.

Table 4:Jaccard similarity of theLogosKG familyvs\. CPU and GPU baselines across hops 1–5\.Table[4](https://arxiv.org/html/2604.18913#A1.T4)shows that all retrieved results are perfectly overlapped, proving the fidelity ofLogosKG\.

![Refer to caption](https://arxiv.org/html/2604.18913v1/prf1_by_hops_zeroshot.png)Figure 6:Performance comparison of KG filtering \(Round 1\) and enhancement \(Round 2\) across varying hop distances \(k=1k=1tok=5k=5\) on ProbSum and DDXPlus datasets using UMLS and PrimeKG\. Precision, recall, and F1 score metrics are shown forGPT\-4\.1, Qwen\-2\.5\-7B\-Instruct, and Llama\-3\.1\-8B\-Instructin the Zero\-shot setting, with baseline performance included for reference\.
### A\.2Entity\-level Evaluation Metric

We compute the baseline precision and recall based on the overlap between predicted and gold\-standard entities, as defined below:

Precision\\displaystyle\\mathrm\{Precision\}=\|p​r​e​d∩g​o​l​d\|\|p​r​e​d\|,\\displaystyle=\\frac\{\|\\,pred\\cap gold\\,\|\}\{\|\\,pred\\,\|\},\(11\)Recall\\displaystyle\\mathrm\{Recall\}=\|p​r​e​d∩g​o​l​d\|\|g​o​l​d\|\.\\displaystyle=\\frac\{\|\\,pred\\cap gold\\,\|\}\{\|\\,gold\\,\|\}\.
We compute precision and recall to assess the effect of KG processing\. Round 1 \(filtered\) and Round 2 \(enhanced\) use the same computation, which can be formulated as follows\. Letp​r​e​dfpred\_\{f\}denote the subset of predictions after KG processing \(filtered in Round 1, enhanced in Round 2\):

Precisionf\\displaystyle\\mathrm\{Precision\}\_\{f\}=\|p​r​e​df∩g​o​l​d\|\|p​r​e​df\|,\\displaystyle=\\frac\{\|\\,pred\_\{f\}\\cap gold\\,\|\}\{\|\\,pred\_\{f\}\\,\|\},\(12\)Recallf\\displaystyle\\mathrm\{Recall\}\_\{f\}=\|p​r​e​df∩g​o​l​d\|\|g​o​l​d\|\.\\displaystyle=\\frac\{\|\\,pred\_\{f\}\\cap gold\\,\|\}\{\|\\,gold\\,\|\}\.

### A\.3Supplementary Sensitivity Analysis

We study the impact ofLogosKGon LLM performance across varying retrieval depths \(k=1k=1–55\) in Rounds 1 and 2\. Figure[6](https://arxiv.org/html/2604.18913#A1.F6)details precision, recall, and F1 scores, supplementing the main results in Figure[3](https://arxiv.org/html/2604.18913#S6.F3)\.

In Round 1, increasing the retrieval depth allowsLogosKGto uncover more supporting evidence from KGs\. We observe this as an increase in recall; however, due to the inherent incompleteness of the KG, recall remains below the baseline\. Conversely, precision consistently exceeds the baseline, asLogosKGeffectively filters out hallucinated diagnoses using retrieval evidence\. To recover important diagnoses missed by the LLM, Round 2 prompts the model to select additional evidence from theLogosKGretrieval evidence\. Here, we observe that recall surpasses the baseline, though this comes with a slight decrease in precision as the inclusion of more evidence inevitably introduces some noise\. Nevertheless, the overall improvement in F1 scores demonstrates thatLogosKGsuccessfully enhances diagnostic performance\. These results underscore the critical role that KG structure plays in determining how much LLMs can benefit from integration\.

### A\.4Diagnosis Quality Evaluation using PDSQI\-9 Criteria

Table 5:PDSQI\-9 evaluation comparing Baseline \(B\), LogosKG Round 1 \(R1\), and Round 2 \(R2\) atk=5k=5\. Results for base models across UMLS and PrimeKG\.↑\\uparrowindicates improvement over baseline\.![Refer to caption](https://arxiv.org/html/2604.18913v1/prf1_by_hops_sft.png)Figure 7:Performance comparison of KG filtering \(Round 1\) and enhancement \(Round 2\) across varying hop distances \(k=1k=1tok=5k=5\) on ProbSum and DDXPlus datasets using UMLS and PrimeKG\. Precision, recall, and F1 score metrics are shown forQwen\-2\.5\-7B\-Instruct \(Fine\-tuned\) and Llama\-3\.1\-8B\-Instruct \(Fine\-tuned\), with baseline performance included for reference\.Table[5](https://arxiv.org/html/2604.18913#A1.T5)shows thatLogosKGgenerally improves diagnosis quality across models and datasets\. For DDXPlus, the gains are particularly evident in accuracy extractive, organization, comprehensibility, succinctness, and synthesis, suggesting that high\-hop retrieval yields more concise and comprehensive outputs\. Specifically, gains in succinctness are most apparent in Round 1, showing the effectiveness ofLogosKGin removing hallucinated diagnoses\. In contrast, the gains in comprehensibility and synthesis during Round 2 confirm the system’s ability to complement incomplete diagnoses by adding relevant evidence from KGs\. Improvements are limited on ProbSum and mainly focused on Round 1, where most concepts are already covered by the input notes \(as shown in Figure[2](https://arxiv.org/html/2604.18913#S6.F2)\), but are much stronger on DDXPlus, which requires retrieving evidence at higher hops\. Improvements across multiple metrics confirm thatLogosKGeffectively enhances LLM diagnostic quality\.

### A\.5Analysis: Fine\-Tuned Models with KG Enhancement

Figure[7](https://arxiv.org/html/2604.18913#A1.F7)shows how task\-specific fine\-tuned models perform withLogosKGenhancement across different hop distances\. Unlike zero\-shot models that gain substantially from KG guidance, fine\-tuned models show minimal improvements or even worse performance\. Round 1 KG filtering reduces recall while providing only small precision gains, making the trade\-off not worthwhile\. Round 2 enhancement helps partially but cannot restore baseline performance across both datasets and KGs\. This differs sharply from zero\-shot scenarios, where the two\-round approach successfully balances precision and recall\.

Why KG Enhancement Cannot Beat Task\-Specific Fine\-Tuning?This performance gap shows three key problems\. First,knowledge mismatch: fine\-tuned models learn disease connections directly from labeled clinical data, picking up patterns and relationships that may not exist in general biomedical KGs\. The KG shows how concepts relate in theory rather than how diseases appear in actual clinical practice\. Second,filtering removes good predictions: Round 1’s strict KG checking throws out predictions that the model correctly learned during training, simply because they don’t connect strongly to extracted entities in the KG\. Third,searching space complexity: While Round 2 finds hundreds of candidate diseases, the model must select from this large set without training\.

When DoesLogosKGHelp?Our results show thatLogosKGworks best in zero\-shot and few\-shot settings where models lack task\-specific training\. While fine\-tuning performs well on target domains, it narrows model knowledge and reduces generalization\.LogosKGtakes a different approach: it maintains broad capabilities while improving domain\-specific performance through external knowledge\. This makes it particularly valuable for applications covering diverse medical specialties or rare diseases with limited training data, where preserving model flexibility is as important as achieving strong performance\. When task\-specific data is scarce or cross\-domain generalization is prioritized, KG enhancement offers a practical alternative to fine\-tuning\.

Table 6:Retrieval refinement performance on UMLS and PrimeKG\. Results are grouped by refinement strategy \(Similarity Thresholdτ\\tauvs\. Top\-N Selection\) with varyingkk\.Table 7:Performance of KG\-augmented supervised fine\-tuning on UMLS and PrimeKG\. We compare Llama\-3\.1\-8B\-Instruct and Qwen\-2\.5\-7B\-Instruct models trained with specific \(k=1,2k=1,2\) versus cumulative \(k≤2,3k\\leq 2,3\) retrieval contexts\.
### A\.6Evaluation of Refinement Techniques for Filtering in Round 1

We also optimized the retrieval results to reduce noise and examined whether refinement could improve performance\. Following a setup common in prior work \(e\.g\., Dr\.Knows\(Gaoet al\.,[2025](https://arxiv.org/html/2604.18913#bib.bib46)\)and GraphRAG\([Hanet al\.,](https://arxiv.org/html/2604.18913#bib.bib58)\)\), we used SapBERT to compute the maximum cosine similarity between candidate diagnoses and query entities\. All results in Table[6](https://arxiv.org/html/2604.18913#A1.T6)were computed using GPT\-5\-mini with ProbSum\. To strictly investigate the impact of ranking and pruning on initial retrieval, these experiments utilize only LogosKG’s Round 1 filtering output, excluding the Round 2 expansion\. We explored two refinement strategies: a threshold\-based method \(τ=0\.7,0\.8,0\.9\\tau=0\.7,0\.8,0\.9\) and a Top\-N selection method \(N=10,15,20,25,30N=10,15,20,25,30\)\.

We found that the threshold method worked well for reducing noise on UMLS, but it struggled with PrimeKG\. It appears that the performance drop for PrimeKG was due to the method being too aggressive, likely filtering out useful evidence\. On the other hand, the Top\-N strategy proved to be much more reliable\. By keeping a fixed number of the best candidates instead of relying solely on a strict score, it struck a better balance between filtering out noise and retaining key information\. This approach led to consistent gains in Precision and F1 score, particularly in later rounds, where error management is important\.

### A\.7LogosKG\-Augmented Supervised Fine\-Tuning

We also investigated whetherLogosKGcould enhance training for downstream medical diagnosis\. We approached this by retrieving evidence in two distinct modes: “at specific hops” \(isolating entities at exact distances\) and “within specific hops” \(aggregating all entities up to a certain distance\)\. We then augmented the original training data by appending these retrieved entities to the patient progress notes\. Using this enriched input, we performed Supervised Fine\-Tuning to teach the models to identify the gold\-standard diagnosis within the provided context\.

Our results in Table[7](https://arxiv.org/html/2604.18913#A1.T7)clearly show that restricting retrieval to specific hops \(k=1,2k=1,2\) consistently outperforms cumulative strategies \(k≤2,3k\\leq 2,3\)\. While cumulative retrieval captures more information, in practice, it overwhelms the model with noise\. For example, for each sample in ProbSum, the number of diagnosis entities retrieved from PrimeKG increases drastically with depth, averaging 215 within 2 hops and rising to 42,533 within 5 hops\. This noise actually drags performance below the baseline of standard supervised fine\-tuning, which has the advantage of a cleaner and more focused search space\. These findings underscore that effective KG\-LLM training is not trivial\. AsKhatwaniet al\.\([2025](https://arxiv.org/html/2604.18913#bib.bib61)\)pointed out, simple fine\-tuning is insufficient\. Instead, the field is moving toward iterative, multi\-agent frameworks, an exciting direction recently explored byZhaoet al\.\([2025](https://arxiv.org/html/2604.18913#bib.bib62)\); Zuoet al\.\([2025](https://arxiv.org/html/2604.18913#bib.bib41)\); Xieet al\.\([2025](https://arxiv.org/html/2604.18913#bib.bib63)\)\. We consider this as a key area for future work, whereLogosKGcan serve as the efficient retrieval backbone necessary for such advanced systems\.