arXiv:2608.11760 2026 Optimization 2 ideas extracted · analyzed Sep 1, 2026
The paper identifies a computable local contraction factor for Sinkhorn-Knopp scaling that is much sharper than worst-case global bounds. For target row marginal p and column marginal q, the rate is governed by the second-largest eigenvalue of a symmetric normalized matrix built from the optimally scaled attention kernel, with contraction factor 1-\sigma_2. This suggests making Sinkhorn normalization in attention adaptive rather than using a fixed iteration count: estimate the local spectral contraction from marginal residuals, stop when the predicted residual is below tolerance, and optionally train kernels with larger spectral gaps. The main potential benefit is reduced normalization cost with unchanged marginal accuracy and improved numerical stability.
Replace the fixed number of Sinkhorn iterations used to normalize an attention kernel with a per-example stopping rule based on the local spectral contraction factor. Estimate the remaining marginal error geometrically and stop early on easy examples while retaining extra iterations on difficult or nearly disconnected examples.
Train attention logits so that the associated Sinkhorn-scaled operator has a favorable local spectral gap, making iterative normalization contract faster. Add a differentiable penalty on the second eigenvalue of the normalized operator while retaining the task loss and marginal-feasibility loss.