Optimizing MIPS Retrieval with Learned Networks

When a RAG/retrieval system has: (1) a large, mostly-static key database, (2) a known, stable query distribution (e.g., real user queries), and (3) a latency-vs-recall bottleneck in its vector index — propose amortizing compute offline by training small neural networks on the query distribution, rather than tuning generic, query-agnostic index parameters (more clusters, bigger probes, etc.).

Core move: reframe MIPS as learning the support function of the key set (a convex function whose value is the max inner product, and whose gradient is the argmax key). Train small NNs to approximate this function (or its argmax) for the actual query distribution, then use them to either (a) route queries to the right cluster, or (b) rewrite queries before handing them to an existing index.

Progress:

• Step 1: Characterize the setup — fixed key database, expected query distribution, existing index type (IVF/clustered, flat, etc.)
• Step 2: Choose the intervention point — routing (replace centroid-based cluster assignment) vs. query rewriting (sit in front of existing index)
• Step 3: Build a supervised training set via exhaustive ground-truth search over sampled queries
• Step 4: Train the appropriate learned model (SupportNet or KeyNet)
• Step 5: Benchmark recall vs. latency and recall vs. budget (fraction of database scanned), comparing against centroid/baseline routing
• Step 6: Select model size (XS/S/M/L as % of database size) based on the latency budget and acceptable recall

Step 1: Characterize the setup

Identify whether keys and queries come from different distributions (e.g., short questions vs. long documents in RAG) — this is exactly where query-agnostic geometric methods (pure clustering/quantization) underperform, and where learned, distribution-aware methods have the most to gain.

Step 2: Choose intervention point

• Routing (SupportNet): Replaces the "compare query to k centroids" step in an IVF-style index. Use when you control the index internals and want better cluster assignment.
• Query rewriting (KeyNet): Sits upstream of an existing, already-optimized index (no index modification needed). Use when the index is a black box or already highly tuned, and you just want to feed it a smarter query vector.

Step 3: Build training data

For each sampled query (drawn from the real/expected query distribution, not synthetically from the key distribution):

• Run exhaustive ground-truth MIPS once (expensive, but offline/amortized).
• Store (query, optimal score) pairs for SupportNet, or (query, optimal key vector) pairs for KeyNet. This supervised dataset captures the actual solution landscape for queries that matter — not generic worst-case geometry.

Step 4: Train the model

• SupportNet: Use a (loosely constrained) input-convex neural network (ICNN) architecture to exploit the known convexity of the support function. Train it to output k scores at once (one per cluster) via regression (MSE against ground-truth support function values).
• KeyNet: A standard regression network mapping query → best-matching key vector. No convexity constraint is enforced directly; instead, add a consistency loss derived from Euler's theorem for homogeneous functions to keep predictions geometrically grounded in the support function structure.

Step 5: Benchmark

Evaluate two orthogonal axes:

• Recall vs. wall-clock latency (include the NN's own inference cost — don't ignore the overhead of running the model).
• Recall vs. search budget (fraction of database/clusters scanned), which isolates routing/rewriting quality independent of hardware/implementation overhead. Always compare against the naive baseline (centroid routing, or raw-query IVF search) at matched budgets.

Step 6: Pick model size

Sweep model sizes as a percentage of database size (e.g., 1%, 5%, 10%, 20% → XS/S/M/L). Larger models cost more to run but shift the recall-latency curve favorably. Choose the smallest model that hits the target recall within the latency budget — diminishing returns typically appear well before 20%.

Example 1: Input: "Our RAG system uses IVF with 128 clusters and centroid routing; recall is lower than we'd like at low latency budgets." Output: Replace centroid-based routing with a trained SupportNet that outputs k=128 scores jointly (one support-function estimate per cluster). Train on real user queries matched against ground-truth per-cluster support function values (max inner product achievable within each cluster). At inference, route to the top-s clusters by predicted support value instead of centroid distance. Expect disproportionate gains at low scan budgets — e.g., at 5% of the database scanned, learned routing can recover the true best-match partition ~90%+ of the time vs. ~87% for centroid routing, and a small SupportNet can reach 95% routing recall at roughly half the latency of centroid routing.

Example 2: Input: "We have a production approximate search index we can't easily modify, but query latency to reach high recall is still too high." Output: Insert a KeyNet query rewriter in front of the existing index. Train KeyNet via regression on (query, ground-truth best key) pairs sampled from production query logs. At inference, pass the query through KeyNet first, then feed the predicted key vector (not the raw query) into the existing index as the search target — this moves the starting point much closer to the true answer, letting the unmodified index converge to high recall with far less exploration (reported up to ~8x latency reduction to reach 99% recall vs. using the raw query).