# Plug-and-play linear attention with provable guarantees for training-free image restoration

arXiv: https://arxiv.org/abs/2506.08520 · HTML: https://mlsanity.com/paper/2506.08520/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 14 of its 22 references that are in the map.
- First posted on arXiv 10 Jun 2025.

## Builds on (most cited first, 14 of 14)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Swin Transformer: Hierarchical Vision Transformer using Shifted Windows](https://mlsanity.com/paper/2103.14030/) (2021)
- [FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness](https://mlsanity.com/paper/2205.14135/) (2022)
- [A ConvNet for the 2020s](https://mlsanity.com/paper/2201.03545/) (2022)
- [SwinIR: Image Restoration Using Swin Transformer](https://mlsanity.com/paper/2108.10257/) (2021)
- [Rethinking Attention with Performers](https://mlsanity.com/paper/2009.14794/) (2020)
- [Linformer: Self-Attention with Linear Complexity](https://mlsanity.com/paper/2006.04768/) (2020)
- [Uformer: A General U-Shaped Transformer for Image Restoration](https://mlsanity.com/paper/2106.03106/) (2021)
- [Nystr"omformer: A Nystr"om-Based Algorithm for Approximating Self-Attention](https://mlsanity.com/paper/2102.03902/) (2021)
- [Axial Attention in Multidimensional Transformers](https://mlsanity.com/paper/1912.12180/) (2019)
- [Vision Transformers for Single Image Dehazing](https://mlsanity.com/paper/2204.03883/) (2022)
- [The Ninth NTIRE 2024 Efficient Super-Resolution Challenge Report](https://mlsanity.com/paper/2404.10343/) (2024)
- [Improving CUR Matrix Decomposition and the Nystr"om Approximation via Adaptive Sampling](https://mlsanity.com/paper/1303.4207/) (2013)
- [SparseFormer: Sparse Visual Recognition via Limited Latent Tokens](https://mlsanity.com/paper/2304.03768/) (2023)

## Abstract (arXiv)

Multi-head self-attention (MHSA) is a key building block in modern vision Transformers, yet its quadratic complexity in the number of tokens remains a major bottleneck for real-time and resource-constrained deployment. We present PnP-Nystra, a training-free Nystr"om-based linear attention module designed as a plug-and-play replacement for MHSA in pretrained image restoration Transformers, with provable kernel approximation error guarantees. PnP-Nystra integrates directly into window-based architectures such as SwinIR, Uformer, and Dehazeformer, yielding efficient inference without finetuning. Across denoising, deblurring, dehazing, and super-resolution on images, PnP-Nystra delivers 1.8--3.6× speedups on an NVIDIA RTX 4090 GPU and 1.8--7× speedups on CPU inference. Compared with the strongest training-free linear-attention baselines we evaluate, our method incurs the smallest quality drop and stays closest to the original model's outputs.