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

Michel Barlaud; Jean-Paul Marmorat

cs.LGOct 28, 2026

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

Authors: Michel Barlaud, Jean-Paul Marmorat

Organizations: I3S Laboratory, CNRS, Universite Côte d’Azur, France · Ecole des Mines, PSL, France.

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.

Figures & tables

Method	Complexity	Main operations
Original Bejar et al	$O(mn\log(mn))$	Sorting and threshold updates
Perez et al. (Algorithm 2)	$O(mn+J\log(mn))$	Inverse ordering and heaps
Proposed TSC	$O(mn)$	$\ell_{1}$ projection and clipping

Table 1: Computational complexity of different

\ell_{1,\infty}

projection methods.

Panel of Figure 1 — Figure 1: Relative difference between the classical Euclidean projection $P_{\eta}^{1,\infty}$ and the proposed two-stage clipping operator $TSC_{\eta}^{1,\infty}$ for i.i.d. Gaussian matrices, as a function of the size and the sparsity.

Panel of Figure 2 — Figure 2: Comparison of two-stage Clipping versus proximal. U: Processing time in PyTorch using an NVIDIA A100 GPU as a function of the size of the square matrix $n\times n$ . Bottom: Logarithm fitting of the speedup of our two-stage clipping operator versus the proximal algorithm.

Figure 3: ECG dataset. Proximal projection versus two-stage $\ell_{1,\infty}$ clipping operator — sparsity–accuracy trade-off.

Figure 4: SEPSIS dataset. Proximal projection versus two-stage $\ell_{1,\infty}$ clipping operator — sparsity–accuracy trade-off.

Figure 5: Kodak dataset. Two-stage $\ell_{1,\infty}$ clipping operator versus Two-stage $\ell_{1,2}$ clipping operator and structured pruning: sparsity–Delta-PSNR trade-off.

Figure 6: Training on Flickr and testing on Kodak dataset. Two-stage $\ell_{1,\infty}$ clipping operator versus Two-stage $\ell_{1,2}$ clipping operator and structured pruning: sparsity–Delta-PSNR trade-off.

Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

Architecture parameter	Value
Input image channels	3 (RGB)
Training image size	$256\times 256$
Patch size	$16\times 16$
Number of tokens	256
Embedding dimension	256
Number of Transformer layers	4

Appendix

Table 2: Transformer architecture shared by the Kodak-to-Kodak and Flickr-to-Kodak experiments.

Panel of Figure 7 — Figure 7: Vertical architecture of the attention sparsity–reconstruction trade-off (ASRT) evaluation framework. Attention sparsification is performed using TSC or structured pruning within the Transformer encoder. Reconstruction quality is evaluated on the Kodak dataset using PSNR and SSIM relative to the dense baseline. No entropy coding is considered.

Structured Sparsity

Structured sparsity organizes zeros into meaningful groups, blocks, channels, or patterns to simplify models and computation.

See all 62 papers

Mar 24, 2026

Sparser, Faster, Lighter Transformer Language Models

Scaling autoregressive large language models (LLMs) has driven unprecedented progress but comes with vast computational costs. In this work, we tackle these costs by leveraging unstructured sparsity within an LLM's feedforward layers, the components accounting for most of the model parameters and execution FLOPs. To achieve this, we introduce a new sparse packing format and a set of CUDA kernels designed to seamlessly integrate with the optimized execution pipelines of modern GPUs, enabling efficient sparse computation during LLM inference and training. To substantiate our gains, we provide a quantitative study of LLM sparsity, demonstrating that simple L1 regularization can induce over 99% sparsity with negligible impact on downstream performance. When paired with our kernels, we show that these sparsity levels translate into substantial throughput, energy efficiency, and memory usage benefits that increase with model scale. We will release all code and kernels under an open-source license to promote adoption and accelerate research toward establishing sparsity as a practical axis for improving the efficiency and scalability of modern foundation models.

Edoardo Cetin, Stefano Peluchetti, Emilio Castillo +3

Sakana AI · NVIDIA

LLM Inference Acceleration Sparse Neural Networks LLM Compression

Ask PDF

Oct 7, 2026

Sparse Attention Is Matrix Approximation, Not Choosing from a Bag of Values

Large Language Models (LLMs) achieve strong performance across many domains, but their efficiency is limited by the quadratic cost of attention with respect to prompt length. Sparse attention reduces this cost by retaining only a small fraction of query-key interactions to approximate the full attention matrix. However, existing methods are trapped in a mathematically wrong view: they simply keep large scalar entries or high-mass regions of the attention matrix. This treats the attention matrix as a bag of values, ignoring that it is used as a structured matrix whose entries jointly determine the attention output through multiplication with value vectors. We argue that this is the core conceptual issue: sparse attention should be formulated as matrix approximation, not as blindly choosing the largest values from a bag of entries. Based on this view, we propose Matrix Approximation Sparse Attention (MASA). MASA replaces raw attention-mass ranking with a closed-form score that measures how much each sparse unit reduces matrix-product approximation error. As a theory-grounded plug-in correction, MASA can be added to existing sparse attention frameworks without changing their sparse kernels or budgets. Extensive experiments across multiple sparse attention methods, benchmarks, and LLM backbones show consistent accuracy gains, supporting both MASA and the matrix-approximation view of sparse attention.

Fang Wan, Xufeng Liu, Fan Li +1

Stony Brook University · Duke University

Sparse Attention Efficient Attention Attention Mechanisms Attention Approximation LLM Inference Acceleration

Ask PDF

Mar 2, 2026

3BASiL: An Algorithmic Framework for Sparse plus Low-Rank Compression of LLMs

Sparse plus Low-Rank

(\mathbf{S} + \mathbf{LR})

decomposition of Large Language Models (LLMs) has emerged as a promising direction in model compression, aiming to decompose pre-trained model weights into a sum of sparse and low-rank matrices

(\mathbf{W} \approx \mathbf{S} + \mathbf{LR})

. Despite recent progress, existing methods often suffer from substantial performance degradation compared to dense models. In this work, we introduce 3BASiL-TM, an efficient one-shot post-training method for

(\mathbf{S} + \mathbf{LR})

decomposition of LLMs that addresses this gap. Our approach first introduces a novel 3-Block Alternating Direction Method of Multipliers (ADMM) method, termed 3BASiL, to minimize the layer-wise reconstruction error with convergence guarantees. We then design an efficient transformer-matching (TM) refinement step that jointly optimizes the sparse and low-rank components across transformer layers. This step minimizes a novel memory-efficient loss that aligns outputs at the transformer level. Notably, the TM procedure is universal as it can enhance any

(\mathbf{S} + \mathbf{LR})

decomposition, including pure sparsity. Our numerical experiments show that 3BASiL-TM reduces the WikiText2 perplexity gap relative to dense LLaMA-8B model by over 30% under a (2:4 Sparse + 64 LR) configuration, compared to prior methods. Moreover, our method achieves over 2.5x faster compression runtime on an A100 GPU compared to SOTA

(\mathbf{S} + \mathbf{LR})

method. Our code is available at https://github.com/mazumder-lab/3BASiL.

Mehdi Makni, Xiang Meng, Rahul Mazumder

Operations Research Center Massachusetts Institute of Technology

LLM Compression Low-Rank Compression Alternating Direction Method of Multipliers

Ask PDF

Abstract

Structured Sparsity

Explore similar work

Sparser, Faster, Lighter Transformer Language Models

Sparse Attention Is Matrix Approximation, Not Choosing from a Bag of Values

3BASiL: An Algorithmic Framework for Sparse plus Low-Rank Compression of LLMs