Causal Masking Constraints in Sub-Quadratic Attention

21 concepts19 papers1 proposal

Standard self-attention is notoriously expensive. Because it computes pairwise interactions between every single token in a sequence, its computational and memory costs scale quadratically ($O(N^2)$) with the sequence length $N$. To scale Transformers to longer contexts, a massive body of research has focused on sub-quadratic alternatives: linear attention, kernel sketching, structured matrices, and sparse approximations.

However, when these efficiency gains are applied to autoregressive large language models (LLMs), they hit a fundamental mathematical roadblock: causal masking. Autoregressive generation requires that token $i$ can only attend to preceding tokens $j \le i$. This imposes a strict lower-triangular constraint on the attention matrix.

While applying a triangular mask to a fully materialized $N \times N$ matrix is trivial, enforcing it within sub-quadratic primitives is incredibly difficult. Across various optimization strategies, enforcing causality frequently breaks the underlying mathematics or inadvertently re-introduces the very quadratic complexity researchers sought to avoid.


Why Matrix Reordering Breaks Down

The most common way to achieve linear ($O(N)$) complexity is to change the order of matrix multiplications. Standard attention computes the query-key interaction first:

$$\text{Attention}(Q, K, V) = \text{softmax}(QK^T)V$$

Linear attention mechanisms—such as those explored in Efficient Attention: Attention with Linear Complexities or the Galerkin Transformer analyzed by Shuhao Cao in Choose a Transformer: Fourier or Galerkin—remove the softmax normalization or replace it with a feature map $\phi(\cdot)$, allowing the associative property of matrix multiplication to bypass the $N \times N$ bottleneck:

$$\text{LinearAttention}(Q, K, V) = \phi(Q) \left( \phi(K)^T V \right)$$

By computing the global context matrix $D = \phi(K)^T V$ first, the computational complexity drops to linear because $D$ has a fixed size of $d \times d$ (where $d$ is the feature dimension).

Standard Attention:  (Q @ K.T) @ V  --> Computes intermediate [N x N] matrix
Linear Attention:    Q @ (K.T @ V)  --> Computes intermediate [d x d] matrix

The Intuition of the Failure

The global context matrix $D$ is constructed by summing up the key-value products across the entire sequence length: $D = \sum_{t=1}^N \phi(k_t) v_t^T$. Because this summation includes every token up to $N$, the resulting matrix $D$ contains information from the future.

When a query at an early position $i$ multiplies $D$, it inherently absorbs information from tokens at positions $j > i$. As noted by Zhuoran Shen et al. in Efficient Attention: Attention with Linear Complexities, preventing this future information leakage within a globally aggregated scheme without expanding the operations back into a quadratic space remains an open challenge.


The Destruction of Low-Rank and Kernel Properties

Another prominent branch of sub-quadratic attention relies on numerical linear algebra to approximate the full softmax matrix. These include randomized importance sampling, such as LARA developed by Lin Zheng et al. in Linear Complexity Randomized Self-attention Mechanism, polynomial kernel sketching in PolySketchFormer: Fast Transformers via Sketching Polynomial Kernels, and sublinear quantum sampling algorithms like those proposed by Zhao Song et al. in Sublinear Time Quantum Algorithm for Attention Approximation.

The Intuition of the Failure

These methods operate on a core assumption: the full, unmasked attention matrix is globally well-behaved, low-rank, or smooth enough to be estimated from a few strategic samples or projections.

Unmasked Matrix (Smooth/Low-Rank)      Causally Masked Matrix (Sharp Discontinuity)
       [ *  *  *  * ]                          [ *  0  0  0 ]
       [ *  *  *  * ]             -->          [ *  *  0  0 ]
       [ *  *  *  * ]                          [ *  *  *  0 ]
       [ *  *  *  * ]                          [ *  *  *  * ]

Causal masking shatters this assumption. By zeroing out the upper triangle, it introduces a sharp, discontinuous step function directly along the main diagonal.

