Span-Based Reasoning with Anonymous Knowledge Graphs
Abstract
AbstractModern KGQA pipelines address complex multi-hop reasoning by shifting retrieval from classical embedding-based methods to iterative LLM calls. Although effective, this incurs significant computational and economic overhead that limits their applicability in real-world settings. In this paper, we introduce GRASE (Graph Reasoning with Anonymous Span Encoders), a framework that replaces LLM-driven search with a novel encoder-based graph-span representations over uncertain nodes and relations in a knowledge graph. Across several multi-hop KGQA benchmark datasets, GRASE achieves up to 85% faster inference than LLM-native pipelines while matching or exceeding state-of-the-art performance, demonstrating that encoder-only hybrid reasoning is a robust, practical, and scalable alternative to fully LLM-driven retrieval.