KGVoyager: Knowledge Graph Agnostic Question Answering via Agentic Navigation

• Domain-specific graphs often lack formal or documented ontologies, while creating example text-SPARQL pairs requires scarce domain and SPARQL expertise.These resources are more available for open-domain graphs, but are rarely available for arbitrary domain-specific knowledge graphs.Source: §1 · pp. 1–2
• KGVoyager uses KG-agnostic search, sampling, and navigation tools in a think-act-observe loop to discover graph structure and refine queries with execution feedback.It assumes only access to a SPARQL query endpoint, without pre-existing ontologies or curated example pairs.Source: §1 · p. 2
• Across four domain-specific benchmarks, KGVoyager improves F1 by ∼8 points on average and reduces cost and runtime by ∼22% each.Source: §1 · p. 2
• GRASP also targets endpoint-only, KG-agnostic SPARQL generation, but its complete entity index builds on ∼21% of Jena-served and 0% of QLever-served okn.us endpoints; KGVoyager’s class index builds on up to ∼97%.Source: §1 · p. 2
• KGVoyager is open-source and can be deployed against any SPARQL endpoint with minimal configuration.Source: §1 · p. 2

2 Related Work

• Unlike GRASP [36], KGVoyager replaces exhaustive entity indexing and ontology-based property typing with class-level indexing and data-driven inference, and combines semantic and keyword retrieval.The paper reports GRASP's complete entity index succeeds for only ∼21% of Jena-served and 0% of QLever-served endpoints in the OKN registry.Source: §2 · p. 2
• Unlike ToG [32]'s instance-by-instance traversal, KGVoyager explores graph structure and semantics to build SPARQL queries, using unified tools without graph downloads or custom traversal interfaces.ToG requires local deployment of the entire graph and a graph-specific Python traversal interface, while KGVoyager uses standard SPARQL across RDFS-compatible graphs.Source: §2 · p. 2
• KGVoyager grounds classes, properties, and entities in endpoint-only QA, while ToG [32] assumes seed entities and search cost grows with hop distance, neighborhood branching, and candidate cardinality.KGVoyager can express arbitrarily many hops in a single SPARQL execution and return results of any cardinality.Source: §2 · p. 3
• Spinach [21] uses Wikidata-specific tools, while Expasy [11] relies on curated text-query pairs and KG-specific schemas, limiting their generalization without substantial re-engineering.Expasy mitigates hallucinations via schema validation, and Spinach uses an in-context learning agent to simulate expert exploration.Source: §2 · p. 3

3 Methodology

• KGVoyager uses a think-act-observe loop [38] to search for candidate graph elements, explore their connections, and execute queries to validate and refine drafts.The tools can be invoked in any order and frequency, though the agent is prompted to generally follow the search, exploration, and execution sequence.Source: §3 · p. 3

3.1 Search Tools

• Class search combines dense-vector similarity and BM25 lexical scoring, while an adaptive filter prunes candidates below 0.125 of the top relevance score.The first class search fetches and caches a lightweight index; instance lookup supports exact-term search, semantic fallback, and optional literal-attribute search without an exhaustive entity index.Source: §3.1 · pp. 3–4
• Property search caches an index of distinct predicates and applies hybrid retrieval and adaptive filtering, returning ranked IRIs with labels, aliases, usage counts, and available domains and ranges.The retrieval and filtering approach mirrors class search.Source: §3.1 · p. 4

3.2 Exploration Tools

• Property-usage exploration samples triples to reveal subject and object classes, representative instances, and labels, helping disambiguate properties and verify their actual connections.Entity-relation exploration inspects an entity’s incoming and outgoing properties with examples, or retrieves entities matching a literal value.Source: §3.2 · pp. 4–5

3.3 Execution Tools

• The execution tool runs final and intermediate SPARQL queries, using results to test graph-structure hypotheses, check for non-empty results, diagnose errors, and iteratively self-correct.Execution-based feedback helps the agent converge on accurate queries.Source: §3.3 · p. 5

3.4 Running Example

• In a DBLP example, KGVoyager resolved a publication-count question in ten tool calls, discovered the publication-to-conference relation through exploration, and returned an answer of 1.The agent mapped the author, publication, and conference to graph classes, grounded the named entities, and used execution to run the COUNT query.Source: §3.4 · pp. 5–6, Figure 2 · p. 5

4.1 Feasibility Analysis

• Under Jena, class indexing succeeded for 69.0% of endpoints versus ∼21% for entity indexing; under QLever, class indexing succeeded for 96.6% (28/29) while entity indexing failed on all 29.Jena entity-indexing failures returned opaque server errors, while QLever failures manifested as memory crashes.Source: §4.1 · p. 6

4.2 Benchmarks and Models

• Evaluation covered Climate Models KG (52 questions), SOCKG [31] (54), DREAMKG (14), and DBLP-QuAD (100 sampled test questions).The first three benchmarks are associated with okn.us; GRASP was compared under its best-case condition, with an entity index available through direct construction, local redeployment, or a pre-built index.Source: §4.2 · p. 6

4.3 QA Performance

• F1 gains ranged from 3.9 percentage points on DBLP to 14.0 points on Climate Models KG.KGVoyager also reduced cost on every benchmark and required fewer iterations throughout; runtime was lower on three benchmarks, with DBLP the exception because its entity-specific questions favored GRASP’s pre-supplied entity index.Source: §4.3 · p. 7, Table 2 · p. 7
• Manual contrast cases linked KGVoyager’s advantages to separate class, instance, and property tools, neighborhood examples, and adaptive filtering that mitigates context rot.GRASP could approximate neighborhood exploration, but often with more iterations and fragility; the paper also reports a detailed analysis of poor-performing cases in Appendix C.Source: §4.3 · pp. 7–8

