acceptodds
Under review as a conference paper at ICLR 2027

LOTFormer: Doubly Stochastic Linear Attention via Low Rank Optimal Transport

Abstract

Standard softmax attention is row stochastic and scales quadratically with sequence length. Doubly stochastic attention also controls aggregate key participation, but computing it is typically expensive. We introduce LOTFormer, an efficient attention mechanism designed for bidirectional Transformers, where tokens act as both information sources and receivers. LOTFormer routes interactions through a learned low rank pivot measure and composes two entropic transport couplings. The resulting ideal attention operator is doubly stochastic, has rank at most , and applies to values in time without forming the full pairwise matrix. We evaluate the method both as a replacement for attention in pretrained embedding models and as an attention mechanism trained in vision Transformers. Across embedding models from 1.5B to 7B parameters, LOTFormer preserves to of the original softmax retrieval quality. On four natural LongEmbed tasks, gte Qwen2 7B retains of its original nDCG@10. In a separate throughput stress test at 128k tokens, it achieves a speedup over softmax. LOTFormer also performs competitively across multiple vision backbones and under limited supervision. These results demonstrate a practical route to efficient bidirectional attention with doubly stochastic structure. Code is available at https://github.com/anonymous13761234/LOTFormer.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Doubly Stochastic Attention, Linear Attention, Plug-and-play, Optimal Transport

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_AyQDOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper introduces LOTFORMER, an efficient attention mechanism designed for bidirectional Transformers in which tokens serve as both information sources and receivers. LOTFORMER routes interactions through a learned low-rank pivot measure and composes two entropic transport couplings.

Critical strengths

LOTFORMER routes interactions through a learned low rank pivot measure and applies the resulting operator in O(nr) time. Composing two entropic transport couplings avoids the dense n × n attention matrix, finite Sinkhorn iterations approximate those marginals.

Critical weaknesses
  1. This paper investigates doubly stochastic attention, emphasizing its property of acting as both an emitter and a receiver; however, the distinctive characteristics are not demonstrated in the experiments.
  2. In Table 8: LOTFormer ablations, when the variable r of the low-rank pivot measure is increased from 32 to 64, Top 1 accuracy actually degrades, which is not reasonable. An explanation is necessary.
  3. The experimental results are not satisfied. In the retrieval experiments, comparing against only Hedgehog is insufficient. In the image recognition experiments, the results based on the Swin Tiny model are even worse than those of FLattenAttn, a 2023 algorithm.
  4. The paper is not written smoothly or clearly enough, especially the algorithm section, which is not concise and easy to understand.
Questions for authors
  1. What and where is the necessary and the unique of doubly stochastic attention?
  2. Why the performance is not better when the rank increases?
4 comments
AuthorsOpenReview ↗

Response to Reviewer AyQD

We thank the reviewer for the review. The revision adds experiments that answer each question directly.

W1 / Q1. What is necessary and unique about doubly stochastic attention, and where is it demonstrated?

What is unique. Softmax attention constrains only the rows: each query distributes one unit of attention, but nothing controls how much attention each key receives. Attention can therefore collapse onto a few tokens while others are ignored. Double stochasticity also fixes the column sums, so every token both sends and receives exactly one unit of mass. This sender-and-receiver balance is the property the reviewer highlights, and it is natural for bidirectional encoders, where every token is both a query and a key.

Where it is demonstrated. We added a controlled experiment that isolates exactly this property (Table 7, Appendix E.3).

  • The control: two-softmax pivot attention, A=softmax(QZ⊤/dk) softmax(ZK⊤/dk)A = \mathrm{softmax}(QZ^\top/\sqrt{d_k})\,\mathrm{softmax}(ZK^\top/\sqrt{d_k}) at ε=1\varepsilon = 1. This is the construction of Agent Attention (Han et al., 2024) and Latte (Dolga et al., 2025), and LOTFormer reduces to it exactly at T = 1.
  • Only the constraint differs: the control has the same pivot locations, r = 32, projections, [CLS] handling, auxiliary components and training as LOTFormer. It differs only in that the column constraint, i.e. the receiver side, is not enforced.

DeiT-Tiny, ImageNet-1K, Top-1 (%). Control: one softmax per plan instead of Sinkhorn.

SettingLOTFormerControlΔ
Full config.74.872.8+2.0
No DWC / polar.73.271.5+1.7
1% of data26.818.1+8.7
  • The constraint alone adds 1.7–2.0 points when attention is trained, with or without the auxiliary components.
  • The gain is largest where an inductive bias matters most: +8.7 points with 1% of the data, and LOTFormer leads softmax by +4.5 points in this regime (Table 6). This is consistent with the constraint acting as a structural prior: every key must receive its share, which prevents attention from collapsing onto a few tokens.
  • Dose–response: enforcing the receiver constraint more tightly raises ImageNet-100 accuracy from 80.5 at T = 1 to 81.5 at T = 5 and 82.1 at T = 10 (Table 9(ii)).

What is necessary for this to be practical. Doubly stochastic attention existed before, but only at quadratic or superlinear cost: Sinkformer and ESPFormer. LOTFormer is the first to provide it in linear time, O(nr)O(nr), which makes the property usable at long context and at the 7B scale.

W2 / Q2. Why does accuracy not improve when the rank grows from 32 to 64?

This is the classical bias–variance trade-off, and the pivot size r is exactly the knob that controls it.

  • Small r: high bias. The operator has rank at most r, so with few pivots every patch must route its attention through a coarse bottleneck. The operator cannot represent the interactions between 196 patches, and both training and test accuracy are low. This is why accuracy rises steeply up to r = 32 (64.5 at r = 4, 68.8 at r = 16, 74.8 at r = 32).

  • Large r: higher variance. Once r suffices to represent these interactions, additional pivots mainly add capacity: more pivot locations and masses per head, and a more flexible operator. Under a fixed data and training budget (ImageNet-1K, 400 epochs), this extra capacity fits the training set better without improving generalization. Test accuracy therefore drops, to 73.9 at r = 64 and 71.6 at r = 128.

  • Direct evidence from training and test accuracy (new Table 10). Training accuracy is one pass over the ImageNet-1K training set with evaluation transforms (no augmentation).

    r48163264128
    Train Top-170.271.775.680.584.689.2
    Test Top-164.566.468.874.873.971.6
    Gap5.75.36.85.710.717.6

    Up to r = 32, training and test accuracy rise together and the gap stays between 5.3 and 6.8 points (bias-limited). Beyond r = 32, training accuracy keeps rising (84.6, 89.2) while test accuracy falls (73.9, 71.6), and the gap grows to 10.7 and 17.6 points (variance-limited): the added capacity is spent on fitting the training set.

  • Consistent settings: every r uses the identical full DeiT-Tiny configuration and recipe (Table 9(iii) caption), so the trend reflects r alone.

  • r = 32 also costs less: the operator cost grows linearly in r (Eq. 8). r = 32 is therefore both the most accurate and cheaper than r = 64, and we use it throughout.

W3. Baselines and Swin.

The evidence supports two uses of LOTFormer: as a plug-and-play replacement in pretrained models, and as an attention layer trained from scratch, especially in vision.

