adu2021 Summary
Every Token Counts introduces Hierarchical Sparse Attention (HSA), which enables efficient ultra-long context modeling by partitioning sequences into fixed-length chunks and using learned landmark representations to retrieve top-k most relevant past chunks for each token. This approach satisfies sparsity, random-access flexibility, and length generalization while an 8B-parameter MoE model achieves 90%+ accuracy on 16M-token retrieval tasks.
Core Technique
Chunk-Based Retrieval: Divide input sequence into non-overlapping chunks of fixed length. Create a learnable landmark representation for each chunk capturing its semantic content. For each query position, score all landmarks to select top-k most relevant chunks.
Landmark-Guided Attention: Landmarks are learned dense vectors computed from chunk content (via a small encoder). During inference, compute similarity scores between query and all landmarks in O(n/chunk_size) time, then attend to selected chunks in O(k * chunk_size) time—yielding O(k * chunk_size + n/chunk_size) complexity versus O(n²) for full attention.
Length Generalization: The architecture extrapolates beyond training context lengths because the retrieval mechanism doesn't depend on absolute position—just relative landmark similarity. Attention fuses results using retrieval scores as weights.
Implementation
Landmark computation: For each chunk, compute landmark vector via: landmark_i = encode(mean_pooling(chunk_i_tokens)). Use a learned transformer layer with cross-attention to refine landmarks based on query context.
Top-k retrieval: For query at position q, compute: scores = similarity(query_embedding, all_landmarks), then k_indices = argsort(scores)[-k:]. Retrieve the corresponding chunks.
Attention fusion: Attend to each selected chunk with standard multi-head attention, then fuse results: output = sum(retrieval_score_i * attention(q, chunk_i) for i in k_indices).
When to Use
- Processing documents longer than 100K tokens where full attention is infeasible
- Retrieval-based tasks requiring dynamic context selection
- Long-context understanding of books, code repositories, chat histories
- Applications needing both sparsity and position-independent generalization
When NOT to Use
- Tasks with relatively short context (under 4K tokens where full attention is fast)
- Applications requiring all historical tokens equally in every decision
- Scenarios where landmark computation overhead dominates (very short chunks)
- Tasks sensitive to hierarchical approximation errors in attention patterns
Key References
- Retrieval-augmented attention mechanisms for long contexts
- Landmark-based sparse attention design patterns
- MoE architectures for scaling ultra-long context models