Technical Summary: TIGRAG (Token-Induced GraphRAG)

1. Problem Statement

Retrieval-Augmented Generation (RAG) is a standard approach for mitigating hallucinations in Large Language Models (LLMs) by grounding generation in external knowledge. However, standard vector-based RAG systems treat documents as isolated units, making them ineffective for multi-hop reasoning tasks that require synthesizing dispersed evidence across independent text chunks.

While Graph-augmented RAG (GraphRAG) approaches attempt to solve this by modeling relationships via Knowledge Graphs (KGs), they face two critical barriers to adoption:

1. Computational Overhead: Offline KG construction often relies on computationally expensive and latency-inducing LLM-based extraction pipelines.
2. Extraction Vulnerabilities: LLM-driven entity and relationship extraction are prone to hallucinations, noise, and missing connections. These errors propagate through the retrieval pipeline, causing cascading failures in downstream reasoning.

2. Methodology: TIGRAG Architecture

The authors propose TIGRAG (Token-Induced GraphRAG), a framework that constructs a topological Knowledge Graph directly from token co-occurrences rather than relying on LLM-based extraction. The architecture operates in two stages: Offline Graph Construction and Online Inference.

2.1. Offline Graph Construction

Instead of using LLMs to extract entities and relations, TIGRAG uses a statistical approach:

• Preprocessing: The corpus is segmented into overlapping text chunks using a sliding-window strategy over sentences.
• Tokenization: Chunks are tokenized, and stopwords are removed. Valid tokens are filtered based on length and numerical constraints.
• Graph Building: A weighted, undirected KG is constructed where:
  • Nodes represent valid tokens.
  • Edges represent co-occurrences between tokens within a sliding window of size $w$.
  • Weights correspond to the cumulative frequency of co-occurrences across the corpus.
• Embeddings: Dense vector representations for each chunk are precomputed and indexed for similarity search.

2.2. Online Inference

The retrieval process is iterative and multi-hop, consisting of four core components:

1. Semantic Expansion (PPR):
   • The user query is tokenized to identify seed nodes in the KG.
   • Personalized PageRank (PPR) is executed starting from these seed nodes to explore the topological neighborhood and identify semantically related concepts.
   • The top-$\gamma$ nodes are selected to form an expanded token set $\Phi_\mu$.
2. Candidate Retrieval & Graph-Weighted Scoring:
   • Candidate chunks are retrieved if they contain tokens from the original query or the expanded set.
   • A hybrid score $\rho(c, \mu)$ is calculated by combining BM25 scores with the PPR-derived probability weights of the tokens, prioritizing structurally relevant concepts over simple lexical overlap.
3. Dynamic Candidate Pooling:
   • A cumulative score thresholding mechanism filters the candidate list. Only chunks whose cumulative score reaches a predefined fraction ($th_\rho$) of the total score mass are retained, dynamically adjusting the pool size based on confidence.
4. Neural Reranking:
   • The dynamic pool is reranked using cosine similarity between the query embedding and chunk embeddings to ensure maximum semantic fidelity.

2.3. Multi-Hop Reasoning Strategy

To handle complex queries requiring multiple reasoning steps:

• Iterative Entity-Driven Expansion: After the first retrieval hop, the top retrieved chunks are processed through a Named Entity Recognition (NER) pipeline.
• Query Augmentation: New, unseen entities extracted from these chunks are concatenated to the original query to form an expanded query ($\mu_{exp}$).
• Re-retrieval: The graph-based retrieval and reranking process is repeated using the expanded query.
• Termination: The process stops when no new entities are found or a maximum hop limit is reached.
• Final Aggregation: Retrieved chunks from all hops are merged, retaining the maximum relevance score for each chunk, and the top-$\beta$ chunks are injected into the LLM prompt.

3. Key Contributions

• Efficient Graph Construction: TIGRAG eliminates the need for LLM-based entity extraction by constructing the KG via token co-occurrence statistics, significantly reducing indexing time and computational cost.
• Topological Semantic Expansion: It leverages PPR to naturally propagate retrieval signals across semantic nodes, enabling the discovery of interconnected evidence without explicit query decomposition.
• Iterative Entity-Driven Retrieval: The framework introduces a mechanism to progressively expand queries using bridging entities from retrieved contexts, specifically targeting multi-hop reasoning gaps.
• Hybrid Scoring & Reranking: It combines graph-weighted structural relevance with neural semantic alignment to filter noise and ensure high-quality context selection.

4. Experimental Results

The framework was evaluated on three multi-hop QA benchmarks: HotpotQA, 2WikiMultiHopQA, and MuSiQue.

• Retrieval Performance: TIGRAG consistently outperformed dense retrieval (NaiveRAG) and state-of-the-art graph-based methods (including HippoRAG2, LightRAG, and GraphRAG).
  • On HotpotQA, it improved Recall@2 by 9.70% over NaiveRAG.
  • On MuSiQue, it achieved a 19.92% gain in Recall@2 over HippoRAG2.
• Downstream QA Performance: TIGRAG achieved new state-of-the-art results in Exact Match (EM) and token-level F1 scores across all datasets. For instance, on HotpotQA, it improved EM by 13.67% over NaiveRAG.
• Efficiency:
  • Indexing Time: TIGRAG's offline graph construction was substantially faster than other graph-based methods (e.g., ~191s vs. ~308,000s for HippoRAG2 on HotpotQA) and comparable to dense retrieval.
  • Inference Latency: On complex datasets (2WikiMultiHopQA, MuSiQue), TIGRAG was faster end-to-end than NaiveRAG due to the reduced prompt footprint.
  • Prompt Footprint: By dynamically selecting compact, high-relevance chunks, TIGRAG significantly reduced the number of tokens sent to the LLM compared to methods that inject extensive KG summaries or triplets.

5. Significance and Claims

The paper claims that TIGRAG demonstrates that graph-augmented RAG systems can solve complex multi-hop reasoning tasks without sacrificing computational efficiency.

• Scalability: By bypassing expensive LLM-driven graph construction, TIGRAG offers a highly scalable solution suitable for real-world deployment.
• Robustness: The statistical construction of the graph avoids the hallucination and noise issues inherent in LLM-based extraction pipelines.
• Performance: The framework establishes new benchmarks for both retrieval accuracy and generation quality in multi-hop QA, proving that topological expansion via token co-occurrence is a viable and superior alternative to traditional dense retrieval and complex GraphRAG architectures.

The authors acknowledge limitations, noting that the framework relies on the quality of the NER pipeline (risking semantic drift if entities are inaccurate) and primarily captures relationships based on token proximity. Future work is proposed to incorporate semantic edges, address token polysemy, and extend the approach to multimodal settings.