Longformer › Mathematical Formulation

To understand why Longformer works, we need to think carefully about what attention computes and why the standard approach becomes expensive. This journey from intuition to formal mathematics will reveal Longformer's mechanics and the deeper insight that makes efficient attention possible.

Understanding the math is not just academic. The formulas encode the design decisions that determine what relationships the model can and cannot learn. Once you see the equations, the tradeoffs in window size selection, global token placement, and the need for separate projection matrices all become transparent.

Recall that standard transformer attention computes, for each token, a weighted average of all other tokens in the sequence. For a token at position $i$, we ask: "How relevant is every other position to understanding this token?" The answer comes as a set of attention weights that sum to 1.

The issue is that this question scales poorly. If you have $n$ tokens, each token must compute $n$ attention scores, giving us $n^2$ total computations. For a 512-token sequence, that's about 260,000 attention weights per layer. For a 4,096-token document, it explodes to over 16 million. This quadratic scaling is what makes long documents prohibitively expensive.

In practice, memory is often the binding constraint before compute. Attention weights must be stored during the forward pass to allow gradient computation during backpropagation. A single attention head over a 4,096-token sequence stores a $4096 \times 4096$ matrix of float32 values, requiring 64 MB of GPU memory. A 12-layer model with 12 heads per layer requires around 9 GB for attention weights alone, leaving almost no headroom for activations, gradients, or optimizer states. Reducing the number of stored attention weights is therefore the most direct path to longer sequences.

Most of these computations are wasted. When you read the word "cat" in a sentence, you don't need to simultaneously consider a word from three paragraphs away to understand its meaning. Most language understanding happens locally. Longformer exploits this observation by restricting which tokens each position can attend to.

Longformer partitions the sequence into two distinct sets:

• Local tokens $\mathcal{L}$: The vast majority of tokens, which only need to see their immediate neighborhood
• Global tokens $\mathcal{G}$: A small number of special tokens that need to aggregate information from the entire sequence

For a sequence of length $n$, we typically have $|\mathcal{L}| \approx n$ local tokens and $|\mathcal{G}| \leq 10$ global tokens. This asymmetry is the source of Longformer's efficiency: we do expensive full-sequence attention for only a handful of tokens, while the rest use a much cheaper local pattern.

For local tokens, we define a window of size $w$ centered on each position. Instead of attending to all $n$ tokens, position $i$ only attends to positions within the range $[i - w/2, i + w/2]$. Think of it as a spotlight that follows each token, illuminating only its immediate neighborhood.

This restriction reflects a property of language: most syntactic and semantic relationships are local. Subjects tend to be near their verbs. Adjectives modify nearby nouns. Pronouns typically refer to recently mentioned entities. By focusing attention on a fixed-size window, we capture the dependencies that matter most while ignoring distant positions that rarely contribute meaningful information.

In practice, the window size $w$ is a critical hyperparameter. The original Longformer paper uses $w = 512$ for most experiments, matching the maximum sequence length of standard BERT. This means each token can see up to 256 positions to its left and 256 to its right, which is sufficient to capture most sentence-level and paragraph-level syntactic dependencies. Smaller windows (like 128 or 256) save memory and compute but may miss longer-range dependencies within a paragraph. Larger windows (like 1024) capture more context but reduce the sparsity gains that make Longformer efficient. The right window size depends on your task and the typical length of relevant local contexts within your documents.

The formal computation for a local token at position $i \in \mathcal{L}$ is:

$$\text{Attention}_i = \text{softmax}\left(\frac{Q_i K_{[i-w/2:i+w/2]}^\top}{\sqrt{d_k}}\right) V_{[i-w/2:i+w/2]}$$

Let's unpack each component:

• $Q_i = x_i W_Q$: The query vector for position $i$. This is what the token is "asking for" from other positions. We compute it by projecting the input embedding $x_i$ through a learned weight matrix $W_Q$.

• $K_{[i-w/2:i+w/2]}$: The key matrix containing only keys for tokens in the local window. This is a matrix of shape $(w, d_k)$ where each row is the key vector for one position in the window. Keys represent what each position "offers" to other tokens.

