After studying this material, you should be able to:

1. Define static pruning and explain why it matters in sparse retrieval
2. Distinguish between index-side pruning and query pruning
3. Explain why index-side pruning is portable across engines while query pruning is not
4. Identify the three retrieval engines and their architectural differences
5. Apply the "NDCG@10 saturation / Recall@10 knee" as a practical stopping criterion
6. Evaluate when and how to combine static and dynamic pruning

---

Step-by-Step Teaching

Step 1: Foundation — What Is Sparse Retrieval?

Before pruning makes sense, you need to understand what we are pruning.

What is sparse retrieval?

Sparse retrieval is a method of finding relevant documents by representing both queries and documents as sparse vectors — meaning most values are zero, and only a few terms carry non-zero weights.

Query: "best coffee shops"
Sparse representation:
  coffee → 2.3
  shop   → 1.8
  best   → 0.4
  (all other 30,000 vocabulary terms → 0)

Two encoder types matter here

💡 Why this matters: These represent opposite extremes. A finding that holds for both is truly general.

---

Step 2: What Is an Inverted Index?

Sparse retrieval relies on an inverted index — the core data structure.

Term:     "coffee"
Postings: [(doc_3, score=2.1), (doc_7, score=1.4), (doc_15, score=0.9), ...]

Term:     "shop"
Postings: [(doc_1, score=1.9), (doc_3, score=1.7), (doc_22, score=0.5), ...]

To answer a query, the engine:

1. Looks up each query term
2. Retrieves its posting list
3. Accumulates scores across documents
4. Returns top-k results

The performance problem

Real indexes have billions of postings. Traversing them all is slow. This is where pruning comes in.

---

Step 3: What Is Static Pruning?

Static pruning = permanently removing entries from the index before any query arrives.

Think of it like editing a book's index before the library opens — you remove entries you believe will rarely matter.

Two flavors of static pruning

┌─────────────────────────────────────────────────────┐
│              STATIC PRUNING                         │
│                                                     │
│  ┌──────────────────┐    ┌──────────────────────┐  │
│  │  INDEX-SIDE      │    │  QUERY-SIDE          │  │
│  │  PRUNING         │    │  PRUNING             │  │
│  │                  │    │                      │  │
│  │ • Document-level │    │ Remove low-weight    │  │
│  │   (remove whole  │    │ terms from query     │  │
│  │   documents)     │    │ before retrieval     │  │
│  │                  │    │                      │  │
│  │ • Posting-list   │    │ e.g., drop terms     │  │
│  │   (remove low-   │    │ with weight < 0.1    │  │
│  │   score entries) │    │                      │  │
│  └──────────────────┘    └──────────────────────┘  │
└─────────────────────────────────────────────────────┘

---

Step 4: What Is Dynamic Pruning?

Dynamic pruning = skipping entries at query time, based on the query itself.

Unlike static pruning, nothing is permanently deleted. The engine decides on-the-fly what to skip.

The three engines in this study

💡 Key insight: BMP and SEISMIC already handle query-level skipping internally. This becomes critical in Step 6.

---

Step 5: Why Is Sparse Retrieval Memory-Bound?

This is the mechanistic explanation for why index-side pruning works.

The bottleneck is memory, not computation

CPU wants data
     ↓
L1 Cache (fast, tiny) → MISS
     ↓
L2 Cache → MISS
     ↓
L3 Cache → MISS
     ↓
RAM (slow) ← This is where posting lists live

The paper validates this with hardware profiling:

• Cache misses — frequent, confirming memory pressure
• TLB misses — address translation failures from large index footprint
• IPC (Instructions Per Cycle) — low, meaning CPU is waiting for memory

Why does index-side pruning help?

Smaller index → Fits better in cache → Fewer cache misses → Faster retrieval

This is a hardware-level argument, which is why it holds across all three engines regardless of their software architecture.

---

Step 6: What Transfers vs. What Breaks

