Mixture-of-PageRanks: Replacing Long-Context with Real-Time, Sparse GraphRAG

Nicholas Alonso, Beren MillidgearXiv 2024 · DOI · arXiv

Introduction

Modern Large Language Models (LLMs) like GPT-4o and Gemini 1.5 Pro have expanded context windows to millions of tokens. However, this capability introduces a significant "long-context tax": computational costs grow quadratically with sequence length, and the memory requirements for KV-caches become prohibitively expensive. While Retrieval-Augmented Generation (RAG) offers an alternative by providing only relevant snippets, it often suffers from a "retrieval gap" in complex multi-hop reasoning tasks and a "latency gap" due to the heavy compute required for neural embeddings.

To address these challenges, we present Mixture-of-PageRanks (MixPR), a novel GraphRAG framework. MixPR enables LLMs to process million-token contexts with state-of-the-art accuracy while running entirely on a CPU, offering a scalable and cost-effective solution for long-context processing.

The MixPR Framework

MixPR conceptualizes a long document as a graph where text chunks serve as nodes and their similarities define the edges. The framework incorporates several key innovations to optimize both speed and retrieval quality:

  • Sparse Embeddings (TF-IDF): Unlike traditional RAG systems that rely on heavy neural networks, MixPR uses TF-IDF for embeddings. This allows for the indexing of millions of tokens in seconds on standard CPU hardware.
  • Personalized PageRank (PPR): To identify the most relevant chunks, MixPR utilizes the PageRank algorithm. This approach moves beyond simple keyword similarity to identify chunks that are structurally "important" within the document's context.
  • The "Mixture" Mechanism: The core of the system is a dynamic hyperparameter, $\alpha$. A high $\alpha$ value prioritizes local retrieval (standard search), while a low $\alpha$ focuses on global retrieval (structurally central chunks).
  • LLM Router: A lightweight, zero-shot LLM call automatically determines whether a query requires a local or global perspective, adjusting the PageRank settings in real-time.
Comparison of retrieval strategies: Standard RAG vs. PageRank-based methods.

Experimental Evaluation

MixPR was evaluated against several rigorous long-context benchmarks designed to test different reasoning capabilities:

  • BABILong: Evaluates the ability to retrieve specific information hidden within up to 10 million tokens.
  • RULER: A comprehensive suite of 13 tasks, including variable tracing and multi-hop reasoning.
  • Hash-Hop: A synthetic benchmark requiring the model to follow chains of assignments across long documents.
  • Infinite-Bench (Eng.Sum): Tests the system's ability to summarize entire books.

Key Results and Efficiency

MixPR demonstrates superior performance and efficiency compared to both native long-context models and standard RAG implementations:

  • State-of-the-Art Accuracy: MixPR achieved SOTA results on the RULER benchmark. On the BABILong leaderboard, MixPR-augmented models rank 2nd overall, surpassed only by models specifically fine-tuned for that task.
  • Multi-Hop Reasoning Gains: On tasks like Hash-Hop, MixPR improved performance over baseline RAG by up to 50%, proving its efficacy in linking disparate pieces of information.
  • Computational Efficiency: The system can embed and retrieve from millions of tokens in seconds on a CPU. Crucially, as input length grows, the number of tokens actually processed by the LLM remains nearly constant, avoiding the quadratic cost of native long-context processing.
Performance and efficiency metrics across BABILong and RULER benchmarks.

Insights and Future Work

The success of MixPR highlights that document structure is as vital as keyword similarity for effective retrieval. By utilizing sparse matrices, the authors demonstrate that high-quality retrieval does not necessitate expensive GPU resources.

However, some limitations remain. Summarization continues to be a difficult task to perform and evaluate perfectly. Additionally, the system's performance is dependent on the accuracy of the initial LLM router. Future research may explore hybrid sparse-dense approaches to capture more subtle semantic nuances while maintaining the speed advantages of the current framework.

Summary updated

BibTeX
@misc{alonso2024mixture,
  author = {Nicholas Alonso and Beren Millidge},
  title = {{Mixture-of-PageRanks: Replacing Long-Context with Real-Time, Sparse GraphRAG}},
  year = {2024},
  eprint = {2412.06078},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2412.06078},
}
Figure