Dynamic Sparse Training of Diagonally Sparse Networks
Authors: Abhishek Tyagi
Arjun Iyer
William H Renninger
Christopher Kanan
Yuhao Zhu
Venue: ICML 2025 poster (2025)
Keywords: Structured Sparsity; Sparse Neural Networks; Dynamic Sparse Training
Primary area: deep_learning->algorithms
TL;DR: A method to train diagonal sparse neural networks and accelerate them on GPUs.

Abstract: Recent advances in Dynamic Sparse Training (DST) have pushed the frontier of sparse neural network training in structured and unstructured contexts, matching dense-model performance while drastically reducing parameter counts to facilitate model scaling. However, unstructured sparsity often fails to translate into practical speedups on modern hardware. To address this shortcoming, we propose DynaDiag, a novel structured sparse-to-sparse DST method that performs at par with unstructured sparsity. DynaDiag enforces a diagonal sparsity pattern throughout training and preserves sparse computation in forward and backward passes. We further leverage the diagonal structure to accelerate computation via a custom CUDA kernel, rendering the method hardware-friendly. Empirical evaluations on diverse neural architectures demonstrate that our method maintains accuracy on par with unstructured counterparts while benefiting from tangible computational gains. Notably, with 90\% sparse linear layers in ViTs, we observe up to a 3.13x speedup in online inference without sacrificing model performance and a 1.59x speedup in training on a GPU compared to equivalent unstructured layers.

Dynamic Sparse Training of Diagonally Sparse Networks
Abhishek Tyagi* Arjun Iyer? William H Renninger"
Christopher Kanan'
Yuhao Zhu'
Abstract
Dense
SET
CHTs
Piselatedb
DSB DynaDiag (Ours)
Rigl
Recent advances in Dynamic Sparse Training (DST) have pushed the frontier of sparse neural network training in structured and unstructured contexts, matching dense-model performance while drastically reducing parameter counts to facilitate model scaling. However, unstructured sparsity often fails to translate into practical speedups on modern hardware. To address this shortcoming, we propose DynaDiag, a novel structured sparse-to-sparse DST method that per- forms at par with unstructured sparsity. Dyna- Diag enforces a diagonal sparsity pattern through- out training and preserves sparse computation in forward and backward passes. We further leverage the diagonal structure to accelerate com- putation via custom CUDA kernel, rendering the method hardware-friendly. Empirical eval- uations diverse neural architectures demon- strate that our method maintains accuracy on par with unstructured counterparts while bene- fiting from tangible computational gains. No- tably, with 90% sparse linear layers in ViTs, we observe up to 3.13x speedup in online infer- ence without sacrificing model performance and 1.59x speedup in training to equivalent unstructured layers. Our source code is available at https: htthhhgtthb...oo com/ hori zon www.ooorreeseerrcr//naoaaaa
1.00
4.0
1.8
Inference Speedup (x)
Training Speedup (x)
1.0
76.5
77.5
76.5
77.5
2.5
1.4
Struc. Sparsity
Struc. Sparsity
1.0
1.0
Better
Accuracy (%)
Accuracy (%6
Figure 1:
Comparing the inference (left) and training speedups (right) (calculated using wall-clock time) of sparse training methods and the Top-1 classification accuracy (x-axis) for a ViT-Base model at 90% sparsity running ImageNet-IK. DynaDiag, being closest to the top right cor- ner, demonstrates superior accuracy and speedup compared structured and unstructured sparse training approaches.
One way to reduce the execution cost of these networks and still perform par with their dense counterparts (Frankle & Carbin, 2018; Blalock et al., 2020; Mostafa & Wang, 2019) is to compress them by removing unnecessary weights using methods such as pruning (Molchanov et al., 2016; Tanaka et al., 2020), and sparse training (Jaiswal et al., 2022; Zhang et al., 2023b).
GPU compared
Weights are typically pruned either randomly (unstructured sparsity (Evei et al., 2020; Han et al., 2015)) in patterns (structured sparsity (Liu et al., 2019)). Unstructured sparsity achieves high sparsity ratios with minimal performance loss but lacks hardware acceleration. Structured sparsity, while hardware- friendly, fardndle-friendly, has yet to match the performance of unstructured approaches.
1. Introduction
Over the years, deep neural networks (DNNs) have grown, and their performance complex tasks has increased and beyond human-level performance (Sparkes, 2023; Lykiar- dopoulou, 2023). However, the cost of training and infer- ence for such large DNNs has skyrocketed (Cottier, 2023).
'Department of Computer Science, University of Rochester, Rochester, NY, USA 'The Institute of Optics, University of Rochester, Rochester, NY, USA. Correspondence to: Abhishck Tyagi <atyagi2 www.eeeeerroreeeereeuu....
Current structured sparsity methods face two key issues. First, they often use dense backpropagation (Lasby et al., 2023), resulting in negligible training speedup. Even when sparse gradients are computed, transposing weight matri- ces in backpropagation breaks hardware-friendl. patterns, hindering acceleration (Hubara et al., 2021). Second, these methods struggle with high sparsity, suffering significant
Proceedings of the ndnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Dynamic Sparse Training of Diagonally Sparse Networks
performance drops-as we show later.
is commonly known as Pruning and has been used com- press CNNs (Cai et al., 2022; Lin et al., 2019), ViTs (Yang et al., 2023b; Yu et al., 2022) and LLMs (Lu et al., 2024), Lottery Ticket Hypothesis (LTH) (Frankle & Carbin, 2018) states that within a large, randomly initialized neural net- work, there exists a smaller, sparse subnetwork (a "winning ticket") that, when trained in isolation from the original initialization, can match or exceed the performance of the full, dense model and potentially be much more efficient to train from scratch.
To address these limitations, we introduce a novel sparse pattern inspired by small-world networks (Watts & Stro- gatz, 1998: Telesford et al., 2011) (ill)-iagonal sparsity-thar that retains its structure during backpropagation, enabling effi- cient training acceleration. We propose DynaDiag, a fully differentiable training method to learn diagonal sparsity by dynamically selecting and updating the most critical diag- onals during training. Our approach outperforms existing structured sparsity methods across tasks and sparsity levels, achieving high performance and efficiency, even at extreme sparsities. Experiments show that diagonal sparsity consis- tently surpasses structured sparse architectures in vision and language tasks while maintaining computational benefits.
2.2. Sparse Training Methods
Sparse training aims train sparse neural network from scratch. It can broadly be classified into either Static Sparse Training (SST) or Dynamic Sparse Training (DST).
Fig. 1 presents comparison of DynaDiag with existing Dy- namic Sparse Training (DST) methods for both structured and unstructured sparsity. DynaDiag achieves the highest accuracy among the structured DST methods. Moreover, DynaDiag significantly reduces the inference and training wall-clock times on a GPU.
In SST, the positions of the non-zeros in each weight matrix are fixed at the start of the training and are maintained the same throughout. Training then optimizes the values of the non-zeros for loss minimization. Pixelated Butterfly (Dao et al., 2021) uses butterfly factorization to fix the mask at initialization. However, SST is prone to higher loss than DST as DST can escape the local minimum (Evci et al., 2020), especially at high sparsities.
The following are the major contributions of our work:
1. We introduce a diagonal sparsity pattern inspired by small-world networks that preserve its structure under transposition and are efficiently accelerated on GPUs.
In DST, the positions of the non-zeros are updated dynami- cally during training. The usual way to do DST by starting with sparse weight matrices before repeatedly training the network for few iterations, then removing the weights that are of least importance based on magnitude (Mocanu et al., 2018; 8; Jayakumar et al., 2020) or gradients (Evci et al., 2020; Chen et al., 2022), and then growing another set of connections which will be trained in the next iterations.
2. We propose DynaDiag, differentiable TopK- based Sparse-To-Spp To-Saase training algorithm to obtain diagonally-sparse neural networks.
3. We conduct extensive empirical evaluations of Dy- naDiag on computer vision and natural language tasks, demonstrating that it outperforms all prior struc- tured sparsity methods under the same sparsity bud- get. Additionally, DynaDiag achieves competitive per- formance, showing no statistically significant differ- ence compared to unstructured sparsity techniques like RigL (Evci et al., 2020).
SET (Mocanu et al., 2018) is one of the earliest DST works that introduced prune-and-regrow strategy for DST, where during the prune phase, weights are pruned based on their magnitude and are regrown randomly. MEST (Yuan et al., 2021) regrows weights randomly and uses a combination of weight magnitude and gradient magnitude of the existing weights to prune them. RigL (Evci et al., 2020), on the other hand, prunes weights based on their magnitudes and are regrown based on the gradients of missing links (zero weights), which makes the backward pass dense and unable to take advantage of the sparsity in the network. Addressing this limitation of RigL, Zhang et al. (2024) proposes CHT and CHTs (Zhang et al., 2025) methods where a gradient- free (and based on the network topology) approach is used during the regrow phase, which makes their method scalable and achieves sfate-of-the-art performance at broad range of sparsities.
4. We introduce a method to convert diagonally sparse ma- trices to Block CSR (BCSR) format to enable speedups in both inference and training.
2. Related Work
2.1. Sparsity in Neural Networks
The main idea behind sparsity in neural networks to re- move the weights or activations that have minimal contribu- tion to the model's overall performance. The most common way of doing this is to pre-train a dense network and re- move unimportant weights using heuristics such as weight magnitude (Han et al., 2015) or gradients (Molchanov et al., 2017; 2019; Lee et al., 2018; Wang et al., 2020) and then fine-tune the model to maintain the accuracy. This approach
Top- KAST (Jayakumar et al., 2020) is closest to our work and uses a TopK function to pick the most useful weights in both the forward and backward pass. However, unlike Dyna-
2

---

Dynamic Sparse Training of Diagonally Sparse Networks
Diag, both methods result in an unstructured distribution of nonzero weights and, hence, do not yield speedups on GPUs. SRigL (Lasby et al., 2023) addresses the above limitations
3.1. Diagonal Sparsity Formulation
To formulate our weight matrix with diagonal sparsity, we first define how the positions of the diagonals are determined and how the trainable parameters along these diagonals are specified.
BSF (f=2733
(B=1)
Permutation Matrix. A permutation matrix P E IR M is a binary matrix containing precisely one entry row and column, with all other entries equal to 0. In our setting, we place these Is along diagonal specified by an offset off as described in Eqn.
per
Diagonal (Our work)
Value Vector. Let V E Rmaa(M.N) be a vector whose elements populate the diagonal entries of W at positions indicated by P. The operator diag(V) forms a diagonal matrix K x K, where K = max (M,N), and places the elements of V along its main diagonal.
Block
Butterfly
Diagonal Definition. Let W E RM and define N min( N). We specify diagonal in W with offset off as the set of entries (i.j) such that
Figure 2: Overview of different sparsity patterns from the literature used in sparse training methods. Bipartite Scale- Free (BSF) and behavior of Bipartite Small-World (BSW) networks with varying 3 is explained Apdx. I
j = (i + off) mod N.
where a negative off indicates a diagonal below the main diagonal.
of RigL by dynamically identifyyng weight matrices that abide by N:M sparsity pattern, which can be accelerated GPUs (by transforming N:M to 2:4 pattern supported by NVIDIA GPUs (Mishra et al., 2021; Hu et al., 2024)). The authors show that SRigL retains the same accuracy as RigL for ViTs and CNNs, though the method lacks evaluations on large language models (LL.Ms). Moreover, while they report inference speedups in the final trained models, the training process does not currently benefit from this sparsity. DSB (Jiang et al., 2022) uses block sparsity to accelerate the training and inference while dynamically looking for the optimal placement of non-zero blocks. However, as we show in Sec. 4, block sparsity loses out significantly at high sparsities like the pixelated butterfly method.
We aim to learn both the positions and the values of diago- nals in W. To achieve this, we express W E M as the product of permutation matrix P and a diagonal matrix diag(V). Concretely, for single diagonal weight matrix,
W1 P x diag(V)
(2)
This factorization enables gradient-based methods to opti- mize the corresponding values of W (through V),, making it well-suited for end-to-end learning.
We generalize the single-diagonal form (2) to represent any matrix WK E M with K being the required num- ber of diagonals (calculated from the desired sparsity level S²), each of length min(M, N). Specifically, we write
The various structured and unstructured sparsity patterns discussed are shown in Fig. 2. We will now describe the training of diagonally sparse neural networks.
WK Σ
Ps diag(Vy),
where each P, is a permutation matrix defining the of the j-th diagonal, and each V, vector of diagonal values.
3. Training Diagonally Sparse DNNs
We present a differentiable formulation of diagonally sparse matrices (Sec. 3.1) learn the pattern shown in Fig. 2. We then describe our TopK -based training approach (Sec. 3.2) that dynamically optimizes diagonal positions during train- ing. Finally, we detail the conversion of our diagonal ma- trices to the GPU-efficient BCSR format (Sec. 3.3). Fig. 3 breaks down the various stages of our training method into forward and backward passes, illustrating what makes our DST approach efficient.
3.2. TopK Based Diagonal Selection
With our learnable diagonal representation (Eqn. 3), we can parameterize each layer, and our objective reduces finding the optimal diagonal placements (offsets) and associated values that yield the lowest overall loss.
(1-S)-M-N
min(M.N)
3

---

Dynamic Sparse Training of Diagonally Sparse Networks
Forward Pass
Wk
Diage to BCSR
Input
Oulput
Topklana
Berrcessssinn
CUDA Kernel
(b)
(c)
(e)
Backward
Pass
g(W))
Diegs
W.
Wg
Transpose
WW
(h)
(g)
Figure 3: Training with DynaDiag and diagonal sparsity. TopK induces sparsity in (a), which leads to selecting subset of diagonals for the forward pass (b) and (c). Matrices with diagonals are converted to BCSR format to accelerate sparse matrix-matrix multiplication (d) and (e). Backward pass is accelerated by converting the diagonal sparse weight matrix to BCSR format (g). Sparse gradients are calculated using our custom CUDA kernels (h) and (i).
To determine which diagonals contribute the most to the final matrix WK. we introduce learnable vector of impor- tance weights a MM (Fig. 3a). We use TopK function select the K most significant diagonals out of all possible diagonals based on the values in a (Fig. 3b). Concretely, we replace the summation in (3) with
TopK or heuristics, especially when the initial selection biased or the significance of the diagonal evolves during training. We employ cosine-annealing schedule during training adjust T from high starting value (yielding smoother TopK). To encourage sparsity in
employ an ( regularization term. We derive per-layer sparsity budget Pj from the global sparsity budget Pglobal, and the number of diagonals K, for each layer is determined based on Pj-
Wx Σ āz P3 diag(Vj),
(4)
Having established the forward pass with diagonal sparse matrices, we next describe how they are efficiently accel- erated on GPUs by converting them into hardware-friende formats.
ā = TopK(a))
where Pj and diag(V,) specify the j-th diagonal WK, and ãj is the importance weight for that diagonal after applying TopK.
3.3. GPU Acceleration
A differentiable TopK function takes vector of values as inputs and outputs vector with higher values assigned to the top К values. We can use differentiable TopK function in an end-to-end training method and learn which values a should be in the top K for particular task. We use the following softmax-base TopK our end-to-end pipeline (we also experimented with other Topk methods, such the one proposed by Sander al. (2023) but found it to be too slow). For a given Mmax(M,N) (M,)) vector,
To efficiently execute diagonally sparse matrices GPUs, they must be transformed into formats compatible with spe- cialized hardware, such as dense matrices, 2:4 sparse matri- ces, or block sparse matrices. We determined that converting to block sparse matrices is the most effective approach for our sparse pattern (Fig. 3d): converting to dense matrices would introduce unnecessary overhead from additional vec- tor addition operations, while 2:4 sparsity would impose overly restrictive constraints on the positioning of the diago- nals.
exp
ã mimin
(5)
When converting diagonal patterns to BCSR format, we optimize for two key objectives: minimizing the number of blocks and maximizing block density. Dense blocks ensure efficient hardware utilization by reducing redundant values, while fewer blocks minimize memory access overhead and computational requirements on the GPU.
== exp
T
where 7 is the temperature. We adopt temperature- controlled TopK function to enable balance between exploration (considering less dominant diagonals) and ex- ploitation (focusing on the most important diagonals). Sub- optimal solutions may arise without temperatune-coonrrlleed
computations

