sparser-block-attention

name	sparser-block-attention
title	Sparser Block-Sparse Attention via Token Permutation
version	0.0.2
engine	skillxiv-v0.0.2-claude-opus-4.6
license	MIT
url	https://arxiv.org/abs/2510.21270
keywords	["Attention","Efficiency","Token Permutation","Long Context","Sparse"]
description	Accelerates self-attention by reordering tokens to concentrate relevant tokens within fewer blocks. Achieves 2.75x speedup on long-context prefilling by permuting tokens so semantically related information clusters together, enabling aggressive block sparsity without accuracy loss.

Permuted Block-Sparse Attention: Accelerating Long-Context Processing

Standard block-sparse attention underperforms because important key tokens scatter across many blocks. Permuting tokens to cluster semantically related information enables aggressive sparsity while maintaining quality.

PBS-Attn reorganizes sequences before applying block-sparse attention, achieving near-full-attention performance with significant latency reduction for long contexts.

Core Concept

The key insight: important tokens for queries within a block may be scattered, so permuting tokens to concentrate attention targets within fewer blocks reduces computational waste without losing critical information.

The approach:

• Compute token importance/relevance scores
• Reorder tokens so related items cluster together
• Apply standard block-sparse attention to permuted sequence
• Achieve high sparsity (skip 50%+ of blocks) with minimal accuracy loss

Architecture Overview

• Token importance scoring based on attention patterns or embeddings
• Permutation mapping to reorder token sequence
• Custom FlashAttention kernels optimized for permuted sequences
• Inverse permutation to restore original token positions in output

Implementation Steps

Compute token importance to identify which tokens matter most for attention. This can be based on embedding norms, gradient signals, or attention statistics:

def compute_token_importance(tokens, embeddings, method='norm'):
    """Score tokens for importance in attention computation."""
    if method == 'norm':
        # L2 norm of embeddings as importance proxy
        importance = np.linalg.norm(embeddings, axis=-1)
    elif method == 'entropy':
        # Entropy of attention weights (higher = more selective)
        importance = compute_attention_entropy(embeddings)
    else:
        # Default: magnitude of key values
        importance = np.abs(embeddings).mean(axis=-1)

    return importance / importance.()