Accelerating MIPS: Making RAG Retrieval Faster and More Efficient

The core bottleneck of Retrieval-Augmented Generation (RAG) often lies not in generation, but in retrieval. When faced with millions of candidate vectors and thousands of dimensions, the computational cost of Maximum Inner Product Search (MIPS) rises sharply. The source material points out that as the number of keys grows to millions and vector dimensionality reaches thousands, the computational overhead of exhaustive search becomes prohibitive. How to accelerate MIPS without sacrificing accuracy is key to improving overall RAG efficiency.

MIPS: The Compute Black Hole of RAG Retrieval

The problem MIPS solves is intuitive: given a query vector, find the candidate key vector with the largest inner product among millions of candidates, then retrieve its associated raw data. In the RAG context, this "raw data" is the document most likely to answer the question, typically concatenated with the query and fed into the generation model.

The problem is that exact exhaustive search requires computing the inner product of the query with every single candidate vector. When the number of candidates reaches millions and dimensionality reaches thousands, the floating-point operations per query balloon to the billion scale. For online RAG services requiring low-latency responses, this constitutes a real performance wall.

Maximum Inner Product Search (MIPS) is a fundamental problem in vector retrieval: given a query vector q and a set of candidate key vectors {k₁, k₂, …, kₙ}, the goal is to find the key that maximizes the inner product ⟨q, kᵢ⟩ and return its associated raw data. It is mathematically interchangeable with Euclidean nearest-neighbor search—when vectors are normalized, inner product maximization is equivalent to cosine similarity maximization, which is also equivalent to Euclidean distance minimization. Therefore, many ANN algorithms originally designed for distance search can be adapted for MIPS with slight modifications. The geometric meaning of the inner product is the projection length of the query onto the candidate direction multiplied by the candidate's magnitude, which means MIPS favors not only vectors with similar direction but also vectors with larger magnitude—a subtle difference from pure cosine similarity that requires attention to whether vectors are normalized when building indexes.

Approximate Search: Trading Controlled Error for Order-of-Magnitude Speedup

Faced with the computational pressure of exhaustive search, the industry's mainstream approach is Approximate Nearest Neighbor (ANN) search—sacrificing "absolute precision" for "good enough and much faster" retrieval results. Although the source material does not elaborate on specific algorithm details, it explicitly raises the scaling computational cost of MIPS as a core problem, which itself points to the necessity of approximate methods in the RAG pipeline.

From an engineering perspective, the acceleration logic of approximate MIPS typically revolves around two directions: reducing the number of candidates that need to participate in inner product computation, and lowering the cost of each individual inner product computation. The former relies on smarter index structures, while the latter relates to techniques such as vector quantization and dimensionality reduction. For RAG systems, a slight drop in retrieval recall can often be partially compensated by the generation model's context understanding capability, making approximate search highly cost-effective in RAG.

Approximate Nearest Neighbor (ANN) search has recall (recall@k) as its core metric—the proportion of true Top-k results captured by approximate results—alongside speedup ratio (the multiple of QPS improvement relative to exact search). Common index families include graph-based methods (such as HNSW, which achieves logarithmic-level hops through navigable small-world graphs), quantization-based methods (such as Product Quantization, PQ, which partitions high-dimensional vectors into subspaces for separate encoding and replaces floating-point inner products with table lookups), hashing-based methods (such as Locality-Sensitive Hashing, LSH), and tree-based partitioning methods. Different methods have different trade-offs in recall, memory usage, build time, and incremental update capability. RAG scenarios typically also care about filtered search (MIPS with metadata constraints), which imposes additional requirements on index structures.

How Retrieval Efficiency Affects RAG's End-to-End Performance

The typical RAG pipeline is "retrieve—concatenate—generate." Once the retrieval stage slows down, the latency of the entire chain is dragged down, especially in multi-turn conversations or high-concurrency scenarios. Faster MIPS means more candidates can be retrieved within the same time budget, more refined reranking can be performed, or the response time per query can be directly reduced.

The source material's emphasis on "Faster Retrieval for Better, More Efficient RAG" actually points to a dual benefit: faster retrieval not only makes RAG more efficient (lower latency, higher throughput) but may also make RAG better (allowing more thorough retrieval and filtering within the same time budget). These two are not a trade-off but can be improved simultaneously through algorithmic optimization.

Reranking is a common step in the RAG retrieval pipeline: first, lightweight, high-speed ANN retrieval is used to recall a larger candidate set (e.g., top-100), then a more precise but more expensive cross-encoder scores and reranks candidates pairwise. This two-stage structure directly reflects the value of "faster MIPS"—the time budget saved in the retrieval stage can be transferred to the reranking stage, thereby improving the quality of documents ultimately fed to the generation model without increasing end-to-end latency. Additionally, RAG involves context window constraints: the number of tokens the generation model can accept is limited, and too many recalled documents will crowd out space and introduce noise, so the number of retrieved documents and reranking precision need to be jointly tuned with the context budget.

Trade-offs in Deployment

Introducing accelerated MIPS into RAG systems requires attention to several practical trade-offs. First is the balance between recall and speed: the higher the degree of approximation, the faster the speed, but the greater the risk of missing truly relevant documents. Second is index maintenance cost: candidate vector stores often need dynamic updates, and whether the index structure can efficiently support incremental writes directly affects system operability. Third is coordination with the generation stage: the number and quality of documents returned by retrieval need to match the generation model's context window, and blindly increasing recall numbers may actually dilute key information.

The source material positions MIPS as a shared foundational capability across recommendation systems, search, and RAG, meaning that related optimizations are not RAG-specific but can be reused in broader retrieval scenarios. For teams building RAG applications, understanding MIPS's cost structure and acceleration approaches is a prerequisite for making sound architectural decisions.

Summary

The scaling computational cost of MIPS is a key constraint on RAG efficiency. Through acceleration methods such as approximate search, significant retrieval speed improvements can be achieved with controlled accuracy loss, thereby improving RAG's end-to-end latency and throughput. In actual deployment, it is necessary to find the right balance among recall, index maintenance, and generation coordination for one's own business needs.

One-line Summary

MIPS's scaling computational cost is the bottleneck of RAG efficiency; approximate search can trade for order-of-magnitude speedup.

Paragraph Summary

The article points out that the core bottleneck of Retrieval-Augmented Generation (RAG) often lies in retrieval rather than generation. Maximum Inner Product Search (MIPS) requires finding the key with the largest inner product with a query among millions of candidate vectors with thousands of dimensions; exact exhaustive search can involve billion-scale floating-point operations per query, posing a performance wall for low-latency online services. The industry's mainstream approach is approximate nearest neighbor search, which reduces the number of candidates participating in computation through smarter index structures, or lowers per-computation cost through quantization and dimensionality reduction—trading controlled accuracy loss for order-of-magnitude speedup, while slight recall drops in RAG can often be partially compensated by the generation model. Faster retrieval brings dual benefits: lower latency and higher throughput, and potentially more thorough retrieval and reranking within the same time budget. In deployment, trade-offs must be made among recall vs. speed, incremental index maintenance cost, and coordination with the generation context window.