S 3 : Structured Sparsity Specification
Ayoub Ghriss · 2026
Read S 3 : Structured Sparsity Specification by Ayoub Ghriss (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-11315.txt.
Introduction
Ghriss introduces S3, the Structured Sparsity Specification, an algebraic framework for setting up and using structured sparse patterns in tensors. Sparsity is set through a View that reshapes the tensor, a Block that defines the atomic pruning unit, and a Scope that decides where sparsity applies. Coupling across tensors allows coordinated pruning. The point is one language for many pruning styles, from fine N:M patterns to coarse channel cuts. Built entirely on S3, structured OBS and OBD implementations beat established second-order rules on output rebuilds across common setups.
Catalog record
| CREATOR | Ayoub Ghriss |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 61764 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.11315
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
S 3 : Structured Sparsity Specification Ayoub Ghriss Abstract We introduce the Structured Sparsity Specification (S 3 ), an algebraic framework for defining, composing, and implementing structured sparse patterns. S 3 specifies sparsity through three components: a View that reshapes the tensor via layout composition, a Block specification that defines the atomic pruning unit, and the sparsity decision Scope . Both Block and Scope support Coupling across tensors for coordinated sparsification. S 3 enables precise specification of diverse sparsity structures, from fine-grained N:M patterns to coarse channel pruning, and integrates seamlessly with Optimal Brain Damage (OBD) and Surgeon (OBS). We formalize the framework mathematically, demonstrate its expressiveness on canonical patterns, and validate it experimentally via structured OBS and OBD implementations 1 1 1 https://sparsekit.readthedocs.io built entirely on S 3 , which surpasses well-established second order heuristics on output reconstruction across common configurations. 1 Introduction (a) NVIDIA Ampere tensor cores partition the left multiplicand ( 16\times 16 ) and right multiplicand ( 16\times 8 ) so that each thread-group of 4 threads provides one row/column of the left/right operand. (b) By structuring the sparsity so that each thread-group handles the same exact number of rows per 32\times 16 left multiplicand, we design a new sparsity pattern that is hardware-native without the need for special hardware support. Figure 1: S 3 can target low-level hardware patterns to avoid any slowdowns due to memory access conflicts. For m16n8k16 matrix multiplication patterns, we can target the thread-group as one block. Quantization has become the dominant approach to compressing large neural networks, delivering substantial inference savings with minimal accuracy loss. Sparsity offers a complementary axis of compression that can compose with quantization for compounded gains, yet its practical impact has been limited. Unstructured pruning achieves high theoretical compression ratios, but its irregular memory access patterns and workload imbalance often negate these benefits on modern hardware ( 9 ) . Structured sparsity, which removes coherent blocks of parameters such as channels, filters, or attention heads, is more hardware-friendly but traditionally lacks the flexibility to express complex patterns, limiting its applicability. Moreover, the current landscape of structured sparsity is fragmented with the "structure" qualification used to describe specific patterns: N:M methods target specific hardware (NVIDIA sparse tensor cores), block sparsity aligns with matrix multiplication tiles, and channel pruning operates at the semantic level of neural network layers. Each paradigm requires its own pruning implementation, and no common formalism exists to relate them or to develop algorithms that generalize across patterns. We address this gap by introducing Structured Sparsity Specification (S 3 ), a framework that unifies diverse sparsity patterns under a common algebraic formalism, composes simple specifications into complex hierarchical structures, and integrates directly with second-order pruning criteria through well-defined index mappings. Our contributions: • A formal specification language based on layout algebra that can express any hyperrectangular sparsity pattern through View, Block, and Scope primitives. • Structured extensions of OBD and OBS (S-OBD, S-OBS) with derived blockwise saliency scores, optimal weight updates, and efficient Schur complement maintenance. • Experimental validation showing that S-OBS implementation, with specification-agnostic code, outperforms SparseGPT by 16–20% across four distinct sparsity configurations. 2 Related Work Neural network pruning has evolved from simple magnitude-based methods ( 7 ) to principled second-order approaches. Optimal Brain Damage (OBD) ( 10 ) uses diagonal Hessian approximations to score parameter importance, while Optimal Brain Surgeon (OBS) ( 8 ) incorporates the full inverse Hessian and derives optimal weight updates that compensate for removed parameters. The Lottery Ticket Hypothesis ( 4 ) provided further motivation by showing that dense networks contain sparse subnetworks matching full accuracy, suggesting that most parameters are redundant. For large language models, where retraining is prohibitively expensive, Wanda ( 20 ) and SparseGPT ( 5 ) adapt OBD and OBS principles to the zero-shot setting with efficient Hessian approximations. A parallel line of work has explored structured sparsity constraints that can be exploited by hardware. N:M sparsity enforces exactly N non-zero values per M consecutive elements, directly mapping to NVIDIA’s sparse tensor cores ( 17 ) . Block sparsity zeros entire contiguous blocks, enabling efficient dense operations on the surviving blocks ( 6 ) . Channel and filter pruning remove entire convolutional channels or attention heads ( 11 ; 15 ) . Early work on structured sparse coding ( 12 ) used sums of \ell_{\infty} norms ( 21 ; 1 ; 13 ) to enforce scope-level consistency, establishing a principled framework to design arbitrary patterns that can be adapted to today’s hardware-aligned structures. Despite this variety, each pattern typically requires its own pruning implementation; S 3 provides a unified specification that covers all of these as special cases. Dynamic sparse training ( 16 ; 3 ) takes a different approach: instead of pruning a trained model, it maintains a fixed sparsity budget throughout training while periodically updating the mask. These methods demonstrate that static masks are suboptimal, but the resulting patterns are unstructured and cannot leverage hardware-accelerated sparsity formats. We discuss how S 3 can serve as a structural backbone for dynamic sparse training. Our sparsity formalism was inspired by the CuTe library ( 18 ) , which implements a layout algebra ( 2 ) of shape-stride pairs with composition operations for GPU kernel design. We extend this representation from the domain of memory addressing to sparsity specification, using layout composition to define views over dense tensors that expose block and scope structure. 3 Preliminaries Layout Algebra ( 18 ) ; see 2 for a comprehensive treatment provides a rigorous tensor layout formalism that we leverage in our framework. A layout \mathcal{L}={\bm{s}}:{\bm{d}} with shape {\bm{s}}\in\mathbb{N}^{n} and stride {\bm{d}}\in\mathbb{Z}^{n} is a mapping from a logical coordinate space to linear memory indices. Definition 1 (Layout Function) . For a layout \mathcal{L}={\bm{s}}:{\bm{d}} with n dimensions, the index function \phi_{\mathcal{L}}:\mathbb{Z}^{n}\to\mathbb{Z} is: \phi_{\mathcal{L}}(i_{0},\ldots,i_{n-1})=\sum_{k=0}^{n-1}i_{k}\cdot d_{k} (1) where 0\leq i_{k}<s_{k} for all k . Definition 2 (Layout Size) . The size of layout \mathcal{L} is defined as: |\mathcal{L}|=\prod_{k=0}^{n-1}s_{k} (2) Definition 3 (Layout Cosize) . The cosize represents the memory footprint: \text{cosize}(\mathcal{L})=\max_{{\bm{i}}\in\text{dom}(\mathcal{L})}\phi_{\mathcal{L}}({\bm{i}})+1=\sum_{k=0}^{n-1}(s_{k}-1)\cdot d_{k}+1 (3) Definition 4 (Layout Composition) . Given layouts \mathcal{A}={\bm{s}}_{A}:{\bm{d}}_{A} and \mathcal{B}={\bm{s}}_{B}:{\bm{d}}_{B} where |\mathcal{A}|=|\mathcal{B}| , the composition \mathcal{A}\circ\mathcal{B} produces a new layout where \mathcal{B} indexes into the logical space of \mathcal{A} : \phi_{\mathcal{A}\circ\mathcal{B}}({\bm{j}})=\phi_{\mathcal{A}}(\phi_{\mathcal{B}}^{-1}({\bm{j}})) (4) The key takeaway is that any tensor can be described by a layout \mathcal{L}={\bm{s}}:{\bm{d}} that may itself be the composition or division of simpler layouts. This compositionality is central to S 3 : it allows us to factor the View out of the Block and Scope specifications. 4 The S 3 Framework (a) 2:4 Sparsity. \mathcal{V}\!=\!\mathcal{L}_{\text{phys}} , {\bm{b}}\!=\!(1,1) , {\bm{s}}\!=\!(1,4) , k\!=\!2 . Scalar blocks; scopes of 4 consecutive columns. (b) 4:8 Sparsity. \mathcal{V}\!=\!\mathcal{L}_{\text{phys}} , {\bm{b}}\!=\!(1,2) , {\bm{s}}\!=\!(1,4) , k\!=\!2 . Column-pair blocks; scopes of 4 blocks. (c) 1:2 thread-group coupled sparsity as seen in Figure 1(b) , \mathcal{V}\!=\!(2,8,16):(128,\!16,\!1) , {\bm{b}}\!=\!(1,1,16) , {\bm{s}}\!=\!(2,1,1) , k\!=\!1 . 16-col blocks; rows 8 apart compete. (d) Coupled 2:4. \mathcal{V}\!=\!(M,\frac{K}{8},4,2):(K,8,1,4) , {\bm{b}}\!=\!(1,1,1,2) , {\bm{s}}\!=\!(1,1,4,1) , k\!=\!2 . Column-pair blocks couple cols 4 apart to reduce metadata. Figure 2: Experimental sparsity patterns: structure (top) and pruned result (bottom). Cell fill color encodes block identity; colored outlines delimit scopes; dark gray cells are pruned to zero. All four patterns are expressed by