SCAIR: Schema-Conditioned Agentic Iterative Reasoning for Enterprise Knowledge Graphs

# Schema-Conditioned Agentic Iterative Reasoning for Enterprise Knowledge Graphs
Source: [https://arxiv.org/html/2607.22571](https://arxiv.org/html/2607.22571)
Prateek Chaturvedi1,2, Yuqicheng Zhu1,2, Hongkuan Zhou1,2, Dongzhuoran Zhou2,3, Yunjie He1,2,Steffen Staab1,4,Fei Du5,6,Jie Tang6,Evgeny Kharlamov2,3 1University of Stuttgart,2Bosch Center for AI,3University of Oslo, 4University of Southampton,5BSH Home Applications Holding \(China\) Co\., Ltd, 6Tsinghua University yuqicheng\.zhu@de\.bosch\.com

###### Abstract

Knowledge Graph–based Retrieval\-Augmented Generation \(KG\-RAG\) enables natural language interaction with structured enterprise knowledge, yet existing agentic approaches that perform well on public benchmarks often fail to generalize to real\-world enterprise Knowledge Graphs \(KGs\), which are dense, schema\-driven, and operationally constrained\. To address these limitations, we propose SCAIR \(Schema\-Conditioned Agentic Iterative Reasoning\), a training\-free framework that integrates structured planning with controlled iterative reasoning by injecting schema\-conditioned structural priors and enforcing schema\-aware traversal during multi\-hop reasoning\. Experiments on an enterprise\-oriented benchmark constructed from a real\-world Configuration Management DataBase \(CMDB\) demonstrate that SCAIR substantially improves performance over existing KG\-RAG methods\. Crucially, our study highlights that reliable enterprise graph reasoning cannot rely on generic agentic designs; instead, it must explicitly incorporate the target domain’s structural and operational constraints into the reasoning process\. We demonstrate that by aligning agent design with business logic, substantial performance gains can be achieved without the need for costly model retraining\.

SCAIR: Schema\-Conditioned Agentic Iterative Reasoning for Enterprise Knowledge Graphs

Prateek Chaturvedi1,2, Yuqicheng Zhu1,2, Hongkuan Zhou1,2, Dongzhuoran Zhou2,3,Yunjie He1,2,Steffen Staab1,4,Fei Du5,6,Jie Tang6,Evgeny Kharlamov2,31University of Stuttgart,2Bosch Center for AI,3University of Oslo,4University of Southampton,5BSH Home Applications Holding \(China\) Co\., Ltd,6Tsinghua Universityyuqicheng\.zhu@de\.bosch\.com

## 1Introduction

In the era of Industry 4\.0, enterprises generate vast amounts of heterogeneous data distributed across isolated systems, ranging from structured sensor logs to unstructured maintenance reportsLasiet al\.\([2014](https://arxiv.org/html/2607.22571#bib.bib1)\); Franket al\.\([2019](https://arxiv.org/html/2607.22571#bib.bib2)\)\. Knowledge Graphs \(KGs\), as a practical solution for integrating such data, provide a flexible structure that explicitly models entities and their dependencies within a unified semantic networkHoganet al\.\([2021](https://arxiv.org/html/2607.22571#bib.bib4)\); Panet al\.\([2024](https://arxiv.org/html/2607.22571#bib.bib3)\)\. This structural representation is particularly valuable for complex industrial applicationsLiuet al\.\([2023](https://arxiv.org/html/2607.22571#bib.bib5)\); Listlet al\.\([2024](https://arxiv.org/html/2607.22571#bib.bib6)\); Grangel\-Gonzálezet al\.\([2020](https://arxiv.org/html/2607.22571#bib.bib7)\)\. For example, in enterprise IT and manufacturing environments, Configuration Management Databases \(CMDBs\) are usually modeled as KGs to represent machines, components, production lines, and their operational statesSchmidtet al\.\([2025b](https://arxiv.org/html/2607.22571#bib.bib8)\)\. Such KGs support business\-critical queries, including dependency analysis, fault diagnosis, and component replacement, where reasoning over interconnected assets is essential for reliable decision\-making\.

To democratize access to structured enterprise knowledge, KG–based Retrieval\-Augmented Generation \(KG\-RAG\) has emerged as an effective solutionPenget al\.\([2024](https://arxiv.org/html/2607.22571#bib.bib14)\); Zhuet al\.\([2025a](https://arxiv.org/html/2607.22571#bib.bib12)\); Zhanget al\.\([2025](https://arxiv.org/html/2607.22571#bib.bib13)\)\. By enabling users to interact with enterprise KGs through natural language, KG\-RAG retrieves grounded and explainable evidence to answer complex queries\. More recently, agentic KG\-RAG approaches typically follow one of two paradigms:*plan\-and\-execute*, which learns explicit reasoning plans or subgraph selection strategiesHeet al\.\([2024a](https://arxiv.org/html/2607.22571#bib.bib16)\); Luoet al\.\([2024](https://arxiv.org/html/2607.22571#bib.bib18)\), and*ReAct\-style iterative exploration*, which dynamically interleaves reasoning and graph traversalSunet al\.\([2024](https://arxiv.org/html/2607.22571#bib.bib17)\); Chenet al\.\([2024](https://arxiv.org/html/2607.22571#bib.bib21)\); Zhouet al\.\([2025a](https://arxiv.org/html/2607.22571#bib.bib24)\)\. Both paradigms have demonstrated strong performance on public KGQA benchmarks\.

To evaluate the deployment readiness of these paradigms, we construct an enterprise\-oriented KGQA benchmark derived from a real\-world manufacturing CMDB\. Unlike the sparse and open\-domain graphs used in existing benchmarks, this dataset captures the dense connectivity, strict schema constraints, and operational dependencies characteristic of industrial environments\. Experiments on this benchmark reveal that existing agentic KG\-RAG methods fail to generalize under these conditions\. Public benchmarks can partially obscure these weaknesses, both because their graphs are structurally simpler and because entity and relation names often overlap with LLM pretraining corpora, which may inflate reported performance\. In contrast, the enterprise setting exposes systematic failure modes: ReAct\-style exploration suffers from uncontrolled search expansion and semantic drift in dense subgraphs, while plan\-and\-execute methods rely heavily on distribution\-specific training and struggle to generalize across query patterns\.

Motivated by these findings, we introduceSCAIR\(Schema\-ConditionedAgenticIterativeReasoning\), a hybrid agentic framework that unifies structured planning with controlled iterative reasoning\. SCAIR injects schema\-conditioned structural priors, enforces schema\-aware traversal during multi\-hop reasoning, and controls topic entity propagation to balance exploration and exploitation during search\. Notably, SCAIR outperforms all evaluated baselines on the enterprise benchmark without any task\-specific training\.

The key lesson from this study is that generic agentic designs optimized on simplified public benchmarks often fail to generalize to real business use cases\. Effective enterprise graph reasoning must explicitly account for the structural and operational characteristics of the target domain and reflect these constraints in the agent design\. With a clear understanding of the business scenario and systematic failure analysis of existing solutions, substantial performance gains can be achieved without costly model retraining\.

## 2Preliminaries

### 2\.1Knowledge Graph Question Answering

KGs represent structured knowledge as a graph of entities connected by typed relations\. Formally, a KG is defined as𝒢=\(ℰ,ℛ,𝒯\)\\mathcal\{G\}=\(\\mathcal\{E\},\\mathcal\{R\},\\mathcal\{T\}\), whereℰ\\mathcal\{E\}denotes the set of entities,ℛ\\mathcal\{R\}the set of relation types, and𝒯⊆ℰ×ℛ×ℰ\\mathcal\{T\}\\subseteq\\mathcal\{E\}\\times\\mathcal\{R\}\\times\\mathcal\{E\}the set of triples\. Each triple\(eh,r,et\)∈𝒯\(e\_\{h\},r,e\_\{t\}\)\\in\\mathcal\{T\}encodes an atomic fact, stating that a relationr∈ℛr\\in\\mathcal\{R\}holds between a head entityeh∈ℰe\_\{h\}\\in\\mathcal\{E\}and a tail entityet∈ℰe\_\{t\}\\in\\mathcal\{E\}\. Knowledge Graph Question Answering \(KGQA\) aims to answer natural language questions by reasoning over relevant facts in𝒢\\mathcal\{G\}\.

### 2\.2Existing Approaches

KGQA has been addressed through two main paradigms\.Semantic parsingapproaches translate natural language questions into executable logical forms, such as SPARQL queries, which can then be executed over the KG to obtain answersBerant and Liang \([2014](https://arxiv.org/html/2607.22571#bib.bib27)\); Berantet al\.\([2013](https://arxiv.org/html/2607.22571#bib.bib28)\); Reddyet al\.\([2014](https://arxiv.org/html/2607.22571#bib.bib29)\)\. In contrast,information retrieval–basedmethods \(i\.e\., KG\-RAG\) retrieve and rank candidate entities or subgraphs using distributed representations, often leveraging graph neural networks to encode structural information, and then generate answers conditioned on the retrieved evidenceBordeset al\.\([2015](https://arxiv.org/html/2607.22571#bib.bib36)\); Donget al\.\([2015](https://arxiv.org/html/2607.22571#bib.bib35)\)\. More recently, the field has converged towardagentic reasoning frameworks, in which an LLM operates as a decision\-making agent that plans, interacts with the KG, and reasons over retrieved evidenceLuoet al\.\([2024](https://arxiv.org/html/2607.22571#bib.bib18)\); Heet al\.\([2024a](https://arxiv.org/html/2607.22571#bib.bib16)\); Sunet al\.\([2024](https://arxiv.org/html/2607.22571#bib.bib17)\); Chenet al\.\([2024](https://arxiv.org/html/2607.22571#bib.bib21)\)\.

Within this agentic paradigm, approaches such as Reasoning on Graphs \(RoG\)Luoet al\.\([2024](https://arxiv.org/html/2607.22571#bib.bib18)\)and G\-RetrieverHeet al\.\([2024a](https://arxiv.org/html/2607.22571#bib.bib16)\)follow aPlan\-and\-ExecutedesignWanget al\.\([2023](https://arxiv.org/html/2607.22571#bib.bib31)\)\. The agent first constructs an explicit reasoning plan or identifies a target subgraph, and subsequently executes this plan through constrained graph retrieval before generating an answer\. These methods are primarily training\-based, as their planning or retrieval components are learned from supervision to align reasoning plans or subgraph selection with downstream question\-answering objectives\. Think\-on\-Graph \(ToG\)Sunet al\.\([2024](https://arxiv.org/html/2607.22571#bib.bib17)\)and Plan\-on\-Graph \(PoG\)Chenet al\.\([2024](https://arxiv.org/html/2607.22571#bib.bib21)\)adhere more closely to theReAct\-style frameworkYaoet al\.\([2023](https://arxiv.org/html/2607.22571#bib.bib30)\), interleaving reasoning steps with iterative graph exploration and allowing the agent to adapt traversal decisions based on intermediate observations\. This class of methods is typically training\-free, relying on the LLM’s reasoning capabilities rather than task\-specific parameter optimization\. Beyond text\-centric KG\-RAG, recent works also explore combining knowledge graphs with multimodal signals to improve representation learning and reasoningYuet al\.\([2025](https://arxiv.org/html/2607.22571#bib.bib57)\); Zhouet al\.\([2026b](https://arxiv.org/html/2607.22571#bib.bib55),[2024](https://arxiv.org/html/2607.22571#bib.bib56)\)\.

## 3An Enterprise\-Oriented KGQA Benchmark

In this section, we first examine why widely used KGQA benchmarks fail to capture the requirements of industrial applications\. We then introduce an enterprise\-oriented benchmark constructed from a real\-world Configuration Management Database \(CMDB\), designed to evaluate agentic KG\-RAG systems under realistic operational constraints\.

### 3\.1Limitations of Existing KGQA

KGQA benchmarks such as*WebQSP*Yihet al\.\([2016](https://arxiv.org/html/2607.22571#bib.bib32)\)and*Complex Web Questions \(CWQ\)*Talmor and Berant \([2018](https://arxiv.org/html/2607.22571#bib.bib33)\)are built on open\-domain KGs \(e\.g\., FreebaseBollackeret al\.\([2008](https://arxiv.org/html/2607.22571#bib.bib34)\)\) and are designed to evaluate compositional reasoning over relatively sparse graph structures\. While influential, these benchmarks rely on assumptions that do not align with enterprise use cases\.

First, they assume that each question maps to a single, well\-defined executable query that fully captures the user’s intent\. In industrial settings, however, questions are often underspecified and constraint\-driven, and multiple reasoning paths may be valid depending on the operational context\. Second, benchmark questions are largely*retrospective*, treating the KG as an encyclopedia for fact retrieval\. Enterprise questions are typically*prospective*and problem\-oriented, involving implicit business logic such as operational status, compatibility, or conditional replacement, which is encoded structurally in the KG rather than explicitly stated in text\. Finally, semantic leakage from LLM pretraining is difficult to avoid in public benchmarks, as entity and relation names often overlap with pretraining data\. This makes it unclear whether strong performance reflects genuine graph reasoning or implicit memorization\.

These differences expose a clear gap between existing KGQA benchmarks and the requirements of real\-world industrial applications\.

### 3\.2Enterprise KGQA Benchmark

To address the gap between public benchmarks and real industrial requirements, we construct an enterprise KGQA benchmark grounded in a real\-world manufacturing CMDB\. The benchmark consists of \(i\) a KG derived from the CMDB \(CMDB\-KG\), and \(ii\) business\-oriented question–answer pairs\.

#### CMDB\-KG\.

CMDB\-KG is constructed from a real\-world manufacturing CMDBSchmidtet al\.\([2025a](https://arxiv.org/html/2607.22571#bib.bib50)\)that integrates heterogeneous enterprise data, including production lines, machines, components, manufacturers, and operational attributes\. The graph contains 116,369 triples\. Construction details are provided in Appendix[A\.1](https://arxiv.org/html/2607.22571#A1.SS1)\.

###### Example 1\(CMDB\-KG\)\.

Figure[1](https://arxiv.org/html/2607.22571#S3.F1)shows a representative fragment of CMDB\-KG\. A production line \(e\.g\.,Line W509\-6\) is linked to multiple machines viahasMachine, and each machine connects to its installed components throughhasComponent\. Machines and components are annotated with operational status \(e\.g\.,working,idle,broken\), and components may additionally be connected bysimilarTorelations to indicate functional interchangeability\.

#### Question\-Answer Pair Generation\.

We begin by collecting representative business\-oriented information needs from the enterprise setting and abstracting them into a set of structured query templates aligned with the CMDB schema\. These templates are then instantiated automatically over the CMDB\-KG in a scalable manner, generating executable question–answer pairs grounded in real enterprise data\. The resulting benchmark comprises 9 representative query types and a total of 19,080 questions\. Detailed specifications are provided in the Appendix[A\.2](https://arxiv.org/html/2607.22571#A1.SS2)\.

###### Example 2\(Business\-Oriented Question\)\.

Consider the question:*“Which working components can replace broken components installed on machines in production lineW509\-6?”*Unlike public benchmark questions, this query cannot be expressed as a single well\-defined compositional logical form\. It requires identifying broken components inW509\-6, retrieving functionally equivalent components viasimilarTo, and enforcing operational constraints\. In particular, valid replacements must be both working and installed on idle machines; otherwise, removing them would disrupt other production lines\. These implicit business constraints must be respected during reasoning\.

![Refer to caption](https://arxiv.org/html/2607.22571v1/figures/complex_example.png)Figure 1:Representative fragment of CMDB\-KG\.
#### Evaluation Protocol\.

We follow the evaluation protocol ofZhouet al\.\([2025b](https://arxiv.org/html/2607.22571#bib.bib22),[2026a](https://arxiv.org/html/2607.22571#bib.bib23)\)\. Let𝒫q\\mathcal\{P\}\_\{q\}and𝒜q\\mathcal\{A\}\_\{q\}denote the predicted and ground\-truth answer sets for questionqq, respectively\.*Accuracy*measures exact set match \(𝒫q=𝒜q\\mathcal\{P\}\_\{q\}=\\mathcal\{A\}\_\{q\}\)\.*Hits@Any*measures whether at least one correct answer is retrieved \(𝒫q∩𝒜q≠∅\\mathcal\{P\}\_\{q\}\\cap\\mathcal\{A\}\_\{q\}\\neq\\emptyset\)\.*Precision*and*Recall*quantify answer correctness and completeness based on set overlap, and*F1*is their harmonic mean\.

### 3\.3Limitations of Existing Agentic KG\-RAG Paradigms

Through qualitative analysis of model outputs and reasoning traces on the enterprise benchmark, we observe systematic limitations in both dominant agentic KG\-RAG paradigms: plan\-and\-execute and ReAct\-style iterative exploration\.

#### Limitations of plan\-and\-execute approaches\.

Plan\-and\-execute methods mitigate uncontrolled exploration by learning explicit reasoning plans or subgraph selection strategies\. However, they rely on substantial training and hyperparameter tuning to perform reliably, which is particularly challenging when adapting large models in enterprise environments\. In practice, effective training requires sufficient coverage of the underlying query and relation distributions; otherwise, learned planning patterns tend to overfit to training\-specific structures and fail to generalize to unseen schemas or reasoning compositions\. This dependence on distribution\-specific training limits robustness under evolving enterprise KGs\.

#### Limitations of ReAct\-style exploration\.

ReAct\-based methods rely on iterative, relevance\-driven traversal\. In dense enterprise graphs, this often leads to*search explosion*, as models expand through high\-degree attribute nodes \(e\.g\., identifiers or status values\), rapidly increasing the search space\. Moreover, traversal guided primarily by semantic similarity frequently results in*schema\-agnostic reasoning*, producing paths that are semantically plausible but structurally invalid under enterprise schema constraints\. As reasoning depth increases, these issues compound into*semantic drift*, where the agent deviates from the original query intent due to locally relevant yet globally irrelevant paths\.

## 4SCAIR: Schema\-Conditioned Agentic Iterative Reasoning

To address the enterprise\-specific limitations identified in Section[3\.3](https://arxiv.org/html/2607.22571#S3.SS3), we proposeSCAIR, a novel KG\-RAG method built on atraining\-free hybrid agentic paradigm\(Figure[2](https://arxiv.org/html/2607.22571#S4.F2)\)\. Unlike existing approaches that adopt either a plan\-and\-execute strategy or a ReAct\-style iterative exploration \(Section[2\.2](https://arxiv.org/html/2607.22571#S2.SS2)\), SCAIR integrates structured planning with controlled iterative reasoning within a unified framework\.

SCAIR is guided by three design principles: \(i\) schema\-conditioned planning to provide structural priors, \(ii\) schema\-aware iterative reasoning to ensure valid and focused multi\-hop traversal, and \(iii\) controlled topic entity propagation to balance exploration and exploitation during search\.

#### Schema\-Conditioned Planning\.

Before iterative reasoning \(i\.e\. the ReAct loop\), SCAIR performs a lightweight planning stage to introduce structural priors\. Specifically, we generate schema\-consistent relation paths based on entity types and relation definitions to restrict traversal to valid relation compositions and avoid expansion through irrelevant high\-degree nodes\. In parallel, the input question is decomposed into depth\-aligned subquestions that specify the information required at each reasoning hop\. Unlike strict plan\-and\-execute systems, this stage does not commit to a single fixed plan, but instead provides structural guidance that constrains subsequent exploration\.

#### Schema\-Aware Iterative Reasoning\.

The core of SCAIR follows an iterative agentic loop\. At each depth, candidate relations connected to the current topic entities are retrieved, filtered using schema constraints, and scored conditioned on the corresponding subquestion\. The selected relations are then expanded to candidate entities, which are further scored and pruned based on the accumulated reasoning context\. Traversal is thus guided jointly by semantic relevance and schema validity, preventing structurally invalid paths and reducing search explosion in dense enterprise graphs\. The process terminates once sufficient evidence is collected or the maximum reasoning depth is reached\.

#### Exploitation\-Exploration Tradeoff\.

SCAIR balances exploration and exploitation through controlled topic entity propagation\. Rather than replacing the topic entity set at each depth, the algorithm maintains a union of previously discovered entities and newly expanded ones\. This preserves earlier reasoning anchors \(exploitation\) while enabling deeper traversal into new regions of the graph \(exploration\)\. In contrast, ReAct\-style methods typically update the working state using only newly expanded entities, which can prematurely discard earlier topic entities and limit the opportunity to explore alternative relations connected to them\.

![Refer to caption](https://arxiv.org/html/2607.22571v1/figures/kgrag_overview.png)Figure 2:Overview of Plan\-and\-Execute, ReAct and SCAIR\.

## 5Experiments and Results

### 5\.1Experimental Settings

All methods are evaluated on the enterprise CMDB benchmark\. We compare SCAIR with agentic KG\-RAG paradigms: plan\-and\-execute methods \(RoG, G\-Retriever\) and ReAct\-style iterative methods \(ToG, PoG\), covering training\-based and training\-free strategies\. Baseline model configurations and hyperparameters follow the settings reported in the original papers to ensure fair comparison\. Detailed configurations are provided in Table[4](https://arxiv.org/html/2607.22571#A4.T4)in Appendix[D](https://arxiv.org/html/2607.22571#A4)\. Training\-based models are fine\-tuned on two NVIDIA A100 GPUs, while training\-free methods are evaluated via OpenAI API\.

### 5\.2Results

#### Overall Performance\.

Table[1](https://arxiv.org/html/2607.22571#S5.T1)reports the performance of baseline KG\-RAG methods and SCAIR on the CMDB benchmark\. Overall, baseline performance remains limited across all metrics\. Among the baselines, training\-based methods perform better than training\-free approaches\. In particular, G\-Retriever achieves the strongest aggregate results among baselines \(25\.27 Accuracy, 24\.28 F1\), while RoG attains the highest Hits@Any \(38\.49\) but with lower precision and recall\. Training\-free methods \(ToG and PoG\) consistently underperform across metrics\. Importantly, SCAIR outperforms all baselines across evaluation metrics\. These results indicate that while existing KG\-RAG paradigms struggle under enterprise KG conditions, aligning reasoning with schema structure, as done in SCAIR, leads to consistent and significant gains\.

#### Performance Across Query Types\.

To better understand the source of the performance gains, we analyze accuracy across query types \(Figure[3](https://arxiv.org/html/2607.22571#S5.F3)\)\. SCAIR consistently outperforms training\-free ReAct\-style methods \(ToG and PoG\) across nearly all categories, with especially large improvements on multi\-hop \(2p, 3p\), intersection \(2i\), and complex queries\. These categories are particularly sensitive to uncontrolled traversal and semantic drift, where ReAct\-based exploration often fails to maintain structural validity\.

Compared to training\-based approaches \(RoG and G\-Retriever\), SCAIR achieves competitive or superior performance across most query types\. While G\-Retriever performs strongly on simpler path queries \(e\.g\., 1p\), its accuracy drops substantially on complex and constraint\-heavy queries\. This pattern suggests that training\-based models tend to internalize reasoning templates prevalent in the training distribution, but struggle to generalize\. In contrast, SCAIR maintains high accuracy even in the most challenging*complex*category, indicating stronger robustness to distribution shifts and structurally diverse reasoning patterns\. The same trends are reflected in Hits@Any and F1 scores \(see Appendix[E](https://arxiv.org/html/2607.22571#A5)\)\.

Overall, the improvements are distributed across query types rather than concentrated on isolated patterns, suggesting that the gains arise from more reliable control over traversal and reasoning structure rather than from stronger language modeling or memorization\.

#### Ablation Study\.

We analyze the impact of structural control by selectively disabling schema\-aware relation filtering and entity\-centric constraints in the proposed agentic KG\-RAG framework\. As shown in Figure[4](https://arxiv.org/html/2607.22571#S5.F4), removing these controls leads to a consistent degradation in performance across query categories\. Overall, the results indicate that explicit structural constraints play a central role in the robustness of the proposed approach\.

Table 1:Overall performance comparison\.![Refer to caption](https://arxiv.org/html/2607.22571v1/figures/stacked_2.png)Figure 3:Accuracy comparison across query types\. Results for other evaluation metrics are reported in the Appendix[E](https://arxiv.org/html/2607.22571#A5)\.![Refer to caption](https://arxiv.org/html/2607.22571v1/figures/stacked_3.png)Figure 4:Component Impact on Overall Performance\.
#### Inference Cost Analysis\.

We report per\-query inference cost for training\-free baselines and SCAIR in Table[2](https://arxiv.org/html/2607.22571#S5.T2)\. SCAIR requires more LLM calls \(42\.36\) and tokens \(22\.5k input, 5\.9k output\) than ToG \(13\.95; 5\.9k/2\.1k\) and PoG \(5\.60; 3\.7k/0\.4k\), reflecting its deeper average traversal \(2\.54 vs\. 2\.14/1\.61\)\. This cost is functional\. Most benchmark query types \(i\.e\. 2p, 3p, ip, pi, and complex\) require 2–4 reasoning hops, and SCAIR’s depth of 2\.54 approximates the minimum needed for correct multi\-hop resolution\. ToG and PoG terminate earlier and consequently underperform on these categories\.

Token growth is input\-dominated, arising from accumulating reasoning context across hops; this structure is particularly amenable to API prompt caching, where repeated prefixes receive 50–90% cost discountsOpenAI \([2025](https://arxiv.org/html/2607.22571#bib.bib58)\)and substantially reduce effective per\-query cost in deployed settings\. Direct cost comparison with training\-based methods is not meaningful, as their total cost includes supervision curation and GPU training time not captured by inference metrics\. SCAIR is therefore suited to enterprise workloads where answer correctness is prioritized over single\-query latency\.

Table 2:Per\-query inference cost for training\-free agentic KG\-RAG methods\. Calls/Q denotes average LLM calls per question; Depth denotes average reasoning depth reached\.

## 6Discussion

### 6\.1Implications for Industrial Deployment

Our results challenge the implicit assumption in KGQA literature that improved language modeling automatically translates to deployment readiness\. In enterprise settings, the "correctness" of an answer is bound by implicit operational constraints \(e\.g\., component availability or compatibility\) rather than just semantic relevance\. We identify three critical principles for deploying KG\-RAG in such dense, schema\-governed environments:

#### 1\. Structural Validity Must Gate Semantic Relevance\.

In dense CMDBs, semantic similarity is a noisy proxy for utility\. High\-degree attribute nodes \(e\.g\., "Status: Broken"\) often act as "semantic supernodes," causing ReAct\-style agents to drift into operationally irrelevant subgraphs\. Effective retrieval must therefore bestructure\-first: schema constraints should prune the search spacebeforesemantic scoring occurs, preventing the "hallucinated validity" observed in standard baselines\.

#### 2\. Traversal Control is the Primary Bottleneck\.

Comparing LLaMA\-2 and Qwen\-2\.5 backbones \(Appendix[E\.3](https://arxiv.org/html/2607.22571#A5.SS3)\) reveals that stronger parametric knowledge improves answer generation but fails to prevent search explosion\. The failure mode is architectural, not parametric\. For practitioners, this implies that investing in lightweight, schema\-aware planning yields higher reliability gains than simply scaling the inference backbone\.

#### 3\. Inference\-Time Adaptation Outperforms Retraining\.

Plan\-and\-execute methods often overfit to specific query templates seen during training, making them brittle to the frequent schema evolutions typical of enterprise IT\. Training\-free frameworks like SCAIR, which inject structural priors at inference time, offer a more maintainable deployment strategy\. They allow the reasoning engine to adapt to new business rules or schema updates without the cost of continuous supervised fine\-tuning\.

## 7Conclusion and Future Work

This work exposes the fragility of current agentic KG\-RAG paradigms when applied to the dense, constraint\-heavy reality of industrial KGs\. By introducing a realistic CMDB benchmark, we demonstrate that dominant failure modes stem from a misalignment between open\-domain retrieval heuristics and enterprise operational logic\.

Our approach SCAIR mitigates these issues by enforcing structural alignment within the agentic loop, but the path to fully autonomous enterprise agents requires further evolution along several directions\. First, moving beyond prompt\-based heuristics, business rules such as disruption risk and valid replacement conditions could be encoded as explicit schema annotations or typed constraints, enabling more principled reasoning over operational logic\. Second, while inference\-time control is effective, designing training objectives that reward structural validity rather than only final\-answer accuracy remains a promising direction for next\-generation graph reasoning models\. Finally, extending the empirical comparison to non\-agentic schema\-constrained traversal and text\-to\-SPARQL baselines would further disentangle the contributions of structural filtering from agentic iteration\.

## 8Acknowledgements

The authors thank the International Max Planck Research School for Intelligent Systems \(IMPRS\-IS\) for supporting Yuqicheng Zhu, Hongkuan Zhou and Yunjie He\. The work was partially supported by EU Projects SMARTY \(GA 101140087\)\.

## References

- Complex query answering with neural link predictors\.InICLR,Cited by:[Appendix F](https://arxiv.org/html/2607.22571#A6.SS0.SSS0.Px1.p1.1)\.
- E\. Arakelyan, P\. Minervini, D\. Daza, M\. Cochez, and I\. Augenstein \(2023\)Adapting neural link predictors for data\-efficient complex query answering\.InNeurIPS,Cited by:[Figure 7](https://arxiv.org/html/2607.22571#A1.F7)\.
- J\. Berant, A\. Chou, R\. Frostig, and P\. Liang \(2013\)Semantic parsing on freebase from question\-answer pairs\.InEMNLP,pp\. 1533–1544\.Cited by:[§2\.2](https://arxiv.org/html/2607.22571#S2.SS2.p1.1)\.
- J\. Berant and P\. Liang \(2014\)Semantic parsing via paraphrasing\.InACL \(1\),pp\. 1415–1425\.Cited by:[§2\.2](https://arxiv.org/html/2607.22571#S2.SS2.p1.1)\.
- K\. D\. Bollacker, C\. Evans, P\. K\. Paritosh, T\. Sturge, and J\. Taylor \(2008\)Freebase: a collaboratively created graph database for structuring human knowledge\.InSIGMOD Conference,pp\. 1247–1250\.Cited by:[§3\.1](https://arxiv.org/html/2607.22571#S3.SS1.p1.1)\.
- A\. Bordes, N\. Usunier, S\. Chopra, and J\. Weston \(2015\)Large\-scale simple question answering with memory networks\.CoRRabs/1506\.02075\.Cited by:[§2\.2](https://arxiv.org/html/2607.22571#S2.SS2.p1.1)\.
- L\. Chen, P\. Tong, Z\. Jin, Y\. Sun, J\. Ye, and H\. Xiong \(2024\)Plan\-on\-graph: self\-correcting adaptive planning of large language model on knowledge graphs\.Advances in Neural Information Processing Systems37,pp\. 37665–37691\.Cited by:[§1](https://arxiv.org/html/2607.22571#S1.p2.1),[§2\.2](https://arxiv.org/html/2607.22571#S2.SS2.p1.1),[§2\.2](https://arxiv.org/html/2607.22571#S2.SS2.p2.1)\.
- L\. Dong, F\. Wei, M\. Zhou, and K\. Xu \(2015\)Question answering over freebase with multi\-column convolutional neural networks\.InACL \(1\),pp\. 260–269\.Cited by:[§2\.2](https://arxiv.org/html/2607.22571#S2.SS2.p1.1)\.
- A\. G\. Frank, L\. S\. Dalenogare, and N\. F\. Ayala \(2019\)Industry 4\.0 technologies: implementation patterns in manufacturing companies\.International journal of production economics210,pp\. 15–26\.Cited by:[§1](https://arxiv.org/html/2607.22571#S1.p1.1)\.
- I\. Grangel\-González, F\. Lösch, and A\. ul Mehdi \(2020\)Knowledge graphs for efficient integration and access of manufacturing data\.In2020 25th IEEE International Conference on Emerging Technologies and Factory Automation \(ETFA\),Vol\.1,pp\. 93–100\.Cited by:[§1](https://arxiv.org/html/2607.22571#S1.p1.1)\.
- X\. He, Y\. Tian, Y\. Sun, N\. V\. Chawla, T\. Laurent, Y\. LeCun, X\. Bresson, and B\. Hooi \(2024a\)G\-retriever: retrieval\-augmented generation for textual graph understanding and question answering\.InNeurIPS,Cited by:[§1](https://arxiv.org/html/2607.22571#S1.p2.1),[§2\.2](https://arxiv.org/html/2607.22571#S2.SS2.p1.1),[§2\.2](https://arxiv.org/html/2607.22571#S2.SS2.p2.1)\.
- Y\. He, B\. He, Z\. Ding, A\. M\. Lupidi, Y\. Zhu, S\. Chen, C\. Zhang, J\. Chen, Y\. Ma, V\. Tresp,et al\.\(2025a\)Supposedly equivalent facts that aren’t? entity frequency in pre\-training induces asymmetry in llms\.InSecond Conference on Language Modeling,Cited by:[Appendix F](https://arxiv.org/html/2607.22571#A6.SS0.SSS0.Px2.p1.1)\.
- Y\. He, D\. Hernandez, M\. Nayyeri, B\. Xiong, Y\. Zhu, E\. Kharlamov, and S\. Staab \(2024b\)Generating𝒮​ℛ​𝒪​ℐ−\\mathcal\{SROI\}^\{\-\}ontologies via knowledge graph query embedding learning\.InECAI,Cited by:[Appendix F](https://arxiv.org/html/2607.22571#A6.SS0.SSS0.Px1.p1.1)\.
- Y\. He, M\. Nayyeri, B\. Xiong, Y\. Zhu, E\. Kharlamov, and S\. Staab \(2023\)Can pattern learning enhance complex logical query answering?\.Cited by:[Appendix F](https://arxiv.org/html/2607.22571#A6.SS0.SSS0.Px1.p1.1)\.
- Y\. He, B\. Xiong, D\. Hernández, Y\. Zhu, E\. Kharlamov, and S\. Staab \(2025b\)Dage: dag query answering via relational combinator with logical constraints\.InProceedings of the ACM on Web Conference 2025,pp\. 2514–2529\.Cited by:[Appendix F](https://arxiv.org/html/2607.22571#A6.SS0.SSS0.Px1.p1.1)\.
- A\. Hogan, E\. Blomqvist, M\. Cochez, C\. d’Amato, G\. D\. Melo, C\. Gutierrez, S\. Kirrane, J\. E\. L\. Gayo, R\. Navigli, S\. Neumaier,et al\.\(2021\)Knowledge graphs\.ACM Computing Surveys \(Csur\)54\(4\),pp\. 1–37\.Cited by:[§1](https://arxiv.org/html/2607.22571#S1.p1.1)\.
- H\. Lasi, P\. Fettke, H\. Kemper, T\. Feld, and M\. Hoffmann \(2014\)Industry 4\.0\.Business & information systems engineering6\(4\),pp\. 239–242\.Cited by:[§1](https://arxiv.org/html/2607.22571#S1.p1.1)\.
- F\. G\. Listl, D\. Dittler, G\. Hildebrandt, V\. Stegmaier, N\. Jazdi, and M\. Weyrich \(2024\)Knowledge graphs in the digital twin: a systematic literature review about the combination of semantic technologies and simulation in industrial automation\.IEEE Access\.Cited by:[§1](https://arxiv.org/html/2607.22571#S1.p1.1)\.
- Y\. Liu, B\. He, M\. Hildebrandt, M\. Buchner, D\. Inzko, R\. Wernert, E\. Weigel, D\. Beyer, M\. Berbalk, and V\. Tresp \(2023\)A knowledge graph perspective on supply chain resilience\.InD2R2,CEUR Workshop Proceedings, Vol\.3401\.Cited by:[§1](https://arxiv.org/html/2607.22571#S1.p1.1)\.
- L\. Luo, Y\. Li, G\. Haffari, and S\. Pan \(2024\)Reasoning on graphs: faithful and interpretable large language model reasoning\.InThe Twelfth International Conference on Learning Representations, ICLR 2024, Vienna, Austria, May 7\-11, 2024,Cited by:[§1](https://arxiv.org/html/2607.22571#S1.p2.1),[§2\.2](https://arxiv.org/html/2607.22571#S2.SS2.p1.1),[§2\.2](https://arxiv.org/html/2607.22571#S2.SS2.p2.1)\.
- OpenAI \(2025\)Prompt caching\.Note:[https://platform\.openai\.com/docs/guides/prompt\-caching](https://platform.openai.com/docs/guides/prompt-caching)Accessed: 2026\-04\-24Cited by:[§5\.2](https://arxiv.org/html/2607.22571#S5.SS2.SSS0.Px4.p2.1)\.
- S\. Pan, L\. Luo, Y\. Wang, C\. Chen, J\. Wang, and X\. Wu \(2024\)Unifying large language models and knowledge graphs: a roadmap\.IEEE Transactions on Knowledge and Data Engineering36\(7\),pp\. 3580–3599\.Cited by:[§1](https://arxiv.org/html/2607.22571#S1.p1.1)\.
- B\. Peng, Y\. Zhu, Y\. Liu, X\. Bo, H\. Shi, C\. Hong, Y\. Zhang, and S\. Tang \(2024\)Graph retrieval\-augmented generation: a survey\.arXiv preprint arXiv:2408\.08921\.Cited by:[§1](https://arxiv.org/html/2607.22571#S1.p2.1)\.
- N\. Potyka, Y\. Zhu, Y\. He, E\. Kharlamov, and S\. Staab \(2024\)Robust knowledge extraction from large language models using social choice theory\.InProceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems,pp\. 1593–1601\.Cited by:[Appendix F](https://arxiv.org/html/2607.22571#A6.SS0.SSS0.Px2.p1.1)\.
- S\. Reddy, M\. Lapata, and M\. Steedman \(2014\)Large\-scale semantic parsing without question\-answer pairs\.Trans\. Assoc\. Comput\. Linguistics2,pp\. 377–392\.Cited by:[§2\.2](https://arxiv.org/html/2607.22571#S2.SS2.p1.1)\.
- H\. Ren, W\. Hu, and J\. Leskovec \(2020\)Query2box: reasoning over knowledge graphs in vector space using box embeddings\.InICLR,Cited by:[Appendix F](https://arxiv.org/html/2607.22571#A6.SS0.SSS0.Px1.p1.1)\.
- W\. J\. Schmidt, I\. Grangel\-González, T\. Huschle, L\. Wagner, E\. Kharlamov, and A\. Paschke \(2025a\)LLM\-supported mapping generation for semantic manufacturing treasure hunting\.InESWC \(2\),Lecture Notes in Computer Science, Vol\.15719,pp\. 84–101\.Cited by:[§3\.2](https://arxiv.org/html/2607.22571#S3.SS2.SSS0.Px1.p1.1)\.
- W\. J\. Schmidt, I\. Grangel\-González, T\. Huschle, L\. Wagner, E\. Kharlamov, and A\. Paschke \(2025b\)MYAM: llm\-supported mapping generation for semantic manufacturing retrieval\.InEuropean Semantic Web Conference,pp\. 135–140\.Cited by:[§1](https://arxiv.org/html/2607.22571#S1.p1.1)\.
- J\. Sun, C\. Xu, L\. Tang, S\. Wang, C\. Lin, Y\. Gong, L\. M\. Ni, H\. Shum, and J\. Guo \(2024\)Think\-on\-graph: deep and responsible reasoning of large language model on knowledge graph\.InICLR,Cited by:[§1](https://arxiv.org/html/2607.22571#S1.p2.1),[§2\.2](https://arxiv.org/html/2607.22571#S2.SS2.p1.1),[§2\.2](https://arxiv.org/html/2607.22571#S2.SS2.p2.1)\.
- A\. Talmor and J\. Berant \(2018\)The web as a knowledge\-base for answering complex questions\.InNAACL\-HLT,pp\. 641–651\.Cited by:[§3\.1](https://arxiv.org/html/2607.22571#S3.SS1.p1.1)\.
- L\. Wang, W\. Xu, Y\. Lan, Z\. Hu, Y\. Lan, R\. K\. Lee, and E\. Lim \(2023\)Plan\-and\-solve prompting: improving zero\-shot chain\-of\-thought reasoning by large language models\.InACL \(1\),pp\. 2609–2634\.Cited by:[§2\.2](https://arxiv.org/html/2607.22571#S2.SS2.p2.1)\.
- S\. Yao, J\. Zhao, D\. Yu, N\. Du, I\. Shafran, K\. R\. Narasimhan, and Y\. Cao \(2023\)ReAct: synergizing reasoning and acting in language models\.InICLR,Cited by:[§2\.2](https://arxiv.org/html/2607.22571#S2.SS2.p2.1)\.
- W\. Yih, M\. Richardson, C\. Meek, M\. Chang, and J\. Suh \(2016\)The value of semantic parse labeling for knowledge base question answering\.InACL \(2\),Cited by:[§3\.1](https://arxiv.org/html/2607.22571#S3.SS1.p1.1)\.
- S\. Yu, C\. Tang, B\. Xu, J\. Cui, J\. Ran, Y\. Yan, Z\. Liu, S\. Wang, X\. Han, Z\. Liu, and M\. Sun \(2025\)VisRAG: vision\-based retrieval\-augmented generation on multi\-modality documents\.InThe Thirteenth International Conference on Learning Representations, ICLR 2025, Singapore, April 24\-28, 2025,External Links:[Link](https://openreview.net/forum?id=zG459X3Xge)Cited by:[§2\.2](https://arxiv.org/html/2607.22571#S2.SS2.p2.1)\.
- Q\. Zhang, S\. Chen, Y\. Bei, Z\. Yuan, H\. Zhou, Z\. Hong, J\. Dong, H\. Chen, Y\. Chang, and X\. Huang \(2025\)A survey of graph retrieval\-augmented generation for customized large language models\.arXiv preprint arXiv:2501\.13958\.Cited by:[§1](https://arxiv.org/html/2607.22571#S1.p2.1)\.
- D\. Zhou, Y\. Zhu, X\. Wang, H\. Zhou, J\. Chen, S\. Staab, Y\. He, and E\. Kharlamov \(2025a\)GR\-agent: adaptive graph reasoning agent under incomplete knowledge\.arXiv preprint arXiv:2512\.14766\.Cited by:[§1](https://arxiv.org/html/2607.22571#S1.p2.1)\.
- D\. Zhou, Y\. Zhu, X\. Wang, H\. Zhou, Y\. He, J\. Chen, S\. Staab, and E\. Kharlamov \(2025b\)Evaluating knowledge graph based retrieval augmented generation methods under knowledge incompleteness\.InProceedings of the International Research and Industry Symposium on AI \(IRIS\-AI 25\),pp\. "2–9"\.Cited by:[§3\.2](https://arxiv.org/html/2607.22571#S3.SS2.SSS0.Px3.p1.5)\.
- D\. Zhou, Y\. Zhu, X\. Wang, H\. Zhou, Y\. He, J\. Chen, S\. Staab, and E\. Kharlamov \(2026a\)What breaks knowledge graph based RAG? benchmarking and empirical insights into reasoning under incomplete knowledge\.InProceedings of the 19th Conference of the European Chapter of the Association for Computational Linguistics \(Volume 1: Long Papers\),V\. Demberg, K\. Inui, and L\. Marquez \(Eds\.\),Rabat, Morocco,pp\. 2522–2538\.Cited by:[§3\.2](https://arxiv.org/html/2607.22571#S3.SS2.SSS0.Px3.p1.5)\.
- H\. Zhou, L\. Halilaj, S\. Monka, S\. Schmid, Y\. Zhu, J\. Wu, N\. Nazer, and S\. Staab \(2026b\)Seeing and knowing in the wild: open\-domain visual entity recognition with large\-scale knowledge graphs via contrastive learning\.InFortieth AAAI Conference on Artificial Intelligence, Thirty\-Eighth Conference on Innovative Applications of Artificial Intelligence, Sixteenth Symposium on Educational Advances in Artificial Intelligence, AAAI 2026, Singapore, January 20\-27, 2026,S\. Koenig, C\. Jenkins, and M\. E\. Taylor \(Eds\.\),pp\. 13638–13646\.External Links:[Link](https://doi.org/10.1609/aaai.v40i16.38370),[Document](https://dx.doi.org/10.1609/AAAI.V40I16.38370)Cited by:[§2\.2](https://arxiv.org/html/2607.22571#S2.SS2.p2.1)\.
- H\. Zhou, L\. Halilaj, S\. Monka, S\. Schmid, Y\. Zhu, B\. Xiong, and S\. Staab \(2024\)Visual representation learning guided by multi\-modal prior knowledge\.CoRRabs/2410\.15981\.External Links:[Link](https://doi.org/10.48550/arXiv.2410.15981),[Document](https://dx.doi.org/10.48550/ARXIV.2410.15981),2410\.15981Cited by:[§2\.2](https://arxiv.org/html/2607.22571#S2.SS2.p2.1)\.
- X\. Zhu, Y\. Xie, Y\. Liu, Y\. Li, and W\. Hu \(2025a\)Knowledge graph\-guided retrieval augmented generation\.arXiv preprint arXiv:2502\.06864\.Cited by:[§1](https://arxiv.org/html/2607.22571#S1.p2.1)\.
- Y\. Zhu, D\. Hernández, Y\. He, Z\. Ding, B\. Xiong, E\. Kharlamov, and S\. Staab \(2025b\)Predicate\-conditional conformalized answer sets for knowledge graph embeddings\.InFindings of the Association for Computational Linguistics: ACL 2025,Vienna, Austria,pp\. 4145–4167\.Cited by:[Appendix F](https://arxiv.org/html/2607.22571#A6.SS0.SSS0.Px1.p1.1)\.
- Y\. Zhu, N\. Potyka, D\. Hernández, Y\. He, Z\. Ding, B\. Xiong, D\. Zhou, E\. Kharlamov, and S\. Staab \(2025c\)ArgRAG: explainable retrieval augmented generation using quantitative bipolar argumentation\.InConference on Neurosymbolic Learning and Reasoning,pp\. 697–718\.Cited by:[Appendix F](https://arxiv.org/html/2607.22571#A6.SS0.SSS0.Px2.p1.1)\.
- Y\. Zhu, N\. Potyka, M\. Nayyeri, B\. Xiong, Y\. He, E\. Kharlamov, and S\. Staab \(2024a\)Predictive multiplicity of knowledge graph embeddings in link prediction\.InFindings of the Association for Computational Linguistics: EMNLP 2024,Miami, Florida, USA,pp\. 334–354\.Cited by:[Appendix F](https://arxiv.org/html/2607.22571#A6.SS0.SSS0.Px1.p1.1)\.
- Y\. Zhu, N\. Potyka, J\. Pan, B\. Xiong, Y\. He, E\. Kharlamov, and S\. Staab \(2025d\)Conformalized answer set prediction for knowledge graph embedding\.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\),pp\. 731–750\.Cited by:[Appendix F](https://arxiv.org/html/2607.22571#A6.SS0.SSS0.Px1.p1.1)\.
- Y\. Zhu, N\. Potyka, B\. Xiong, T\. Tran, M\. Nayyeri, E\. Kharlamov, and S\. Staab \(2024b\)Approximating probabilistic inference in statistical el with knowledge graph embeddings\.arXiv preprint arXiv:2407\.11821\.Cited by:[Appendix F](https://arxiv.org/html/2607.22571#A6.SS0.SSS0.Px1.p1.1)\.
- Y\. Zhu, N\. Potyka, B\. Xiong, T\. Tran, M\. Nayyeri, S\. Staab, and E\. Kharlamov \(2023\)Towards statistical reasoning with ontology embeddings\.\.Cited by:[Appendix F](https://arxiv.org/html/2607.22571#A6.SS0.SSS0.Px1.p1.1)\.
- Y\. Zhu, J\. Wu, Y\. Wang, H\. Zhou, J\. Chen, E\. Kharlamov, and S\. Staab \(2025e\)Certainty in uncertainty: reasoning over uncertain knowledge graphs with statistical guarantees\.InProceedings of the 2025 Conference on Empirical Methods in Natural Language Processing,pp\. 8741–8763\.Cited by:[Appendix F](https://arxiv.org/html/2607.22571#A6.SS0.SSS0.Px1.p1.1)\.
- Y\. Zhu \(2025\)Thesis proposal: uncertainty in knowledge graph embeddings\.InProceedings of the 2025 Conference of the Nations of the Americas Chapter of the Association for Computational Linguistics: Human Language Technologies \(Volume 4: Student Research Workshop\),pp\. 40–47\.Cited by:[Appendix F](https://arxiv.org/html/2607.22571#A6.SS0.SSS0.Px1.p1.1)\.

## Appendix ABenchmark construction details

### A\.1CMDB\-KG Construction

#### KG Enhancement\.

To support realistic reasoning patterns, we extend the original CMDB KG with a small set of auxiliary relations commonly required in operational scenarios, such as component status, manufacturer information, and functional similarity between components\. These extensions do not alter the core semantics of the CMDB but enable queries related to diagnostics, filtering, and component replacement that are central to enterprise use cases\. \(Figure[5](https://arxiv.org/html/2607.22571#A1.F5)\) illustrates the high\-level schema structure of the CMDB KG which supports complex diagnostic and replacement queries\.

![Refer to caption](https://arxiv.org/html/2607.22571v1/figures/cmdb_schema_overview.png)Figure 5:High\-level schema overview of the enterprise CMDB KG\. The figure illustrates the core entity types \(lines, machines, components\), their relations, and selected operational attributes introduced to support enterprise reasoning tasks\.

### A\.2Question\-Answer Pair Construction\.

Rather than collecting natural language questions from crowd workers or logs, we construct the benchmark using a template\-based question generation framework grounded in the CMDB schema\. Each question template corresponds to a predefined reasoning pattern \(illustrated in Figure[7](https://arxiv.org/html/2607.22571#A1.F7)\), including multi\-hop projection, logical conjunction, disjunction, and domain\-specific compositional reasoning\. The benchmark covers nine query categories: single\-hop projection \(1p\), multi\-hop projection \(2p, 3p\), intersection \(2i\), path–intersection hybrids \(ip, pi\), union \(2u, up\), and domain\-specific complex queries involving operational constraints\.

Templates are defined over the CMDB schema and specify both the underlying graph traversal pattern and a natural language realization\. During instantiation, template placeholders are grounded with concrete entities from the CMDB KG, and the resulting queries are executed against the KG to obtain gold\-standard answers\. An example of a template specification and its corresponding executable query is shown in Figure[6](https://arxiv.org/html/2607.22571#A1.F6)\.

![Refer to caption](https://arxiv.org/html/2607.22571v1/figures/template.png)Figure 6:Example of a template\-based question specification and its executable graph query used for benchmark construction\.In addition to standard compositional patterns, the benchmark includes domain\-specific multi\-hop queries that reflect real industrial scenarios\. For example, replacement queries require identifying functionally similar components that satisfy operational constraints, such as being currently functional while the original component is broken\. These queries combine topological traversal with attribute\-based filtering and implicit business logic, making them particularly challenging for KG\-RAG systems\.

![Refer to caption](https://arxiv.org/html/2607.22571v1/figures/query-types.png)Figure 7:Illustrative examples of structured reasoning templates used in this work\. The visualization style and template taxonomy are inspired by\(Arakelyanet al\.,[2023](https://arxiv.org/html/2607.22571#bib.bib54)\)As shown in Table[3](https://arxiv.org/html/2607.22571#A1.T3), the benchmark contains 19,080 questions in total\. While single\-hop \(1p\) queries dominate in absolute number due to large entity coverage, the benchmark includes 7,080 compositional queries \(excluding 1p\), spanning multi\-hop, intersection, union, and domain\-specific complex patterns\. This distribution reflects realistic enterprise workloads, where simple lookups are frequent but structurally complex queries are critical for diagnostic and operational tasks\.

Table 3:Distribution of query types and instantiated question instances\.

## Appendix BCase Study of Existing Methods

We report representative failure cases observed for ReAct style ToG on the enterprise benchmark\. Each case includes \(i\) a real benchmark question, \(ii\) the intended KG reasoning pattern, and \(iii\) a concrete failure symptom consistent with the failure modes\.

### B\.1Search Explosion

#### Question \(complex\)\.

*Which working components can replace broken components installed on machines in production lineW509\-6?*

#### Intended KG reasoning\.

Line W509\-6→hasMachine\\xrightarrow\{\\texttt\{hasMachine\}\}machines→hasComponent\\xrightarrow\{\\texttt\{hasComponent\}\}components→componentStatus\\xrightarrow\{\\texttt\{componentStatus\}\}filterbroken→similarTo\\xrightarrow\{\\texttt\{similarTo\}\}candidates→componentStatus\\xrightarrow\{\\texttt\{componentStatus\}\}filterworking\. Additionally, candidates installed onidlemachines are preferred to avoid disrupting other lines\.

#### Observed failure symptom\.

ReAct\-style exploration frequently expands via high\-degree attribute relations before committing tosimilarTo\. A typical trajectory is:

> Step 1:retrieve machines forW509\-6\(hasMachine\) Step 2:retrieve components \(hasComponent\) Step 3:expand viamanufacturerorcomponentStatus\(hub attribute\) Step 4:retrieve many unrelated “working” components sharing the same attribute value

This produces large candidate sets dominated by generic attribute matches \(e\.g\., many components linked toworking\), exhausting the beam budget and preventing exploration along the intendedsimilarTorelation\.

#### Example incorrect output\.

Predicted answer sets often contain many unrelated working components \(high Hits@Any but low precision\), e\.g\., \{P\-E11\-26838,P\-E11\-27317,P\-E11\-31641, …\}, where the returned components share an attribute hub \(e\.g\.,working\) but are not valid replacements for the broken components inW509\-6\.

### B\.2Schema\-Agnostic Reasoning

#### Question \(3p\-style\)\.

*Which IP addresses are assigned to components installed on machines in production line W509\-6?*

#### Intended KG reasoning\.

ProductionLine→hasMachine\\xrightarrow\{\\texttt\{hasMachine\}\}Machine→hasComponent\\xrightarrow\{\\texttt\{hasComponent\}\}Component→ipAddress\\xrightarrow\{\\texttt\{ipAddress\}\}IP\.

#### Observed incorrect traversal\.

Instead of expanding towardipAddress, the agent may select a semantically plausible relation such asmanufacturer:

Machine→manufacturer\\xrightarrow\{\\texttt\{manufacturer\}\}BoschX→manufacturer−1\\xrightarrow\{\\texttt\{manufacturer\}^\{\-1\}\}Machine\.

Because network configuration is often associated with vendors in real\-world settings, this transition appears relevant at the language level\. However, it expands through a high\-degree manufacturer node and retrieves machines unrelated to the queried production line\.

### B\.3Semantic Drift Under Increasing Reasoning Depth

#### Question \(3p\-style\)\.

*Which production lines contain machines that use components manufactured by Siemens?*

#### Intended KG reasoning\.

Manufacturer\(Siemens\)→manufacturer−1\\xrightarrow\{\\texttt\{manufacturer\}^\{\-1\}\}Component→hasComponent−1\\xrightarrow\{\\texttt\{hasComponent\}^\{\-1\}\}Machine→hasMachine−1\\xrightarrow\{\\texttt\{hasMachine\}^\{\-1\}\}ProductionLine\.

#### Observed drift pattern\.

After reachingComponentnodes, the agent may select a semantically plausible but task\-irrelevant relation such assimilarTo:

Component→similarTo\\xrightarrow\{\\texttt\{similarTo\}\}Component→hasComponent−1\\xrightarrow\{\\texttt\{hasComponent\}^\{\-1\}\}Machine\.

Because similarity is often associated with compatibility, this transition appears reasonable at the language level\. However, it expands the search to components not manufactured by Siemens, thereby violating the original constraint\.

#### Effect\.

Although each hop is schema\-valid, the reasoning progressively drifts from the manufacturer constraint\. As depth increases, locally plausible transitions accumulate, leading to production lines unrelated to Siemens\-manufactured components\. This illustrates semantic drift in multi\-hop enterprise reasoning\.

#### Summary\.

These cases instantiate the failure modes discussed in Section[3\.3](https://arxiv.org/html/2607.22571#S3.SS3): uncontrolled expansion via high\-degree hubs, schema\-agnostic relation selection, and progressive semantic drift under increasing reasoning depth\.

## Appendix CMore Details of SCAIR

Algorithm[1](https://arxiv.org/html/2607.22571#alg1)provides the full pseudocode of SCAIR\. In the following sections, we also detail implementation parameters, prompting strategy, and search control mechanisms used in our experiments\.

Algorithm 1Schema\-Aware and Question\-Guided Method1:Question

QQ, initial topic entities

E0E\_\{0\}, beam width

ww, maximum depth

dd, KG

𝒢\\mathcal\{G\}
2:Answer set

𝒫Q\\mathcal\{P\}\_\{Q\}
3:

𝒫←GenerateRelationPaths​\(Q,𝒢\)\\mathcal\{P\}\\leftarrow\\textsc\{GenerateRelationPaths\}\(Q,\\mathcal\{G\}\)⊳\\trianglerightschema\-guided relation paths

4:

\{q1,q2,…,qd\}←DecomposeQuestion​\(Q,𝒫\)\\\{q\_\{1\},q\_\{2\},\\dots,q\_\{d\}\\\}\\leftarrow\\textsc\{DecomposeQuestion\}\(Q,\\mathcal\{P\}\)⊳\\trianglerightdepth\-aligned subquestions

5:

E0←E\_\{0\}\\leftarrowgiven topic entities

6:for

t=0t=0to

d−1d\-1do

7:Relation Search:

8:

ℛt←RetrieveRelations​\(Et,𝒢\)\\mathcal\{R\}\_\{t\}\\leftarrow\\textsc\{RetrieveRelations\}\(E\_\{t\},\\mathcal\{G\}\)
9:

ℛt←FilterRelations​\(ℛt,qt\+1,𝒫\)\\mathcal\{R\}\_\{t\}\\leftarrow\\textsc\{FilterRelations\}\(\\mathcal\{R\}\_\{t\},q\_\{t\+1\},\\mathcal\{P\}\)
10:Score

ℛt\\mathcal\{R\}\_\{t\}using LLM

\(Q,qt\+1,Et\)\(Q,q\_\{t\+1\},E\_\{t\}\)
11:Refine scores using relation paths

𝒫\\mathcal\{P\}
12:

ℛt←TopK​\(ℛt,w\)\\mathcal\{R\}\_\{t\}\\leftarrow\\textsc\{TopK\}\(\\mathcal\{R\}\_\{t\},w\)
13:Entity Search:

14:

Et′←∅E\_\{t\}^\{\\prime\}\\leftarrow\\emptyset
15:for all

r∈ℛtr\\in\\mathcal\{R\}\_\{t\}do

16:

C←RetrieveEntities​\(Et,r,𝒢\)C\\leftarrow\\textsc\{RetrieveEntities\}\(E\_\{t\},r,\\mathcal\{G\}\)
17:Score

CCusing LLM

\(Q,qt\+1,r,C,𝒫\)\(Q,q\_\{t\+1\},r,C,\\mathcal\{P\}\)
18:Update search history with

\(Et,r,C\)\(E\_\{t\},r,C\)
19:

Et′←Et′∪CE\_\{t\}^\{\\prime\}\\leftarrow E\_\{t\}^\{\\prime\}\\cup C
20:endfor

21:if

Et′=∅E\_\{t\}^\{\\prime\}=\\emptysetthen

22:Half\-stopand skip to next depth

23:endif

24:

Et′←TopK​\(Et′,w\)E\_\{t\}^\{\\prime\}\\leftarrow\\textsc\{TopK\}\(E\_\{t\}^\{\\prime\},w\)
25:Reasoning Check:

26:ifSufficientEvidence\(

Q,Et′Q,E\_\{t\}^\{\\prime\}\)then

27:return

GenerateAnswer​\(Q,Et′\)\\textsc\{GenerateAnswer\}\(Q,E\_\{t\}^\{\\prime\}\)
28:endif

29:

Et\+1←Et∪Et′E\_\{t\+1\}\\leftarrow E\_\{t\}\\cup E\_\{t\}^\{\\prime\}⊳\\trianglerightbalanced topic entity propagation

30:endfor

31:return

BestCandidate​\(Q,Ed\)\\textsc\{BestCandidate\}\(Q,E\_\{d\}\)⊳\\trianglerightfinal half\-stop

#### Search Control Mechanisms\.

To stabilize traversal in dense graphs, we apply three controls: \(i\)*subsampling*when relation expansion yields more than 20 entity candidates, \(ii\)*cycle prevention*by tracking visited \(entity, relation\) expansions and discarding repeats, and \(iii\) a*half\-stop*policy: if no valid entity remains at depthtt, we skip expansion and continue with the previous topic state at deptht\+1t\{\+\}1\.

### C\.1Reasoning Parameters and Execution Setup

SCAIR is implemented using GPT\-4\.1\-mini via API\-based inference\. We adopt a multi\-turn chat format with explicit reasoning instructions\.

Decoding parameters are set to temperature = 0\.4 during exploration steps \(relation and entity scoring\) to allow controlled diversity, and temperature = 0\.0 during reasoning and final answer generation to ensure deterministic outputs\.

The maximum reasoning depth is set tod=4d=4, and beam width tow=6w=6\. When entity expansion yields more than 20 candidates, we apply subsampling and retain the top 8 candidates per relation \(pre\-pruning\), before beam pruning\.

All questions are processed sequentially due to the multi\-step API interaction\. API retries are enabled to mitigate transient failures\.

The choice of beam widthw=6w=6reflects a trade\-off between search coverage and stability in dense enterprise graphs\. Smaller beam widths restrict exploration and reduce recall, while larger values increase noise and semantic drift\. Empirical sensitivity analysis over beam width is provided in Appendix[E\.2](https://arxiv.org/html/2607.22571#A5.SS2), where we show thatw=6w=6yields the best balance between F1 and computational efficiency\.

### C\.2Prompting Design

SCAIR operates entirely at inference time using structured prompts that guide schema\-conditioned planning, iterative traversal, and answer verification\. To ensure reproducibility, we provide the core prompt templates used in each stage below\.

#### Relation Path Generation\.

Given the enterprise KG schema and the input question, the model first generates valid relation paths that are consistent with the ontology\. These paths restrict traversal to schema\-valid compositions and prevent structurally invalid expansions\.

Relation Path Generation PromptYou are a reasoning assistant over an industrial Knowledge Graph\.Given a question and the KG schema below, generate a valid relation path required to answer the question\. Use only relations present in the schema\. Assume the topic entity is already known\.KG Structure: CMDBLine \-hasMachines\-\> CMDBMachine \-hasCmdbComponent\-\> CMDBMachineComponent \-similarTo\-\> CMDBMachineComponentRelations: \- CMDBLine: lineName, hasMachines \- CMDBMachine: machineIdentification, machineDescription, hasCmdbComponent, company, machineStatus \- CMDBMachineComponent: componentId, componentName, macAddress, ipAddress, manufacturer, componentStatus, similarToOutput a numbered list of relation paths\.Q: <Question\>

#### Subquestion Decomposition\.

Conditioned on the generated relation path, the model decomposes the original question into depth\-aligned subquestions\. Each subquestion corresponds to a single hop in the relation path\.

Subquestion Decomposition PromptYou are given: \- A question \- A relation path \- The topic entityDecompose the question into small subquestions, each corresponding to one relation in the path\.Rules: \- Each subquestion must be self\-contained\. \- Highlight the required relation using curly braces\. \- Follow the order of the relation path exactly\. \- Output only a numbered list\.Q: <Question\> Relation Path: <Path\> Topic Entity: <Entity\>

#### Relation Scoring\.

At each depth, candidate relations connected to the current topic entities are scored conditioned on the current subquestion\. Schema\-consistent relations are prioritized\.

Relation Scoring PromptGiven: \- The question \- The current subquestion \- Candidate relations \- The relation pathAssign scores to relations such that: \- Relations highlighted in curly braces receive the highest score\. \- Scores must sum to 1\. \- Only consider the current subquestion \(no future hops\)\.Q: <Question\> Sub Question: <Subquestion\> Topic Entity: <Entity\> Candidate Relations: <Relations\> Relation Path: <Path\>

#### Entity Scoring\.

For each selected relation, candidate entities are scored based on their usefulness for answering the current subquestion\. Binary scoring \(0 or 1\) is used to reduce ambiguity\.

Entity Scoring PromptYou are given: \- The question \- The current subquestion \- The current relation \- Candidate entities \- The relation pathScore each entity strictly for this hop: \- 1 if critical for the subquestion\. \- 0 otherwise\. \- Do not hallucinate entities\.Q: <Question\> Sub Question: <Subquestion\> Relation: <Relation\> Entities: <Entities\> Relation Path: <Path\>

#### Sufficiency Evaluation\.

Before answer generation, the model evaluates whether the retrieved triples are sufficient to answer the question\.

Sufficiency Check PromptGiven a question and retrieved knowledge triples, determine whether the information is sufficient to answer\.Output: \- Yes followed by the final answer in curly braces, or \- No with a brief explanation\.Q: <Question\> Knowledge Triples: <Triples\>

#### Answer Generation\.

If sufficient evidence is available, the model generates the final answer grounded strictly in the retrieved triples\.

Answer Generation PromptGiven the question and retrieved knowledge triples, generate the final answer\. The answer entities must be wrapped in curly braces\. Do not hallucinate additional entities\.Q: <Question\> Knowledge Triples: <Triples\>

## Appendix DBaseline Implementation Details

All baseline implementations follow the original architectural designs and training procedures described in their respective publications\. We adopt the reported hyperparameters directly \(see Table[4](https://arxiv.org/html/2607.22571#A4.T4)\)\. If a parameter is unspecified, we use default values from the official codebases\.

Table 4:Key configuration settings for baseline models\.#### Hardware\.

Training\-based baselines were fine\-tuned on two NVIDIA A100 GPUs \(80GB\)\. Inference\-only methods were executed sequentially via API due to their multi\-step reasoning structure\. All implementations use PyTorch with mixed precision where applicable\.

## Appendix EMore Experimental Results

### E\.1Hits@Any and F1 Across Query Types

This appendix reports Hits@Any and F1\-score across query types for all evaluated methods\. These results complement the accuracy\-based analysis presented in the main text \(Section[5\.2](https://arxiv.org/html/2607.22571#S5.SS2)\) and provide additional insight into partial answer overlap and retrieval robustness\.

Consistent with the accuracy trends discussed in the main body, SCAIR maintains strong performance across multi\-hop, intersection, and complex query categories\. The improvements are reflected not only in exact\-match accuracy but also in overlap\-based metrics, indicating more reliable retrieval and reasoning behavior across structurally diverse query types\.

![Refer to caption](https://arxiv.org/html/2607.22571v1/figures/hits_per_type.png)Figure 8:Hits@Any per query type for all evaluated methods\.![Refer to caption](https://arxiv.org/html/2607.22571v1/figures/f1_per_type.png)Figure 9:F1\-score per query type for all evaluated methods\.
### E\.2Sensitivity to Beam Width

To analyze the robustness of SCAIR with respect to search hyperparameters, we evaluate performance under varying beam widthww\. We varyw∈\{3,4,6\}w\\in\\\{3,4,6\\\}while keeping the maximum depth fixed atd=4d=4\.

As shown in Figure[10](https://arxiv.org/html/2607.22571#A5.F10), increasing the beam width from 3 to 6 consistently improves Accuracy, Hits@Any, and F1\. The improvement fromw=3w=3tow=4w=4is moderate, while the gain fromw=4w=4tow=6w=6is more pronounced, particularly for F1 and Hits@Any\. This indicates that broader exploration improves coverage of relevant relations and entities in dense enterprise graphs\.

However, the gains diminish aswwincreases, suggesting that simply expanding the beam cannot indefinitely improve performance\. Larger beams introduce more structurally irrelevant candidates, increasing computational cost without proportional accuracy gains\.

We therefore adoptw=6w=6as a balanced setting that provides strong performance while maintaining controlled exploration\.

![Refer to caption](https://arxiv.org/html/2607.22571v1/figures/beam_width_sweep.png)Figure 10:Performance of SCAIR under different beam widths\.
### E\.3Effect of Stronger Training\-Based Backbones

To investigate whether stronger language backbones can resolve the structural limitations observed in Plan&Execute approaches, we replace the original LLaMA backbone in RoG with Qwen and retrain under identical settings\.

In a controlled setting where gold\-standard intermediate triples are provided, Qwen demonstrates stronger local reasoning ability than LLaMA, correctly answering complex compositional queries that LLaMA fails to resolve\. This suggests that Qwen has improved conditional reasoning capacity when the relevant evidence is explicitly given\.

However, when evaluated in the full end\-to\-end KG\-RAG pipeline, replacing LLaMA with Qwen does not yield meaningful improvements in overall benchmark performance \(Figure[11](https://arxiv.org/html/2607.22571#A5.F11)\)\. Performance on multi\-hop and complex query types remains limited\.

This discrepancy indicates that the primary bottleneck is not answer generation or conditional reasoning given correct evidence, but rather the structural search process that retrieves the evidence\. Stronger LLM backbones improve reasoning over provided triples, but they do not mitigate uncontrolled traversal, schema\-agnostic exploration, or search explosion in dense enterprise graphs\.

These results reinforce our central claim: structural control over graph traversal is more critical than backbone strength for enterprise KG\-RAG robustness\.

![Refer to caption](https://arxiv.org/html/2607.22571v1/figures/rog-llm-comp.png)Figure 11:Comparison of RoG with LLaMA and Qwen backbones\.

## Appendix FExtended Related Work

SCAIR addresses enterprise KG reasoning from the perspective of schema\-aware traversal control during agentic retrieval\. For completeness, we outline research threads that complement this direction\.

#### Embedding\-based Retrieval\.

SCAIR retrieves evidence through entity grounding followed by schema\-constrained traversal\. A complementary paradigm instead embeds queries into a continuous space and retrieves answers via similarity search over entity embeddings, turning multi\-hop reasoning into geometric composition rather than iterative traversalRenet al\.\([2020](https://arxiv.org/html/2607.22571#bib.bib59)\); Arakelyanet al\.\([2021](https://arxiv.org/html/2607.22571#bib.bib60)\); Heet al\.\([2023](https://arxiv.org/html/2607.22571#bib.bib61),[2024b](https://arxiv.org/html/2607.22571#bib.bib63),[2025b](https://arxiv.org/html/2607.22571#bib.bib62)\)\. The reliability of these methods, however, is bounded by the quality of the underlying KG embedding, which is itself uncertainZhu \([2025](https://arxiv.org/html/2607.22571#bib.bib68)\)\.Zhuet al\.\([2024a](https://arxiv.org/html/2607.22571#bib.bib64)\)show that equally well\-performing KGE models systematically disagree on a large fraction of link predictions, so a single point prediction cannot be treated as a reliable summary of the retriever’s output\. To expose this uncertainty explicitly, KGCP\(Zhuet al\.,[2025d](https://arxiv.org/html/2607.22571#bib.bib65)\)and CondKGCP\(Zhuet al\.,[2025b](https://arxiv.org/html/2607.22571#bib.bib66)\)apply conformal prediction to produce answer sets with marginal and predicate\-conditional coverage guarantees for KGE\-based link prediction, UnKGCP\(Zhuet al\.,[2025e](https://arxiv.org/html/2607.22571#bib.bib67)\)extends these guarantees to uncertain KGEs through calibrated confidence intervals, and BoxSEL\(Zhuet al\.,[2023](https://arxiv.org/html/2607.22571#bib.bib69),[2024b](https://arxiv.org/html/2607.22571#bib.bib70)\)provides approximate probabilistic inference in Statisticalℰ​ℒ\\mathcal\{EL\}with formal soundness guarantees at the schema level\. Until such statistical guarantees are tightly integrated into embedding\-based retrieval, entity\-grounded traversal as used in SCAIR remains a more auditable choice for enterprise settings, where silently wrong answers are costly\.

#### Language Model Reasoning\.

An analogous tradeoff arises on the language\-model side\. One could delegate a larger share of reasoning to the LLM, for instance by letting it infer answers directly from loosely retrieved context, but the LLM itself is a source of silent unreliability\.Heet al\.\([2025a](https://arxiv.org/html/2607.22571#bib.bib72)\)show that entity frequency in pretraining induces systematic asymmetries in LLM factual reasoning, so that semantically equivalent facts are handled inconsistently depending on the training distribution; related instabilities also arise at the prompt level, where minor wording changes can alter extracted outputs\. Complementary mitigations have been explored in prior work:Potykaet al\.\([2024](https://arxiv.org/html/2607.22571#bib.bib71)\)aggregate outputs across multiple prompts through social choice theory, producing extractions that are more stable than any single prompt, while ArgRAG\(Zhuet al\.,[2025c](https://arxiv.org/html/2607.22571#bib.bib73)\)addresses the downstream reasoning step by framing multi\-document evidence combination as quantitative bipolar argumentation, so that each generated claim is backed by explicit supporting and attacking arguments\. Together with the retrieval\-side analysis above, these results support the central design choice of SCAIR: robust enterprise KG reasoning requires jointly controlling the retrieval process and the reasoning behavior of the underlying model, rather than relying on either side alone\.