As mathematically demonstrated by Yingyu Liang et al. in Multi-Layer Transformers Gradient Can be Approximated in Almost Linear Time, this hard truncation completely disrupts the low-rank structure of the attention matrix. Because the mathematical guarantees of sketching and randomized sampling rely on having simultaneous, unhindered access to the full sequence properties, enforcing a directional constraint means the algorithms must find ways to track the mask without reconstructing the quadratic interaction space (PolySketchFormer).


The Quadratic Reversion in Structured Matrices and Convolutions

To bypass the limitations of pure linear attention, some architectures replace standard attention entirely with hardware-efficient algebraic primitives. For example, Monarch Mixer and MonarchAttention use sub-quadratic block-factorized Monarch matrices. Similarly, CAT, introduced by Yoshihiro Yamada in CAT: Circular-Convolutional Attention for Sub-Quadratic Transformers, maps global softmax attention to circular convolutions computed via the Fast Fourier Transform (FFT) in $O(N \log N)$ time.

The Intuition of the Failure

These methods achieve speed by operating in a highly structured or transformed domain. Circular convolutions via FFT assume shift-invariance across the entire sequence. Kronecker-factored structures, such as those used by Soroush Omranpour et al. in Higher Order Transformers: Efficient Attention Mechanism for Tensor Structured Data, rely on symmetric multi-mode factorizations.

A causal mask is fundamentally position-dependent and asymmetric; it breaks shift-invariance and cross-dimensional symmetry. When you attempt to force a lower-triangular constraint onto a circular convolution or a Kronecker product, the clean algebraic factorization collapses.

As detailed in both Monarch Mixer and CAT, isolating the causal components within these transformed spaces typically requires unpacking or modifying the operations in a way that reverts the computational complexity right back to quadratic levels ($O(N^2)$).


Sparsity and Hashing Mismatches

A final strategy involves learning sparse attention patterns on the fly, ensuring tokens only look at a subset of highly relevant keys. Learning-to-Hash Attention (LHA), proposed by Zhiqing Sun et al. in Sparse Attention with Learning to Hash, learns separate hashing functions to bucket queries and keys, while Zhaodong Chen et al. in Dynamic N: M Fine-grained Structured Sparse Attention Mechanism design custom CUDA kernels to dynamically prune attention weights.

The bottleneck here is a mismatch between optimization metrics and physical hardware execution. Hashing and pruning strategies are typically optimized for bidirectional contexts, where the similarity between a query and a key is independent of their sequence order.

When a causal mask is applied, many of the learned hash buckets or pruned blocks end up falling into the forbidden upper-triangular region. As argued by the authors of LHA and Dfss, adapting these dynamic patterns to respect sequential dependencies requires complex indexing, sorting, and memory access overheads that severely diminish their theoretical hardware speedups.

Summary of the Dilemma

The tension between efficiency and causality can be summarized as follows:

Attention Type Sub-Quadratic Mechanism Why Causal Masking Breaks It
Linear Attention Reorders operations to $Q(K^T V)$ $K^T V$ aggregates globally, leaking future tokens to past queries.
Kernel / Sketching Assumes global low-rank or smooth matrix Hard triangular truncation introduces a sharp discontinuity that spikes the matrix rank.
Structured / Convolutional Operates in symmetric or frequency domains Causal constraints break shift-invariance, forcing a reversion to $O(N^2)$ to unpack.
Sparse / Hashing Clusters queries and keys dynamically Learned buckets and hardware kernels waste capacity on forbidden upper-triangular regions.

Key Foundational Work

Nyströmformer: A Nyström-based Algorithm for Approximating Self-Attention (2021) — contributed 2 concept elements to this direction.
Efficient Attention: Attention with Linear Complexities (2021) — contributed 1 concept elements to this direction.
LittleBird: Efficient Faster & Longer Transformer for Question Answering (2022) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_causal_masking_constraints_ac81cd52,
  title = {causal masking constraints},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/causal-masking-constraints/rdr_ac81cd52fc9846999378957fff6f1d21},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_causal_masking_constraints_ac81cd52_v1,
  title = {causal masking constraints},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/causal-masking-constraints/rdr_ac81cd52fc9846999378957fff6f1d21/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake