Pith. sign in

REVIEW 1 major objections 2 minor 36 references

Attention-based representations for multi-task computation

T0 review · 1 major / 2 minor · reviewed 2026-08-08 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read One softmax attention head cannot cheaply feed linear classifiers for both min and max — two heads need only logarithmic dimension — and n-bit XOR forces the product of heads and polynomial degree to be at least n, with the bound provably…

desk verdict Clean, rigorous lower bounds on single-layer attention head counts; one repairable gap in the matching upper bound proof. read the letter →

arxiv 2608.04243 v1 pith:BQXNM7WF submitted 2026-08-04 cs.LG

Daniel Hsu , Mingyue Xu This is my paper · ORCID
classification cs.LG MSC 68T0768Q32
keywords multi-headattentionsoftmaxthresholddegreeparitymin-maxcomputationadditivebasespolynomialfunctionrepresentations
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

This paper asks how much a single attention head must sacrifice in width and precision to do what several heads do for free, and answers with two exact resource tradeoffs. Theorem 1: a single softmax head whose value vectors live in dimension $d$ with $p$ bits of precision cannot simultaneously let linear classifiers read off the minimum and maximum of an $n$-element list over $[M]$ unless $d(1+p+\log_2\ell)\ge\min\{\lfloor 1+\sqrt{M-1}\rfloor,\lfloor(n-1)/2\rfloor\}$, while two heads solve the same task with dimension $\lceil 8\ln M\rceil$ and zero bit precision — an exponential gap in embedding resources. Theorem 2: any $H$-head attention layer followed by a degree-$D$ polynomial threshold function that computes $n$-bit XOR must satisfy $D\times H\ge n$, and Theorem 3 shows this is tight, with value-vector dimension as small as $O(\min\{D,\log H\})$; the same degree-times-heads law governs every symmetric Boolean function, with $n$ replaced by its threshold degree. The upshot is a provable sense in which head count is a parallel-computation resource that a single head cannot recover by raising its dimension or precision.

What carries the argument

For the min/max theorem the load-bearing objects are monotone subsequences of attention weights and an approximately triangular configuration of value vectors. The Erdős–Szekeres theorem guarantees that any assignment of unnormalized attention weights over $[M]$ contains a long increasing or decreasing run; an increasing run obstructs the min classifier, a decreasing run obstructs the max classifier, and whichever obstruction appears translates, through one-sided inner-product inequalities of the Lasso irrepresentable type, into a system of near-triangular constraints on the value vectors. A volume argument then shows that integer-lattice vectors of bounded norm can satisfy such constraints only if their span grows slowly: each rank-preserving step multiplies a change-of-basis determinant by at least $1/(r\epsilon)$, while Hadamard's inequality and the integrality of $\det(A^\top A)$ cap the total volume, yielding the dimension-precision lower bound. For the XOR theorem the key object is the rational representation of softmax attention: over $\{0,1\}^n$ each head's output is an affine function divided by a positive affine function, so an $H$-head layer is a single rational function with numerator and denominator of degree at most $H$; composing with a degree-$D$ polynomial produces a degree-$DH$ polynomial that sign-represents the target, and the threshold degree of the target then forces $D\times H\ge T$. The matching constructions run on two further devices: factoring the univariate sign-representing polynomial into partial products (value dimension $D$), and additive $D$-bases — postage-stamp bases — drawn from $[H]$ with range $DH$ (value dimension $O(\log H)$).

What would settle it

For the min/max theorem, search small exact instances — say $M=10$, $n=8$ — for a single head whose dimension and precision violate $d(1+p+\log_2\ell)\ge\min\{\lfloor 1+\sqrt{M-1}\rfloor,\lfloor(n-1)/2\rfloor\}$ yet still admit two unambiguous linear classifiers that are correct on all $M^n$ inputs; any such configuration refutes the bound. For the XOR theorem, exhaustively optimize plain softmax layers with $H$ heads and degree-$D$ polynomial readouts on all $2^n$ parity strings for pairs with $D\times H<n$; Theorem 2 predicts that no parameter setting succeeds no matter how large the value-vector dimension, so a single exact solution would falsify the claim.

Watch

Extended reading notes

Core claim

