Stream-CQSA: Avoiding Out-of-Memory in Attention Computation via Flexible Workload Scheduling

• URL: http://arxiv.org/abs/2604.20819v1
• Date: Wed, 22 Apr 2026 17:46:09 GMT
• Title: Stream-CQSA: Avoiding Out-of-Memory in Attention Computation via Flexible Workload Scheduling
• Abstract summary: Stream-CQSA is a memory-adaptive scheduling framework that partitions attention into subproblems that fit within arbitrary memory budgets.<n> Experiments demonstrate predictable memory scaling and show that exact attention over billion-token sequences can be executed on a single GPU via streaming.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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, we 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, we introduce Stream-CQSA, a memory-adaptive scheduling framework that partitions attention into subproblems that fit within arbitrary memory budgets. This recasts 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 exact attention over billion-token sequences can be executed on a single GPU via streaming, without changing the underlying mathematical definition of attention or introducing approximation error.

Related papers

• LLM Inference in a Flash! [66.43896490006965]
  Large Language Models (LLMs) have shown impressive capabilities across a range of natural language processing tasks.<n>We present an end-to-end integer-only quantization approach to eliminate expensive floating-point computations.
  arXiv  Detail & Related papers  (2026-09-14T18:04:30Z)
• Self-Indexing KVCache: Predicting Sparse Attention from Compressed Keys [30.377113902938678]
  Existing approaches treat sparsity prediction and compression as separate modules, relying on auxiliary index structures to select relevant tokens, and on complex quantization schemes to reduce memory usage.<n>We propose a novel paradigm: treating the compressed key representation not merely as storage, but as a self-indexing structure that directly enables efficient attention.<n>By designing a sign-based 1-bit vector quantization (VQ) scheme, our method unifies compression and retrieval in a single, hardware-friendly format.
  arXiv  Detail & Related papers  (2026-03-15T05:02:17Z)
• RAM-Net: Expressive Linear Attention with Selectively Addressable Memory [11.262593123857995]
  RAM-Net is a novel architecture designed to bridge the gap between the representational capacity of full attention and the memory efficiency of linear models.<n>The core of RAM-Net maps inputs to high-dimensional sparse vectors serving as explicit addresses, allowing the model to selectively access a massive memory state.
  arXiv  Detail & Related papers  (2026-02-12T13:55:29Z)
• Fast SAM2 with Text-Driven Token Pruning [52.8350457627401]
  Segment Anything Model 2 (SAM2), a vision computation model has significantly advanced in prompt-driven video object segmentation.<n>SAM2 pipelines propagate all visual tokens produced by the image encoder through downstream temporal reasoning modules, regardless of their relevance to the target object.<n>We introduce a text-guided token pruning framework that improves inference efficiency by selectively reducing token density prior to temporal propagation.
  arXiv  Detail & Related papers  (2025-12-24T18:59:05Z)
• Training-free Context-adaptive Attention for Efficient Long Context Modeling [57.703159205740185]
  Training-free Context-adaptive Attention (TCA-Attention) is a training-free sparse attention mechanism that selectively attends to only the informative tokens for efficient long-context inference.<n>TCA-Attention achieves a 2.8$times$ speedup and reduces KV cache by 61% at 128K context length while maintaining performance comparable to full attention.
  arXiv  Detail & Related papers  (2025-12-10T01:54:57Z)
• OptPipe: Memory- and Scheduling-Optimized Pipeline Parallelism for LLM Training [13.814101909348183]
  Pipeline (PP) has become a standard technique for scaling large language model (LLM) training across multiple devices.<n>In this work, we revisit the pipeline scheduling problem from a principled optimization perspective.<n>We formulate scheduling as a constrained optimization problem that jointly accounts for memory capacity, activation reuse, and pipeline bubble minimization.
  arXiv  Detail & Related papers  (2025-10-06T01:06:33Z)
• RetroInfer: A Vector-Storage Approach for Scalable Long-Context LLM Inference [27.69137902678418]
  RetroInfer is a novel system that exploits the inherent attention sparsity to accelerate long-context inference.<n>We show up to 4.5X speedup over full attention within GPU memory limits and up to 10.5X over sparse attention baselines when KV cache is extended to CPU memory.
  arXiv  Detail & Related papers  (2025-05-05T18:01:17Z)
• Structured Token Retention and Computational Memory Paths in Large Language Models [0.0]
  This paper introduces a probabilistic selection framework that dynamically adjusts token persistence based on contextual significance.<n>It is extended through hierarchical memory allocation, refining retention efficiency through structured reallocation of token embeddings.<n>The integration of STR and CMP into an open-source model illustrates the adaptability of structured memory retention methodologies.
  arXiv  Detail & Related papers  (2025-02-05T11:59:22Z)
• ThinK: Thinner Key Cache by Query-Driven Pruning [63.13363917871414]
  Large Language Models (LLMs) have revolutionized the field of natural language processing, achieving unprecedented performance across a variety of applications.<n>This paper focuses on the long-context scenario, addressing the inefficiencies in KV cache memory consumption during inference.<n>We propose ThinK, a novel query-dependent KV cache pruning method designed to minimize attention weight loss while selectively pruning the least significant channels.
  arXiv  Detail & Related papers  (2024-07-30T17:59:08Z)
• Sparser is Faster and Less is More: Efficient Sparse Attention for Long-Range Transformers [58.5711048151424]
  We introduce SPARSEK Attention, a novel sparse attention mechanism designed to overcome computational and memory obstacles. Our approach integrates a scoring network and a differentiable top-k mask operator, SPARSEK, to select a constant number of KV pairs for each query. Experimental results reveal that SPARSEK Attention outperforms previous sparse attention methods.
  arXiv  Detail & Related papers  (2024-06-24T15:55:59Z)
• CORM: Cache Optimization with Recent Message for Large Language Model Inference [57.109354287786154]
  We introduce an innovative method for optimizing the KV cache, which considerably minimizes its memory footprint. CORM, a KV cache eviction policy, dynamically retains essential key-value pairs for inference without the need for model fine-tuning. Our validation shows that CORM reduces the inference memory usage of KV cache by up to 70% with negligible performance degradation across six tasks in LongBench.
  arXiv  Detail & Related papers  (2024-04-24T16:11:54Z)
• Bifurcated Attention: Accelerating Massively Parallel Decoding with Shared Prefixes in LLMs [39.16152482491236]
  Bifurcated attention is a method designed to enhance language model inference in shared-context batch decoding scenarios. Our approach addresses the challenge of redundant memory IO costs, a critical factor contributing to latency in high batch sizes and extended context lengths.
  arXiv  Detail & Related papers  (2024-03-13T16:30:57Z)
• Ring Attention with Blockwise Transformers for Near-Infinite Context [88.61687950039662]
  We present a novel approach, Ring Attention with Blockwise Transformers (Ring Attention), which leverages blockwise computation of self-attention and feedforward to distribute long sequences across multiple devices. Our approach enables training and inference of sequences that are up to device count times longer than those achievable by prior memory-efficient Transformers.
  arXiv  Detail & Related papers  (2023-10-03T08:44:50Z)
• ABC: Attention with Bounded-memory Control [67.40631793251997]
  We show that bounded-memory control (ABC) can be subsumed into one abstraction, attention with bounded-memory control (ABC) ABC reveals new, unexplored possibilities. First, it connects several efficient attention variants that would otherwise seem apart. Last, we present a new instance of ABC, which draws inspiration from existing ABC approaches, but replaces their memory-organizing functions with a learned, contextualized one.
  arXiv  Detail & Related papers  (2021-10-06T03:53:25Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.