Sparse Attention

Standard self-attention computes pairwise interactions between all tokens, requiring memory that scales quadratically with sequence length. Sparse attention reduces this to O(n log n) or O(n) by enforcing a fixed sparsity pattern. For a 100,000-base-pair genomic locus, this transforms an infeasible 40GB memory requirement into a manageable 2-4GB footprint, enabling single-GPU processing of full-length regulatory regions.

Sparse attention architectures combine multiple attention patterns to balance efficiency with expressivity:

• Sliding window: Each token attends to a fixed neighborhood of adjacent tokens, capturing local regulatory motifs like transcription factor binding sites
• Global tokens: A small set of task-specific tokens attend to all positions, aggregating long-range signals from distant enhancers
• Random patterns: A subset of random connections ensures information can propagate between any two positions in O(log n) layers This hybrid design preserves the ability to model both proximal promoter elements and distal enhancer-promoter looping interactions.

BigBird extends the BERT architecture with a theoretically grounded sparse attention mechanism proven to be a universal approximator of full attention. It combines:

• Block sparse attention: Tokens are grouped into blocks, and attention is computed only between selected blocks
• Random attention: Each token attends to a random subset of other tokens
• Global attention: Designated tokens attend to the entire sequence BigBird processes sequences up to 8x longer than dense attention models with equivalent compute, making it suitable for full-gene and multi-gene genomic contexts.

Longformer introduces a dilated sliding window attention pattern that exponentially increases the receptive field without additional computation. By inserting gaps between attended tokens in higher layers, the model achieves an effective receptive field of thousands of tokens while maintaining linear complexity. For genomic applications, this allows lower layers to capture local k-mer patterns while upper layers integrate signals across entire topologically associating domains (TADs) —structural units of 3D genome organization spanning hundreds of kilobases.

Sparse attention aligns naturally with the modular architecture of the genome. Regulatory elements like enhancers primarily interact with promoters within the same TAD, creating a locality bias that sliding window attention exploits efficiently. By restricting cross-attention to biologically plausible ranges, sparse mechanisms act as an architectural inductive prior that reflects the physical constraints of chromatin looping, potentially improving generalization by preventing the model from learning spurious long-range correlations that violate known biology.

Hyena replaces explicit attention entirely with an implicit long convolution operator parameterized by a small neural network. This sub-quadratic alternative achieves quality comparable to sparse attention while scaling to 1 million tokens—sufficient for entire bacterial genomes or human chromosomal arms. HyenaDNA, a genomic adaptation, processes sequences 160x longer than standard transformers by learning the convolution kernel dynamically from the input, effectively discovering the optimal sparsity pattern rather than imposing a fixed design.

Divides the input sequence into fixed-size blocks and computes attention only within a predefined sparsity pattern, such as a block-diagonal or block-strided mask. This approach maps efficiently to GPU tensor cores because the computation remains dense within each block. In genomic models, blocks can be aligned with biologically meaningful units like exons or conserved non-coding elements, ensuring that attention is concentrated where regulatory interactions are most likely.