On the paper's own terms, the discovery is that head count exchanges against other resources through two clean quantitative laws. In the min/max scenario, exact linear readouts of both the smallest and largest of $n$ numbers from $[M]$ force the resource product $d(1+p+\log_2\ell)$ of a single head to exceed $\min\{\lfloor 1+\sqrt{M-1}\rfloor,\lfloor(n-1)/2\rfloor\}$; because two ordinary heads achieve both tasks with $d=\lceil 8\ln M\rceil$ and $p=0$, any single head that tries to do both must blow up its value-vector dimension, its precision, or both — exponentially so when $M$ is polynomial in $n$. In the XOR scenario, the authors identify the invariant that controls multi-head computation: the threshold degree. If an $H$-head attention layer post-processed by a degree-$D$ polynomial threshold function computes a Boolean function of threshold degree $T$, then $D\times H\ge T$; parity has $T=n$, so computing $n$-bit XOR costs at least $n$ in the product of heads and degree, regardless of value-vector dimension. They then build explicit $H$-head layers for every factorization $D\times H\ge T$ of a symmetric function's threshold degree, using value-vector dimension at most $\min\{D,\,2\max\{1,\lceil\log_2 H\rceil\}+2\}$, so the lower bound is exactly tight.

Load-bearing premise

The lower bounds are proven only for plain softmax attention with linear or polynomial readouts, and the XOR bound specifically relies on each head's output being one straight-line formula divided by another over the input bits; add layer normalization, positional encodings, or nonlinear value transformations and that exact rational form breaks, so the head-degree tradeoff need not transfer.

Editorial extensions

If this is right

  • For min and max over $M=\mathrm{poly}(n)$ values, one attention head must spend exponentially more embedding resources than two heads: the product of dimension and precision must grow like $\sqrt{n}$, versus $d=\lceil 8\ln M\rceil$ and $p=0$ for two heads.
  • Any attention layer that computes $n$-bit XOR (parity) satisfies $D\times H\ge n$, so enlarging the value-vector dimension can never compensate for having too few heads or too low a polynomial readout degree.
  • The tradeoff is tight for every symmetric Boolean function: whenever its threshold degree $T$ admits positive integers $D,H$ with $D\times H\ge T$, an explicit $H$-head layer with value-vector dimension at most $\min\{D,\,O(\log H)\}$ computes it under a degree-$D$ polynomial threshold readout.
  • In the regimes where $D$ is a constant or at least a constant positive power of $H$, the constructions need only constant value-vector dimension; the paper leaves open whether intermediate $(D,H)$ pairs can beat $O(\min\{D,\log H\})$.
  • The min/max lower bound holds with no restrictions on query/key vectors or classifier weight magnitudes, and tolerates value-vector norms as large as $2^{d+p}$; only the dimension-precision product is what the geometry prohibits.

Reading between the lines

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

  • The affine-over-affine form of a softmax head probably does not depend on the exponential itself: any per-token positive score that is a fixed constant raised to a linear function of the features should keep the rational representation intact, so the $D\times H\ge T$ law may extend to other normalized linear-score attention variants.
  • The authors note that layer normalization and positional encodings break their rational representation; a concrete stress test is to train single-head transformers with layer normalization on parity for $n=3,\dots,8$ and ask whether any polynomial readout of degree below $n$ reaches perfect accuracy — the paper's machinery predicts it cannot in the plain-softmax regime, and a positive result would
  • Read together, the two theorems suggest that head count should be treated as an explicit parallel-computation budget in transformer-width studies, with an exchange rate against geometric resources (dimension-precision) for linear readouts and against algebraic resources (threshold degree) for polynomial readouts.
  • The gap between the two results — exponential for min/max, only linear for XOR — indicates distinct bottlenecks, and neither bound obviously dominates the other in practical architectures; combining both scenarios in one layer is a natural next target.
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

1 major / 2 minor

Summary. The paper studies the representational power of single-layer multi-head softmax attention for two multi-task computation scenarios. In the first scenario, a single attention head whose value vectors lie on a 2^{-p}-lattice of norm at most ℓ is post-processed by linear classifiers to compute both the minimum and maximum of n numbers from [M]. Theorem 1 gives the lower bound d(1+p+log_2 ℓ) ≥ min{⌊1+√(M−1)⌋, ⌊(n−1)/2⌋}, and Appendix A gives a matching two-head construction with d=O(log M) and p=0. The proof combines Erdős–Szekeres monotone-subsequence arguments with an approximate triangular-configuration volume bound (Lemma 6). In the second scenario, the paper considers an H-head attention layer post-processed by a degree-D polynomial threshold function computing a Boolean function of threshold degree T. Theorem 2 proves the lower bound D×H≥T, so n-bit XOR requires D×H≥n. Theorem 3 proves a matching upper bound for symmetric Boolean functions: whenever D×H≥T, H heads with value-vector dimension O(min{D,log H}) suffice, via rational-function representations of attention heads, polynomial factorization, and constructive additive bases. An appendix also gives a lower bound against Lipschitz post-processors.

