Pith. sign in

REVIEW 3 major objections 3 minor 68 references

Transformers Learn Faster with Semantic Focus

T0 review · 3 major / 3 minor · reviewed 2026-08-07 · deepseek-v4-flash

Pith's one-line read The paper claims that top-k attention makes transformers converge faster and generalize no worse than full attention, and derives stability bounds based on score dispersion and separation that explain when and why input-dependent sparsity…

desk verdict Solid controlled empirical evidence that top-k attention accelerates learning, but the stability theory's key separation condition is unverified along the training trajectory and violated on the very task where the speedup is largest. read the letter →

arxiv 2506.14095 v2 pith:XU7HWBUP submitted 2025-06-17 cs.LG

classification cs.LG MSC 68T0768Q32
keywords sparseattentiontop-kheavyhitterstransformeralgorithmicstabilityLipschitzconstantERMconvergencegeneralization
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Sparse attention is usually studied as a way to cut the quadratic cost of transformers; this paper asks instead whether it can make transformers easier to train, and answers yes for one specific form. Empirically, restricting each query to its top-k highest-scoring keys (heavy-hitter attention) reaches the same training accuracy in a fraction of the epochs (up to about 8.8x fewer on Even Pairs) and reaches equal or better held-out accuracy, while fixed patterns such as banded or block-local attention show no consistent benefit across eight structured-language tasks. The theoretical explanation chains softmax input-stability to the Lipschitz constant of the training loss, and shows that input-dependent heavy-hitter sparsity shrinks the range of scores the softmax sees ('semantic dispersion') enough to dominate full attention's stability constants, provided the attended scores are separated from the discarded ones by a gap. In short, the paper claims that concentrating attention on the semantically relevant tokens accelerates learning, and that this is a property of the learning problem, not of computational savings.

What carries the argument

The load-bearing quantities are the per-query 'semantic dispersion' $\delta$ (Definition 2: the largest gap between any two unmasked query-key dot products for a query) and, for heavy-hitter attention, the 'semantic separation' $\Delta$ (Definition 3: the smallest gap between an attended and a masked-out dot product). The argument chains them through four levels of constants: the masked softmax input-stability $\xi = e^\delta/k$ (times $(1+1/\Delta)$ for heavy hitters), the attention's stability constants $\lambda_X(\xi)$ and $\lambda_W(\xi)$ from Theorem 5, the transformer block's parameter-stability $\lambda_\theta(\xi)$ from Theorem 1, and finally the ERM objective's Lipschitz constant $\lambda_L(\xi)$ from Theorem 2. Because standard SGD convergence and algorithmic-stability generalization bounds both grow with the Lipschitz constant, any sparsity pattern that shrinks $\delta$ shrinks the bounds; heavy-hitter attention is the pattern that provably can, since it restricts the softmax to a narrow band of high scores.

What would settle it

Instrument a top-k transformer during training and record the per-query separation $\Delta_h$ and dispersion $\delta_h$ at every epoch. The stability mechanism predicts that the epochs showing the convergence edge over full attention are also the epochs where the corollary's inequalities hold; if a substantial fraction of queries have $\Delta_h$ near zero early in training while the speedup is still strong, the proposed mechanism is not what drives it. The controlled version is to construct a task where the k-th and (k+1)-th scores are forced to stay within $\varepsilon$ of each other throughout training, in which case the theory's $(1+1/\Delta_h)$ factor predicts that the advantage over full attention should vanish or reverse.

Watch

Extended reading notes

Core claim

The paper's central claim is that heavy-hitter (top-k) sparse attention improves learning convergence and generalization not despite but because of its sparsity, by making the softmax more stable as a function of its input. The argument runs through three results. First, Theorem 1 and Theorem 2 show that the Lipschitz constant of the ERM objective is an increasing function of the masked softmax's input-stability constant $\xi$, and that smaller Lipschitz constants directly improve standard SGD convergence rates and stability-based generalization bounds. Second, Theorem 3 and Theorem 4 bound $\xi$ for full attention and for $k$-regular input-agnostic masks: both give $\xi = e^{\delta}/k$ with a dispersion $\delta$ that is typically as large as full attention's, so input-agnostic sparsity buys nothing in worst-case stability. Third, Theorem 5 bounds the heavy-hitter softmax by $\xi_h = (e^{\delta_h}/k)(1+1/\Delta_h)$, where $\delta_h$ is the dispersion of only the attended scores and $\Delta_h$ is their separation from the discarded scores; since attended scores are concentrated, $\delta_h \ll \delta_s$, which can overcome the $(1+1/\Delta_h)$ factor. Corollary 1 turns this into explicit inequalities on $c_1 = \delta_h/\delta_s$ and $c_2 = \Delta_h/\delta_s$ under which $\lambda_W(\xi_h) < \lambda_W(\xi_s)$ and $\lambda_X(\xi_h) < \lambda_X(\xi_s)$, and the paper reports that dispersions and separations measured on trained models satisfy these inequalities in most cases.

Load-bearing premise

The load-bearing premise is that for every pair of inputs the top-k attention mask keeps a strictly positive separation gap $\Delta_h$ between the k-th and (k+1)-th dot-product scores; if that gap is ever vanishingly small, a tiny input perturbation can flip which tokens are selected, and the $(1 + 1/\Delta_h)$ factor in the stability bound explodes, and the paper only measures $\Delta_h$ on the final trained model rather than along the training trajectory.

Editorial extensions

