Long Context Techniques: Sliding Window, Sparse Attention, and Retrieval-Augmented Approaches

Positional encodings (previous subtopic) help a model GENERALIZE to longer sequences, but they don't reduce the underlying O(n^2) computational cost from the first subtopic — a rotated or biased attention score is still one score among n^2 total scores that must be computed. This subtopic covers techniques that attack the cost itself, by changing WHAT gets computed, not just how position is represented.

Sliding window attention restricts each token to only attend to a fixed-size WINDOW of nearby tokens (say, the previous 4096 tokens), rather than the entire sequence. This caps the per-token attention cost at a constant amount regardless of total sequence length — instead of O(n^2) for the whole sequence, it's O(n * w) where w is the fixed window size, which scales LINEARLY with n instead of quadratically. The tradeoff is direct: a token genuinely loses direct access to information far outside its window. Some architectures (Mistral's sliding window attention is a well-known example) partially compensate by stacking multiple layers, so information can still propagate across a wider effective range through several hops, even though no single layer's attention spans the whole sequence directly.

Sparse attention takes a related but more flexible approach: instead of a fixed contiguous window, only compute attention for a carefully chosen SUBSET of token pairs (e.g. attend densely to nearby tokens, plus sparsely to a few distant 'global' tokens, or tokens selected by some learned or fixed pattern), skipping the vast majority of the n^2 pairs entirely. This preserves some ability to attend to distant, important context (unlike a strict sliding window) while still avoiding the full quadratic cost — the design challenge is choosing WHICH sparse pattern captures enough of the genuinely useful long-range dependencies without needing every pair.

Retrieval-augmented approaches sidestep the problem differently: rather than feeding an enormous document directly into the context window at all, use RAG (covered extensively elsewhere in this curriculum) to retrieve only the most relevant chunks at query time, keeping the ACTUAL context the model attends to comparatively short regardless of how large the underlying knowledge base is. This is a fundamentally different strategy from the previous two — rather than making the ATTENTION mechanism cheaper for a fixed amount of information, it reduces HOW MUCH information ever needs to enter the context window in the first place. The next subtopic covers exactly when this retrieval-based strategy is preferable to simply using a model's full long context window, and when it isn't.

# Comparing full attention's O(n^2) cost against sliding-window
# attention's O(n*w) cost, and a sparse-attention pattern that mixes
# local + global tokens.

def full_attention_cost(seq_len: int) -> int:
    return seq_len * seq_len

def sliding_window_cost(seq_len: int, window: int) -> int:
    """Each token attends to at most `window` neighbors -- cost scales
    LINEARLY with seq_len instead of quadratically."""
    return seq_len * window

def sparse_attention_pattern(seq_len: int, local_window: int, num_global: int) -> set:
    """A toy sparse pattern: each token attends locally, PLUS every
    token attends to a small fixed set of 'global' tokens (e.g. the
    first few tokens) -- captures some long-range info cheaply."""
    global_tokens = set(range(num_global))
    pairs = set()
    for i in range(seq_len):
        for j in range(max(0, i - local_window), i + 1):
            pairs.add((i, j))            # local window
        for g in global_tokens:
            pairs.add((i, g))             # global tokens, cheap addition
    return pairs

seq_len, window = 10_000, 512
print(f"Full attention pairs:          {full_attention_cost(seq_len):>15,}")
print(f"Sliding window attention pairs: {sliding_window_cost(seq_len, window):>15,}")
print(f"Reduction factor: {full_attention_cost(seq_len) / sliding_window_cost(seq_len, window):.0f}x fewer computations\n")

small_seq = 20
sparse_pairs = sparse_attention_pattern(small_seq, local_window=2, num_global=2)
print(f"Sparse pattern on a {small_seq}-token sequence: {len(sparse_pairs)} pairs "
      f"(vs {full_attention_cost(small_seq)} for full attention)")