How NaLaFormer Revives Linear Attention with Query‑Norm Awareness

Background

Transformer‑based models use self‑attention whose computational cost grows quadratically with the token length O(N^2). This makes processing high‑resolution images or long sequences infeasible on limited hardware.

Why Conventional Linear Attention Falls Short

Linear attention replaces the softmax over the query‑key dot‑product with a kernel‑based linear form, reducing the complexity to O(N). The linearisation introduces a normalisation step that divides the kernel output by the sum of all kernel values. Because the query norm appears both in the numerator and denominator, it is cancelled out, making the attention distribution insensitive to the magnitude of the query vector. Consequently, the sharpness (or “temperature”) of the attention cannot be modulated, leading to a consistent performance gap compared with softmax attention.

Query Norm as an Implicit Temperature

For a query vector q, write it as q = \|q\| \cdot \hat q where \hat q is the unit‑direction. In softmax attention the exponent contains \|q\|, so larger norms produce a steeper (lower‑entropy) distribution, while smaller norms yield a flatter distribution. This behaviour is analogous to a temperature parameter that automatically adapts to the importance of each query. Linear attention’s normalisation removes this dependence, a phenomenon the authors call “query‑norm‑unaware”.

NaLaFormer – Norm‑Aware Linear Attention Former

NaLaFormer restores the missing query‑norm control while keeping linear complexity through two complementary mechanisms:

Norm‑aware feature mapping : a query‑dependent sharpening function f(q) = (\|q\|)^{\alpha}\,\phi(q) (with exponent \alpha learned or fixed) re‑injects the query norm into the kernel. The exponent acts as a temperature: higher \|q\| increases the effective sharpness of the attention weights.

Cosine‑based directional similarity : instead of enforcing non‑negativity with ReLU or 1+ELU, the similarity between query and key is computed as the cosine of their directions,

cos(\theta_{q,k}) = \frac{\langle \hat q, \hat k \rangle}{\|\hat q\|\|\hat k\|}

. Cosine similarity is naturally bounded in [-1,1] and can be shifted to a non‑negative range (e.g., (1+cos)/2) without discarding negative components, preserving sign information that is valuable for modeling complex relationships.

The overall attention weight for token i attending to token j becomes:

w_{ij} = \frac{ (\|q_i\|)^{\alpha} \cdot \text{cos}(\hat q_i, \hat k_j) }{ \sum_{j'} (\|q_i\|)^{\alpha} \cdot \text{cos}(\hat q_i, \hat k_{j'}) }

Because the numerator and denominator share the same query‑norm factor, it cancels out only after the sharpening exponent is applied, leaving a controllable temperature effect while the denominator still enables linear‑time computation via kernel decomposition.

Implementation Details

Feature mapping uses a kernel \phi(x) = \exp(\beta x) with a learnable scalar \beta. The query‑norm term is raised to a power \alpha (default \alpha=1) and multiplied with the kernel output.

Key vectors are processed with the same kernel but without the norm‑dependent exponent, ensuring that the linear‑time reduction \sum_j \phi(k_j) can be pre‑computed.

Cosine similarity is implemented as a dot product of normalised vectors, followed by a shift (1+cos)/2 to guarantee non‑negativity while retaining directional information.

All operations are batched and compatible with existing Transformer libraries; the additional cost is a few element‑wise multiplications, preserving O(N) complexity.

Comprehensive Multimodal Evaluation

NaLaFormer was benchmarked on image classification, object detection, semantic segmentation, super‑resolution, diffusion models, long‑range sequence modeling, and language modeling.

ImageNet‑1K : up to 7.5 % absolute accuracy gain over strong linear‑attention baselines.

Semantic segmentation : 46.9 % mIoU on ADE20K (+4.7 % over comparable models) and 82.5 % mIoU on Cityscapes.

Super‑resolution : peak memory reduced from 69 GB to 5.3 GB (‑92.3 %) and latency from 195 ms to 124 ms (‑36.4 %) with no degradation in PSNR/SSIM.

Long‑range sequence modeling : 61.2 % average accuracy on the Long‑Range Arena, surpassing all other linear‑attention variants.

Language modeling : a 340 M‑parameter model trained from scratch outperformed strong baselines such as Mamba on commonsense reasoning benchmarks.

Visual comparisons (see figures) show clearer object boundaries and richer structural details compared with SegNeXt, highlighting practical benefits for tasks like autonomous driving.

Overall, NaLaFormer bridges the efficiency‑performance gap of linear attention, offering a scalable solution for high‑resolution vision and long‑sequence language tasks while retaining linear computational complexity.

Reference: https://arxiv.org/pdf/2506.21137