4.4 Tool-Use Dynamics

• Gemini 3 Flash Preview showed cleaner search–exploration–execution phase separation than Devstral Small, whose benchmark-averaged KGVoyager F1 was 46.8% versus 70.1% and whose mean iterations were 22.30 versus 12.39.The authors suggest phase mixing signals that a model finds the task challenging.Source: §4.4 · p. 8

4.5 Ablation Study

• Removing explore_entity_relations reduced F1 across all three model–benchmark pairs, while hybrid retrieval improved F1 by 2.7–6.1 points over keyword-only search and reduced cost and iterations.Adding explore_property_usage raised F1 by up to 8.7 points on SOCKG and 4.8 points on DREAMKG with Gemini 3 Flash, at added time, money, and iterations; GPT-5.4 Mini showed no SOCKG gain. Ablations retained search and query execution, focusing on additional navigation mechanisms.Source: §4.5 · p. 8

• KGVoyager answers natural-language questions over arbitrary RDF knowledge graphs using only access to a SPARQL endpoint.It is a knowledge-graph-agnostic framework.Source: §5 · p. 8
• 96.6% of okn.us endpoints were supported by KGVoyager’s lightweight class index under QLever, versus 0% by GRASP’s required entity index; across four benchmarks and four backbones, it improved F1 while generally reducing runtime, cost, and agent iterations.The results demonstrate endpoint-only KGQA feasibility and efficiency for domain-specific knowledge graphs where curated resources are often unavailable.Source: §5 · p. 8

Limitations

• The tool suite assumes standard RDFS/RDF typing patterns, making KGVoyager best suited to RDFS-compatible graphs and not broadly applicable to differently modeled graphs such as Wikidata.Supporting such graphs may require adapter tools or graph-specific normalization layers, left for future work.Source: Limitations · p. 8
• Domain-specific text-SPARQL benchmarks remain scarce, and outreach to KG authors and maintainers did not yield larger datasets.The authors call for more public benchmarks and suggest automated benchmark generation as a promising direction.Source: Limitations · p. 8

• The experiments used publicly available knowledge-graph endpoints and benchmarks, collected or processed no private or personal data, and used existing artifacts for research and benchmarking.Released artifacts are intended for research, evaluation, and reproducibility; third-party resources remain subject to their original terms.Source: Ethical Considerations · p. 9
• KGVoyager may generate syntactically valid but semantically incorrect SPARQL queries, so users should verify outputs before relying on them for scientific or policy decisions.Source: Ethical Considerations · p. 9
• KGVoyager reduced monetary cost and wall-clock runtime by approximately 22% relative to the prior state-of-the-art system, partially mitigating LLM inference’s environmental cost.Source: Ethical Considerations · p. 9

A Implementation Details

• Table 4 lists the key implementation parameters used across all experiments.Source: A Implementation Details · p. 12, Table 4 · p. 12

B Query Complexity Analysis

• Query complexity was measured by counting triple patterns in translated SPARQL algebra and distinct special constructs, including aggregation, FILTER, OPTIONAL, UNION, MINUS, EXISTS, subqueries, and property paths.Source: B Query Complexity Analysis · p. 12
• The analysis pooled four benchmarks, averaged repeats within each backbone model, then averaged across models to compute paired per-question KGVoyager-minus-GRASP F1 differences.Source: B Query Complexity Analysis · p. 12
• KGVoyager’s average F1 improvement over GRASP appears larger for queries with at least five triple patterns, suggesting greater tool-suite benefit on structurally complex queries.Figure 5 groups mean paired F1 differences by triple-pattern count and number of distinct special SPARQL constructs.Source: Figure 5 · p. 12, B Query Complexity Analysis · p. 12

• The analysis defined complete failures as model–KG–question triples scoring F1 0 across three independent runs, then manually assigned one or more root causes to a random sample of 50 of 148 cases.The 148 cases spanned four models and benchmarks; causes were organized in a two-level taxonomy with six coarse-grained groups.Source: C Failure Analysis · p. 12
• 48% of failures stemmed from concept resolution: 24% wrong property choice, 18% wrong entity grounding, and 6% wrong class grounding, making property ambiguity the primary failure driver.Source: Table 5 · p. 12, C Failure Analysis · p. 13
• Query construction errors accounted for 22% of failures and mostly involved missing constraints; 12% were over-constrained gold queries that unfairly penalized valid answers, slightly understating F1.Source: C Failure Analysis · p. 13

D Tool Invocation Distributions

• Across four benchmarks, four backbone models, and three runs, KGVoyager often requires fewer tool invocations or SPARQL executions per question.Figure 6 reports the pooled distributions of both measures; the passage gives no numerical values.Source: D Tool Invocation Distributions · p. 13, Figure 6 · p. 13

E KGVoyager System Prompt and Tool Specification

• Figure 7 presents the KGVoyager system prompt.Source: Figure 7 · p. 14
• Figure 8 presents KGVoyager’s search-tool specifications.Source: Figure 8 · p. 14
• Figure 9 presents KGVoyager’s exploration-tool specifications.Source: Figure 9 · p. 15
• The execution tool runs SPARQL against the knowledge graph and supports both final-answer retrieval and iterative reasoning feedback.It can be used to test intermediate query drafts and diagnose errors in partial queries.Source: E KGVoyager System Prompt and Tool… · p. 15
• Verification queries should use LIMIT to avoid fetching too much data, and the final query should use LIMIT only when consistent with the question.Source: E KGVoyager System Prompt and Tool… · p. 15
• Execution returns a table with query-result columns or an error message if the query fails.Source: E KGVoyager System Prompt and Tool… · p. 15
• Figure 10 presents KGVoyager’s execution-tool specifications.Source: Figure 10 · p. 15