LBI: Parallel Scan Backpropagation via Latent Bounded Interfaces

• URL: http://arxiv.org/abs/2605.09204v1
• Date: Sat, 09 May 2026 22:46:46 GMT
• Title: LBI: Parallel Scan Backpropagation via Latent Bounded Interfaces
• Abstract summary: We introduce Latent Bounded Interfaces (LBI), an algorithmic formulation that makes scan-based backpropagation tractable.<n>LBI reduces the adjoint recursion to a suffix scan over $r times r$ Jacobians, cutting per-combine cost from $O(d3)$ to $O(r3)$.<n>We demonstrate that LBI maintains model quality across four architectures (Mamba-2, Mamba-3, Transformer, and a Mamba--Transformer hybrid) at 47--61M block parameters.
• Score: 1.8179911892344436
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: Backpropagation is inherently sequential across depth, creating an $O(K)$-deep dependency chain that bottlenecks parallel training. While parallel-scan formulations theoretically reduce this depth to $O(\log K)$, they are computationally prohibitive for modern architectures due to the $O(d^3)$ cost of composing full-rank $d\times d$ Jacobians over the entire hidden state. We introduce Latent Bounded Interfaces (LBI), an algorithmic formulation that makes scan-based backpropagation tractable by restricting inter-region communication to a low-dimensional latent interface, $ m_k \in \mathbb{R}^{r}$, where $r \ll d$. This reduces the adjoint recursion to a suffix scan over $r \times r$ Jacobians, cutting per-combine cost from $O(d^3)$ to $O(r^3)$ while preserving exact gradients under the bounded-interface model. We demonstrate that LBI maintains model quality across four architectures (Mamba-2, Mamba-3, Transformer, and a Mamba--Transformer hybrid) at 47--61M block parameters. Interfaces of dimension $r=16$ suffice to preserve training quality within 0.16--0.35 cross entropy of dense baselines. The resulting framework provides an algorithmic foundation for region-parallel training, reducing cross-device backward communication to a single scan over $K$ fixed-size matrices, of approximately 56 KB for our experimental configurations.

Related papers

• SILAGE: Memory-Efficient, Full-Gradient-Free Nonconvex Optimization for Nested Finite Sums [51.49970814177172]
  Empirical risk on datasets naturally exhibits similarities in $N=nm$ total samples.<n>We provide an analysis that avoids pessimistic convergence analysis.<n>Our results improve existing state-of-the-art regimes.
  arXiv  Detail & Related papers  (2026-06-14T14:11:07Z)
• Scaling Neural Network Verification with Tensor Parallelism and Fully Sharded Data Parallelism [0.0]
  Formal neural network verification is bounded in practice by GPU memory.<n>We adapt two techniques originally developed for large-scale model training to the auto_LiRPA / $,$-CROWN verification framework.<n>Fully Sharded Data Parallelism (FSDP) shards only weight matrices with a per-layer AllGather, producing bounds that are bitwise identical to the single- GPU baseline.
  arXiv  Detail & Related papers  (2026-06-08T11:56:29Z)
• Efficient Mean Curvature Computation on High-Dimensional Data Manifolds [52.452902154360565]
  Estimating local mean curvature at each point of a high-dimensional dataset is a key ingredient of machine learning algorithms.<n>This paper introduces two complementary contributions that together reduce this cost by several orders of magnitude.<n> Experiments on real-world datasets confirm speedups of 50 to 300 times relative to the original implementation.
  arXiv  Detail & Related papers  (2026-06-04T16:04:31Z)
• Scaling Federated Linear Contextual Bandits via Sketching [49.12000877146222]
  This paper proposes Federated Sketch Contextual Linear Bandits (FSCLB)<n>Experiments on both synthetic and real-world datasets show that FSCLB significantly reduces computational and communication costs by over 90 %.
  arXiv  Detail & Related papers  (2026-05-01T08:22:06Z)
• Learning Hippo: Multi-attractor Dynamics and Stability Effects in a Biologically Detailed CA3 Extension of Hopfield Networks [0.0]
  We present a biologically detailed extension of the classical Hopfield/Marr auto-associative memory model for CA3.<n>We implement ten populations (two asymmetric pyramidal subtypes, eight GABAergic interneuron classes), forty-seven compartments, multi-rule plasticity, and a bimodal cholinergic encoding/consolidation cycle.
  arXiv  Detail & Related papers  (2026-04-22T15:28:17Z)
• Evolution Strategies at the Hyperscale [57.75314521465674]
  We introduce EGGROLL, an evolution strategies (ES) algorithm designed to scale backprop-free optimization to large population sizes.<n>ES is a set of powerful blackbox optimisation methods that can handle non-differentiable or noisy objectives.<n>EGGROLL overcomes these bottlenecks by generating random matrices $Ain mathbbRmtimes r, Bin mathbbRntimes r$ with $rll min(m,n)$ to form a low-rank matrix perturbation $A Btop$
  arXiv  Detail & Related papers  (2025-11-20T18:56:05Z)
• 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)
• Trading-off Accuracy and Communication Cost in Federated Learning [5.83744681136074]
  We develop a training-by-pruning protocol that achieves a 34-fold reduction in communication cost.<n>We establish a novel link between training-by-sampling and random convex geometry.
  arXiv  Detail & Related papers  (2025-03-18T13:35:24Z)
• Demystifying Linear MDPs and Novel Dynamics Aggregation Framework [8.087699764574788]
  In linear MDPs, the feature dimension $d$ is lower bounded by $S/U$ in order to aptly represent transition probabilities. We propose a novel structural aggregation framework based on dynamics, named as the "dynamics aggregation" Our proposed algorithm exhibits statistical efficiency, achieving a regret of $ tildeO ( d_psi3/2 H3/2sqrt T)$, where $d_psi$ represents the feature dimension of aggregated subMDPs.
  arXiv  Detail & Related papers  (2024-10-31T16:21:41Z)
• 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)
• Differentially Private Exploration in Reinforcement Learning with Linear Representation [102.17246636801649]
  We first consider the setting of linear-mixture MDPs (Ayoub et al., 2020) (a.k.a. model-based setting) and provide an unified framework for analyzing joint and local differential private (DP) exploration. We further study privacy-preserving exploration in linear MDPs (Jin et al., 2020) (a.k.a. model-free setting) where we provide a $widetildeO(sqrtK/epsilon)$ regret bound for $(epsilon,delta)
  arXiv  Detail & Related papers  (2021-12-02T19:59:50Z)
• Deep Learning Meets Projective Clustering [66.726500395069]
  A common approach for compressing NLP networks is to encode the embedding layer as a matrix $AinmathbbRntimes d$. Inspired by emphprojective clustering from computational geometry, we suggest replacing this subspace by a set of $k$ subspaces.
  arXiv  Detail & Related papers  (2020-10-08T22:47:48Z)
• Fixed-Support Wasserstein Barycenters: Computational Hardness and Fast Algorithm [100.11971836788437]
  We study the fixed-support Wasserstein barycenter problem (FS-WBP) We develop a provably fast textitdeterministic variant of the celebrated iterative Bregman projection (IBP) algorithm, named textscFastIBP.
  arXiv  Detail & Related papers  (2020-02-12T03:40:52Z)

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.