---

Dynamic Sparse Training of Diagonally Sparse Networks
Although finding the optimal block-minimizing permuta- tion from diagonals BCSR is NP-hard, various heuristics have been developed to cluster non-zero values and reduce the block count. Our approach builds upon SmaT library, proposed by Okanovic et al. (2024). The Sma'T library uses Jaccard-based similarity metric (Labini et al., 2022) for de- termining blocking, which works the best when matrices have a banded structure.
SRigL (Lasby et al., 2023), DSB (Jiang et al., 2022), and DiagHeur train networks with structured spar- sity via DST. SRigL exploits N:M sparsity to accel- erate inference (but not training), DSB accelerates both, and DiagHeur serves as a diagonal-sparsity base- line without our differentiable topk selection (it uses a magnitude-based grow-and-decay scheme as detailed in Apdx. H).
Our approach yields training acceleration by leveraging the same diagonal-to Cissonnl-to-BSRR BCBR conversion for Wx and W This optimization enables efficient sparse computation during forward propagation and backpropagation, where we com- pute sparse gradients and accelerate the sparse operations required for gradient calculation.
PixelatedBFly (Dao et al., 2021) factorizes dense ma- trices into fixed butterfly structure. With further opti- mizations, it leverages block sparsity speed up both training and inference.
Our hardware implementation also leverages key optimiza- tions for sparse matrix multiplication on GPUs, inspired by the techniques described in (Okanovic et al., 2024). We elaborate on these techniques in more detail in Apdx. D.
4.2. Main Results
4.2.1. VISION EXPERIMENTS
Setup. We evaluate two architectures for vision tasks on CIFARIO and CIFARIO0 (Krizhevsky & Hinton, 2009) and ImageNet-1 (Deng et al., 2009). Due to space limitations, we focus our discussion on ImageNet- IK results. For CI- FARIO and CIFAR100 results, please see Apdx. F.I.
4. Experiments
We first describe our experimental setup in Sec. 4.1. We then present main results, comparing the performance of DynaDiag with other baselines (Sec. 4.2.1) and (Sec. 4.2.2) and comparing DST methods' training and inference time on GPUs (Sec. 4.2.3). We wrap up this section by proposing a fine-tuning method to improve DynaDiag's 's algorithmic performance beyond unstructured sparsity (Sec. 4.3.1).
MLP:
We use MLP-Mixer (Tolstikhin et al., 2021) to focus on the impact of sparsity on large matrix multi- plication components without additional complexities.
VIT: To demonstrate scalability, we train various sizes of Vision Transformers (ViT) (Dosovitskiy, 2020).
4.1. Experimental Setup
We test DynaDiag with uniform sparsity (Dao et al., 2021) at 60%, 70%, 80%, 90%, and 95%, following the training regime in Apdx. C.2
The aim for our experiments is to show the efficacy of our structured DST approach on different modalities (vision and language), model types (mlp and attention), and sparsity regimes.
Results on ImageNet-IK. Tbl. I shows the performance of MLP-Mixer and three sparse variants of ViTs-small (S), large (L), and huge (H)-on on ImageNet- 1 IK. Except for VIT-L/16 and ViT-H/14, all other experiments are performed three times with average accuracies reported in the table.
Evaluation. We assess the algorithmic performance of all training methods using Top-1 accuracy for vision tasks and perplexity for language tasks. Additionally, we measure the training and inference speedups achieved by each method at varying sparsity levels through end-to-end execution. We conduct paired asymptotic McNemar tests (a 0.05) com- paring the top-performing method at each sparsity level against all others, bolding results that show no statistical difference from the best.
The results highlight the effectiveness of DynaDiag, partic- ularly at higher sparsities, where it consistently outperforms other structured sparse training (DST) methods. DynaDiag demonstrates significant improvements over competing DST methods at higher sparsities (90% and 95%). For instance: On ViT-L/16, DynaDiag achieves 77.74% accuracy at 90% sparsity, outperforming the next best method (SRigl.) by 2.28%.To To the best of our knowledge, we are the first to show a DST method's performance training large and huge vari- ants of ViTs from scratch. DynaDiag consistently achieves results on par with RigL., SET, MEST, CHT and CHT's across most sparsity levels. We explain the reason behind
Baselines. We compare our approach against the following sparse training methods:
RigL. (Evei et al., 2020), MEST (Yuan et al., 2021), SET (Mocanu et al., 2018), CHT (Zhang et al., 2024), and CHTs (Zhang et al., 2025) uses DST to produce unstructured sparsity, which does not yield significant speedups in training or inference.
All modules in VIT-S/16 set to the desired sparsity level, except the muadi- attention input projections.
5

---

Dynamic Sparse Training of Diagonally Sparse Networks
Table I: Top-1 accuracy of DynaDiag alongside baseline methods at varying sparsities. We bold results that are not significantly different (based on paired asymptotic McNemar tests (a = 0.05)) from the best-performing method (marked with *) in each column, Among all structured sparse training methods, DynaDiag achieves the highest accuracy on the ImageNet- IK dataset.
Model
Method
Struc.
60%
70%
80%
90
95%
dense accuracy
78.5
Rigl.
no
79.75
79.28
78.71
77.24
71.50
SET
78.15
78.01
77.78
77.01
71.48
CHT
no 79.78
79.37
79.06*
77.66*
71.68*
VIT-B/16
CHTs
79.88*
79.38*
79.05
77.54
71.61
MEST
78.04
77.76
77.39
76.45
69.67
SRigl
yes
77.79
77.84
77.35
75.90
68.70
PixelatedBFly
78.04
77.90
77.31
73.89
62.52
DSB
yes 77.98
77.85
76,26
72.89
64.17
DiagHeur.
77.37
76.95
75.75
71.46
68.06
DynaDiag yes 78.29
77.94
77.62
76,91
69.54
dense ассиrасу
82.2
RigL
no 81.85*
81.57*
81.7
78.26
72.11
SRigL
yes 79.87
78.94
77.54
75.46
66.68
ViT-L/16
PixelatedBFly
yes 79.13
79.06
79.33
75.12
66.59
DSB
79.44
77.46
75.34
73.55
66.77
DiagHeur.
yes
80.02
80.07
78.23
74.24
68.79
DynaDiag yes
81.52
81.56
81.37
77.74
69.59
dense aсcuracy = 83.2
RigL
83.84
83,47*
82.85
80.52
74.54*
ViT-H/14
SRigL
yes
80.62
79.09
75.42
76.58
69.24
PixelatedBFly
82.24
82.10
81.37
79.91
70.21
DSB
yes
79.53
76.44
71.32
68.09
62,86
DiagHeur.
yes
80.64
78.97
73.07
75.04
65.45
DynaDiag
yes 82.76
82.60
81.89
80.44
73.74
dense accuracy
72.4
RigL
n1
73.21
73.23
73.47
73.01
70.41
SRigl.
71.89
72.05
71.71
70.21
66.87
Mixer-S/16
PixelatedBFly
yes 71.95
71.91
71.45
69.17
67.85
DSB
yes 69.94
70.21
68.9
65.16
60,88
DiagHeur.
yes
69.91
69.77
67.87
64.17
59.16
DynaDiag
yes
72.92
72.95
73.05
72.31
68.89
this disparity in accuracy between DynaDiag and unstruc- tured methods in Sec. 4.3.1 to surpass RigL's performance.)
the substantial memory and computational overheads ciated with increasing parameter counts in large language models.
DynaDiag achieves superior accuracy than other DST ap- proaches on all the ViT variants, demonstrating the scal- ability our method to large models while maintaining competitive performance. The p-values under the asymp- totie McNemar's 's test reported in Tbl. 10 in Apdx. E. This trend holds for CIFAR10 and CIFAR 100 experiments as well.
Results on WikiText-1003 103. We train GPT2-Small and GPT2- Medium (Radford et al., 2019) from scratch² on WikiText- 103 data and show the resulting performance Tbl. 2. All experiments performed racies reported in the table. Both GPT2 models trained with DynaDiag outperform other DST methods on the perplexity metric (lower the better).
times with average accu-
4.2.2. LANGUAGE EXPERIMENTS
Notably, DynaDiag demonstrates increasingly significant improvements over competing DST approaches as sparsity levels rise. For example, 90% sparsity on GPT2-Small,
Setup. For language tasks, we evaluate on the WikiText- 103 dataset using two variants (Small and Medium) of GPT-2 (Radford et al., 2019) at varying sparsities e (40%, 50%, 60%, 80%, 90%). This setup aims to reduce
We make both the attention MLP layers sparse.
6

---

Dynamic Sparse Training of Diagonally Sparse Networks
DinaDiag achieves perplexity of 6.22 points lower than that of the next best DST method while remaining within 2.57 points of the performance ceiling established by RigL. The p-values under the asymptotic McNemar's 's test are re- ported in Tbl. in Apdx. E.
clock measurements.
Setup. We select the most suitable libraries to accelerate execution based on the structured sparsity type: (1) RigL: We use CUSPARSE, as RigL lacks exploitable structure. (2) SRigL: The authors propose a custom method for the acceleration inference in SRigL (Lasby et al., 2023), which we employ to estimate inference and training times. However, the provided CUDA kernels lack the necessary supporting infrastructure (e.g., integration with PyTorch") to enable end-to-end execution and real-time data collec- tion. (3) DSB and PixelatedBFly: Both methods yield block-sparse weight matrices. We use the Triton-based brary from PixelatedBFly (Dao et al., 2021) 1) to accelerate inference for both. However, while this library is used for PixclatedBFly training, it cannot be applied to DSB due to the significant effort required to integrate it into DSB's training pipeline. (4) Diag: We employ custom-developed kernels to accelerate both training and inference for diagonal sparse networks.
Table 2: Perplexity of DynaDiag and baselines. We bold significantly different from RigL based
results that on paired asymptotic McNemar tests (a 0.05). Among all the baselines, DynaDiag achieves the lower PPI. (lower, the better) on the WikiText- 103 dataset.
Model
Method
40%
50%
60%
90%
dense accuracy = 22.21
RigT.
22.34
22.80
23.79
29.87
53.76
GPT2-S
SRigL
22.74
23.19
25.09
31,08
62.55
PixclaredBFly
22.50
23.25
25.98
34.89
66.44
DynaDiag
22.60
22.74
24.67
30.46
56.33
dense accuracy
20.18
RigI.
20.45
21.60
23.49
28.87
51.76
GPT2-M
SRigT.
21.14
22.59
26.09
32.16
55.66
PixclatedBFly
20.86
22.49
25.45
34.24
56.09
Training & Inference Time. In Fig. 4, we present real- world timing comparisons of DynaDiag and other dynamic sparse training (DST) approaches. We implement custom layers in PyTorch for each method and leverage their ded- icated CUDA kernels to accelerate execution. Our results demonstrate that DynaDiag achieves an inference speedup of up to 3.1 x and training speedup of 1.59x compared to the dense equivalent at 90% sparsity. However, we observe diminishing gains lower sparsity levels, with inference speedups of 1.37 x at 60% sparsity and training times ap- proaching parity (0.98x x at 60% sparsity). Our PyTorrch im- plementation does not exploit CUDA kernel optimizations, and addressing this could lead to further speed increases.
DynaDiag
20.69
22.14
24.98
29.65
54.87
RigL
DSB
DynaDiag Dense
SRigL
PixelatedBFly
150
Time (ms)
100
50
(a) Inference Time
4.3. Additional Results
Time (hrs)
15.
4.3.1. How TO IMPROVE DYNADIAG PERFORMANCE?
10-
Tbl. 1 reveals a performance gap between RigL and Dyna- Diag at sparsities 2 80%, which we attribute to the increased expressivity of unstructured sparsity in RigL (Liu & Wang, 2023). To validate this hypothesis, we conduct an experi- ment using LoRA-FA (Zhang et al., 2023a) to fine-tune the weight matrices of VIT-B/16 model at 80% sparsity trained with DynaDiag. We choose LoRA-FA specifically for its memory and computational efficiency during fine-tuning.
5
0
60%
70%
80%
90%
Sparsity Level (b) Training Time
Figure 4: Inference and training time of a ViT-Base at dif- ferent sparsity levels trained with DynaDiag and baselines. When controlling for an equivalent number of non-zero pa- rameters, our specialized diagonal-spars kernel achieves faster execution GPUs than standard sparse kernels.
As shown in Fig. 5a), increasing the rank of LoRA-FA's A and B matrices leads to improved model accuracy. No-
"While custom CUDA kemels can theoretically accelerate train- ing, their effectiveness depends the surrounding infrastructure, such as memory management
integration with deep learning frameworks like Py Torch. In DSB and SRigL, the absence of this supporting structure limits their practical utility for end-to-end training acceleration.
4.2.3. TRAINING AND INFERENCE ACCELERATION
We measure GPU training and inference times for the meth- ods described in Sec. 4.1. 1. All reported timings reflect wall-

