A sports-analytics startup in Bengaluru is building a model that reads full IPL commentary transcripts — every ball, every over, every wicket — and writes a natural-language season summary. A single T20 match produces roughly 260 balls across two innings; commentary text for one match runs to about 2,500 tokens. String together a full 74-match season and the transcript is close to 180,000 tokens. Feed that into a transformer with ordinary self-attention and every one of those 180,000 tokens computes a similarity score against every other token: 180,000² is 32.4 billion query-key pairs, for one layer, one attention head, one match summary job. No GPU in the building holds that attention matrix in memory, and no training budget covers the FLOPs. The fix is not a bigger GPU. It is asking a sharper question: does token 4,000 — a single ball bowled in the 3rd over of match 12 — actually need to compute a similarity score against token 179,999, a boundary hit in the last over of match 74? Almost certainly not, directly. But the over-27 collapse in match 40 probably does need to "see" the powerplay context from over 1 of that same match, and the final summary token needs some way to reach the match state from every game in the tournament. Sparse attention is the design discipline of deciding, deliberately, which pairs of tokens get to talk to each other directly — and it turns out you can throw away the overwhelming majority of those n² pairs and still let information travel exactly as far as it needs to.
Attention as a graph, not a matrix
The most useful way to think about sparse attention is to stop picturing an n×n score matrix and start picturing a directed graph. Put one node per token. Draw an edge from token i to token j if i is allowed to attend to j — meaning j's value vector can flow into i's updated representation at that layer. Full self-attention is the complete graph: every node connects to every other node, so the graph has diameter 1. Any token's representation can depend on any other token's content after a single layer.
Once you view it this way, stacking transformer layers is exactly graph message-passing: each layer lets information travel one hop further along the attention graph, the same way each layer of a graph neural network lets a node aggregate information from one more hop of its neighbourhood. A model with L layers can only mix information between two tokens whose graph distance is at most L. This reframing is the entire idea behind sparse attention: instead of asking "how do I approximate the n² score matrix," ask "what is the sparsest graph, with the fewest edges per node, whose diameter is still small enough that L layers give every pair of tokens a path?" Every sparse-attention scheme in production is an answer to that question, and they differ in which edges they keep.
Fixed local + strided patterns: Sparse Transformers (Child, Gray, Radford & Sutskever, 2019)
The earliest systematic answer, from OpenAI's "Generating Long Sequences with Sparse Transformers" (2019), splits the attention heads in a layer into two fixed, hand-designed patterns rather than one dense one. A local head lets token i attend only to a contiguous window of nearby tokens — the previous few hundred positions. A strided head lets token i attend only to tokens at fixed stride intervals — every s-th position going back through the whole sequence. The intuition, borrowed from how a 2D image's pixels factor into rows and columns, is to treat the 1D token sequence as if it were reshaped into an s × (n/s) grid: local attention covers movement within a "row," strided attention covers movement across "rows." A token combining one local layer and one strided layer can reach any other token in the sequence within two hops, because any position is at most one row-hop and one column-hop away in that grid decomposition — the same trick as factorizing a large multiplication into two smaller ones.
Choosing the stride s ≈ √n balances the two costs, since local attention costs O(n·s) and strided attention costs O(n·(n/s)) — setting them equal by picking s = √n gives O(n·√n) total, down from O(n²). For the 180,000-token season transcript, √180000 ≈ 424; rounding to s = 512 for clean tiling, local-plus-strided attention costs n·s + n·(n/s) = (180000 × 512) + (180000 × 180000/512) = 92,160,000 + 63,281,250 = 155,441,250 ≈ 155.4 million pairs, against 32.4 billion for full attention — a reduction of about 208×. The tradeoff is that the pattern is fixed at model-design time: it has no notion of which tokens are semantically important, only which are nearby or evenly spaced.
Sliding window + task-chosen global tokens: Longformer (Beltagy, Peters & Cohan, 2020)
Longformer keeps the local sliding-window idea but replaces the rigid stride pattern with a small, task-chosen set of global tokens that attend to — and are attended to by — every other token, in addition to the window. Crucially, which tokens are global is a modelling choice tied to the task: a classification model makes the [CLS] token global; a question-answering model makes every token of the question global, so the answer span anywhere in a long passage can be reached in one hop from the question. For the cricket transcript, the natural global tokens are the periodic "match state" summaries — score, wickets, overs remaining — re-inserted every few balls, since a token describing a batting collapse needs a short path to the state of the game, not to the literal text of an unrelated ball fifteen overs earlier.
Work through the actual numbers for a realistic single-match-plus-context window: n = 8,192 tokens, a local window w = 512 (each token attends to roughly 256 neighbours on either side), and g = 64 global tokens.
Full attention: n² = 8192² = 67,108,864 attended pairs
Local window: n·w = 8192 × 512 = 4,194,304 pairs
Global (both ways): 2·g·n = 2 × 64 × 8192 = 1,048,576 pairs
Sparse total: 4,194,304 + 1,048,576 = 5,242,880 pairs
Reduction factor = 67,108,864 / 5,242,880 = 12.8×
(The two counts overlap slightly — a token inside the window of a global token is counted in both terms — but that overlap is at most g² = 4,096 pairs, under 0.08% of the sparse total, small enough to ignore for this estimate.) The memory consequence is just as concrete. Storing one attention matrix in fp16 (2 bytes per entry): full attention needs 67,108,864 × 2 bytes = 134,217,728 bytes = 128 MiB, per head, per layer, per sequence in the batch. Sparse attention needs 5,242,880 × 2 bytes = 10,485,760 bytes = exactly 10 MiB. Multiply either number by, say, 16 attention heads and 24 layers, and the difference between "128 MiB × 16 × 24 ≈ 48 GiB" and "10 MiB × 16 × 24 ≈ 3.75 GiB" of activations is the difference between fitting a long-context batch on a single 40 GB GPU and needing to shard it across several.
The attention graphs, side by side
The diagram below shows which (query i, key j) pairs actually receive a computed attention score — the same four patterns just discussed — for a small 10-token sequence, so every colored cell is a real edge, not an illustration.
Why a handful of global tokens rescues expressivity: the graph-diameter argument (BigBird)
Sliding-window attention alone has a real weakness the diagram above already shows: the "Sliding window" panel's colored band never reaches the corners of the grid. If token 0 needs to influence token 9's representation and the window radius is 1, information has to hop through tokens 1, 2, 3... one position at a time — it takes as many layers as the distance between them. For a 180,000-token season transcript with a window radius of 256, two tokens at opposite ends of the sequence need roughly 180,000 / 256 ≈ 703 layers before either can affect the other's representation. No production transformer has 703 layers. This is the real problem Zaheer, Guruganesh, Dubey, Ainslie, Alberti, Ontanon, Pham, Ravula, Wang, Yang and Ahmed's BigBird paper (NeurIPS 2020) solves, and it solves it with a graph-theory result, not a bigger window: adding just r random edges per node — a fixed, small constant, independent of n — turns the attention graph into something close to a random (Erdős–Rényi-style) graph, and random graphs have small-world behaviour: their diameter grows only as O(log n), not O(n). A global token does even better — since it connects directly to and from every node, it collapses any two-token path to length 2, a star graph's diameter, regardless of how large n gets. BigBird's actual design combines all three: local window (nearby context, cheap to compute), a few global tokens (a worst-case 2-hop guarantee for any pair), and a few random edges per token (redundancy so that expressivity doesn't rest entirely on which tokens happen to be marked global). The paper's core theoretical contribution is proving this exact combination is a universal approximator of sequence-to-sequence functions and is Turing-complete — matching full attention's expressive power while touching only O(n) query-key pairs instead of O(n²).
This claim is checkable, not just quotable. Build a tiny 16-token sequence, give every token a window radius of 1 (attend to itself, one neighbour left, one right), and designate token 0 as a global token that attends to, and is attended by, every other token. Represent the attention pattern as a boolean adjacency matrix A, where A[i, j] = True means token i attends to token j — meaning j's value can flow into i's next-layer representation. Simulating one more transformer layer is exactly one more hop of boolean message-passing: a token becomes "reached" by information starting at some source token once it attends to a token that is already reached.
import numpy as np
n = 16 # sequence length (tokens)
window = 1 # local radius: each token attends to itself, 1 left, 1 right
global_idx = 0 # token 0 is the designated global token
# Build the boolean adjacency (attention) matrix:
# A[i, j] = True means token i attends to token j (j's value flows into i)
A = np.zeros((n, n), dtype=bool)
for i in range(n):
for j in range(max(0, i - window), min(n, i + window + 1)):
A[i, j] = True # local sliding window
A[i, global_idx] = True # every token attends to the global token
A[global_idx, i] = True # the global token attends to every token
np.fill_diagonal(A, True)
def hops_to_connect(A, src, dst, max_hops=20):
"""Smallest number of transformer layers before dst's representation
can depend on src's original content."""
n = A.shape[0]
reach = np.zeros(n, dtype=bool)
reach[src] = True
for h in range(1, max_hops + 1):
# a token i becomes newly reached if it attends to some already-reached token
reach = reach | (A.astype(np.int64) @ reach.astype(np.int64) > 0)
if reach[dst]:
return h
return None
# Local-only baseline: built directly from the window rule, not by
# stripping the global token's edges out of A (that would also erase
# the legitimate local-window edge between token 0 and its neighbours).
A_local_only = np.zeros((n, n), dtype=bool)
for i in range(n):
for j in range(max(0, i - window), min(n, i + window + 1)):
A_local_only[i, j] = True
print("local window only: ", hops_to_connect(A_local_only, src=15, dst=1))
print("window + global: ", hops_to_connect(A, src=15, dst=1))
Trace it by hand to confirm the code before trusting the output. With the local-only matrix (radius 1, no global token), "reached" starts as just {15}. Each hop, a token i joins the reached set if A[i, j] is true for some already-reached j — with radius 1 this can only extend the reached interval by one position per hop. Starting from {15} it takes exactly 14 hops for the reached set to grow down to include index 1, since |15 − 1| = 14 and each hop advances the boundary by exactly one position. So hops_to_connect(A_local_only, 15, 1) returns 14.
Now add the global token. After hop 1, the reached set from source 15 is {14, 15, 0} — 14 and 15 from the local window, and 0 because token 0 attends to token 15 directly (global tokens attend to everyone, so A[0, 15] is True). After hop 2, every token joins the reached set: since token 0 is now reached and every single token attends to token 0 (A[i, 0] = True for all i, by construction), the reach update pulls in all 16 tokens at once. Token 1 is reached at hop 2. Fifteen tokens' worth of local-window distance collapsed from 14 hops to 2, by adding one node with full connectivity — exactly the star-graph diameter argument BigBird formalizes at scale.
The misconception to correct
The natural — and wrong — assumption is that sparse attention means a token permanently cannot see information outside its local window: "if token 4,000 only attends to its 256 neighbours, then whatever happened in over 1 of match 1 is simply invisible to it, forever." That is false on two counts. First, even pure local-window attention with no global or random edges still propagates information arbitrarily far — just slowly, through repeated hops across layers, the same way a stack of 3×3 convolutions builds a large receptive field in a CNN without any single layer seeing the whole image. Token 4,000 can be influenced by token 1 after enough layers; the window only bounds how far one layer reaches, not how far the network as a whole reaches. Second, and this is precisely the point of adding global or random edges, network depth is expensive and fixed at design time (a 24-layer model is not going to grow 700 layers to fit a long context), so relying on pure local propagation to cover long distances is impractical, not impossible. Global tokens and random edges exist to make the diameter small enough that the fixed, practical depth you already have is sufficient — not to create a connectivity path that pure local attention structurally lacks.
Active recall
Attempt each question before reading its answer.
- A document-QA model uses Longformer-style attention with n = 4,096 tokens, window w = 256, and g = 8 global tokens (all placed on the question). Compute the sparse attention pair count and the reduction factor versus full attention.
- Now scale the same setup to a full-book context: n = 32,768, keeping w = 512 and g = 64 fixed (note: w changed from question 1's setup to match the chapter's main worked example). Compute (a) the new sparse pair count, (b) the new full-attention pair count and reduction factor, (c) the new per-head fp16 memory footprint for both full and sparse attention, and (d) the number of hops needed to connect the two farthest tokens using local-window-only attention (radius = w/2), compared with the earlier n = 8,192 case. A student might also assume g must grow with n to "keep up" — does the diameter argument support that assumption?
- BigBird adds r random edges per token instead of (or alongside) a global token. Using the small-world approximation diameter ≈ log₂(n) / log₂(r), estimate the diameter for n = 32,768 with r = 3. How does this compare to the 2-hop guarantee a single global token provides, and why might a real system still want both?
- Find the bug: a teammate writes
reach = reach | (reach.astype(np.int64) @ A.astype(np.int64) > 0)instead ofA.astype(np.int64) @ reach.astype(np.int64) > 0insidehops_to_connect. Explain what this computes instead, and why it gives the wrong answer for a directed (non-symmetric) attention graph. - For the cricket-commentary model, which tokens should be marked global, and why would making every ball-by-ball token global defeat the purpose of using sparse attention at all?
- A Sparse Transformer-style model factorizes n = 65,536 tokens with local attention (window w) and strided attention (stride s), choosing s so the two costs are equal. Derive s in terms of n, then compute the total attended-pair count and the reduction factor versus full attention.
Answer 1. Local: n·w = 4,096 × 256 = 1,048,576. Global: 2·g·n = 2 × 8 × 4,096 = 65,536. Sparse total = 1,048,576 + 65,536 = 1,114,112. Full: n² = 4,096² = 16,777,216. Reduction factor = 16,777,216 / 1,114,112 ≈ 15.06×.
Answer 2. (a) Local: n·w = 32,768 × 512 = 16,777,216. Global: 2·g·n = 2 × 64 × 32,768 = 4,194,304. Sparse total = 16,777,216 + 4,194,304 = 20,971,520. (b) Full: n² = 32,768² = 1,073,741,824. Reduction factor = 1,073,741,824 / 20,971,520 = 51.2×. (c) Full memory: 1,073,741,824 × 2 bytes = 2,147,483,648 bytes = 2,048 MiB (2 GiB) per head. Sparse memory: 20,971,520 × 2 bytes = 41,943,040 bytes = 40 MiB per head. Cross-check: 2,048 / 40 = 51.2, matching the pair-count reduction factor exactly, as it must since both scale by the same 2-bytes-per-pair constant. (d) Radius = w/2 = 256; farthest distance = n − 1 = 32,767; hops ≈ 32,767 / 256 ≈ 128. At n = 8,192 (this chapter's main example) the equivalent figure is 8,191 / 256 ≈ 32 hops. Quadrupling n quadrupled the local-only hop count (32 → 128), because pure local-window reach grows linearly with n. On the "does g need to grow with n" question: no — this is the trap. The diameter argument shows a global token gives a 2-hop guarantee regardless of n, because every token connects directly to it; g staying fixed at 64 does not weaken that guarantee. What does shrink, holding g = 64 fixed, is the global-token share of the sequence: 64/8,192 ≈ 0.78% at the chapter's original n = 8,192, versus 64/32,768 ≈ 0.20% here — a real fourfold drop. It looks like it should matter, but the diameter bound never depended on that fraction; it depended only on every token having a direct edge to some global token, which g = 64 still guarantees at any n. The instinct to scale g with n conflates "more edges per node" with "shorter diameter" — but a star graph's diameter is 2 whether it has 100 leaves or 100 million.
Answer 3. log₂(32,768) = 15 (since 2¹⁵ = 32,768). log₂(3) ≈ 1.585. Estimated diameter ≈ 15 / 1.585 ≈ 9.46, so roughly 9–10 hops. That is far worse than the global token's flat 2-hop guarantee, but still enormously better than pure local attention's ~128 hops at this n, and it requires no single token to be structurally special — useful when a task has no obvious global anchor (unlike QA's question tokens). This is why BigBird keeps both mechanisms rather than picking one: global tokens give a tight worst-case guarantee when a natural anchor exists, random edges give a weaker but anchor-free guarantee as a backstop.
Answer 4. reach @ A (reach as a row vector, or equivalently Aᵀ @ reach) computes, for each token j, whether some already-reached token i attends to j — i.e., it asks "who did the reached tokens look at," which is the wrong direction. The chapter's definition is that a token becomes reached when it attends to an already-reached token (information flows from the attended-to token into the attending token's representation). The buggy line instead propagates along the direction "reached tokens' outgoing attention," which happens to look identical on a symmetric graph (where A[i,j] = A[j,i] for every pair, as it is for this chapter's local-window-plus-global example) but gives the wrong reachability set the moment the attention graph is directional — for instance, a causal (autoregressive) mask, where token i can only attend to j ≤ i, making A asymmetric.
Answer 5. The periodic match-state tokens (score, wickets, overs, required run rate) inserted at fixed intervals through the commentary — the tokens any downstream summary token needs a short path to, regardless of which match or over it's describing. Marking every ball-by-ball token global would set g = n, making every token attend to every other token — that is exactly full O(n²) attention again, just relabelled; the entire point of choosing a small g is that most tokens do not need a direct connection to most other tokens, only a short path through a few well-chosen hubs.
Answer 6. Setting local cost n·w equal to strided cost n·(n/s) gives w = n/s; picking the balanced factorization s = √n makes both terms equal. For n = 65,536, s = √65,536 = 256. Total attended pairs ≈ n·s + n·s = 2·n·s = 2 × 65,536 × 256 = 33,554,432. Full attention: n² = 65,536² = 4,294,967,296. Reduction factor = 4,294,967,296 / 33,554,432 = 128×.
Practice Exercises
Now it is time to practice! Complete these challenges to solidify your understanding:
- Exercise 1: Write a short program that demonstrates the core concept from this chapter. Test it with at least 3 different inputs.
- Exercise 2: Find a real-world example where sparse attention: making transformers efficient at scale is used in an Indian company (like TCS, Infosys, Flipkart, or ISRO). Write a paragraph explaining the connection.
- Exercise 3: Create a mind-map connecting sparse attention: making transformers efficient at scale to at least 3 other topics you have studied.