Two-Stage Clipping: Linear-Time Approximate and Exact Mixed-Norm Projections for Transformers

Michel Barlaud, Jean-Paul MarmoratarXiv 2026 · arXiv

TL;DR

This paper introduces Two-Stage Clipping (TSC), a new method for enforcing structured sparsity in Transformers. By replacing expensive proximal projection algorithms with a linear-time two-stage approach, the authors achieve up to a 540x speedup on GPUs while maintaining nearly identical accuracy and better reconstruction quality than standard pruning.

What Problem Does This Paper Address?

Transformer-based models (like LLMs) are computationally expensive. One way to make them faster is through structured sparsification—specifically, forcing entire columns of weight matrices to zero. This is hardware-friendly because it allows for actual memory and computation savings.

The mathematical tool used for this is the $\ell_{1,\infty}$ mixed-norm projection. However, existing "exact" methods (Proximal projections) are slow. They typically require sorting operations or complex heap-based updates, leading to a complexity of $\mathcal{O}(nm \log(nm))$. For the massive matrices in modern Transformers, this becomes a major bottleneck. The authors sought a way to achieve this sparsity in linear time ($\mathcal{O}(nm)$) without sacrificing model performance.

Methods

The authors propose Two-Stage Clipping (TSC), a framework inspired by bilevel optimization that breaks the projection into two distinct steps:

  1. Stage 1 (Budgeting): The algorithm calculates the $\ell_\infty$ norm of each column and projects this vector of norms onto an $\ell_1$ ball. This effectively decides how much "sparsity budget" to allocate to each column.
  2. Stage 2 (Clipping): The resulting values from Stage 1 are used as individual thresholds to clip the coefficients within each column.

Key Innovations: * Complexity: TSC runs in $\mathcal{O}(nm + m \log m)$, which simplifies to $\mathcal{O}(nm)$ for large matrices—making it linear relative to the number of parameters. * GPU-Friendliness: Unlike previous methods that rely on sequential sorting or irregular memory access, TSC uses parallel reductions and element-wise operations perfectly suited for CUDA architectures. * Unified Framework: The authors show this logic applies to both $\ell_{1,\infty}$ and $\ell_{1,2}$ norms.

Datasets

The researchers evaluated TSC across three distinct domains:

  • Synthetic Data: I.I.D. Gaussian matrices used to measure theoretical bounds and speedups.
  • Biomedical Classification:
    • PhysioNet PTB Diagnostic ECG Database: Heart failure diagnosis (14,550 recordings).
  • Sepsis Dataset: Early warning detection for sepsis (40,336 patients).
  • Image Reconstruction:
    • Kodak Image Dataset: Standard benchmark for image processing.
  • Flickr Dataset: Used for training the Transformer-based image autoencoder (473 high-resolution images).

Key Insights and Ideas

  • The "Exact" Surprise: The most striking theoretical finding is that for the $\ell_{1,2}$ norm, the TSC approach isn't just an approximation—it is mathematically identical to the exact Euclidean projection.
  • Negligible Error for $\ell_{1,\infty}$: While TSC is technically an approximation for $\ell_{1,\infty}$, the authors prove a theoretical bound on the discrepancy. In practice, the difference in classification accuracy between the "exact" slow method and the "fast" TSC method is less than 1%.
  • Sparsity Budgeting: The "aha" moment is treating sparsity as a resource allocation problem. By projecting column norms first, you identify which groups should be active before you ever touch the individual weights.
  • Norm Conservation: The paper establishes new "norm identities," showing that TSC preserves the global mixed-norm budget similarly to classical Euclidean projections.

Key Results

  • Massive Speedups: On an NVIDIA A100 GPU, TSC outperformed the standard proximal method by a factor of 143x to 540x as matrix sizes increased from 1,000 to 10,000.
  • Accuracy Parity: On ECG and Sepsis datasets, TSC achieved classification accuracy within 1% of the exact proximal approach while reaching high levels of sparsity (up to 90%+).
  • Superior to Pruning: In image reconstruction tasks (Kodak dataset), TSC-based methods preserved Peak Signal-to-Noise Ratio (PSNR) significantly better than classical structured pruning at the same sparsity levels.

Limitations and Future Work

  • Unstructured Sparsity: The authors note that extending TSC to the $\ell_{1,1}$ constraint is less effective because it induces unstructured sparsity and lacks the same tight theoretical error bounds.
  • Scaling to LLMs: While tested on lightweight Transformers for biomedical and image tasks, the paper leaves the evaluation of TSC on massive-scale LLMs (like Llama or GPT-scale) for future research.
  • Codec Comparison: The authors plan to compare TSC-based image compression against industry standards like JPEG 2000 to see if the learned sparsity translates to better real-world compression ratios.

Summary updated

Abstract

Large Language Models (LLMs) based on Transformer architectures have achieved remarkable performance across artificial intelligence tasks, but their computational cost remains a major bottleneck. Structured sparsification provides a promising approach to reducing this cost. In particular, $\ell_{1,\infty}$ projections can induce column-wise sparsity in model matrices, but existing proximal methods (Prox) typically require $\mathcal{O}(nm\log(nm))$ operations for matrices in $\mathbb{R}^{n\times m}$, limiting their computational and energy efficiency. In this paper, we introduce Two-Stage Clipping (TSC), an efficient structured sparsification operator inspired by bilevel optimization. Rather than solving a bilevel optimization problem in the strict sense, TSC decomposes the computation into two successive stages. First, group-level quantities are projected to allocate the global sparsity budget and identify active groups. Second, the resulting values are used as group-wise clipping thresholds for the matrix coefficients. For square attention matrices ($n \times n$), the complexity of our TSC method is $O(n^2)$, which is linear in the number of matrix coefficients. We establish a theoretical bound on the discrepancy between TSC and the exact proximal projection and show on synthetic data that the additional Euclidean approximation cost remains small in practice. Extensive benchmarks demonstrate substantial runtime improvements over proximal baselines and validate the theoretical norm identities underlying the proposed construction.
BibTeX
@misc{barlaud2026two,
  author = {Michel Barlaud and Jean-Paul Marmorat},
  title = {{Two-Stage Clipping: Linear-Time Approximate and Exact Mixed-Norm Projections for Transformers}},
  year = {2026},
  eprint = {2610.38598},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.38598},
}
Figure