Sparse Attention Changes the Visibility Graph

Calculate dense, local-window, and global-token causal visibility edges, then separate guaranteed graph savings from task-dependent empirical quality.

Dense causal attention allows position $i$ to read every position from $0$ to $i$ . Sparse attention removes selected edges from this visibility graph. The immediate saving is countable; the effect on learning is task-dependent.

Count Dense Causal Edges

For length $T$ , row $i$ contains $i+1$ allowed keys. Therefore

E_{dense}=\sum_{i=0}^{T-1}(i+1)=\frac{T(T+1)}{2}.

At $T=8$ , dense causal attention has $8\times9/2=36$ edges.

Count a Local Window

Let each query see itself and at most $w$ preceding tokens. Then

E_{local}=\sum_{i=0}^{T-1}\min(i+1,w+1).

For $T=8$ and $w=2$ , the row counts are

[1,2,3,3,3,3,3,3],

so $E_{local}=21$ . Adding position 0 as a global key gives 26 edges because five later rows gain one edge that was not already local.

Pattern	Edges at $T=8$	Immediate fact
dense causal	36	every earlier position is directly visible
local causal, $w=2$	21	direct visibility is limited to recent positions
local plus global position 0	26	every row can also read the first token

Fewer Edges Do Not Guarantee the Same Capability

With a local window, position 7 cannot directly read position 1. Information may travel through several layers, or a global/structured edge may connect the positions. Whether this is sufficient depends on the task and depth.

Longformer combines local and task-specific global attention. BigBird studies a different mix of local, global, and random connections. Their results support their specified graphs and experiments, not every sparse pattern.

Q1. Count local causal edges

For $T=5$ and $w=1$ , each query sees itself and at most one preceding token. How many edges are allowed?

Your answer

Compute it first, then check your number.

Hint

Add

[1,2,2,2,2]

Solution

The sum is

1+2+2+2+2=9

State the Two Claims Separately

“This graph uses 21 rather than 36 edges” is an analytical result. “This graph preserves accuracy on a task” requires a controlled experiment.