Conversion: more baselines, and LOTFormer remains the strongest. Beyond Hedgehog, we added the closest transport-based alternatives under the identical conversion protocol on gte-Qwen2-1.5B (Table 16), with mean LongEmbed retention over three seeds:

DS: doubly stochastic. Positive-feature Sinkhorn uses r = 32 random features; the uniform-mass variant learns pivot locations only.

MethodDSRetention (%)
Hedgehog✗93.2
Positive-feature Sinkhorn✓76.6
LOTFormer, uniform masses✓90.1
LOTFormer✓98.3
  • Across model scales: LOTFormer retains 98.3–98.9% from 1.5B to 7B, against 93.2–94.1% for Hedgehog (Table 3).
  • On GLUE: it recovers 99.6% of fine-tuned BERT, ahead of Hedgehog, T2R and T2R-HH under Hedgehog's own protocol (Table 4).
  • Why few other conversion baselines apply: most recent conversion methods (Liger, SUPRA, DiJiang, RADLADS) linearize causal decoders through recurrent or causal structure and do not apply to bidirectional encoders. Hedgehog is the standard bidirectional plug-and-play baseline.

Training from scratch in vision: LOTFormer is the strongest under matched conditions.

  • DeiT-Tiny, like for like. With identical auxiliary components and recipe (Table 12), LOTFormer is ahead both with and without DWC.

DeiT-Tiny, ImageNet-1K, Top-1 (%). Attention only: [CLS] softmax row, no DWC.

ConfigurationFLattenPolaFormerLOTFormer
Attention only71.861.973.2
With DWC (and polarization)74.174.674.8
  • DeiT-Small: LOTFormer reaches 80.1, against 79.8 for PolaFormer under the same 400-epoch recipe, with fewer parameters (22.3M vs. 23.0M) and the same FLOPs (4.8G).
  • PVT-Tiny: 79.6, against 78.8 for PolaFormer.
  • Limited supervision: LOTFormer leads softmax and PolaFormer at every data fraction (Table 6), by +4.5 points over softmax with 1% of the data.

Swin-Tiny.

  • Result: LOTFormer reaches 81.8, which is +0.6 over softmax, within 0.3 of FLatten (82.1) and 0.8 of PolaFormer (82.6), with fewer parameters (28.0M vs. 29.0M).
  • Why Swin differs: it attends within local 7×7 windows of only 49 tokens. This is the regime where a global low-rank operator has the least to offer, yet LOTFormer remains competitive there.
  • Revised claim: Contribution 3 now states this precisely. LOTFormer outperforms the baselines on DeiT and PVT and is competitive on Swin.

Together, these results show that LOTFormer is effective in conversion and plug-and-play replacement, and that it is a strong choice when attention is trained from scratch, particularly for vision models.

W4. Clarity of the method section. We rewrote Section 3 with the same notation. It proceeds in order:

  1. entropic OT;
  2. queries, keys and the pivot measure;
  3. the two thin transport plans;
  4. gluing them through the pivot;
  5. the resulting attention operator, with the finite-T caveat;
  6. complexity and learning.

We also moved secondary tables and discussions to the appendix, with pointers from the main text.

AuthorsOpenReview ↗

End of Discussion Period

Dear Reviewer AyQD,

With the discussion period ending, we would like to briefly summarize how the revision addresses your questions, including results added after our first response.

Q1 (what is necessary and unique about double stochasticity). A matched control isolates the column (receiver) constraint, with the same pivots, rank, projections and recipe. It adds +1.7 to +2.0 points on DeiT-Tiny and +8.7 points with 1% of the data (Table 7). Accuracy also rises monotonically as the constraint is enforced more tightly (T = 1 → 5 → 10). In pretrained conversion on gte-Qwen2-7B, the same control trails LOTFormer (98.2% vs. 99.2% retention, Table R2).

Q2 (rank 32 vs. 64). New Table 10 shows a bias–variance trade-off. Up to r = 32, train and test accuracy rise together. Beyond r = 32, train accuracy keeps rising (84.6, 89.2) while test accuracy falls, and the gap grows from 5.7 to 17.6 points.

W3 (baselines and Swin).

  • Conversion baselines. We added positive-feature Sinkhorn with both fixed and learned features, and a uniform-mass reference. They reach 76.6%, 94.3% and 90.1% retention respectively, against 98.3% for LOTFormer (Tables 16, R3).
  • Swin-Tiny. We revised the claim to "competitive on Swin" (81.8 vs. 82.1 FLatten).
  • Correction to our earlier reply. PolaFormer's 61.9 uses deformable convolution. Its convolution-free result is 68.1. Without convolution, LOTFormer reaches 73.2, against 71.8 for FLatten and 68.1 for PolaFormer. With DWC, we now describe LOTFormer as matching PolaFormer (74.8 vs. 74.6).

W4 (clarity). Section 3 has been rewritten in a linear order with consistent notation, and secondary material has moved to the appendix.

Reviewer arSF raised their score after these additions. We would sincerely appreciate it if you would consider them in your final assessment.

Reviewer_arSFOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
3(+1)
Read review
Paper summary

The paper proposes LOTFormer, a linear-complexity bidirectional attention mechanism based on optimal transport. Instead of directly computing attention between queries and keys, the method introduces a learned pivot distribution with rr support points and routes token interactions through two entropic OT problems, one between queries and pivots and another between pivots and keys. The resulting transport plans are combined through their shared pivot marginal to construct a low-rank attention matrix. When the prescribed marginals are satisfied exactly, the resulting matrix is doubly stochastic and has rank at most rr. The computational complexity is linear in the sequence length for a fixed number of pivots and Sinkhorn iterations.

The authors evaluate the method in two settings. First, they replace softmax attention in pretrained embedding models ranging from 1.5B to 7B parameters, retaining 98.3–98.9% of the original performance on LongEmbed, compared with 93.2–94.1% for Hedgehog. They also report retaining 99.7% of the performance of a fine-tuned BERT model on GLUE. Second, they evaluate LOTFormer by training vision architectures, including DeiT, PVT, and Swin, on ImageNet-1K. A separate long-sequence experiment reports a 7.5× throughput improvement over softmax attention at 128k tokens.

Critical strengths
  1. The core construction is sound and well motivated computationally. The marginal identities, the rank bound, and the complexity analysis are correct. The factorization gives a doubly stochastic operator without forming any n×nn \times n object.
  2. The pretrained-conversion setting addresses a useful practical problem. Retrofitting structured attention into existing bidirectional encoders is valuable. The stage-wise analysis in Table 2 (zero-shot swap, then distillation, then LoRA) is informative.
  3. The vision results are encouraging. They span four backbones, and the limited-supervision study shows the largest gain at 1% of the data.
  4. The ablations and scope discussion are useful. These include the ϵ\epsilon/T/pivot ablations, the [CLS] study, and the clear argument in Appendix F that double stochasticity collapses to the identity under a causal mask.
Critical weaknesses

