Week 5 — Hierarchical Sparse Indexing

Retrieval · Sparse Attention · Indexing

Advanced

I — Long-context architecture

Overview

Even sparse attention is expensive if every indexer scans a million tokens. An early decoder indexer scores the full visible range, selects high-scoring blocks into a candidate pool, and later Reindex layers score only that pool.

What You Will Learn

• Explain coarse-to-fine candidate discovery.
• Compute the block/pool/Top-K budget.
• Measure recall against exact global top-K.
• Construct an adversarial selection-error case.

Core Concepts

Candidate pool budget

2048\ \text{blocks}\times 8\ \text{positions}\Rightarrow \le 16{,}384\ \text{candidates}\Rightarrow \text{Top-}512

Context-independent deeper indexing

Later indexers only score the candidate pool, so their cost does not grow with context length.

Connection to graph retrieval

Both separate broad candidate discovery from expensive high-resolution reasoning.

Prerequisites

Work these pages on this site before the lecture.

• BM25
• TF-IDF
• Precision / recall at K

Lecture notes

Even top-K attention is expensive if the indexer scores a million positions. Hierarchical indexing is coarse-to-fine: an early Full layer scores blocks, keeps a candidate pool, and later Reindex layers only score that pool. Deeper indexer cost becomes independent of N.

The silent failure mode is selection error: the true token’s block never enters the pool, so later layers cannot recover it. Your adversarial lab must drop the true block on purpose and watch recall collapse. That is the same shape as a GraphRAG candidate-generation miss (week 13).

Required readings

• DeepSeek-V4.1-Flash report — Hierarchical Sparse Indexer
• BM25 and precision/recall at K

Related on this site

• TF-IDF · Week 13 — knowledge graphs

Lab / Implementation

Implement hierarchical top-K and measure recall vs exact global top-K as block/pool/Top-K vary; inject a case where the coarse stage drops the true block.

Not on this site (paper reading required)

• Hierarchical Sparse Indexer
• block scoring
• the candidate-pool contract

Mastery Check

• DERIVE: the coarse-to-fine budget and why deeper cost is context-independent
• IMPLEMENT: hierarchical top-K + exact reference
• BENCHMARK: recall vs block/pool; selection-error rate
• DEBUG: the adversarial dropped-block case
• EXPLAIN: where recall silently degrades in production

Part of CS/AI 684 — Efficient Long-Context Agent Systems.