# PIVOT: Efficient Query-Group Indexing for Token-Level Sparse Attention

> PIVOT groups nearby queries to share one proxy indexer scan, cutting indexing cost from O(gL) to O(L) and speeding up long-context inference up to 4.8x without accuracy loss.

- **Source:** [arXiv](https://arxiv.org/abs/2607.24593)
- **Published:** 2026-09-19
- **Permalink:** https://picx.dev/p/vg4SWb
- **Whiteboard:** https://picx.dev/p/vg4SWb/image

## Summary

## Summary (Overview)

- **PIVOT** introduces a training-free, drop-in replacement for the DeepSeek Sparse Attention (DSA) indexer that amortizes the expensive per-query full-prefix scan across a group of nearby queries, reducing indexing cost from O(gL) toward O(L) per group.
- The method exploits three empirical observations: (O1) neighboring queries share heavily overlapping top-k token sets, (O2) a group's combined top-k union remains small (1.3–2.4×k even for g=16), and (O3) indexer scores are long-tailed along the key axis.
- Two variants are proposed: **PIVOT-Reuse** (maximum speed, shares proxy top-k across group) and **PIVOT-Refine** (re-scores a candidate set per query, matching dense accuracy).
- On DeepSeek-V3.2 and GLM-5.1 across LongBench and RULER, PIVOT matches dense DSA accuracy while accelerating the indexer by up to **4.8×** and reducing end-to-end latency by up to **1.6×** at long context.
- PIVOT defines a **fourth efficiency axis** (query axis) orthogonal to prior work on token (HISA), head (MISA), and layer (IndexCache) axes, and composes with them.

---

## Introduction and Theoretical Foundation

**Background.** Long-context LLM inference is dominated by the quadratic cost of full attention. DSA (DeepSeek-AI 2025) reduces this by letting each query attend to only the top-k most relevant tokens via a lightweight indexer, reducing main attention cost from O(L²) to O(Lk). However, the indexer itself remains dense: every query must still score the full prefix, yielding O(L²) indexing cost per layer. At 200K tokens, the indexer accounts for ~81% of prefill and ~41% of decode end-to-end latency.

**Key observations (Figure 2).** The paper identifies three properties that motivate group-shared indexing:

- **O1 (Local):** Adjacent queries share 0.8–0.9 of their top-k tokens from shallow to deep layers (L3/L30/L58), and 0.6–0.8 even across a full g=4 group.
- **O2 (Group-shareable):** A group's top-k union stays near 1.3–1.9×k for g≤8, far below the worst-case g·k.
- **O3 (Sparse):** Indexer scores $I_s = \sum_h w_h \text{ReLU}(q_h \cdot k_s)$ concentrate on a small active set, with cumulative mass saturating far below k/2, 3k/4, k.

**Theoretical basis.** The indexer relevance score for query position t and key position s is:

$$I_{t,s} = \sum_{j=1}^{H_I} w_{t,j}^I \text{ReLU}\left(q_{t,j}^I \cdot k_s^I\right) \tag{1}$$

where $q_{t,j}^I$ and $w_{t,j}^I$ are projected from token t, $k_s^I$ from token s, and $H_I$ is the number of indexer heads. The indexer retains the top-k scoring tokens as $T_t = \text{TopK}(I_{t,:}, k)$.

---

## Methodology

### Grouping

**Prefill:** Query positions are partitioned into contiguous groups of fixed size g:
$$G_t^P = \{q_t, q_{t+1}, \ldots, q_{t+g-1}\} \tag{2}$$

**Decode:** PIVOT leverages Multi-Token Prediction (MTP), grouping the current token with its d draft tokens:
$$G_t^D = \{q_t, \tilde{q}_{t+1}, \ldots, \tilde{q}_{t+d}\}, \quad g = d+1 \tag{3}$$

### Shared Proxy Scan

The group is aggregated into a **proxy query** via per-head mean pooling:

$$\bar{q}_j^I = \frac{1}{g}\sum_{t' \in G} q_{t',j}^I, \quad \bar{w}_j^I = \frac{1}{g}\sum_{t' \in G} w_{t',j}^I \tag{4}$$

The proxy scores the full prefix once:

$$\bar{I}_s = \sum_{j=1}^{H_I} \bar{w}_j^I \text{ReLU}\left(\bar{q}_j^I \cdot k_s^I\right), \quad s \leq t \tag{5}$$

### Two Variants

**PIVOT-Reuse:** Skips fine step, assigns proxy top-k to all group members:
$$T_t = \text{TopK}\left(\{\bar{I}_s \mid s \leq t\}, k\right) \quad \text{for all } t \in G \tag{6}$$
Cost: O(L) per group vs. O(gL) for DSA.

**PIVOT-Refine:** Forms a shared candidate set from proxy top-c scores:
$$C = \text{TopK}\left(\{\bar{I}_s \mid s \leq t\}, c\right) \tag{7}$$
with c = 2k (k < c ≪ L). Each query then re-scores only the candidates:

$$I_{t,s} = \sum_{j=1}^{H_I} w_{t,j}^I \text{ReLU}\left(q_{t,j}^I \cdot k_s^I\right), \quad s \in C \tag{8}$$

$$T_t = \text{TopK}\left(\{I_{t,s} \mid s \in C\}, k\right) \tag{9}$$

Cost: O(L + gc) per group, between Reuse and DSA.

---

## Empirical Validation / Results

### Accuracy Results (Table 1)

| Method | LongBench AVG (DeepSeek-V3.2) | RULER AVG (DeepSeek-V3.2) | LongBench AVG (GLM-5.1) | RULER AVG (GLM-5.1) |
|---|---|---|---|---|
| DSA (dense) | 55.95 | 94.30 | 56.79 | 95.19 |
| HISA | 55.85 | 84.49 | 56.51 | 87.77 |
| MISA | 55.43 | 92.59 | 57.14 | 92.26 |
| IndexCache | 56.07 | 94.16 | 56.85 | 95.17 |
| **PIVOT-Reuse** | **56.08** | **93.22** | **56.62** | **94.15** |
| **PIVOT-Refine** | **56.18** | **94.24** | **56.95** | **95.17** |
| **PIVOT-Refine + IC** | **55.96** | **93.69** | **56.92** | **94.90** |

*Key findings:*
- On RULER, HISA degrades sharply at 128K (19–28 points below dense), MISA trails by 6–18 points. PIVOT-Refine tracks dense DSA across all lengths.
- PIVOT-Reuse holds up through moderate lengths but declines at extreme context, while PIVOT-Refine remains on par with dense.
- On LongBench, all sparse methods stay within ~0.5 points of dense; PIVOT is on par or slightly better.

### Efficiency Results (Figure 4)

| Context Length | Prefill Speedup (Reuse) | Prefill Speedup (Refine) | Decode Speedup (Reuse) | End-to-end (Reuse) |
|---|---|---|---|---|
| 4K | 0.55× | 0.93× | 0.93× | 0.97× |
| 8K | 1.70× | 1.40× | 1.40× | 1.01× |
| 16K | 2.19× | 2.05× | 2.05× | 1.07× |
| 32K | 2.86× | 2.85× | 2.85× | 1.21× |
| 64K | 3.87× | 3.16× | 3.16× | 1.45× |
| 128K | **4.28×** | **3.42×** | **3.42×** | **1.61×** |
| 256K | **4.77×** | **3.98×** | — | — |

*Key findings:*
- Indexer kernel speedup grows with context length, reaching up to ~4.8× at 256K.
- End-to-end speedup reaches ~1.6× at long context, where the indexer dominates.
- PIVOT falls back to dense DSA at short context to avoid overhead (guardrail).

### Ablation Studies

**Proxy aggregation (Table 2):** Mean pooling is far more robust than first/last query (at 128K, first-query proxy loses >10 points to mean).

**Group size g (Table 3):** Accuracy decreases as g grows, with loss concentrating at long context. g=4 keeps near-lossless accuracy.

**Candidate budget c (Table 4):** Accuracy saturates quickly in c; c=2k is at the knee of the trade-off.

**Deployment phase (Table 5):** PIVOT is near-lossless in prefill-only, decode-only, or both; a single algorithm serves both phases.

---

## Theoretical and Practical Implications

- **New efficiency axis:** PIVOT defines the **query axis** for accelerating token-level sparse attention, orthogonal to token (HISA), head (MISA), and layer (IndexCache) axes. These axes compose: PIVOT+IndexCache retains near-dense accuracy while stacking speedups.
- **Theoretical cost reduction:** The paper formalizes the shift from O(gL) to O(L) per group (Reuse) or O(L+gc) (Refine), with c ≪ L. This is the first work to amortize the indexer's cost across queries rather than making individual calls cheaper.
- **Practical deployment:** PIVOT is training-free, drop-in (preserves the T_t interface), leaves Sparse MLA and KV cache unchanged, and requires only three hyperparameters (g, c, aggregation). It rides on top of MTP at no additional cost, with speedups compounding.
- **Design principles:** The three observations (O1-O3) provide a theoretical justification: O1 enables sharing, O2 makes it efficient, and O3 preserves accuracy. The long-tailed score distribution ensures that re-scoring a small candidate set recovers nearly the same top-k as a full-prefix search.

---

## Conclusion

PIVOT demonstrates that the DSA indexer's per-query full-prefix scans are largely redundant: nearby queries select heavily overlapping token sets, group unions remain small, and scores are long-tailed. By aggregating a group into a proxy query, running one shared scan, and then optionally re-scoring per query, PIVOT matches dense DSA accuracy while accelerating the indexer by up to 4.8× and end-to-end latency by up to 1.6× at long context. The method is training-free, requires no changes to the downstream Sparse MLA operator or KV cache, and composes with existing accelerations along other axes. Future work includes combining the query axis with token, head, and layer axes, and extending PIVOT to broader model families beyond DeepSeek-V3.2 and GLM-5.1.

---

_Markdown view of https://picx.dev/p/vg4SWb, served by PicX — AI-generated visual whiteboard summaries of research papers._