If this is right

  • Top-k attention becomes a candidate architectural choice for learnability, not just for saving compute, since under the paper's conditions it provably reduces the Lipschitz constant of the training objective.
  • The predicted benefit scales with the number of attention heads, because multi-head attention multiplies the stability constants and amplifies any improvement in the softmax stability constant.
  • Adding global tokens restores expressivity to input-agnostic sparse attention but does not restore convergence speed, separating the question of capacity from the question of learnability.
  • Faster training with top-k attention does not indicate overfitting risk: on tasks where full attention generalizes, top-k attention matches or beats its final and best held-out accuracy.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • My inference: the separation condition makes the benefit task-dependent, so measuring the dispersion and separation on the first few batches could predict, before full training, whether a task will favor heavy-hitter attention.
  • My inference: the bounds are worst-case upper bounds, so the observed speedups could stem from other mechanisms such as implicit regularization; testing this would require estimating the effective Lipschitz constant along the whole trajectory rather than at the final model.
  • My inference: the paper's limitation section leaves decoder-only and pretrained settings open; a natural extension is whether top-k selection among causal keys preserves the speedup, since a causal mask already pre-shrinks the attended set.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 3 minor

Summary. The paper studies sparse attention in transformers from the perspective of learning convergence and in-distribution generalization rather than computational efficiency. Empirically (Section 4, 8 tasks, hyperparameter-controlled, 10 seeds), it finds that input-dependent heavy-hitter (top-k) sparse attention converges faster and generalizes at least as well as full attention, while input-agnostic sparse attention shows no consistent benefit. The theory (Section 5) links the input stability of the (masked) softmax to the Lipschitz constant of the ERM objective, and hence, via standard SGD guarantees, to convergence and generalization. Theorems 3–5 give stability constants for full, k-regular input-agnostic, and heavy-hitter attention; Corollary 1 gives conditions (Eqs. 24–25) under which the heavy-hitter bounds on λW and λX are smaller than full attention's. Table 5 evaluates these conditions at the final trained models; Appendix E.5 supplements with loss-surface Lipschitz estimates. The paper concludes that semantic focus explains the empirical benefit.

Significance. The empirical finding—that input-dependence of the sparsity pattern, not sparsity per se, is what accelerates learning—is clean and practically relevant, and the experiments are carefully controlled (same parameter count and hyperparameters, 10 seeds, ablations over activation, depth, heads, learning rate schedule, and Adam). The theoretical chain is detailed and largely self-contained, adapting known softmax stability lemmas, with thorough proofs in Appendices D and E. The paper also states falsifiable conditions (Corollary 1) and evaluates them empirically, which is a genuine strength; if those conditions were verified along the training trajectory and the Even Pairs discrepancy resolved, the work would be a useful bridge between efficient-attention architecture choices and learning-theoretic guarantees. Currently the significance is partially held back by the gap between the point at which the conditions are validated (the final model) and the regime in which the advantage develops (early training).

major comments (3)
  1. [Table 5, Eqs. (24)–(25), §E.5] For Even Pairs—the task with the largest measured speedup (8.83× in Table 3, 6 vs 53 epochs)—the reported left-hand sides of both inequalities exceed 1 at every percentile (3.17, 1.98, 1.31 for Eq. (24); 3.59, 2.40, 1.58 for Eq. (25)), so Corollary 1's sufficient conditions are not met even at the final trained model. The text acknowledges this as "counter to what we see in the empirical evaluations" and defers to the loss-surface analysis of Appendix E.5, but that analysis computes directional Lipschitz estimates only around the final optimum. Since the convergence advantage develops during training, the paper's central explanatory mechanism is unverified precisely for its strongest empirical case.
  2. [Appendix E.3, Assumption H1, Lemma S4] The heavy-hitter stability bound carries the factor (1 + 1/Δh), and H1 requires a uniform per-query semantic separation Δh > 0 for every pair of inputs. Top-k attention enforces no such margin: the gap between the k-th and (k+1)-th scores can be arbitrarily small, especially early in training when dot products are near-random, and the bound explodes as Δh → 0. Table 5 measures Δh only at the final trained model, where values as small as 0.002 already imply (1 + 1/Δh) ≈ 501. Because H1 is not verified over the parameter space visited during training, Theorem 5 and Corollary 1 rest on an unmeasured, load-bearing quantity.
  3. [Section 5 preamble, Theorem 2, Appendix A limitation 4] The theoretical comparison is between worst-case upper bounds on λW(ξ) and λX(ξ) (Table 1), not on the actual Lipschitz constant of the loss, as the paper itself concedes in Appendix A. Moreover, the step from a smaller bound on the Lipschitz constant to faster convergence and better generalization requires controlling the smoothness constant β of the objective, which enters multiplicatively in the quoted SGD and stability guarantees (ε ∼ O(βα²·…) and the Hardt et al. bound); β is neither bounded nor compared between full and sparse attention. The empirical Lipschitz estimates in E.5 are distributional estimates in two random directions around the optimum and cannot by themselves close the bound-versus-actual gap, so the inference from Corollary 1 to Observations 1 and 2 is heuristic at these points.
minor comments (3)
  1. [Abstract and §5.2] The wording that the theory "theoretically establish[es] that input-agnostic sparse attention does not provide any benefits" overstates Theorem 4, which shows that k-regular attention has the same bound as full attention when δr ≈ δs; the additional claim that δr cannot generally be small is argued heuristically (Fig. 9b), not proven.
  2. [Theorem 2, Eq. (16)] The closed-form expression contains (λX(ξ) − 1) in the denominator and is only valid for λX(ξ) > 1; the theorem statement should state this condition explicitly, even though it is plausibly satisfied under the paper's norm bounds.
  3. [Various sections] There are several typos and minor wording issues: "absense" (§4.1), "bottow row" (captions of Figures 2 and 3), "comparitively" (§4.1), "paramter" (Appendix D.1), and "left-hand-size" (Appendix E.3); these do not affect the substance.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found; the derivation is conditional on explicit dispersion and separation assumptions, supported by external lemmas and independent empirical checks.

full rationale

