Binary Hypothesis Testing for Softmax Models and Leverage Score Models
Authors: Yuzhou Gu
Zhao Song
Junze Yin
Venue: ICML 2025 poster (2025)
Keywords: Binary hypothesis testing
softmax distributions
large language models
attention
Primary area: deep_learning->large_language_models
TL;DR: We analyze the binary hypothesis testing problem for softmax and leverage score models, which are relevant to large language models and attention mechanisms.

Abstract: Softmax distributions are widely used in machine learning, including Large Language Models (LLMs), where the attention unit uses softmax distributions. We abstract the attention unit as the softmax model, where given a vector input, the model produces an output drawn from the softmax distribution (which depends on the vector input). We consider the fundamental problem of binary hypothesis testing in the setting of softmax models. That is, given an unknown softmax model, which is known to be one of the two given softmax models, how many queries are needed to determine which one is the truth? We show that the sample complexity is asymptotically $O(\epsilon^{-2})$ where $\epsilon$ is a certain distance between the parameters of the models.  Furthermore, we draw an analogy between the softmax model and the leverage score model, an important tool for algorithm design in linear algebra and graph theory. The leverage score model, on a high level, is a model which, given a vector input, produces an output drawn from a distribution dependent on the input. We obtain similar results for the binary hypothesis testing problem for leverage score models.

Binary Hypothesis Testing for Softmax Models and Leverage Score Models
Yuzhou Gu Zhao Song?
Junze Yin
Abstract
et al., 2024a). These models, together with those built upon them, have demonstrated significant prowess actoss diverse fields. The robustness and vitality of their development are attested to by the widespread integration of LLMs. In the realm of Natural I. Language Processing (NLP), evaluations by (Liang et al., 2023; Laskar et al., 2023; Choi et al., 2023; Bang et al., 2023) center around natural language under- standing, while (Wang et al.. 2023: Qin et al., 2023a; Pu & Demberg, 2023; Chia al., 2023; Chen et al., 2023b) delve into natural language generation. LLMs have found upplications in diverse fields, including both social science and science (Guo et al., 2023; Deroy et al., 2023; Ferrara, 2023; Nay et al., 2023), medical applications (Chervenak et al., 2023; Johnson et al., 2023), cybersecurity (Sun et al., 2023: Xu et al., 2024; Li et al., 2025b; Huang al., 2025; Das et al., 2025) and engineering (Pallagani et al., 2023; Sridhara et al., 2023; Bubeck et al., 2023; Liu et al., 2023a), showcasing their potent capabilities. A consistent theme among these models is the adoption of the transformer ar- chitecture, a proven and highly efficient framework. The prevailing prevalence of models like ChatGPT (OpenAI, 2023) further underscores the transformative impact of this architecture.
Softmax distributions are widely used in ma- chine learning, including Large Language Models (LLMs), where the attention unit uses softmax distributions. We abstract the attention unit as the softmax model, where given a vector input, the model produces an output drawn from the soft- max distribution (which depends on the vector input). We consider the fundamental problem of binary hypothesis testing in the setting of soft- max models. That is, given an unknown softmax model, which is known to be one of the two given softmax models, how many queries are needed to determine which one the truth? We show that the sample complexity is asymptotically O(e where is certain distance between the param- eters of the models. Furthermore, we draw an analogy between the softmax model and the lever- age score model, an important tool for algorithm design in linear algebra and graph theory. The leverage score model, on high level, a model which, given vector input, produces an output drawn from distribution dependent the input. We obtain similar results for the binary hypothesis testing problem for leverage score models.
However, there is crucial problem with LLMs: their train- ing costs and uncertainty regarding their inference ability in different parts of the whole. Understanding how different domains work is important in retrieval argument generation (RAG) (Siriwardhana al., 2023; Zamani & Bendersky, 2024; Salemi & Zamani, 2024), well as sparsity for LLMs by identifying the ability domain in the model which is im- portant in solving the problem above. Then question arose:
1. Introduction
In transforming various aspects of people's 's lives, large lan- guage models (LLMs) have exhibited tremendous potential. In recent years, numerous content learning and LLMs have been developed, including notable models such as Adobe Firefly, Microsoft 365 Copilot (Spataro, 2023), Adobe Pho- toshop, and Google's Meena chatbot (Rathee, 2020), along with the GPT series, the DeepSeek series, Google's Gemini series and others (Radford al., 2018; 2019; Devlin al., 2019; Radford et al., 2019; Yang et al., 2019; Brown al., 2020; ChatGPT, 2022; OpenAl, 2023; Team, 2023; Liu
Can we distinguish different ability parts of large language models by limited parameters sampling?
We take an initial step toward addressing this question from a theoretical perspective. As we delve deeper into LLMs, the softmax mechanism is found play an important role in the computation of self-attention. Thus, it is imperative to study how the self-attention mechanism works, why it contributes significantly to the impressive capabilities of LLMs, and what role it plays are still not fully understood.
'Institute for Advanced Study University of California Berkeley 'Boston University. Correspondence to: Zhao Song <magic.linuxkde@ gmail.com>.
Proceedings of the 4nnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
Therefore, in this work, we want to explore the mechanism of softmax distribution from a binary hypothesis testing

---

Binary Hypothesis Testing for Softmax Models and Leverage Score Models
perspective. By delving into the intricacies of the softmax formulation, we explore which parameters are important by explaining how the softmax can be distinguished from each other. By delving into this idea, we can determine how many parameters are important in the inference of trans- formers (Vaswani et al., 2017). In continuation of the paper and drawing upon a formulation similar to softmax, we also direct our attention to the distribution of leverage scores. Much like softmax, the leverage score is a distribution pa- rameterized by matrix. Both softmax and leverage score can be treated as functions of distribution within this context. Importantly, resembling softmax, leverage score assumes significance across various fields. Leverage scores have demonstrated their significant utility in both linear algebra and graph theory. In the field of graph theory, researchers have extensively explored the application of leverage scores in various areas such the generation of random span- ning trees (Schild, 2018), max-flow problems (Daitch & Spielman, 2008; Madry, 2013; 2016; Liu & Sidford, 2020),
and denoted Leverage Given input & E (0))) the model returns an element i E [n] with probability A.)-+
where A, S A, and
pi S = Diag(s) is the diagonal matrix with diagonal s. We define the binary hypothesis testing problem for leverage score models similarly to the softmax case.
1.1. Main Result.
We state informal versions of our main results.
Theorem 1.1 (Informal statement of Theorem 3.2 and The-
orem 3.5). Consider the binary hypothesis testing problem with two softmax models Sof tMax a and Sof tMax We have 1). | Al2-- S c, then any successful algorithm uses Qi ((())) queries (Lower bound), and 2). if = A+ for some small e then the hypothesis testing problem can be solved in O(E-2v) queries, where v depends on A and M (Upper bound).
Theorem 1.2 (Informal statement of Theorem 4.2 and Theorem 4.3). Consider the binary hypothesis testing problem with two leverage score models Leverage A and Leverageg. We have 1). if Eigjm) IIBT,. Br., AT S then any successful algorithm uses !)(= queries (Lower bound), and 2). if B = A + cM for some small then the hypothesis testing problem can be solved in (( 2v) queries, where v depends on A and M (Upper bound).
maximum matching (Brand et al., 2020a; Liu et al., 2020b),
and graph sparsification (Spielman & Srivastava, 2008a).
Many studies have delved into the deep exploration of lever- age scores, showcasing their effectiveness in optimization tasks such linear programming (Lee & Sidford, 2014; Cohen et al., 2019h; Song, 2019; Lee et al., 2019; Brand et al., 2020b; Song& & Yu, 2021; Liu et al., 2023c; Song et al., 2024b; Qin et al., 2023b; Gu et al., 2025), cutting- plane methods (Vaidya, 1989 Lee et al., 2015; Jiang et al., 2020b), semi-definite programming (Jiang et al., 2020a; Huang et al., 2022; Chen et al., 2023a: Gu et al.. 2024), and the approximation of the John Ellipsoid (Cohen al., 2019a; Song et al., 2022; Li et al., 2024a;b). These applications underscore the importance of leverage scores in the context of theory of computer science and linear algebra. Based on the analysis provided, both the leverage score and softmax computation are parameterized by single matrix. Given the significance of the application of softmax and computation, understanding the influence on parameter behavior becomes crucial. Hence, we delve into this inquiry by differentiating the model through parameter sampling and discussing how the number of samples affects the distinguishing ability.
1.2. Related Work
Theoretical LLMs Several investigations (Cai et al.,
2021; Liu et al., 2024c; Reif et al., 2019; Hewitt & Manning,
2019) have concentrated on theoretical analyses concerning LLMs. The algorithm presented by (Cai et al., 2021), named ZO-BCD, introduces novel approach characterized by ad- vantageous overall query complexity and reduced computa- tional complexity in each iteration. The work by (Liu et al., 2024c) introduces Sophia, a straightforward yet scalable second-order optimizer. Sophia demonstrates adaptability to curvature variations across different parameter regions, feature particularly advantageous for language modeling tasks with strong heterogeneity. Importantly, the runtime bounds of Sophia are independent of the condition number of the loss function.
A softmax model is parameterized by a matrix A E Radd, and denoted SoftMaxA. Given x E IRd, the model outputs an element i E [n] with probability p; (exp(Az), 1,,) -¹ exp(Ar);- In the binary hypothesis test- ing problem, we are given access to a softmax model which is either Sofx or SoftMaxp: We have query access to the model, that is, we can feed the model an input x E Rdd, and it will produce an output. The goal is to determine whether the model is SoftMax, tMax,1 or Sof tMax using the fewest number of queries possible. We can similarly de- fine the question for leverage score models. A leverage score model is parameterized by matrix A E gaad
Studies by (Wang et al., 2022; Li & Liang, 2021; Dai et al., 2022; Burns et al., 2023; Hase et al., 2023; Xie et al., 2022) investigate the knowledge and skills of LLMs. In the realm of optimization for LLMs, (Kaplan et al., 2020; Rafailov et al., 2023; Liu et al., 2024c; Cao et al., 2024) have delved into this domain. Demonstrating the effectiveness of pre- trained models in localizing knowledge within their feed- forward layers, both (Hase et al., 2023) and (Meng et al., 2022) contribute valuable insights to the field. The explo- ration of distinct "skill" neurons and their significance in
2

---

Binary Hypothesis Testing for Softmax Models and Leverage Score Models
soft prompt-tuning for language models is a central theme in the analysis conducted by (Wang et al., 2022), building upon the groundwork laid out in a prior discussion by (Li & Liang, 2021). The activation of skill neurons and their corre- lation with the expression of relevant facts is a focal point in the research presented by (Dai et al., 2022), particularly in the context of BERT. In contrast, the work of (Burns et al., 2023) takes an entirely unsupervised approach, leveraging the internal activations of a language model to extract latent knowledge, Next, the investigation by (Li et al., 2023) sheds light on the sparsity observed in feedforward activations of large trained transformers, uncovering noteworthy patterns in their behavior. In addition to the above, (Cai et al., 2021; Malladi et al., 2023; Deng et al., 2024; Zelikman et al., 2023) explore zeroth order algorithms for LLMs, and (Hu al., 2022: 2024c; Cao, 2024) explore parameter-efficient fine-tuning of LLMs.
leverage scores. In optimization, areas such as linear pro- gramming (Lee & Sidford, 2014; Brand et al., 2020b), the approximation of the John Ellipsoid (Cohen et al., 2019a), cutting-plane methods (Vaidya, 1989; Lee et al., 2015; Jiang et al., 2020b), and semi-definite programming (Jiang et al., 2020a) incorporate leverage scores. Within graph theory applications, leverage scores play a crucial role in max-flow problems (Daitch & Spielman, 2008; Madry, 2013; 201 6; Liu & Sidford, 2020), maximum matching (Brand et al., 2020a; Liu et al., 2020b), graph sparsification (Spielman & Srivastava, 2008a), and the generation of random span- ning trees (Schild, 2018). Several studies, such as (Spiel- man & Srivastava, 2008b; Drineas et al., 2012: Clarkson & Woodruff, 2013), focus on the approximation of leverage scores. Simultancously, Lewis weights, serving as a gener- alization of leverage scores, are explored in depth by (Bour- gain et al., 1989; Cohen & Peng, 2015). Notably, leverage scores may also motivate efficient computational methods in machine learning, including regression problems (Price et al., 2017; Song et al., 2019a; Gilyén et al., 2022: Song et al., 2023; Song. 2019), deep neural networks (Lee et al., 2020; Zandieh et al., 2021), graph neural networks (Shin et al., 2023; Zhang, 2024), recommender systems (Huang et al., 2023; Zhang et al., 2024), active learning (Shimizu et al., 2024; Gajjar et al., 2024), discrepancy minimiza- tion (Deng et al., 2025) and Fourier transform (Li et al., 2025c).
Several recent works have revealed the inherent limitations of LLMs from a theoretical perspective. These limitations are grounded in empirical benchmarks indicating that LLMs may face difficulties in simple tasks (Zhou et al., 2023; Guo et al., 2025a; Cao et al., 2025b; Guo al., 2025b). An important line of research (Alman & Song, 2023; 2024a;b; 2025a;b) has theoretically shown that the forward and back- ward passes of Transformers cannot be approximated with low error in truly subquadratic time, unless the attention weights are sufficiently small in each entry. Beyond the sig- nificant success of circuit complexity in showing that many neural architectures (Ke et al., 2025; Chen et al., 2025b; Li et al., 2025a) may belong to weak class of logical circuits, such as TC", and may fail to solve harder problems, these results have effectively explained LLMs' limitations (Wei et al., 2022: Li et al., 2024c; Chen et al., 2024). For exam- ple, they show that Transformers cannot solve arithmetic formula evaluation and that COT may enhance LLMs' circuit complexity bounds. Recent works have also gone beyond numerical approximation and model expressiveness, finding that under gradient descent training, certain types of simple Boolean function problems may be difficult for LLMs to learn, such as the parity problem (Kim & Suzuki, 2025), the majority problem (Chen et al., 2025a), and simpler and/or problems (Hu et al., 2025).
Hypothesis Testing Hypothesis testing is a central prob- lem in statistics, and has many applications in machine learning in recent years (Liu et al., 2020a; Gao et al., 2021; Liu et al., 2021a; Xu et al., 2022; Song et al., 2025). In hypothesis testing, two (or more) hypotheses about the truth are given and an algorithm needs to distinguish which hy- pothesis is true. The most classic testing problem is the binary hypothesis testing. In this problem, two distributions Po and P1 are given, and there is an unknown distribution P which is either Po or P.. The goal is to distinguish whether P = Po or P = P1 by drawing samples from P. This problem is well-studied, with (Neyman & Pearson, 1933) giving tight characterization of the possible error regions in terms of the likelihood ratio. It is known that the asymptotic sample complexity of binary hypothesis testing for distri- butions is given by O(H [Po. Pt)), where H denotes the Hellinger distance, see e.g., (Polyanskiy & Wu, 2023+). There are other important kinds of hypothesis testing prob- lems. In the goodness-of- testing problem, a distribution Q is given, and there is an unknown distribution P which is known to be either equal to Q far away from Q. The goal is to distinguish which is the true by drawing samples from P. In the two-sample testing problem, two unknown distributions P and Q are given, and is known that either P = Q or P and Q are far away from each other. The goal is to distinguish which is true by drawing samples from
Leverage Scores Given A E Raxd and E [n]. az represents the i-th row of matrix A. We use oz = a. (AA A)ta, to denote the leverage score for the i-th row of matrix A. The concept of leverage score finds extensive applications in the domains of machine learning and linear algebra. In numerical linear algebra and graph theory, lever- age scores serve as fundamental tools. In the context of matrices, both the tensor CURT decomposition (Song et al., 2019b) and the matrix CUR decomposition (Boutsidis & Woodruff, 2014; Song et al., 2017; 2019b) heavily rely on
3

---

Binary Hypothesis Testing for Softmax Models and Leverage Score Models
and Q. For these problems there are simple general char- acterization as in the binary hypothesis testing. However, for reasonable classes of distributions such as Gaussian dis- tributions or distributions on discrete spaces, a lot of nice results are known (Ingster, 1987; 1982; Goldreich & Ron, 2011; Valiant & Valiant, 2017; Chan et al., 2014; Arias- Castro et al., 2018; Li Yuan, 2019). We are not aware of any previous work that studies hypothesis testing problems for the class of softmax models or leverage score models.
In particular, if P and Q are the discrete space [n] and P (Pi, (u......PP). Q (91.-..: ... then
TV(P, Q)) = 2 P: qol.
Definition 2.2 (Hellinger distance). For two distributions P. the same measurable space, their squared Hellinger distance is
(P(P - 1 / / P(dz)))) - ((Vp()))xQ((aaa v((r))²
Roadmap. In Section 2, we introduce notation and con- cepts related to information theory and hypothesis testing. Our results are presented Section 3 and Section 4: Sec- tion 3 establishes upper and lower bounds on the sample complexity for distinguishing two different softmax models, and Section 4 delves into the case of leverage scores. We present several additional remarks for our main results in Section 5. We conclude and make further discussions in Section 6.
In particular, if P and Q are the discrete space [n| and P (pI,..., .Pn), Q (q....., .n). then
n
H² Q) 2 Σ (Vp. /
=1
Piqp-
2. Preliminaries
The Hellinger distance H(P, Q) is the square root of the squared Hellinger distance H² (P,, Q).
In Section 2.1, we define several basic notations. In Sec- tion 2.2, we provide definitions related to information theory. In Section 2.3, we provide backgrounds about hypothesis testing. In Section 2.4, we provide definition of softmax model. In Section 2.5, we provide definition of leverage score model.
We recall the following relationship between the Hellinger distance and the TV distance. For any distributions P, Q on the same space, we have
(P, S TV(P,Q) S (2H(P.Q).
Definition 2.3 (Expectation and variance). Let P be dis- tribution measurable space X' and f be continuous function on X. Then [f] is the expectation of under P and Varp (f) f) is the variance of f under P. In particular, if X' = [n]. P= (pi,...,,,.. .o.) E RP, and x E IR", then
2.1. Notation
Given x E R we use |.>||p p to denote bp norm of x,
where ||0|||o Σd n ((x; * 0), ||>||| = Σ²= [ (&) norm), | == (E xx) 1/2 (l2 norm), and ||0|| max4e(x) |z,| (foo norm). For square matrix, tr tr[A] is used to represent the trace of A. Given 1 S p S oo represents the p-to-q oper-
E Σ pid and Varr(x) Σ pr(x -E-BB B
and 1 < < x., ||Al|-= ator norm ||Al|| = =1l,:
||A In particu- lar, ||Al|2-000 = maxie[m] 112 For x E R", let Diag(z) R"x= denote the diagonal matrix with diagonal For square matrix A Raxn, let diag(A) IR" denote the diagonal of A. For non-negative integer n, let [n] denote the set {1....,n} n). For sequence x,....,Xe X,m of random variables, we use X to denote the whole sequence "X.
2.3. Hypothesis Testing
We review the classic hypothesis testing problem for distri- butions.
Definition 2.4 (Binary hypothesis testing for distributions). Let Po, P1 be two distributions on the same space. We have sample access to a distribution P, which is known to be either Po P1. The goal is to determine whether p= Po P Pi, using few samples possible. We say an algorithm successfully distinguishes Po and P1 is at least 2/3 under both hypotheses.
2.2. Information Theory
Definition 2.1 (TV distance). For two distributions P, Q on the same measurable space, their total variation (TV) distance is
In the above definition, the constant 2/3 can be replaced by any constant > 1/2, and the asymptotic sample complexity of the binary hypothesis testing problem does not change. The reason is that if we have an algorithm that achieves
TV(P,Q) = 2 / P((dx) / Q(dx))

---

Binary Hypothesis Testing for Softmax Models and Leverage Score Models
success probability 8 > 2.2 then we can run it independently constant number of times and take the majority of the outputs. Thus, we can boost the success probability to an ar- bitrarily high constant. A classic result in information theory states that the sample complexity of the binary hypothesis testing problem is determined by the Hellinger distance.
2.5. Leverage Score Model
Definition 2.9 (Leverage score model). The leverage score model Leverage A associated with A E Rnxd is model such that on imput E (R)())), , it outputs sample y [n] from the distribution Leverage a (s), defined as follows: the probability mass of i E [<] is equal to
Lemma 2.5 (c.g.. (Polyanskiy & Wu, 2023+)). The sam- ple complexity of the binary hypothesis testing problem for distributions is @(H-2 Pi)). That is, there is an algorithm that solves the problem using ( Pi))
[I( A.)) A.)- B// (A.(AA A.) (1s//dd
where A, S-1A, and S = Diag(s).
queries, and any algorithm that solves the problem uses Q( (Po. queries.
Definition 2.10 (Binary hypothesis testing for leverage score model). Let A, B E Rnaxd be two matrices. Let Po Leverage Pi = Leverageg be two leverage score models. Let P be the leverage score model which is either Po or P1. In each query. we can feed 8 E (RR(())) )" into P. and retrieve a sample y E [ni] from P(s). The goal is to determine whether the model P is Po or Pi in as few samples as possible. We say an algorithm successfully dis- tinguishes Po and PL, if the correctness probability is least 2/3 under both hypotheses.
2.4. Softmmx Model
Definition 2.6 (Softmax model). The softmax model SoftMax, associated with A E Raxd a model such that on input x E IRd, outputs sample y E [m] from the dis- tribution SoftMaxA (z), defined as follows: the probability mass of i [n] is equal to (cxp(Az), 1n)-1 bx)===ex((a)) cxp(Ax);
Note that Ei (exp(AA) Ax), 1,,) exp(Ax); = 1, so the above definition gives a valid distribution.
Similar to the softmax model case, if we do not put any restrictions on then there will be certain weird behavior.
Definition 2.7 (Binary hypothesis testing for softmax mod- els). Let A, B E Raxd be two matrices. Let Po SoftMaxA. Pi = SoftMaxg be two softmax models. Let P be the softmax model which is either Po or PI. In each query, we can feed æ E Rd into P, and retrieve a sample y E [n] from P(x). The goal is to determine if the model P is Po or Pi in as few samples as possible. We say an algorithm successfully distinguishes Po and P1, if the cor- rectness probability at least 2/3 under both hypotheses.
For example, if we take 2. d 1, A
and 0
B for some small e > O. Because A and B are [c]
close to each other, we should expect it to be difficult to distinguish Leverage A and Leverage However, if we allow any 8 E (R) as input, then we can take 8 = [1 8) for some very small ô > O. In this way, we can verify that Leverage (s) has all mass on 1 E [n], while Leverage (s) has almost all mass on 2 [xi] So we can distinguish the two models using only one query. To avoid such cases we put additional constraints on
The above definition is valid. However, if we make no restrictions on the input v, then there would be undesirable consequences. For example, suppose n = 2, d = 1, A
[c] 00
Definition 2.11 1 (Constraint for leverage score model). We assume that input E (R){())² should satisfy the con- straint such that c S s I C for some given constants 0 <<c<C.
B for some very small e 0. Because A and
0
6
B are close to each other, we should expect it to be difficult to distinguish SoftMaxA and SoftMaxn. However, if we allow any x E Rdd as input, then we could take x to be a very large real number. Then SoftMax, A (x)) has almost all mass on 1 E [n]], while SoftMax (æ) has almost all mass on (n). and we can distinguish the two models using only one query. To avoid this peculiarity, we assume that there is an energy constraint on x.
3. Softmax Model
In Section 3.1. we state our general result of softmax model. In Section 3.2, we provide show how to prove the lower bound. In Section 3.3, we explain how to prove the upper bound.
Definition 2.8 (Energy constraint for softmax model). We assume that there is an energy constraint, that is, input e R should satisfy ||æ:|| I E, for some given constant E.
3.1. General Result
We first prove a general result that relates the binary hypoth- esis testing problem with Hellinger distance, and the proof is deferred to Appendix A.
The energy constraint is a reasonable assumption in the con- text of LLMs and more generally neural networks, because of the widely used batch normalization technique (Ioffe & Szegedy, 2015).
Theorem 3.1. Let A, E Raxd be two matrices. Con- sider the binary hypothesis testing problem of distinguish-
5