1. Novelty is not sufficiently distinguished from closely related transport constructions.

  • OTKE [1] already computes entropic transport plans between an input set and a trainable reference. Its Sec. 3.2 composes them as pP(x,z)P(x′,z)⊤p P(\mathbf{x},\mathbf{z}) P(\mathbf{x}',\mathbf{z})^\top via the gluing lemma, which is the glued coupling in Eq. (5) with uniform reference masses. Its Sec. 4 notes that this yields self-attention-like weights.
  • Positive-feature Sinkhorn [2] already gives linear-cost normalization of a low-rank kernel. Applied to ϕ(Q)ϕ(K)⊤\phi(Q)\phi(K)^\top, it produces a doubly stochastic, rank-rr operator in O(nr)O(nr). This contradicts the statement at L53 that no existing mechanism combines double stochasticity with linear complexity.
  • Low-Rank Sinkhorn Factorization [3] and transport through anchor points [4, 5] are also closely related.
  • Table 8 suggests that learned masses add only 0.1–0.7 points over a fixed uniform measure. That narrows the gap to the OTKE-style construction further.

What, precisely, do LOTFormer's learned masses, architectural choices, conversion procedure, or implementation contribute beyond these works? A comparison under matched rank and compute against (a) a uniform-mass learned-reference construction and (b) a positive-feature Sinkhorn attention baseline would clarify the contribution.

Please also clarify whether "fixed" pivots in Table 8 fix only the masses or also the locations.


2. The implemented marginal accuracy is unverified, and the normalization equations are inconsistent.

  • No row- or column-marginal residuals are reported at the default T=5T=5, so the practical degree of double stochasticity is unclear.
  • Please report ∥A1−1∥\Vert A\mathbf{1}-\mathbf{1} \Vert and ∥A⊤1−1∥\Vert A^\top\mathbf{1}-\mathbf{1} \Vert across representative layers, heads and sequence lengths, at the precision used in experiments, as a function of TT and ε\varepsilon.
  • Eq. (12) omits the factor nn that appears in Eq. (7). Eq. (10) omits the 1/dk1/\sqrt{d_k} scaling from Sec. 3, which changes the effective temperature by a factor of 8 at dk=64d_k=64 and makes the ε grid in Table 8 hard to interpret. Are these notational slips or implementation differences? Which formulation produced the reported results?
  • The default ε=0.1\varepsilon=0.1 (L260) contradicts Table 8, where ε=1\varepsilon=1 is best in every row and the text itself says performance "peaks near ε = 1". Please justify the default.

3. The vision comparisons neither isolate the benefit of double stochasticity nor establish matched baselines.

  • Table 9 usefully examines the [CLS] aggregator, polarization and depthwise convolution (DWC), but it lacks a row-stochastic pivot control with the same architecture and budget. Can the authors add this control, keeping rank, projections and auxiliary components fixed?
  • Table 5 does not disclose that the 74.8 DeiT-Tiny result uses DWC and [CLS] polarization. The attention-only LOTFormer scores 73.2, below FLatten (74.1) and PolaFormer (74.6).
  • Training uses 400 epochs (Table 11), while the baselines follow 300-epoch recipes. Which Table 5 baselines were reproduced under the 400-epoch recipe, and which were taken from prior publications?
  • Please confirm that the rank ablation in Table 8(iii) uses consistent settings. The jump from r=16r=16 to r=32r=32 (+6.0) is larger than the whole gain from r=4r=4 to r=16r=16 (+4.3), and the r=32r=32 value equals the full DWC + polarization result.
  • How is the [CLS] column handled? If patches also attend to [CLS], the patch rows of AA no longer sum to one.

4. The speed comparisons lack the details needed to judge fairness.

  • Table 7 gives no throughput units and does not name the softmax backend. FlashAttention-3 is identified only for the memory comparison.
  • Please state the implementation, hardware, precision, batch size and timing boundaries for Table 7 and Figure 3. Do the timings include both transport solves and value aggregation?
  • On the H200 used in Appendix D.5, FlashAttention-3 is the strongest compatible softmax kernel; FA4 targets Blackwell only [6]. Figure 3's softmax curve (about 1.5×1051.5 \times 10^5 ms at N=217N=2^{17}) appears to come from a naive implementation.
  • Please reconcile the r=64r=64 timings across panels. Panel (c) at T=5T=5 shows about 170 ms at N=217N=2^{17}, while panels (a) and (b) show about 350 ms at the default T=5T=5.
  • In Table 7, the 64k speedup is 0.15/0.045=3.3×0.15/0.045 = 3.3\times, not 3.4×3.4\times. Hedgehog's throughput falls by a factor of 4 from 64k to 128k, which is implausible for a linear-time method; please verify.
  • Figure 3 measures forward passes only, and Table 8 gives no baseline backward timings. If training efficiency is claimed, please report matched backward and full training-step timings, including gradients through Sinkhorn and the pivots.

5. Quality preservation is not shown where the largest speedups occur, and some claims are broader than the evidence.

  • The paper correctly labels 128k as a separate throughput stress test, but the 98.9% retention and the 7.5× speedup are never shown together. Can the authors report quality alongside throughput across sequence lengths, and explain how inputs beyond each model's supported context are treated?
  • Contribution 2 claims superiority over "competing efficient attention replacements", but the only such comparison is Hedgehog.
  • Contribution 3 ("matches or improves") does not hold on Swin-Tiny, where LOTFormer (81.8) trails FLatten (82.1) and PolaFormer (82.6).
  • Please qualify these claims or strengthen the comparisons.

References

[1] G. Mialon, D. Chen, A. d'Aspremont, and J. Mairal. [A Trainable Optimal Transport Embedding for Feature Aggregation and its Relationship to Attention](https://arxiv.org/abs/2006.12065). ICLR, 2021.
[2] M. Scetbon and M. Cuturi. [Linear Time Sinkhorn Divergences using Positive Features](https://proceedings.neurips.cc/paper/2020/file/9bde76f262285bb1eaeb7b40c758b53e-Paper.pdf). NeurIPS, 2020.
[3] M. Scetbon, M. Cuturi, and G. Peyré. [Low-Rank Sinkhorn Factorization](https://proceedings.mlr.press/v139/scetbon21a.html). ICML, 2021.
[4] A. Forrow, J.-C. Hütter, M. Nitzan, P. Rigollet, G. Schiebinger, and J. Weed. Statistical Optimal Transport via Factored Couplings. AISTATS, 2019.
[5] C.-H. Lin, M. Azabou, and E. Dyer. Making Transport More Robust and Interpretable by Moving Data through a Small Number of Anchor Points. ICML, 2021.
[6] [FlashAttention-4: Algorithm and Kernel Pipelining Co-Design for Asymmetric Hardware Scaling](https://arxiv.org/abs/2603.05451). MLSys, 2026.
Questions for authors

1. The pretrained conversion protocol is insufficiently specified.

  • Uniform pivot masses do not determine the support vectors ZZ or their scale, so the zero-shot result in Table 2 (58.7) cannot be reproduced. How are ZZ and p0p^0 initialized for each layer and head? Does initialization use pretrained activations or calibration data?
  • Please specify the distillation objective, datasets, training budget, trainable parameters and LoRA configuration for the embedding models.
  • Please explain how pivots interact with grouped-query attention, and how padding is handled given the uniform 1/n1/n marginals.
  • Please state whether Hedgehog received matched adaptation resources. Appendix D.3 documents only the BERT protocol, and the Reproducibility Statement claims more than Appendix D provides.
  • In Table 4, the T2R, T2R-HH and Hedgehog rows appear to be taken verbatim from Zhang et al. (2024). This conflicts with the claim of a "same conversion and adaptation budget" (L265).
  • The Recovery column also mixes definitions. LOTFormer's 99.7 matches the mean of per-task ratios (the ratio of means is 99.64). Hedgehog's 99.3 matches the ratio of means (the mean of ratios is 99.45). T2R's 88.9 matches neither. Please use one definition for every row.
14 comments
AuthorsOpenReview ↗

Response to Reviewer arSF

We thank the reviewer for an exceptionally thorough review. Every point is addressed below, with new experiments where needed, and all changes are marked in blue.

W1. Novelty relative to related transport constructions.

We thank the reviewer for these pointers. All of these works are now discussed in Related Work and compared in Appendix F (Table 15). We first clarify the scope of our claim, and then address each work.

Scope of the claim. Two ingredients are well established in optimal transport, and we do not claim otherwise; the revised introduction (L53) says so explicitly.

  • Doubly stochastic plans in linear time, through positive-feature Sinkhorn (Scetbon & Cuturi, 2020) and low-rank Sinkhorn (Scetbon et al., 2021).
  • Transport through a reference measure, which avoids pairwise transport between inputs, as in linear OT (Wang et al., 2013; Moosmüller & Cloninger, 2023) and Wasserstein embeddings such as WEGL (Kolouri et al., 2021).

Our contribution is to bring this structure to attention. We propose a doubly stochastic attention operator that runs in linear time, for an arbitrary learned query–key cost, without approximating a kernel. Earlier doubly stochastic attention is either quadratic, like Sinkformer (Sander et al., 2022), or superlinear, like ESPFormer (Shahbazi et al., 2025). Earlier linear-time pivot attention, such as Agent Attention (Han et al., 2024) and Latte (Dolga et al., 2025), is not doubly stochastic. To our knowledge, LOTFormer is the first attention mechanism that is both doubly stochastic and linear-time. Beyond the operator itself, we show that it works as a drop-in attention layer, in conversion of 1.5B–7B encoders and in training from scratch.

OTKE (Mialon et al., 2021) is a pooling layer. It belongs with Wasserstein embeddings such as WEGL (Kolouri et al., 2021), not with attention.

  • What OTKE computes: it transports the elements of an input set to a single reference z (shared across the dataset and often obtained by k-means) and pools them into p bins. The result is one fixed-size embedding per set.
  • What its glued plan P(x,z)P(x′,z)⊤P(x,z)P(x',z)^\top is: a kernel between two different input sets xx and x′x', used to compare samples. It is not an attention matrix between the tokens of one sequence.
  • What LOTFormer computes: token-to-token attention inside every layer. Queries and keys come from separate projections of the same sequence, they are coupled through a per-head pivot measure with learned locations and masses, and the layer returns one output per token.

Low-Rank Sinkhorn (Scetbon et al., 2021) is impractical as an attention operator.

  • Cost: for a general cost, it needs the full n × n cost matrix. It becomes linear only when the cost itself admits a low-rank factorization, which holds exactly only for the squared Euclidean cost.
  • Solver: it solves a non-convex problem by mirror descent with inner Dykstra projections.
  • What attention would require: a separate low-rank OT problem for every query–key pair of sequences, in every head, layer and forward pass, with backpropagation through the non-convex solver. That is not feasible at our scale.
  • What LOTFormer does instead: it evaluates costs only between tokens and r pivots, so the cost is O(nr)O(nr) for any learned cost. It needs two convex Sinkhorn solves (T = 5), and it amortizes the low-rank structure by learning the pivots across the training distribution. Appendix H quantifies the cost of this amortization relative to per-input factors.
  • Factored and anchor couplings (Forrow et al., 2019; Lin et al., 2021) likewise fit their anchors separately for each problem, by alternating optimization.

Positive-feature Sinkhorn (Scetbon & Cuturi, 2020) is elegant, but it underperforms as attention.

  • What it shares with LOTFormer: applied to ϕ(Q)ϕ(K)⊤\phi(Q)\phi(K)^\top, it gives a doubly stochastic, rank-r operator in O(nr)O(nr).
  • Where it differs: its factors are fixed random features that approximate a specific kernel, whereas LOTFormer's factors are transport plans to a learned pivot measure.
  • The matched comparison the reviewer asked for, (b) (Table 16): gte-Qwen2-1.5B under our identical conversion protocol, data, budget and seeds, with r = 32, T = 5 and ε=1\varepsilon = 1, reporting mean LongEmbed retention over three seeds.

DS: doubly stochastic. Positive-feature Sinkhorn uses r = 32 random features; the uniform-mass variant learns pivot locations only.

MethodDSRetention (%)
Hedgehog✗93.2
Positive-feature Sinkhorn✓76.6
LOTFormer, uniform masses✓90.1
LOTFormer✓98.3

Positive-feature Sinkhorn is doubly stochastic at matched rank and solver budget, yet it loses 21.7 points. Double stochasticity alone does not explain LOTFormer's quality. What preserves the pretrained behavior is the learned pivot coupling.

Learned masses and "fixed" pivots (Table 9).

  • "Fixed" means both are frozen: "fixed" pivots freeze both the locations and the masses. The caption now says so.
  • Why the gap is small when training from scratch (0.1–0.7 points): the query and key projections are trained and can align to any fixed pivot configuration.
  • Conversion is where the masses matter, the reviewer's comparison (a) (Table 16). Fixing the masses to uniform (1/r) while learning the locations costs 8.2 points of retention (90.1% vs. 98.3%).
    • Why: the pretrained projections stay frozen during distillation, so the pivot measure must absorb how unevenly pretrained attention distributes mass over keys. Under the doubly stochastic constraint, uniform masses force every pivot to carry the same mass, and learned masses remove this restriction.
  • Learned masses are a substantive part of the method. They also add to the conceptual difference from OTKE, which computes a pooled set embedding rather than attention.

What LOTFormer contributes, precisely.

  1. The first doubly stochastic attention with linear runtime. It is exact up to Sinkhorn convergence, at O(nr)O(nr), for an arbitrary learned cost, and without approximating a kernel.
  2. A per-head pivot measure with learned locations and masses, shared by two asymmetric transport plans, one from queries to pivots and one from pivots to keys.
  3. A unifying view of pivot attention. At T = 1, LOTFormer reduces exactly to two-softmax pivot (agent-token) attention, softmax(QZ⊤/dk) softmax(ZK⊤/dk)\mathrm{softmax}(QZ^\top/\sqrt{d_k})\,\mathrm{softmax}(ZK^\top/\sqrt{d_k}). The further Sinkhorn iterations make it doubly stochastic, which is worth +1.7 to +8.7 points when attention is trained (Table 7).
  4. A practical conversion procedure and kernel: distillation plus LoRA, grouped-query attention and padding, and FlashSinkhorn. Together they bring the operator to 7B-parameter encoders at 98.9% retention, with a 4.2× end-to-end speedup over FlashAttention-3 at 128k (Through put only).

W2. Marginal accuracy, normalization equations, and the default ε\varepsilon.

(a) Marginal residuals. New Appendix G reports what the reviewer asked for.

  • Quantities: the row residual ∥A1−1∥2\lVert A\mathbf{1}-\mathbf{1}\rVert_2 and the column residual ∥A⊤1−1∥2\lVert A^\top\mathbf{1}-\mathbf{1}\rVert_2 of the implemented operator, over all layers and heads.
  • How they are computed: from the factors, without forming A, in float32, which is the precision of the Sinkhorn solves in our training and conversion code.
  • What is varied: sequence length, model scale, T, ε\varepsilon and r.

Sequence length and model scale (Table 17; r = 32, T = 5, ε=1\varepsilon = 1; max / mean over all layers and heads; row = ∥A1−1∥2\lVert A\mathbf{1}-\mathbf{1}\rVert_2, column = ∥A⊤1−1∥2\lVert A^\top\mathbf{1}-\mathbf{1}\rVert_2):

ModelnRowColumn
gte-Qwen2-1.5B5121.2e-5 / 1.1e-57.3e-6 / 5.2e-6
gte-Qwen2-1.5B8k7.0e-5 / 4.9e-57.2e-5 / 4.9e-5
gte-Qwen2-1.5B32k1.2e-4 / 7.8e-51.2e-4 / 8.0e-5
gte-Qwen2-1.5B128k2.9e-4 / 2.0e-46.2e-2 / 6.1e-4
gte-Qwen2-7B8k6.7e-5 / 4.7e-56.8e-5 / 4.8e-5
gte-Qwen2-7B32k1.2e-4 / 7.8e-51.2e-4 / 7.9e-5
DeiT-Tiny (patches)1968.7e-6 / 7.0e-61.8e-4 / 1.1e-5
  • Up to 32k tokens: both residuals are at the float32 rounding level, about 5×10−75\times10^{-7} per entry. The ℓ2\ell_2 norm grows only as n\sqrt{n}, and the values are the same for 1.5B and 7B.
  • At 128k: the mean column residual is 6×10−46\times10^{-4}, and the largest value (6×10−26\times10^{-2}) occurs in a single head.
  • Depth: each layer runs its own Sinkhorn iterations, so residuals are not carried from layer to layer. Since the mean residual per layer is already small, we do not expect residuals to become an issue layer by layer.

Number of half-steps T (new Table 19; T = 2k for k full iterations; gte-Qwen2-1.5B, 8k tokens, r = 32; mean over all layers and heads):

TRow, ε=1\varepsilon = 1Column, ε=1\varepsilon = 1Row, ε=0.1\varepsilon = 0.1Column, ε=0.1\varepsilon = 0.1
11.0e-53.6e-11.1e-58.5e-1
31.2e-52.0e-31.4e-55.1e-2
51.6e-55.0e-51.7e-52.2e-4
101.5e-51.0e-61.0e-45.0e-5
  • What T counts: T counts half-steps: each of the T iterations is one row or one column scaling, applied alternately, so k full row–column iterations correspond to T = 2k. The last scaling enforces its marginal exactly. For odd T the last scaling is on the row side, so the row residual is at rounding level and the column residual measures convergence. For even T the roles swap.
  • T trend: at T = 1 (the two-softmax pivot control), rows sum to one exactly and columns are unconstrained (3.6×10−13.6\times10^{-1} at ε=1\varepsilon = 1). Each further iteration shrinks the column residual geometrically, to 2.0×10−32.0\times10^{-3} at T = 3 and 5.0×10−55.0\times10^{-5} at the default T = 5. At ε=0.1\varepsilon = 0.1, Sinkhorn converges more slowly (8.5×10−18.5\times10^{-1}, 5.1×10−25.1\times10^{-2}, 2.2×10−42.2\times10^{-4}), which is why we use ε=1\varepsilon = 1. At T = 10 the last scaling is on the column side and the roles swap.

ε\varepsilon and r (Table 18, DeiT-Tiny, T = 5):

  • ε≥1\varepsilon \ge 1: the column residual is at rounding level.
  • ε≤0.1\varepsilon \le 0.1: it is visibly larger.
  • r: only a weak effect.

(b) Normalization equations. Both are notational slips in the submission. The implementation, and hence every reported result, uses the formulation of Section 3, and both equations are now corrected (Appendix D.1).

  • The factor n (Eq. (12) of the submission): the output is now written O=n ΓQ Diag(p0)−1 ΓK⊤VO = n\,\Gamma^{Q}\,\mathrm{Diag}(p^0)^{-1}\,\Gamma^{K\top} V, as in Eq. (7).
    • The implementation applies this factor.
  • The 1/dk1/\sqrt{d_k} scaling (Eq. (10) of the submission): the kernels are now written exp⁡(QZ⊤/(dk ε))\exp\big(QZ^\top/(\sqrt{d_k}\,\varepsilon)\big) and exp⁡(KZ⊤/(dk ε))\exp\big(KZ^\top/(\sqrt{d_k}\,\varepsilon)\big), i.e. exp⁡(S/ε)\exp(S/\varepsilon) for the scaled similarities S=QZ⊤/dkS = QZ^\top/\sqrt{d_k} of Section 3.
    • The implementation applies the standard 1/dk1/\sqrt{d_k} scaling, and ε\varepsilon acts on top of it, as the revised text now states.
    • The ε\varepsilon grid of Table 9 is therefore relative to standard attention scaling: ε=1\varepsilon = 1 corresponds to the usual softmax temperature.

(c) The default ε\varepsilon. The ε=0.1\varepsilon = 0.1 at L260 was an error in the text. ε=1\varepsilon = 1 is used in all experiments, consistent with Table 9, where ε=1\varepsilon = 1 is best in every row. The revision states ε=1\varepsilon = 1 everywhere: Section 4, the protocols for every experiment, and all table captions. The residuals in (a) give a second reason for this default: at ε=1\varepsilon = 1 and T = 5, both marginals are at rounding level, whereas at ε=0.1\varepsilon = 0.1 they are not.

Reviewer_avDPOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes LOTFormer, an efficient attention mechanism that combines doubly stochastic normalization with low-rank optimal transport for bidirectional Transformers. Instead of explicitly computing a dense query-key attention matrix, the method introduces a learnable pivot measure and constructs two entropic optimal transport couplings between queries, keys, and a shared set of pivots.

The resulting attention operator is obtained by composing these two couplings. Under exact marginal constraints, the operator is doubly stochastic and has rank at most (r). Its factorized form also allows attention to be applied to values with linear complexity in sequence length, assuming the pivot size and other relevant dimensions remain fixed.

The authors evaluate LOTFormer by replacing attention in pretrained embedding models, including models with up to 7B parameters, and by training several vision Transformer architectures. The results show strong retrieval-quality retention, competitive image classification performance, and considerable inference speedups at long sequence lengths. The paper also includes ablations on pivot size and Sinkhorn iterations, along with analyses of attention approximation error and implementation efficiency.

Critical strengths

Strength 1: A well-motivated combination of doubly stochastic attention and low-rank factorization.

The paper presents a mathematically grounded approach to constructing doubly stochastic attention without explicitly computing the quadratic attention matrix. By introducing a shared learnable pivot measure, the authors factorize the attention operator into two transport couplings while retaining the desired marginal structure under exact transport solutions.

I find this construction appealing because it provides a clear connection between the mathematical properties of optimal transport and the computational requirements of efficient attention. Although low-rank optimal transport factorization itself is not new, adapting it to learnable attention is a meaningful contribution.

The paper also makes the scope of the approach reasonably clear, particularly regarding its focus on bidirectional attention and the difficulties associated with causal masking.

Strength 2: Strong experimental results across pretrained embedding models and vision architectures.

The experimental evaluation is another strength. The authors test LOTFormer on several pretrained embedding models ranging from 1.5B to 7B parameters, as well as multiple vision Transformer backbones.

I find the attention-conversion experiments particularly encouraging. For example, LOTFormer retains 98.9% of the original retrieval quality on gte-Qwen2-7B, compared with 94.1% for Hedgehog under the reported conversion setting. This suggests that the proposed factorization can preserve much of the behavior of pretrained attention.

The long-context efficiency results are also promising. The reported 7.5x throughput improvement over softmax attention at 128K tokens indicates that the factorized implementation can offer substantial computational benefits in long-sequence settings.

I also appreciate the ablation studies on pivot size and Sinkhorn iterations. Together with the attention approximation analyses, they help explain how different design choices affect the method's performance.

Critical weaknesses

Weakness 1: The individual contribution of doubly stochastic normalization is not clearly established.

My main concern is that the paper combines two important design choices, low-rank pivot factorization and doubly stochastic normalization, without fully isolating their effects.

The current experiments demonstrate that the overall LOTFormer architecture can perform well, but they do not clearly show how much of the improvement comes specifically from imposing the doubly stochastic constraint.

For example, it would be useful to compare LOTFormer with a row-stochastic attention mechanism that uses the same learnable pivots, factorization rank, and parameter budget. Ideally, the remaining architectural components and training settings should also be kept identical. Such a comparison would help determine whether doubly stochastic normalization offers benefits beyond those of the low-rank pivot-based representation itself.

This concern is also relevant to the vision experiments. The strongest DeiT-Tiny configuration includes several additional components, such as a separate softmax aggregator for the CLS token, CLS polarization, and depthwise convolution.

According to Table 9, the classification accuracy increases from 68.2% in the initial configuration to 74.8% after these modifications. These additions appear to have a substantial effect on the final performance.

I appreciate that the authors explicitly limit the doubly stochastic guarantee to patch-to-patch attention in this configuration. However, the dependence on these additional components makes it difficult to determine how much of the final improvement should be attributed to the proposed normalization mechanism.

I think a more direct comparison against matched row-stochastic low-rank attention would make the methodological contribution considerably clearer.

Weakness 2: The practical accuracy of the doubly stochastic constraint needs more quantitative analysis.

Another concern is the gap between the exact mathematical formulation and its practical implementation.

The theoretical doubly stochastic guarantee assumes that the two optimal transport couplings satisfy their prescribed marginal constraints exactly. In practice, however, LOTFormer uses a finite number of Sinkhorn iterations, with (T=5) as the default setting.

With a limited number of iterations, the resulting couplings may not satisfy their marginal constraints exactly. Consequently, the composed attention operator is not necessarily exactly doubly stochastic.

Although the paper acknowledges this approximation, I would like to see a more detailed analysis of the actual row-sum and column-sum errors in the implemented attention operators. In particular, it would be useful to understand how these errors vary with sequence length, attention depth, and the number of Sinkhorn iterations.

I am also concerned about potential numerical issues associated with very small learned pivot masses. Since the coupling composition involves the inverse of the pivot masses, small values could amplify numerical errors or affect training stability.

These questions matter because doubly stochastic normalization is one of the central motivations of the proposed method. A quantitative characterization of how accurately this property is maintained in practice would strengthen the paper's theoretical and empirical connection.

Questions for authors

Q1. Isolating the effect of doubly stochastic normalization

Could the authors provide a controlled comparison between LOTFormer and a low-rank pivot-based attention baseline that uses row-wise normalization instead of doubly stochastic Sinkhorn normalization?

It would be particularly helpful to keep the pivot size, learnable parameter budget, CLS handling, depthwise convolution, and training protocol fixed. This would allow a more direct assessment of whether the doubly stochastic constraint provides an independent benefit.

Q2. Marginal errors and numerical stability with finite Sinkhorn iterations

Could the authors report quantitative row-sum and column-sum errors for the attention operators produced by the practical implementation?

I would be interested in how these errors change with the number of Sinkhorn iterations, entropy regularization strength, and sequence length. Have the authors also examined whether very small learned pivot masses affect numerical stability or training behavior?

Q3. Efficiency comparisons and reproducibility of pretrained conversion

Could the authors provide a more detailed accuracy-throughput comparison against optimized linear-attention baselines, especially at intermediate sequence lengths?

The reported long-context speedups are encouraging, but it would be useful to understand where LOTFormer becomes more efficient than the competing methods and how this depends on the model configuration.

I would also appreciate additional details about the conversion and adaptation procedures used for the pretrained embedding models. This would make it easier to reproduce and interpret the reported retrieval-quality retention.

5 comments
AuthorsOpenReview ↗

Response to Reviewer avDP (part 1)

We thank the reviewer for the careful and constructive review. We ran every experiment the reviewer asked for, and all results are in the revised PDF (new and changed text in blue).


W1 / Q1. Isolating the effect of double stochasticity.

We ran exactly the controlled comparison the reviewer proposed (Table 7, Appendix E.3).

The control. LOTFormer builds both transport plans from the kernels exp⁡(QZ⊤/(dk ε))\exp\big(QZ^\top/(\sqrt{d_k}\ \varepsilon)\big) and exp⁡(KZ⊤/(dk ε))\exp\big(KZ^\top/(\sqrt{d_k}\ \varepsilon)\big), and then balances each plan with T Sinkhorn iterations. The control keeps the same kernels and normalizes each plan once instead:

A=softmax(QZ⊤/dk)softmax(ZK⊤/dk)(ε=1).A = \mathrm{softmax}(QZ^\top/\sqrt{d_k}) \mathrm{softmax}(ZK^\top/\sqrt{d_k}) \qquad (\varepsilon = 1).

  • What it computes: each query distributes its mass over the pivots with a softmax, and each pivot distributes its mass over the keys with a softmax.
  • An established construction: this is the two-softmax pivot attention of Agent Attention (Han et al., ECCV 2024) and Latte (Dolga et al., TMLR 2025), with the same scaling. The comparison is therefore against a published design, not a weakened variant of our own.
  • What stays identical to LOTFormer: pivot locations, r = 32, dk\sqrt{d_k} scaling and ε\varepsilon, projections, [CLS] handling, DWC, polarization, and the training protocol. The operator keeps rank ≤r\le r and O(nr)O(nr) cost.
  • What changes: the column marginal is no longer enforced. The learned pivot masses, a softmax-parameterized distribution over the pivots, cancel in this composite. The control therefore differs from LOTFormer only by the marginal constraint and the r mass parameters per head that it requires.
  • LOTFormer contains this construction as a special case. With T = 1 (and ε=1\varepsilon = 1), each plan receives exactly one normalization, and LOTFormer reduces to the control, i.e., it recovers agent / pivot-token attention exactly. LOTFormer therefore generalizes these methods: additional Sinkhorn iterations turn the two independent softmaxes into transport plans that are balanced across queries and keys.

Table 7. LOTFormer vs. the two-softmax pivot control

DeiT-Tiny, ImageNet-1K, Top-1 (%). Control: one softmax per plan instead of Sinkhorn.

SettingLOTFormerControlΔ
Full config.74.872.8+2.0
No DWC / polar.73.271.5+1.7
1% of data26.818.1+8.7

What this shows.

  1. The gain comes from the doubly stochastic constraint. Pivots, rank, scaling and parameters are shared, and the gain remains (+1.7) without DWC and polarization.
  2. It grows as supervision shrinks: +8.7 points with 1% of ImageNet. This is consistent with the constraint acting as a structural prior: each key must receive its share of attention, which prevents attention from collapsing onto a few keys.
  3. It is monotone in how tightly the constraint is enforced. Since T = 1 recovers agent / pivot-token attention, the Sinkhorn sweep (Table 9(ii)) is a dose–response from that construction to LOTFormer: ImageNet-100 accuracy rises from 80.5 at T = 1 to 81.5 at T = 5 and 82.1 at T = 10.

The control rows are single runs (stated in the caption). We will add ImageNet seeds in the final version.

The auxiliary vision components (Table 12) are generic and not specific to LOTFormer: DWC and polarization come from PolaFormer, and in Table 12 we apply them to PolaFormer and FlattenAttention under the same recipe.

  • Breakdown of 68.2 → 74.8: a softmax row for [CLS] gives +5.0, [CLS]-only polarization +0.4, and DWC +1.2.
  • The same components help the baselines as much or more: PolaFormer gains +12.7 from them, and FlattenAttention +2.3.
  • With identical components, LOTFormer is the strongest: 74.8, against 74.6 for PolaFormer and 74.1 for FlattenAttention.
  • Matched against its own row-stochastic control, LOTFormer is ahead both with the components (+2.0) and without them (+1.7).

The doubly stochastic guarantee still applies to all patch-to-patch interactions, as stated in Section 4.2.

W2 / Q2. Marginal accuracy with finite Sinkhorn iterations, and small pivot masses.

We agree this is central and now quantify it in a new Appendix G.

  • What we measure: the row and column residuals ∥A1−1∥2\lVert A\mathbf{1}-\mathbf{1}\rVert_2 and ∥A⊤1−1∥2\lVert A^\top\mathbf{1}-\mathbf{1}\rVert_2 of the implemented operator, over every layer and head. We vary sequence length, model scale, T, ε\varepsilon and r.
  • How: the residuals are computed from the factors, without forming A, in float32 (the precision of our Sinkhorn solves).

Table 17. Marginal residuals at the default setting (r = 32, T = 5, ε=1\varepsilon = 1; max / mean over all layers and heads; row = ∥A1−1∥2\lVert A\mathbf{1}-\mathbf{1}\rVert_2, column = ∥A⊤1−1∥2\lVert A^\top\mathbf{1}-\mathbf{1}\rVert_2)

ModelnRowColumn
gte-Qwen2-1.5B5121.2e-5 / 1.1e-57.3e-6 / 5.2e-6
gte-Qwen2-1.5B8k7.0e-5 / 4.9e-57.2e-5 / 4.9e-5
gte-Qwen2-1.5B32k1.2e-4 / 7.8e-51.2e-4 / 8.0e-5
gte-Qwen2-1.5B128k2.9e-4 / 2.0e-46.2e-2 / 6.1e-4
gte-Qwen2-7B8k6.7e-5 / 4.7e-56.8e-5 / 4.8e-5
gte-Qwen2-7B32k1.2e-4 / 7.8e-51.2e-4 / 7.9e-5
DeiT-Tiny (patches)1968.7e-6 / 7.0e-61.8e-4 / 1.1e-5

Table 18. DeiT-Tiny across ε\varepsilon and r (T = 5; max over layers and heads, ∥A1−1∥2\lVert A\mathbf{1}-\mathbf{1}\rVert_2 / ∥A⊤1−1∥2\lVert A^\top\mathbf{1}-\mathbf{1}\rVert_2)

ε=0.01\varepsilon = 0.01ε=0.1\varepsilon = 0.1ε=1\varepsilon = 1ε=10\varepsilon = 10
r = 162.7e-5 / 7.9e16.5e-6 / 1.0e08.7e-6 / 1.5e-47.7e-6 / 7.4e-6
r = 322.9e-5 / 5.4e16.8e-6 / 1.6e08.7e-6 / 1.8e-47.3e-6 / 6.8e-6
r = 642.8e-5 / 4.2e17.1e-6 / 1.3e07.7e-6 / 6.4e-55.5e-6 / 5.4e-6

Sequence length and model scale. At the default setting, both residuals stay at the float32 rounding level up to 32k tokens, about 5×10−75\times10^{-7} per entry. The ℓ2\ell_2 norm grows only as n\sqrt{n}, as expected for rounding error summed over n entries. The values are the same for the 1.5B and 7B models. At 128k, the mean column residual is 6×10−46\times10^{-4}, and the largest value (6×10−26\times10^{-2}) occurs in a single head.

Depth: residuals do not propagate across layers. Every layer runs its own Sinkhorn iterations on its own inputs, so a marginal error in one layer is not carried into the next; the next layer re-normalizes from scratch. Since the mean residual per layer is already small (Tables 17 and 19), we do not expect residuals to become an issue layer by layer.

Iterations, ε\varepsilon and r.

  • What T counts: T counts half-steps: each of the T iterations is one row or one column scaling, applied alternately, so k full row–column iterations correspond to T = 2k. The last scaling enforces its marginal exactly. T = 5 ends on a row scaling, so the row residual is at rounding level in every setting, and the column residual is the one that measures convergence.
  • ε\varepsilon governs convergence (Table 18):
    • For ε≥1\varepsilon \ge 1, the column residual reaches rounding level within five iterations.
    • For ε≤0.1\varepsilon \le 0.1, Sinkhorn converges more slowly and T = 5 leaves a visible column residual.
    • The pivot size r has only a weak effect.
  • The accuracy ablation agrees (Table 9): ε=1\varepsilon = 1 gives the best accuracy, and T = 5 is within 0.6 points of T = 10. The default ε=1\varepsilon = 1, T = 5 thus enforces both marginals to rounding level at the cost of five scalings per layer.

Small pivot masses.

  • Masses never act as divisors. The composed operator contains Diag(p0)−1\mathrm{Diag}(p^0)^{-1}, but the last Sinkhorn update of the pivot-to-key plan is v=p0⊘(M⊤u)v = p^0 \oslash (M^\top u), so the factor cancels analytically: Diag(p0)−1ΓK⊤=Diag(M⊤u)−1M⊤Diag(u)\mathrm{Diag}(p^0)^{-1}\Gamma^{K\top} = \mathrm{Diag}(M^\top u)^{-1} M^\top \mathrm{Diag}(u) (Appendix D.1).
  • Masses enter only as log⁡p0\log p^0 in the log-domain Sinkhorn update.
  • Masses are strictly positive: they are a softmax-parameterized distribution over the pivots.
  • A small mass therefore cannot amplify rounding error. It only reduces the share of attention routed through that pivot.
  • Training behavior: consistent with this, we observed no numerical instability (no NaNs, loss spikes, or divergence) in any of our training or conversion runs.

Q3. Accuracy–throughput against optimized baselines, and reproducibility of conversion.

We redid the efficiency evaluation under a fully specified protocol, on an NVIDIA H200 against FlashAttention-3 (flash_attn_3 0.0.3), with batch size 1. The protocol covers warmup, the median over 200 forward passes, and CUDA-event timing (Appendix D.1). It is reported at two levels.

(i) Attention operator (Table 14, Figure 3; 16 heads, dk=64d_k = 64; LOTFormer r = 32, T = 5, ε=1\varepsilon = 1). Runtime in ms, then throughput in M tokens/s; HH = Hedgehog, LOT = LOTFormer, Flash = LOTFormer with FlashSinkhorn.

nFA3 msHH msLOT msFlash msFA3 tok/sHH tok/sLOT tok/sFlash tok/s
1k0.0210.0250.6460.61148.841.11.591.68
4k0.1480.1991.2940.66327.720.63.176.18
16k2.0611.6815.1762.4397.959.753.176.72
32k8.6432.80810.4033.5743.7911.73.159.17
64k34.0977.30120.5997.3991.928.983.188.86
128k142.81419.58239.34415.6130.926.693.338.40
  • Softmax: FlashAttention-3 throughput halves with every doubling of n.
  • LOTFormer: throughput is constant from 4k to 128k, about 3.2M tokens/s unfused and about 9M tokens/s with FlashSinkhorn from 32k. This is the O(nr)O(nr) signature.
  • Crossover with softmax: LOTFormer overtakes FlashAttention-3 at about 40k tokens unfused and about 18k with FlashSinkhorn. At 128k it is 3.6× and 9.1× faster.
  • Hedgehog: it is the fastest linear operator up to 32k at this shape and matches FlashSinkhorn LOTFormer at 64k. It is slower at 128k, where its unfused n×2dkn \times 2d_k feature maps dominate memory traffic.

(ii) End to end, paired with quality (Table 8; gte-Qwen2-7B; LOTFormer uses FlashSinkhorn). Softmax: nDCG@10; Ret.: retention relative to softmax; Speedup: end to end over FlashAttention-3; HH = Hedgehog, LOT = LOTFormer; the last row is throughput only.

TaskTokensContextSoftmaxRet. HHRet. LOTSpeedup HHSpeedup LOT
SummScreenFD≈7.3k8k94.295.6%99.4%0.80×0.92×
2WikiMQA≈8.0k8k71.094.1%98.7%0.80×0.92×
QMSum≈13k16k68.593.7%99.0%1.24×1.31×
NarrativeQA≈66k (truncated to 32k)32k52.392.0%98.3%1.75×2.05×
Average—≤ 32k71.594.1%98.9%——
Dummy tokens—64k / 128k———2.4× / 3.6×2.8× / 4.2×
  • On every task, LOTFormer is both more accurate and faster than Hedgehog.
  • Hedgehog loses quality as documents grow, falling from 95.6% to 92.0%. LOTFormer stays at or above 98.3%.
  • Against FlashAttention-3: LOTFormer is on par at 8k (0.92×), faster from 16k on, and its advantage grows with length, reaching 2.05× at 32k, 2.8× at 64k and 4.2× at 128k.

Dependence on model configuration (Appendix E.6). The ordering of Hedgehog and LOTFormer differs between (i) and (ii) because it depends on the number of heads H and the head dimension dkd_k.

  • Hedgehog's cost: its dk×dkd_k \times d_k feature map and 2dk×dk2d_k \times d_k state cost O(Hdk2)O(H d_k^2) per token.
  • LOTFormer's cost: O(Hrdk)O(H r d_k), plus O(HTr)O(H T r) for Sinkhorn.
  • From the operator shape to the model: going from (H = 16, dk=64d_k = 64) to gte-Qwen2-7B (H = 28, dk=128d_k = 128), Hedgehog's attention cost grows by about 7× and LOTFormer's by about 3×. Hedgehog's per-head state also becomes 8× larger than LOTFormer's (256×128 vs. 32×128).
  • What this means for comparisons: operator timings at one shape do not transfer directly to a model, which is why we report both levels.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Global response

We thank all reviewers for their careful reviews. All changes are marked in blue in the revised PDF. The main additions:

  1. Isolating double stochasticity (Table 7). We added a control that normalizes each plan with one softmax instead of Sinkhorn. This is the pivot (agent-token) attention of Agent Attention and Latte, so LOTFormer generalizes it. On DeiT-Tiny / ImageNet-1K, the doubly stochastic constraint adds +2.0 points, +1.7 without DWC and polarization, and +8.7 with 1% of the data. More Sinkhorn half-steps raise ImageNet-100 accuracy monotonically (80.5, 81.5, 82.1 at T = 1, 5, 10).
  2. Marginal accuracy (Tables 17–19). Both marginals hold at float32 rounding level (about 5×10−75\times10^{-7} per entry) up to 32k tokens, for 1.5B and 7B models. The column residual falls geometrically with T, and each layer re-normalizes, so residuals do not accumulate.
  3. Efficiency, re-measured (Tables 8 and 14). All methods are timed under one protocol on an H200 against FlashAttention-3. LOTFormer is 2.05×2.05\times faster end to end at 32k and 4.2×4.2\times at 128k (throughput only), and Table 8 now reports retrieval quality next to each speedup.
  4. Positioning (Tables 15 and 16). Linear-time doubly stochastic plans are known in OT. LOTFormer is, to our knowledge, the first doubly stochastic attention with linear runtime for an arbitrary learned cost. Under an identical conversion protocol, positive-feature Sinkhorn retains 76.6% against 98.3% for LOTFormer.
  5. Pivot size (Table 10). Train and test accuracy show a bias–variance trade-off: test accuracy peaks at r = 32, and beyond it the train–test gap grows from 5.7 to 17.6 points.
  6. Vision baselines (Table 12). Under identical components and recipe, LOTFormer leads FLatten and PolaFormer on DeiT-Tiny, with and without DWC.
  7. Clarity. We corrected the output equation and kernel scaling, defined T as Sinkhorn half-steps (T=2kT = 2k for kk full iterations), and added full conversion, initialization and timing details.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.