Efficient Retrieval-Augmented Generation via Token Co-occurrence Graphs
2026-06-29 • Computation and Language
Computation and LanguageInformation Retrieval
AI summaryⓘ
The authors present TIGRAG, a new method to help language models answer complex questions requiring multiple steps. Instead of relying on slow and error-prone techniques, TIGRAG builds a simple graph based on how words appear together in texts. It uses this graph to find connected pieces of information by expanding questions step-by-step with related terms. Their tests showed that TIGRAG retrieves better evidence and answers questions more accurately than other methods, while also being faster and more efficient.
Retrieval-Augmented GenerationLarge Language ModelsMulti-hop ReasoningKnowledge GraphToken Co-occurrenceSemantic ExpansionNeural RerankingEntity-driven RetrievalQuestion AnsweringInference Latency
Authors
Gianluca Bonifazi, Christopher Buratti, Michele Marchetti, Federica Parlapiano, Giulia Quaglieri, Davide Traini, Domenico Ursino, Luca Virgili
Abstract
Retrieval-Augmented Generation (RAG) mitigates hallucinations in Large Language Models (LLMs) by grounding the generation process on external knowledge. However, standard RAG approaches struggle with multi-hop reasoning. While recent graph-based RAG methods improve the retrieval of interconnected chunks, they often rely on computationally expensive and error-prone LLM-based extraction pipelines. To address these issues, we propose TIGRAG (Token-Induced GraphRAG), an efficient graph-augmented RAG framework based on a token co-occurrence Knowledge Graph. TIGRAG directly models topological relationships between tokens using sliding-window co-occurrence statistics, thus enabling scalable graph construction. During inference, it combines graph-based semantic expansion and neural reranking to retrieve interconnected evidence for multi-hop reasoning. Specifically, it introduces an iterative entity-driven retrieval strategy that progressively expands the query using bridging entities extracted from previously retrieved contexts. We evaluated TIGRAG on three widely adopted multi-hop Question Answering (QA) benchmarks. Experimental results demonstrated that our framework consistently outperforms dense retrieval and graph-based RAG methods in both retrieval and downstream QA tasks, while substantially reducing indexing time, inference latency, and prompt footprint.