---

Binary Hypothesis Testing for Softmax Models and Leverage Score Models
ing SoftMaxA and SoftMaxg using energy-constrrained queries (Definition 2.8). Define
Now, we're ready finish the proof of Theorem 3.2.
Proof of Theorem 3.2. By Corollary 3,4, we have HS (1)
8 sup x: =
(I),
O for any | S E. Therefore å in the statement of Theorem 3.1 satisfies 8 = E() Applying Theorem 3.1 we finish the proof.
Then the sample complexity of the binary hypothesis test- ing problem is ((5-2). That is, there is an algorithm that successfully solves the problem using 2) energy- constrained queries, and any algorithm that successfully solves the problem uses 32(8-2) meeryy-oosstranee queries.
3.3. Upper Bound
In the previous section, we established an (?(= lower bound for solving the hypothesis testing problem for the softmax model. The upper bound is more subtle. Let us discuss a few difficulties in establishing the upper bound. Let A, B E Raxd be parameters of the softmax models, F be the input vector, P = SoftMax (2) (PI..... .P.)
3.2. Lower Bound
Now, we prove the following lower bound for binary hy- pothesis testing for softmax models.
Theorem 3.2 (Lower bound). If two softmax models (Def- inition 2.6) with parameters E Truxd and B E Raxd satisfy
Q (oftMax = (41 (qI..... 4n). First, two different matrices A and B could give rise to the same softmax model. If B = A + 1 w for some E Rdd, then for any x E Rd we have
||A B112-000 Se,
exp(Br), q (exp(Brr 1n))
which is
max jE(m]
||
Bz,all2 Se
exp( (Ax)s exp(w ( Tx) (exp(Ax) cxp(e)x (w x,, 1n) exp(Az)) (exp(Ax), 1m) Pt
then any algorithm with energy constraint F. that distin- guishes the two models with success probability 2 uses at least Q(c==2 samples.
Before giving the proof of Theorem 3.2, we state a lemma, and the proof deferred to Appendix A.2.
for all i E [d]. Therefore in this case a SoftMaxp(x) for all E Rd and it is impossible to dis- tinguish the two models. This issue may be resolved by adding additional assumptions such as 1 = 1,, B. A more important issue is that A and B may differ only in rows with very small probability weight under any input x. For example, suppose A is the zero matrix, and B differ with A only in the first row. For any x E Rd. the distri- bution Sof MoftMax (2)) is the uniform distribution on [d]. If ||a||2 < E,
Lemma 3.3. Let a, b E R" be such that ||a - 6oo0 S
Let P be the distribution on [m] with Pt exp(a))/\exp(a), 1n). Let Q be the distribution on [n]] with 2: exp(b:)/ (exp()) In). Then
=(P.)))=((E) IV(P.Q)=0(6)
Next, we prove an application of Lemma 3.3.
|1,, A1, e, then for any x with have
Corollary 3.4. If matrices A E Rn B E Baxd satisfy maXje(n] |A B 12 S e, for any E RR, the distributions = SoftMax (x) and Q = (oft satisfy
I cxp(Br), Bx))
exp(Ar) exp(eE).
(P..Q)
A simple calculation shows that in this case.
(((P)))=((2)))))))
Proof. For any x R,, we have
So the sample complexity of any hypothesis testing algo- rithm is at least ((n/(c2E3)) (?))), which grows with n. This shows that the sample complexity may depend on n. Never- theless, using Theorem 3.1, we show a local upper bound, which says that for fixed A and fixed direction M, there is an algorithm that distinguishes SoftMax, and Sof A+eM using ( queries, for small enough >
||Ax Bi|loc=
max
AA, BR,rrl
]E(n]
< max
Aj,. |aal1111
sc(m]
2 <||
The result then follows from Lemma 3.3.
6

