llms.blog
AI

Sparse Attention and BigBird: How Window, Global, and Random Graphs Preserve Turing Completeness in Linear Time

Standard self-attention in transformer architectures scales quadratically with sequence length. Computing full pairwise interactions between n tokens requires evaluating an n x n attention matrix, yielding O(n^2) computational complexity and memory consumption. While hardware accelerators and IO-aware tiling algorithms like FlashAttention optimize memory traffic, the quadratic compute and KV footprint remains a barrier for processing long contexts, document-level summarization, and genomic seque

axc
axc
7 min
Sparse Attention and BigBird: How Window, Global, and Random Graphs Preserve Turing Completeness in Linear Time

Standard self-attention in transformer architectures scales quadratically with sequence length. Computing full pairwise interactions between n tokens requires evaluating an n x n attention matrix, yielding O(n^2) computational complexity and memory consumption. While hardware accelerators and IO-aware tiling algorithms like FlashAttention optimize memory traffic, the quadratic compute and KV footprint remains a barrier for processing long contexts, document-level summarization, and genomic sequence modeling.

To break this quadratic scaling while preserving the expressive power of transformers, sparse attention mechanisms replace the dense attention matrix with structured sparse graphs. Introduced by Zaheer et al. (2020), BigBird demonstrated that a sparse attention pattern combining sliding window attention, random connections, and global memory tokens reduces attention complexity to strictly linear O(n) time while maintaining universal approximation and Turing completeness.

Attention as a Directed Graph

To analyze sparse attention theoretically, the attention mechanism is formulated as a directed graph G = (V, E), where the vertex set V = {1, 2, ..., n} represents the sequence of n tokens, and a directed edge (i, j) in E denotes that token i attends to token j.

In standard dense self-attention, G is the complete directed graph K_n, where every token attends to every other token (|E| = n^2). The attention output for token i with queries Q, keys K, and values V in R^{n x d} is defined as:

Attn(Q_i, K, V) = sum_{j in N(i)} [ exp(Q_i K_j^T / sqrt(d_k)) / sum_{l in N(i)} exp(Q_i K_l^T / sqrt(d_k)) ] V_j

where N(i) = {j : (i, j) in E} is the incoming neighborhood of node i.

BigBird Block Sparse Attention Matrix Topology

In sparse attention, the edge set E is restricted such that |E| is much smaller than n^2. The central theoretical challenge is constructing a sparse graph topology that drastically reduces |E| to O(n) while maintaining sufficient information flow across the sequence to avoid representational collapse.

The BigBird Tripartite Graph Topology

BigBird addresses this by constructing an attention graph from three complementary edge sets: E = E_w union E_r union E_g.

1. Sliding Window Attention (E_w)

Natural language and structured sequence data exhibit strong locality of reference; adjacent tokens typically share high mutual information and syntactic dependencies. BigBird defines a local sliding window of half-width w:

E_w = {(i, j) : |i - j| <= w}

This forms a band matrix around the diagonal. Each token attends to its 2w nearest neighbors, capturing short-range lexical structure, phrases, and morphological dependencies.

2. Random Attention (E_r)

Local window attention alone suffers from slow information propagation: passing information between tokens at opposite ends of sequence length n requires O(n / w) transformer layers.

To accelerate communication without introducing dense connections, BigBird incorporates random edges. For each token i, a set R_i of r random tokens is sampled uniformly from the sequence:

E_r = {(i, j) : j in R_i, |R_i| = r}

This construction leverages the mathematical properties of Erdős-Rényi random graphs G(n, p). Random graphs possess high expansion properties and a non-zero spectral gap in their graph Laplacian. As a result, adding just r random edges per node shrinks the average shortest path and graph diameter from O(n) down to O(log n). Information mixes across the sequence in logarithmic depth rather than linear depth.

3. Global Memory Tokens (E_g)

Certain tasks require aggregating sequence-wide representations (such as classification, sentiment analysis, or global document question answering). BigBird introduces a set G of g global tokens:

E_g = {(i, j) : i in G or j in G}

Global tokens attend to all n tokens in the sequence, and all n tokens attend to every global token. This establishes a star graph topology over the sequence.

