PYTHIA: Universal Question Answering over Knowledge Graphs
Knowledge graph question answering (KGQA) focuses on answering questions with data retrieved from knowledge graphs (KGs). Although Large Language Models (LLMs) have enabled the development of innovative KGQA systems, serious challenges remain. Approaches that utilize supervised finetuning are accurate and responsive, but also require large training datasets that provide good coverage of both the target knowledge graph and expected user questions. Likewise, integrating KG-specific optimizations improves accuracy and responsiveness but limits versatility and is susceptible to updates to the KG's ontology. LLMs have facilitated the development of training-free and KG-agnostic solutions that utilize reasoning and real-time decision making to explore the target KG, but the semi-structured nature of KGs makes this a complex and unpredictable task, leading to performance degradation and longer response times. In this paper we present PYTHIA, a training-free, plug-and-play solution for KGQA over any RDF KG. At its core, PYTHIA consists of an LLM agent guided by a relation-centric conceptual model of the KGQA task which is acted upon through a suite of tools for entity linking, graph exploration and query execution. The agent is responsible for interpreting user intent, orchestrating tool calls, and evaluating tool output, while the tools themselves present simple interfaces that abstract complex processes, reducing cognitive load on the agent. To assess its viability, we perform a comprehensive evaluation of PYTHIA and prior systems across four knowledge graphs and six datasets. The results show PYTHIA achieving a median performance improvement of 15.31% while improving cost and time efficiency at the performance frontier.