---

Dynamic Sparse Training of Diagonally Sparse Networks
Dense
PixelatedBFly
RiGL
DSB
RigL
DynaDiag LoRA-FA
DynaDiag
Dyna w/ Dense Fine Tuning
SRigL
Diag
Accuracy aayc
ViT Base
82
102
80
Accuracy (%)
2
3
5
9
Rank
10
(a) Base with LORA-FA.
LoRA-FA Points
100
MLPMixer
576
102
Row Index
Accuracy (%)
1152
10a
1728
2304
0
192
384
576
768
Column Index
100
0.9
0.95
0.99
0.999
Weight matrix (w/ LoRA-FA.)
Sparsity
Figure 5: Performance of ViT-Base at 80% sparsity fine- tuned with LoRA-FA matrices of different ranks (a). We see an increase in the accuracy over a diagonally sparse model, with rank six matrices enough to match RigL performance. (b) Shows distribution of new fine-tuned parameters for linear layer in the attention block of ViT-Base.
Performance of DynaDiag compared to other base- lines at extreme sparsities for ViT-Base and MLPMixer models on ImageNet-IK: K. DynaDiag outperforms other base- lines, including RigL, at extreme sparsities.
Figure 6:
4.3.2. PERFORMANCE EXTREME SPARSITY
Dynamic sparse training typically uses predefined layer- wise sparsity ratios (e.g., uniform) to avoid layer col- lapse at high sparsity levels, where entire layers risk be- ing pruned (Tanaka et al.. 2020). However, individual lay- ers exhibit distinct learning dynamics (Chen et al., 2023), and extreme sparsity can disrupt gradient flow. We eval- uate DynaDiag under sparsity levels of up to 99.99% on ImageNet- IK using ViT-Base and MLP-Mixer. As shown in Fig. 6, DynaDiag demonstrates robust performance even under these extreme conditions, indicating that it effectively discovers accurate masks from the network topology even in highly sparse settings. DynaDiag outperforms RigL at extreme sparsities, where RigL's performance known to degrade significantly, as documented in prior work (Ji et al., 2024).
tably, DynaDiag surpasses RigL's performance at rank 6, requiring only 1.67% increase in total parameters. This minimal parameter overhead demonstrates that DynaDiag can exceed the accuracy ceiling of unstructured sparsity while maintaining most of its structured sparsity benefits for inference acceleration.
We examine the spatial distribution of fine-tuned parameters in Fig. 5, analyzing linear layer within attention head of ViT-B/16 trained on ImageNet- 1 K. The visualization re- veals that the newly introduced parameters are distributed across the weight matrix an unstructured pattern, support- ing our hypothesis that unstructured sparsity enables better optimization of the loss landscape.
8

---

Dynamic Sparse Training of Diagonally Sparse Networks
5. Discussion
sparsification approach on model faimesss and bias, particu- larly regarding class imbalances and data distribution shifts compared to dense models.
We have identified three current limitations of Dina which will be significant part of the future work. First, while effective for ViTs and LLMs, DynaDiag faces scalabil- ity challenges with CNNs due to the overhead of searching for distinct diagonal patterns across each channel. Secondly, we aim to extend our method to networks with extremely sparse weight matrices-e.g. at sparsity levels approaching 99. 99.999%% or more more-while still retaining more than a single active diagonal. We believe that with large matrices, we will see the effectiveness of having small-world connectivity, resulting in highly sparse networks. However, we could not find good example model to test our hypothesis. Fi- nally, our method's 's performance could be further improved through optimized GPU implementations of diagonal spar- sity using frameworks like Triton.
References
Barabási, A.-L. and Albert, R. Emergence of scaling in random networks. science, 286(5439):509- 512, 1999.
Blalock, D., Gonzalez Ortiz, J. J., Frankle, J., and Guttag, J.
What is the state of neural network pruning? Proceedings of machine learning and systems, 2: 14129116, 2020.
Cai, Y., Hua, W., Chen, H., Suh, G. E.,, De Sa, C., and Zhang, 7. Structured pruning is all you need for pruning cnns at initialization. arXiv preprint arXiv:2203.022 02544, 2022.
Chen, T., Zhang, Z., Wang, P., Balachandra, S., Ma, H., Wang. Z., and Wang, Z. Sparsity winning twice: Better robust generalization from more efficient training. arXiv preprint arXiv:2202.0984. 2022.
6. Conclusion
This work presents novel dynamic sparse training algo- rithm, DynaDiag, that uses small world networks inspired diagonal structured sparsity to train neural networks. We demonstrate that models trained using our TopK -based al- gorithm surpass those from other structured sparse training approaches in terms of both algorithmic effectiveness and hardware acceleration. Ultimately, we show that DynaDiag achieves competitive performance- matching other structured sparsity training methods at lower sparsity levels while beginning to match and, in some cases, surpassing them at extreme sparsity levels.
Chen, Y., Yuille, A., and Zhou, Z. Which layer is learning faster? systematic exploration of layer-wise conver- gence rate for deep neural networks. In The Eleventh International Conference on Learning Representations, 2023.
Cottier, B. Trends in the dollar training cost of machine learning systems. Epoch. January, 31:2023, 2023.
Dao, T., Chen, B., Liang, K., Yang. J., Song, Z., Rudra, A., and Re, C. Pixelated butterfly: Simple and efficient sparse training for neural network models. arXiv preprint arXiv:21 2021.
Acknowledgments
This work was partly supported by NSF award #2326491 to CK and #2419721 to WR and YZ. The views and conclu- sions contained herein are those of the authors and should not be interpreted as representing any sponsor's official poli- cies or endorsements.
Deng, J., Dong, W., Socher, R., L.-J,, Li, K., and Fei-Fei, L. Imagenet: A large-scale hierarchical image database. In 2009 IEEE conference on computer vision and pattern recognition, pp. 248-24888 248-255. Ieee, 2009.
Dosovitskiy, A. An image is worth 16x16 words: Trans- formers for image recognition at scale. arXiv preprint arXiv:2010.11 11999, 2020.
Impact Statement
Our work introduces an efficient sparse training method that enables training larger models with fixed computational resources, supporting the democratization of deep learning as model sizes continue to grow. The method's ability to maintain sparsity throughout training reduces computational and energy costs during both training and deployment, par- ticularly benefiting on-device and real-time learning scenar- ios. While anticipate primarily positive impacts through improved resource efficiency and accessibility, we acknowl- edge that any advancement in machine learning capabili- ties warrants careful consideration. We encourage future research to investigate potential differential effects of our
Evci, U. Gale, T., Menick, J., Castro, S., and Elsen, E. Rigging the lottery: Making all tickets winners. In International conference on machine learning, pp. 2943- 2952. PMLR, 2020.
Frankle, J. and Carbin, M. The lottery ticket hypothesis: Finding sparse, trainable neural networks. arXiv preprint arXiv: 000..8033.000 03..3,66355 2018
Han, S., Pool, J., Tran, J., and Dally, W. Learning both weights and connections for efficient neural network. Advances in neural information processing systems, 28, 2015.

---