BigBird supports two configurations for global tokens:

  • Internal Global Tokens: Pre-existing sequence tokens (such as [CLS] or designated prompt indices) are upgraded to full bidirectional global connectivity.
  • Extended Global Tokens: Additional auxiliary tokens are prepended to the sequence strictly to serve as global memory registers, preventing perturbation of sequence positions.

With global tokens, information between any two arbitrary tokens i and j can be routed in exactly 2 hops (i to global to j), reducing effective communication latency across the graph to O(1).

Total Complexity

Summing the three components, each token attends to at most 2w + r + g tokens. The total edge count in the attention graph is:

|E| = n * (2w + r + g)

Since w, r, and g are fixed hyperparameters independent of sequence length n (for example, w=3, r=3, g=2), the total memory and computation scale strictly as O(n), enabling sequence lengths of 4,096 to 16,384 tokens on hardware constrained to 512 tokens under dense attention.

Theoretical Guarantees: Universal Approximation and Turing Completeness

Many heuristic sparse attention patterns compromise the theoretical expressive power of the underlying transformer. Zaheer et al. proved that the BigBird graph preserves the core theoretical properties of full transformers.

Universal Approximation of Continuous Sequence Functions

Let F denote the class of continuous sequence-to-sequence functions f: R^{n x d} -> R^{n x d} defined on a compact domain. Yun et al. (2019) previously proved that standard dense transformers are universal approximators in L_p norm for 1 <= p < infinity.

Zaheer et al. extended this result to sparse graphs, establishing that a transformer whose attention graph G contains:

  1. Star graph subgraphs (provided by global tokens E_g), and
  2. A connected graph over all sequence positions (provided by E_w and E_r),

can approximate any continuous sequence function to arbitrary precision epsilon > 0. The proof demonstrates that global tokens act as intermediate communication hubs that can simulate full pairwise matrix evaluations through function composition across stacked transformer layers.

Turing Completeness

Pérez et al. (2019) established that full transformers with positional encodings and rational activation functions are Turing complete, capable of simulating any Turing machine in bounded tape configurations.

Because the BigBird topology retains full token accessibility through global memory routing and logarithmic-diameter random graphs, it can simulate arbitrary state transitions, tape head movements, and conditional memory read/write cycles. Consequently, BigBird maintains the Turing completeness of dense transformers.

Block-Sparse Implementation on Hardware Accelerators

A key challenge in deploying sparse graph neural networks on modern GPUs and TPUs is memory access alignment. Unstructured, fine-grained point-wise random attention produces irregular memory access patterns, causing memory divergence, poor cache line utilization, and low arithmetic intensity on tensor cores.

To achieve high hardware efficiency, BigBird implements Block Sparse Attention:

  1. The sequence of n tokens is partitioned into contiguous blocks of size B (typically B = 64).
  2. Window, random, and global operations are executed at the block level rather than the token level:
  • Window Blocks: Each block attends to its w adjacent left and right blocks.
  • Random Blocks: Each block attends to r randomly sampled blocks.
  • Global Blocks: g dedicated blocks attend to and receive attention from all blocks.
  1. Attention computations are structured as dense batched matrix multiplications (GEMMs) of shape (B x d) x (d x B) -> (B x B).

By executing dense tensor contractions over contiguous B x B tiles, the block-sparse kernel maximizes Tensor Core utilization and saturates High Bandwidth Memory (HBM) bandwidth.

# Conceptual PyTorch block-sparse attention layout
import torch

def compute_block_sparse_attention(
    q_blocks: torch.Tensor,     # [num_blocks, B, head_dim]
    k_blocks: torch.Tensor,     # [num_blocks, B, head_dim]
    v_blocks: torch.Tensor,     # [num_blocks, B, head_dim]
    block_indices: torch.Tensor # [num_blocks, total_attended_blocks]
) -> torch.Tensor:
    num_blocks, B, d = q_blocks.shape
    scale = 1.0 / (d ** 0.5)
    
    # Gather key and value blocks according to sparse graph topology
    # k_gathered: [num_blocks, total_attended_blocks * B, d]
    k_gathered = k_blocks[block_indices].view(num_blocks, -1, d)
    v_gathered = v_blocks[block_indices].view(num_blocks, -1, d)
    
    # Dense block GEMM: [num_blocks, B, total_attended_blocks * B]
    scores = torch.bmm(q_blocks, k_gathered.transpose(1, 2)) * scale
    attn_weights = torch.softmax(scores, dim=-1)
    
    # Context projection: [num_blocks, B, d]
    out = torch.bmm(attn_weights, v_gathered)
    return out

