Count local and global connections without double-counting

For a noncausal sequence indexed zero through N−1, a radius-r local window includes keys whose distance in position is at most r, including the token itself. Interior rows have 2r+1 keys, but boundary rows have fewer. Summing clipped row widths gives an exact count smaller than N(2r+1). Causal windows use a different one-sided pattern, so a radius or width must be defined before comparing formulas or library settings.

Longformer combines local windows with selected symmetric global connections; BigBird combines local, random, and global patterns in its original construction. These choices define different operators and inductive biases. The simple count in this lesson describes a boolean dependency pattern with shared ordinary score semantics, not every projection or positional-bias detail of either architecture. In particular, actual Longformer includes separate projections for global attention, which must be preserved in an implementation-equivalence reference.

Let a selected set of g existing tokens be global. Add all edges from every global query to all keys and from every ordinary query to every global key, then union them with the local pattern. The global-global submatrix lies in both added rectangles, and many global-local edges were already local. Counting each distinct ordered pair once avoids exaggerating work or accidentally duplicating a key’s exponential weight in the denominator.

For fixed radius and fixed global-token count, the upper bound is linear in N. If the task marks a number of global tokens that grows proportionally with the sequence length, the added rectangles can become quadratic. Thus a report of linear attention must state which parameters are held constant. Random blocks introduce another term and seed-dependent realized pattern, so their count and overlap should be included explicitly rather than hidden inside the word sparse.

With only radius-r local attention, stacking layers can move information across a larger neighborhood through intermediate tokens. Global tokens create shorter routes, but an ordinary query reading a global token in the current layer reads that token’s input representation, not its newly computed output from the same parallel layer. A distant ordinary token’s new information generally needs another layer to travel through a global intermediary. Structural connectivity is a capacity for communication, not a guarantee that training uses it effectively.

Evaluate the kernel against the exact intended window/global mask and projections, then evaluate task quality against the desired dense or alternative architecture. Include globals at boundaries and in the middle, overlapping local/global entries, and cases where every token is global. A useful implementation should neither count duplicates twice nor silently expand a bounded window into dense work. Measure actual executed tiles as well as logical pairs, because a fine window can occupy partially masked hardware blocks.