Michael Brenndoerfer | Data & AI, Private Equity, Technology

Michael Brenndoerfer

BigBird › Why Random Attention Works

Michael BrenndoerferUpdated June 24, 20257 min read

Language AI HandbookAll chapters

Part 17 of 67Efficient Attention

Chapter 122BigBird › Why Random Attention Works

Reading section 3 of 12 · Why Random Attention Works · 7 minSection 3 of 12 · 7 min

Section 3 of 12 · 7 min read

BigBird › Why Random Attention WorksOne section · Sections in this chapter3 / 12 ↓

Sections in this chapter12

Reading tools Definitions & inline links

Choose your expertise level to adjust how many terms are explained. Beginners see more tooltips, experts see fewer to maintain reading flow. Hover over underlined terms for instant definitions.

Article links

Make inline references clickable

We've claimed that random attention connections have deep theoretical significance, but why exactly? To understand this, we need to think about attention patterns as graphs and consider how information propagates through them.

The Graph Theory PerspectiveLink Copied

The key insight is to view attention as a communication network. Each token is a node, and an attention connection is a directed edge along which information can flow. When token $i$ attends to token $j$ , information from $j$ 's representation contributes to $i$ 's output. Over multiple layers, information propagates along paths in this graph.

Formally, consider the attention pattern as a directed graph $G = (V, E)$ where each token is a node, and there's an edge from token $i$ to token $j$ if $i$ attends to $j$ :

E = \{(i, j) : \text{token } i \text{ attends to token } j\}

The diameter of this graph is the maximum shortest path length between any two nodes:

\text{diameter}(G) = \max_{u, v \in V} d(u, v)

where $d(u, v)$ is the shortest path length from node $u$ to node $v$ .

With only local sliding window attention, the diameter is $O(n/w)$ . To understand why, consider passing information from token 1 to token $n$ . Each attention layer can propagate information by at most $w$ positions in either direction. Therefore, you need at least $\lceil n / w \rceil$ layers (or attention hops) to bridge the gap. This limits how deep information can flow in a fixed number of layers.

Adding random connections reduces the diameter to $O(\log n)$ with high probability. This is a well-known result from random graph theory: even a small number of random edges create shortcuts that connect distant regions of the graph. These shortcuts mean that any two nodes can reach each other in logarithmic rather than linear steps.

In[8]:

Code

def estimate_graph_diameter(mask, num_samples=100):
    """
    Estimate the diameter of the attention graph using BFS.

    Args:
        mask: Binary attention mask (n, n)
        num_samples: Number of random source nodes to sample

    Returns:
        Estimated diameter (maximum shortest path length)
    """
    n = mask.shape[0]
    max_distance = 0

    # Sample random source nodes
    sources = np.random.choice(n, size=min(num_samples, n), replace=False)

    for source in sources:
        # BFS from source
        visited = np.zeros(n, dtype=bool)
        distance = np.full(n, -1)
        queue = [source]
        distance[source] = 0
        visited[source] = True

        while queue:
            current = queue.pop(0)
            # Find neighbors (positions this token attends to)
            neighbors = np.where(mask[current] > 0)[0]
            for neighbor in neighbors:
                if not visited[neighbor]:
                    visited[neighbor] = True
                    distance[neighbor] = distance[current] + 1
                    queue.append(neighbor)

        # Update max distance for reachable nodes
        reachable_distances = distance[distance >= 0]
        if len(reachable_distances) > 0:
            max_distance = max(max_distance, reachable_distances.max())

    return max_distance


# Compare diameters of different attention patterns
seq_len_test = 128

# Local-only attention
local_only_mask = np.zeros((seq_len_test, seq_len_test))
window = 3
for i in range(seq_len_test):
    start = max(0, i - window)
    end = min(seq_len_test, i + window + 1)
    local_only_mask[i, start:end] = 1.0

# BigBird attention (local + global + random)
bigbird_test_mask = create_bigbird_attention_pattern(
    seq_len_test, window_size=3, num_global=2, num_random=3, seed=42
)

local_diameter = estimate_graph_diameter(local_only_mask)
bigbird_diameter = estimate_graph_diameter(bigbird_test_mask)

Out[9]:

Console

Graph diameter comparison (n=128):
  Local-only attention: 43
  BigBird attention:    2

Theoretical expectation:
  Local-only: O(n/w) = 128/3 ≈ 42
  BigBird:    O(log n) = log2(128) ≈ 7

The measured diameters closely match theoretical predictions. With local-only attention, information must hop through roughly 42 positions to traverse the sequence, but BigBird's random connections create shortcuts that reduce this to just a handful of hops. This dramatic reduction means information can propagate between any two tokens in just a few attention layers. This is essential for tasks requiring long-range reasoning, such as understanding that a pronoun at position 500 refers to an entity introduced at position 50.

Out[10]:

Visualization

Line plot showing graph diameter versus sequence length for three attention patterns, with BigBird achieving the flattest curve. — Graph diameter scaling for different attention patterns. Local-only attention (blue) grows linearly with sequence length, requiring O(n/w) hops to traverse the sequence. Adding global tokens (orange) reduces diameter but still grows. BigBird with random connections (green) achieves logarithmic diameter, staying nearly flat as sequence length increases.

The visualization confirms the theoretical predictions. Local-only attention diameter grows linearly, closely following the $O(n/w)$ curve. BigBird's diameter stays nearly flat, following the $O(\log n)$ curve. This logarithmic scaling is the key to BigBird's ability to handle long sequences: even for 16,384-token documents, information only needs about 14 hops to travel end-to-end.

Theoretical GuaranteesLink Copied

The practical benefits of reduced graph diameter translate into formal theoretical guarantees. The BigBird paper provides three key proofs about the expressiveness of their sparse attention pattern:

1. Turing Completeness. BigBird sparse attention can simulate any Turing machine. This proves that the sparse pattern is computationally universal. Any computation that can be performed by a standard transformer (which is Turing complete) can also be performed by a BigBird transformer. The random connections are essential for this proof because they ensure the attention graph is well-connected enough to route information arbitrarily.

2. Universal Approximation. Any sequence-to-sequence function computed by a full attention transformer can be approximated by a BigBird transformer with only $O(1)$ random connections per position. You don't need many random connections. A constant number per token, regardless of sequence length, is sufficient. The proof relies on showing that the BigBird pattern can simulate a star graph (where one central node connects to all others), which in turn can simulate full attention.

3. Star Graph Simulation. The combination of global and random attention can simulate the star graph topology, which is sufficient for full attention approximation. Intuitively, any full attention computation can be decomposed into: (a) aggregating information at a central hub, (b) processing it, and (c) distributing results back. The global tokens provide the hub, and random connections ensure the hub can reach any position efficiently.

These results provide confidence that BigBird's sparse pattern doesn't fundamentally limit what the model can learn. The efficiency gains come from reducing constant factors and exploiting the structure of natural data, not from sacrificing expressive power. When BigBird performs worse than full attention on some task, it's because the learned attention patterns happened to need dense connections, not because the architecture is inherently less capable.