Significance. If the results hold, they give clean and essentially tight tradeoffs between the number of attention heads, the post-processing polynomial degree, and the value-vector dimension. The lower bounds are unconditional with respect to query/key parameters and classifier weights, and the proof techniques are elegant: the triangular-configuration argument in Lemma 6 is a nice adaptation of barycentric-spanner volume arguments, and the use of additive bases to control value-vector dimension is a genuinely novel construction. The proofs are self-contained and checkable, with no fitted parameters or circularity; all upper bounds are explicit constructions, and all lower bounds rest on standard external results such as the threshold degree of parity. The paper also states its limitations clearly: Theorem 1 concerns linear post-processing, and the attention model is standard softmax without positional encodings or layer normalization. The core lower bounds in Theorems 1 and 2 appear sound, and the asymptotic form of the matching construction in Theorem 3 is supported by the supplied lemmas.

major comments (1)
  1. [§5.5, proof of Theorem 3] The proof's case split does not establish the claimed exact dimension bound d ≤ min{D, 2p+2}, where p = max{1, ⌈log_2 H⌉}. Case 1 handles D ≤ 2p−3 and gives d ≤ D via Lemma 12; Case 2 handles D ≥ 2p−2 and gives d ≤ 2p+2 via Lemmas 13 and 14. For 2p−2 ≤ D ≤ 2p+1, neither stated case yields the minimum. For example, with D=2 and H=4 (so p=2), Case 2 gives d ≤ 5, while the theorem claims d ≤ 2. The text notes that Lemma 12 is applicable for all D, so the missing step is to use Lemma 12 whenever D ≤ 2p+2 and to reserve Case 2 for D ≥ 2p+2. Please make this combination explicit; as written, the exact dimension bound in Theorem 3 is not proved, although the asymptotic O(min{D, log H}) bound and the lower bounds in Theorems 1 and 2 survive.
minor comments (2)
  1. [§5.4, Lemma 12] The construction is not defined when F has no real roots (T' = 0), because the partition of [T'] into d positive sets is empty. For constant-sign F, take d=1, P_1(t)=1, and g(z)=sign(c) (a homogeneous polynomial of degree 0, which is at most D), or alternatively g(z)=sign(c)z; please add this boundary case.
  2. [§5.5, proof of Theorem 3, Case 2] The equality b := ⌈H^{1/p}⌉ = 2 is not true for H=1, where b=1. This does not affect the final dimension bound because Lemma 12 already gives d ≤ D in that case, but the statement should be qualified by 'for H ≥ 2'.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: lower bounds derive from independent external results and upper bounds are explicit constructions.

full rationale

The paper's derivation chain is self-contained and does not reduce any claimed prediction to its own inputs. Theorem 1's lower bound uses the Erdős–Szekeres theorem as an external combinatorial fact plus a self-proved volume argument (Lemma 6) and self-proved classifier constraints (Lemmas 2–5); the matching two-head upper bound is an explicit Gilbert–Varshamov construction, not a fit. Theorem 2's lower bound is proved from scratch in Lemma 7 and Lemma 8: the rational-function representation of an H-head attention layer is derived from the definition of softmax attention, and the appeal to the threshold degree of parity is an external result (Minsky–Papert). Theorem 3's upper bounds are constructive: Lemma 12 uses polynomial factorization and Lemma 13 uses additive bases whose existence is proved in Lemma 14. No parameter is fitted to a subset of data and then renamed a prediction. The only self-citations (Sanford–Hsu–Telgarsky references in the related-work section) are contextual and not load-bearing for any theorem. The proof gap noted in the skeptical review concerns the case split in Theorem 3's dimension bound; that is a correctness/incompleteness issue, not circularity, because the claimed bound is not assumed and the missing argument would use a separate construction rather than an input. Accordingly, the circularity score is 0.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The paper's results rest on standard external theorems (Erdos-Szekeres, Minsky-Papert symmetrization, Gilbert-Varshamov, determinant inequalities) and on its own lemmas. There are no fitted constants, no new postulated entities, and no assumptions that include the target claims.

