New solver accelerates Birkhoff projection 20x for hyper-connections
Researchers replace Sinkhorn-Knopp with Newton's method and implicit differentiation, achieving 20x speedup.
Manifold-constrained hyper-connections (mHCs) improve neural network stability by constraining residual mixing matrices to be doubly stochastic via projection onto the Birkhoff polytope. Current implementations rely on Sinkhorn-Knopp iterations for the forward pass and unrolled differentiation for the backward pass, introducing significant computation and memory overhead, and producing inaccurate projections for challenging inputs. This paper targets the practical 4x4 Birkhoff projection setting, developing an end-to-end acceleration framework.
By leveraging the dual formulation, the authors reduce the problem to a three-dimensional unconstrained convex problem solved with Newton's method, achieving fast convergence and high accuracy. For the backward pass, they replace unrolled differentiation with implicit differentiation, yielding exact gradients without storing intermediate states. A custom warp-level CUDA kernel uses only register-level primitives, avoiding global and shared memory I/O. Extensive benchmarks show the solver yields substantially more reliable doubly stochastic projections—especially when input magnitude is large—and achieves over 20x end-to-end speedup at large batch sizes while maintaining orders of magnitude smaller marginal errors.
- Replaces Sinkhorn-Knopp iterations with Newton's method on a 3D convex dual for 4x4 Birkhoff projection
- Uses implicit differentiation for backward pass, eliminating memory overhead from unrolled differentiation
- Custom warp-level CUDA kernel with register primitives achieves >20x speedup at large batch sizes
Why It Matters
Faster, more accurate manifold constraints enable scalable hyper-connections in large neural networks, improving training stability and efficiency.