Stream-CQSA: Resolving Memory Bottlenecks in Attention Computation via Flexible Workload Scheduling

This article introduces Stream-CQSA, a novel attention computation method based on the theory of Cyclic Quorum Sets (CQS), which can handle sequences of billions of tokens on a single GPU, completely avoid memory overflow, maintain precise attention computation without introducing approximation errors, and break through the memory bottleneck of large language models with long contexts.

The self-attention mechanism is a core component of the Transformer architecture, and its memory demand grows quadratically with sequence length—for a sequence of millions of tokens, the attention matrix alone requires several terabytes of memory. Existing optimization techniques (sparse attention, linear attention approximation, gradient checkpointing) either introduce approximation errors or are still limited by memory capacity, making them unable to handle ultra-large-scale sequences.

The core of Stream-CQSA is the CQS Divide operation, derived from the Cyclic Quorum Set (CQS) theory. Its key insight is that the attention of a complete sequence can be exactly decomposed into independent sub-sequence computations, and the results can be restored via a recombination strategy (without approximation). The input sequence is divided into sub-sequences; each sub-sequence computation involves internal tokens and external tokens selected by CQS, controlling memory demand while ensuring the integrity of global semantics.

Stream-CQSA is a memory-adaptive scheduling system. Its workflow includes: evaluating memory budget to determine sub-problem size; decomposing into sub-problems that meet the budget (minimizing redundancy); scheduling execution according to dependencies and resources (single/multi-device); merging sub-results to get the complete output. It supports stream execution, which can handle continuous token streams without waiting for the complete sequence.

Experiments show that memory demand is linearly related to the size of sub-problems. Exact attention computation for billions of tokens (without approximation errors) was successfully executed on a single consumer-grade GPU. Although there is scheduling overhead, the overall time does not increase significantly under parallel execution; in memory-constrained scenarios, it even avoids swap overhead and improves wall-clock performance.

Stream-CQSA removes the constraint of memory on context length, making it possible to deploy ultra-long context models on resource-constrained devices; it maintains the mathematical purity of attention, so existing theories and optimizations are still applicable; its streaming capability supports new scenarios such as real-time long-document analysis and continuous learning.

The current implementation targets standard self-attention and needs to be extended to variants such as multi-head and cross-attention; the computational complexity is still quadratic, which can be reduced by combining linear approximation or sparse patterns; explore different CQS construction strategies and learn to optimize CQS parameters.