Sparser Block Attention

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.sum()

Implement token permutation that clusters related tokens. Sort by importance while preserving some local structure to maintain spatial coherence:

def permute_tokens_by_relevance(tokens, embeddings, block_size=64):
    """Permute tokens to cluster relevant ones within blocks."""
    # Compute importance scores
    importance = compute_token_importance(tokens, embeddings)

    # Create permutation: sort by importance, chunked by block
    seq_len = len(tokens)
    permutation = np.argsort(-importance)  # Descending importance

    # Apply permutation to tokens and embeddings
    permuted_tokens = tokens[permutation]
    permuted_embeddings = embeddings[permutation]

    return permuted_tokens, permuted_embeddings, permutation

Apply block-sparse attention to permuted sequence with minimal modification to standard attention code:

def permuted_block_sparse_attention(queries, keys, values,
                                   permutation, block_size=64, sparse_ratio=0.5):
    """Apply block-sparse attention on permuted tokens."""
    seq_len = len(queries)
    num_blocks = (seq_len + block_size - 1) // block_size

    # Determine which blocks to attend to
    # Keep 'dense' blocks where important tokens reside
    num_active_blocks = max(1, int(num_blocks * (1 - sparse_ratio)))

    # Apply FlashAttention kernels with sparse block structure
    # Only compute attention for selected blocks
    output = flash_sparse_attention(
        queries, keys, values,
        num_active_blocks=num_active_blocks,
        block_size=block_size
    )

    # Inverse permutation to restore original order
    inv_perm = np.argsort(permutation)
    output = output[inv_perm]

    return output

Practical Guidance

When to use:

• Long-context inference (4K+ tokens)
• Batch processing where latency matters
• Scenarios with clear token importance gradients

When NOT to use:

• Short sequences (<1K tokens) where full attention is fast
• Tasks needing dense attention patterns (all tokens equally important)
• Inference with streaming (permutation requires full sequence upfront)

Common pitfalls:

• Permutation overhead exceeds attention savings for short sequences
• Sparsity ratio too high, discarding necessary context
• Using static importance scores that don't adapt per query
• Not accounting for inverse permutation cost in end-to-end timing

Reference: Sparser Block-Sparse Attention on arXiv