Exact Attention at Extreme Scale: Combinatorial Decomposition Enables Billion-Token Contexts on Single GPUs

Long context windows remain one of the most persistent bottlenecks in large language model deployment. While architectural innovations have pushed context lengths from thousands to millions of tokens, the fundamental constraint of GPU memory continues to limit practical scalability. The issue is not merely computational; the quadratic memory complexity of exact self attention means that for sufficiently long sequences, simply materializing the query, key, and value tensors exhausts available device memory before computation even begins.

Existing solutions fall into two categories. Methods like FlashAttention and its successors optimize the IO patterns of attention computation, reducing memory usage from quadratic to linear relative to sequence length, but they assume the full QKV tensors reside in GPU memory. Approximate methods, including sparse attention and kernelized approaches, reduce complexity by sacrificing exactness. Neither addresses the scenario where the input tensors themselves exceed memory capacity.

The paper "Stream-CQSA: Avoiding Out-of-Memory in Attention Computation via Flexible Workload Scheduling" by Bian and Akey introduces a fundamentally different approach. By deriving a decomposition from cyclic quorum sets (CQS) theory, the authors demonstrate how to partition attention into independent subsequence computations whose recomposition yields mathematically exact results, enabling streaming execution of billion token sequences on memory constrained hardware.

The Combinatorial Foundation of CQS Divide

At the heart of Stream-CQSA lies CQS Divide, an operation that decomposes the complete graph of token interactions into smaller complete subgraphs. The mathematical elegance of this approach stems from its basis in combinatorial design theory, specifically Steiner systems.

The construction requires partitioning a sequence of length N into c chunks. The goal is to create subsequences such that every pair of chunks interacts exactly once across the entire computation, ensuring no redundancy while maintaining completeness. For a decomposition parameter l, the number of chunks must satisfy c = l(l-1) + 1, generating the sequence {1, 3, 7, 13, 21, ...}. Each subsequence consists of l chunks, and there are exactly c such subsequences.

The smallest nontrivial case uses l=3 and c=7. Here, the sequence divides into seven chunks (C0 through C6), with each subsequence i constructed as concat(C(0+i)mod7, C(1+i)mod7, C(3+i)mod7). The base pattern (0,1,3) serves as the interest set I, and the cyclic permutation ensures that every possible pair of chunks appears in exactly one subsequence. This corresponds to a Steiner system S(2, 3, 7), a well studied configuration in design theory where every pair of elements appears in exactly one block.

This decomposition preserves exactness because attention computation over a subsequence captures all pairwise interactions within that subset. By ensuring that every pair of original chunks appears together in exactly one subsequence, the union of all subsequence attentions covers the full attention matrix without overlap or omission. The recomposition simply aggregates the numerators and denominators of the softmax computations across subsequences, followed by normalization.

Streaming Execution and Memory Adaptivity

Stream-CQSA operationalizes this decomposition through a streaming framework that treats attention not as a monolithic operation but as a collection of schedulable tasks. Algorithm 1 outlines the forward pass: for each subsequence defined by the CQS construction, the system gathers the relevant query, key, and value tensors, computes the attention output for that subsequence, and scatters the results into global accumulators for the numerator and denominator.

The memory advantage becomes apparent when considering the working set size. Rather than materializing Q, K, and V tensors of shape (B, H, N, D) where N is the full sequence length, the system only needs to hold tensors corresponding to l chunks at any given time. For the c=7, l=3 case, this reduces the memory requirement by roughly a factor of c/l, or approximately 2.3x, though the actual savings scale with the recursive application of the decomposition.

Critically, this approach enables exact gradient computation during training. The backward pass mirrors the forward decomposition, computing gradients for each subsequence independently before merging them back to full sequence coordinates. This avoids the approximation errors inherent in checkpointing strategies that discard intermediate activations, or the communication overhead of tensor parallelism across devices.

Analysis of Trade-offs and Practical Implications

While the theoretical contribution of CQS Divide is compelling, the practical implications warrant careful analysis. The method trades computational efficiency for memory capacity. Specifically, the total floating point operations increase because each token participates in multiple subsequences. For the c=7 construction, each chunk appears in exactly three subsequences (since each chunk pairs with six others, and each subsequence containing it covers two of those pairs). Thus, the total computation increases by a factor of l relative to standard attention, or 3x in this case.

This trade off reveals an interesting asymmetry in modern AI hardware. Memory capacity has grown slower than computational throughput; HBM capacity increases linearly with hardware generations while FLOPS grow exponentially. Stream-CQSA exploits this divergence by converting memory pressure into additional computation, a strategy that becomes increasingly favorable as compute costs relative to memory continue to decline.

However, the approach introduces scheduling complexity that existing deep learning frameworks may not optimize for efficiently. The gather and scatter operations, while conceptually simple, require careful memory management to avoid fragmentation. Furthermore, the discrete nature of