---

Binary Hypothesis Testing for Softmax Models and Leverage Score Models
Theorem 3.5. Fix A, M,Me Ruxd where |Mlla-se = 0(1) For > O, define B. = A + eM. We consider the binary hypothesis lesting problem with SoftMax and BoftMax for small e. Let V supr:|||=]a VaTsottNax (ar) (Mx). Then > 0 small enough, there is an algorithm that uses O(E ((E-2v~1) energy-constrained queries and distinguishes between A and Sof n.
4.2. Lower Bound
The goal of this section is to prove the following lower bound for binary hypothesis testing for leverage score mod- cls.
Theorem 4.2. Consider two leverage score model L and Leverage g. Assume that there exists 8 > such that A TA= 81. If
Proof of Theorem 3.5 is deferred to Appendix A.3. From Theorem 3.5 we see that it is an interesting problem to bound = suP::||=||=< a (Mx) for fixed A, M e Raxd For different A and M the value of y can be quite different. For example, if A is the all zero matrix and M zero except for row (and || = O()), then 0(E2/n) for any ||>|||2 S E. On the other hand, if A the zero matrix, and the first column M are i.i.d. Gaussian (EE²) for
Σ 8Ein]
- Sc
(where I| llop denotes the 2-to-2 operator norm), then any algorithu that solves the binary hypothesis testing problem takes at least (2c5/ (Ce) constrained queries.
Proof. Let
NO, (())), then with high probability, (F, ,,, We remark that Theorem 3.5 is in fact tight. We have a matching lower bound.
0).
P= L=Leverage_lo = -Pp.....PPN)
and
Theorem 3.6. Under the same setting as Theorem 3.5 and let be defined as Theorem 3.5, for sufficient small e > O. any algorithm that distinguishes between Sof A and SoftMax,, must use ((()) energy-constrained queries.
Q = (everagee(s) (q))....9))
By Theorem 4.1, it suffices prove that H² Q) ((eC/(c5)) We first consider the case where A and B differ in exactly one row i. Fix s E Rd with c S s S C
for all j E [n]]. Let A, = S-1 A and B, = S B, where
Proof. It follows from combining the proof of Theorem 3.5 and Theorem 3.1.
S = Diag( (s).
G
Because A A 2 81, we have
4. Leverage Score Model
A, A, 2 (6/C) -1
In Section 4.1, we state our general result of softmax model.
Because |BBT, B AT, Ai. llop S c, we have
In Section 4.2, we provide show how to prove the lower bound. In Section 4.3, we explain how prove the upper bound.
-e,C/AA A. 3 B,, AT, 1 ec//AA A..
Recall that A and B differ in exactly one row i. Therefore
4.1. General Result
(1 (1--a cb
cC AJA.BBB. (1+
CC
AT (1)
c8
We first prove a general result which the leverage score version of Theorem 3.1.
For j # i, we have
Theorem 4.1. Let A, E Re be two matrices. Con- sider the binary hypothesis testing problem of distinguish- ing Leverage A and Leverage y using constrained queries (Definition 2.11). Define
L = 8, B [B_ B.) - (B )dgld
-r|s, (B (B") B, (B. B.) 1
= (1 OleCO(((((O urs -2 (A. A.)
8= sup H(Leverage, (s), Leverage (+)). RecR
=1 (L=(((((())))))
(2)
where the first step by definition of the leverage score model, the second step is by property of trace, the third step is Eq. (1), the fourth step is by definition of the leverage score model.
Then the sample complexity of the binary hypothesis test- ing problem is 0(8-2). That is, there is an algorithm that successfully solves the problem using O energy- constrained queries, and any algorithm that successfully solves the problem uses 2(5-2) energy- congs-ccontt queries.
Upper bound for TV. For the TV distance, we have
n
TV(P, Q) = Σ
lps 9,1
Proof. The proof is similar to Theorem 3.1 and omitted. LI
j=1
7

---

Binary Hypothesis Testing for Softmax Models and Leverage Score Models
lpj - 4z
model. If B AR for some invertible matrix R E Rdxdd then we have
12
x Σ ((EC/(co))p:
q: = (,) )a/d
8+1 S O(cC/(co))
(A,R(R' AT A.) "R) Au//d
(As(A) A.) )is/ )is//
where the first step is by definition of TV distance, and the third step is by Eq. (2). Therefore QV), z ((tC/(cō))
Pi.
Then Leverage, (s) = Leverage (s) for all s e (RR((0))* and is impossible distinguish the two models. Furthermore, there exist scenarios where A and B differ only in rows with very small probability weight under any input
Upper bound for (P,,, Q). Using
(P(P, S TVP..Q)
we also get
We now give an example where
(P,)))) S ((CC(c88))
AI, Bj,, -1,.11-(((11 2(1)
but
Now we have established the result when A and B differ in exactly one row. Let us now consider general case. If
TV (s), Leveragge)) 0(1/n)
0.16, then cō/(Ce)
O(1) and there is nothing to
prove. In the following, assume that c S 0.16. For 0 I k < n, define B* E Raxd be the matrix with B Bi,- for i < k and B Ai,, for i 2 k. Then D A. 8" B, and B and B differ exactly in one row. Let & = Br, A,, A,,
for any s satistying e S of S C for all i E [n].
Suppose A [L eι of A is equal to la, and all remaining rows are equal to ef =
ei] that is, the first d rows
Then for & satisfying e S 8 S C for all i E [n]. the distribu- tion P = Leverage, x (s) has probability mass ((1/n) on every element i {1,d d + d 2 n. (hiding constants depending on and C).
Then by the above discussion, we have
TV(Leverage gu (s), Leverage (8)) (c)) for all 0 S kn n-mnn1 1. 1. By metric property of TV,, we have
Now suppose B differs with A only in the first entry (1, 1),
and
QV(
< Σ
TV (t), Leverage petn (s))
B1,1 = A1,1 + 0(1).
0gkgn-1
Then for fixed 8, qj Pj for j E 12,...,,], 9i 2 pl, and
Σ ((eC/(c8))
qj S Pj for j E {d - 1,..., n}. So
0skgn-1
(P,Q) < TV(P,Q)
= -c(C((o))
= P1
Using (I²(P,,) Q) < TV(P.Q Q) we also get 1/2 Q) (cō)) This finishes the proof.
= =(1/n).
This shows that the sample complexity may depend After discussing the difficulties in establishing an upper bound, we now show local upper bound, which says for fixed A and fixed direction M, there is an algorithm that dis- tinguishes Leverage, a and Leverage AteM queries, for small enough e > 0.
In Theorem 4.2, the bound has linear dependence in -1, An interesting question is the improve the bound to quadratic dependence
A+eM using O 2)
4.3. Upper Bound
Theorem 4.3. Fix A, M E paad where || O(1). For > define B, A + cM. We consider the binary hy- pothesis testing problem with Leverage, A and Leveragen; for small Let u sup, Val'Leverage, a (s) (w.) where
Let A, B E Raxd be parameters of the leverage score mod- els, 8 E T be the input vector, P = Leverage, A (s) (Pi...., PP), Q Leverage = (q ..)). For the upper bounds of the leverage score model, we run into sim- ilar difficulties as for the softmax model. Firstly, different matrices A and B could give rise to the same leverage score
W. diag(( - -A.AA] A.) -1 (MM ATT)
(A, -1))
8

---

Binary Hypothesis Testing for Softmax Models and Leverage Score Models
where the division between vectors is entrywise division. Then for < > 0 small enough, there is algorithm that uses 0(E-2V= =)- queries and distinguishes between Leverage and Leverage
tance (Polyanskiy & Wu, 2023+) between softmax outputs under constrained inputs governs the sample complexity. This leads to a tight upper and lower bound framework via careful analysis of the sensitivity of softmax distributions to perturbations in the parameter matrix.
Proof of Theorem 4.3 is deferred to Appendix A.4, Similarly to the softmax model case, Theorem 4.3 is also tight.
For the leverage score model (Section 4), the challenge is even greater due to the nonlinear matrix expressions in- volved, including matrix inversion and normalization, and the fact that the input sss is vector that rescales rows of the matrix. We overcome this by establishing operator norm bounds and using perturbation theory to relate changes in the parameter matrix to changes in the output distribution. Our proof carefully propagates these changes through the matrix expressions and yields tight dependence on both the model diference and input constraints.
Theorem 4.4. Work under the same setting as Theorem 4.3. For > 0 small enough, any algorithm that distinguishes between S and SoftMaxg, must use S2(= (()) energy-constrained queries.
Proof. The proof is by combining the proof of Theorem 4.3 and Theorem 4.1. We omit the details.
D
5. Discussion
6. Conclusion and Future Directions
Practical Implications. Softmax and leverage score dis- tributions arise naturally in machine learning and numerical linear algebra (Lee & Sidford, 2014; Lee al., 2015; Cohen et al., 2019b; Song, 2019; Jiang et al., 2020a; Song al., 2019b; Lee et al., 2020). Softmax distributions have clear connection to LLMs (Wang et al., 2022; Li & Liang. 2021; Dai et al., 2022: Burns et al., 2023; Hase et al., 2023; Xie et al., 2022), and leverage score distribution serves as a more general and complex case. We study the distinguishability of models (softmax and leverage score based) through the lens of binary hypothesis testing, establishing tight sam- ple complexity bounds. These results directly address the challenge of determining how much information (or how many queries) is needed to tell apart closely related mod- els, a theoretical formulation aligned with understanding model "abilities" via limited parameter access. Moreover, our framework sets a path toward identifying distinguishable components of large models. For instance, showing that cer- tain parameters contribute more significantly to distinguisha- bility (via Hellinger distance bounds) ofers insight into what might constitute an "ability region" " within a model, aligning with the introductory motivation.
Widely applied across various domains, softmax and lever- age scores play crucial roles in machine learning and linear algebra. This study delves into the testing problem aimed at distinguishing between different models of softmax and leverage score distributions, each parameterized by distinct matrices. We establish bounds on the number of samples within the defined testing problem. With the rapidly es- calating computational costs in current machine learning research, our work holds the potential to offer valuable insights and guidance for distinguishing between the dis- tributions of different models. We discuss a few possible directions for further research. In Theorem 3.5 and Theo- rem 4.3, determine the local sample complexity of the binary hypothesis testing problems for softmax models and leverage score models. In particular, the sample complexity is 2(), where v is a certain function depending on A and M (where B = A + eM). The form of v is an op- timization problem over the space of possible inputs. An interesting question is to provide bounds on the quantity v. or provide computation-effiin efffccienn algorithms for determin- ing the value of v of finding the optimal input (x for softmax, for leverage score). This will lead to computation-efficien algorithms for solving the binary hypothesis testing problem in practice.
Technical Novelty. The core novelty of our proofs lies in adapting classical binary hypothesis testing (Pensia et al., 2023; 2024), typically studied in the context of generic distributions, to the structured, parameterized families of distributions induced by softmax and leverage score models. Unlike arbitrary distributions, these models produce distri- butions that are nonlinear functions of the input and matrix parameters, which poses unique analytical challenges.
In this paper, we focused on the binary hypothesis testing problem, where the goal is distinguish two models with different parameters. There are other hypothesis testing problems that are of interest both in theory and practice. For example, in the goodness-of fit problem, the goal is to determine whether an unknown model is equal to or far away from given model. In the two-sample testing problem, the goal is to determine whether two unknown models are the same or far away from each other. These problems have potential practical applications and we leave them as an interesting future direction.
For the softmax model (Section 3), one key difficulty is that different parameter matrices and can induce indistin- guishable distributions due to invariance under certain trans- formations (c.g., row shifts). To handle this, we intro- duce structural constraints and prove that the Hellinger dis-

---

Binary Hypothesis Testing for Softmax Models and Leverage Score Models
Acknowledgements
Brand, v. d., Lee, Y.-T., Nanongkai, D., Peng, R., Sara- nurak, T.,, Sidford, A., Song, Z.., and Wang, D. Bipar- tite matching in nearly-linear time on moderately dense graphs. In 2020 IEEE st Annual Symposium on Founda- tions of Computer Science (FOCS), pp- 919-930. IEEE, 2020a.
The author would like to thank the anonymous reviewer of ICML 2025 for their highly insightful suggestions.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted here.
Brand, J. v. d., Lee, Y. T., Sidford, A., and Song. Z. Solving tall dense linear programs in nearly linear time. In Pro- the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pp. 775-788, 2020b.
ceedings of the
Brand, v. d., Song, Z., and Zhou, T. Algorithm and hard- ness for dynamic attention maintenance in large language models. In ICML, 2024.
References
Alman, and Song, Fast attention requires bounded entries. Advances Neural Information Processing Sys- tems, 36:631 2023.
Brock, A., Donahue, J., and Simonyan, K. Large scale GAN training for high fidelity natural image synthesis. In International Conference on Learning Representations, 2019. URL https:ttp///.....t http://ppneeeeeeeeeeeeeeeee net net.oouumtee/fu forum? i id=Bixsqj09Fm.
Alman, and Song, Z. How capture higher-order correla- tions? generalizing matrix softmax attention kronecker computation. In ICLR, 2024a.
Alman, and Song. The fine- grained complexity of gradient computation for training large language models. In NeurIPS, 2024b.
Brown, T., Mann, B., Ryder, N., Subbiah, M., Kaplan, J. D., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., et al. Language models are few-shot learners. Advances in neural information processing systems, 33: 1877-1901, 2020.
Alman, J. and Song, Z. Only large weights (and not skip connections) can prevent the perils of rank collapse. arXiv preprint arXiv:2505. 16284, 2025a.
Bubeck, S., Chandrasekaran, V., Eldan, R., Gehrke, J., Horvitz, E., Kamar, E., Lee, P.. Lee, Y. T., Li, Y., Lundberg, S., et al. Sparks of artificial general intel- ligence: Early experiments with gpt-4. arXiv preprint arXiv:2303. /2712, 2023.
Alman, J. and Song. Z. Fast rope attention: Combining the polynomial method and fast fourier transform. In arXiv preprint arXiv:2505, 11892, 2025b.
Arias-Castro, E., Pelletier, B., and Saligrama, V. Remember the curse of dimensionality: The case of goodness-of testing in arbitrary dimension. Journal of Nonparametric Statistics, 30(2):448-477 2018
Burns, C., Ye. H., Klein, D., and Steinhardt, J. Discovering latent knowledge language models without supervision. ICLR, 2023.
Cai, H., Lou, Y., McKenzie, D., and Yin, W. zeroth- order block coordinate descent algorithm for huge-scale black-box optimization. International Conference on Machine Learning, pp. 1193-1203. PMLR, 2021.
Bang, Y., Cahyawijaya, S., Lee, N., Dai, W., Su, D., Wilie, B., Lovenia, H., Ji, Z., Yu, T., Chung, W., et al. A mul- titask, multilingual, multimodal evaluation of chatgpt on reasoning, hallucination, and interactivity. In Pro- ceedings of the 13th International Joint Conference on Natural Language Processing and the 3rd Conference of the Asia-Pacific Chapter of the Association for Computa- tional Linguistics (Volume 1: Long Papers), pp. 675-718, 2023.
Cao, Y. Sorsa: Singular values and orthonormal regular- ized singular vectors adaptation of large language models. arXiv preprint arXhv:2409.0005. 2024.
Cao, Y., Li, X., and Song, Z. Grams: Gradient de- scent with adaptive momentum scaling. arXiv preprint arXiv:2412. 2024.
Bourgain, J., Lindenstrauss, J., and Milman, V. Approxima- tion of zonoids by zonotopes. 1989.
Cao, Y., Chen, B., Li, X., Liang, Y., Sha, Z.,, Shi, Z., Song. Z., and Wan, M. Force matching with rela- tivistic constraints: physics-inspired approach to sta- ble and efficient generative modeling. arXiv preprint 0rXiv:2502.08/500 2025a.
Boutsidis, C. and Woodruff, D. P. Optimal cur matrix de- compositions. In Proceedings of the forty-sixth annual ACM symposiun on Theory of computing, pp. 353-362, 2014.
10

---

Binary Hypothesis Testing for Softmax Models and Leverage Score Models
Cao, Y., Guo, X., Huo, J., Liang, Shi, Z., Song, Z., Zhang, J., and Zhuang, Z.. Text-to-image diffusion models cannot count, and prompt refinement cannot help, arXiv preprint Axiv::2003.06884, 2025b.
Chervenak, J., Lieman, H., Blanco-Breindel, M., and Jindal, S. The promise and peril of using a large language model to obtain clinical information: Chatgpt performs strongly as fertility counseling tool with limitations. Fertility and Sterility, 2023.
Cao, Y., Li, X., Liang, Y., Sha, Z., Shi, 7., Song, Z., and Zhang, J. Dissecting submission limit in desk-rejections: A mathematical analysis of fairness in ai conference poli- cics. arXiv preprint arXiv:2502.00690 2025c.
Chia, Y. K., Hong. P., Bing, L.,, and Poria, S. Instructeval: Towards holistic evaluation of instruction-tun tuned large lan- guage models. arXiv preprint arXiv:2306.0477 04757, 2023.
Cao, Y., Song, Z., and Yang, C. Video latent flow match- ing: Optimal polynomial projections for video interpola- tion and extrapolation. arXiv preprint arXiv:2502.00500, 2025d.
Choi, M., Pei, J., Kumar, S., Shu, C., and Jurgens, D. Do Ilms understand social knowledge? evaluating the socia- bility of large language models with socket benchmark. In Proceedings of the 2023 Conference on Empirical Meth- ods in Natural Language Processing, pp- 11370-11403, 2023.
Chan, S.-O., Diakonikolas, I., Valiant, P., and Valiant, G. Optimal algorithms for testing closeness of discrete distri- butions. In Proceedings of the twenty- anmual ACM- SIAM symposium on Discrete algorithms, pp. 1193-1203. SIAM, 2014.
Clarkson, K. L. and Woodruff, D. P. Low-rank approxi- mation and regression in input sparsity time. In STOC, 2013.
Cohen, M. B. and Peng, R. Lp row sampling by lewis weights. In Proceedings of the forty-seventh annual ACM symposium on Theory of computing, pp. 183--192 2015.
Chang, Y.TT., Hu, Z., Li. X., Yang, S., Jiang, J., and Sun, N. Dihan: A novel dynamic hierarchical graph attention network for fake news detection. In Proceedings of the 33rd ACM International Conference on Information and Knowledge Management, pp. 197-206, 2024.
Cohen, M. B., Cousins, B., Lee, Y. T., and Yang. X. A near- optimal algorithm for approximating the john ellipsoid. In Conference on Learning Theory, pp. 849-873. PMLR, 2019a.
ChatGPT. Optimizing language models for dialogue. Ope- nAI Blog, November 2022. URL https: /openai. com/bloge chatgpt/.
Cohen, M. B., Lee, Y. T., and Song. Z. Solving linear programs in the current matrix multiplication time. In STOC, 2019b.
Chen, B., Li, X., Liang, Y., Long, J., Shi, Z., and Song, Z. Circuit complexity bounds for rope-based transformer architecture. arXiv preprint urXiv:2411.0000
2024.
Corbett-Davies, S., Gaebler, J. D., Nilforoshan, H., Shroff, R., and Goel, S. The measure and mismeasure of fairness. Journal of Machine Learning Research, 24(312):1-117, 2023.
Chen, B., Shi, Z., Song, Z., and Zhang. J. Provable failure of language models in learning majority boolean logic via gradient descent. arXiv preprini arXiv:2504.04702. 2025a.
Dai, D., Dong, L., Hao, Y., Sui, Z., Chang, B., and Wei, F. Knowledge neurons pretrained transformers. In Pro- ceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Longg Papers), pp. 8493-8502, 2022.
Chen, L.., Kol, G., Paramonov, D., Saxena, R. R., Song, Z and Yu, H. Towards multi-past pasts streaming lower bounds for optimal approximation of max-cut. Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 878- 978-9244.55 SIAM, 2023a.
Daitch, S. I. and Spielman, D. A. Faster approximate lossy generalized flow via interior point algorithms. In Proceed- ings of the fortieth annual ACM symposium on Theory of computing, pp. 451 155-460, 2008
Chen, Y., Wang, R., Jiang, H., Shi, S., and Xu, R. Exploring the use of large language models for reference-free text quality evaluation: An empirical study. In Findings of the Association for Computational Linguistics: IJCNLP- AACI 2023 (Findings), pp- 361-374, 2023b.
Das, B. C., Amini, M. H., and Wu, Y. Security and privacy challenges of large language models: A survey. ACM Computing Surveys, 57(6):1-39 2025.
Chen, Y., Li, X., Liang, Y., Shi, Z., and Song, Z. The computational limits of state-space models and mamba via the lens of circuit complexity. In Conference on Parsimony and Learning. PMLR, 2025b.
Deng, Y., Li, Z., and Song, Z. Attention scheme inspired softmax regression. arXiv preprint (rXiv:2304.10111 2023a.

---

Binary Hypothesis Testing for Softmax Models and Leverage Score Models
Deng, Y., Mahadevan, S., and Song, Z. Randomized and deterministic attention sparsification algorithms for over- parameterized feature dimension. arxiv preprint: arxiv 23304.3426,, 2023b.
Gao, Y., Mahadevan, S., and Song, Z. An parameterized exponential regression. arXiv preprint arXiv:2303.16504 2023.
Gilyén, A., Song, Z., and Tang, E. An improved quantum- inspired algorithm for linear regression. Quantum, 6:754, 2022.
Deng, Y., Li, Z.., Mahadevan, S., and Song, Z. Zero-th order algorithm for softmax attention optimization. In 2024 IEEE International Conference on Big Data (BigData),
pp. 24-33. IEEE, 2024.
Go. J. H., Sari, A., Jiang. J., Yang, S., and Jha, S. Fake news quick detection on dynamic heterogeneous information networks. arXiv preprint arXiv:2205.07033 2022.
Deng, Y., Li, X., Song. Z., and Weinstein, O. Discrepancy minimization in input-sparsity time. In Proceedings of the 42nd International Conference on Machine Learning (ICML), 2025.
Goldreich, O. and Ron, D. On testing expansion in bounded- degree graphs. Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation: In Collaboration with Lidor Avigad, Mihir Bellare, Zvika Brakerski, Shafi Goldwasser, Shai Halevi, Tali Kaufman, Leonid Levin, Noam Nisan, Dana Ron, Madhu Sudan, Luca Trevisan, Salil Vadhan, Avi Wigder- son, David Zuckerman, pp. 68-75, 2011.
Deroy, A., Ghosh, K., and Ghosh, S. How ready are pre- trained abstractive models and lims for legal case judge- ment summarization? arXiv preprint arXiv:2306.012 01244, 2023.
Devlin, J., Chang, M.-W., Lee, K., and Toutanova, K. Bert: Pre-training of deep bidirectional transformers for lan- guage understanding. Proceedings of the 2019 confer- ence of the North American chapter of the association for computational linguisties: human language technologies, volume I (long and short papers), pp. 4171-4186, 2019.
Gu, Y., Song, Z., Yin, J., and Zhang. L. Low rank matrix completion via robust alternating minimization in nearly linear time. In ICLR, 2024.
Gu, Y., Song, Z., and Zhang, L. Faster algorithms for structured linear and kernel support vector machines. In ICLR, 2025.
Dosovitskiy, A., Beyer, L., Kolesnikov, A., Weissenborn, D., Zhai, X., Unterthiner, T., Dehghani, M., Minderer, M., Heigold, G., Gelly, S., al. An image is worth 16x16 words: Transformers for image recognition at scale. arXiv preprint arXiv:2010.1192 2020.
Guo, T., Guo, K., Liang. Z., Guo, Z., Chawla, N. V., Wiest, O., Zhang, X., et al. What indeed can gpt models do in chemistry? comprehensive benchmark eight tasks. arXiv preprint 2rX.v:2305. 2023.
Drineas, P., Magdon-Ismail. M., Mahoney, M. W., and Woodruff, D. P. Fast approximation of matrix coher- ence and statistical leverage. The Journal of Machine Learning Research, 13(1):345533066 2012.
Guo, X., Huang, Z., Huo, J., Liang, Y., Shi, Z., Song, Z., and Zhang. J. Can you count to nine? human evaluation benchmark for counting limits in modern text-to-video models. arXiv preprint arXiv:2504.04053 50.55004441,,.. 2025a.
Ferrara, E. Should chatgpt be biased? challenges and risks of bias in large language models. arXiv preprint arXiv:2304.03338, 2023.
Guo, X., Huo, J., Shi, Z., Song, Z., Zhang, J., and Zhao, J. T2vphysbench: first-priccipls benchmark for physical consistency text-to-video generation. arXiv preprint vrXiv:2555.03377 2025b.
Fu, Z., Liu, F., Zhang, J.. Wang, H., Yang, C., Xu, Q. Qi, J., Fu, X., and Zhou, A. Sagn: semantic adaptive graph network for skeleton-based human action recognition. In Proceedings of the 2021 International Conference on Multimedia Retrieval, pp. 110-117, 2021.
Hase, P., Bansal, M., Kim, B., and Ghandeharioun, A. Does localization inform editing? surprising differences in causality-based localization vs. knowledge editing in lan- guage models. Advances in Neural Information Process- ing Systems, 36: 36:17643-17663 2023.
Gajjar, A., Tai, W. M., Xingyu, X., Hegde, C., Musco, C., and Li, Y. Agnostic active learning of single index models with linear sample complexity. In The Thirty Seventh Annual Conference on Learning Theory, pp. 1715-1754. PMLR, 2024.
Hewitt, J. and Manning, C. D. A structural probe for finding syntax in word representations. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Lan- guage Technologies, Volume (Long and Short Papers), pp. 4129-4138, 2019.
Gao, R., Liu, F., Zhang, J., Han, B., Liu, T., Niu, G., and Sugiyama, M. Maximum mean discrepancy test is aware of adversarial attacks. In International Conference on Machine Learning, pp. 3564-3575. PMLR, 2021.
12

---

Binary Hypothesis Testing for Softmax Models and Leverage Score Models
Hu, E. J., Shen, Y., Wallis, P., Allen-Zuu, Z., Li, Y., Wang, S., Wang, L.,, Chen, W., al. Lora: Low-rank adaptation of large language models. ICLR, 1(2):3, 2022.
Jiang, H., Kathuria, T., Lee, Y. T., Padmanabhan, S., and Song, 7_ A faster interior point method for semidefinite programming. In 2020 IEEE 6l annual symposium on foundations of computer science (FOCS), pp. 910-918. IEEE, 2020a.
Hu, J. Y.-.., Chen, B.-Y., Wu, D., Ruan, F., and Liu, H. Nonparametric modern hopfield models. arXiv preprint arXiv:2404.03900, 2024a.
Jiang, H., Lee, Y. T., Song, Z., and Wong, S. C.-w. An improved cutting plane method for convex optimization, convex-concave games and its applications. In STOC, 2020b.
Hu, J. Y.-C., Lin, T., Song, Z., and Liu, H. On computational limits of modern hopfield models: A fine-grain fine-grained com- plexity analysis. In Forty-first International Conference on Machine Learning, 2024b.
Johnson, D., Goodman, R., Patrinely, J., Stone, C., Zimmer- man, E., Donald, R., Chang, S., Berkowitz, S., Finn, A., Jahangir, E., et al. Assessing the accuracy and reliability of ai ai-generated medical responses: an evaluation of the chat-gpt model. Research square, pp. rs-3, 2023.
Hu, J. Y.C.,, Su, M., Kuo, E.-J., Song, Z., and Liu, H. Computational limits of low-rank adaptation (lora) for transformer-based models. arXiv preprint arXiv:2406.03116, 2024c.
Kang. W.-C. and McAuley, J. Self-attentive sequential recommendation. In ICDM, 2018.
Hu, J. Y.-C., Wu, D., and Liu, H. Provably optimal mem- ory capacity for modern hopfield models: Transformer- compatible dense associative memories as spherical codes. In eiirth- Conference Neural Informa- tion Processing Systems (NeurIPS), 2024d.
Kaplan, J., McCandlish, S., Henighan, T., Brown, T. B., Chess, B., Child, R., Gray, S., Radford, A., Wu, J., and Amodei, D. Scaling laws for neural language models. arXiv preprint arXiv:2001.08366 2020.
Karunanayake, I., Jiang, J., Ahmed, N., and Jha, S. K. Ex- ploring uncharted waters of website fingerprinting. IEEE Transactions on Information Forensics and Security, 19: 1840-1854, 2023.
Hu, J. Y.CC,, Zhang, X., Su, M., Song, Z., and Liu, H. Minimalist softmax attention provably learns constrained boolean functions. arXiv preprint arXiv:2505.19531 2025.
Ke, Y., Li, X., Liang, Y., Shi, Z., and Song. Z. Circuit complexity bounds for visual autoregressive model. arXiv preprint arXiv:2501.0422 0429999 2025.
Huang, B., Jiang, S., Song. Z.. Tao, R., and Zhang, R. Solving sdp faster: robust ipm framework and efficient implementation. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pp. 233- 244. IEEE, 2022.
Kim, J. and Suzuki, T. Transformers provably solve parity efficiently with chain of thought. In ICLR, 2025.
Laskar, M. T. R., Bari, M. S., Rahman, M., Bhuiyan, M.
Huang, H., Sun, N., Tani, M., Zhang, Y., Jiang, J., and Jha, S. Can Ilm- renegeeerrted misinformation be detected: A study on cyber threat intelligence. Fature Generation Computer Systems, pp. 107877, 2025.
A. H. Joty, S.,, and Huang. J. A systematic study and com- prehensive evaluation of chatgpt on benchmark datasets. In Findings of the Association for Computational Linguis- tics: ACL 2023, pp. 431 469, 2023.
Huang, X., Liu, W., Du, B., and Tao, D. Leveraged matrix completion with noise. IEEE Transactions Cybernet- ics, (0(():4444))) 4453, 2023.
Lee, J. D., Shen, R., Song, Z., Wang, M., et al. Generalized leverage score sampling for neural networks. Advances Neural Information Processing Systems, 33:10775- 10787, 2020.
Ingster, Y. I. On the minimax nonparametric detection of signals in white gaussian noise. Problemy Peredachi Informatsii, 18(2):61-73, 1982.
Lee, Y. T. and Sidford, Path finding methods for lin- ear programming: Solving linear programs (vrank) iterations and faster algorithms for maximum flow. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pp. 424 433. IEEE, 2014.
Ingster, Y. I. Minimax testing of nonparametric hypotheses on a distribution density in the Lp metrics. Theory of Probability & Its Applications, 31(2):333-3377 1987.
Lee, Y. T., Sidford, A., and Wong, S. C.-w. A faster cutting plane method and its implications for combinatorial and convex optimization. In 2015 IEEE 56th Annual Sym- posium on Foundations of Computer Science, pp. 1049 1065. IEEF, 2015.
loffe, S. and Szegedy, C. Batch normalization: Accelerat- ing deep network training by reducing internal covariate shift. In International Conference on Machine Learning (ICML), pp. 448 456. PMLR, 2015.
13

---

Binary Hypothesis Testing for Softmax Models and Leverage Score Models
Lee, Y. T., Song, Z., and Zhang, Q. Solving empirical risk minimization in the current matrix multiplication time. In Conference Learning Theory, pp. 2140-2157. PMLR, 2019.
Liu, C., Zhang, Wang, S., Fan, W., and Li, Q. Score-based generative diffusion models for social recommendations, arXiv preprint arXiv:2412.
2024b.
Liu, F., Xu, W., Lu, J., Zhang, G., Gretton, A., and Suther- land, D. J. Learning deep kernels for non-parametric two-sample tests. In International conference on machine learning, pp. 6316 6326. PMLR, 2020a.
Li, T. and Yuan, M. On the optimality of gaussian kernel based nonparametric tests against smooth alternatives. arXiv preprint arXiv: (909:039900002 2019.
Li, X., Liang, Y. Shi, Z., Song, Z., and Yu, Fast john ellip- soid computation with differential privacy optimization. arXiv preprint ar arXiv:2408.06399 2024a.
Liu, F. Xu, W., Lu, J., and Sutherland, D. J. Meta two- Learning kemelss for testing with limited data. Advances in Neural Information Processing Sys- tems, 34:5848-5860, 2021a.
sample testing:
Li, X., Song, Z., and Yu, J. Quantum speedups for approximating the john ellipsoid. arXiv preprint arXiv:2408. 14018, 2024b.
Liu, F., Wang. H., Zhang. J., Fu, Z., Zhou, A., Qi, J., and Li, Z. Evogan: An evolutionary computation assisted gan. Neurocomputing. 469:81-90, 2022a.
Li, X., Liang. Y., Shi, Z., Song, Z., Wang, W., and Zhang. On the computational capability of graph neural networks: A circuit complexity bound perspective. arXiv preprint arXiv:2501.0644 2025a.
Liu, H., Li, Z., Hall, D., Liang, P., and Ma. T. Sophia: A scalable stochastic second-order optimizer for language model pre-training, ICLR, 2024c.
Li, X., Sun, N., and Jiang, J. LIm- lim-daeed approaches for real-time eyber threat detection and response: A survey. manuscript, 2025b.
Liu, J., Xia, C. S., Wang, Y., and Zhang, L. Is your code generated by chatgpt really correct? rigorous evaluation of large language models for code generation. NewrIPS, 2023a.
Li, X., Xie, S., and Song, Z. Deterministic sparse fourier transform for continuous signals with frequency gap. In Proceedings of the 42nd International Conference on Machine Learning (ICML), 2025c.
Liu, L., Cai, L.,, Zhang, C., Zhao, X., Gao, J., Wang, W., Lx, Y., Fan, W., Wang, Y., He, M., Liu, Z., and Li, Q. Lin- rec: Linear attention mechanism for long-term sequential recommender systems. In SIGIR, 2023b.
L. and Liang, P. Prefix-tuning: Optimizing continuous prompts for generation. In ACI., 2021.
Liu, S. C., Song, Z., and Zhang, Breaking the n-pass bar- rier: A streaming algorithm for maximum weight bipartite matching. arXiv preprint arXi::2009.06106 2020b.
Li, Z., You, C., Bhojanapalli, S., Li, D., Rawat, A. S., Reddi, S. J., Ye, K., Chern, F., Yu, F., Guo, R., et al. The lazy neuron phenomenon: On emergence of activation sparsity in transformers. ICLR, 2023.
Liu, S. C., Song, Z., Zhang, H., Zhang, L., and Zhou, T. Space-efficient interior point method, with applica- tions to linear programming and maximum weight bi- partite matching. 50th International Colloquium on Automata, Languages. and Programming (ICALP 2023), pp. 1. Schloss Bagsuuhl-Liibniz--eenmum für Infor- matik, 2023c.
Li, Z., Liu, H., Zhou, D., and Ma, T. Chain of thought em- powers transformers to solve inherently serial problems. In ICLR, 2024c.
Liang, P., Bommasani, R., Lee, T., Tsipras, D., Soylu, D., Yasunaga, M., Zhang, Y., Narayanan, D., Wu, Y., Ku- mar, A., et al. Holistic evaluation of language models. Transactions on Machine Learning Research (TMLR), 2023.
Liu, S. C., Song, Z., Zhang, H., Zhang, L., and Zhou, T. Space-efficient interior point method, with applications to linear programming and maximum weight bipartite matching. In ICALP, 2023d.
Lipman, Y., Chen, R. T., Ben-Hamu, H., Nickel, M., and Le, M. Flow matching for generative modeling. arXiv 2022.
Liu, X., Gong, C., and Liu, Q. Flow straight and fast: Learning generate and transfer data with rectified flow. arXiv preprint arXiv:2209.003:
preprint 2rXiv:2210.07..2
2022b.
Liu, A., Feng, B., Xue, B., Wang, B., Wu, B., Lu, C., Zhao, C., Deng, C., Zhang, C., Ruan, C., et al. Deepseek- v3 technical report. arXiv preprint axXiv:2412.19437, 2024a.
Liu, Y. P. and Sidford, A. Faster energy maximization for faster maximum flow. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pp. 803-814, 2020.
14

---

Binary Hypothesis Testing for Softmax Models and Leverage Score Models
Liu, Z.,, Lin, Y., Cao, Y., Hu, H., Wei, Y., Zhang, Z., Lin, S., and Guo, B. Swin transformer: Hierarchical vision transformer using shifted windows. In ICCV, 2021b.
Price, E., Song. Z., and Woodruff, D. P. Fast regression with fx guarantee. In International Colloquium Au- tomata, Languages, and Programming. Schloss Dagstuhl- fur Informatik GmbH, Dagstuhl Pub-
Madry, A. Navigating central path with electrical flows: From flows to matchings, and back. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pp. 252-262. IEEE, 2013.
lishing, 2017.
Pu, D. and Demberg, V. Chatgpt vs authord text: In- sights into controllable text summarization and sentence style transfer. ACL (Student Abstract), 2023.
Madry, A. Computing maximum flow with augmenting electrical flows. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pp. 593- 602. IEEE, 2016.
Qin, C.,, Zhang, A., Zhang. Z., Chen, J., Yasunaga, M., and Yang, D. Is chatgpt ceneral-purpose natural language processing task solver? EMNLP, 2023a.
Malladi, S., Gao, T., Nichani, E., Damian, A., Lee, J. D., Chen, D., and Arora, S. Fine-tuning language models with just forward passes. NeurIPS, 2023.
Qin, L., Song, Z., Zhang, L., and Zhuo, D. An online and unified algorithm for projection matrix vector multiplica- tion with application to empirical risk minimization. In AISTATS, 2023b.
Meng, K., Bau, D., Andonian, A., and Belinkov, Y. Locating and editing factual associations in gpt. Advances in Neu- ral Information Processing Systems, 15:1739-17377, 2022.
Radford, A., Narasimhan, K., Salimans, T., Sutskever, I., al. Improving language understanding by generative pre-training, OpenAl Blog, 2018.
Nay, J., Karamardian, D., Lawsky, S. B., Tao, W., Bhat, M., Jain, R., Lee, A. T., Choi, J. H., and Kasai, J. Large language models as tax attorneys: A case study in legal capabilities emergence. arXiv preprint arXiv:2306.07075, 2023.
Radford, A., Wu, J., Child, R., Luan, D., Amodei, D., Sutskever, I., et al. Language models are unsupervised multitask learners. OpenAl blog, 1(8)9 2019.
Rafailov, R., Sharma, A., Mitchell, E., Ermon, S., Manning, D., and Finn, C. Direct preference optimization: Your language model secretly reward model. NeurIPS, 2023.
Neyman, and Pearson, E. S. Ix. on the problem of the most efficient tests of statistical hypotheses. Philosophi- cal Transactions of the Royal Society of London. Series A, Containing Papers of a Mathematical or Physical Char- acter, 231 (89477766)) 1933.
Rathee, K. Meet google meena, 2020.
Reif, E., Yuan, A., Wattenberg, M., Viegas, F. B., Coenen, A., Pearce, A., and Kim, B. Visualizing and measuring the geometry of bert. Advances in Neural Information Processing Systems, 32, 2019.
OpenAl. Gpt-4 technical report. arXiv preprint arXiv:2303.08774, 2023.
Pallagani, V., Muppasani, B., Murugesan, K., Rossi, F., Sri- vastava, B., Horesh, L., Fabiano, F,, and Loreggia, A. Un- derstanding the capabilities of large language models for automated planning. arXiv preprint ar115. 2023.
Salemi, A. and Zamani, H. Evaluating retrieval quality in retrieval-augmented generation. SIGIR, 2024.
Schild, A. An almost-linear time algorithm for uniform ran- dom spanning tree generation. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Comput- ing. pp. 214-227, 2018.
Peebles, W. and Xie, S. Scalable diffusion models with transformers. In Proceedings of the IEEE/CVF interna- tional conference on computer vision, pp. 4195-4205, 2023.
Shen, X., Song, Z., Zhou, Y., Chen, B., Li, Y., Gong, Y., Zhang. K., Tan, H., Kuen, J., Ding, H., et al. Lazydit: Lazy learning for the acceleration of diffusion transform- ers. In Proceedings of the AAAI Conference Artificial Intelligence, volume 39:19, pp. 20409-20413 2025.
Pensia, A., Asadi, A. R., Jog, V., and Loh, P.-L. Simple binary hypothesis testing under local differential privacy and communication constraints. In COLT, 2023.
Pensia, A., Jog, V., and Loh, P.-L. The sample complexity of simple binary hypothesis testing. In COLT, 2024.
Shimizu, A., Cheng, X., Musco, C., and Weare, J. Improved active learning via dependent leverage score sampling. The Tweifth International Conference on Learning Representations, 2024.
Polyanskiy, Y. and Wu, Y. Information Theory: From Cod- ing to Learning. Cambridge University Press, 2023+
15

---

Binary Hypothesis Testing for Softmax Models and Leverage Score Models
Shin, S., Shomorony, I,, and Zhao, H. Efficient learning of linear graph neural networks via node subsampling. Advances in Neural Information Processing Systems, 36: 55479-55501, 2023.
Spataro, J. Introducing microsoft 365 copilot - your copilot for work, 2023.
Spielman, D. A. and Srivastava, N. Graph sparsification by effective resistances. In Proceedings of the fortieth annual ACM symposiun on Theory of computing, pp. 563-568, 2008a.
Siriwardhana, S., Weerasekera, R., Wen, E., Kaluarachchi, T., Rama, R., and Nanayakkara, S. Improving the domain adaptation of retrieval augmented generation (rag) models for open domain question answering. Transactions of the Association for Computational Linguisties, 11:1-17, 2023.
Spielman, D. A. and Srivastava, N. Graph sparsification by effective resistances. In Proceedings of the fortieth annual ACM symposium on Theory of computing, pp- 563-568, 2008b.
Song, Y., Yuan, Z., Zhang, S., Fang, Z., Yu, J., and Liu, F. Deep kernel relative test for machine- machine-generated text detection. The Thirteenth International Conference on Learning Representations, 2025.
Sridhara, G., Mazumdar, S., al. Chatgpt: A study on its utility for ubiquitous software engineering tasks. arXiv preprint arXiv:2305. 16837, 2023.
Sun, N., Ding, M., Jiang, J., Xu, W., Mo, X., Tai, Y., and Zhang, J. Cyber threat intelligence mining for proactive cybersecurity defense: A survey and new perspectives. IEEE Communications Surveys & Tutorials, 15(3))1748- 1774, 2023.
Song, Z. Matrix Theory:
Optimization, Concentration and Algorithms. PhD thesis, The University Texas at Austin, 2019.
Song, Z. and Yu, Z. Oblivious sketching-based central path method for solving linear programming problems. 38th International Conference on Machine Learning (ICML), 2021.
Team, G. Gemini: a family of highly capable multimodal models. arXiv preprini urXiv:2312. 1805, 2023.
Tian, K., Jiang, Y., Yuan, Z., Peng, B., and Wang, L. Visual autoregressive modeling: Scalable image generation via next-scale prediction. Advances in neural information processing systems, 37:84839 84865, 2024.
Song, Z., Woodruff, D. P., and Zhong, P. Low rank approxi- mation with entrywise 11 lo-norm error. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pp. 688-701, 2017.
Tran, N.-T., Tran, V.-H., Nguyen, B.-N., Yang, L., and Cheung, N.-M. M. Self-supervised gan: Analysis and im- provement with multi-class minimax game. In Advances in Neural Information Processing Systems, 2019.
Song, Z., Wang, R., Yang, I.., Zhang, H., and Zhong, Efficient symmetric norm regression via linear sketching. Advances in Neural Information Processing Systems, 32, 2019a.
Vaidya, P. M. A new algorithm for minimizing convex functions over convex sets. In 30th Annual Symposium Foundations of Computer Science, pp. 338 343. IEEE Computer Society, 1989.
Song. Z. Woodruff, D. P., and Zhong, P. Relative error tensor low rank approximation. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Al- gorithmss pp. 2772-2789. SIAM, 2019b.
Valiant, G. and Valiant, P. An automatic inequality prover and instance optimal identity testing. SIAM Journal on Computing, 46(1):422 (441)))42455))) 455, 2017.
Song, 7.,, Yang. X., Yang, Y., and Zhou, T. Faster algorithm for structured john ellipsoid computation. arXiv preprint arXiv:2211. 144.00771 2022.
Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, L., and Polosukhin, I. At- tention is all you need. Advances in neural information processing systems, 30, 2017.
Song, Z., Ye, M., Yin, J., and Zhang, L. A nearly-optimal bound for fast regression with Eo guarantee. In Inter- national Conference on Machine Learning (ICML), pp. 92463-32483 PMLR, 2023.
Veličković, P., Cucurull, G., Casanova, A., Romero, A.. Liò, P., and Bengio. Y. Graph attention networks. In International Conference on Learning Representations, 2018. URL https: http:///peeeeeeeeeeeeee net//oruum i id=rJXMpikCZ.
Song. Z., Vakilian, A., Woodruff, D., and Zhou, S. On socially fair low-rank approximation and column subset selection. Advances in Neural Information Processing Systems, 37:88874-88905, 2024a.
Wang, L., Lyu, C., Ji, T., Zhang, Z., Yu, D., Shi, S., and Tu, Z. Document-level machine translation with large language models. EMNLP, 2023.
Song. Z., Yin, J., and Zhang, L. Solving attention kernel regression problem via pre-conditioner. AISTATS, 2024b.
16

---

Binary Hypothesis Testing for Softmax Models and Leverage Score Models
Wang, X., Wen, K., Zhang, Z., Hou, L.,, Liu, Z., and Li, J. Finding skill neurons in pre-trained transformer-based language models. EMNLP, 2022.
Zhang, J. Graph unlearning with efficient partial retrain- ing. In Companion Proceedings of the ACM on Web Conference 2024, pp. 1218-1221, 2024.
Wei, C., Chen, Y., and Ma, T. Statistically meaningful approximation: a case study on approximating turing machines with transformers. Advances in Neural Infor- mation Processing Systems, 13:12071-12088 2022.
Zhang. J., Liu, F., and Zhou, A. Off-tanet: lightweight
neural micro-expression recognizer with optical flow fea- tures and integrated attention mechanism. In Pacific Rim International Conference on Artificial Intelligence, pp. 266 166-279. Springer, 2021.
Wu, D., Hu, J. Y.-C,, Hsiao, T.-.,, and Liu, H. Uniform memory retrieval with larger capacity for modern hop- field models. In International Conference on Machine Learning, pp. 53471-53514, PMLR, 2024a.
Zhang, J., Xue, R., Fan, W. Xu, X., Li, Q. Pei, J., and Liu, X. Linear-time graph neural networks for scalable recommendations. In Proceedings of the ACM Web Conference 2024, pp. 3533-3544, 2024.
Wu, D.. Hu, J. Y.-C., Li, W., Chen, B.-Y., and Liu, H. STanhop: Sparse tandem hopfield model for memory- enhanced time series prediction. In The Twelfth Interna- tional Conference Learning Representations (ICLR), 2024b.
Zhou, K., Zhu, Y., Chen, Z., Chen, W., Zhao, W. X., Chen, X., Lin, Y., Wen, J.-R., and Han, Don't make your Ilm evaluation benchmark cheater. arXiv preprint arXiv:231 100::2211..11444 2023.
Xie. S., Qiu, J., Pasad, A.. Du L., Qu, Q., and Mei, H. Hidden state variability of pretrained language models can guide computation reduction for transfer learning. EMNLP, 2022.
Xu, H., Wang, S., Li, N., Wang, K., Zhao, Y., Chen, K., Yu, T., Liu, Y., and Wang, H. Large language models for cyber security: A systematic literature review. arXiv preprint arXiv:2405.0477
2024.
Xu, X., Zhang, J., Liu, F., Sugiyama, M., and Kankanhalli, M. Adversarial attack and defense for non-parane non-parametric two-sample tests. In International Conference on Ma- chine Learning, pp. 24743-24769. PMLR, 2022.
Yang. Z., Dai, Z., Yang. Y., Carbonell, J., Salakhutdinov, R. R., and Le, Q. V. Xlnet: Generalized autoregressive pretraining for language understanding. Advances in neural information processing systems, 32, 2019.
Yao, T., Li, Y., Pan, Y.. and Mei, T. Hiri-vit: Scaling vision transformer with high resolution inputs. TPAMI, 2024.
Zamani, H. and Bendersky, M. Stochastic rag: End-to-end retreeval-uugmented generation through expected utility maximization. SIGIR, 2024.
Zandieh, A., Han, I., Avron, H., Shoham, N., Kim, C., and Shin, Scaling neural tangent kernels via sketching and random features. Advances in Neural Information Processing Systems, 1110020017,.,. 2021.
Zelikman, E., Huang, Q., Liang. P., Haber, N., and Good- man, N. D. Just one byte (per gradient): A note on low- bandwidth decentralized language model finetuning using shared randomness. arXiv preprint arXiv:2306.10015, 2023.
17

---

Binary Hypothesis Testing for Softmax Models and Leverage Score Models
Appendix
Roadmap. Section A, we provide all proofs which are missing from the main text. In Section B, we present more related work.
A. Missing Proofs
This section provide missing proofs from the main text. In Section A. we show the proof of general result for softmax model. In Section A.2, we demonstrate the proof of the lower bound for softmax model. In Section A.3, we prove the local upper bound for softmax model. In Section A.4, we present the proof for local upper bound for leverage score model.
A.1. General Result for Softmax Model
Proof of Theorem 3.1. Lower bound. If 2 0.1 then there is nothing to prove. In the following assume that < 0.1. Suppose that there is an algorithm that successfully solves the binary hypothesis testing problem. Suppose makes queries 31 F E Rd where z; may depend on previous query results. Let Yi...., Y,, [n] denote the query results, Let By and Qy denote the distribution of y under P and Q, respectively. By definition of 8, we have
(P QYaIY=-1) S 0².
for any E [mm] and yk-1, Then
(P Qym)
/ v PymMyym Qym
/ VPmm-1Qmm- / V P Um Qpm.
2 / /P 1ym-1Qmm-1l m 82
Repeating this computation, in the end we get
1 1- H-H' 2 8m
Because 5 S 0.1, we have - 1-22 322e8 exp(-228" If m S 0.016-2 then
1 112 m, Qym) exp(-202 22022m2)
exp(-0.000 -0.02)
0.98,
and
H2 Qvm) S 0.02.
This implies
TV(Pym, (PH(Py.,.QQ))) Qym) S 0.2,
which implies the success rate for binary hypothesis testing cannot be 2 3/-
In conclusion, any algorithm that successfully solves the hypothesis testing problem need to use ((5-2) queries.
Upper bound. Take x E d such that || < and = H(SoftMax, (I), toftMax By Lemma 2.5, using 0(8 samples we can distinguish SoftMax and SoftMax (x). Therefore we can distinguish Sof SMax and SoftMax, in ( queries by repeatedly querying x.
18

---

Binary Hypothesis Testing for Softmax Models and Leverage Score Models
A.2. Lower Bound for Softmax Model
Before giving the proof of Lemma 3.3, we prove weaker version of the lemma.
Lemma A.1. Let a, E R". Suppose there exists an 2 such that for every i E [n]. b; - as E (0,c). Let P be the distribution on [n]] with p; = exp(ax)((exp(a), 1n). Let Q be the distribution on [n] with qi exp(b:)/ (exp(b), (xx(()))exxp(() 1,). Then
HP(PQQ) = (1 exp(c/4))² = -
explc/2)
TV(P.Q) = tanh(c/4)= O(c).
Proof. Assume that a and b differ in m coordinates. By permuting the coordinates, WLOG assume that b, a, + for 1 S S m and b; = a, for m + 1 S i S n.
Write
8 = exp(a:)
and
Σ
exp(a:).
m=l
Then
(P(P.))=1- Σ VPiqi
sE/mi
eexp(e22)
V8 (x) + +1)
For fixed and the above is maximized at
eex((_e/2).
Plugging in the above s, we get
2
H²(PQQ) $
Texpl (exp(-ee/2 + 1)(exp(e/2)
(1 - (1-cxp(c/4) exp(c/4))²
1 + exp(e/2)
For TV, we have
TV(P.Q) Σ
(a: - pi) m+isisn t
t
++
8 exp((c) +
For fixed and c the above maximized at = texpl c/2). Plugging in this s, we get
TV(P,Q) Q) tanh(c/4).
19

---

Binary Hypothesis Testing for Softmax Models and Leverage Score Models
Proof of Lemma 3.3. We first prove the case where b; 2 a; for all E [n] Define e;
ay for all i [n]. By permuting
the coordinates, WLOG assume that 61 S ..... S Cn- Specially, define co 0. For 0 S k S n,, let D E R denote the vector where by = + min ) for all E [k]. Then can see that 6a and 6 b. and for every 0 S k S n - 1, the pair (b", bl+1) satisfies the assumption in Lemma A.I, For & lo I n, let p denote the softmax distribution corresponding to
b By Lemma A. for every 0 v k S n - 1, we have
H(P* ph+1) = 0((+1 1 - ck),
TV(P phtt) O Ek..
Because Hellinger distance and TV distance are both metries, we have
H(P,Q) H(P" P*)
n-1
$ Σ H(Ph, phtl)
k=
= =(()),
and
TV(P,Q) TV(PO, P")
Σ TV(P*, pkt1)
Oce).
This finishes the proof of the result when b, a, for all i [n].
Now let us consider the general case. Let E R be defined as = max(a; bj} for all i E [n]. Then
max{ ||a c|lso ||c - b s ||a - bl e.
Let R be the softmax distribution corresponding c. By our previous discussion, we have
H(P. R), HI (R, Q), TV(P, R), (R, Q) O(e).
By metric property of Hellinger distance and TV distance, we get
H(P.Q), 0()
as desired.
A.3. Local Upper Bound for Softmax Model
Proof of Theorem 3.5. We take satisfying ||ж|| < E that maximizes ValsodeMaxa (Mxx and repeatedly query x. We would like to apply Theorem 3.1. To do that, we need to show that
H'of SoftMax (x)) = (((EE)).
Let P- (oftMax (pi, . Pn), Q. SoftMaxn, (x) (q., 1.n)) Write Za (exp(AA)) 1m), Zn. (exp(B.x), 1n).
Then, it follows that
ZB = Σ exp(Ar), exp(c(Mz))))
JE|n]
Σ
exp(Aar)) Σ
(xp(Ar))(exp((MMb)) - 1)
jEIm
jE(m]
20

---

Binary Hypothesis Testing for Softmax Models and Leverage Score Models
Σ
exp(Ar) +
exp(Az))(((M)))+00
sE(m]
JEIn]
(1 + Ma) + 0(2)).
where the initial step is because of = A AM, , the second step is a result of simple algebra, the third step a consequence of the Taylor expansion of exp(:), assuming is sufficiently small and the fourth step the result the definition of A and involves the consolidation of addition, introducing the common term Za.
Then
qe,i exp( exp(Brx);
ZB exp(Ar); exp(eMxt)
ZA + c(p, Mx) 0((2))
px(1 + ((Ma): (v. Mx)) + ((²)).
(4)
where the initial step is because of the definition of qe,i the subsequent step is result of E3)(3), and the third step is due the definition of qi along with the Taylor expansion of f(x) 1/(1 + x) and exp(-), considering sufficiently small value.
So, we have that
1
H²(P.Q.)
Σ
(pp v
2
1=1
Σ
Pi(E - (x) 0(²2))
2
1=1
1 Varr + +(22)
1
1 v 0(e))
2
where the first step the result of Definition 2.2, the second step because of Eq), the third step the result of definition of (Mr)(Mx) (See Definition 2.3) and the forth step follows from the expression supp:l VaTgortNax, (()) (Mx). Applying Theorem 3.1 we finish the proof.
A.4. Local Upper Bound for Leverage Score Model
Proof of Theorem 4.3. We take satisfying S 57 S C' and Vi E [n] that maximizes sup, (ar and repeatedly query s. We need to show that
H² (Leverage (s) (s), Lsv, (s)) 1))
Leveragen,
Let P = Leverage (b) (pI, . ,r), Q. = Leverage (x) (q., (e,,)) We can compute that
de Dess = (2(1 - AA) AA (A,, A.)- A)))...
Define W -I- TT-AAAA, A,) (M, A.)-1 AA)) Then
4et = pe + 2W, + O
Computing (P(PQQ.) we get
HP(PQQ)) 1 -(Va..- 2
iE[m]
21

---

Binary Hypothesis Testing for Softmax Models and Leverage Score Models
Wis c + 0(2))
Pi
1E/n]
+ +
Pi
sE/n|
ēv + O
B. More Related Work
Softmax Computation and Regression Softmax computation, a crucial element in attention computation (Vaswani et al., 2017), plays a pivotal role in the development of LLMs. Several studies (Alman & Song, 2023; Brand et al., 2024; Liu et al., 2023d; Deng et al., 2023b) delve into the efficiency of softmax computation. To improve computational efficiency, (Alman Song, 2023) presents quicker attention computation algorithm utilizing implicit matrices. Similarly, (Brand al., 2024) utilizes lazy updates to speed up dynamic computation, while (Deng al., 2023b) employs a randomized algorithm for similar efficiency gains. Conversely, (Liu al., 2023d) utilizes approximate Newton method that operates in nearly linear time. (Gao al., 2023) centers the convergence of overparameterized two-layer networks with exponential activation functions, whereas (Deng et al., 2023a; Liu et al., 2023d) explore regression analysis within the framework of attention computation. All of these studies specifically focus on softmax based regression problems.
Softmax functions also widely used in computer vision. In particular, it is widely used in different backbone models, such as Vision Transformers (ViTs) (Dosovitskiy et al., 2020; Zhang et al., 2021; Liu et al., 2021b; Yao et al., 2024) and Visual Autoregressive (VAR) (Tian al., 2024) models, and also has advanced many applications including diffusion models (Peebles & Xie, 2023; Cao al., 2025d; Shen al., 2025), flow matching (Lipman et al., 2022: Liu et al., 2022b; Cao et al., 2025a), and GANs (Brock et al., 2019; Tran et al., 2019; Liu et al., 2022a). Beyond computer vision, there are also other ML applications that involve softmax computation, such as Hopfield networks (Karunanayake et al., 2023; Hu et al., 2024b;d;a; Wu et al., 2024b;a; Hu et al., 2025), graph neural networks (Veličković et al., 2018; Fu et al., 2021; Go et al., 2022; Chang et al., 2024), recommender systems (Kang & McAuley, 2018; Liu et al., 2023b; 2024b), and fairness problems (Corbett-Davies et al., 2023; Song et al., 2024a; Cao et al., 2025c).
22