assumptions (5)
  • standard math Erdos-Szekeres theorem on monotone subsequences
    Used in Lemma 1 to obtain a monotone subsequence of attention weights of length N; if it failed, Theorem 1's lower bound would not follow.
  • standard math Minsky-Papert symmetrization of threshold degree
    Used in Theorem 3 and Corollary 1 to convert the threshold degree of symmetric Boolean functions to the minimum degree of a univariate polynomial F with sign(F(|x|)); this is the bridge from multivariate threshold degree to the univariate root-factorization construction.
  • standard math Known threshold degree n for n-bit XOR (parity)
    Used in Corollary 1 to turn the general DH≥T lower bound into DH≥n for parity; this numerical anchor is cited to Minsky and Papert.
  • standard math Gilbert-Varshamov existence of long binary error-correcting codes
    Used in Appendix A to construct the two-head min/max upper bound with d=ceil(8 ln M); standard coding-theory bound.
  • standard math Hadamard's inequality and integrality of det(A^T A) for integer matrices
    Used in Claims 1 and 2 inside Lemma 6's volume argument to bound the growth of approximately triangular vector configurations.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Attention-based representations for multi-task computation." pith.science (2026). https://pith.science/paper/BQXNM7WF

@misc{pith2026260804243,
  author       = {Pith},
  title        = {Pith review of: Attention-based representations for multi-task computation},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/BQXNM7WF}},
  note         = {Machine review of arXiv:2608.04243}
}
abstract

Multi-head attention layers produce vector representations that support multiple downstream tasks. We establish bounds on the number of heads required in two simple and concrete multi-task scenarios. In the first scenario, a vector representation is sought so that linear predictors can compute both the smallest and largest numbers in a given list. In this case, it is known two attention heads with small embedding dimension and bit precision level suffice. We prove that a single attention head requires exponentially higher embedding dimension or precision level. In the second scenario, a vector representation is sought so that a polynomial threshold function can compute the XOR of a given string of $n$ bits. This scenario is analogous to the first one for $n=2$, since XOR is readily computed by a linear function using a vector representation that encodes both the AND and the OR of the two bits. We observe that $n$-bit XOR requires the product of the number of heads and the polynomial degree to be at least $n$, and we construct multi-head attention layers that match this lower bound. These results generalize to arbitrary (symmetric) Boolean functions, where the bound is given in terms of the threshold degree.

Figures

Figures reproduced from arXiv: 2608.04243 by the authors.

