Block-Wise Differentiable Sinkhorn Attention: Tail-Refinement Gradients with a Single-Active-Dustbin Bridge
Dylan B. Forde · 2026
Read Block-Wise Differentiable Sinkhorn Attention: Tail-Refinement Gradients with a Single-Active-Dustbin Bridge by Dylan B. Forde (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-08123.txt.
Introduction
Dylan Forde studies how to train attention layers built on optimal transport, where a Sinkhorn solver balances attention weights across long contexts. Running the solver inside training is costly on TPU hardware, and gradients through many solver steps are awkward to compute exactly.
Forde splits the solve into a stopped base phase and a short refinement tail, then differentiates only the surrogate tail. For the reported two-step path, the backward pass collapses to one reference plan tile times an explicit modifier field, giving block-wise costs and small extra memory. A dustbin bridge extends the same schedule to the augmented support used in the TPU runs.
Catalog record
| CREATOR | Dylan B. Forde |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 59 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.08123
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Block-Wise Differentiable Sinkhorn Attention: Tail-Refinement Gradients with a Single-Active-Dustbin Bridge Dylan B. Forde Abstract We study long-context balanced entropic optimal transport (OT) attention on TPU hardware through a stopped-base, fixed-depth tail-refinement surrogate. After a stopped T T -step Sinkhorn solve, we unroll a short refinement tail and differentiate that surrogate exactly. For the reported R = 2 R=2 TPU path, the backward pass contains four staircase plan factors. We prove an exact one-reference-tile schedule: the R = 2 R=2 score cotangent is a single reference plan tile times an explicit modifier field built from vector cotangents and dual differences. This yields block-wise cost O ( ( T + R ) L W ) O((T+R)LW) , O ( L d ) O(Ld) input storage, and O ( L ) O(L) additional HBM usage for fixed head dimension d d and band width W W on the balanced fixed-support path. We also formalize the current dustbin_block path as the same unit-target surrogate on an augmented support, so the adjoint schedule lifts to the single-active-dustbin path used in our TPU runs; this bridge is algebraic and does not claim a general KL-unbalanced or arbitrary-capacity gap model. We provide a local surrogate-bias bound, an a posteriori bias certificate, and a projective contraction certificate for strictly positive active blocks. On synthetic masked problems, the optimized kernel matches exact autodiff of the same centered surrogate to within 10 − 5 10^{-5} – 10 − 10 10^{-10} . On TPU v6e-8, a four-configuration Pfam screen completes end-to-end, and a promoted balanced R = 2 R=2 run sustains roughly 8.5 8.5 examples per second through a three-hour budget, reaching step 1437 1437 . Held-out Pfam test shards improve reconstruction from 5.57 5.57 to 2.05 2.05 and sparse CE from 5.53 5.53 to 5.30 5.30 relative to step 0 0 , with CE logged diagnostically rather than optimized directly; target-barycenter alignment metrics do not materially improve, and a deterministic diagonal reference remains stronger on those metrics. These results support exact fixed-depth backward theory, centered-kernel validation, and scoped trainability evidence for the reported TPU path. 1 Introduction Pairwise alignment and structural matching remain central problems for sequence modeling. Classical dynamic-programming methods such as Smith–Waterman ( Smith and Waterman 1981 ) provide optimal alignments but are not differentiable, so they cannot be inserted directly into end-to-end neural architectures. Entropic optimal transport (OT) offers a natural differentiable relaxation ( Cuturi 2013 ; Peyré and Cuturi 2019 ) : it replaces a discrete assignment with a smooth transport plan computed by Sinkhorn scaling. For long-context models, however, two bottlenecks dominate. First, dense OT attention materializes L\times L scores or plans, which is prohibitive at large L . Second, backward-pass design is difficult. Exact autodiff through many Sinkhorn steps is expensive and memory-hungry, while implicit differentiation can require large and unstable linear solves ( Luise et al. 2018 ; Bai et al. 2019 ) . The key question is therefore not only how to make OT attention differentiable, but how to make its differentiated object explicit, exact for the surrogate actually used, and compatible with accelerator kernels. We address this with a stopped-base, fixed-depth tail-refinement surrogate . After a stopped T -step balanced Sinkhorn solve, we append a short differentiable tail of depth R and differentiate that surrogate exactly. The reported TPU path uses R=2 . A direct implementation of the exact R=2 adjoint must evaluate four distinct staircase plan factors. The signature implementation observation of the paper is that these factors lie in a single row/column scaling orbit, so each block can be evaluated from one reference transport tile plus vector modifiers, avoiding separate plan-tile formation for the remaining three terms. Single-active-dustbin bridge. The central factorization is balanced and fixed-support. The first extension carried in the unified manuscript is intentionally narrow: the current dustbin_block path is not treated as a new OT solver, but as the same unit-target surrogate on an augmented state space with one active dustbin token per side. This keeps the implemented dustbin path inside the algebraic orbit of the main factorization, while leaving general gap-capacity and KL-unbalanced transport models to future work. Related context. Our work is closest in spirit to recent efforts to make OT-style attention practical at accelerator scale, including FlashSinkhorn ( Ye et al. 2026 ) . The comparison separates along two axes. FlashSinkhorn is an IO-aware solver for streaming entropic OT updates; our contribution is the differentiated stopped-base backward object. In particular, a direct R=2 adjoint must evaluate four distinct staircase plan factors, whereas our transport-orbit calculus evaluates each block from one reference transport tile plus vector modifiers. This does not replace a direct solver-level benchmark against FlashSinkhorn, a matched trained-attention baseline, or a direct four-plan-adjoint TPU benchmark. Fair Pfam comparisons must match the sampler, projection, objective, mask, evaluator, and runtime; the current bundle does not contain a FlashSinkhorn-on-Pfam adapter, trained attention checkpoint, or TPU direct-adjoint result. We therefore treat those as pending benchmarks rather than negative results and do not claim wall-clock dominance. The present paper instead establishes the exact factorized backward object and its TPU realization on the alignment stack used in our experiments. The approach is also complementary to long-context transformer architectures that obtain efficiency through structured sparsity rather than transport constraints, such as Longformer ( Beltagy et al. 2020 ) and BigBird ( Zaheer et al. 2020 ) . The paper makes three main contributions: • an explicit balanced fixed-support tail-refinement surrogate together with its exact R=2 adjoint and one-reference-tile backward schedule; • a theorem-aligned single-active-dustbin augmentation showing that the current dustbin transport path is the same unit-target surrogate on an enlarged state space; • an empirical bridge from exactness validation to TPU-scale training, comprising a completed four-configuration Pfam screen, a promoted long-budget balanced run, and a held-out checkpoint evaluation on Pfam test shards. 2 Method 2.1 Forward Pass: Block-Wise Balanced Sinkhorn Let Q,K,V be query, key, and value tensors with head dimension d , and let \Omega denote a fixed active support with band width W . We absorb the entropic temperature \varepsilon into the score matrix S_{ij}=\frac{Q_{i}K_{j}^{\top}}{\sqrt{d}\,\varepsilon}. The stopped base solve and the refinement tail both use the same masked balanced half-steps \displaystyle u_{i}^{(t+1)} \displaystyle=-\log\!\Bigl[\sum_{j:(i,j)\in\Omega}\exp(S_{ij}+v_{j}^{(t)})\Bigr], (1) \displaystyle v_{j}^{(t+1)} \displaystyle=-\log\!\Bigl[\sum_{i:(i,j)\in\Omega}\exp(S_{ij}+u_{i}^{(t+1)})\Bigr]. (2) These are unit-target updates: each active row and active column target mass is one. When the active row and column counts are equal, this is the usual compatible balanced OT normalization. On rectangular masked Pfam examples, the implementation still uses this same unit-target Sinkhorn attention map; it should be read as the differentiable transport surrogate actually evaluated by the code, not as a compatible-marginal balanced OT problem with unequal total masses. The implementation computes these updates in tiles, in the same spirit as IO-aware attention kernels. For fixed band width W , a T -step base solve followed by an R -step tail has cost O((T+R)LW) time, O(Ld) input storage, and O(L) additional HBM usage. Remark 1 (Fixed-Budget \varepsilon -Scaling) . The implementation optionally uses a short continuation schedule \varepsilon_{1}\geq\cdots\geq\varepsilon_{S}=\varepsilon during the stopped base solve. If the stage iteration counts satisfy \sum_{s=1}^{S}T_{s}=T , the asymptotic cost remains O(TLW) time and O(L) additional HBM memory for fixed head dimension. 2.2 Balanced Tail Refinement and