Reviews:
[{"review_id": "acqnVtnlbW", "reviewer": "Reviewer_8u1R", "summary": "The paper derived orderwise tight upper and lower bounds on the sample complexity of hypothesis testing for softmax distributions (capturing the last layer output) and the leverage score distribution.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We express our deepest gratitude to the reviewer for the time and effort in reviewing our work. Below, we want to respond to the weaknesses and questions.\n\n**Response to Weakness 1**: We thank the reviewer for raising this important point. Our work intentionally focuses on single-layer softmax and leverage score models as a foundational step in the theory of binary hypothesis testing over these widely-used classes of distributions. The novelty of our contribution lies in formalizing and analyzing the binary hypothesis testing problem in these structured settings, which, to the best of our knowledge, has not been previously addressed in the literature.\n\nRegarding motivation, we highlight that both softmax and leverage score distributions arise naturally in machine learning and numerical linear algebra, but their sample complexity under hypothesis testing had remained unexplored. We clarify this explicitly in the introduction (Section 1) and further elaborate on the motivation from LLMs and self-attention mechanisms, where softmax distributions are central.\n\nAs for the extension to multiple layers of softmax, we agree that this is an important direction and appreciate the opportunity to clarify. In deep neural networks, softmax layers often appear at the output or in attention blocks. While our current theoretical framework addresses a single softmax layer parameterized by matrix $A$, multi-layer architectures can be viewed as compositions of functions, where only the final layer produces a distribution over outputs (which can be seen in Figure 1 of the famous “attention is all you need” paper https://arxiv.org/pdf/1706.03762). Therefore, the final softmax layer can still be abstracted and analyzed using our current hypothesis testing framework.\n\nIn the revised version of our paper, we plan to discuss this direction more explicitly and include formal remarks about the potential for generalization to multi-layer or multi-head softmax settings.\n\n**Response to Weakness 2**: Thank you very much for your insightful comments. Leverage scores are a central concept in numerical linear algebra, machine learning, and graph algorithms. As detailed in Section 1 and Section 4 of our paper, they appear in numerous algorithmic applications including matrix approximation (e.g., CUR decomposition), randomized linear algebra, graph sparsification, maximum flow and matching, and random spanning tree generation.\n\nIn all these applications, a leverage score distribution defines a probability distribution over data points, rows, or graph elements, used for randomized sampling or importance weighting. Given their probabilistic nature and sensitivity to the underlying data matrix, it is natural to ask whether two leverage score models correspond to the same or different underlying structures, particularly when the models are accessed as black boxes, which motivates our formulation of the binary hypothesis testing problem for leverage score distributions.\n\n**Response to Weakness 3**: The core novelty of our proofs lies in adapting classical binary hypothesis testing, typically studied in the context of generic distributions, to the structured, parameterized families of distributions induced by softmax and leverage score models. Unlike arbitrary distributions, these models produce distributions that are nonlinear functions of the input and matrix parameters, which poses unique analytical challenges.\n\nFor the softmax model, one key difficulty is that different parameter matrices $A$ and $B$ can induce indistinguishable distributions due to invariance under certain transformations (e.g., row shifts). To handle this, we introduce structural constraints (e.g.,$\\\\|A - B\\\\|\\_{2 \\to \\infty}$) and prove that the Hellinger distance between softmax outputs under constrained inputs governs the sample complexity. This leads to a tight upper and lower bound framework via careful analysis of the sensitivity of softmax distributions to perturbations in the parameter matrix.\n\nFor the leverage score model, the challenge is even greater due to the nonlinear matrix expressions involved, including matrix inversion and normalization, and the fact that the input sss is a vector that rescales rows of the matrix. We overcome this by establishing operator norm bounds and using perturbation theory to relate changes in the parameter matrix to changes in the output distribution. Our proof carefully propagates these changes through the matrix expressions and yields tight dependence on both the model difference $\\\\|A - B\\\\|$ and input constraints.\n\n**Response to the question**: Thank you very much for carefully checking this. We will fix this in the revised version of our paper.\n\nWe thank you again for your insightful comments.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "Looks correct.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "Softmax distributions are highly common in neural networks and the hypothesis testing of such distributions might be of interest.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "Strengths: The paper derived tight upper and lower bounds on sample complexity of hypothesis for softmax and leverage score distributions, respectively, which are interesting and solid results.\n\nWeaknesses: While both softmax and leverage score functions have many applications, it would be good to motivate more about the hypothesis testing on these two types of distributions. Also in neural networks, there can be multiple layers. How the analysis in the paper extends to multiple layers of softmax functions or how the single layer softmax fits in such cases.\n\nSimilarly for leverage score distributions. I am not familiar with the leverage score applications. Are there motivations for hypothesis testing for leverage score distributions?\n\nIn terms of proof techniques, is it possible to elaborate more on the challenge or novelty part of the proof?", "other_comments_or_suggestions": "Typo in \"retrieval argument generation (RAG)\" (should be \"augmented\")", "questions_for_authors": "See above.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "vf0uPLMKb6", "reviewer": "Reviewer_yyRt", "summary": "This paper studies binary hypothesis testing in the setting of softmax models and leverage score models. That is, quantifying the number of queries needed to identify an unknown distribution given two possible candidates. Some theoretical analysis shows the lower and upper bound for such problem.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We express our deepest gratitude to the reviewer for the time and effort in reviewing our work. Below, we want to respond to the weaknesses and questions.\n\n**Concern 1**: However, in the latter sections of the paper, the contents are not cycling back to the theme.\n\n**Answer**: We thank you very much for your insightful comments. In Sections 3 and 4, we study the distinguishability of models (softmax and leverage score based) through the lens of binary hypothesis testing, establishing tight sample complexity bounds. These results directly address the challenge of determining how much information (or how many queries) is needed to tell apart closely related models, a theoretical formulation aligned with understanding model \"abilities\" via limited parameter access.\nMoreover, our framework sets a path toward identifying distinguishable components of large models. For instance, showing that certain parameters contribute more significantly to distinguishability (via Hellinger distance bounds) offers insight into what might constitute an “ability region” within a model — aligning with the introductory motivation.\n\n**Concern 2**: In addition, the claim in the first page \"As we delve deeper .... self-attention\" needs reference to support.\n\n**Answer**: We completely agree with your comment. In the revised version of our paper, we will include the following citations:\n\n$\\bullet$ [1] introduced the Transformer model and the use of softmax in computing attention weights.\n\n$\\bullet$ [2] discussed variants and performance implications of softmax in attention computation.\n\n$\\bullet$ [3] and [4] directly analyze optimization on the softmax regression problem and show the impact of the softmax unit on self-attention and in-context learning.\n\n\n**Concern 3**: Authors study a softmax models and leverage score models which can be formulated as a matrix. However, it is not clear how the conclusions made on this single-layer model can be generalized to the LLM and transformer as a whole system.\n\n**Answer**: We thank you for your insightful comments and kindly refer you to our **Response to Weakness 1** to Reviewer 8u1R.\n\n\n**Concern 4**: The discussion on leverage scores appears forced and disconnected from the original motivation, aside from some vague remarks about their usefulness. While highlighting similarities may be valuable, the authors need to clarify how this perspective relates to the central question at hand.\n\n\n**Answer**: ​​Our primary motivation is to understand how model components, especially those arising in LLMs, can be distinguished via limited parameter sampling. While the softmax mechanism arises directly in self-attention, the leverage score model serves as a broader, more general abstraction of distributional behavior driven by matrix-parameterized functions, similar in form to softmax. Both softmax and leverage score models define distributions over outputs conditioned on structured inputs, and both are parameterized by matrices, making them amenable to a unified theoretical treatment through hypothesis testing.\nRather than being a disconnected addition, the leverage score model allows us to extend our analysis framework and highlight that the difficulty of distinguishing close models under sample constraints is not unique to softmax, but also arises in other distributional settings relevant to algorithms and data analysis. \n\nWe thank you again for your insightful comments.\n\n\n\n[1] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. \"Attention is all you need.\" NeurIPS’17.\n\n[2] Krzysztof Choromanski, Valerii Likhosherstov, David Dohan, Xingyou Song, Andreea Gane, Tamas Sarlos, Peter Hawkins et al. \"Rethinking attention with performers.\" ICLR’21.\n\n[3] Zhihang Li, Zhizhou Sha, Zhao Song, Mingda Wan. \"Attention scheme inspired softmax regression.\" ICLR’25 workshop.\n\n[4] Yeqi Gao, Zhao Song, and Junze Yin. \"An iterative algorithm for rescaled hyperbolic functions regression.\" AISTATS’25.", "claims_and_evidence": "1. In the introduction of the paper, authors claim that the paper is motivated by distinguish different ability parts of LLMs by limited parameters sampling. However, in the latter sections of the paper, the contents are not cycling back to the theme. \n\n2. In addition, the claim in the first page \"As we delve deeper .... self-attention\" needs reference to support. \n\n3. Authors study a softmax models and leverage score models which can be formulated as a matrix. However, it is not clear how the conclusions made on this single-layer model can be generalized to the LLM and transformer as a whole system. \n\n4. The discussion on leverage scores appears forced and disconnected from the original motivation, aside from some vague remarks about their usefulness. While highlighting similarities may be valuable, the authors need to clarify how this perspective relates to the central question at hand.", "methods_and_evaluation_criteria": "This paper is built based on theoretical analysis without any experiments.", "theoretical_claims": "Yes.", "experimental_designs_or_analyses": "No experiment included in this paper.", "relation_to_broader_scientific_literature": "This paper relates more to binary hypothesis testing. Although, in the introduction, authors try to connect this paper with LLMs, no clear analysis has been made in the rest parts.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "The paper presents no experiment to suggest the application scenario of the study, which significantly limit its influence for LLM/transformer community.", "other_comments_or_suggestions": "No", "questions_for_authors": "See above", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "b0Jl9UtUhq", "reviewer": "Reviewer_acsd", "summary": "The paper addresses the problem of binary hypothesis testing in the context of two important probabilistic models: softmax models and leverage score models. The main contributions and findings of the paper are as follows:\n\n- **Binary Hypothesis Testing for Softmax Models**: The authors study the fundamental problem of determining which one of two given softmax models is the true model, based on queries to the models. They establish that the sample complexity for this task is asymptotically $O(ϵ^{−2})$, where ϵ quantifies a specific distance between the parameters of the two models.\n  \n- **Connection to Leverage Score Models**: The paper draws an analogy between softmax models and leverage score models, which are widely used in algorithmic applications such as linear algebra and graph theory.\n  \n- **Binary Hypothesis Testing for Leverage Score Models**: The authors extend their analysis to leverage score models and derive similar results for binary hypothesis testing in this setting.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We express our deepest gratitude to the reviewer for the time and effort in reviewing our work. Below, we want to respond to the weaknesses and questions.\n\n**Concern 1**: The primary issue lies in the disconnect between the stated motivation—understanding large language models (LLMs) through the softmax attention mechanism—and the actual focus of the work, which is on sample complexity for binary hypothesis testing of softmax distributions.\n\n**Answer**: We thank you very much for your insightful comments. In Sections 3 and 4, we study the distinguishability of models (softmax and leverage score based) through the lens of binary hypothesis testing, establishing tight sample complexity bounds. These results directly address the challenge of determining how much information (or how many queries) is needed to tell apart closely related models, a theoretical formulation aligned with understanding model \"abilities\" via limited parameter access. Moreover, our framework sets a path toward identifying distinguishable components of large models. For instance, showing that certain parameters contribute more significantly to distinguishability (via Hellinger distance bounds) offers insight into what might constitute an “ability region” within a model, aligning with the introductory motivation.\n\nThank you very much for your help checking our typos, and we will fix them in the revised version of our paper.\n\n We thank you again for your insightful comments.", "claims_and_evidence": "The claims in the paper are generally supported by clear and convincing evidence, with rigorous mathematical derivations and proofs provided for the main results. The sample complexity bounds for both softmax and leverage score models are substantiated through formal theorems, such as Theorem 3.1 (general result for softmax models) and Theorem 4.1 (general result for leverage score models). Lower bounds (e.g., Theorem 3.2, Theorem 4.2) and upper bounds (e.g., Theorem 3.5, Theorem 4.3). Additionally, the analogy between softmax and leverage score models is well-motivated by their shared structural properties, and the energy constraints on inputs are justified to avoid trivial solutions.", "methods_and_evaluation_criteria": "The methods proposed in the paper are well-suited to the problem of binary hypothesis testing for softmax and leverage score models. The authors use mathematically rigorous frameworks, such as Hellinger distance, to define sample complexity bounds, ensuring theoretical soundness. The evaluation focuses on deriving tight lower and upper bounds for sample complexity, which are validated through formal proofs, demonstrating their relevance to distinguishing between parameterized models.", "theoretical_claims": "The paper provides rigorous proofs for its theoretical claims, particularly regarding the sample complexity of binary hypothesis testing for softmax and leverage score models. The main results, such as the asymptotic sample complexity bounds of $O(ϵ^{−2})$ and $Ω(ϵ^{−2})$, are supported by formal derivations using tools like Hellinger distance and variance-based metrics (e.g., Theorems 3.1, 3.2, 3.5 for softmax models and Theorems 4.1, 4.2, 4.3 for leverage score models).", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "The paper's key contributions are closely tied to broader scientific literature in machine learning, linear algebra, and statistical hypothesis testing. The analogy drawn between softmax models and leverage score models connects the work to established research in numerical linear algebra and graph theory, where leverage scores are widely used for tasks like graph sparsification, maximum matching, and optimization problems. The binary hypothesis testing framework leverages classical results in hypothesis testing extending these ideas to structured models like softmax and leverage scores.", "essential_references_not_discussed": "None", "other_strengths_and_weaknesses": "**Strengths:**\n\nThe paper demonstrates several strengths in terms of originality, significance, and clarity. The paper offers a novel theoretical framework for binary hypothesis testing in softmax and leverage score models. The authors provide detailed theoretical analysis, including tight bounds on sample complexity and rigorous proofs, which contribute to the significance of the work. Additionally, the analogy drawn between softmax and leverage score models bridges concepts from machine learning and linear algebra. The paper’s rigorous mathematical formulations highlights its originality and relevance.\n\n**Weakness**:\n\nThe paper has several weaknesses that limit its overall impact and coherence. The primary issue lies in the disconnect between the stated motivation—understanding large language models (LLMs) through the softmax attention mechanism—and the actual focus of the work, which is on sample complexity for binary hypothesis testing of softmax distributions. The analysis appears tangential to the original motivation, and the results are not tied back to improving theoretical or practical understanding of LLMs. The paper primarily focuses on asymptotic results without empirical validation, which limits its practical applicability. Additionally, the paper does not deeply explore connections to related work or practical advancements in LLMs. Similarly, the conclusions and future work primarily address hypothesis testing problems without exploring meaningful real-world applications or implications for LLMs. Finally, the paper’s structure could be improved.", "other_comments_or_suggestions": "- **Broader Context**: The discussion of related work is thorough but could better emphasize how this paper’s contributions differ from prior studies on hypothesis testing for machine learning models.\n  \n- **Typographical Errors**:\n  \n  - In Section 1, “Then a question arose:” is stylistically abrupt and could be rephrased for a smoother transition.\n  - Ensure proper formatting of references (e.g., missing publication in citations like “Brown et al., 2020;?”).", "questions_for_authors": "The questions for the authors are already addressed in the \"Weaknesses\" section.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper provides sample complexity bounds for hypothesis testing of softmax and leverage score distributions. The theoretical results look correct. While authors argue that these results are a step towards understanding power of different parts of language models, the reviewers were not convinced. Ultimately, the latter is a subjective belief but for topics that are not central to the conference, it is worthwhile to take into account the feedback of reviewers regarding relevance. Therefore, my recommendation is weak acceptance.
Decision: Accept (poster)