Dynamic Sparse Training of Diagonally Sparse Networks
Hu, Y., Zhao, K., Huang, W., Chen, J., and Zhu, Acceler- ating transformer pre-training with 2: 4 sparsity. arXiv preprint arXiv:2404.014 0014474,, 2024.
Lin, S., Ji, R.,, Yan, C., Zhang, B., Cao, L.,, Ye, Q.. Huang. F., and Doermann, D. Towards optimal structured enn pruning via generative adversarial learning, In Proceed- ings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 2790-2799, 2019.
Hubara, I., Chmiel, B., Island, M., Banner, R., Naor, J., and Soudry, D. Accelerated sparse neural training: A provable and efficient method to find n: m transposable masks. Advances in neural information processing systems, 34: 21099-21111, 2021.
Liu, S. and Wang, Z. Ten lessons have learned in the new" sparseland. A short handbook for sparse neural network researchers, 2023.
Jaiswal, A. K., Ma, H., Chen, T., Ding, Y., and Wang, Z. Training your sparse neural network better with any mask. In International Conference on Machine Learning, pp. PMLR, 2022.
Liu, S., Mocanu, D. C., and Pechenizkiy, M. On improving deep learning generalization with adaptive sparse connec- tivity. arXiv preprint arXiv: 11626, 2019.
Lu, H., Zhou, Y., Liu, S., Wang, Z., Mahoney, M. W., and Yang, Y. Alphapruning: Using heavy-tailed self reg- ularization theory for improved layer-wise pruning of large language models. arXiv preprint arXiv:2410.10913 2024.
Jayakumar, S., Pascanu, R., Rae, J., Osindero, S., and Elsen, E. Top-kast: Top-k always sparse training. Advances in Neural Information Processing Systems, 33:20744 20754, 2020.
Lykiardopoulou, Ai beats humans for the first time in phys- ical skill game. https:/ / /www. nwwscienteieie ist. com/ wawticeeeee02aaae. 12 2023. Accessed: 20 01 2025.
Ji, J., Li, G., Yin, Qin, M., Yuan, G., Guo, L., Liu, S., and Ma, X. Advancing dynamic sparse training by exploring optimization opportunities. In Forty-First International Conference on Machine Learning, 2024.
Marcus, M., Santorini, B., and Mareinkiewicz. M. A. Build- ing a large annotated corpus of english: The penn tree- bank. Computational linguistics, 19(2):313-330, 1993.
Janng P., Hu, L.,, and Song, S. Exposing and exploiting fine-grained block structures for fast and accurate sparse training. Advances in Neural Information Processing Systems, 35:38345-38355 2022.
Merity, S., Xiong, C., Bradbury, J., and Socher, R. Pointer sentinel mixture models. arXiv preprint arXiv:1609.00 1609.07893,, 2016.
Krizhevsky, A. and Hinton, G. Learning multiple layers of features from tiny images. Technical Report TR-2009, University of Toronto, 2009.
Mishra, A., Latorre, J. A., Pool, J., Stosic, D., Stosic, D.., Venkatesh, G., Yu, C., and Micikevicius, P. Ac- celerating sparse deep neural networks. arXiv preprint arXiv:2104.088 08378, 2021.
Kuznedelev, D., Kurtic, E., Iofinova, E.,, Frantar, E., Peste, A., and Alistarh, D. Accurate neural network pruning requires rethinking sparse optimization. arXiv preprint arXiv:2308.02006 2023.
Mocanu, D. C., Mocanu, E., Stone, P., Nguyen, P. H., Gibescu, M., and Liotta, A. Scalable training of arti- ficial neural networks with adaptive sparse connectivity inspired by network science. Nature communications, (1):2383, 2018
Labini, P. S., Bernaschi, M., Nutt, W., Silvestri, F,, and Vella, Blocking sparse matrices to leverage dense- specific multiplication. In 2022 IEEF/ACM Workshop Irregular Applications: Architectures and Algorithums (IA3), pp. 19-24. IEEE, 2022.
Molchanov, D., Ashukha, A., and Vetrov, D. Variational dropout sparsifies deep neural networks. In International conference on machine learning, pp. 1498-2507.2 PMLR, 2017.
Langley, P. Crafting papers on machine learning. In Langley, P. (ed.), Proceedings of the 17th International Conference on Machine Learning (ICML pp. 1207-1216, Stan- ford, CA, 2000. Morgan Kaufmann.
Molchanov, P., Tyree, S., Karras, T., Aila, T., and Kautz, J. Pruning convolutional neural networks for resource efficient inference. arXiv preprint arXiv: 161 1.06440, 2016.
Lasby, M., Golubeva, A.. Evci, U., Nica, M., and Ioannou, Y. Dynamic sparse training with structured sparsity. arXiv preprint arXivv2305.02299 2023.
Molchanov, P., Mallya, A., Tyree, S., Frosio, I., and Kautz, J. Importance estimation for neural network pruning. In Proceedings of the IEFE/CVF conference on computer vision and pattern recognition, pp. 11264-1122 11272, 2019.
Lee, N., Ajanthan, T., and Torr, P. H. Snip: Single-shot network pruning based on connection sensitivity. arXiv preprint
2018.
10

---

Dynamic Sparse Training of Diagonally Sparse Networks
Mostafa, H. and Wang, X. Parameter efficient training of deep convolutional neural networks by dynamic sparse reparameterization. In International Conference Ma- chine Learning, pp.
Yang, H., Liang, Y., Guo, X., Wu, L., and Wang. Z. Pruning before training may improve generalization, provably. arXiv preprint arXiv:2301.00 230.:00331300 2023a.
PMLR, 2019.
Yang, H., Yin, H., Shen, M., Molchanov, P., Li, H., and Kautz, J. Global vision transformer pruning with hessian- aware salieney. In Proceedings of the IEEE/CVF con- ference on computer vision and pattern recognition, pp. 18547-18557, 2023b.
Okanovic, P., Kwasniewski. G., Labini, P. S., Besta, M., Vella, F., and Hoefler, T. High performance unstructured spmm computation using tensor cores. In SC24: Inter- national Conference for High Performance Computing, Networking, Storage and Analysis, pp. 1-14. IEEE, 2024.
Yu, F., Huang, K., Wang, M., Cheng, Y., Chu, W., and Cui, L. Width & depth pruning for vision transformers. In Proceedings of the AAAI Conference Artificial Intelli- gence, volume 36, pp. 3143-3151, 2022.
Radford, A., Wu, J., Child, R., Luan, D., Amodei, D., Sutskever, I., et Language models are unsupervised multitask learners. OpenAI blog, 1(8):9, 2019.
Yuan, G., Ma, X., Niu, W. Li, Z., Kong, Z., Liu, N., Gong, Y., Zhan, Z., He, C.,, Jin, Q. et al. Mest: Accurate and fast enemory-econome sparse training framework the edge. Advances in Neural Information Processing Systems, 34: 20838-20850, 2021.
Sander, M. E., Puigcerver, J., Djolonga, J., Peyré, G., and Blondel, M. Fast, differentiable and sparse top-k: convex analysis perspective. In International Conference on Machine Learning, pp. 29919-29936. PMLR, 2023.
Sparkes, M. Game-playing deepmind ai can beat top hu- mans chess, go and poker. https: httpp::///hheexxttte http///theeweeb...ee/ com/news. / 11 2023. Accessed: 20 01 2025.
Zhang, L., Zhang, L.,, Shi, S., Chu, X., and Li, B. Lora-fa: Memory-efficient low-rank adaptation for large language models fine-tuning. arXiv preprint 2.xvv2230.0033:2 2023a.
Sun, M., Liu, Z., Bair, A., and Kolter, J. Z. A simple and effective pruning approach for large language models. arXiv preprint arXiv:2306. 11695, 2023.
Zhang, X.-J,, Moore, J. M.. Yan, G., and Li, X. Universal structural patterns in sparse recurrent neural networks. Communications Physics, 6(1):243, 2023b.
Tanaka, H., Kunin, D., Yamins, D. L., and Ganguli, S. Prun- ing neural networks without any data by iteratively con- serving synaptic flow. Advances in neural information processing systems, 33:6377-6389, 2020.
Zhang, Y., Zhao, J., Wu, W., Muscoloni, A., and Cannis- traci, C. V. Epitopological learning and cannistraci-hebt network shape intelligence brain-inspired theory for ultra- sparse advantage in deep learning. In The Twelfth Inter- national Conference on Learning Representations, 2024.
Telesford, Q. K., Joyce, K. E., Hayasaka, S., Burdette, J. H., and Laurienti, P. J. The ubiquity of small-world networks. Brain connectivity, 1(5):367-375, 2011.
Zhang, Y., Zhao, J., Wu, W., Liao, Z., Michieli, U., and Can- nistraci, C. V. Brain-inspired sparse training enables trans- formers and Ilms to perform as fully connected. arXiv preprint 2rXiv:2501.19000 2025.
Tolstikhin, O., Houlsby, N., Kolesnikov, A., Beyer, L., Zhai, X., Unterthiner, T., Yung, J., Steiner, A., Keysers, D., Uszkoreit, J., et al. Mip-mixer: An all-mip architec- ture for vision. Advances in neural information process- ing systems, 14:24261-222722 2021.
Wang, C., Zhang, G., and Grosse, R. Picking winning tickets before training by preserving gradient flow. arXiv preprint arXiv:2002.07376, 2020.
Watts, D. J. and Strogatz, S. H. Collective dynamics of 'small-world" networks. nature, 393(6684):440 1998.
Yamaguchi, T. and Busato, F. Accelerating matrix multipli- cation with block sparse format and nvidia tensor cores. NVIDIA Developer Technical Blog. https://developer mvidia, mamareaiiinngaiiiiimiiiiiictttt block- bock-sparse-formal - tenoorrccrttssso-orrreeeeee 2021.

---

Dynamic Sparse Training of Diagonally Sparse Networks
Appendix
Apdx. A proves that secudo-diagona masks remain pseudo-diagonal after transposition.
Apdx. B gives the theoretical justification for diagonal sparsity (coverage, rank, universal approximation).
Apdx. C lists all experimental hyper-parameters and datasets.
Apdx. D describes our CUDA BCSR implementation and speed-up analysis.
Apdx. E reports McNemar p- p-values for all comparative studies.
Apdx. F.3 analyzes temperature, sparsity scheduling, and distribution schemes.
Apdx. G summarizes accuracy vs. speed-up trade-off's across sparsity levels.
Apdx. H details the Hhagonal--heristte variant of Rigl..
Apdx. reviews the BSW and BSF graph models.
Apdx. I.1 quantifies the woald-world properties of DynaDiag networks.
A. Proving the Transposability of Diagonal Sparse Matrices
THEOREM
Let M E (0,1)mxx be binary mask matrix constructed with pseudo-diagonal pattern starting position 8. Then, the transpose M also exhibits pscudo-dis gecudo-diagonal pattern, with the diagonal's 's starting position adjusted based on the relative dimensions of m and n.
PROOF
We consider two cases based on the relationship between m and n:
CASE m 2 n (MORE ROWS THAN COLUMNS)
1. Construction of M:
The diagonal starts at row & and spans n entries.
Entries M are at positions:
(r, = ((s + c) mod m, e) for (0,1, 10,1..... ..... 1}.
2. Transposition MT:
The transposed matrix M has dimensions n X m.
Entries MT are at positions:
(c, (s mod m) for {0, 10.1....,, 1}.
3. Pseudo-Diagonal in M
Since the transposed matrix M now has fewer rows than columns.
The pscudo-diagonal in M starts at column (original row offset) and spans n entries:
= (r, (8 mod m) for r {0,1, 10.1,...,n4 1}.
This matches the transposed entries, confirming M retains a pseudo-diagon starting at column s.
12

---

Dynamic Sparse Training of Diagonally Sparse Networks
CASE 2: m (MORE COLUMNS THAN ROWS)
1. Construction of M:
The diagonal starts at column s and spans m entries.
Entries M are at positions:
(r,c) = (r, (s +r) mod n) for E (0.1..... 1}.
2. Transposition M
The transposed matrix T has dimensions n x m.
Entries in M are at positions:
(()+)) mod n, r) for E (0,1,...,mm m 1}.
3. Pseudo-Diagonal in M
Since m, M has more rows than columns.
The pseudo-diagonal in M starts at row (original column offset) and spans entries:
(r, c) = ((s + c) mod n, c) for c E {0, 1, ,,, 1}.
This aligns with the transposed entries, confirming M retains a pseudo-diagonal starting at row s.
In both cases, transposing a pseudo-diagonal mask results in a matrix with an equivalent pseudo-diagonal structure. The starting position s transitions between row and column offsets depending on the original matrix's dimensions, preserving the diagonal nature under transposition. Thus, matrices constructed with the described pseudo-diagonal pattern exhibit transposition invariance in their sparsity structure.
B. Theoretical Justification of Diagonal Sparsity
Consider a single linear layer of a neural network represented by the weight matrix W E R Sparsity patterns enforce structural constraints on W through binary masks M E (0, 1 producing sparse weight matrices as W + M, where O denotes clement-wise multiplication.
Definition (Diagonal Sparsity). A diagonal sparsity pattern selects set of diagonals defined by their offsets. Formally, the mask M is constructed as:
1,
(j () à (mod min(n, m)) for some diagonal offset 6,
Mij
0, otherwise.
The number of diagonals selected, denoted k. controls the density of M.
Lemma 1 (Full Input-Output Coverage). A diagonal mask M constructed as above ensures that each row and each column of M contains at least one nonzero entry, given k 2 1.
Proof. Consider two cases:
Case 2 mc Each diagonal covers all m columns exactly once. By varying diagonal offsets, each row index represented by some diagonal least once, thus no row remains empty. Since each diagonal always covers every column exactly once, column remains empty either.
Case m > n: By symmetry, each diagonal covers all n rows exactly once. By shifting offsets across multiple diagonals, all columns are covered least once.
13

---

Dynamic Sparse Training of Diagonally Sparse Networks
This ensures no input dimension output neuron ever completely disconnected by the sparsity mask, guaranteeing full coverage. D
Expressivity via Universal Approximation. The universal approximation theorem (Cybenko, 1989; Hornik, 1991) asserts that fully connected neural networks with nonlinear activations (such as ReLU or sigmoid) are capable of approximating arbitrary continuous functions. Structural sparsity patterns, however, may potentially violate universal approximation by severing input-output connections.
Theorem (Universal Approximation under diagonal Sparsity). A feed-forwart neural network consisting of layers employing diagonal sparsity masks with sufficiently large number of diagonals k 2 kmins nonlinear activations, and adequate width and depth, retains the universal approximation property.
Proof Universal approximation requires that any input neuron can influence any output neuron, possibly through multiple layers. Lemma ensures full input-output coverage at every sparse linear transformation. Thus, each neuron maintains at least one active input and output edge. preserving connectivity across the network.
Because diagonal patterns ensure no dimension is eliminated globally, subsequent nonlinear activations can still combine these preserved dimensions arbitrarily. Therefore, the assumptions required for universal approximation [1][2] remain valid, implying the network's 's expressivity is not significantly impaired by this structured sparsity pattern. D
Rank Preservation Argument. Another perspective on expressivity arises through linear algebraic arguments. Any row or column in a weight matrix W being entirely zero automatically restricts the maximum achievable rank. A rank-deficient weight matrix severely limits the set of linear transformations expressible by that layer.
With diagonal sparsity:
Each row and column has at least one nonzero element, removing a trivial structural cause of rank deficiency.
For random initialization of nonzero weights, such sparse matrices will have full achievable rank (min(n, m)) almost surely (standard linear algebra argument; see e.g. random matrix theory.).
High rank at initialization and throughout training supports richer linear transformations, ultimately preserving higher network expressivity and better gradient propagation properties.
Comparison to Other Patterns. Unlike structured sparsity patterns such as block-sparse or n-of-m sparsity, diagonal sparsity guarantees deterministic full input-output coverage. In block sparsity, some neurons risk being completely disconnected if blocks overlap in suboptimal ways, limiting expressivity and training stability. diagonal sparsity patterns avoid these degeneracies by design.
Furthermore, diagonal sparsity provides a structured yet near-random pattern, capturing many beneficial properties of un- structured random sparsity, demonstrated empirically by experiments in this paper- paper-while offering improved computational efficiency and implementation simplicity.
These theoretical results substantiate the empirically observed superior or near-optimal performance of diagonal sparsity patterns, positioning them as a particularly promising structured sparsity approach for efficient neural network training and inference.
C. Experiment Details
All experiments are conducted on the NVIDIA Tesla A100 GPUs with the following configuration:
Model: NVIDIA A100 80GB
Memory: 80GB HBM2e
Memory Bandwidth: ~2.0 TB/s (higher than the 40GB version)
14

---

Dynamic Sparse Training of Diagonally Sparse Networks
TDP: 400W (PCle: 300W)
Peak FP32 Performance: 19.5 TFLOPS (same as 40GB)
Peak FP16 Performance: ~312 TFLOPS (same as 40GB)
C.1. Datasets
1. CIFAR-10 (Krizhevsky & Hinton, 2009) consists of 60,000 colored images of resolution 32 32, divided into 10 classes (e.g., airplanes, cars, birds). The dataset is split into 50,000 training and 10,000 test images.
2. CIFAR-100 (Krizhevsky & Hinton, 2009) also contains 32 x 32 resolution images but spans 100 classes. Each class includes 500 training and 100 test images, totaling 60,000 images.
3. ImageNet-1K (Deng et al., 2009) covers 1,000 object classes, with 1.28M training, 50,000 validation, and 100,000 test images. Images are typically resized and cropped 224 224 for processing.
4. WikfText-103 (Merity et al., 2016) comprises over 100 million tokens extracted from verified Wikipedia articles. is significantly larger than other language datasets, such as Penn Treebank (PTB) (Marcus et al., 1993).
15

---

Dynamic Sparse Training of Diagonally Sparse Networks
Table 3: Configuration of the CIFARIO and CIFAR100 experiments with MLPMixer.
Parameter
Value
Adam 31
0.9
Adam $2
0.99
AutoAugment
True
Batch Size
128
CutMix Probability
0.5
CutMix B
1.0
Dropout
0.0
Epochs
300
Hidden.C C
512
Hidden_S S
64
Hidden
128
(Initial LR, Final LR)
(1 x 10 10-3, x 10-9)
Label Smoothing
0.1
Layers
8
LR Scheduler
Cosine
Optimizer
Adam
Random Seed
3407
Weight Decay
x 10
Warmup
5 epochs
Table 4: Configuration of the CIFAR1O and CIFAR 100 experiments with ViT-Small.
Parameter
Value
Epochs
200
Batch Size
128
Optimizer
Adam
Weight Decay
x 10
LR Scheduler
Cosine
(Initial LR, Final LR)
(1 x 10-3, x 10 10-5)
Warmup
5 epochs
Dropout
0.0
AutoAugment
Truc
Label Smoothing
0.1
Heads
12
Layers
7
Hidden
384
MLP Hidden
384
16

---

Dynamic Sparse Training of Diagonally Sparse Networks
Table 5: Configuration of the ImageNet experiments with ViT-Base and MLPMixer.
Model
Optimizer
Weight Decay
Learning Rate
Drop Path
Warmup/Eppch
ViT-Base
Adam W
0.05
0.001
0.1
5/300
DynaDiag- ViT-Base
Adam W
0.05
0.001
0
5/300
Mixer-Sman
Adam W
0.1
0,001
0.1
5/300
DynaDiag-Mixxn Smxll
AdamW W
0.1
0.001
5/300
Table 6: Configuration of the ImageNet experiments with ViT-Large and Huge.
Parameter
Value
Batch size
256
Optimizer
AdamW
Learning Rate (LR)
x 10-3
LR decay
cosine
Weight decay
0.02
Warmup epochs
5
Label smoothing
0.1
Dropout
Stochastic Depth
Repeated Aug
Gradient Clipping
1.0
Horizontal flip
Random Resized Crop (RRC)
Rand Augment
3 Augment (ours)
LayerScale
Mixup
0.8
Cutmix
1.0
Erasing prob.
X
Colorlitter
0.3
Test crop ratio
1.0
Loss
BCE
D. GPU Acceleration
We leverage the known diagonal structure to enforce the clustering of rows/columns from the same diagonal into contiguous blocks. Modify the reordering algorithm to:
Prioritize grouping rows/columns from the same diagonal.
Allow limited flexibility for rows/columns from adjacent diagonals (controlled by Diag Proximity).
We modify Jaccard's similarity with a diagonal proximity term to prioritize clustering rows/columns that belong to diagonals with nearby starting positions. For two rows and j:
Sim(i,j) = a Jaccard(i.)) + (1 - . Prrxxiity((...) (i.
(6)
where:
(i.card(i.j): Standard Jaccard index (overlap of non-zeros between rows i and j).
Proximity(i..) Normalized inverse distance between the starting positions of the diagonals containing rows i and j:
Proximity (i.j) = 1 dist(d,, dy)
(7)
maxx(ist)
17

---

Dynamic Sparse Training of Diagonally Sparse Networks
Table 7: Configuration of the Wikitext- 103 experiments GPT-2Small experiments.
Model
Optimizer
Weight Decay
Learning Rate
Dropout
Warmup/Epoch
GPT-2-Small
AdamW
0.1
0.0001
0.1
5/100
DynaDiag
AdamW
0.1
0.0001
0.1
5/100
where da, dy are the diagonal start positions for rows j. and max(dist) is the maximum possible distance between diagonals.
Tuning parameter (0 I S 1) balance the two terms. For our case, we set < 0.5 to prioritize diagonal structure over raw overlap.
Since the diagonals are determined by their starting positions, we precompute the diagonal membership for each row/column. Using this preprocessing step. we can convert sparse diagonal matrices dense blocks during the forward (Fig. 3d) and backward (Fig. 3h) pass which accelerates both inference and training of models with DynaDiag.
Specifically, we employ the following strategies to maximize computational efficiency and minimize memory overhead:
Tensor Cores (TC) API: We utilize half cuff-precision matrix multiply- accumulate (mma ml 6n8k16 6) operations via the TC API, illustrated in the PTX code provided in (Okanovic al., 2024). This allows us exploit the high throughput of Tensor Cores for dense submatrix computations within the sparse matrix framework.
Block Compressed Sparse Row (BCSR) Iteration: To efficiently iterate over non-zero blocks in the sparse matrix, we use the BCSR format, which relies on rowPtr and co Idx arrays. This avoids unnecessary iterations over zero blocks, significantly reducing computational overhead.
Asynchronous Data Movement: To hide memory latency, we employ cuda: : : mmmeppy_ssym for overlapping computation with data transfers. This allows efficient movement of data from global memory to shared memory without intermediate register staging, freeing up registers for computation.
Warp-Level Parallelism: Each warp in our CUDA kernel is responsible for computing a submatrix of the output matrix C, with dimensions matching those of the Tensor Cores. Non-zero blocks are loaded into registers using 1 ldmatri iix (see Listings 2 and 3 in (Okanovic et al., 2024)), and the results are written back to global memory after computation.
For comprehensive understanding of the implementation details, including pseudocode and additional optimizations, direct readers to (Okanovic et al., 2024). The SMAT library can be found at https//ggthub.cco/sp///smaa
Correlation Between Number of Diagonals and Speedups. Using our custom CUDA implementation, we perform matrix-matrix multiplication on matrices of size 768 x 76S(matching the size of the blocks. laattts..atttpprrr www.ppoo...iie. weight layer in ViT where I is the block count) to isolate the impact of number of diagonals on potential speedup. All the experiments were carried out on NVIDIA A100 40GB GPUs. Each configuration was run 100 times, and we averaged the total time of converting diagonals to BCSR plus the subsequent BCSR computation. As expected, below 50% sparsity, speed gains taper off, and below 20% sparsity, see some slowdown yet this remains more favorable than comparable block-sparse paaroaches(Yamaguug & Busato, 2021).
Performance Impact of Diagonals to BCSR Conversion. With empirical experiments on ViT-B/16 at 90% sparsity with ImageNet-IK, we verify that there is no significant accuracy difference between direct diagonal computation and the BCSR- approach. From Tbl. 8, we can see that there is no significant difference the accuracies of the two methods, proving their equivalence. However, the training time is significantly improved using our custom BCSR kernel.
E. McNemar's Test Results
McNemar's 's test is a non-parametric x² procedure for paired binary outcomes. Given two classifiers (or a pre-post condition) evaluated on the same n instances, their predictions form a 2 x 2 contingency table. The statistic considers only the off off-diagonal counts instances mis-classified by exactly one of the two methods- and tests the null hypothesis that these two counts are equal, i.e., that the marginal proportions of successes are identical. A significant result therefore indicates
18

---

Dynamic Sparse Training of Diagonally Sparse Networks
Speed-up vs. Number of Diagonals for a 768x768 matrix
Speed up vs. Dense
1x
20
Speed-up
15-
10
5
(99.74%) 7.44))
8 (98.96%)
15 (98.05%)
38 (95 05%)
76 (90.10%)
153 (80.08%
230 75.)5%)
307 (60.03%)
384 (50. (50.00% 00%)
460 (40. 10%%
537 (30. 08%)
614 (20 05%)
691 (10.03%)
768 (0.00%)
2 (99.
Number of diagonals (sparsity)
Figure 7: Speedup obtained using our custom CUDA implementation while doing matrix-matrix multiplication with matrices having the diagonal sparsity pattern.
Table 8:
DynaDiag performance with and without BCSR conversion with a 90% sparse ViT-B/16 on ImageNet-
Method
Accuracy
Training Time (hrs)
Without BCSR Conversion With BCSR Conversion
76.92+:0.001 76.91+000007
18.07
1 11.42
Table 9: P-values from MeNemar's 's test comparing each method with Rigl. at varying sparsities (0.6, 0.7, 0.8, 0.9, 0.95).
Bold values indicate no significant difference (p-value 2 0.05) from RigL.
Models
Methods
Struc.
Cifar10
Cifar100
0.6
0.7
0.8
0.95
0.95
RigL.
SRigl.
yes
0.0523
0.0614
0.0312
0.0285
0.0221
0.0654
0.0531
0.0598
0.0356
0.0299
Mixer-S/16
PixclatedBFly
yes
0.0751
0.0845
0,0213
0.0198
0.0174
0.0321
0.0212
0.0315
0.0287
0.0253
DSB
yes
0.0231
0.0198
0.0123
0.0098
0.0075
0.0225
0.0187
0.0112
0.0085
0.0063
DiagHeur.
yes 0.0145
0.0123
0.0091
0.0067
0.0052
0.0132
0.0110
0.0084
0.0058
0.0047
DynaDing
yes 0.0587
0.0674
0.0512
0.0543
0.0601
0.0756
0.0823
0,0654
0.0682
0.0745
RigL.
nO
SRigl.
yes 0.0578
0.0695
0.0345
0.0302
0.0253
0.0712
0.0421
0.0623
0.0381
0.0324
PixelatedBFly
yes 0.0245
0.0193
0.0167
0.0132
0.0111
0.0223
0.0676
0.0650
0.0125
0.0103
VIT-S/16
DSB
yes
0.0184
0.0165
0,0122
0.0095
0.0078
0.0193
0.0161
0.0124
0.0090
0.0072
DeagHeur.
yes
0.0123
0.0105
0.0087
0,0065
0.0051
0.0131
0.0114
0.0093
0.0069
0.0050
DynaDing
yes
0.0612
0,0725
0,0534
0,0568
0,0632
0,0773
0,0834
0,0675
0,0708
0,0761
that the two methods differ in predictive accuracy while properly accounting for the dependence induced by evaluating on the same data points.
We show the p- palues for VIT-S/16 and Mixer-S/16 running Cifar10 and C0f in Tbl. 9. And the p-values for models ImageNet-I 1K and GPT models on WikiText- 103 are shown in Tbl. 10 and Tbl. 11 respectively.
F. Additional Results
F.1. CIFARIO and CIFARI00 Results
All the experiments are performed three times with the average accuracies shown in the table. We omit the standard deviation since the training is relatively stable (i.e., usually less than 0.06% standard deviation). We present results for Mixer-S/16
19

---

Dynamic Sparse Training of Diagonally Sparse Networks
Table 10: P-values from paired asymptotic McNemar tests comparing each method with RigL. at varying sparsities
E (60%, 70,, 80%, 90%, 95% Bold values indicate no significant difference (p-value 2 0.05) from RigL.
Model
Method
60 %
70%
80
90%
95%
RigL
SET
0.0542
0.0401
0.0364
0.0419
0.0564
CHT
0.0764
0.0672
0.0693
0.0628
0.0572
ViT-B/16
CHTs
0.0654
0.0619
0.0629
0.0724
0.0529
MEST
0.0598
0.0462
0.0298
0.0387
0.0432
SRigL.
0.0473
0.0521
0.0345
0.0289
0.0224
PixelatedBFly
0.0542
0.0396
0,0317
0.0253
0,0198
DSB
0.0124
0.0187
0.0105
0.0083
0.0061
DiagHeur:
0.0098
0.0123
0.0075
0.0059
0.0043
DynaDiag
0.0654
0.0789
0.0411
0.0598
0.0352
RigL.
SRigL
0,0415
0.0253
0,0367
0.0302
0,0235
PixelatedBFly
0.0398
0.0312
0.0329
0.0264
0.0201
ViT-L/16
DSB
0.0142
0.0201
0.0113
0.0091
0.0067
DiagHeur:
0,0105
0.0137
0,0082
0.0065
0,0049
DynaDiag
0.0698
0.0836
0.0564
0.0517
0.0379
RigL.
SRigL
0.0431
0.0395
0.0382
0.0320
0.0258
PixelatedBFly
0.0627
0.0343
0.0341
0.0276
0.0214
ViT-H/14
DSB
0,0165
0.0223
0,0131
0.0105
0,0079
DiagHeur.
0.0128
0.0159
0.0095
0.0078
0.0056
DynaDiag
0.0725
0.0874
0.0583
0.0529
0.0394
RigL
SRigL
0.0672
0.0294
0,0356
0.0294
0.0230
PixelatedBFly
0,0311
0.0491
0,0308
0.0247
0,0185
Mixer-S/16
DSB
0.0139
0.0195
0.0102
0.0079
0.0054
DiagHeur. 0.0112
0.0148
0.0087
0.0063
0.0045
DynaDiag
0.0701
0.0856
0.0605
0.0553
0.0617
Table 11: P-values from McNemar's test comparing DynaDiag (Diag), SRigL, and PixelatedBFly with RigL varying sparsities s E {0.4, 0.5, 0.6, 0.8, 0.9}. Bold values indicate no significant difference (p-value 2 0.05) from RigL.
Model
Method
40%
50%
60%
80 %
90%
RigL.
SRigL.
0.0456
0.0398
0.0321
0.0275
0.0213
GPT2-S
PixelatedBFly
0.0523
0.0471
0.0384
0.0332
0.0285
DynaDiag
0.0183
0.0518
0.0675
0.0529
0.0401
RigL 0.0395
SRigL
0.0352
0.0287
0.0231
0.0178
GPT2-M
PixelatedBFly
0.0589
0.0427
0.0356
0.0304
0.0256
DynaDiag
0.0518
0.0576
0.0547
0.0657
0.0136
20

---

Dynamic Sparse Training of Diagonally Sparse Networks
Table 12: Top-1 accuracy of DynaDiag alongside baseline methods at varying sparsities. We bold results that are not significantly different from RigL based on paired asymptotic McNemar tests (a = 0.05). Among all structured sparse training methods, DynaDiag achieves the highest accuracy on ViT-Small and MI.eMixer architectures across CIFAR-10 and CIFAR-100 datasets.
Models
Methods
Struc.
CIFARIO
CIFARI00
60%
70%
80%
90%
95%
60%
70%
80%
90%
95%
dense accuracy = 85.64
dense accuracy = 66,98
RigL.
86.44
86.47
86.74
85.85
84.65
67.44
67.97
67.54
66.52
64.2
Mixer-S/16
SRigL.
yes
85.98
85.69
85.14
83.45
82.14
67.19
66.94
66.88
64.03
60.41
PixelatedBFly
yes
85.39
85.25
84.69
82.41
81.09
66.45
65.74
64.36
63.57
59.56
DSB yes
83.14
83.45
82.14
80.21
80.12
65.14
64.74
64.26
62.44
58.14
DynaDiag yes
DiagHeur.
82.69
83.01
81.11
79.56
78.65
64.54
64.21
63.47
62.3
60.08
86.14
86.19
85.69
85,55
83.13
67.08
67.02
66.91
64.21
61.30
dense accuracy;
89.67
dense accuracy:
66.61
RigL
no 91.04
91.03
90.38
88.45
84.56
68.91
68.43
66.54
65.31
62.32
SRigL.
yes 90.67
90.51
89.32
86.88
81.54
68.51
67.85
66.21
64.81
61.11
VIT-S/16
PixclatedBFly
yes
90.08
90.16
87.51
83.31
80.14
68. 14
68.10
66.13
64.12
61.33
DSB
yes
89.55
89.45
88.39
83.52
80.09
68.01
67.69
66.05
63.23
60.08
DiagHHeur:
yes
89.14
88.51
86.49
80.61
66.87
65.57
65.08
64.09
60.26
DynaDiag
yes
90.55
90.63
89.43
87.09
82.76
68.41
68.12
66.31
65.06
61.43
Table 13: Perplexity of DynaDiag alongside baseline methods. We bold results that are not significantly different (calculated using paired asymptotic McNemar tests (a = 0.05)) from the best performing method in the column (marked with a *). Among the baselines, DynaDiag achieves the lower PPL (lower, the better) on the WikiText- dataset.
Model
Method
40 %
50%
60 %
80% %
90%
dense accuracy = 22.21
RigL
22.34
22.80
23.79
29.87
53.76
SRigL
22.74
23.19
25.09
31.08
62.55
GPT2-S
PixclatedBFly
22.50
23.25
25.98
34.89
66.44
Wanda
22.14*
22.35*
23.48
29.12
53.07*
DynaDiag
22.60
22.74
24.67
30.46
56.33
and ViT-Small in Tbl. 12, where DynaDiag performs as new state-of-the-art among structured DST methods, exceeding prior approaches at every sparsity level except one (60% CIFAR10 with Mixer-S/16). The p-values under the asymptotic McNemar's test are reported in Tbl. 9 in Apdx. E.
We also observe that for CIFARIO, the accuracy of both ViT-S/16 and Mixer-S/16 improves after sparsification compared to their dense counterparts. We hypothesize that this improvement stems from the fact that both models are overparameterized, meaning they possess more parameters than necessary to the training data. By sparsifying the models, we eliminate less important redundant parameters, leading to more efficient and generalizable model (Liu et al., 2019; Yang et al., 2023a).
F.2. Comparison with Pruning Methods
Pruning LLMs (Sun et al., 2023; Kuznedelev al., 2023) has been an effective way of reducing the size of the model while producing models with kate-of-the-an inference accuracies high sparsity levels. However, pruning requires dense training along with fine-tuning post pruning which is not the case with sparse-to-sparse training of models.
To see how DynaDiag performs as compared to pruning methods, we ran Wanda (Sun et al., 2023) with the GPT-2 small model and reported the results Tbl. 13. As expected, Wanda, a pruning method, produces models with better perplexity than DST-based methods. However, Wanda's 's results are produced at significantly higher computational cost (dense training + fine-tun munnnnn whereas our method remains computationally efficient.
21

---

Dynamic Sparse Training of Diagonally Sparse Networks
Comparison of Temperature Schedules (Target Sparsity: or 78)
Weight Size: 768x768
180
Exploration Phase
Cosine Constant
1.l.atttn pro) wwt.pproo.iieee..... inear..eee
160
Number of non-2ero values in
140
(VIT-8116: blocks. blocks.1attn...
120
100
80
100
200
250
300
Iteration
Figure 8: Comparing the three different temperature schedules which affect the amount of non-zeros present at training step.
F33. Impact of Temperature Scheduling, Sparsity Scheduling, and Sparsity Distribution on Training
Temperature Scheduling: We study the evolution of non-zero entries a representative weight matrix from ViT-B/16 under three temperature scheduling strategies-Linen Linear, Cosine, and Constant-in Fig. 8. All approaches target 90% sparsity (i.e., retaining K 78 values of 768). We observe that both Linear and Cosine schedules gradually reduce the number of non-zeros during the early training iterations (exploration phase), allowing the model to adapt its sparse structure progressively. In contrast, the Constant schedule enforces the target sparsity from the beginning. leading exploration. This supports our finding that gradual temperature decay yields better performance by allowing more flexible structural learning early in training.
Sparsity Scheduling: We study the effect of different sparsity scheduling strategies Constant, Linear, and Cosine on the performance of VIT-B/16 trained on ImageNet- KK. IK These schedules control how the sparsity level evolves over training. As shown in Tbl. 15, the Cosine schedule consistently achieves the best accuracy across all sparsity levels, followed closely by Linear, while Constant performs significantly worse. This highlights the importance of gradually decaying sparsity schedule for maintaining model accuracy under high sparsity regimes.
Sparsity Distribution: In our experiments, we allocate the sparsity budget, based on layer's compute fraction (proportional to layer size) as proposed in Pixelated Butterfly (Dao et al., 2021)(See 3.3 and Appendix 1.1). However, we also experiment with two other distributions: Uniform and ERK and the results are shown in Tbl. 14. We can see that computational fraction- based allocation yields better results, consistent with findings from Pixelated Butterfly.
Table 14: Impact of different sparsity distribution methods on VIT-B/16 performance ImageNet- 1K
Method
60%
70%
80 %
90%
95 %
Uniform
77.02=10.0013 77.6410.0021
76.73:10.002
76. 06.14
69.31=000011
Frdös-Rényi-Kernel (ERK)
77.93-L0.0018
77.43-10.0019
76.53+10.0014
76.21100.0007
69.45-10.0016
ComputeFraction (PBFly)
78.29100.0000
77.9410.0017
77.62-00.0016
69.54-10.0014 76.01
22

---

Dynamic Sparse Training of Diagonally Sparse Networks
Table 15: Impact of different scheduling methods on ViT-B/16 performance on ImageNet-IK
Method
60%
70%
80 %
90%
95%
Constant 75.64:00.0013
74.82:10.0019
74.03:10.0012
72.74=0.0015 76.21 0.003
68.17:100016
Linear 77.13::000018
77.43=0.0019
69.45=000016
Cosine
78.29+00.0020
07.94
07.021
76.91 69.54+0.0014
Dense
RigL
CHT
CHIs
SRigL
Pixelated8Fly
DSB
DynaDiag (Ours)
1.
3.12
80
1,10
Training Speedup (x)
5.005
75
Inference Speedup
Accuracy (9)
0.30 U. BAZ
0.05
0.00
70
78.5
1.2
65
77.5
0.6
0.7
0.8
0.95
0.6
0.7
0.3
0.9
0.95
0.6
0.7
0.3
0.9
0.95
Sparsity Level
0.9
Sparsity Level
Sparsity Level
Figure 9: Comparing the inference speedup (left), training speedup (center), and Top-1 accuracy (right) of sparse training methods for ViT-B/16 model at varying levels of sparsity running ImageNet-1 K. DynaDiag achieves the highest training and inference speedup while demonstrating superior accuracy other structured sparsity patterns.
G. Summary of Our Experiments
Fig. 9 shows the results of our experiments in single figure. We can see that at 60% and 70% sparsity, DST accuracy performance is better than dense training, and that DynaDiag is the only structured method to keep its performance close to the unstructured ones that perform better than dense. DynaDiag shows a stable accuracy curve that remains high in comparison to the other structured methods. It is the only structured method to present a performance stability similar to unstructured methods across different levels of sparsity.
H. Details of the Heuristics-Basee Method
RigI. is a dynamic sparsification technique that maintains a constant sparsity budget by repeatedly removing the lowest- magnitude weights (decay) and "growing" new connections. Similarly, in our DiagHeur method, we follow the same principle but focus on diagonal blocks: we prune the diagonals with the lowest magnitudes and randomly grow back the same number of diagonal connections, thereby preserving overall sparsity while continually redistributing capacity to potentially more valuable diagonals. We keep all the hyperparameters same as the original RigL (Evci et al., 2020) paper.
I. Bipartite Small-World (BSW) and Bipartite Scale-Free (BSF)
Bipartite Scale-Free (BSF). The Bipartite Scale-Free (BSF) model ofZhang et al. (2024) adapts scale-free connectivity to bipartite graphs, making it ideal for dynamic sparse training. The procedure begins by sampling a standard Barabási-Albert (BA) graph(Barabást & Albert, 1999), whose node degrees follow a power-law distribution. Every edge that links two neurons in the same layer is then eliminated and re-attached neuron in the opposite layer. Crucially, each node keeps its original degree, so the resulting bipartite network retains the BA power-law exponent.
Bipartite Small-World (BSW). The Bipartite Small-Works (BSW) model ofZhang et al. (2024) embeds small-world behaviour and strong clustering into a bipartite graph. starts from a regular ring lattice, labeling the vertices with two distinct layer types. Every vertex connects to the same number of nearest neighbours that belong to the opposite layer, producing highly clustered but not yet
structure. Analogous the Watts Strogatz construction( Watts
23

---

Dynamic Sparse Training of Diagonally Sparse Networks
Strogatz, 1998), the model then applies rewiring rate 8: proportion 3 of existing edges is randomly removed and re-attached elsewhere, introducing the shorteuts that create small-world characteristics.
I.1. Diagonal Sparsity and Small World Networks
To test the small-worldness of networks trained with DynaDiag, we take 90% sparse ViT-B/16 network trained on ImageNet- IK and calculate the small-world factor, using the NetworkX library in Python. Tbl. 16 shows that all tested layers exhibit 2 I, confirming that DynaDiag's structured sparsity indeed reflects small-world characteristics.
Table 16: world factor, a of various layers in a DynaDiag trained ViT-B/16 ImageNet-1K 90% sparsity. a 1 indicates small world.
Layer
Cr
Lr
C
L
0
blocks.O.. Dlatkss...ttm..rroo... linaar weight
0.032
2.14
0.063
3.94
1.069
linea. I linear. Jinear.
0.039
2.67
0.072
3.67
1.343
blocks...mlp.fe..linee... weight
0.041
2.64
0.084
3.55
1.524
blocks.3.attt..rpj.liiea..a weight
0.047
2.94
0.088
3.95
1.394
blocks. flocks.4.mlp.ffl.iinc... weigght
0.029
2.15
0.061
3.87
1.169
Soookk..mmlppfcc.linnaaweeed
0.049
3.42
0.087
3.31
1.835
blocks....tth..pgjliieee..eee weight
0.061
2.65
0.099
3.91
1.100
blocks. blocks.7.mlppfc...iinee. weight
0.041
2.71
0.097
3.90
1.644
blocks. Blocks.8.mlp..f2..ineea. weigh
0.032
2.83
0.066
3.88
1.504
blocks.9. blockss..atth..rrg.lineaa weight
0.047
2.23
0.081
3.77
1.019
blocks. 10..k..f...mm.c1....... .line.rrr..iiiear..... ..w.aa...wigh weight
0.054
3.06
0.096
4.13
1.317
blocks. 11. 1.lp..fc2.linea.. weight
0.051
3.11
0.097
3.97
1.490
24


Reviews:
[{"review_id": "NSKL18FimQ", "reviewer": "Reviewer_XE14", "summary": "The paper introduces DynaDiag, a novel structured Dynamic Sparse Training (DST) method that enforces diagonal sparsity to improve both computational efficiency and model accuracy. Unlike unstructured DST methods, which often fail to achieve hardware acceleration despite high sparsity ratios, DynaDiag maintains structured sparsity throughout training, enabling significant speedup in both training and inference. The key idea is to enforce a diagonal sparsity pattern that remains structured under transposition, making it well-suited for efficient GPU execution. To optimize learning, DynaDiag employs a dynamic TopK-based selection mechanism to adaptively update the most critical diagonals, allowing the model to learn the optimal sparse connectivity during training. Additionally, the authors introduce a custom CUDA kernel that utilizes Block Compressed Sparse Row (BCSR) format, ensuring fast execution for both forward and backward passes. Empirically, DynaDiag achieves a 3.13× inference speedup and a 1.59× training speedup compared to dense models, while matching or outperforming existing structured sparse training methods. The method is evaluated on Vision Transformers (ViTs), CNNs, and GPT-2 models across ImageNet, CIFAR-10, CIFAR-100, and WikiText-103, demonstrating strong generalization even at extreme sparsities (up to 99.99%). The results indicate that DynaDiag is a viable alternative to unstructured DST, offering comparable accuracy while significantly improving computational efficiency. The study highlights the limitations of existing sparse training approaches and presents DynaDiag as an effective way to achieve both hardware acceleration and model performance, making it highly promising for scaling sparse deep learning models in practical applications. By bridging the gap between sparse training and hardware efficiency, DynaDiag paves the way for more efficient deep learning architectures, especially in resource-constrained environments.", "questions": "", "limitations": "", "rating": 5, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their insightful and constructive feedback, which has significantly helped enhance our work. Below, we concisely address each comment:\n## Comparison with SET, MEST, CHT, CHTs Methods (Response to Q1, Q4, Q7)\nDue to time constraints, we chose the above four of the five methods suggested by the reviewer and carried out experiments on ViT-B/16 with ImageNet-1K.\n\n**Results:** Please refer to [Table 11 here](https://figshare.com/s/b6386a7f35eca3ebcfeb) for performance numbers.  We also [updated Figure 1](https://figshare.com/s/3c8b904acdce99263d30) to incorporate the methods suggested by the reviewer.\n\n**Conclusion:** CHT and CHTs outperform RigL at most sparsities. We calculate the statistical significance (using McNemar’s test) of the performance at various sparsities, and find that all the models in bold can be considered equivalent for that sparsity level. DynaDiag’s performance is also equivalent to that of the best model at that sparsit.; Thus, our structured sparsity performs comparable to current SOTA unstructured methods.\n\n## Small-Worldness (Response to Q3)\nWe agree with the reviewer, and we take a ViT-B/16 trained with DynaDiag and calculate the small-world factor, $\\sigma$ using NetworkX[[1]](https://shorturl.at/7qS5A) library in Python.\n\n **Results:** Please refer to the results for various layers in [Table 12 here](https://figshare.com/s/b6386a7f35eca3ebcfeb)\n\n**Conclusion:** All tested layers exhibit $\\sigma \\geq 1$, confirming that DynaDiag's structured sparsity indeed reflects small-world characteristics.\n\n## Alpha Initialization and Other Scheduling Strategies (Response to Q5 & Q12)\nAll $\\alpha$s are initialized equally to start with, which are then passed as input to our $TopK$ function. The output of the TopK function is a sparse vector $\\tilde{\\alpha_i}$, which is used to obtain a diagonally sparse weight matrix for a layer, given as: \n$W_{K} = \\sum_{j=1}^K \\tilde{\\alpha}_j \\,P_j \\,\\mathrm{diag}(V_j)$\n\n**Results:** \n\nWe obtain a [density decay curve ](https://figshare.com/s/2b5d7955c1c92fb72c42). \n\nWe also show how different scheduling methods affect the performance of ViT-B/16 [Table 14](https://figshare.com/s/b6386a7f35eca3ebcfeb).\n\nThe duration of the exploration phase is a hyper-parameter, and we choose its value as $\\frac{1}{3}\\times epochs$.  The initial and final temperature value is set as described by Sander et al [[2]](https://shorturl.at/eOKWy).\n\n## Training Time of RigL (Response to Q6)\nFor training unstructured sparse networks, we use torch.sparse for doing sparse matrix-matrix operations. We report the wall clock time for both training and inference. \nFor Fig 1 and Fig 4a, we use the inference time with a batch size of 1 to obtain per sample inference time.Although no substantial speedup was observed from 60% to 90% sparsity, consistent with SRigL[[3]](https://shorturl.at/HX30S) and SparseRT[[4]](https://shorturl.at/baywp), noticeable improvements appear at 95% sparsity.\n\n**Results:** We report the inference and training time in [Tables 17 and 18 here](https://figshare.com/s/b6386a7f35eca3ebcfeb), respectively.\n\nWe welcome reviewer suggestions for enhancing our unstructured timing baseline.\n\n## Per Layer Sparsity (Response to Q9)\nWe allocate the sparsity budget, based on a layers compute fraction (proportional to layer size) as proposed in PixelatedBFly[[1]](https://shorturl.at/Gblym) (Sec 3.3 and Appendix I.1). \n\n**Experiment:** We also experiment with two other distributions: Uniform and ERK. \n\n**Results:** We tabulate the results in [Table 13 here](https://figshare.com/s/b6386a7f35eca3ebcfeb).\n\n**Conclusion:** Computational fraction-based allocation yields better results, consistent with findings from PixelatedBFly.\n\n## Arguments of $TopK(\\alpha, s, t)$ (Response to Q8)\nThe TopK function arguments are the importance vector ($\\alpha$), layer sparsity ($s$), and\ntemperature ($t$), controlling the softness/hardness of the selection.\n\n## Clarification on Equation (5) and L1 regularization of $\\alpha$ (Response to Q10 & Q11)\nWe updated the equation considering the reviewer’s comments:\n\n$\\tilde{\\alpha_i} = \\min \\Bigl(k \\cdot \n   \\frac{\\exp\\bigl(\\tfrac{\\alpha_i}{T}\\bigr)}{\\sum_{j=1}^n \\exp\\bigl(\\tfrac{\\alpha_i}{T}\\bigr)}\n, 1\\Bigr)$\n\nK is the total number of diagonals per layer, determined from per-layer sparsity (footnote 1 on page 3).\n\nWe apply L1 regularization on alphas to encourage sparsity and we add the L1 loss to the overall loss function as:\n\t$\\text{Loss} = \\text{crossEntropyLoss} + \\lambda \\sum_{l=1}^{L} \\|\\alpha^{(l)}\\|_1$\nThe regularization coefficient $\\lambda$ is set at 0.2 following a hyperparameter search, and we\nobserve no noticeable impact on training speed.\n\n## Do we plan to release the code? (Response to Q13)\nYes. We also plan to provide a step-by-step guideguide for reproducibility.\n\nWe sincerely hope these adjustments fully address the reviewer’s feedback and request reconsideration of our work based on these substantial enhancements.", "claims_and_evidence": "About the claim that “Empirical evaluations on diverse neural architectures demonstrate that our method maintains accuracy on par with unstructured counterparts while benefiting from tangible computational gains.” I think it should be adjusted and reduced because there are many new evidences in literature in which unstructured methods such as CHT, CHTs and CHTss can perform better than RigL, GMP and even better than fully connected architectures (see the section below on essential references not discussed).\n\nI agree of course about these second part of the claim “while benefiting from tangible computational gains.” \nIn my opinion the current version of the paper do not report solid evidence that supports the claim because it neglects to compare with the most recent methods in unstructured and structured dynamic sparse training (see the section below on essential references not discussed). In addition, also the related work and the Figure 1 and 2 and the other section of the article should be adjusted reporting appropriate claims on the most recent methods in the literature.", "methods_and_evaluation_criteria": "Yes, they make sense but the number of tested methods are few. I recommend discussing and add SET, MEST, CHTs, CHTss (see the section below on essential references not discussed).", "theoretical_claims": "I have checked the proof of this article and it is correct", "experimental_designs_or_analyses": "Yes, I checked, and I believe the manuscript should be improved. I recommend to test and discuss result including MEST, CHTs, CHTss  (see the section below on essential references not discussed).", "relation_to_broader_scientific_literature": "The idea and method of this article is nice and solid, and I believe that if the authors address my concerns this article would be interesting for all the community.\n\nHowever, considering the current version of the paper, I think that the relation to Broader scientific literature should be significantly improved. The authors are not aware of relevant new finding in unstructured/structured dynamic sparse training and that there are today also methods such as CHT, CHTs and CHTss that can perform better than fully connected networks. In addition, the authors do not discuss that the network topology initialization with network science modelling such as bipartite small-world and bipartite scale-free modelling or with method such as CSTI that are input data based in Figure. 2.  \nThe study overclaims the relevance of their results with respect unstructured methods not comparing with current SOTA. \nI invite the authors to largely revise the study to put in the appropriate and balanced context, because I believe this study can be of value for the community.", "essential_references_not_discussed": "Mocanu, D. C.,et al. Scalable training of artificial neural networks with adaptive sparse connectivity inspired by network science. Nature Communications (2018), 9, Article number: 2383.\n\nYuan, G., et al. \"MEST: Accurate and fast memory-economic sparse training framework on the edge.\" Advances in Neural Information Processing Systems 34 (2021): 14476-14489.\n\nZhang, Y. et al. Epitopological learning and Cannistraci-Hebb network shape intelligence brain-inspired theory for ultra-sparse advantage in deep learning. Proceedings of the Twelfth International Conference on Learning Representations (ICLR) 2024.\n\nWu, B., et al. Dynamic Sparse Training versus Dense Training: The Unexpected Winner in Image Corruption Robustness. Proceedings of the Twelfth International Conference on Learning Representations (ICLR) 2025.\n\nZhang, Y., et al. \"Brain-inspired sparse training enables Transformers and LLMs to perform as fully connected.\" arXiv preprint arXiv:2501.19107 (2025)", "other_strengths_and_weaknesses": "Strengths\nThis article introduces the diagonal sparse training which is novel in this field. Very nice idea. \nThe proposed methods outperform the other structured sparsity sparse training methods in Comprehensive Benchmarking on Vision and Language Tasks\n\nWeakness:\nThe study section on related work is incomplete and far from reporting the most recent advancements in the field. \nThe study needs to compare with SOTA unstructured methods to support their claims and offers an updated comparison of their method.\nA lot of the training details of this article are unclear and the work necessity a robust revision to match the standard of reproducibility", "other_comments_or_suggestions": "Please see the question section", "questions_for_authors": "I kindly ask to the authors whether they can revise the study:\n\n1. balancing their claims under the light of my comments above and the new literature I provided.\n2. rewrite all the articles sections, and in particular the related work section, taking in consideration my comments and the new literature I provided.\nIn particular:\n Fig1 should modified including if possible other methods such as SET, MEST, CHTs, CHTss. \nFig. 2 should be modified including other sparsity patterns such as bipartite small-world (BSW, which for beta=1 includes the random pattern) and bipartite scale-free (BSF) modelling or with methods such as CSTI which create a regular diagonal pattern that is input data based. \n3. The authors should offer a quantitative proof that their topologies are really small-world using the small word measures. The claim is not really theoretically well posed from the network science standpoint, it necessity evidences by small-worldness measures to offer evidence that their sparsity patter is characterized by the small-world phenomenon. To me it seems that their sparsity pattern is more inspired by a regular highly clustered pattern which is indeed very similar to CSTI (see Zhang et al ICLR2014 in the section Essential References Not Discussed) or BSW with beta=0 (which in reality is not small-world because the Watts-Strogatz small-world model for beta=0 is a regular clustered structure for which the small-world effect vanishes). But I might be wrong and for this I kindly ask a quantification of small-worldness. \n4. insert in the computational experiments, when it is possible , the comparison with new methods such as SET, MEST, CHTs, CHTss. \n5. How the alpha initialized? If alpha is initialized equally, then it will start from a fully connected network. Then how is the learned density decay curve?\n6. I'm not sure how the unstructured sparse training method RigL is tested. As the article said, \"We use CUSPARSE, as RigL lacks exploitable structure.\" Which kind of sparse format is the author using? Can you provide the single module running time of the proposed diagonal sparse training/inference and the other structures? As the density changes, the running time of RigL doesn't change. However, as my experience, if using the torch.sparse module, the running time will change significantly based on sparsity. However as shown in the article, the running time doesn't change from 60-90% sparsity.\n7. Could the authors compare their method with CHTs [1], which has been shown to outperform RigL in most cases, as a baseline for unstructured sparse training?\n8. In Figure 3a, what are the arguments of TopK(α, t, s)? Specifically, what do t and s represent?\n9. The per-layer sparsity budget ρj is derived from the global sparsity budget ρglobal, and the number of diagonals Kj for each layer is determined based on ρj. Does the paper adopt a non-uniform sparsity distribution across layers? And what does the final sparsity distribution look like.\n10. In Formula (5), the authors use min(max(oi, 0), 1). However, shouldn't oi always be ≥ 0? Also, what does k represent in the formula, and how is it tuned?\n11. The authors mention that to encourage sparsity in α, they employ an ℓ1 regularization term. Could they elaborate on how this is implemented and its impact on training?\n12. The authors apply a cosine-annealing schedule to adjust T during training, starting from a high value for a smoother TopK selection. Have they tested alternative scheduling methods?\n13. Many training details is missing which makes the article hard to reproduce. If the article is accepted, do the authors plan to release the code?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "P4brCFWRjD", "reviewer": "Reviewer_vAzp", "summary": "This paper introduces DynaDiag, a novel structured Dynamic Sparse Training (DST) method based on the composition of diagonal matrices. This parametrization is then transformed into the BCSR format to enable actual GPU acceleration. The proposed model is evaluated by training from scratch vision VIT and MLP-Mixer models, as well as the GPT-2 model, closing the gap between the unstructured and structured DST algorithms.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their feedback and positive comments. We are glad to hear that the\nreviewer appreciates the novelty of our work. We address the questions and comments below:\n\n## BCSR Transformation and Contribution (Q1)\nFor acceleration on GPUs, a diagonal matrix is converted to blocks (represented in BCSR) by calculating a row transformation $P$. \n\n**Contribution:** We propose a heuristic-based method to convert diagonal matrices to block matrices which is built on top of SMAT[[1]](https://arxiv.org/pdf/2408.11551), which proposes a method to calculate $P$ for the general case of unstructured matrices.\n\n Where SMAT uses Jaccard similarity between the rows to block them efficiently (see Section IV C of SMAT), we modify Jaccard’s similarity (as mentioned in detail in Appendix A.3) with a diagonal proximity term to prioritize diagonals close to the main diagonals, which maximizes the total number of dense blocks. Our heuristics take advantage of the fact that each row in the matrix has the same number of nonzeros which help with load balancing when running on the GPU.\n\n## Performance Impact of Diags to BCSR conversion (Q4)\nConverting a diagonal matrix $W_{diag}$ to a blocked matrix (in BCSR) $W_{BCSR}$ is done by applying row permutation to $W_{diag}$ given as:\n\t \n $W_{BCSR} = P_{perm}W_{diag}$\n\n**Matrix-Vector equivalence in diag and BCSR Format:** To ensure that matrix-vector multiplication remains equivalent between the two formats, an inverse of $P_{perm}$ (which is its transpose) is applied to the incoming input $x$. We show the equivalence below:\n\nWe can write:\t\n\t\n$Output_{diag} = W_{diag}X$\n\n$Output_{diag} = W_{BCSR}P_{perm}^{-1}X$\n\n$Output_{diag} = W_{BCSR}(P_{perm}^{-1}X)$\n\nTherefore, the two methods result in the same output. \n\n**Experiment:** With empirical experiments on ViT-B/16 at 90% sparsity with ImageNet-1K, we verify that there is no significant accuracy difference between direct diagonal computation and the BCSR-based approach.\n\n**Results:** Please refer to [Table 16 here](https://figshare.com/s/b6386a7f35eca3ebcfeb).\n\n**Conclusion:** We see no significant difference in the accuracies of the two methods, proving their equivalence. However, the training time is significantly improved using our custom BCSR kernel.\n\n## Comparison with Sparse-to-Sparse finetuning methods (Q2)\nWe agree with the reviewers' suggestion to apply our training method to LLaMA models for comparison with SOTA pruning methods such as Wanda and SparseGPT. Doing so will require us to train a LLaMA model from scratch, and hence, **we propose to share those results in our final manuscript.**\n\nHowever, we ran Wanda (SparseGPT did not work out of the box with GPT-2) with the GPT-2 model and reported the results.\n\n**Results:** Please refer to [Table 15 here](https://figshare.com/s/b6386a7f35eca3ebcfeb).\n\n**Conclusion:** As expected, Wanda, a pruning method, produces models with better perplexity than DST-based methods. However, the performance difference is not significant compared to DST methods (as evident from McNemar’s test results). However, Wanda's results are produced at a significantly higher computational cost (dense training + fine-tuning), whereas our method remains computationally efficient.\n\n## Per Layer Sparsity (Q3)\nPlease refer to our [response to Reviewer XE14](https://openreview.net/forum?id=bAUVnNc0Ky&noteId=K2Jst84n3i), under the section titled: “Per Layer Sparsity”.\n\n## Justification For The Choice Of Training Configurations\nWe thank the reviewer for pointing out the missing justification for the choice of training configurations in Tables 3, 4, 5, 6, and 7. All the configurations are obtained from the literature, and here are the references:\n\n1) Tbl 3 [[2]](https://shorturl.at/QFzJw)\n2) Tbl 4 [[3]](https://shorturl.at/bc3hz) \n3) Tbl 5 and Tbl 7 [[4]](https://shorturl.at/4Hzxp)\n4) Tbl 6 [[5]](https://shorturl.at/4qmmR)\n\n## Temperature and Alpha Initialization (Q5)\n\n### Temperature:\n\nWe employ a temperature-based softmax for differentiable TopK approximation. Initially set high (T=1.0), the temperature gradually anneals to T=0.01, focusing the search from broad exploration to a sharp selection of diagonals. This approach balances exploration and computational overhead effectively, guided by prior methods such as Sander et al [[6]](https://dl.acm.org/doi/10.5555/3618408.3619649).\n\n### Alpha Initialization:\n\nCurrently, all $\\alpha$s are initialized equally, assuming initial equal importance across diagonals. For future exploration, we are working with two alternative initialization methods:\n\n**Distance-Based Initialization:** Higher initial values for diagonals near the main diagonal.\n\n**Data-Driven Initialization:** Input data-driven initial importance reflecting intrinsic data structure or correlations.\n\nThese strategies may enhance convergence speed and overall performance.\n\nWe appreciate the reviewer’s valuable suggestions, which can considerably improve the clarity and strength of our paper.", "claims_and_evidence": "The claims in the paper are mostly clear, supported either by empirical analysis or previous research. I do have, however, one issue with the contributions. In particular, with the last point. The paper presents the conversion of matrices to BCSR format as a contribution, but it remains unclear how novel this conversion method is. Does it simply apply existing techniques from Section 3.3, or does it introduce new fundamental ideas?", "methods_and_evaluation_criteria": "The paper evaluates DynaDiag primarily on ViT and MLP-Mixer architectures using vision datasets, with a single experiment on GPT-2 for text. The selected baselines include other common structured sparse-to-sparse methods and RigL as the sole representative of unstructured Dynamic Sparse Training (DST). While RigL is a strong baseline—often matching dense model performance in sparse training for vision tasks—expanding the evaluation to additional LLM architectures would strengthen the analysis.\nI recognize that pretraining larger LLMs may be computationally prohibitive, but exploring sparse-to-sparse finetuning (e.g., using LLaMA) could offer valuable insights. This would not only increase model diversity but also allow for comparisons with widely used pruning-based methods like Wanda and SparseGPT. Additionally, investigating the impact of dataset size could make the paper more relevant to the broader research community and enhance its impact.", "theoretical_claims": "The paper does not include theorems or proofs, the claims are evaluated via empirical experimentation.", "experimental_designs_or_analyses": "The experimental designs and analyses seem sound (Table 1, Table 2, Figure 4, Figure 1, Table 8). However, in terms of replicating the experiments, the Appendix lists the used hyperparameters in tables, but the section responsible for their summary (A.2.2) lacks reference to those tables. Furthermore, it would be beneficial to explain why such configurations were used (are they an effect of grid search, or maybe they were adapted from literature etc.)", "relation_to_broader_scientific_literature": "Dynamic Sparse Training (DST) is a well-established field focused on developing algorithms for training models that are sparse from initialization. The term “dynamic” refers to methods that adaptively modify the connectivity or sparse structure throughout training.\n\nThe core contribution of this paper is the introduction of a new structured DST algorithm. While prior structured DST approaches, such as SparseRigL, have been proposed and are discussed by the authors, I am not aware of any previous attempts that leverage the composition of diagonal matrices as presented here.\n\nMore broadly, in the context of sparsity in transformer-based models, this work is also relevant to pruning-at-initialization methods. Consequently, I believe the paper would benefit from a comparison with pruning approaches such as Wanda or SparseGPT to provide additional context and insights.", "essential_references_not_discussed": "I do not indicate any missing essential references at this point", "other_strengths_and_weaknesses": "Strengths:  \n-  The proposed method is built on an elegant idea of parametrizing linear projection matrices as a composition of diagonal matrices.\n-  It helps bridge the gap between unstructured Dynamic Sparse Training (e.g., RigL) and structured approaches while also reducing computational time, as measured in terms of wall-clock time.  \n-  The paper is well-structured and easy to follow. The core idea is simple yet elegant and shows great promise both in empirical evaluations and in its potential for real-world speedups.\n\nWeaknesses:  \n- I have discussed the weaknesses in the corresponding paragraphs above.", "other_comments_or_suggestions": "-", "questions_for_authors": "1. What is the precise contribution regarding the transformation to the BCSR format? The authors present this as a key contribution, but Section 3.3 leaves some ambiguity. Are they merely applying existing methods, or does their approach introduce novel aspects? Clarifying this is essential for assessing whether the paper fully delivers on its claims.  \n2. Could the evaluation be extended to sparse-to-sparse finetuning? (See Methods and Evaluation Criteria.) Including this aspect could  enhance my assessment of the experimental results.  \n\nClarification Questions (to ensure a proper understanding of the paper):\n\n  3. The paper states, \"We derive the per-layer sparsity budget from the global sparsity budget.\" How exactly is per-layer sparsity distributed, and how do different distribution strategies impact DynaDiag’s performance?  \n  4. Additionally, could the BCSR conversion influence overall performance? How would DynaDiag perform if implemented naïvely using simple masking instead?  \n\nMinor (curiosity-driven) Questions (unlikely to impact my overall score but still of interest):  \n\n   5. What effect do temperature and alpha initialization have on DynaDiag’s final results?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "vRqjETnjam", "reviewer": "Reviewer_NGkq", "summary": "This paper introduces DynaDiag, a structured Dynamic Sparse Training (DST) method that enforces a diagonal sparsity pattern in neural networks. The method aims to overcome the inefficiencies of unstructured sparsity, which struggles to translate into hardware acceleration. The authors propose a custom CUDA kernel to optimize computations, making DynaDiag more hardware-friendly.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments and feedback, especially about grounding our work in theoretical foundations. We address the questions and comments below:\n\n## LoRA-FA Finetuning\n\nWe used LoRA-FA (Sec 4.3.1) primarily to interpret the performance gap between RigL and DynaDiag by introducing limited unstructured sparsity. While we acknowledge that LoRA-FA introduces additional computational overhead at inference, this was purely an exploratory experiment rather than a core component of our method. To avoid confusion, we will rename the section to “Interpreting the gap between unstructured sparsity and DynaDiag” in the final version. \n\n## DynaDiag on CNNs\n\nWe agree with the reviewer, and we are working towards extending DynaDiag for CNNs. The current implementation of DynaDiag uses one $alpha$ vector for each linear layer. This approach is not scalable to a CNN directly as there are many weight matrices (filters) for each layer, and each matrix can have diagonals in different positions, resulting in an $alpha$ vector per filter and increasing the memory overhead.\n\n## Exploring Extreme Sparsity\n\nWe agree with the reviewer that it will be beneficial to compare DynaDiag’s performance with unstructured sparsity by scaling the models up. For such a study, we ideally need models that posses more than one diagonal when sparsity reaches levels such as 99.999\\%, where RigL has been shown to collapse [[1]](https://openreview.net/pdf?id=szRHR9XGrY). Our currently chosen models do not possess such properties, and hence, we welcom any suggestions from the reviewer on which models would be suitable for such a study.\n\n## Reporting Standard Deviations\n\nWe do not report std dev values at this stage as we find that our training is relatively stable for vision tasks and language tasks, which has previously been the case [[2]](https://openreview.net/pdf?id=MWZWUyfFHC). However, we plan to add more elaborate results to the final version of our manuscript.\nWe do, however, report the p-values from our statistical significance tests for all the experiments in Table 8, Table 9, and Table 10 in Appendix A.4.\n\n## Theoretical Explanation of DynaDiag’s Performance\n\nWe submit a theoretical justification of why diagonal sparsity works better than other structured sparsity patterns. \n\n**Theoretical Explanation:** We request the reviewer to check out our [theoretical explanation for DynaDiag’s performance](https://figshare.com/s/06ea8e6cf2c4b86f38f0).\n\n**Conclusion:** Briefly, we show that diagonal sparsity offers a full input-output coverage i.e. each row and column contains at least one non-zero entry in each weight matrix, even with a single diagonal). This:\n\n1) Preserves the rank of the matrix, maintaining the same expressivity as that of the dense matrix.\n2) Ensures global input-output connectivity and coverage, avoiding dimension collapse.\n3) Preserves theoretical guarantees of universal approximation capability.\n\n## Diagonal-to-BCSR Transformation\n\nWe request the reviewer to kindly check our [response to the Reviewer vAzp](https://openreview.net/forum?id=bAUVnNc0Ky&noteId=HoMgMLdsaV) under the section “BCSR Transformation and Contribution” and “Performance Impact of Diags to BCSR conversion (Q4)”, where we discuss how the conversion takes place and its impact on the performance.\n\n## Speedup at Lower Sparsities\n\nAt lower sparsity levels, we have a larger (but still less than dense) number of diagonals in all weight matrices. We see an increase in training time as compared to high sparsity due to the following overhead:\n\nDiag to BCSR conversion: We find that the time taken to convert a diagonal matrix to BCSR using our method is proportional to the number of diagonals in the matrix. For example, for a projection matrix (ViT-B/16) of size 768x768 in an attention block, the total conversion time varies as 4.35 us, 5.23 us, 7.78 us, and 10.53 us at sparsities 90%, 80%, 60%, and 50% respectively.\n\nDynaDiag can still accelerate inference at lower sparsities as the conversion of diagonal matrices to BCSR takes place offline and is done just once at the start of inference.\n\n## Writing Edits \n\nWe appreciate the reviewer’s feedback regarding clarity. We commit to improving:\n\n1) The description of random pruning in the introduction.\n\n2) Clarifying RigL’s growth strategy in Sec 2.2, Para 3.\n\nProper acknowledgment of SET approach in Sec 2.2, Para 4.\n\nVerifying and updating bolded values in tables to clearly reflect best-performing methods.\n\nThese edits will be included in the camera-ready version of our manuscript. We thank the reviewer again for their valuable input.", "claims_and_evidence": "The paper is generally clear, and the claims are supported by empirical evaluations on vision and language models. The reported inference acceleration (3.13×) and training speedup (1.59×) on GPUs at 90% sparsity is backed by experimental results. However, I question the necessity of LoRA-FA fine-tuning in the context of the paper's efficiency claims, as it introduces unstructured sparsity, which may counteract the structured sparsity benefits.", "methods_and_evaluation_criteria": "The proposed methods and evaluation criteria are generally appropriate, as they include evaluations on vision and language tasks across different architectures. However, analyzing the applicability of DynaDiag to CNN-based models could strengthen its claims, as CNNs are still widely used in real-world applications.", "theoretical_claims": "The paper presents a relatively good theoretical foundation, particularly in its proof of transposability for diagonal sparse matrices and Top-K selection mechanism. However, the justification for diagonal sparsity is weak. While inspired by small-world networks, the paper lacks an intuitive explanation for why diagonal sparsity performs better than other structured sparsity methods (e.g., block sparsity, N:M sparsity). A comparative theoretical analysis would be beneficial.", "experimental_designs_or_analyses": "No standard deviation for accuracy results. At extreme sparsity levels, instead of focusing solely on high sparsity, it might be more insightful to scale up the model first and then test at high sparsities while keeping the total parameter count comparable.", "relation_to_broader_scientific_literature": "The paper is well-situated within the broader field of Dynamic Sparse Training (DST) and relates well to prior work. However, some claims could be further refined with more details in the suggestions section.", "essential_references_not_discussed": "I did not find any critical missing references that significantly impact the understanding of the paper’s contributions.", "other_strengths_and_weaknesses": "### Strengths\n\n- This paper introduces a hardware-friendly approach that leverages the Block Compressed Sparse Row (BCSR) format to optimize GPU execution. While it successfully accelerates both inference and training, the full potential of sparsity speedup for training has yet to be fully realized.\n\n- The introduction of diagonal sparsity, inspired by small-world networks, enables the method to scale effectively for large ViT models and GPT-2, demonstrating its robustness across different architectures and modalities.\n\n### Weaknesses\n- It would be useful to include a theoretical comparison explaining why the diagonal sparsity pattern works better under certain conditions. The paper lacks a clear, intuitive explanation for why it performs better than other structured sparsity patterns and why it achieves performance comparable to unstructured sparsity.\n- Given that CNNs are still widely used in real-world applications, discussing the potential impact of DynaDiag on CNNs would strengthen the paper.\n- The necessity of LoRA-FA for improving DST efficiency in this paper is unclear. Since it introduces unstructured sparsity after fine-tuning (as mentioned in Section 4.3.1, Paragraph 3), how does it affect inference speedup?\n- How is the BCSR transformation performed, and how time-consuming is it? The effectiveness of this operation should be further analyzed, ideally with an ablation study comparing accuracy and computation time with and without the BCSR transformation. The lack of impact analysis weakens the discussion.\n- The paper lacks an in-depth analysis of speedup at lower sparsity levels. In this case, what causes slower training but faster inference?\n- Is it valuable to explore extreme sparsity levels if it only slightly outperforms RigL? How about scaling up the model first and then exploring extreme sparsity levels? Would it be more informative to maintain the same number of parameters under 90% sparsity for the original models and test both accuracy and computation time?", "other_comments_or_suggestions": "### Some sections are confusing:\n- In the beginning of the second paragraph, the description of randomly pruning weights is unclear and confusing.\n- In Section 2.2, Paragraph 3, RigL removes weights based on magnitude, while regrowth is based on gradient-this should be clarified.\n- In Section 2.2, Paragraph 4, Mocanu (2018) is an earlier work on DST, which should be acknowledged appropriately.\n- Bold text in all tables should be double-checked, as it may be misleading or confusing.", "questions_for_authors": "This paper introduces a new structured sparsity approach that improves both accuracy and hardware speedup, paving the way for advancements in the sparse training community. Please consider the provided comments, and these questions are open for discussion.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper aims to bridge the gap between hardware, software, and the theoretical potential with respect to the efficiency of dynamic sparse training (DST) methods by proposing a new structured sparse-to-sparse DST method named DynaDiag. The paper demonstrates that DynaDiag achieves comparable or improved performance relative to dense training and structured DST methods, while providing a 1.59× training speedup on GPU. The discussion between the reviewers and the authors was productive, and the paper's scores significantly improved after the rebuttal. Therefore, the Area Chair suggests acceptance and urges the authors to include all rebuttal discussions and experimental results in the final version of the paper.
Decision: Accept (poster)