Source-linked AI summary
Schema-Agnostic Graph Reasoning Agent for Hybrid Knowledge Graphs
Marius Dragic, Ruben Ifrah, Alexandre Rio
TL;DR
Hybrid knowledge-graph question answering must balance exhaustive prompt context against bounded, tool-mediated access. GRA navigates the graph with seven generic tools while discovering domain-specific structure at run time. It outperforms a full-context agent by up to 5.1 pp while reading only a quarter to a third of its input.
Problem
The paper examines whether bounded, tool-mediated access can outperform serializing all hybrid-graph documentation and schema into a prompt for analytical question answering.
Method
GRA navigates hybrid knowledge graphs with seven generic tools, discovering schema, vocabulary, tables, and join paths at run time without domain-specific hard-coding.
Results
Up to 5.1 pp: GRA outperforms a full-context agent while reading only a quarter to a third of its input.
Takeaways & Limitations
Selective navigation over a structured substrate beats exhaustive context, while graph topology contributes less clearly to the advantage.
Takeaways & Limitations
Turning an approved rule into a running constraint still requires reliable translation from natural language to mathematical formulation and solver code.
Abstract
from arXiv · showhide
Tool-calling LLM agents navigate unfamiliar codebases with a handful of generic primitives for listing, reading and searching files (ls, cat, grep). A knowledge graph admits the same interface: listing neighbours, reading node content and searching descriptions are the same operations on a different substrate. Building on this correspondence, we present GRA, a Graph Reasoning Agent that explores hybrid knowledge graphs, whose nodes are either textual concepts or relational tables, with seven generic tools, discovering everything domain-specific at run time. On UFK-M (Unified Factory Knowledge Model), an industrial benchmark of 258 analytical questions whose gold answers are produced by executing validated SQL programs, GRA beats a full-context agent by 5.1 pp (88.4% vs. 83.3%), while reading under a third of its input tokens. A graph-free control shows the gain comes chiefly from selective agentic access rather than graph topology, and that the effect depends on a model able to drive tools reliably. Seeing less, the agent answers better: selective navigation over a structured substrate beats exhaustive context.
1 From code agents to graph agents
The section frames graph agents as an extension of code agents: generic navigation primitives transfer from unfamiliar repositories to knowledge graphs. It then defines a minimal hybrid substrate combining textual nodes with SQL-queryable relational tables.
- From code agents to graph agents: Generic code-agent primitives—listing, reading, and searching—map structurally to listing graph neighbours, reading node content, and searching node descriptions.In both settings, the agent reconstructs an unfamiliar substrate through navigation rather than domain-specific tools.
- From code agents to graph agents: Every graph node has an identifier, natural-language description, labels, and optional properties, while relations are directed subject–predicate–object triples.This defines the minimal substrate contract assumed by the graph agent.
- From code agents to graph agents: The hybrid graph combines textual knowledge with relational nodes backed by real DuckDB tables that can be queried using SQL.Answering a question may require textual knowledge, relational knowledge, or both.
2 Related works
Prior agent and graph-retrieval work establishes tool-mediated navigation over unfamiliar repositories and structured knowledge, but GRA combines schema-agnostic operation, hybrid semantic-relational substrates, and computation beyond stored node values. These distinctions motivate GRA’s unified interface and its application to grounded feasibility verdicts.
- Agent and graph interfaces: ReAct introduced interleaved reasoning and tool calls, while SWE-agent showed that a few file-system commands can operate over unfamiliar repositories.GRA extends this correspondence from codebases to knowledge graphs explored by following links rather than reading them whole.
- Agent and graph interfaces: Graph-retrieval systems expose language models to graphs, tables, and databases through relation following, node lookup, and neighbour listing.They share GRA’s premise of navigating graphs instead of reading flat dumps, but assume the graph’s vocabulary is known and that traversal alone answers the question.
- GRA’s distinction: GRA uniquely combines operation without perschema tuning, a substrate uniting semantic graphs with relational tables, and computation of quantities no node stores.The paper applies this combination to turn an operator’s plain-language rule into a grounded feasibility verdict.
3 Three agents, one substrate
The section contrasts three agents on one hybrid-knowledge-graph task substrate: GRA navigates with seven generic tools, RSA removes graph structure, and SQA serializes the entire corpus. Their traces show selective discovery versus retrieved-text inference versus exhaustive context.
- GRA: GRA uses seven generic unix-style tools to orient, read, search, and query hybrid-knowledge-graph nodes without domain-specific prompts or hard-coded names.Its toolkit includes ls, cat, grep, sems, and a read-only query operation.
- GRA: GRA starts without schema, table names, or vocabulary, then discovers the knowledge graph and the definition of “late” during navigation.The demonstrated trace moves from labels and tables through literal and semantic search, node reading, querying, thinking, and answering.
- RSA: RSA removes the graph while preserving the execution loop and strategy prompt, retrieving textual documentation and table schemas through flat-search tools.Both agents share the same execution loop and prompt blocks, differing only in substrate and toolset.
- RSA: RSA reaches the same answer, but must infer concept–table links from retrieved text chunks and scan candidate tables by name rather than follow edges.This contrasts with GRA’s graph-mediated discovery of the relevant relationships.
- SQA: Approximately 17 k tokens of graph description and fully rendered schema are supplied to SQA before it answers within at most six turns.SQA performs no search or navigation; the join path is visible from the start, and later turns only repair failed queries.
4 The UFK-M benchmark
UFK-M is a synthetic bicycle-assembly factory benchmark combining executable DuckDB tables with a semantic knowledge graph. Its 258-question frozen set uses validated SQL gold answers and deterministic scoring to ensure answerability and reproducible evaluation.
- Benchmark construction: UFK-M models a fictional bicycle-assembly factory through a founding text, DuckDB data layer, and semantic knowledge graph mapped onto the tables.Two nested tiers scale the benchmark without removing information.
- Question generation: Each question is generated from a retained SQL program that produced a non-empty, non-degenerate result of at most ten rows.The LLM writes the natural-language question only after the SQL program executes successfully.
- Dataset composition: 258 questions comprise 116 table answers, 84 single values, 48 booleans, and 10 lists.The frozen xlarge set also includes 147 questions needing at most one join, 45 needing two, and 66 needing three or more.
- Gold-answer construction: Validated SQL makes every question answerable from the data, with gold answers defined by executed program outputs rather than model-generated text.34 questions additionally require the semantic layer for a named operational rule or KPI.
- Evaluation: Scoring uses a deterministic matcher with rounding-tolerant numeric comparison, scale-free percentage comparison, and recall over required gold rows for table answers.This avoids relying on an LLM judge.
5 Experimental setup
The experiments span seven backbone configurations across four providers and evaluate them under three agentic baselines. GRA/RSA receive 45 LLM-call turns, SQA receives 6, and SQL tools cap results at 50 rows.
- Backbone configurations: Seven backbone configurations across four providers are evaluated, including DeepSeek V4 variants, GPT-5 Nano, GLM-4.5-Air, and Qwen3-Coder-Flash.DeepSeek V4-Pro and V4-Pro-Think use the same weights with reasoning off versus on; GPT-5 Nano uses low versus high reasoning effort.
- Agentic baselines: Each backbone runs under three described agentic baselines, with GRA/RSA allocated 45 LLM-call turns and SQA allocated 6.The turn budgets differ substantially between the agentic systems.
- Tool configuration: SQL tools cap results at 50 rows, while GRA/RSA retrieve through the local multilingual-e5-large-instruct embedder.The passage contrasts this retrieval setup with the SQA configuration, whose description is truncated in the supplied text.
6 Results
Results show that GRA’s advantage depends on the backbone’s tool-use reliability, while selective navigation substantially reduces input context. Accuracy rises sharply with tool-call budgets up to about 30 calls, after which additional budget yields little benefit.
- Model-dependent accuracy: GRA performs best with DeepSeek and GLM models, while SQA leads with Qwen3-Coder-Flash and GPT-5 Nano.DeepSeek models exceed others by 8–18 pp under GRA and RSA, but only 2–9 pp under SQA; SQA exceeds GRA by 2.3 pp with Qwen3-Coder-Flash and 5.5 pp with GPT-5 Nano.
- Tool-call reliability: Extended reasoning changes little for reliable models: the three DeepSeek configurations differ by at most 1.2 pp with overlapping intervals.GPT-5 Nano instead gains 6.2 pp, alongside reduced call failures, indicating that reliability mediates its improvement.
- Tool-call reliability: Lower call-failure rates coincide with higher GRA accuracy: DeepSeek configurations fail well under 1% of calls, whereas GPT-5 Nano fails 10.2% and misses calls on more than half of questions.Reasoning on GPT-5 Nano roughly halves both failure measures, from 10.2% to 5.8% of failed calls and from 51.6% to 34.9% of questions with failures.
- Token usage: GRA reads 29–33% of SQA’s unique input across five models, while RSA reads 24–29%, keeping both agents below the full-context baseline.These figures measure corpus coverage rather than billed usage; graph navigation reads slightly more input than flat textual retrieval.
- Token usage: Under cache-aware pricing, warm-cache batch evaluation favors SQA, whereas cold-start single-question serving favors GRA and RSA.GRA and RSA resend growing context over 11–15 turns, while SQA averages fewer than three turns and incurs its full 17 k-token prompt for each cold-start question.
- Tool-call budget: Accuracy increases sharply from 10 to 30 tool calls and then plateaus, while truncated xlarge questions fall from 118 to 11.Accuracy is 63.6% at B = 10 on xlarge, and no measurable gain appears above 30 calls; mean turns stabilize at approximately 11 on large and 13 on xlarge.
7 Further analysis
The analysis attributes GRA’s benchmark advantage primarily to selective agentic access: with reliable tool-calling models, it achieves the largest supported gain while reading far fewer input tokens than SQA. This efficiency is expected to become more important as corpora exceed a single prompt’s capacity.
- Selective agentic access is identified as the primary source of GRA’s advantage on the benchmark.
- +5.1 pp is GRA’s largest well-supported gain when models call tools reliably.Both agents outperform SQA under this condition.
- 29–33% of SQA’s unique input tokens are read by GRA, indicating substantially lower input-token use.
- As the corpus grows beyond a single prompt’s capacity, selective reading is expected to become more valuable than processing the full serialized context.SQA’s cost scales with the full serialized context, whereas agents read only a fraction of it.
8 GRA brings industrial intelligence — complete overview
GRA operates within a factory loop that turns plain-language rules into evidence-grounded feasibility verdicts, while approved rules can be compiled into optimization models and written back to the graph. Two examples show it finding cross-layer conflicts and computing historical capacity risk at question time.
- Deployment loop: In deployment, an orchestrator asks GRA for a cited feasibility verdict, while ORA compiles accepted rules into optimization models and solver code.Plans and execution logs return to the data layer, allowing the substrate to accumulate the loop’s decisions.
- Example 1: feasibility refusal: GRA refuses the aluminium-frame rule because station 1 conflicts with quality rule R7 and station 2 has insufficient measured capacity.Standard times suggest 936 minutes against 960 available, but measured durations and changeovers raise demand to about 1,300 minutes.
- Example 1: feasibility refusal: GRA returns the refusal with evidence and two repairs: suspend the carbon-only rule for one day or move three orders to Tuesday.Neither the conflict nor the capacity shortfall was stored; both were found or computed at question time.
- Example 2: risk-aware adoption: On 11 of 428 recorded shifts, more than three colour changes were unavoidable, giving the admissible rule a measured seasonal risk.GRA therefore recommends either a hard limit with manual override on peak days or a soft constraint with a bounded penalty.
- Example 2: risk-aware adoption: After operator confirmation and expert approval, ORA formalises the rule as a mathematical constraint and solver code, then registers it as graph node R23.The write-back links the rule to the exact scheduling.mzn lines and validation evidence.
9 Conclusion
GRA applies a seven-tool, schema-agnostic navigation interface to unfamiliar hybrid industrial knowledge graphs, enabling analytical question answering and operational-rule feasibility assessment. The paper identifies reliable natural-language-to-constraint translation as the next step toward ORA.
- Conclusion: GRA uses seven generic primitives to discover schemas, vocabulary, tables, and join paths while answering analytical questions over an unfamiliar hybrid industrial knowledge graph.This mirrors how coding agents navigate unfamiliar codebases without reading them whole.
- Conclusion: GRA also judges whether new operational rules are feasible by tracing interactions across rules, tables, and computed results in the semantic and data layers.Graph paths can expose conflicts and limits several hops away, turning scattered manual investigation into grounded, auditable analysis.
- Conclusion: Future ORA work must translate approved natural-language rules into correct mathematical formulations and formal solver code that composes with existing constraints.The target is translation that is reliable, verifiable, and grounded in the graph.