TLDR: TERAG is a novel framework for graph-based Retrieval-Augmented Generation (RAG) that addresses the high token consumption and costs associated with building knowledge graphs for LLMs. It achieves significant cost reduction by employing lightweight LLM calls for concept extraction and efficient non-LLM methods for graph construction. TERAG then uses Personalized PageRank for retrieval, maintaining competitive accuracy on multi-hop question-answering benchmarks while reducing output token usage by 89-97% compared to existing graph-based RAG methods.
In the rapidly evolving landscape of Artificial Intelligence, Retrieval-Augmented Generation (RAG) has emerged as a crucial framework to enhance the reliability and accuracy of Large Language Models (LLMs). RAG systems help LLMs access external knowledge, preventing them from “hallucinating” or generating incorrect information. While traditional RAG often retrieves simple text snippets, a more advanced approach, known as graph-based RAG, leverages knowledge graphs to model complex relationships between pieces of information. This structured method allows for more sophisticated reasoning and offers greater transparency into how an AI model arrives at its answers.
However, the impressive capabilities of current state-of-the-art graph-based RAG systems come with a significant drawback: high operational costs. These systems often rely heavily on LLMs for various stages of graph construction, such as extracting entities, defining relationships, and inducing schemas. This extensive use of LLMs leads to a massive consumption of “tokens” – the basic units of text processed by LLMs – making the construction of these knowledge graphs prohibitively expensive for large-scale applications. For instance, indexing a relatively small dataset of legal documents was recently estimated to cost tens of thousands of dollars.
Introducing TERAG: A Token-Efficient Solution
To tackle this critical challenge, researchers have proposed TERAG (Token-Efficient Graph-Based Retrieval-Augmented Generation), a novel framework designed to build informative knowledge graphs at a significantly lower cost. TERAG aims to strike a better balance between cost and performance by minimizing LLM usage during the graph construction phase, while still harnessing their strengths for essential concept extraction.
Instead of engaging LLMs in multiple, expensive rounds of reasoning for graph creation, TERAG employs a streamlined approach. It uses a few carefully designed prompts to extract multi-level concepts, including named entities and broader document-level concepts, directly from the source text. These extracted concepts are then efficiently structured into a knowledge graph using non-LLM methods. This process is far less token-intensive, drastically reducing the financial burden.
For the retrieval phase, TERAG takes inspiration from HippoRAG and utilizes a technique called Personalized PageRank (PPR) on the constructed graph. This method enhances the effectiveness of information retrieval without requiring additional LLM calls, further contributing to its overall efficiency. By focusing LLM usage on initial, lightweight tasks, TERAG achieves a favorable trade-off between efficiency and effectiveness.
Key Advantages and Performance
The core contributions of TERAG are its ability to significantly reduce LLM token consumption during graph construction and its competitive retrieval accuracy. Experiments show that TERAG reduces output token usage by an impressive 89-97% compared to other widely-used graph-based RAG methods. This makes it a highly cost-effective solution for deploying RAG systems at scale.
Despite its lightweight design, TERAG maintains strong retrieval accuracy across standard multi-hop question-answering benchmarks like MuSiQue, HotpotQA, and 2WikiMultihopQA. For example, on the 2Wiki dataset, TERAG achieved accuracy levels very close to the widely adopted GraphRAG, while consuming substantially fewer tokens. The framework consistently meets its predefined performance target, achieving at least 80% of the accuracy of more expensive systems like AutoSchemaKG combined with HippoRAG.
The efficiency gains are particularly notable in output token consumption, which is a major driver of LLM inference costs. TERAG consumes dramatically fewer output tokens—ranging from 3% to 11% of what other lightweight graph-based RAG methods use. This is crucial because generating output tokens is computationally more intensive than processing input tokens.
An ablation study further confirmed the effectiveness of TERAG’s approach to calculating the Personalized PageRank restart vector, which combines semantic relevance and concept frequency. This novel weighting scheme consistently improved retrieval accuracy across all tested datasets.
Also Read:
- Enhancing RAG Systems: A New Approach to Document Utility with Process Supervision
- Enhancing Math Textbook Learning: A Deep Dive into AI Retrieval Systems
Conclusion
TERAG represents a significant step forward in making advanced graph-based RAG systems more accessible and affordable. By simplifying the graph construction process and focusing on token efficiency, it demonstrates that powerful RAG systems can be built without incurring exorbitant costs. This framework offers a practical solution for organizations looking to leverage the benefits of graph-based RAG without the prohibitive expenses associated with heavy LLM reliance. You can read the full research paper here: TERAG: Token-Efficient Graph-Based Retrieval-Augmented Generation.
