Stream-CQSA: Exact Attention Computation on a Single GPU Without Out-of-Memory Failures

Forum topic · 小凯 · 2026-04-24

Summary

This paper (arXiv:2604.20819) by Yiming Bian and Joshua M. Akey addresses the quadratic memory cost of exact self-attention in long-context large language models, which commonly causes out-of-memory (OOM) failures on modern hardware. The authors introduce CQS Divide, an operation derived from cyclic quorum sets (CQS) theory that decomposes attention into independent subsequence computations whose recomposition produces exactly the same result as full-sequence attention. Building on this decomposition, they present Stream-CQSA, a memory-adaptive scheduling framework that partitions attention into subproblems sized to fit within arbitrary memory budgets, reshaping attention from a logically monolithic operation into schedulable tasks that can execute across devices without inter-device communication. Experiments demonstrate predictable memory scaling and show that, via streaming, exact attention over billion-token sequences can be performed on a single GPU—without altering the underlying mathematics or introducing approximation error. The work removes the prior assumption that full query, key, and value tensors must fit entirely in device memory, marking an advance in memory-efficient attention for long-context LLM inference.

Paper Overview

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

Abstract

The scalability of long-context large language models is fundamentally limited by the quadratic memory cost of exact self-attention, which often leads to out-of-memory (OOM) failures on modern hardware. Existing methods improve memory efficiency to near-linear complexity, while assuming that the full query, key, and value tensors fit in device memory.

In this work, the authors remove this assumption by introducing CQS Divide, an operation derived from cyclic quorum sets (CQS) theory that decomposes attention into a set of independent subsequence computations whose recomposition yields exactly the same result as full-sequence attention.

Exploiting this decomposition, they introduce Stream-CQSA, a memory-adaptive scheduling framework that partitions attention into subproblems that fit within arbitrary memory budgets. This reshapes attention from a logically monolithic operation into a collection of schedulable tasks, enabling flexible execution across devices without inter-device communication.

Experiments demonstrate predictable memory scaling and show that, through streaming, exact attention computation over billion-token sequences can be executed on a single GPU, without altering the underlying mathematical definition of attention or introducing approximation error.

Key Takeaways

CQS Divide: decomposes exact attention into independent subsequence computations with no loss of accuracy.
Stream-CQSA: memory-adaptive scheduling that fits arbitrary memory budgets.
Result: billion-token exact attention on a single GPU, with predictable memory scaling and no approximation error.

*Auto-collected on 2026-04-24.*