• $V_{[i-w/2:i+w/2]}$: The value matrix for the same window, also shape $(w, d_k)$. Values contain the actual information that gets aggregated. The attention weights determine how much of each value to include in the output.

• $d_k$: The dimension of key and query vectors, typically 64 in base transformer models.

• $\sqrt{d_k}$: A scaling factor that prevents attention scores from growing too large. Without this, dot products between high-dimensional vectors can become very large, causing softmax to produce nearly one-hot distributions that are hard to learn from.

The computation proceeds through three carefully designed steps:

1. Score computation: We compute $Q_i K_{[i-w/2:i+w/2]}^\top$, which produces a vector of $w$ scores. Each score measures how well the query at position $i$ matches each key in the window. Geometrically, this is a dot product: vectors pointing in similar directions produce high scores.

2. Normalization: We divide by $\sqrt{d_k}$ to stabilize the magnitude, then apply softmax to convert raw scores into a probability distribution. The $w$ weights now sum to 1, telling us what fraction of attention to allocate to each position.

3. Aggregation: We compute a weighted average of the value vectors using these probabilities. Positions with high attention weights contribute more to the output; positions with low weights contribute less.

The critical complexity reduction comes from step 1: instead of computing $n$ scores, we compute only $w$ scores. Since $w$ is a constant (typically 256 or 512), the cost per token is $O(w)$ instead of $O(n)$. Across all $n$ tokens, the total complexity is $O(nw)$, which is linear in sequence length.

Sliding window attention solves the efficiency problem, but it creates a new one: how does information travel between distant parts of the sequence? If token 1 can only see tokens 1-256, and token 4000 can only see tokens 3744-4000, how do they ever communicate?

In a standard transformer, information propagates through repeated local interactions across layers. After $L$ layers with window size $w$, a token's effective receptive field covers $L \times w$ positions. With 8 layers and window size 512, a token can be influenced by content up to 4,096 positions away, but this requires routing information through many intermediate tokens before it arrives. The signal may degrade or get mixed with irrelevant context along the way.

The answer in Longformer is global tokens. These are special positions that break the local-only rule. A global token attends to every position in the sequence, and every position attends back to it. Think of global tokens as relay stations: information from any part of the sequence can flow through them to reach any other part in a single attention step rather than through many layers of local propagation.

Global tokens are task-specific designations, not architectural constants. For a classification task, you designate the [CLS] token as global because it needs to aggregate the entire document before predicting a label. For question answering, you designate all question tokens as global because the model must scan the entire passage to locate the answer. For coreference resolution, you might designate entity mentions as global to allow the model to directly compare them regardless of how far apart they appear. This flexibility is one of Longformer's most practical advantages over methods that fix the sparse attention pattern at architecture design time.

For a global token at position $g \in \mathcal{G}$, the attention computation spans the entire sequence:

$$\text{Attention}_g = \text{softmax}\left(\frac{Q_g K^\top}{\sqrt{d_k}}\right) V$$

where:

• $Q_g = x_g W_Q^g$: The query vector for the global token, computed using a separate projection matrix $W_Q^g$
• $K$: The key matrix for all $n$ tokens, shape $(n, d_k)$
• $V$: The value matrix for all $n$ tokens, shape $(n, d_k)$

Global tokens use different projection matrices ($W_Q^g$, $W_K^g$, $W_V^g$) than local tokens ($W_Q$, $W_K$, $W_V$) because local and global attention serve fundamentally different purposes.

When a local token computes attention, it is asking: "Which of my neighbors help me understand my immediate context?" When a global token computes attention, it is asking: "What are the most important pieces of information across the entire document?" These are different questions, and the model benefits from learning different representations to answer them.

The separation also matters for the tokens attending to global positions. When a local token attends to a global token, it should receive a representation tailored for aggregation, not one optimized for local context understanding. The separate projection matrices allow this flexibility. Without them, the model would need a single set of projections that performs well at both local syntactic reasoning and global semantic aggregation simultaneously. In practice, sharing projections forces a compromise that reduces performance on both tasks. The separate projections roughly double the parameter count in attention layers, but this cost is worthwhile for the quality improvement they provide.

