After studying this material, you should be able to:

1. Explain what Maximum Inner Product Search (MIPS) is and why it matters for RAG systems
2. Describe the limitations of traditional centroid-based MIPS approaches
3. Understand the mathematical insight connecting MIPS to support functions
4. Distinguish between SupportNet and KeyNet architectures and their use cases
5. Apply the concept of amortized MIPS to choose the right tool for a retrieval problem

---

Step-by-Step Teaching

Step 1: The Core Problem — What is MIPS and Why Does It Get Expensive?

What is MIPS?

Imagine you have a library of millions of documents, each converted into a vector of numbers (an embedding). When a user asks a question, that question is also converted into a vector.

MIPS answers: "Which document vector aligns best with my question vector?"

Inner product = a mathematical measure of how well two vectors point in the same direction. Higher = better match.

A Concrete RAG Example

User asks: "What causes thunder?"
         ↓
Convert to query vector: [0.2, 0.8, 0.1, ...]
         ↓
Compare against 2,000,000 document vectors
         ↓
Find the document with the HIGHEST inner product score
         ↓
Prefix that document to the query → send to LLM

Why Does It Get Expensive?

Checking every single document = exhaustive search = slow and expensive at scale.

---

Step 2: The Traditional Fix — Clustering and Its Flaw

How Clustering Speeds Things Up

Instead of comparing the query to all n documents, traditional systems:

1. Group all documents into k clusters
2. Assign each cluster a centroid (the average/representative vector)
3. Compare the query to only k centroids (much cheaper)
4. Route the query to the closest cluster
5. Search exhaustively only within that cluster (~n/k documents)

Without clustering:  compare to n = 2,600,000 documents
With k=128 clusters: compare to 128 centroids + ~20,000 documents
                     → roughly 128× speedup

The Critical Flaw: Centroids Lie

Here is the problem visualized conceptually:

Cluster A centroid: ●  (average position)
                    
Actual documents:   ○ ○ ○ ○ ○ ★ ← outlier, far from centroid
                                    but VERY close to query ✦

Query ✦ is near ★, but centroid ● looks far from ✦
→ System skips Cluster A entirely → WRONG answer

The centroid cannot tell you how good the BEST key inside a cluster is. It only tells you where the average is.

The Additional Problem: Queries ≠ Documents

In RAG specifically:

• Keys (documents): Long, detailed, curated text passages
• Queries: Short, informal user questions

These live in different regions of embedding space. Methods designed assuming queries look like documents will perform poorly.

---

Step 3: The Mathematical Insight — Support Functions

What is a Support Function?

This is the key theoretical breakthrough in the paper.

The function that takes a query vector and returns the highest possible inner product score with any key in the database is called the support function of that set of keys.

Formally:

h(query) = max over all keys { inner_product(query, key) }

This function has two powerful properties:

Why This Matters

Traditional approach:  search through all keys to find the best one
                       (expensive at runtime)

New approach:          train a neural network ONCE to learn h(query)
                       then at runtime: just run the small NN
                       (cheap at runtime)

This is called amortization — pay a one-time training cost upfront, save repeatedly at inference time.

---

Step 4: The Two Neural Network Solutions

How Training Works (Both Networks)

Both networks are trained using regression — a supervised learning approach:

Step 1: Sample many query vectors from the real query distribution
Step 2: For each query, run exhaustive search → find ground truth answer
Step 3: Store (query, answer) pairs as training data
Step 4: Train neural network to predict answer given query
Step 5: Deploy the small NN — no more exhaustive search needed

---

Network 1: SupportNet — The Better Router

What it learns: The support function value for each cluster

What it replaces: Centroid comparison during routing

How it works:

Old routing:
  query → compare to centroid of each cluster → pick closest centroid

New routing with SupportNet:
  query → SupportNet outputs k scores → pick cluster with HIGHEST score
  
  The score now answers: "What is the BEST possible match 
                          inside this cluster for this query?"

Why it's better than centroids:

Centroid asks: "Is the average of this cluster close to my query?"
SupportNet asks: "Is there ANY key in this cluster that matches my query well?"
                  ↑ This is the right question to ask!

Architecture detail: Uses Input Convex Neural Networks (ICNNs) — a special NN architecture that guarantees the output is a convex function of the input, matching the mathematical structure of support functions.

Performance on Natural Questions (2.6M passages, 128 clusters):

Key result: Large SupportNet hits 97% recall at the same latency (1.74 ms) that centroid routing needs just to reach 95% recall.

---

Network 2: KeyNet — The Query Rewriter

What it learns: To predict the best-matching key vector directly

What it replaces: The original query vector

How it works:

Old search pipeline:
  raw question → IVF index → retrieved documents

New search pipeline with KeyNet:
  raw question → KeyNet → predicted key vector → IVF index → retrieved documents
  
  KeyNet transforms: "What is Matchbox Twenty?"
               into: a vector that looks like the answer document

The intuition:

Problem:  Query "What is Matchbox Twenty?" lives in "question space"
          Answer document lives in "answer space"
          These spaces don't perfectly overlap

Solution: KeyNet bridges the gap by predicting WHERE in embedding space
          the answer document likely lives

Architecture detail: Uses a consistency loss derived from Euler's theorem for homogeneous functions — this keeps predictions geometrically grounded even without enforcing convexity explicitly.

Performance on Natural Questions:

Key result: KeyNet L achieves 99% recall ~8× faster than raw query search, and scans ~11× fewer keys to reach the same recall level.

---

Step 5: Choosing Between SupportNet and KeyNet

Think of it as a decision tree:

Do you need a calibrated SCORE (for re-ranking or thresholding)?
├── YES → Use SupportNet
│         (outputs meaningful scores, not just a key vector)
│
└── NO → Is inference speed your primary concern?
         ├── YES → Use KeyNet
         │         (fastest path to the right document)
         │
         └── BOTH matter at massive scale?
                   → Use BOTH
                     SupportNet routes across clusters
                     KeyNet refines search within each cluster

Summary Comparison Table

---

Step 6: The Big Picture — Why This Approach is Novel

The Paradigm Shift

The Amortization Principle

Cost without amortization:
  Every query → expensive exhaustive search
  1,000,000 queries × high cost = very expensive

Cost with amortization:
  One-time training cost (paid once)
  + Every query → cheap NN forward pass
  1,000,000 queries × low cost = much cheaper overall

This is the same principle behind many ML systems: invest once in learning, profit repeatedly at inference.

---

Concept Check — Test Your Understanding

1. Why does centroid routing fail for outlier documents?

   Because the centroid represents the cluster average, not the best possible match. A document far from the centroid but close to the query gets skipped.

2. What two mathematical properties make support functions learnable?

   Convexity (allows ICNN approximation) and the gradient property (gradient = best matching key).

3. What does "amortization" mean in this context?

   Paying a one-time training cost upfront so that each individual query at inference time is much cheaper to answer.

4. When would you use KeyNet over SupportNet?

   When you need maximum inference speed and don't need a calibrated score — KeyNet rewrites the query to look like the answer, then hands off to a standard fast index.

5. Why is the query-key mismatch a special problem in RAG?

   Because queries are short informal questions while keys are long curated documents — they occupy different regions of embedding space, so methods assuming they look similar will perform poorly.