The paper's derivation chain runs from softmax input stability (Definition 1), via transformer-block stability (Theorem 1), to the Lipschitz constant of the ERM objective (Theorem 2), then specializes to full, regular-sparse, and heavy-hitter attention (Theorems 3-5) and compares them in Corollary 1. The softmax stability lemmas are adapted from Li et al. (2023), and the convergence/generalization connection comes from Hardt et al. (2016); these are external, independently published results, not author self-citations. The heavy-hitter bound is conditional: under assumptions H1 (per-query separation Delta_h > 0), H2 (bounded sink ratio beta k), H3 (norm bounds), and H4 (dispersion delta_h), it derives stability constants. Corollary 1 compares these constants with full attention under the parametric assumptions delta_h = c1 delta_s and Delta_h = c2 delta_s. Neither dispersion nor separation is fitted to reproduce the observed speedups; they are measured at the trained model as validation. The Even Pairs row of Table 5 shows the Corollary 1 inequalities failing at reported percentiles, and the paper explicitly acknowledges this is 'counter to what we see in the empirical evaluations' and defers to loss-surface analysis. That is an assumption-verification gap or correctness risk, not a circular argument: the conclusion is not equivalent to the inputs by construction, and no parameter fitted from the empirical curves is renamed as a prediction. The paper also has no load-bearing self-citation chain. Hence the appropriate circularity score is 0.

Assumptions & free parameters 2 free parameters · 6 assumptions · 0 invented entities

The theoretical claim rests on boundedness assumptions plus two data-dependent quantities, semantic dispersion and semantic separation, that are measured empirically. The separation axiom is the most fragile: it must hold uniformly over all input pairs for the heavy-hitter stability bound, but it is verified only at the final trained model. No new physical or architectural entities are introduced.

free parameters (2)
  • top-k sparsity k = 5 and 9
    Hand-selected sparsity levels for all tasks. Results are reported for both values and the claimed advantage persists, so it is not a parameter tuned to match a target result.
  • number of global tokens = 0, 1, 3
    Hand-selected for input-agnostic sparse attention experiments. Global tokens introduce a small number of extra learned parameters not present in the core theory.
assumptions (6)
  • domain assumption MLP activation sigma is lambda_sigma-Lipschitz with sigma(0)=0, and MLP parameter norms are bounded by B.
    Used in Lemma 1 to bound the stability of the MLP and LayerNorm components. Holds for ReLU, GELU, and Mish under bounded weights.
  • domain assumption Per-token embedding norms are bounded by Xi, query-key parameter norm is bounded by Gamma, value parameter norm is bounded by Upsilon, and the readout satisfies Phi norm at most 1.
    Standard bounded-input, bounded-weight assumptions used throughout Theorems 3, 4, and 5 to make the Lipschitz constants finite and comparable.
  • domain assumption The per-query semantic dispersion delta bounds the range of unmasked dot-products for each query, with delta_s at most 2 Gamma Xi squared for full attention.
    This is Definition 2 and the worst-case bound in Remark S1. The empirical value of delta is measured only on trained models, not uniformly over the training trajectory.
  • ad hoc to paper For any query-key pairs X and X-bar, the k-heavy-hitter mask has a minimum per-query semantic separation Delta_h > 0.
    Appendix E.3 assumption H1. This is invented to control how much the input-dependent mask can change under perturbation. Near-ties between the k-th and (k+1)-th scores would make Delta_h arbitrarily small and break the bound.
  • domain assumption At most beta k query tokens attend to any single key token, with beta > 1.
    Appendix E.3 assumption H2. Needed for the heavy-hitter lambda_X bound. The measured sink ratios reach 15 to 26 at the 95th percentile in Table 5, which weakens the lambda_X improvement.
  • domain assumption For SGD, convergence and generalization rates depend on the Lipschitz constant while the smoothness constant beta and learning-rate schedule are held fixed.
    Section 5 invokes standard SGD convergence and Hardt et al. stability theorems but then analyzes only the Lipschitz constant. The paper does not bound beta for sparse versus full attention.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Transformers Learn Faster with Semantic Focus." pith.science (2026). https://pith.science/paper/XU7HWBUP

@misc{pith2026250614095,
  author       = {Pith},
  title        = {Pith review of: Transformers Learn Faster with Semantic Focus},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/XU7HWBUP}},
  note         = {Machine review of arXiv:2506.14095}
}
read the original abstract

Various forms of sparse attention have been explored to mitigate the quadratic computational and memory cost of the attention mechanism in transformers. We study sparse transformers not through a lens of efficiency but rather in terms of learnability and generalization. Empirically studying a range of attention mechanisms, we find that input-dependent sparse attention models appear to converge faster and generalize better than standard attention models, while input-agnostic sparse attention models show no such benefits -- a phenomenon that is robust across architectural and optimization hyperparameter choices. This can be interpreted as demonstrating that concentrating a model's "semantic focus" with respect to the tokens currently being considered (in the form of input-dependent sparse attention) accelerates learning. We develop a theoretical characterization of the conditions that explain this behavior. We establish a connection between the stability of the standard softmax and the loss function's Lipschitz properties, then show how sparsity affects the stability of the softmax and the subsequent convergence and generalization guarantees resulting from the attention mechanism. This allows us to theoretically establish that input-agnostic sparse attention does not provide any benefits. We also characterize conditions when semantic focus (input-dependent sparse attention) can provide improved guarantees, and we validate that these conditions are in fact met in our empirical evaluations.

Figures

Figures reproduced from arXiv: 2506.14095 by the authors.

