Rethinking Dense Linear Transformations: Stagewise Pairwise Mixing (SPM) for Near-Linear Training in Neural Networks

• URL: http://arxiv.org/abs/2512.23905v1
• Date: Tue, 30 Dec 2025 00:03:22 GMT
• Title: Rethinking Dense Linear Transformations: Stagewise Pairwise Mixing (SPM) for Near-Linear Training in Neural Networks
• Abstract summary: We introduce Stagewise Pairwise Mixers (SPM), a structured linear operator that replaces dense matrices with a composition of sparse pairwise-mixing stages.<n>We show substantial reductions in wall-clock cost and improved accuracy on structured learning problems, while retaining competitive performance on real-world benchmarks.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Dense linear layers are a dominant source of computational and parametric cost in modern machine learning models, despite their quadratic complexity and often being misaligned with the compositional structure of learned representations. We introduce Stagewise Pairwise Mixers (SPM), a structured linear operator that replaces dense matrices with a composition of sparse pairwise-mixing stages. An SPM layer implements a global linear transformation in $O(nL)$ time with $O(nL)$ parameters, where $L$ is typically constant or $log_2n$, and admits exact closed-form forward and backward computations. SPM is designed as a drop-in replacement for dense linear layers in feedforward networks, recurrent architectures, attention mechanisms, etc. We derive complete forward and backward expressions for two parameterizations: an orthogonal norm-preserving rotation-based variant and a fully general $2 \times 2$ mixing variant. Beyond computational savings, the stagewise structure of SPM induces an explicit compositional inductive bias that constrains model capacity and improves generalization when aligned with task structure. We present proof-of-concept experiments demonstrating substantial reductions in wall-clock cost and improved accuracy on structured learning problems, while retaining competitive performance on real-world benchmarks.

Related papers

• Looped SSMs: Depth-Recurrence and Input Reshaping for Time Series Classification [50.994194925685434]
  We show that a looped SSM with $k$ parameters iterated $L$ times consistently closely matches or outperforms a standard SSM.<n>We also show that input reshaping is an equally neglected design axis.
  arXiv  Detail & Related papers  (2026-05-15T15:18:12Z)
• High-dimensional Adaptive MCMC with Reduced Computational Complexity [0.8594140167290097]
  We propose an adaptive MCMC method that learns a linear preconditioner which is dense in its off-diagonal elements but sparse in its parametrisation.<n>We show that it outperforms diagonal preconditioning in terms of absolute performance.
  arXiv  Detail & Related papers  (2026-04-10T12:58:00Z)
• go-$m$HC: Direct Parameterization of Manifold-Constrained Hyper-Connections via Generalized Orthostochastic Matrices [0.0]
  We introduce a novel exact parameterization grounded in the theory of generalized orthostochastic matrices.<n>We instantiate this parameterization in go-$m$HC.<n>Our method composes naturally with Kronecker-factorized methods, substantially recovering expressivity at similar FLOP costs.
  arXiv  Detail & Related papers  (2026-04-02T17:51:19Z)
• Differentiable Sparsity via $D$-Gating: Simple and Versatile Structured Penalization [22.883367233817836]
  We show that $D$-Gating is theoretically equivalent to solving the original group sparsity problem.<n>We validate our theory across vision, language, and tasks, where $D$-Gating consistently delivers strong performance-sparsity tradeoffs.
  arXiv  Detail & Related papers  (2025-09-28T14:08:29Z)
• Structured Sparse Transition Matrices to Enable State Tracking in State-Space Models [68.31088463716269]
  We propose a structured sparse parametrization of transition matrices in state-space models (SSMs)<n>Our method, PD-SSM, parametrizes the transition matrix as the product of a column one-hot matrix ($P$) and a complex-valued diagonal matrix ($D$)<n>The model significantly outperforms a wide collection of modern SSM variants on various FSA state tracking tasks.
  arXiv  Detail & Related papers  (2025-09-26T12:46:30Z)
• Tensor Decomposition Networks for Fast Machine Learning Interatomic Potential Computations [48.46721044282335]
  tensor decomposition networks (TDNs) achieve competitive performance with dramatic speedup in computations.<n>We evaluate TDNs on PubChemQCR, a newly curated molecular relaxation dataset containing 105 million DFT-calculated snapshots.<n>Results show that TDNs achieve competitive performance with dramatic speedup in computations.
  arXiv  Detail & Related papers  (2025-07-01T18:46:27Z)
