A Parametric Linear Conic Projection for Structured Sparse Attention

Michel Barlaud, Clement Genninasca, Maxime Zanella, Benoit Macq, Benoit LegatarXiv 2026 · arXiv

TL;DR

This paper introduces the Cone Alignment Index (CAI), a novel geometric framework for inducing structured sparsity in Transformer attention matrices. By projecting weights onto the boundary of a Lorentz cone, the authors develop efficient, closed-form algorithms (PLCP and PECP) that achieve up to 90% attention sparsity with minimal accuracy loss, outperforming existing heuristic and projection-based methods.

What Problem Does This Paper Address?

As Large Language Models (LLMs) grow, the quadratic cost of dense attention matrices becomes a massive bottleneck for memory and computation. While "sparsity" is the obvious solution, implementing it effectively is hard.

Most current approaches fall into two camps:

  1. Heuristic Pruning: Methods like magnitude pruning are effective but often lack theoretical guarantees and produce "unstructured" patterns that are hard for hardware to accelerate.
  2. Fixed Patterns: Architectures like BigBird use predefined sparse masks (e.g., sliding windows), which are hardware-friendly but don't adapt to the actual data.

The authors seek a "third way": a principled, geometric formulation for structured sparsity that is scale-invariant, computationally efficient, and provides strong optimization guarantees.

Methods

The core of the paper is the Cone Alignment Index (CAI). Mathematically, it measures how well a vector aligns with the diagonal axis in a non-negative space. Geometrically, it defines a Lorentz cone.

The authors propose two complementary projection methods to enforce sparsity:

  • Parametric Euclidean Conic Projection (PECP): The exact Euclidean projection of a point onto the cone's boundary.
  • Parametric Linear Conic Projection (PLCP): An efficient, closed-form affine approximation.

A key theoretical contribution is proving that PLCP and PECP are collinear. They identify the exact same "active support" (the set of non-zero weights) and differ only by a radial scaling factor. This allows researchers to use the faster PLCP without sacrificing the structural quality of the exact Euclidean projection.

To handle large matrices, they use a bilevel optimization strategy. Instead of sparsifying every individual weight, they sparsify the norms of columns or rows. This naturally generates hardware-friendly structured patterns (like entire columns being zeroed out) while keeping the computational complexity near-linear relative to the number of active elements.

Datasets

The authors evaluated their framework on:

  • Synthetic Data: Gaussian and uniform distributions were used to validate the probabilistic analysis of the CAI score.
  • GLUE Benchmark: Including SST-2 (sentiment), QNLI (natural language inference), QQP (question pairs), and MNLI (multi-genre inference).
  • SuperGLUE: Specifically the WiC (Word-in-Context) task.

Key Insights and Ideas

  • The Geometry of Sparsity: By treating sparsity as a conic constraint, the authors move away from "trim-and-fit" heuristics toward a rigorous projection framework.
  • Scale Invariance: Many optimization problems are unaffected by global rescaling. CAI is inherently scale-invariant, meaning the sparsity pattern remains consistent even if the input values are scaled up or down.
  • The High-Sparsity Regime: The paper provides a probabilistic proof showing that in high-sparsity settings, samples naturally tend to lie within the convex cone, making the projection onto the boundary highly stable.
  • Collinearity is a "Free Lunch": The discovery that the fast linear approximation (PLCP) yields the same active support as the exact Euclidean projection (PECP) is a major win for practical implementation.
Figure 1: CAI score asymptotic distribution.

Key Results

  • Superior Trade-offs: On the SST-2 benchmark, PLCP delivered a 2% accuracy gain over competitors at high sparsity. On the more challenging WiC benchmark, the gain jumped to 10%.
  • Extreme Sparsity: The model maintains high performance even at 90% attention sparsity, consistently outperforming GSP, structured pruning, and the BigBird baseline.
  • Computational Speedup: On NVIDIA A100 GPUs, PLCP achieved a quadratic speedup over GSP-Hybrid. Its complexity is essentially linear in the size of the active support, making it highly scalable for massive matrices.
  • Stability: The method showed comparable or better stability across different random seeds compared to standard pruning techniques.

Limitations and Future Work

  • Linguistic Impact: While the quantitative results are strong, the authors note that a deeper "linguistic analysis" is needed. Preliminary results suggest the method removes punctuation and function words first, but more work is required to see if it preserves complex syntactic dependencies.
  • Beyond Attention: The current work focuses on attention matrices. The authors suggest extending this to general weight matrices and Mixture-of-Experts (MoE) architectures, where structured sparsity could significantly reduce the memory footprint of "expert" weights.
  • Hardware Integration: While the patterns are "hardware-friendly," the paper does not detail a custom kernel implementation to fully exploit these masks for maximum wall-clock inference speedups.

Summary updated

Abstract

In this paper, we introduce the Cone Alignment Index (CAI), a scale-invariant sparsity measure associated with a Lorentz-cone geometry. We provide a probabilistic analysis of the distribution of the CAI score, including a general theorem and explicit corollaries for Gaussian and uniform distributions. As a consequence, we show that, in the high-sparsity regime, the probability that the samples lie within the convex cone tends to one. Building upon this formulation, we derive two complementary projections: the \emph{Parametric Linear Conic Projection} (PLCP), an efficient closed-form approximation, and the \emph{Parametric Euclidean Conic Projection} (PECP), the exact Euclidean projection onto the cone boundary. Our analysis establishes several fundamental theoretical properties. We prove that PLCP and PECP are collinear, differ only by a positive radial scaling factor, and induce exactly the same sparsity threshold, thereby preserving an identical active support. Furthermore, we derive a support-identification theorem showing that, for any prescribed sparsity level $l<n$, the number of coefficients discarded at each iteration is theoretically controlled. Building on this theoretical foundation, we develop a bilevel PLCP framework for structured matrix sparsification. The proposed method naturally generates hardware-friendly structured sparsity patterns, including row-wise, column-wise, and diagonal masks, making it particularly well suited for accelerating Transformer attention mechanisms.
BibTeX
@misc{barlaud2026parametric,
  author = {Michel Barlaud and Clement Genninasca and Maxime Zanella and Benoit Macq and Benoit Legat},
  title = {{A Parametric Linear Conic Projection for Structured Sparse Attention}},
  year = {2026},
  eprint = {2611.04479},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.04479},
}
Figure