This is the central finding of the paper.

✅ What TRANSFERS: Index-side pruning

Why it transfers: The memory-bound nature of retrieval is universal. Smaller index = less memory pressure = faster on any engine.

❌ What BREAKS: Query pruning

Exhaustive pipeline:    4–11× speedup  ✓ (very helpful!)
BMP:                    ~0× speedup    ✗ (already handled by β)
SEISMIC:                ~0× speedup    ✗ (already handled by query_cut)

Why it breaks: Modern engines already internalize query-level pruning through their dynamic mechanisms. Adding static query pruning on top is redundant — you're pruning what the engine would have skipped anyway.

💡 Analogy: Imagine pre-sorting a deck of cards before handing it to a machine that automatically sorts cards. Your pre-sorting effort is wasted.

---

Step 7: What Still Helps — Combining Static + Dynamic

Even though query pruning alone doesn't help modern engines, combining index-side static pruning with dynamic pruning does.

BMP example

Baseline (exact):           NDCG@10 = X,    latency = 1.0×
+ Document pruning only:    NDCG@10 ≈ X,    latency = 1.8×
+ Query pruning only:       NDCG@10 ≈ X,    latency = 1.1×  (minimal gain)
+ Both combined:            NDCG@10 within 0.003 of X,  latency = 2.5×

The combination works because:

• Index-side pruning reduces memory pressure (hardware benefit)
• BMP's dynamic pruning handles query-level skipping (software benefit)
• They address different bottlenecks and therefore compound

---

Step 8: The Practical Stopping Criterion

This is the actionable guideline for practitioners.

The NDCG@10 vs. Recall@10 divergence

Pruning aggressiveness →

Recall@10:   100% ──────────────────╲──────── drops sharply
                                     ╲
NDCG@10:     100% ──────────────────────╲──── drops later
                                          ╲
                              ↑
                         "The Knee"
                    Recall ≈ 85–95%
                    NDCG still stable

What this means

The stopping rule

Push pruning until Recall@10 reaches ~85–95%. At this point, NDCG@10 will still be within noise of the unpruned baseline.

Why Recall@10 is the right signal:

• NDCG@10 measures ranking quality of retrieved documents
• Recall@10 measures whether the right documents are retrieved at all
• Recall degrades first → it's the early warning signal
• When Recall is still 85–95%, ranking quality (NDCG) is unaffected

---

Step 9: Synthesis — The Complete Picture

┌─────────────────────────────────────────────────────────────┐
│              DECISION FRAMEWORK FOR PRACTITIONERS           │
│                                                             │
│  What engine are you using?                                 │
│                                                             │
│  ┌─────────────────┐  ┌──────────────┐  ┌───────────────┐  │
│  │   Exhaustive    │  │     BMP      │  │    SEISMIC    │  │
│  │   (no dynamic   │  │  (has β)     │  │ (has query_   │  │
│  │    pruning)     │  │              │  │    cut)       │  │
│  └────────┬────────┘  └──────┬───────┘  └───────┬───────┘  │
│           │                  │                   │          │
│  Use BOTH │         Use INDEX-SIDE only           │          │
│  static   │         (query pruning redundant)     │          │
│  prunings │                  │                   │          │
│           └──────────────────┴───────────────────┘          │
│                              │                              │
│              Stop when Recall@10 ≈ 85–95%                   │
│              (NDCG@10 will still be safe)                   │
└─────────────────────────────────────────────────────────────┘

---

Summary Table

---

Self-Check Questions

1. Why does index-side pruning improve latency even when the retrieval algorithm itself doesn't change?
2. You are using BMP. A colleague suggests adding static query pruning. What would you tell them?
3. Your Recall@10 is 90% and NDCG@10 is unchanged from baseline. Should you prune more aggressively?
4. Why is it important that the study tested both SPLADE and V3-GTE encoders?
5. What hardware metrics confirm that sparse retrieval is memory-bound?