Figure 1
Figure 1. Visualizations of dot-product based attention scores matrices, which along with the value matrix [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Learning convergence and generalization curves for full attention and various sparse attention based [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗
Figure 3
Figure 3. Same as figure 2 with 4 more NNCH tasks. Further results with different mask sizes and different number of global tokens is presented in figure 13 (training cross-entropy) and figure 14 (training accuracy). † For the Modular Arithmetic, Solve Equation and Cycle Navigation tasks, all forms of attention have poor generalization, with a held-out accuracy as low as random guessing (20% for each of these 5-class classifi… view at source ↗
Figures from the paper (24 more)
Figure 4
Figure 4. Figure 4: Same as figure 2 for 3 of the tasks with GELU activation. See results for additional tasks and configurations in section C.2. Observation 3. The improvement of input-dependent heavy-hitter sparse attention over full attention in terms of learning convergence and genera…
Figure 5
Figure 5. Figure 5: Same as figure 2 for 3 of the tasks with Mish activation. See additional results in section C.2. The input-agnostic sparse attention models continue to converge comparably to full attention with ListOps and Missing Duplicates while falling behind in Even Pairs. One mar…
Figure 6
Figure 6. Figure 6: Comparison of full attention and top-k attention in terms of the training loss trajectory for varying model architectures with the ListOps task. In figure 6, we study the effect of varying the model architecture in terms of the number of transformer blocks or the numbe…
Figure 7
Figure 7. Figure 7: Comparison of full attention and top-k attention in terms of the training loss trajectory for varying optimization hyperparameters with the ListOps task. and vary the initial learning rate from 0.66 (column 1), 1.0 (column 2; used in previous experiments with ListOps),…
Figure 8
Figure 8. Figure 8: Varying learning rates for Adam optimizer. [PITH_FULL_IMAGE:figures/full_fig_p012_8.png]
Figure 9
Figure 9. Figure 9: Examples of per-query semantic dispersion [PITH_FULL_IMAGE:figures/full_fig_p016_9.png]
Figure 10
Figure 10. Figure 10: Top and middle rows: Loss surfaces of the models with full attention (top row) and top-k attention (middle row) for the tasks considered in figure 2 with the corresponding hyperparameters utilizing the filter-normalized version of the loss landscape visualization. The…
Figure 11
Figure 11. Figure 11: Training cross-entropy (vertical axis, lower is better) vs number of epochs (horizontal axis) across [PITH_FULL_IMAGE:figures/full_fig_p029_11.png]
Figure 12
Figure 12. Figure 12: Training accuracy (vertical axis – higher is better) vs number of epochs (horizontal axis) across [PITH_FULL_IMAGE:figures/full_fig_p030_12.png]
Figure 13
Figure 13. Figure 13: Training cross-entropy (vertical axis, lower is better) vs number of epochs (horizontal axis) across [PITH_FULL_IMAGE:figures/full_fig_p032_13.png]
Figure 14
Figure 14. Figure 14: Training accuracy (vertical axis – higher is better) vs number of epochs (horizontal axis) across [PITH_FULL_IMAGE:figures/full_fig_p033_14.png]
Figure 15
Figure 15. Figure 15: Same as figure 11 with GELU activation in the MLP component of the transformer block. where a and b are the scale and shift hyperparameter. Then LayerNorm is Lipschitz with ζLN = ϵ − 1 2 ∥a∥∞(d 2−2)/d in equation (29). For equation (26), we have the following: ∥MLPP,R…
Figure 16
Figure 16. Figure 16: Same as figure 12 with GELU activation in the MLP component of the transformer block. With activations such as ReLU, the MLP(x) = R⊤σ(Px) are often positive homogeneous such that, for any α ̸= 0, we have R⊤σ(Px) = αR⊤σ(α −1Px), leading to symmetries in the paramter sp…
Figure 17
Figure 17. Figure 17: Same as figure 11 with Mish activation in the MLP component of the transformer block. D.2 Proof of Theorem 1 Theorem S1. Given definition 1 and lemma 1, a transformer block TF with learnable parameters θ = (W, V, P, R) is λθ(ξ)-Lipschitz with respect to its learnable …
Figure 18
Figure 18. Figure 18: Same as figure 12 with Mish activation in the MLP component of the transformer block. (T1) = ∥TFW,V,P,R(X) − TFW,V,P,R¯ (X)∥2,1 = ∥LN(Xe + MLPP,R(Xe )) − LN(Xe + MLPP,R¯ (Xe ))∥2,1 (45) = X i∈JLK ∥LN(Xe :i + MLPP,R(Xe :i)) − LN(Xe :i + MLPP,R¯ (Xe :i))∥ (46) ≤ X i∈JLK…
Figure 19
Figure 19. Figure 19: Same as figure 13 with GELU activation in the MLP component of the transformer block. (T3) = ∥TFW,V,P¯ ,R¯ (X) − TFW,V¯ ,P¯ ,R¯ (X)∥2,1 = ∥LN(Xe + MLPP¯ ,R¯ (Xe )) − LN(Xe ′ + MLPP¯ ,R¯ (Xe ′ ))∥2,1 (53) = X i∈JLK ∥LN(Xe :i + MLPP¯ ,R¯ (Xe :i)) − LN(Xe ′ :i + MLPP¯ ,R…
Figure 20
Figure 20. Figure 20: Same as figure 14 with GELU activation in the MLP component of the transformer block. = ∥LN(Xe ′ + MLPP¯ ,R¯ (Xe ′ )) − LN(Xe ′′ + MLPP¯ ,R¯ (Xe ′′))∥2,1 (62) = X i∈JLK ∥LN(Xe ′ :i + MLPP¯ ,R¯ (Xe ′ :i )) − LN(Xe ′′ :i + MLPP¯ ,R¯ (Xe ′′ :i ))∥ (63) ≤ X i∈JLK ζLN∥(Xe …
Figure 21
Figure 21. Figure 21: Relationship of c1, c2, δs in equation (24). For any value of δs, the region above the line de￾notes values of c1, c2 for which λW (ξh) < λW (ξs). Note that, once δs is large enough, c2 can be very small, and c1 can be quite large. Based on this result, we want the co…
Figure 22
Figure 22. Figure 22: Relationship of c1, c2, δs, β in equation (25). For any value of δs and β, the region above the line denotes values of c1, c2 for which λX(ξh) < λX(ξs). In these figures, we assume δs = 2ΓΞ2 so that we just need to vary δs without considering different values of Γ and…
Figure 23
Figure 23. Figure 23: Loss surfaces of the models with full attention (top row) and top- [PITH_FULL_IMAGE:figures/full_fig_p059_23.png]
Figure 24
Figure 24. Figure 24: Loss surfaces as in figure 23 but in the form of heatmaps instead of contour plots. 1.0 0.5 0.0 0.5 1.0 1.00 0.75 0.50 0.25 0.00 0.25 0.50 0.75 1.00 STANDARD 0.51 0.540.56 0.59 0.62 0.65 0.71 0.68 0.78 0.74 0.81 0.89 0.85 1.02 0.97 0.93 1.07 1.12 1.47 1.34 1.22 1.40 1…
Figure 25
Figure 25. Figure 25: Loss surfaces as in figure 23 of the models with full attention (top row) and top-k attention (bottow row) for each of the 4 tasks considered in figure 2 and table 3. Note that both forms of attention now utilize the MLP with GELU activation for all tasks (as opposed …
Figure 26
Figure 26. Figure 26: Loss surfaces as in figure 25 but in the form of heatmaps instead of contour plots. 0.0 0.2 0.4 0.6 Grid range around 0 10 20 30 40 50 Distrib utio n of | ( ) ( )| || || FULL:50% FULL:75% FULL:95% FULL:99% TOPK:50% TOPK:75% TOPK:95% TOPK:99% (a) ListOps 0.0 0.2 0.4 0.…
Figure 27
Figure 27. Figure 27: Distribution of the estimated Lipschitz constants computed in the random directions utilized to [PITH_FULL_IMAGE:figures/full_fig_p061_27.png]

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

68 extracted references · 50 canonical work pages

  1. [1]

    Attention is all you need

    Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, ukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in neural information processing systems, 30, 2017. URL https://proceedings.neurips.cc/paper/2017/file/3f5ee243547dee91fbd053c1c4a845aa-Paper.pdf

  2. [2]

    Are transformers universal approximators of sequence-to-sequence functions? In International Conference on Learning Representations, 2020 a

    Chulhee Yun, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank Reddi, and Sanjiv Kumar. Are transformers universal approximators of sequence-to-sequence functions? In International Conference on Learning Representations, 2020 a . URL https://openreview.net/forum?id=ByxRM0Ntvr

  3. [3]

    Efficient transformers: A survey

    Yi Tay, Mostafa Dehghani, Dara Bahri, and Donald Metzler. Efficient transformers: A survey. ACM Computing Surveys, 55 0 (6), 2022. ISSN 0360-0300. URL https://doi.org/10.1145/3530811

  4. [4]

    Long range arena: A benchmark for efficient transformers

    Yi Tay, Mostafa Dehghani, Samira Abnar, Yikang Shen, Dara Bahri, Philip Pham, Jinfeng Rao, Liu Yang, Sebastian Ruder, and Donald Metzler. Long range arena: A benchmark for efficient transformers. In International Conference on Learning Representations, 2021. URL https://openreview.net/forum?id=qVyeW-grC2k

  5. [5]

    Cognitive Mechanisms Associated with Auditory Sensory Gating

    LA Jones, PJ Hills, KM Dick, SP Jones, and P Bright. Cognitive Mechanisms Associated with Auditory Sensory Gating . Brain and cognition, 102: 0 33--45, 2016. URL https://www.sciencedirect.com/science/article/pii/S0278262615300440

  6. [6]

    The Senses: A Comprehensive Reference

    Bernd Fritzsch. The Senses: A Comprehensive Reference . Academic Press, 2020

  7. [7]

    Sensory gating deficits in schizophrenia: new results

    LL Judd, L McAdams, B Budnick, and DL Braff. Sensory gating deficits in schizophrenia: new results. The American journal of psychiatry, 149 0 (4): 0 488--493, 1992. URL https://pubmed.ncbi.nlm.nih.gov/1554034/

  8. [8]

    The consciousness prior, 2019

    Yoshua Bengio. The consciousness prior, 2019. URL https://arxiv.org/abs/1709.08568

Show all 68 references
  1. [9]

    URL https://neurosymbolic.github.io/nsss2024

    3rd Neuro-Symbolic AI Summer School , 2024. URL https://neurosymbolic.github.io/nsss2024

  2. [10]

    Neural machine translation by jointly learning to align and translate, 2016

    Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. Neural machine translation by jointly learning to align and translate, 2016. URL https://arxiv.org/abs/1409.0473

  3. [11]

    Neural networks and the chomsky hierarchy

    Gregoire Deletang, Anian Ruoss, Jordi Grau-Moya, Tim Genewein, Li Kevin Wenliang, Elliot Catt, Chris Cundy, Marcus Hutter, Shane Legg, Joel Veness, and Pedro A Ortega. Neural networks and the chomsky hierarchy. In The Eleventh International Conference on Learning Representatio...

  4. [12]

    O(n) connections are expressive enough: Universal approximability of sparse transformers

    Chulhee Yun, Yin-Wen Chang, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank Reddi, and Sanjiv Kumar. O(n) connections are expressive enough: Universal approximability of sparse transformers. Advances in Neural Information Processing Systems, 33: 0 13783--13794, 2020 b . URL h...

  5. [13]

    Etc: Encoding long and structured inputs in transformers

    Joshua Ainslie, Santiago Ontanon, Chris Alberti, Vaclav Cvicek, Zachary Fisher, Philip Pham, Anirudh Ravula, Sumit Sanghai, Qifan Wang, and Li Yang. Etc: Encoding long and structured inputs in transformers. In Proceedings of the 2020 Conference on Empirical Methods in Natural ...

  6. [14]

    Big bird: Transformers for longer sequences

    Manzil Zaheer, Guru Guruganesh, Kumar Avinava Dubey, Joshua Ainslie, Chris Alberti, Santiago Ontanon, Philip Pham, Anirudh Ravula, Qifan Wang, Li Yang, et al. Big bird: Transformers for longer sequences. Advances in neural information processing systems, 33: 0 17283--17297, 20...

  7. [15]

    Memory-efficient transformers via top-k attention

    Ankit Gupta, Guy Dar, Shaya Goodman, David Ciprut, and Jonathan Berant. Memory-efficient transformers via top-k attention. In Proceedings of the Second Workshop on Simple and Efficient Natural Language Processing, pages 39--52. Association for Computational Linguistics, 2021. ...

  8. [16]

    ZETA : Leveraging z -order curves for efficient top- k attention

    QIUHAO Zeng, Jerry Huang, Peng Lu, Gezheng Xu, Boxing Chen, Charles Ling, and Boyu Wang. ZETA : Leveraging z -order curves for efficient top- k attention. In The Thirteenth International Conference on Learning Representations, 2025. URL https://openreview.net/forum?id=j9VVzueEbG

  9. [17]

    Algorithmic stability and generalization performance

    Olivier Bousquet and Andr \'e Elisseeff. Algorithmic stability and generalization performance. Advances in Neural Information Processing Systems, 13, 2000. URL https://proceedings.neurips.cc/paper_files/paper/2000/file/49ad23d1ec9fa4bd8d77d02681df5cfa-Paper.pdf

  10. [18]

    Train faster, generalize better: Stability of stochastic gradient descent

    Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. In International conference on machine learning, pages 1225--1234. PMLR, 2016. URL https://arxiv.org/pdf/1509.01240

  11. [19]

    Formal algorithms for transformers

    Mary Phuong and Marcus Hutter. Formal algorithms for transformers. arXiv preprint arXiv:2207.09238, 2022. URL https://arxiv.org/pdf/2207.09238.pdf

  12. [20]

    A survey of transformers

    Tianyang Lin, Yuxin Wang, Xiangyang Liu, and Xipeng Qiu. A survey of transformers. AI Open, 2022. URL https://www.sciencedirect.com/science/article/pii/S2666651022000146

  13. [21]

    Image transformer

    Niki Parmar, Ashish Vaswani, Jakob Uszkoreit, Lukasz Kaiser, Noam Shazeer, Alexander Ku, and Dustin Tran. Image transformer. In International conference on machine learning, pages 4055--4064. PMLR, 2018. URL https://proceedings.mlr.press/v80/parmar18a/parmar18a.pdf

  14. [22]

    Blockwise self-attention for long document understanding

    Jiezhong Qiu, Hao Ma, Omer Levy, Wen-tau Yih, Sinong Wang, and Jie Tang. Blockwise self-attention for long document understanding. In Findings of the Association for Computational Linguistics: EMNLP 2020, pages 2555--2565, 2020. URL https://aclanthology.org/2020.findings-emnlp.232/

  15. [23]

    Longformer: The long-document transformer

    Iz Beltagy, Matthew E Peters, and Arman Cohan. Longformer: The long-document transformer. arXiv preprint arXiv:2004.05150, 2020. URL https://arxiv.org/abs/2004.05150

  16. [24]

    Generating long sequences with sparse transformers

    Rewon Child, Scott Gray, Alec Radford, and Ilya Sutskever. Generating long sequences with sparse transformers. arXiv preprint arXiv:1904.10509, 2019. URL https://arxiv.org/abs/1904.10509

  17. [25]

    Sparse sinkhorn attention

    Yi Tay, Dara Bahri, Liu Yang, Donald Metzler, and Da-Cheng Juan. Sparse sinkhorn attention. Proceedings of ICML, 2020. URL http://proceedings.mlr.press/v119/tay20a/tay20a.pdf

  18. [26]

    Efficient content-based sparse attention with routing transformers

    Aurko Roy, Mohammad Saffar, Ashish Vaswani, and David Grangier. Efficient content-based sparse attention with routing transformers. Transactions of the Association for Computational Linguistics, 9: 0 53--68, 2021. URL https://direct.mit.edu/tacl/article/doi/10.1162/tacl_a_00353/

  19. [27]

    Reformer: The efficient transformer

    Nikita Kitaev, Lukasz Kaiser, and Anselm Levskaya. Reformer: The efficient transformer. In International Conference on Learning Representations, 2020. URL https://openreview.net/pdf?id=rkgNKkHtvB

  20. [28]

    COGS : A compositional generalization challenge based on semantic interpretation

    Najoung Kim and Tal Linzen. COGS : A compositional generalization challenge based on semantic interpretation. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 9087--9105, 2020. URL https://aclanthology.org/2020.emnlp-main.731.pdf

  21. [29]

    Generalization without systematicity: On the compositional skills of sequence-to-sequence recurrent networks

    Brenden Lake and Marco Baroni. Generalization without systematicity: On the compositional skills of sequence-to-sequence recurrent networks. In International Conference on Machine Learning, pages 2873--2882. PMLR, 2018. URL https://proceedings.mlr.press/v80/lake18a.html

  22. [30]

    When can transformers ground and compose: Insights from compositional generalization benchmarks

    Ankur Sikarwar, Arkil Patel, and Navin Goyal. When can transformers ground and compose: Insights from compositional generalization benchmarks. In Yoav Goldberg, Zornitsa Kozareva, and Yue Zhang, editors, Proceedings of the 2022 Conference on Empirical Methods in Natural Langua...

  23. [31]

    The devil is in the detail: Simple tricks improve systematic generalization of transformers

    R \'o bert Csord \'a s, Kazuki Irie, and Juergen Schmidhuber. The devil is in the detail: Simple tricks improve systematic generalization of transformers. In Marie-Francine Moens, Xuanjing Huang, Lucia Specia, and Scott Wen-tau Yih, editors, Proceedings of the 2021 Conference ...

  24. [32]

    Making transformers solve compositional tasks

    Santiago Ontanon, Joshua Ainslie, Zachary Fisher, and Vaclav Cvicek. Making transformers solve compositional tasks. In Smaranda Muresan, Preslav Nakov, and Aline Villavicencio, editors, Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Vo...

  25. [33]

    Inducing transformer ' s compositional generalization ability via auxiliary sequence prediction tasks

    Yichen Jiang and Mohit Bansal. Inducing transformer ' s compositional generalization ability via auxiliary sequence prediction tasks. In Marie-Francine Moens, Xuanjing Huang, Lucia Specia, and Scott Wen-tau Yih, editors, Proceedings of the 2021 Conference on Empirical Methods ...

  26. [34]

    a rli, Ekin Aky \

    Andrew Drozdov, Nathanael Sch \"a rli, Ekin Aky \"u rek, Nathan Scales, Xinying Song, Xinyun Chen, Olivier Bousquet, and Denny Zhou. Compositional semantic parsing with large language models. In The Eleventh International Conference on Learning Representations, 2023. URL https...

  27. [35]

    What formal languages can transformers express? a survey

    Lena Strobl, William Merrill, Gail Weiss, David Chiang, and Dana Angluin. What formal languages can transformers express? a survey. Transactions of the Association for Computational Linguistics, 12: 0 543--561, 2024. URL https://direct.mit.edu/tacl/article/doi/10.1162/tacl_a_0...

  28. [36]

    On the ability and limitations of transformers to recognize formal languages

    Satwik Bhattamishra, Kabir Ahuja, and Navin Goyal. On the ability and limitations of transformers to recognize formal languages. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 7096--7116, 2020. URL https://aclanthology....

  29. [37]

    Theoretical limitations of self-attention in neural sequence models

    Michael Hahn. Theoretical limitations of self-attention in neural sequence models. Transactions of the Association for Computational Linguistics, 8: 0 156--171, 2020. URL https://direct.mit.edu/tacl/article/doi/10.1162/tacl_a_00306/43545

  30. [38]

    Formal language recognition by hard attention transformers: Perspectives from circuit complexity

    Yiding Hao, Dana Angluin, and Robert Frank. Formal language recognition by hard attention transformers: Perspectives from circuit complexity. Transactions of the Association for Computational Linguistics, 10: 0 800--810, 2022. URL https://transacl.org/ojs/index.php/tacl/articl...

  31. [39]

    Saturated transformers are constant-depth threshold circuits

    William Merrill, Ashish Sabharwal, and Noah A Smith. Saturated transformers are constant-depth threshold circuits. Transactions of the Association for Computational Linguistics, 10: 0 843--856, 2022. URL https://transacl.org/ojs/index.php/tacl/article/view/3465

  32. [40]

    Overcoming a theoretical limitation of self-attention

    David Chiang and Peter Cholak. Overcoming a theoretical limitation of self-attention. In Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 7654--7664, 2022. URL https://aclanthology.org/2022.acl-long.527/

  33. [41]

    Tighter bounds on the expressivity of transformer encoders

    David Chiang, Peter Cholak, and Anand Pillay. Tighter bounds on the expressivity of transformer encoders. In International Conference on Machine Learning, pages 5544--5562. PMLR, 2023. URL https://proceedings.mlr.press/v202/chiang23a.html

  34. [42]

    Transformers as algorithms: Generalization and stability in in-context learning

    Yingcong Li, Muhammed Emrullah Ildiz, Dimitris Papailiopoulos, and Samet Oymak. Transformers as algorithms: Generalization and stability in in-context learning. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, ...

  35. [43]

    Transformers learn in-context by gradient descent

    Johannes Von Oswald, Eyvind Niklasson, Ettore Randazzo, Jo \ a o Sacramento, Alexander Mordvintsev, Andrey Zhmoginov, and Max Vladymyrov. Transformers learn in-context by gradient descent. In International Conference on Machine Learning, pages 35151--35174. PMLR, 2023. URL htt...

  36. [44]

    The emergence of clusters in self-attention dynamics

    Borjan Geshkovski, Cyril Letrouit, Yury Polyanskiy, and Philippe Rigollet. The emergence of clusters in self-attention dynamics. Advances in Neural Information Processing Systems, 36, 2023. URL https://proceedings.neurips.cc/paper_files/paper/2023/file/b2b3e1d9840eba17ad9bbf07...

  37. [45]

    Transformers learn to implement preconditioned gradient descent for in-context learning

    Kwangjun Ahn, Xiang Cheng, Hadi Daneshmand, and Suvrit Sra. Transformers learn to implement preconditioned gradient descent for in-context learning. Advances in Neural Information Processing Systems, 36, 2023. URL https://proceedings.neurips.cc/paper_files/paper/2023/file/8ed3...

  38. [46]

    Trained transformers learn linear models in-context

    Ruiqi Zhang, Spencer Frei, and Peter L Bartlett. Trained transformers learn linear models in-context. Journal of Machine Learning Research, 25 0 (49): 0 1--55, 2024. URL https://www.jmlr.org/papers/volume25/23-1042/23-1042.pdf

  39. [47]

    Why are adaptive methods good for attention models? Advances in Neural Information Processing Systems, 33: 0 15383--15393, 2020

    Jingzhao Zhang, Sai Praneeth Karimireddy, Andreas Veit, Seungyeon Kim, Sashank Reddi, Sanjiv Kumar, and Suvrit Sra. Why are adaptive methods good for attention models? Advances in Neural Information Processing Systems, 33: 0 15383--15393, 2020. URL https://proceedings.neurips....

  40. [48]

    Toward understanding why adam converges faster than SGD for transformers

    Yan Pan and Yuanzhi Li. Toward understanding why adam converges faster than SGD for transformers. In OPT 2022: Optimization for Machine Learning (NeurIPS 2022 Workshop), 2022. URL https://openreview.net/forum?id=Sf1NlV2r6PO

  41. [49]

    How does adaptive optimization impact local neural network geometry? Advances in Neural Information Processing Systems, 36: 0 8305--8384, 2023

    Kaiqi Jiang, Dhruv Malik, and Yuanzhi Li. How does adaptive optimization impact local neural network geometry? Advances in Neural Information Processing Systems, 36: 0 8305--8384, 2023. URL https://proceedings.neurips.cc/paper_files/paper/2023/file/1a5e6d0441a8e1eda9a50717b087...

  42. [50]

    Noise is not the main factor behind the gap between sgd and adam on transformers, but sign descent might be

    Frederik Kunstner, Jacques Chen, Jonathan Wilder Lavington, and Mark Schmidt. Noise is not the main factor behind the gap between sgd and adam on transformers, but sign descent might be. In The Eleventh International Conference on Learning Representations, 2023. URL https://op...

  43. [51]

    Linear attention is (maybe) all you need (to understand transformer optimization)

    Kwangjun Ahn, Xiang Cheng, Minhak Song, Chulhee Yun, Ali Jadbabaie, and Suvrit Sra. Linear attention is (maybe) all you need (to understand transformer optimization). In The Twelfth International Conference on Learning Representations, 2024. URL https://openreview.net/forum?id...

  44. [52]

    On the optimization and generalization of two-layer transformers with sign gradient descent

    Bingrui Li, Wei Huang, Andi Han, Zhanpeng Zhou, Taiji Suzuki, Jun Zhu, and Jianfei Chen. On the optimization and generalization of two-layer transformers with sign gradient descent. In The Thirteenth International Conference on Learning Representations, 2025. URL https://openr...

  45. [53]

    Layer normalization

    Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E Hinton. Layer normalization. arXiv preprint arXiv:1607.06450, 2016. URL https://arxiv.org/pdf/1607.06450

  46. [54]

    Root mean square layer normalization

    Biao Zhang and Rico Sennrich. Root mean square layer normalization. Advances in Neural Information Processing Systems, 32, 2019. URL https://proceedings.neurips.cc/paper/2019/file/1e8a19426224ca89e83cef47f1e7f53b-Paper.pdf

  47. [55]

    BERT : Pre-training of deep bidirectional transformers for language understanding

    Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. BERT : Pre-training of deep bidirectional transformers for language understanding. In Proceedings of the 2019 Conference of the North A merican Chapter of the Association for Computational Linguistics: Human Lan...

  48. [56]

    Bridging nonlinearities and stochastic regularizers with gaussian error linear units

    Dan Hendrycks and Kevin Gimpel. Bridging nonlinearities and stochastic regularizers with gaussian error linear units. CoRR, abs/1606.08415, 2016. URL http://arxiv.org/abs/1606.08415

  49. [57]

    Fast and accurate deep network learning by exponential linear units ( ELU s)

    Djork-Arn \'e Clevert, Thomas Unterthiner, and Sepp Hochreiter. Fast and accurate deep network learning by exponential linear units ( ELU s). arXiv preprint arXiv:1511.07289, 2015. URL https://arxiv.org/abs/1511.07289

  50. [58]

    Listops: A diagnostic dataset for latent tree learning

    Nikita Nangia and Samuel Bowman. Listops: A diagnostic dataset for latent tree learning. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Student Research Workshop, pages 92--99, 2018. URL https://aclantholog...

  51. [59]

    Mish: A self regularized non-monotonic neural activation function

    Diganta Misra. Mish: A self regularized non-monotonic neural activation function. CoRR, abs/1908.08681, 2019. URL http://arxiv.org/abs/1908.08681

  52. [60]

    Kingma and Jimmy Ba

    Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In The Third International Conference on Learning Representations, 2015. URL http://arxiv.org/abs/1412.6980

  53. [61]

    The lipschitz constant of self-attention

    Hyunjik Kim, George Papamakarios, and Andriy Mnih. The lipschitz constant of self-attention. In International Conference on Machine Learning, pages 5562--5571. PMLR, 2021. URL https://arxiv.org/pdf/2006.04710

  54. [62]

    Explicit sparse transformer: Concentrated attention through explicit selection

    Guangxiang Zhao, Junyang Lin, Zhiyuan Zhang, Xuancheng Ren, Qi Su, and Xu Sun. Explicit sparse transformer: Concentrated attention through explicit selection. CoRR, abs/1912.11637, 2019. URL http://arxiv.org/abs/1912.11637

  55. [63]

    Visualizing the loss landscape of neural nets

    Hao Li, Zheng Xu, Gavin Taylor, Christoph Studer, and Tom Goldstein. Visualizing the loss landscape of neural nets. Advances in neural information processing systems, 31, 2018. URL https://proceedings.neurips.cc/paper_files/paper/2018/file/a41b3bb3e6b050b6c9067c67f663b915-Paper.pdf

  56. [64]

    Never train from scratch: Fair comparison of long-sequence models requires data-driven priors

    Ido Amos, Jonathan Berant, and Ankit Gupta. Never train from scratch: Fair comparison of long-sequence models requires data-driven priors. In The Twelfth International Conference on Learning Representations, 2024. URL https://openreview.net/forum?id=PdaPky8MUn

  57. [65]

    Learning overparameterized neural networks via stochastic gradient descent on structured data

    Yuanzhi Li and Yingyu Liang. Learning overparameterized neural networks via stochastic gradient descent on structured data. Advances in neural information processing systems, 31, 2018. URL https://proceedings.neurips.cc/paper_files/paper/2018/file/54fe976ba170c19ebae453679b362...

  58. [66]

    A convergence theory for deep learning via over-parameterization

    Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over-parameterization. In International conference on machine learning, pages 242--252. PMLR, 2019. URL https://proceedings.mlr.press/v97/allen-zhu19a/allen-zhu19a.pdf

  59. [67]

    Gradient descent optimizes over-parameterized deep relu networks

    Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Gradient descent optimizes over-parameterized deep relu networks. Machine learning, 109: 0 467--492, 2020. URL https://link.springer.com/content/pdf/10.1007/s10994-019-05839-6.pdf

  60. [68]

    Convergence rates for the stochastic gradient descent method for non-convex objective functions

    Benjamin Fehrman, Benjamin Gess, and Arnulf Jentzen. Convergence rates for the stochastic gradient descent method for non-convex objective functions. Journal of Machine Learning Research, 21 0 (136): 0 1--48, 2020. URL https://jmlr.csail.mit.edu/papers/volume21/19-636/19-636.pdf

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.