Source-linked AI summary
Support Topology and Gradient Mixing in Sinkhorn Layers
Dylan Forde
TL;DR
Sparse Sinkhorn layers leave open how support topology controls gradient propagation through scaling iterations. The paper develops a fixed-support quotient calculus, proves topology- and plan-based mixing criteria including face-level obstructions, and extends them to scheduled supports, while restricting guarantees to the quotient-transport component.
Problem
The paper addresses how fixed support graphs control cotangent mixing, trapping, and residual-path behavior in Sinkhorn scaling, which ordinary topology descriptions leave unspecified.
Method
The paper derives exact half-step and cycle operators with source terms, then applies Dobrushin, minorization, face-lattice, and windowed certificates to fixed and scheduled supports.
Results
Every feasible transportation-polytope face must provide pairwise two-hop column overlap for score-uniform one-step contraction; otherwise finite score directions can make the coefficient arbitrarily close to one.
Takeaways & Limitations
Support design can be evaluated through quotient-gradient mixing certificates that distinguish topology-only guarantees from realized-plan guarantees and scheduled-window guarantees.
Takeaways & Limitations
The guarantees cover only the fixed-support quotient-transport component, not complete parameter-to-loss gradients without separate source- and map-norm bounds.
Abstract
from arXiv · showhide
Sparse Sinkhorn layers use a fixed support graph to restrict transport between tokens. How does this graph control gradient propagation through the scaling iterations. We develop a fixed-support calculus showing that each row-column cycle induces a row-stochastic operator on column-potential perturbations modulo constants. Its transpose propagates zero-mass reverse-mode cotangents. The finite-cycle operator uses two distinct half-step transport plans; at a balanced fixed point it reduces to a two-step walk determined by a single plan. We derive the accompanying score and marginal source terms and use Dobrushin contraction and minorization to bound homogeneous and source-driven tail cotangents. Our main result characterizes when support and marginals guarantee one-step contraction uniformly over finite scores: every feasible face of the transportation polytope must have pairwise two-hop column overlap. Otherwise, suitable score directions make the contraction coefficient arbitrarily close to one. We extend this analysis to ordered support schedules and derive certificates for partition heat-bath layers, coordinate sweeps, forced shared mass, and register-augmented supports. These results provide mathematical criteria for support design in differentiable transport layers, with guarantees restricted to the fixed-support quotient-gradient component.
1 Introduction
The paper asks how fixed or scheduled support topologies shape quotient-gradient mixing in Sinkhorn attention, rather than treating topology and differentiation separately. It develops support-sensitive certificates while restricting guarantees to the fixed-support quotient-transport component.
- Research question: The paper positions its calculus as complementary to local differentiated-surrogate methods by studying topology-induced quotient reverse dynamics.
- Design principle: Sparse transport topologies should be evaluated by quotient-gradient mixing, not only density, graph diameter, or token reachability.
- Motivation: Fixed support turns each Sinkhorn scaling cycle into an explicit reverse-mode transport operator whose mixing depends on topology and the realized plan.The coefficient is a derivative certificate, not merely a graph statistic.
- Certificate scope: The certificate distinguishes dense, local-window, disconnected, global-token, register-augmented, and residual topologies.In equal-score biregular settings it is graph-based; otherwise it depends on the scaled plan, distortion bounds, or mass-floor assumptions.
- Scope: The analysis targets fixed support, compatible positive marginals, finite active scores, and quotient cotangents.Source cotangents from neural parameters, values, attention maps, residuals, or losses require separate projection and norm bounds.
2 Fixed-Support Sinkhorn Calculus
The fixed-support calculus turns Sinkhorn linearization into a quotient Markov operator whose support is determined by two-hop column overlap. This yields exact topology criteria for contraction, while score-sensitive cycle structure and feasible boundary faces determine when those guarantees persist uniformly.
- Fixed-support operator: The finite-cycle reverse dynamics use distinct half-step plans, while balanced fixed points reduce the operator to a single-plan two-step walk.The transpose propagates zero-mass quotient cotangents; the finite-cycle kernel need not be reversible or stationary with respect to b.
- Derivative kernel: Mαβ > 0 exactly when columns α and β share an active row, so each kernel row records a two-hop column co-neighborhood.Strict positivity on active plan entries makes this support identity exact.
- Overlap criterion: τ(M) < 1 exactly when every pair of two-hop kernel rows has overlapping support; otherwise the one-step certificate equals one.This is a Dobrushin criterion for quotient-gradient contraction, not a generic graph statistic.
- Equal-score baseline: In the equal-score biregular case, M is exactly the two-step random walk on the bipartite support graph, making τ(M) a pure topology quantity.Multiple closed column-overlap components preserve a global coefficient of one, even when componentwise formulas hold.
- Score and cycle sensitivity: Score sensitivity is carried by non-additive cycle imbalance, and the quotient dimension of score patterns affecting the entropic plan equals the support cycle rank.Forest supports have zero cycle rank, so feasible plans and derivative kernels are fixed by support and marginals alone.
- Boundary obstructions: Bad feasible faces can force active edge masses to vanish in the limit, causing edgewise distortion relative to a positive reference plan to diverge.The paper therefore recommends ruling out bad faces or using realized-plan, windowed, or plan-distortion certificates.
- Score-uniform mixing: Uniform one-step contraction holds exactly when every nonempty feasible face has pairwise two-hop column overlap; a failing face allows finite scores with τ(M) arbitrarily close to one.The criterion is equivalent to a positive uniform overlap bound over finite-score Sinkhorn plans.
3 Dobrushin and Tail-Cotangent Certificates
Dobrushin coefficients contract zero-mass quotient cotangents through fixed-support Sinkhorn kernels, while projected source terms generate an inhomogeneous tail bound. Minorization and hub certificates provide practical contraction guarantees, but these results cover only the quotient-transport component and depend on realized plan masses.
- Homogeneous contraction: Dobrushin’s coefficient bounds the total-variation contraction of zero-mass cotangents under the transpose of any row-stochastic quotient kernel.The same argument extends to products of row-stochastic kernels through product coefficients.
- Source-driven tails: Projected source cotangents enter the reverse recurrence additively, producing a path/product sum bound for the inhomogeneous tail.The recurrence aggregates local score, marginal, value, residual, and feature branches after quotient projection.
- Implicit gradients: If a fixed-support quotient operator has τ(M) < 1, its implicit quotient VJP has a unique solution with ||η||TV ≤ ||ξ||TV/(1 − τ(M)).The same contraction controls truncation residuals through powers of M.
- Scope and limitations: The tail theorem rigorously covers fixed-support quotient transport, not complete parameter-to-loss gradients without separate source-norm and intervening-map bounds.Projection is the adjoint of the chosen quotient lift rather than an additional Sinkhorn transpose step.
- Minorization certificates: A common row component of mass γ certifies τ(M) ≤ 1 − γ, and mass-floored hub columns instantiate this bound with γH.The hub result is quantitative only when the realized scaled plan supplies the required mass floor.
- Scope and limitations: The certificates are kernel-level guarantees: support suggests overlap, but scores and marginal masses determine the realized shared component and contraction bound.Dense support alone does not prevent τ(M) from approaching one without a mass floor or equivalent score and marginal assumptions.
4 Negative and Windowed Topology Certificates
One-step contraction can fail for disconnected, permutation-like, and sparse supports, but ordered support products can restore quotient mixing. Partition and coordinate-resampling layers provide exact examples where individual layers have τ=1 while a full window contracts perfectly.
- τ(M) = 1 for closed components with disjoint transition supports, so the one-step certificate provides no global quotient contraction.
- Permutation-like kernels with distinct point-mass rows have τ(M) = 1 and preserve some quotient cotangent modes exactly.
- Windowed pairwise product overlap across every feasible face tuple is equivalent to a positive score-uniform contraction bound for ordered support schedules.
- τ(M_t) = 1 for every layer can coexist with τ(M_K · · · M_1) < 1 when successive kernels mix different partitions.A four-state example has each layer at τ=1, while their product sends every row to the uniform distribution and has coefficient zero.
- Partition-supported transport layers induce heat-bath kernels, so products of such layers inherit the corresponding windowed Dobrushin certificates.
- Coordinate-resampling layers can withhold every one-step contraction certificate while applying each coordinate once yields 1_b⊤ and τ = 0.
- The hypercube butterfly realizes this pattern: every bit-flip layer has τ(M_t) = 1, but the full r-layer product has zero Dobrushin coefficient.
5 Support-Schedule Design Consequences
Support design should be evaluated through feasible-face overlap and ordered quotient-kernel products, not only individual-layer connectivity. Local windows may need windowed certificates, while registers and layered schedules help only under conditions that force shared mass or product overlap.
- Support design is governed by feasible faces and row-overlap of induced Markov kernels.
- Local windows can be connected yet lack one-step contraction, requiring powered or windowed certificates.
- Register or dustbin rows help only when realized plans or marginal constraints force genuine common mass.
- Layered sparse schedules can mix globally even when every individual layer has τ = 1.
6 Computational Complexity of Certificates
Certificate computation can become dense even when the transport support is sparse. Exact kernel construction, Dobrushin evaluation, window products, and face-lattice checking therefore require targeted offline or structural methods.
- A dense row or enough sparse rows covering all column pairs yields nnz(M) = n^2 and O(n^2) storage even when P is sparse.
- Exact Dobrushin evaluation costs O(n^3) time and O(n^2) memory for dense kernels.
- With sparse rows, merging row supports costs O(s_α + s_β), but the all-pairs bound is O(n nnz(M)) and becomes O(n^3) after densification.
- Exact window products may densify after a few layers, so they are intended for small or offline validation unless structural alternatives apply.
- Face-lattice checking is exponential in active edges because it quantifies over every nonempty face, making tractable family theorems and realized-plan certificates practical alternatives.
7 Discussion
The theory separates exact fixed-support quotient dynamics, tail contraction bounds, and topology-level support criteria. Its quantitative guarantees depend on specific regimes such as equal scores, forced capacities, realized plans, or plan distortion.
- The half-step calculus gives an exact quotient Markov operator with explicit source terms, while Dobrushin coefficients bound homogeneous residuals and projected-source path sums.
- Equal-score biregular supports reduce the analysis to explicit graph walks, while the face-lattice dichotomy characterizes score-uniform one-step mixing.
- The face-lattice and product-coordinate theorems rely on primal entropy-center face convergence, compactness, and support overlap.
- The quantitative regimes are equal-score, forced-capacity, realized-plan, and plan-distortion analyses.
8 Conclusion
The paper develops a fixed-support calculus for quotient transport derivatives, turning support schedules into rigorous contraction and mixing certificates.
- Fixed-support proofs characterize quotient-transport dynamics through explicit operators, limits, computational costs, and certificate-level validation.
A Spectral Architecture Corollaries
Spectral and Dobrushin certificates connect support topology to reverse-mode mixing and tail depth. Circular local bands can mix diffusively or fail to contract in one step, whereas expander-like overlap can yield stronger contraction.
- Spectral certificates: In the equal-score biregular baseline, the derivative kernel is symmetric and doubly stochastic, enabling spectral contraction bounds on zero-mass cotangents.
- Architecture implications: Graph design becomes tail-depth design: expander-like column-overlap walks favor small λ⋆, while butterfly-like supports may require powered certificates.
- Spectral certificates: A zero-mass spectral rate λ⋆≤ρ<1 yields an expander tail-depth rule, with powered kernels providing contraction after sufficient cycles.
- Circular local bands: Circular local-band kernels are circulant, with Fourier eigenvalues determined by the band autocorrelation and Dirichlet-kernel structure.
- Circular local bands: For fixed-radius circular bands, the first nonconstant Fourier mode mixes diffusively, and no subquadratic depth uniformly contracts all zero-mass modes.
- Circular local bands: If n≥8r+2, a circular local band has one-step Dobrushin coefficient τ(M)=1 because some derivative neighborhoods are disjoint.
B Registers, Dustbins, and Shared Buses
Shared register, dustbin, and bus structures create common derivative-kernel mass that can certify contraction beyond narrow local supports. Quantitative guarantees remain tied to the realized plan and stated score or marginal assumptions.
- Shared buses: Global tokens, registers, dustbins, and expert buses can route reverse-mode mass through a shared component, preventing perfect isolation of zero-mass cotangents.
- Register certificates: A realized common mass on register targets yields a sparse-support overlap certificate τ(M)≤1−γreg.
- Equal-score construction: The equal-score register-bus construction uses regular token-token support, register rows and columns, uniform marginals, and a four-value Sinkhorn plan.
- Equal-score construction: The proposed scaling is feasible because token and register row and column sums match the uniform marginal under the defining quadratic for t.
- Scope and limitations: The register-bus guarantee is quantitative only under the stated equal-score setting or a separate realized-plan, distortion, or mass-floor certificate.
- Design implication: Adding a small register budget can reduce τ(M) when the scaled plan routes enough mass through the shared component, but this is not a task-accuracy proof.
C Certificate-Level Design Rules
The paper presents certificate logic rather than accuracy claims and proposes a workflow for stress-testing support designs before downstream use.
- The results establish certificate logic for fixed-support transport derivatives rather than task-accuracy claims.
- A matched-edge workflow compares equal-score graph walks, realized powered contraction, local-band controls, and robustness to marginal and score perturbations.
D Short DAG Path-Sum Remark
The remark extends quotient bookkeeping to residual or branching graphs when edge maps have explicitly bounded operator norms. It separates zero-mass path-sum propagation from the treatment of inhomogeneous source terms.
- Residual or branching graphs remain outside the core chain theorem, but quotient bookkeeping applies when every edge map has a bounded operator norm.The bound must be stated on the chosen quotient representative.
- Zero-mass cotangents along finite sink-to-source path sums are handled using Theorem 6 and the triangle inequality.
- Inhomogeneous source terms require separate projection and bounding under Theorem 7.The passage characterizes this as bookkeeping rather than an additional architecture claim.