PLASH: Provably Linear-Time Attention with Selective Higher-Order Feature Sketching

Yuwen Huang, Xiang PanICML 2026 · OpenReview

The "Achilles' heel" of the Transformer architecture is its self-attention mechanism. Because its computational cost grows quadratically ($O(N^2)$) with sequence length ($N$), processing massive contexts—like entire books, high-resolution images, or long genomic sequences—remains prohibitively expensive.

While hardware-aware optimizations like FlashAttention have pushed the boundaries of what is practical, the underlying algorithmic math still imposes a hard ceiling. Existing "efficient attention" methods typically attempt to solve this by restricting which tokens can interact (sparse attention) or by replacing the softmax operation with a linear approximation (kernel methods). However, these approaches often sacrifice the exactness of standard attention and, crucially, offer no way to measure how much error is introduced for a specific input.

To address this, researchers have introduced PLASH (Provably Linear-Time Attention with Selective Higher-Order Feature Sketching), a novel attention mechanism that breaks the quadratic scaling bottleneck while providing a mathematical guarantee of its reliability.

How PLASH Works: A Three-Stage Architecture

PLASH achieves linear-time complexity ($O(N)$) by compressing keys and values into learned prototypes, operating in three distinct stages:

  1. KV Compression (Stage I): Instead of attending to all $N$ keys and values, PLASH utilizes a learnable routing matrix to compress them into $M$ "prototypes," where $M$ is significantly smaller than $N$.
  2. Higher-Order Enrichment (Stage II): Simple compression often destroys vital token-to-token information, such as variance and covariance. PLASH restores this distinguishing power by injecting randomized polynomial features using a technique called TensorSketch. By squaring or tripling terms, the compressed prototypes recover the complex, higher-order "texture" of the original data.
  3. Exact Softmax Readout (Stage III): Finally, the model performs standard, exact scaled dot-product softmax attention from the original queries to these enriched prototypes.

Because the final stage uses a standard softmax interface, PLASH acts as a drop-in replacement for existing Transformer architectures and remains fully compatible with IO-aware kernels like FlashAttention.

The Game-Changer: A Per-Input Safety Certificate

The most significant breakthrough of PLASH is its randomness localization. Because the approximation randomness is strictly confined to Stage II, the authors were able to derive a mathematical "certificate."

During inference, the model calculates an upper bound on its own approximation error for every single forward pass. This allows researchers to mathematically bound how much the approximation deviates from standard softmax attention. If the error exceeds a safety threshold, a system could theoretically fall back to standard attention for that specific input. In the researchers' time-series forecasting experiments, this certificate held for 100% of the 35,058 test samples, proving the approximation remained consistently within guaranteed safety bounds.

Empirical Performance: NLP and Time-Series

The researchers evaluated PLASH across two highly distinct domains to demonstrate its versatility and scaling advantages:

  • Language Modeling: Training a Qwen3-4B model on the PG-19 dataset (long-form books) at sequence lengths up to 32,768 tokens, PLASH achieved the lowest training loss among all efficient-attention baselines (including Grouped-Query Attention and Longformer) at $N=16K$. Furthermore, at a sequence length of 32K, PLASH was 2.4x faster than standard FlashAttention-2.
  • Time-Series Forecasting: Using standard Informer protocol benchmarks, PLASH set new state-of-the-art scores on the Weather and ETTm1 datasets. This proves that the compression mechanism does not sacrifice the fine-grained numerical detail required for accurate forecasting.

Limitations and Future Directions

While PLASH offers a robust solution to the quadratic bottleneck, it introduces new considerations for model design:

  • Hyperparameter Sensitivity: Performance heavily depends on the number of prototypes ($M$) and the sketch size ($D_k$). Bigger is not universally better; these parameters require careful tuning for specific datasets. Interestingly, smaller sketch sizes can sometimes act as a form of "implicit regularization," opening avenues for future research into how approximation noise affects learning dynamics.
  • Causal Complexity: The paper introduces a "Block-Causal" version for autoregressive models (like GPT). However, implementing this efficiently while maintaining the error certificate is algorithmically more complex than the standard bidirectional version.

By combining linear scaling with rigorous mathematical reliability, PLASH represents a significant step forward in the quest to build efficient, trustworthy, long-context AI systems.

Summary updated

Abstract

Standard softmax attention scales quadratically with sequence length, which makes long-context training and inference expensive. We introduce PLASH, an attention block whose cost grows linearly in the number of keys. PLASH compresses the original keys and values into $M$ learned prototypes, where $M\in\mathbb{Z}_{>0}$ is much smaller than the number of keys. The compressed prototypes are then enriched with randomized polynomial features that recover inter-token information lost to compression. The output is computed by exact scaled dot-product softmax attention from each query to the enriched prototypes, so PLASH preserves the standard attention interface.The construction applies to self- and cross-attention. We prove sketch-error bounds for the enrichment step, a per-input certificate that upper-bounds the deviation from standard softmax attention on each forward pass, and a runtime bound linear in the number of queries and keys. Experiments on long-context language modeling (Qwen3-4B on PG-19) and time-series forecasting (ETT, ECL, Weather) show competitive accuracy and favorable scaling against efficient-attention baselines.
BibTeX
@inproceedings{huang2026plash,
  author = {Yuwen Huang and Xiang Pan},
  title = {{PLASH: Provably Linear-Time Attention with Selective Higher-Order Feature Sketching}},
  booktitle = {International Conference on Machine Learning},
  year = {2026},
  url = {https://openreview.net/forum?id=CYg2w0YKM4},
}
Figure