Comparison Across Sparse Attention Approaches

BigBird is part of a broader spectrum of sparse attention mechanisms developed to mitigate quadratic complexity:

  • Full Attention (Vaswani et al., 2017): Complete bipartite graph K_n with O(n^2) complexity. Uses standard dense GEMMs but is memory-bound at long contexts.
  • Sparse Transformer (Child et al., 2019): Strided and fixed factorization patterns with O(n sqrt(n)) complexity. Relies on customized 2D strided slice kernels.
  • Longformer (Beltagy et al., 2020): Sliding window, dilated window, and task-specific global tokens with O(n) complexity. Requires custom CUDA kernels built via TVM or CUTLASS.
  • Reformer (Kitaev et al., 2020): Locality-Sensitive Hashing (LSH) angular clustering with O(n log n) complexity. Incurs dynamic bucket sorting and padding overhead.
  • BigBird (Zaheer et al., 2020): Sliding window, Erdős-Rényi random connections, and global star tokens with O(n) complexity. Executes via block-sparse batched GEMM tiles.

While Longformer relies on deterministic dilated strides to expand its receptive field, BigBird's incorporation of random expander graphs provides stronger theoretical guarantees regarding graph diameter and spectral expansion, preventing blind spots in unstructured document retrieval.

The Role of Sparse Attention in Modern LLM Systems

In contemporary foundation models, dense attention accelerated by IO-aware exact kernels (such as FlashAttention-2 and FlashAttention-3) remains standard for pre-training up to 32k or 128k sequence lengths. However, the theoretical and architectural principles established by BigBird and block-sparse attention remain vital in several specialized domains:

  1. Document-Level Encoders and Summarization: In encoder-decoder architectures (such as BigBird-Pegasus), linear attention enables direct processing of whole books, legal filings, and financial reports without recursive chunking.
  2. Biological and Genomic Sequence Modeling: In DNA/RNA foundation models (such as Enformer and HyenaDNA), sequences often span hundreds of thousands of base pairs where quadratic attention is physically infeasible.
  3. Dynamic KV Cache Eviction and Sparse Prefill: Modern inference optimization runtimes increasingly employ sparse attention graphs (such as Quest, SparQ, and SnapKV) to dynamically select a sparse subset of KV cache blocks during the decode and prefill phases, directly drawing on block-sparse routing principles.

By demonstrating that linear sparse graphs can retain the universal representation power of dense transformers, BigBird established the theoretical blueprint for scalable sequence modeling across deep learning.

Sources

AILLMArchitectureExplainer
ShareX (Twitter)LinkedIn

Written by

axc

More to read

  • Hybrid SSM-Transformer Architectures: How Interleaving Attention and Recurrence Solves the State-Retrieval Trade-Off

    Hybrid SSM-Transformer Architectures: How Interleaving Attention and Recurrence Solves the State-Retrieval Trade-Off Autoregressive language models face a fundamental tension between inference efficiency and long-context retrieval capacity. Pure Transformer architectures scale quadratic computational complexity during sequence prefill and linear key-value (KV) cache memory consumption during autoregressive token generation. Conversely, pure State Space Models (SSMs) and linear recurrent neural

    1 min

  • Study: Why Labor-Saving LLMs Incline Scientists to Do More Work Less Well

    A theoretical study published by researchers from Princeton University, the University of Washington, and collaborating institutions models how large language models alter researchers' time allocation across projects. The authors find that by reducing time friction across different stages of the research lifecycle, AI assistants increase the opportunity cost of researcher time, creating economic incentives to publish a higher volume of less thoroughly refined papers. The paper, titled The unint

    1 min

  • Memory Shortage Drives Nvidia AI Server Prices Up Over 15%

    Nvidia has notified major customers that prices for server systems containing its artificial intelligence accelerators are increasing by more than 15% in many configurations, according to reports from Bloomberg and Fortune. The price adjustments stem from severe supply constraints and rising costs across dynamic random-access memory (DRAM) and high-bandwidth memory (HBM) modules. The price increases will apply to server systems scheduled for delivery starting in early 2027, covering platforms p

    1 min