Pith. sign in

REVIEW 11 cited by

Self-attention Does Not Need $O(n^2)$ Memory

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2112.05682 v3 pith:OHSEAYOV submitted 2021-12-10 cs.LG

Markus N. Rabe , Charles Staats This is my paper · ORCID
classification cs.LG
keywords memoryrequiresself-attentionattentionacceleratorsimplementationlengthsequence
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
abstract

We present a very simple algorithm for attention that requires $O(1)$ memory with respect to sequence length and an extension to self-attention that requires $O(\log n)$ memory. This is in contrast with the frequently stated belief that self-attention requires $O(n^2)$ memory. While the time complexity is still $O(n^2)$, device memory rather than compute capability is often the limiting factor on modern accelerators. Thus, reducing the memory requirements of attention allows processing of longer sequences than might otherwise be feasible. We provide a practical implementation for accelerators that requires $O(\sqrt{n})$ memory, is numerically stable, and is within a few percent of the runtime of the standard implementation of attention. We also demonstrate how to differentiate the function while remaining memory-efficient. For sequence length 16384, the memory overhead of self-attention is reduced by 59X for inference and by 32X for differentiation.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 11 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. OpenAlex reports about 18 citations worldwide. Full citation record

  1. Intrinsic and Triangulation-Agnostic Attention: A Simple and Powerful Approach for Learning on Meshes

    cs.GR 2026-07 conditional novelty 6.0 of 10

    Mass-weighted FEM attention on intrinsic mesh features is triangulation-agnostic and beats current mesh and point-cloud baselines on several geometry-learning benchmarks.

  2. Design-CP: Context Parallelism for Design of Protein Nanoparticles

    cs.LG 2026-07 conditional novelty 6.0 of 10

    Context-parallel inference for RFdiffusion 3 enables end-to-end all-atom design of large symmetric protein nanoparticles on multi-GPU hardware without retraining.

  3. Custom Algorithm-based Fault Tolerance for Attention Layers in Transformers

    cs.LG 2025-07 conditional novelty 6.0 of 10

    Flash-ABFT verifies an entire transformer attention layer with one fused checksum that covers softmax and all three matrix products, reporting 96-99% fault detection at under 5.3% area overhead.

  4. Local Representative Token Guided Merging for Text-to-Image Generation

    cs.CV 2025-07 conditional novelty 6.0 of 10

    ReToM merges tokens around a similarity-selected representative token in adaptive local windows, improving Stable Diffusion FID from 37.02 to 34.89 at comparable inference speed.

  5. Inter2Former: Dynamic Hybrid Attention for Efficient High-Precision Interactive

    cs.CV 2025-07 conditional novelty 6.0 of 10

    A new interactive segmentation decoder that routes computation to boundary regions, using binary quantization attention and mixture-of-experts, achieves state-of-the-art accuracy with CPU-friendly latency.

  6. HMAR: Efficient Hierarchical Masked Auto-Regressive Image Generation

    cs.CV 2025-06 conditional novelty 6.0 of 10

    HMAR is an image generator that builds each resolution scale from the previous scale and refines it with masked prediction, matching or improving ImageNet FID/IS versus VAR with faster training and inference.

  7. Low-Cost FlashAttention with Fused Exponential and Multiplication Hardware Operators

    cs.AR 2025-05 conditional novelty 6.0 of 10

    A fused exponential-multiplication hardware unit using logarithmic quantization and exponent adjustment reduces FlashAttention accelerator area by about 29% and power by about 18% without visible accuracy loss on GLUE.

  8. Scaling Laws for Forgetting during Finetuning with Pretraining Data Injection

    cs.LG 2025-02 conditional novelty 6.0 of 10

    Finetuning forgetting follows a multiplicative scaling law in model size, finetuning tokens, and injected pretraining fraction, with 1% injection nearly eliminating forgetting.

  9. Efficient Speculative Decoding for Llama at Scale: Challenges and Solutions

    cs.CL 2025-08 conditional novelty 5.0 of 10

    Meta reports EAGLE-based speculative decoding optimizations for Llama models, achieving state-of-the-art latency (about 4 ms/token for Llama4 Maverick) and 1.4-2.0x speedups for large batches.

  10. TransAct V2: Lifelong User Action Sequence Modeling on Pinterest Recommendation

    cs.IR 2025-06 conditional novelty 5.0 of 10

    TransAct V2 adds lifelong user sequences and a next-action loss to Pinterest's CTR model, reporting online gains of +6.35% repin volume and -12.80% hide volume.

  11. FLASH-D: FlashAttention with Hidden Softmax Division

    cs.LG 2025-05 conditional novelty 5.0 of 10

    FlashAttention can be rewritten exactly so each softmax weight is a sigmoid of a neighboring score difference plus a log-weight term, removing max subtraction and simplifying hardware.

Pith tools