Figure 1
Figure 1. The process analyzed in the proof of Lemma 6. [PITH_FULL_IMAGE:figures/full_fig_p011_1.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

36 extracted references · 20 canonical work pages

  1. [1]

    A capacity-based rationale for multi-head attention, 2026

    Micah Adler. A capacity-based rationale for multi-head attention, 2026. URL https://arxiv. org/abs/2509.22840

    work page arXiv 2026

  2. [2]

    Online linear optimization and adaptive routing

    Baruch Awerbuch and Robert Kleinberg. Online linear optimization and adaptive routing. Journal of Computer and System Sciences, 74(1):97–114, 2008

    work page 2008

  3. [3]

    Some extremal postage stamp bases.Journal of Integer Sequences, 13(2):3, 2010

    Michael F Challis and John P Robinson. Some extremal postage stamp bases.Journal of Integer Sequences, 13(2):3, 2010. 20

    work page 2010

  4. [4]

    Theoretical limitations of multi-layer transformer,

    Lijie Chen, Binghui Peng, and Hongxun Wu. Theoretical limitations of multi-layer transformer,

    work page

  5. [5]

    Tighter Bounds on the Expressivity of Transformer Encoders

    David Chiang, Peter Cholak, and Anand Pillay. Tighter bounds on the expressivity of transformer encoders, 2023. URLhttps://arxiv.org/abs/2301.10743

    work page Pith review arXiv 2023

  6. [6]

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

    Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: Pre-training of deep bidirectional transformers for language understanding, 2018. URL https://arxiv.org/ abs/1810.04805

    arXiv 2018

  7. [7]

    Du, Wei Hu, Sham M

    Simon S. Du, Wei Hu, Sham M. Kakade, Jason D. Lee, and Qi Lei. Few-shot learning via learning the representation, provably, 2020. URLhttps://arxiv.org/abs/2002.09434

    arXiv 2020

  8. [8]

    A combinatorial problem in geometry.Compositio Mathematica, 2:463–470, 1935

    Paul Erd˝ os and George Szekeres. A combinatorial problem in geometry.Compositio Mathematica, 2:463–470, 1935

    work page 1935

Show all 36 references
  1. [9]

    Theoretical limitations of self-attention in neural sequence models.Transactions of the Association for Computational Linguistics, 8:156–171, December 2020

    Michael Hahn. Theoretical limitations of self-attention in neural sequence models.Transactions of the Association for Computational Linguistics, 8:156–171, December 2020. ISSN 2307-387X. doi: 10.1162/tacl a 00306. URLhttp://dx.doi.org/10.1162/tacl_a_00306

    2020 doi

  2. [10]

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

    Yiding Hao, Dana Angluin, and Robert Frank. Formal language recognition by hard attention transformers: Perspectives from circuit complexity, 2022. URL https://arxiv.org/abs/2204. 06618

    2022

  3. [11]

    Are transformers with one layer self-attention using low-rank weight matrices universal approximators?, 2023

    Tokio Kajitsuka and Issei Sato. Are transformers with one layer self-attention using low-rank weight matrices universal approximators?, 2023. URLhttps://arxiv.org/abs/2307.14023

    2023 arXiv

  4. [12]

    Lower bounds on transformers with infinite precision, 2024

    Alexander Kozachinskiy. Lower bounds on transformers with infinite precision, 2024. URL https://arxiv.org/abs/2412.20195

    2024 arXiv

  5. [13]

    Parity, sensitivity, and transformers, 2026

    Alexander Kozachinskiy, Tomasz Steifer, and Przemys law Wa l¸ ega. Parity, sensitivity, and transformers, 2026. URLhttps://arxiv.org/abs/2602.05896

    2026 arXiv

  6. [14]

    A structured self-attentive sentence embedding, 2017

    Zhouhan Lin, Minwei Feng, Cicero Nogueira dos Santos, Mo Yu, Bing Xiang, Bowen Zhou, and Yoshua Bengio. A structured self-attentive sentence embedding, 2017. URL https: //arxiv.org/abs/1703.03130

    2017 arXiv

  7. [15]

    Ash, Surbhi Goel, Akshay Krishnamurthy, and Cyril Zhang

    Bingbin Liu, Jordan T. Ash, Surbhi Goel, Akshay Krishnamurthy, and Cyril Zhang. Trans- formers learn shortcuts to automata, 2022. URLhttps://arxiv.org/abs/2210.10749

    2022 arXiv

  8. [16]

    The parallelism tradeoff: Limitations of log-precision transformers, 2022

    William Merrill and Ashish Sabharwal. The parallelism tradeoff: Limitations of log-precision transformers, 2022. URLhttps://arxiv.org/abs/2207.00729

    2022 arXiv

  9. [17]

    A little depth goes a long way: The expressive power of log-depth transformers, 2025

    William Merrill and Ashish Sabharwal. A little depth goes a long way: The expressive power of log-depth transformers, 2025. URLhttps://arxiv.org/abs/2503.03961

    2025

  10. [18]

    MIT Press, 1969

    Marvin Minsky and Seymour Papert.Perceptrons: An introduction to computational geometry. MIT Press, 1969

    1969

  11. [19]

    On extremalh-basesA 4.Mathematica Scandinavica, pages 5–16, 1987

    Svein Mossige. On extremalh-basesA 4.Mathematica Scandinavica, pages 5–16, 1987. 21

    1987

  12. [20]

    Parikh, Oscar T¨ ackstr¨ om, Dipanjan Das, and Jakob Uszkoreit

    Ankur P. Parikh, Oscar T¨ ackstr¨ om, Dipanjan Das, and Jakob Uszkoreit. A decomposable attention model for natural language inference, 2016. URL https://arxiv.org/abs/1606. 01933

    2016

  13. [21]

    On limitations of the transformer architecture, 2024

    Binghui Peng, Srini Narayanan, and Christos Papadimitriou. On limitations of the transformer architecture, 2024. URLhttps://arxiv.org/abs/2402.08164

    2024 arXiv

  14. [22]

    Representational strengths and limitations of transformers, 2023

    Clayton Sanford, Daniel Hsu, and Matus Telgarsky. Representational strengths and limitations of transformers, 2023. URLhttps://arxiv.org/abs/2306.02896

    2023 arXiv

  15. [23]

    One-layer transformers fail to solve the induction heads task, 2024

    Clayton Sanford, Daniel Hsu, and Matus Telgarsky. One-layer transformers fail to solve the induction heads task, 2024. URLhttps://arxiv.org/abs/2408.14332

    2024 arXiv

  16. [24]

    Transformers, parallel computation, and logarithmic depth, 2024

    Clayton Sanford, Daniel Hsu, and Matus Telgarsky. Transformers, parallel computation, and logarithmic depth, 2024. URLhttps://arxiv.org/abs/2402.09268

    2024 arXiv

  17. [25]

    Michael Steele

    J. Michael Steele. Variations on the monotone subsequence theme of Erd¨ os and Szekeres. In David Aldous, Persi Diaconis, Joel Spencer, and J. Michael Steele, editors,Discrete Probability and Algorithms, pages 111–131, New York, NY, 1995. Springer New York

    1995

  18. [26]

    Two (narrow) heads are better than (an arbitrarily wide) one

    Amanuel Tesfaye, Zeno Kujawa, Rajmohan Rajaraman, and Ravi Sundaram. Two (narrow) heads are better than (an arbitrarily wide) one. InThe Fourteenth International Conference on Learning Representations, 2026. URLhttps://openreview.net/forum?id=RRmPbbZsvl

    2026

  19. [27]

    Nilesh Tripuraneni, Chi Jin, and Michael I. Jordan. Provable meta-learning of linear represen- tations, 2020. URLhttps://arxiv.org/abs/2002.11684

    2020 arXiv

  20. [28]

    Gomez, Lukasz Kaiser, and Illia Polosukhin

    Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need, 2017. URL https://arxiv. org/abs/1706.03762

    2017 arXiv

  21. [29]

    How many attention heads do you need to do XOR? Less- Wrong, April 2026

    Karthik Viswanathan. How many attention heads do you need to do XOR? Less- Wrong, April 2026. URL https://www.lesswrong.com/posts/T66BKwSufh5SfiPHm/ how-many-attention-heads-do-you-need-to-do-xor-3

    2026

  22. [30]

    The effect of attention head count on transformer approximation, 2025

    Penghao Yu, Haotian Jiang, Zeyu Bao, Ruoxi Yu, and Qianxiao Li. The effect of attention head count on transformer approximation, 2025. URL https://arxiv.org/abs/2510.06662

    2025

  23. [31]

    On model selection consistency of Lasso.Journal of Machine Learning Research, 7(90):2541–2563, 2006

    Peng Zhao and Bin Yu. On model selection consistency of Lasso.Journal of Machine Learning Research, 7(90):2541–2563, 2006. URLhttp://jmlr.org/papers/v7/zhao06a.html. 22 A Attention-based minimum computation In this appendix, we describe an attention head and linear classifier ...

    2006

  24. [33]

    The minimum isx, so MX i=1 hi∆x,y i >0

    Supposeh x =nandh i = 0 for alli̸=x. The minimum isx, so MX i=1 hi∆x,y i >0. 23 Moreover, MX i=1 hi∆x,y i =h x∆x,y x =n∆ x,y x . Hence ∆x,y x >0. This proves the first part of the claim

  25. [34]

    The minimum isy, so MX i=1 hi∆x,y i <0

    Supposeh y =nandh i = 0 for alli̸=y. The minimum isy, so MX i=1 hi∆x,y i <0. Moreover, MX i=1 hi∆x,y i =h y∆x,y y =n∆ x,y y . Hence ∆x,y y <0.(19)

  26. [35]

    The minimum is x, so MX i=1 hi∆x,y i >0

    Suppose hx = 1 and hz = n− 1 for some z≥y , and hi = 0 for all i /∈ {x, z}. The minimum is x, so MX i=1 hi∆x,y i >0. Moreover, MX i=1 hi∆x,y i =h x∆x,y x +h z∆x,y z = ∆x,y x + (n−1)∆ x,y z . Hence ∆x,y z >− 1 n−1 ∆x,y x ,(20) and, in particular, forz=y, |∆x,y y |=−∆ x,y y < 1 ...

  27. [36]

    The minimum is y, so MX i=1 hi∆x,y i <0

    Suppose hy = 1 and hz = n− 1 for some z > y, and hi = 0 for all i /∈ {y, z}. The minimum is y, so MX i=1 hi∆x,y i <0. Moreover, MX i=1 hi∆x,y i =h y∆x,y y +h z∆x,y z = ∆x,y y + (n−1)∆ x,y z . 24 Hence ∆x,y z <− 1 n−1 ∆x,y y = 1 n−1 |∆x,y y |. Combining with (21), we have ∆x,y ...

  28. [2024]

    URLhttps://arxiv.org/abs/2412.02975

    arXiv

Pith tools

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