The separate global projections also help with training stability. Because global tokens see vastly more positions than local tokens, the gradients flowing back through them have a different character: they average information from across the entire sequence rather than from a small local neighborhood. Using separate parameters allows the optimizer to calibrate learning rates and weight updates appropriately for each regime without the two objectives interfering with each other.

Global attention is bidirectional: global tokens attend to all positions, and all positions attend back to global tokens. This symmetry is essential for information flow. It is worth pausing to understand exactly what "bidirectional" means here and why it matters.

If global attention were one-directional, say global tokens attend to all positions but local tokens cannot attend back to global tokens, then local tokens would be unaware that a global token exists. A paragraph in the middle of a document would compute its local representations without incorporating any document-level signal. The classification token at position 0 would aggregate information from the full document, but the words in paragraph 7 would not have access to what the classification token "knows" about the document structure.

With bidirectional global attention, every local token's output representation includes a weighted combination of the global token representations as part of its attended context. This is the mechanism by which document-level information percolates down to even the most local tokens. A sentence in paragraph 7 can effectively "know" what the document's main question is because it attends to the [CLS] or question tokens that encode that information.

Consider document classification with a [CLS] token at position 0. The [CLS] token needs to see the entire document to make a classification decision, so it receives global attention. But equally important, every token in the document can "see" the [CLS] token and incorporate that global context into its own representation. This bidirectional flow ensures that even local tokens have access to document-level information, just mediated through the global tokens rather than computed directly.

The symmetry also provides a useful mental model for thinking about information paths in the network. Without global tokens, information takes a long path: it travels layer by layer through local windows, like a game of telephone where each intermediary can only talk to its neighbors. With global tokens, any token can communicate with any other token in two steps: first to a global token, then from that global token to the destination. The maximum information distance collapses from $O(n / w)$ hops (proportional to sequence length divided by window size) to just 2 hops when a global token mediates the connection.

Now we can see how Longformer attention works as a unified system:

1. Most tokens use sliding window attention, computing relevance only within their local neighborhood. This keeps the bulk of computation cheap.

2. A few tokens (typically [CLS], question tokens, or task-specific markers) use global attention, seeing the entire sequence. This maintains the ability to aggregate long-range information.

3. All tokens can attend to global tokens, even if they're outside the local window. This ensures information can flow from any position to any other position through the global intermediaries.

The result is a sparse attention pattern that covers the essential dependencies while skipping the redundant ones. Local relationships are captured directly. Global relationships are captured through designated relay tokens.

Let's verify that this design achieves linear complexity. The total attention computation involves three components:

1. Local attention: Each of the $n$ tokens computes attention over a window of size $w$. This contributes $O(nw)$ to the total cost.

2. Global tokens attending to all: Each of the $|\mathcal{G}|$ global tokens attends to all $n$ positions. This contributes $O(|\mathcal{G}| \cdot n)$.

3. All tokens attending to global tokens: Each token includes global positions in its attention set. This cost is already absorbed into the local window computation (global tokens simply become part of the attended set).

The total complexity is:

$$O(nw + |\mathcal{G}| \cdot n) = O(n(w + |\mathcal{G}|))$$

where:

• $n$: the sequence length, the variable that grows with document size
• $w$: the sliding window size, a constant chosen at model design time (typically 512)
• $|\mathcal{G}|$: the number of global tokens, a constant chosen per task (typically 1 to 10)

The key observation is that $(w + |\mathcal{G}|)$ is a constant. It doesn't grow with sequence length. This means the overall complexity is $O(n)$, linear in sequence length.

Compare this to standard attention's $O(n^2)$ complexity. When you double the sequence length:

• Standard attention: cost quadruples ($2n \times 2n = 4n^2$)
• Longformer attention: cost only doubles ($2n \times (w + |\mathcal{G}|) = 2 \times n(w + |\mathcal{G}|)$)

This difference is what enables Longformer to process documents of 4,096 tokens or more on hardware that would run out of memory with standard attention at just 512 tokens.