MARS: Multi-hop Adaptive Retrieval and SPARQL Generation for KGQA

Technical Summary of MARS: Multi-hop Adaptive Retrieval and SPARQL Generation for KGQA

Problem Statement
Large Language Models (LLMs) demonstrate strong reasoning capabilities but suffer from hallucinations and factual inconsistencies, particularly in knowledge-intensive tasks requiring up-to-date, grounded information. While Retrieval-Augmented Generation (RAG) mitigates these issues, text-based RAG struggles with complex multi-hop reasoning because relational structures are only implicitly represented in text. Conversely, existing Knowledge Graph Question Answering (KGQA) approaches face significant trade-offs:

• Fact-retrieval methods that retrieve subgraphs for LLM reasoning often exceed context window limits when dealing with large, relevant subgraphs.
• Fine-tuned Question-SPARQL models are limited by training data coverage and diversity.
• Agent-oriented approaches relying on LLMs for iterative graph exploration are vulnerable to error propagation and hallucination at every step.
• Reproducibility challenges persist as benchmark datasets are often released without the specific Knowledge Graph (KG) versions used during their creation, or with versions lacking necessary coverage.

Methodology: The MARS Pipeline
MARS is a scalable, fine-tuning-free approach that combines pattern-based graph retrieval with context-augmented knowledge to generate executable SPARQL queries. It operates via a structured, three-stage pipeline that iteratively refines context until a query can be generated or a multi-hop limit is reached.

1. Entity Linking and Text Augmentation:
   The system first extracts entities from the input question using a pipeline based on GRASP. To support graph traversal and non-English queries, it employs a multilingual LLM for translation and an instruction-tuned LLM to generate augmented text ($q_{aug}^{text}$) that incorporates predicted entity type labels. This hybrid strategy preserves the original query's semantic structure while leveraging translation for entity linking.

2. Pattern Retrieval and Filtering:
   Instead of retrieving raw triples or full subgraphs, MARS retrieves triple patterns (predicate, entity, placeholder).

   • Pattern Definition: Patterns are defined as $(s, p, \_)$ or $(\_, p, o)$ based on the extracted entities.
   • Verbalization: Patterns are converted into natural language strings (e.g., "entity predicate ?object").
   • Semantic Ranking: These verbalized patterns are embedded and ranked by semantic similarity to the input question. The top-$N$ patterns are selected.
   • Enrichment: The selected patterns are enriched with instance counts, instance labels (limited to a subset to reduce cost), and typological information (domain and range constraints from the KG schema).

3. Iterative Reasoning and SPARQL Generation:
   An LLM (acting as a SPARQL Reasoner) receives the original question and the enriched pattern context.

   • Decision Loop: The model determines if the current context is sufficient to generate the final SPARQL query ($q_{sparql}$).
   • Adaptive Traversal: If the context is insufficient, the model selects specific patterns to expand. The system extracts the entities from these patterns, treats them as new starting points, and repeats the pattern retrieval process to gather "next-hop" information.
   • Termination: The loop continues until a query is generated or a predefined multi-hop limit ($m_{hop}$) is reached.

Key Contributions

1. Pattern-Based Retrieval: A method that curtails LLM context size by filtering and ranking triple patterns rather than operating on raw subgraphs, iteratively incorporating next-hop facts into reasoning.
2. Hybrid Multilingual Setup: A framework that combines machine translation with native-language text and entity-type augmentation, supporting 10 languages (including four low-resource languages) across three benchmark datasets.
3. Comprehensive Evaluation and Analysis: An in-depth ablation study on features (e.g., concrete examples, typological info, verification) and configurations, alongside a detailed error analysis.
4. Reproducibility: The release of the underlying Wikidata snapshot used for evaluation, updated datasets, and code using open-weight LLMs to address the common issue of KG version drift in benchmarks.

Experimental Results
MARS was evaluated on three benchmarks: LC-QuAD2.0 (large-scale English), QALD-9-plus (multilingual), and QALD-10 (complex, multi-hop queries).

• Performance: MARS achieved competitive or state-of-the-art Macro F1 scores across all datasets. Notably, on the highly complex QALD-10 benchmark (where ~29% of queries require multi-hop reasoning), MARS outperformed all baselines, including the agentic system GRASP, across all four evaluated languages.
• Comparison to Baselines: MARS outperformed fine-tuned models (DeepPavlov, UniQ-Gen, MST5) and the agentic baseline GRASP in 8 of 14 head-to-head comparisons. The results suggest that a fixed, planning-oriented pipeline is more effective than dynamic tool-selection agents for multi-hop questions.
• Ablation Insights:
  • Concrete Examples: Providing concrete instance examples from retrieved patterns significantly improved performance.
  • Verification: A second pass to verify and update the generated SPARQL query yielded substantial gains.
  • Configuration: The optimal configuration used GPT-OSS with a top-$N$ of 20 patterns and a multi-hop limit of 10, balancing inference cost and accuracy.

Significance and Limitations
The paper claims that MARS demonstrates that deterministic, pattern-guided abstraction loops can outperform fully agentic approaches in multi-hop KGQA by reducing hallucination risks and providing more predictable retrieval depths. The approach achieves high performance without dataset-specific fine-tuning, relying instead on the reasoning capabilities of open-weight LLMs guided by structured retrieval.

The authors acknowledge specific limitations:

• Technical Constraints: Errors primarily stem from result truncation (capping at 1,000 results), missing boolean/aggregate projections (ASK, COUNT), and overly cautious literal generation.
• Scalability: Pattern retrieval on high-degree nodes in large-scale KGs (like Wikidata) requires specialized triple stores (e.g., Tentris) for efficient joins.
• Benchmark Coverage: Evaluation was restricted to Wikidata-based benchmarks; extending to Freebase or DBpedia is future work.
• Reproducibility Standards: The paper highlights that F1 scores are not directly comparable across different papers due to varying denominator definitions (predicted sets vs. exact match vs. components), necessitating the re-evaluation of all baselines under a unified protocol.

The work concludes that while MARS is not a perfect solution, it offers a robust, reproducible, and efficient alternative to current fine-tuned and agentic KGQA systems, particularly for complex, multi-hop reasoning tasks.