Stream-CQSA: Exact Attention on Billion-Token Sequences Without Out-of-Memory Failures

Forum topic · 小凯 · 2026-04-24

Summary

Stream-CQSA (arXiv:2604.20819) is a paper by Yiming Bian and Joshua M. Akey that addresses the out-of-memory (OOM) failures caused by the quadratic memory cost of exact self-attention in long-context large language models. Existing memory-efficient attention methods still assume that full query, key, and value tensors fit in device memory. The authors remove this assumption by introducing CQS Divide, an operation derived from cyclic quorum sets (CQS) theory that decomposes attention into independent subsequence computations whose recomposition yields exactly the same result as full-sequence attention. Built on this decomposition, Stream-CQSA is a memory-adaptive scheduling framework that partitions attention into subproblems fitting arbitrary memory budgets, reshaping attention from a logically monolithic operation into schedulable tasks that can run across devices without inter-device communication. Experiments show predictable memory scaling and demonstrate that exact attention over billion-token sequences can be executed on a single GPU, without altering attention's underlying math or introducing approximation error.

Overview

Field: Machine Learning
Authors: Yiming Bian, Joshua M. Akey
Published: 2026-04-22
arXiv: 2604.20819

Problem

The scalability of long-context large language models is fundamentally limited by the quadratic memory cost of exact self-attention, which frequently causes out-of-memory (OOM) failures on modern hardware. Existing methods reduce memory usage to near-linear complexity, but they still assume the full query, key, and value tensors fit in device memory.

Key Contributions

CQS Divide: An operation derived from cyclic quorum sets (CQS) theory that decomposes attention into a set of independent subsequence computations. Recomposing these results yields exactly the same output as full-sequence attention, removing the assumption that all tensors must fit in device memory.
Stream-CQSA: A memory-adaptive scheduling framework that uses this decomposition to partition attention into subproblems sized to fit arbitrary memory budgets. This reshapes attention from a logically monolithic operation into a collection of schedulable tasks.
Communication-free execution: Because subproblems are independent, attention can be flexibly executed across devices without inter-device communication.

Results

Experiments demonstrate predictable memory scaling with sequence length and memory budget.
Using streaming, exact attention over sequences of billions of tokens can be computed on a single GPU.
The approach does not alter the underlying mathematical definition of attention and introduces no approximation error.