indexcache-sparse-attention-acceleration

name	indexcache-sparse-attention-acceleration
title	IndexCache: Accelerating Sparse Attention via Cross-Layer Index Reuse
version	0.0.2
engine	skillxiv-v0.0.2-claude-opus-4.6
license	MIT
url	https://arxiv.org/abs/2603.12201
keywords	["Sparse Attention","Acceleration","Long Context","Inference","Indexing"]
description	Accelerate sparse attention by reusing token selection indices across layers. Partition layers into full indexer (F) and shared (S) types using greedy search or multi-layer distillation to eliminate 75% of indexer computation.

Technique: Cross-Layer Index Sharing for Sparse Attention Efficiency

Sparse attention mechanisms use indexers to select the most relevant tokens at each layer, but this indexing computation becomes expensive for long contexts. IndexCache observes that token selections are highly correlated across consecutive layers, enabling index reuse: most layers can skip indexing and reuse indices from a nearby layer, dramatically reducing compute.

The approach combines training-free discovery (greedy search) with optional training-aware optimization (multi-layer distillation) to determine optimal sharing patterns.

Core Concept

IndexCache partitions transformer layers into two types:

1. F (Full) layers: Retain their indexer, computing fresh top-k token selections
2. S (Shared) layers: Skip indexer computation, reusing cached indices from the nearest preceding F layer

By carefully choosing which layers retain indexers using either greedy search or learned patterns, the method eliminates 50-75% of indexer operations while maintaining sparse attention quality.

Architecture Overview

• Indexer computation: Produces top-k token selections per layer
• Index cache: Stores recent indices for sharing across layers
• Layer partition pattern: Binary string determining F vs S layer types
• Training-free search: Greedy algorithm to find good patterns
• Multi-layer distillation: Optional training to adapt to sharing structure

Implementation Steps

Step 1: Analyze Index Correlation Across Layers

Quantify how similar token selections are across consecutive layers.

import torch
import torch.nn as nn

def measure_index_correlation(model, input_ids, sample_size=1000):
    """
    Measure Jaccard similarity of top-k selections across layers.
    """
    batch_size, seq_len = input_ids.shape
    num_layers = model.config.num_hidden_layers
    k = 100  # Assuming top-100 sparse attention

    correlations = []

    with torch.no_grad():
        # Forward pass, collecting indices
        indices_by_layer = []

         layer_idx  (num_layers):
            
            
            layer_indices = extract_topk_indices(
                model,
                input_ids,
                layer_idx,
                k
            )  

            indices_by_layer.append(layer_indices)

        
         layer_idx  (num_layers - ):
            indices_curr = indices_by_layer[layer_idx]  
            indices_next = indices_by_layer[layer_idx + ]

            
            jaccard_scores = []
             b  (batch_size):
                 pos  (seq_len):
                    set_curr = (indices_curr[b, pos].tolist())
                    set_next = (indices_next[b, pos].tolist())

                    intersection = (set_curr & set_next)
                    union = (set_curr | set_next)
                    jaccard = intersection / (union + )
                    jaccard_scores.append(jaccard)

            avg_jaccard = (jaccard_scores) / (jaccard_scores)
            correlations.append(avg_jaccard)

     correlations