• Scaling Up Liquid-Resistance Liquid-Capacitance Networks for Efficient Sequence Modeling [50.994194925685434]
  LrcSSM is a $textitnon-linear$ recurrent model that processes long sequences as fast as today's linear state-space layers.<n>By forcing its Jacobian matrix to be diagonal, the full sequence can be solved in parallel.<n>LrcSSM offers a formal gradient-stability guarantee that other input-varying systems such as Liquid-S4 do not provide.
  arXiv  Detail & Related papers  (2025-05-27T20:02:59Z)
• Structured Linear CDEs: Maximally Expressive and Parallel-in-Time Sequence Models [15.650005330621148]
  This work introduces Structured Linear Controlled Differential Equations (SLiCEs)<n>It is a unifying framework for sequence models with structured, input-dependent state-transition matrices.<n>We prove that SLiCEs employ block-diagonal, sparse, or Walsh-Hadamard matrices.
  arXiv  Detail & Related papers  (2025-05-23T11:34:21Z)
• The Sample Complexity of Online Reinforcement Learning: A Multi-model Perspective [55.15192437680943]
  We study the sample complexity of online reinforcement learning in the general setting of nonlinear dynamical systems with continuous state and action spaces.<n>Our algorithm achieves a policy regret of $mathcalO(N epsilon2 + mathrmln(m(epsilon)/epsilon2)$, where $epsilon$ is the time horizon.<n>In the special case where the dynamics are parametrized by a compact and real-valued set of parameters, we prove a policy regret of $mathcalO(sqrt
  arXiv  Detail & Related papers  (2025-01-27T10:01:28Z)
• In-context Learning for Mixture of Linear Regressions: Existence, Generalization and Training Dynamics [34.458004744956334]
  We prove that there exists a transformer capable of achieving a prediction error of order $mathcalO(sqrtd/n)$ with high probability.<n>We also analyze the training dynamics of transformers with single linear self-attention layers, demonstrating that, with appropriately parameters, gradient flow optimization over the population mean square loss converges to a global optimum.
  arXiv  Detail & Related papers  (2024-10-18T05:28:47Z)
• Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
  We consider the problem of learning an $varepsilon$-optimal policy in a general class of continuous-space Markov decision processes (MDPs) having smooth Bellman operators. Key to our solution is a novel projection technique based on ideas from harmonic analysis. Our result bridges the gap between two popular but conflicting perspectives on continuous-space MDPs.
  arXiv  Detail & Related papers  (2024-05-10T09:58:47Z)
• Transformers as Support Vector Machines [54.642793677472724]
  We establish a formal equivalence between the optimization geometry of self-attention and a hard-margin SVM problem. We characterize the implicit bias of 1-layer transformers optimized with gradient descent. We believe these findings inspire the interpretation of transformers as a hierarchy of SVMs that separates and selects optimal tokens.
  arXiv  Detail & Related papers  (2023-08-31T17:57:50Z)
• The Generalization Error of Stochastic Mirror Descent on Over-Parametrized Linear Models [37.6314945221565]
  Deep networks are known to generalize well to unseen data. Regularization properties ensure interpolating solutions with "good" properties are found. We present simulation results that validate the theory and introduce two data models.
  arXiv  Detail & Related papers  (2023-02-18T22:23:42Z)
• Improving the Sample-Complexity of Deep Classification Networks with Invariant Integration [77.99182201815763]
  Leveraging prior knowledge on intraclass variance due to transformations is a powerful method to improve the sample complexity of deep neural networks. We propose a novel monomial selection algorithm based on pruning methods to allow an application to more complex problems. We demonstrate the improved sample complexity on the Rotated-MNIST, SVHN and CIFAR-10 datasets.
  arXiv  Detail & Related papers  (2022-02-08T16:16:11Z)
• A Fast Parallel Tensor Decomposition with Optimal Stochastic Gradient Descent: an Application in Structural Damage Identification [1.536989504296526]
  We propose a novel algorithm, FP-CPD, to parallelize the CANDECOMP/PARAFAC (CP) decomposition of a tensor $mathcalX in mathbbR I_1 times dots times I_N $.
  arXiv  Detail & Related papers  (2021-11-04T05:17:07Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.