Binary Hypothesis Testing for Softmax Models and Leverage Score Models

## 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 ⁢ ( ϵ − 2 ) 𝑂 superscript italic-ϵ 2 O(\epsilon^{-2}) italic_O ( italic_ϵ start_POSTSUPERSCRIPT - 2 end_POSTSUPERSCRIPT ) where ϵ italic-ϵ \epsilon italic_ϵ is a certain distance between the parameters of the models. Furthermore, we draw 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 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.

## 1 Introduction

In transforming various aspects of people’s lives, Large Language 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 [], Adobe Photoshop, and Google’s Meena chatbot [], along with the GPT series and others [, , , , , , , , ]. These models, together with those built upon them, have demonstrated significant prowess across diverse fields.

The robustness and vitality of their development are attested to by the widespread integration of LLMs. In the realm of Natural Language Processing (NLP), evaluations by [, , , ] center around natural language understanding, while [, , , , ] delve into natural language generation. LLMs have found applications in diverse fields, including both social science and science [, , , ], medical applications [, ], and engineering [, , , ], showcasing their potent capabilities.

A consistent theme among these models is the adoption of the transformer architecture, a proven and highly efficient framework. The prevailing prevalence of models like ChatGPT [] further underscores the transformative impact of this architecture.

However, there is a crucial problem with large language models: their training 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) [, , ], as well as sparsity for large language models by identifying the ability domain in the model which are important in solving the problem above. Then a question arose.

Can we distinguish different ability parts of Large Language Models by limited parameters sampling?

We give an initial step to the question from the theoretical perspective. As we delve deeper into large language models, softmax mechanism plays an important role in the computation of self-attention. But how the self-attention mechanism works, why it dedicates a lot to impressive ability in large language models, and what role it plays is still undiscovered.

So in this work, we want to explore the mechanism of softmax distribution from a binary hypothesis testing 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 transformers [].

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 parameterized by a 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 as the generation of random spanning trees [], max-flow problems [, , , ], maximum matching [, ], and graph sparsification []. Many studies have delved into the deep exploration of leverage scores, showcasing their effectiveness in optimization tasks such as linear programming [, ], cutting-plane methods [, , ], semi-definite programming [], and the approximation of the John Ellipsoid []. 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 a 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. Our formal problem definition is now presented.

A softmax model is parameterized by a matrix $A\in\mathbb{R}^{n\times d}$, and denoted $\operatorname{\mathtt{SoftMax}}_{A}$. Given $x\in\mathbb{R}^{d}$, the model outputs an element $i\in[n]$ with probability
$p_{i}=\langle\exp(Ax),{\bf 1}_{n}\rangle^{-1}\exp(Ax)_{i}.$
In the binary hypothesis testing problem, we are given access to a softmax model which is either $\operatorname{\mathtt{SoftMax}}_{A}$ or $\operatorname{\mathtt{SoftMax}}_{B}$. We have query access to the model, that is, we can feed the model an input $x\in\mathbb{R}^{d}$, and it will produce an output. The goal is to determine whether the model is $\operatorname{\mathtt{SoftMax}}_{A}$ or $\operatorname{\mathtt{SoftMax}}_{B}$, using the fewest number of queries possible.

We can similarly define the question for leverage score models. A leverage score model is parameterized by a matrix $A\in\mathbb{R}^{n\times d}$, and denoted $\operatorname{\mathtt{Leverage}}_{A}$. Given input $s\in(\mathbb{R}\backslash 0)^{n}$, the model returns an element $i\in[n]$ with probability
$p_{i}=(A_{s}(A_{s}^{\top}A_{s})^{-1}A_{s}^{\top})_{i,i}/d,$
where $A_{s}=S^{-1}A$, and $S=\operatorname{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 now state informal versions of our main results.

###### Theorem 1.1 (Informal statement for softmax models) .

Consider the binary hypothesis testing problem with two softmax models $\operatorname{\mathtt{SoftMax}}_{A}$ and $\operatorname{\mathtt{SoftMax}}_{B}$.

(Lower bound) If $\|B-A\|_{2\to\infty}\leq\epsilon$, then any successful algorithm uses $\Omega(\epsilon^{-2})$ queries.

(Upper bound)
If $B=A+\epsilon M$ for some small $\epsilon$ then the hypothesis testing problem can be solved in $O(\epsilon^{-2}\nu)$ queries, where $\nu$ depends on $A$ and $M$.

See Theorem 3.2 and Theorem 3.5 for formal statements.

###### Theorem 1.2 (Informal statement for leverage score models) .

Consider the binary hypothesis testing problem with two leverage score models $\operatorname{\mathtt{Leverage}}_{A}$ and $\operatorname{\mathtt{Leverage}}_{B}$.

(Lower bound) If $\sum_{i\in[n]}\|B_{i,*}^{\top}B_{i,*}-A_{i,*}^{\top}A_{i,*}\|_{\operatorname{
op}}\leq\epsilon$, then any successful algorithm uses $\Omega(\epsilon^{-1})$ queries.

(Upper bound) If $B=A+\epsilon M$ for some small $\epsilon$ then the hypothesis testing problem can be solved in $O(\epsilon^{-2}\nu)$ queries, where $\nu$ depends on $A$ and $M$.

See Theorem 4.2 and Theorem 4.3 for formal statements.

###### Theorem 1.1 (Informal statement for softmax models) .

###### Theorem 1.2 (Informal statement for leverage score models) .

### 1.2 Related Work

#### Theoretical Large Language Models (LLMs)

Several investigations [, , , ] have concentrated on theoretical analyses concerning LLMs.

The algorithm presented by [], named ZO-BCD, introduces a novel approach characterized by advantageous overall query complexity and reduced computational complexity in each iteration. The work by [] introduces Sophia, a straightforward yet scalable second-order optimizer. Sophia demonstrates adaptability to curvature variations across different parameter regions, a 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.
Studies by [, , , , , ] investigate the knowledge and skills of LLMs.
In the realm of optimization for LLMs, [, , , ] have delved into this domain.

Demonstrating the effectiveness of pre-trained models in localizing knowledge within their feed-forward layers, both [] and [] contribute valuable insights to the field.
The exploration of distinct ”skill” neurons and their significance in soft prompt-tuning for language models is a central theme in the analysis conducted by [], building upon the groundwork laid out in a prior discussion by []. The activation of skill neurons and their correlation with the expression of relevant facts is a focal point in the research presented by [], particularly in the context of BERT. In contrast, the work of [] takes an entirely unsupervised approach, leveraging the internal activations of a language model to extract latent knowledge.
Lastly, the investigation by [] sheds light on the sparsity observed in feedforward activations of large trained transformers, uncovering noteworthy patterns in their behavior.
In addition to the above, [, , ] explore Zero-th order algorithms for LLMs.

#### Softmax Computation and Regression

Softmax computation, a crucial element in attention computation [], plays a pivotal role in the development of large language models. Several studies [, , , ] delve into the efficiency of softmax computation.

To improve computational efficiency, [] presents a quicker attention computation algorithm utilizing implicit matrices. Similarly, [] utilizes lazy updates to speed up dynamic computation, while [] employs a randomized algorithm for similar efficiency gains. Conversely, [] utilizes an approximate Newton method that operates in nearly linear time.

[] centers on the convergence of overparameterized two-layer networks with exponential activation functions, whereas [, ] explore regression analysis within the framework of attention computation. All of these studies specifically focus on softmax-based regression problems.

#### Leverage Scores

Given $A\in\mathbb{R}^{n\times d}$ and $i\in[n]$, $a_{i}$ represents the $i$-th row of matrix $A$. We use $\sigma_{i}(A)=a_{i}^{\top}(A^{\top}A)^{\dagger}a_{i}$ 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, leverage scores serve as fundamental tools.

In the context of matrices, both the tensor CURT decomposition [] and the matrix CUR decomposition [, , ] heavily rely on leverage scores. In optimization, areas such as linear programming [, ], the approximation of the John Ellipsoid [], cutting-plane methods [, , ], and semi-definite programming [] incorporate leverage scores.

Within graph theory applications, leverage scores play a crucial role in max-flow problems [, , , ], maximum matching [, ], graph sparsification [], and the generation of random spanning trees [].

Several studies, such as [, , ], focus on the approximation of leverage scores. Simultaneously, Lewis weights, serving as a generalization of leverage scores, are explored in depth by [, ].

#### Hypothesis Testing

Hypothesis testing is a central problem in statistics. In hypothesis testing, two (or more) hypotheses about the truth are given and an algorithm needs to distinguish which hypothesis is true.

The most classic testing problem is the binary hypothesis testing.
In this problem, two distributions $P_{0}$ and $P_{1}$ are given, and there is an unknown distribution $P$ which is either $P_{0}$ or $P_{1}$. The goal is to distinguish whether $P=P_{0}$ or $P=P_{1}$ by drawing samples from $P$. This problem is well-studied, with [] 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 distributions is given by $\Theta(H^{-2}(P_{0},P_{1}))$, where $H$ denotes the Hellinger distance, see e.g., [].

There are other important kinds of hypothesis testing problems. In the goodness-of-fit testing problem, a distribution $Q$ is given, and there is an unknown distribution $P$ which is known to be either equal to $Q$ or 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 it 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 $P$ and $Q$.
For these problems there are no simple general characterization as in the binary hypothesis testing. However, for reasonable classes of distributions such as Gaussian distributions or distributions on discrete spaces, a lot of nice results are known [, , , , , , ].

We are not aware of any previous work that study hypothesis testing problems for the class of softmax models or leverage score models.

### 1.3 Roadmap

In Section 2, we introduce notations, basic definitions, and concepts relevant to information theory and hypothesis testing. Our results are presented in Section 3 and Section 4. Specifically, Section 3 establishes upper and lower bounds on the sample complexity for distinguishing two different softmax models, while Section 4 delves into the case of leverage scores. We conclude and make further discussions in Section 5.

## 2 Preliminaries

#### Notations

Given $x\in\mathbb{R}^{n}$, we use $\|x\|_{p}$ to denote $\ell_{p}$ norm of $x$, where $\|x\|_{0}=\sum_{i=1}^{n}\mathbbm{1}(x_{i}\neq 0)$, $\|x\|_{1}:=\sum_{i=1}^{n}|x_{i}|$ ($\ell_{1}$ norm), $\|x\|_{2}:=(\sum_{i=1}^{n}x_{i}^{2})^{1/2}$ ($\ell_{2}$ norm), and $\|x\|_{\infty}:=\max_{i\in[n]}|x_{i}|$ ($\ell_{\infty}$ norm). For a square matrix, $\operatorname{tr}[A]$ is used to represent the trace of $A$.
Given $1\leq p\leq\infty$ and $1\leq q\leq\infty$, $\|A\|_{p\to q}$ represents the $p$-to-$q$ operator norm

$$ $\displaystyle\|A\|_{p\to q}=\sup_{x:\|x\|_{p}\leq 1}\|Ax\|_{q}.$ $$

In particular, $\|A\|_{2\to\infty}=\max_{i\in[n]}\|A_{i,*}\|_{2}$.
For $x\in\mathbb{R}^{n}$, let $\operatorname{Diag}(x)\in\mathbb{R}^{n\times n}$ denote the diagonal matrix with diagonal $x$.
For square matrix $A\in\mathbb{R}^{n\times n}$, let $\operatorname{diag}(A)\in\mathbb{R}^{n}$ denote the diagonal of $A$.
For a non-negative integer $n$, let $[n]$ denote the set $\{1,\ldots,n\}$.
For a sequence $X_{1},\ldots,X_{m}$ of random variables, we use $X^{m}$ to denote the whole sequence $(X_{1},\ldots,X_{m})$.

### 2.1 Information Theory

###### Definition 2.1 (TV distance) .

For two distribution $P,Q$ on the same measurable space, their total variation (TV) distance is

$$ $\displaystyle\operatorname{TV}(P,Q)=\frac{1}{2}\int\left|P(\mathrm{d}x)-Q( \mathrm{d}x)\right|.$ $$

In particular, if $P$ and $Q$ are on the discrete space $[n]$ and $P=(p_{1},\ldots,p_{n})$, $Q=(q_{1},\ldots,q_{n})$, then

$$ $\displaystyle\operatorname{TV}(P,Q))=\frac{1}{2}\sum_{i=1}^{n}|p_{i}-q_{i}|.$ $$

###### Definition 2.2 (Hellinger distance) .

For two distributions $P,Q$ on the same measurable space, their squared Hellinger distance is

$$ $\displaystyle H^{2}(P,Q)=\frac{1}{2}\int(\sqrt{P(\mathrm{d}x)}-\sqrt{Q(\mathrm {d}x)})^{2}.$ $$

In particular, if $P$ and $Q$ are on the discrete space $[n]$ and $P=(p_{1},\ldots,p_{n})$, $Q=(q_{1},\ldots,q_{n})$, then

$$ $\displaystyle H^{2}(P,Q)=\frac{1}{2}\sum_{i=1}^{n}(\sqrt{p_{i}}-\sqrt{q_{i}})^ {2}=1-\sum_{i=1}^{n}\sqrt{p_{i}q_{i}}.$ $$

The Hellinger distance $H(P,Q)$ is the square root of the squared Hellinger distance $H^{2}(P,Q)$.

We recall the following relationship between the Hellinger distance and the TV distance. For any distributions $P,Q$ on the same space, we have

$$ $\displaystyle H^{2}(P,Q)\leq\operatorname{TV}(P,Q)\leq\sqrt{2}H(P,Q).$ $$

###### Definition 2.3 (Expectation and variance) .

Let $P$ be a distribution on a measurable space $\cal X$ and $f$ be a continuous function on $\cal X$. Then $\operatorname*{{\mathbb{E}}}_{P}[f]$ is the expectation of $f$ under $P$ and $\operatorname{Var}_{P}(f)$ is the variance of $f$ under $P$.

In particular, if ${\cal X}=[n]$, $P=(p_{1},\ldots,p_{n})\in\mathbb{R}^{n}$, and $x\in\mathbb{R}^{n}$, then

$$ $\displaystyle\operatorname*{{\mathbb{E}}}_{P}[x]$ $\displaystyle=\sum_{i=1}^{n}p_{i}x_{i},$ $\displaystyle\operatorname{Var}_{P}(x)$ $\displaystyle=\sum_{i=1}^{n}p_{i}(x-\operatorname*{{\mathbb{E}}}_{P}[x])^{2}.$ $$

###### Definition 2.1 (TV distance) .

###### Definition 2.2 (Hellinger distance) .

###### Definition 2.3 (Expectation and variance) .

### 2.2 Hypothesis Testing

We review the classic hypothesis testing problem for distributions.

###### Definition 2.4 (Binary hypothesis testing for distributions) .

Let $P_{0},P_{1}$ be two distributions on the same space.
We have sample access to a distribution $P$, which is known to be either $P_{0}$ or $P_{1}$.
The goal is to determine whether $P=P_{0}$ or $P=P_{1}$, using as few samples as possible.
We say an algorithm successfully distinguishes $P_{0}$ and $P_{1}$ is at least $2/3$ under both hypotheses.

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 success probability $\delta>\frac{1}{2}$, then we can run it independently a constant number of times and take the majority of the outputs. In this way we can boost the success probability to an arbitrarily 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.

###### Lemma 2.5 (e.g., [ 62 ] ) .

The sample complexity of the binary hypothesis testing problem for distributions is $\Theta(H^{-2}(P_{0},P_{1}))$. That is, there is an algorithm that solves the problem using $O(H^{-2}(P_{0},P_{1}))$ queries, and any algorithm that solves the problem uses $\Omega(H^{-2}(P_{0},P_{1}))$ queries.

###### Definition 2.4 (Binary hypothesis testing for distributions) .

###### Lemma 2.5 (e.g., [ 62 ] ) .

### 2.3 Softmax Model

###### Definition 2.6 (Softmax model) .

The *softmax model* $\operatorname{\mathtt{SoftMax}}_{A}$ associated with $A\in\mathbb{R}^{n\times d}$ is a model such that on input $x\in\mathbb{R}^{d}$, it outputs a sample $y\in[n]$ from the distribution $\operatorname{\mathtt{SoftMax}}_{A}(x)$, defined as follows: the probability mass of $i\in[n]$ is equal to $\langle\exp(Ax),{\bf 1}_{n}\rangle^{-1}\exp(Ax)_{i}$.

We can verify that $\sum_{i=1}^{n}\langle\exp(Ax),{\bf 1}_{n}\rangle^{-1}\exp(Ax)_{i}=1$, so the above definition gives a valid distribution.

###### Definition 2.7 (Binary hypothesis testing for softmax models) .

Let $A,B\in\mathbb{R}^{n\times d}$ be two matrices.
Let $P_{0}=\operatorname{\mathtt{SoftMax}}_{A},P_{1}=\operatorname{\mathtt{SoftMax}
}_{B}$ be two softmax models.
Let $P$ be the softmax model which is either $P_{0}$ or $P_{1}$.
In each query, we can feed $x\in\mathbb{R}^{d}$ into $P$, and retrieve a sample $y\in[n]$ from $P(x)$.
The goal is to determine whether the model $P$ is $P_{0}$ or $P_{1}$ in as few samples as possible.
We say an algorithm successfully distinguishes $P_{0}$ and $P_{1}$, if the correctness probability is at least $2/3$ under both hypotheses.

The above definition is valid. However, if we make no restrictions on the input $x$, then there would be undesirable consequences. For example, suppose $n=2$, $d=1$, $A=\begin{bmatrix}\epsilon\\
0\end{bmatrix}$, $B=\begin{bmatrix}0\\
\epsilon\end{bmatrix}$ for some very small $\epsilon>0$. Because $A$ and $B$ are close to each other, we should expect it to be difficult to distinguish $\operatorname{\mathtt{SoftMax}}_{A}$ and $\operatorname{\mathtt{SoftMax}}_{B}$. However, if we allow any $x\in\mathbb{R}^{d}$ as input, then we could take $x$ to be a very large real number. Then $\operatorname{\mathtt{SoftMax}}_{A}(x)$ has almost all mass on $1\in[n]$, while $\operatorname{\mathtt{SoftMax}}_{B}(x)$ has almost all mass on $2\in[n]$, and we can distinguish the two models using only one query. To avoid this peculiarity, we make the assumption that there is an energy constraint on $x$.

###### Definition 2.8 (Energy constraint for softmax model) .

We assume that there is an *energy constraint*, that is, input $x\in\mathbb{R}^{n}$ should satisfy $\|x\|_{2}\leq E$, for some given constant $E$.

The energy constraint is a reasonable assumption in the context of LLMs and more generally neural networks, because of the widely used batch normalization technique [].

###### Definition 2.6 (Softmax model) .

###### Definition 2.7 (Binary hypothesis testing for softmax models) .

###### Definition 2.8 (Energy constraint for softmax model) .

### 2.4 Leverage Score Model

###### Definition 2.9 (Leverage score model) .

The *leverage score model* $\operatorname{\mathtt{Leverage}}_{A}$ associated with $A\in\mathbb{R}^{n\times d}$ is a model such that on input $s\in(\mathbb{R}\backslash 0)^{n}$, it outputs a sample $y\in[n]$ from the distribution $\operatorname{\mathtt{Leverage}}_{A}(s)$, defined as follows: the probability mass of $i\in[n]$ is equal to

$$ $\displaystyle\|(A_{s}^{\top}A_{s})^{-1/2}(A_{s})_{*,i}\|_{2}^{2}/d=(A_{s}(A_{s }^{\top}A_{s})^{-1}A_{s}^{\top})_{i,i}/d,$ $$

where $A_{s}=S^{-1}A$, and $S=\operatorname{Diag}(s)$.

###### Definition 2.10 (Binary hypothesis testing for leverage score model) .

Let $A,B\in\mathbb{R}^{n\times d}$ be two matrices.
Let $P_{0}=\operatorname{\mathtt{Leverage}}_{A}$, $P_{1}=\operatorname{\mathtt{Leverage}}_{B}$ be two leverage score models.
Let $P$ be the leverage score model which is either $P_{0}$ or $P_{1}$.
In each query, we can feed $s\in(\mathbb{R}\backslash 0)^{n}$ into $P$, and retrieve a sample $y\in[n]$ from $P(s)$.
The goal is to determine whether the model $P$ is $P_{0}$ or $P_{1}$ in as few samples as possible.
We say an algorithm successfully distinguishes $P_{0}$ and $P_{1}$, if the correctness probability is at least $2/3$ under both hypotheses.

Similar to the softmax model case, if we do not put any restrictions on $s$, then there will be certain weird behavior. For example, if we take $n=2$, $d=1$, $A=\begin{bmatrix}1\\
0\end{bmatrix}$ and $B=\begin{bmatrix}1\\
\epsilon\end{bmatrix}$ for some small $\epsilon>0$. Because $A$ and $B$ are close to each other, we should expect it to be difficult to distinguish $\operatorname{\mathtt{Leverage}}_{A}$ and $\operatorname{\mathtt{Leverage}}_{B}$. However, if we allow any $s\in(\mathbb{R}\backslash 0)^{n}$ as input, then we can take $s=\begin{bmatrix}1&\delta\end{bmatrix}$ for some very small $\delta>0$. In this way, we can verify that $\operatorname{\mathtt{Leverage}}_{A}(s)$ has all mass on $1\in[n]$, while $\operatorname{\mathtt{Leverage}}_{B}(s)$ has almost all mass on $2\in[n]$. So we can distinguish the two models using only one query. To avoid such cases we put additional constraints on $s$.

###### Definition 2.11 (Constraint for leverage score model) .

We assume that input $s\in(\mathbb{R}\backslash 0)^{d}$ should satisfy the constraint such that $c\leq s_{i}^{2}\leq C$ for some given constants $0<c<C$.

###### Definition 2.9 (Leverage score model) .

###### Definition 2.10 (Binary hypothesis testing for leverage score model) .

###### Definition 2.11 (Constraint for leverage score model) .

## 3 Softmax Model

### 3.1 General Result

We first prove a general result which relates the binary hypothesis testing problem with Hellinger distance.

###### Theorem 3.1 .

Let $A,B\in\mathbb{R}^{n\times d}$ be two matrices. Consider the binary hypothesis testing problem of distinguishing $\operatorname{\mathtt{SoftMax}}_{A}$ and $\operatorname{\mathtt{SoftMax}}_{B}$ using energy-constrained queries (Definition 2.8).
Define $\delta=\sup_{x:\|x\|_{2}\leq E}H(\operatorname{\mathtt{SoftMax}}_{A}(x),
\operatorname{\mathtt{SoftMax}}_{B}(x))$.
Then the sample complexity of the binary hypothesis testing problem is $\Theta(\delta^{-2})$.
That is, there is an algorithm that successfully solves the problem using $O(\delta^{-2})$ energy-constrained queries, and any algorithm that successfully solves the problem uses $\Omega(\delta^{-2})$ energy-constrained queries.

Proof of Theorem 3.1 is deferred to Appendix A.1.

###### Theorem 3.1 .

### 3.2 Lower Bound

The goal of this section is to prove the following lower bound for binary hypothesis testing for softmax models.

###### Theorem 3.2 (Lower bound) .

If two softmax models (Definition 2.6)
with parameters $A\in\mathbb{R}^{n\times d}$ and $B\in\mathbb{R}^{n\times d}$ satisfy $\|A-B\|_{2\to\infty}\leq\epsilon$ (i.e., $\max_{j\in[n]}\|A_{j,*}-B_{j,*}\|_{2}\leq\epsilon$), then any algorithm with energy constraint $E$ that distinguishes the two models with success probability $\geq\frac{2}{3}$ uses at least $\Omega(\epsilon^{-2}E^{-2})$ samples.

Before giving the proof of Theorem 3.2, we state a useful lemma.

###### Lemma 3.3 .

Let $a,b\in\mathbb{R}^{n}$ be such that $\|a-b\|_{\infty}\leq\epsilon$.
Let $P$ be the distribution on $[n]$ with $p_{i}=\exp(a_{i})/\langle\exp(a),{\bf 1}_{n}\rangle$.
Let $Q$ be the distribution on $[n]$ with $q_{i}=\exp(b_{i})/\langle\exp(b),{\bf 1}_{n}\rangle$.
Then

$$ $\displaystyle H^{2}(P,Q)$ $\displaystyle=O(\epsilon^{2})$ $\displaystyle\operatorname{TV}(P,Q)$ $\displaystyle=O(\epsilon).$ $$

Proof of Lemma 3.3 is deferred to Appendix A.2.

###### Corollary 3.4 .

If matrices $A\in\mathbb{R}^{n\times d},B\in\mathbb{R}^{n\times d}$ satisfy $\max_{j\in[n]}\|A_{j,*}-B_{j,*}\|_{2}\leq\epsilon$, then for any $x\in\mathbb{R}^{d}$, the distributions $P=\operatorname{\mathtt{SoftMax}}_{A}(x)$ and $Q=\operatorname{\mathtt{SoftMax}}_{B}(x)$ satisfy

$$ $\displaystyle H^{2}(P,Q)$ $\displaystyle=O(\epsilon^{2}\|x\|_{2}^{2}),$ $\displaystyle\operatorname{TV}(P,Q)$ $\displaystyle=O(\epsilon\|x\|_{2}).$ $$

###### Proof.

For any $x\in\mathbb{R}^{n}$, we have

$$ $\displaystyle\|Ax-Bx\|_{\infty}=$ $\displaystyle~{}\max_{j\in[n]}|A_{j,*}x-B_{j,*}x|$ $\displaystyle\leq$ $\displaystyle~{}\max_{h\in[n]}\|A_{j,*}-B_{j,*}\|_{2}\|x\|_{2}$ $\displaystyle\leq$ $\displaystyle~{}\epsilon\|x\|_{2}.$ $$

The result then follows from Lemma 3.3.
∎

###### Proof of Theorem 3.2 .

By Corollary 3.4, for any $\|x\|_{2}\leq E$, we have $H^{2}(\operatorname{\mathtt{SoftMax}}_{A}(x),\operatorname{\mathtt{SoftMax}}_{
B}(x))=O(\epsilon^{2}E^{2})$.
Therefore $\delta$ in the statement of Theorem 3.1 satisfies $\delta^{2}=O(\epsilon^{2}E^{2})$.
Applying Theorem 3.1 we finish the proof.
∎

###### Theorem 3.2 (Lower bound) .

###### Lemma 3.3 .

###### Corollary 3.4 .

###### Proof.

###### Proof of Theorem 3.2 .

### 3.3 Upper Bound

In the previous section we established an $\Omega(\epsilon^{-2})$ 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\in\mathbb{R}^{n\times d}$ be parameters of the softmax models, $x\in\mathbb{R}^{d}$ be the input vector, $P=\operatorname{\mathtt{SoftMax}}_{A}(x)=(p_{1},\ldots,p_{n})$, $Q=\operatorname{\mathtt{SoftMax}}_{B}(x)=(q_{1},\ldots,q_{n})$.

Firstly, two different matrices $A$ and $B$ could give rise to the same softmax model. If $B=A+{\bf 1}_{n}^{\top}w$ for some $w\in\mathbb{R}^{d}$, then for any $x\in\mathbb{R}^{d}$, we have

$$ $\displaystyle q_{i}=$ $\displaystyle~{}\frac{\exp(Bx)_{i}}{\langle\exp(Bx),{\bf 1}_{n}\rangle}$ $\displaystyle=$ $\displaystyle~{}\frac{\exp(Ax)_{i}\exp(w^{\top}x)}{\langle\exp(Ax)\exp(w^{\top }x),{\bf 1}_{n}\rangle}$ $\displaystyle=$ $\displaystyle~{}\frac{\exp(Ax)_{i}}{\langle\exp(Ax),{\bf 1}_{n}\rangle}$ $\displaystyle=$ $\displaystyle~{}p_{i}$ $$

for all $i\in[d]$. Therefore in this case $\operatorname{\mathtt{SoftMax}}_{A}(x)=\operatorname{\mathtt{SoftMax}}_{B}(x)$ for all $x\in\mathbb{R}^{d}$ and it is impossible to distinguish the two models.
This issue may be resolved by adding additional assumptions such as ${\bf 1}_{n}^{\top}A={\bf 1}_{n}^{\top}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\in\mathbb{R}^{d}$, the distribution $\operatorname{\mathtt{SoftMax}}_{A}(x)$ is the uniform distribution on $[d]$.
If $\|B_{1,*}-A_{1,*}\|_{2}=\epsilon$, then for any $x$ with $\|x\|_{2}\leq E$, we have

$$ $\displaystyle\exp(-\epsilon E)\leq\frac{\exp(Bx)_{1}}{\exp(Ax)_{1}}\leq\exp( \epsilon E).$ $$

A simple calculation shows that in this case,

$$ $\displaystyle H^{2}(P,Q)=O(\epsilon^{2}E^{2}/n).$ $$

So the sample complexity of any hypothesis testing algorithm is at least $\Omega(n/(\epsilon^{2}E^{2}))$, which grows with $n$.
This shows that the sample complexity may depend on $n$.

Nevertheless, 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 $\operatorname{\mathtt{SoftMax}}_{A}$ and $\operatorname{\mathtt{SoftMax}}_{A+\epsilon M}$ using $O(\epsilon^{-2})$ queries, for small enough $\epsilon>0$.

###### Theorem 3.5 .

Fix $A,M\in\mathbb{R}^{n\times d}$ where $\|M\|_{2\to\infty}=O(1)$.
For $\epsilon>0$, define $B_{\epsilon}=A+\epsilon M$.
We consider the binary hypothesis testing problem with $\operatorname{\mathtt{SoftMax}}_{A}$ and $\operatorname{\mathtt{SoftMax}}_{B_{\epsilon}}$, for small $\epsilon$.
Let $\nu=\sup_{x:\|x\|_{2}\leq E}\operatorname{Var}_{\operatorname{\mathtt{SoftMax}
}_{A}(x)}(Mx)$. Then for $\epsilon>0$ small enough, there is an algorithm that uses $O(\epsilon^{-2}\nu^{-1})$ energy-constrained queries and distinguishes between $\operatorname{\mathtt{SoftMax}}_{A}$ and $\operatorname{\mathtt{SoftMax}}_{B_{\epsilon}}$.

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 $\nu=\sup_{x:\|x\|_{2}\leq E}\operatorname{Var}_{\operatorname{\mathtt{SoftMax}
}_{A}(x)}(Mx)$ for fixed $A,M\in\mathbb{R}^{n\times d}$. For different $A$ and $M$ the value of $\nu$ can be quite different. For example, if $A$ is the all zero matrix and $M$ is zero except for row $1$ (and $\|M\|_{2\to\infty}=O(1)$), then $\nu=O(E^{2}/n)$ for any $\|x\|_{2}\leq E$.

On the other hand, if $A$ is the zero matrix, and the first column $M$ are i.i.d. Gaussian $\mathcal{N}(0,\Theta(1))$, then with high probability, $\nu=\Omega(E^{2})$ for $x=(E,0,\ldots,0)$.

We remark that Theorem 3.5 is in fact tight. We have a matching lower bound.

###### Theorem 3.6 .

Work under the same setting as Theorem 3.5.
For $\epsilon>0$ small enough, any algorithm that distinguishes between $\operatorname{\mathtt{SoftMax}}_{A}$ and $\operatorname{\mathtt{SoftMax}}_{B_{\epsilon}}$ must use $\Omega(\epsilon^{-2}\nu^{-1})$ energy-constrained queries.

###### Proof.

The proof is by combining the proof of Theorem 3.5 and Theorem 3.1. We omit the details.
∎

###### Theorem 3.5 .

###### Theorem 3.6 .

###### Proof.

## 4 Leverage Score Model

### 4.1 General Result

We first prove a general result which is the leverage score version of Theorem 3.1.

###### Theorem 4.1 .

Let $A,B\in\mathbb{R}^{n\times d}$ be two matrices. Consider the binary hypothesis testing problem of distinguishing $\operatorname{\mathtt{Leverage}}_{A}$ and $\operatorname{\mathtt{Leverage}}_{B}$ using constrained queries (Definition 2.11).
Define $\delta=\sup_{s:c\leq s_{i}^{2}\leq C\forall i}H(\operatorname{\mathtt{Leverage
}}_{A}(s),\operatorname{\mathtt{Leverage}}_{B}(s))$.
Then the sample complexity of the binary hypothesis testing problem is $\Theta(\delta^{-2})$.
That is, there is an algorithm that successfully solves the problem using $O(\delta^{-2})$ energy-constrained queries, and any algorithm that successfully solves the problem uses $\Omega(\delta^{-2})$ energy-constrained queries.

###### Proof.

The proof is similar to Theorem 3.1 and omitted.
∎

###### Theorem 4.1 .

###### Proof.

### 4.2 Lower Bound

The goal of this section is to prove the following lower bound for binary hypothesis testing for leverage score models.

###### Theorem 4.2 .

Consider two leverage score model $\operatorname{\mathtt{Leverage}}_{A}$ and $\operatorname{\mathtt{Leverage}}_{B}$.
Assume that there exists $\delta>0$ such that $A^{\top}A\succeq\delta I$.
If

$$ $\displaystyle\sum_{i\in[n]}\|B_{i,*}^{\top}B_{i,*}-A_{i,*}^{\top}A_{i,*}\|_{ \operatorname{op}}\leq\epsilon$ $$

(where $\|\cdot\|_{\operatorname{op}}$ denotes the $2$-to-$2$ operator norm), then any algorithm that solves the binary hypothesis testing problem takes at least $\Omega(c\delta/(C\epsilon))$ constrained queries.

###### Proof.

Let $P=\operatorname{\mathtt{Leverage}}_{A}(s)=(p_{1},\ldots,p_{n})$ and $Q=\operatorname{\mathtt{Leverage}}_{B}(s)=(q_{1},\ldots,q_{n})$.

By Theorem 4.1, it suffices to prove that $H^{2}(P,Q)=O(\epsilon C/(c\delta))$.

We first consider the case where $A$ and $B$ differ in exactly one row $i$.
Fix $s\in\mathbb{R}^{d}$ with $c\leq s_{j}\leq C$ for all $j\in[n]$.

Let $A_{s}=S^{-1}A$ and $B_{s}=S^{-1}B$, where $S=\operatorname{Diag}(s)$.

Because $A^{\top}A\succeq\delta I$, we have

$$ $\displaystyle A_{s}^{\top}A_{s}\succeq(\delta/C)\cdot I.$ $$

Because $\|B_{i,*}^{\top}B_{i,*}-A_{i,*}^{\top}A_{i,*}\|_{\operatorname{op}}\leq\epsilon$, we have

$$ $\displaystyle-\epsilon_{i}C/\delta A_{s}^{\top}A_{s}\preceq B_{i,*}^{\top}B_{i ,*}-A_{i,*}^{\top}A_{i,*}\preceq\epsilon_{i}C/\delta A_{s}^{\top}A_{s}.$ $$

Recall that $A$ and $B$ differ in exactly one row $i$. Therefore

$$ $\displaystyle(1-\frac{\epsilon C}{c\delta})A_{s}^{\top}A_{s}\preceq B_{s}^{ \top}B_{s}\preceq(1+\frac{\epsilon C}{c\delta})A_{s}^{\top}A_{s}.$ (1) $$

For $j\neq i$, we have

$$ $\displaystyle q_{j}$ $\displaystyle=s_{j}^{-2}B_{j,*}(B_{s}^{\top}B_{s})^{-1}(B^{\top})_{*,j}/d$ $\displaystyle=\operatorname{tr}[s_{j}^{-2}(B^{\top})_{*,j}B_{j,*}(B_{s}^{\top} B_{s})^{-1}]/d$ $\displaystyle=(1\pm O(\epsilon C/(c\delta)))\operatorname{tr}[s_{j}^{-2}A_{j,* }^{\top}A_{j,*}(A_{s}^{\top}A_{s})^{-1}]/d$ $\displaystyle=(1\pm O(\epsilon C/(c\delta)))p_{j},$ (2) $$

where the first step is 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.

Upper bound for $\operatorname{TV}$.
For the TV distance, we have

$$ $\displaystyle\operatorname{TV}(P,Q)$ $\displaystyle=\frac{1}{2}\sum_{j=1}^{n}|p_{j}-q_{j}|\leq\sum_{j\neq i}|p_{j}-q _{j}|$ $\displaystyle\leq\sum_{j\neq i}O(\epsilon C/(c\delta))p_{i}\leq O(\epsilon C/( c\delta)).$ $$

where the first step is by definition of TV distance, the third step is by Eq. (4.2).
Therefore $\operatorname{TV}(P,Q)\leq O(\epsilon C/(c\delta))$.

Upper bound for $H^{2}(P,Q)$.

Using

$$ $\displaystyle H^{2}(P,Q)\leq\operatorname{TV}(P,Q)$ $$

we also get

$$ $\displaystyle H^{2}(P,Q)\leq O(\epsilon C/(c\delta)).$ $$

Now we have established the result when $A$ and $B$ differ in exactly one row. Let us now consider general case.

If $\epsilon\geq 0.1\delta$, then $c\delta/(C\epsilon)=O(1)$ and there is nothing to prove. In the following, assume that $\epsilon\leq 0.1\delta$.

For $0\leq k\leq n$, define $B^{k}\in\mathbb{R}^{n\times d}$ be the matrix with $B^{k}_{i,*}=B_{i,*}$ for $i\leq k$ and $B^{k}_{i,*}=A_{i,*}$ for $i\geq k$.
Then $B^{0}=A$, $B^{n}=B$, and $B^{k}$ and $B^{k+1}$ differ exactly in one row.
Let $\epsilon_{i}=\|B_{i,*}^{\top}B_{i,*}-A_{i,*}^{\top}A_{i,*}\|_{\operatorname{op}}$.
Then by the above discussion, we have

$$ $\displaystyle~{}\operatorname{TV}(\operatorname{\mathtt{Leverage}}_{B^{k}}(s), \operatorname{\mathtt{Leverage}}_{B^{k+1}}(s))$ $\displaystyle=$ $\displaystyle~{}O(\epsilon_{k}C/(c\delta))$ $$

for all $0\leq k\leq n-1$.
By metric property of $\operatorname{TV}$, we have

$$ $\displaystyle~{}\operatorname{TV}(P,Q)$ $\displaystyle\leq$ $\displaystyle~{}\sum_{0\leq k\leq n-1}\operatorname{TV}(\operatorname{\mathtt{ Leverage}}_{B^{k}}(s),\operatorname{\mathtt{Leverage}}_{B^{k+1}}(s))$ $\displaystyle=$ $\displaystyle~{}\sum_{0\leq k\leq n-1}O(\epsilon_{i}C/(c\delta))$ $\displaystyle=$ $\displaystyle~{}O(\epsilon C/(c\delta)).$ $$

Using $H^{2}(P,Q)\leq\operatorname{TV}(P,Q)$ we also get $H^{2}(P,Q)=O(\epsilon C/(c\delta))$. This finishes the proof.
∎

In Theorem 4.2, the bound has linear dependence in $\epsilon^{-1}$. An interesting question is the improve the bound to quadratic dependence $\epsilon^{-2}$.

###### Theorem 4.2 .

###### Proof.

### 4.3 Upper Bound

Let $A,B\in\mathbb{R}^{n\times d}$ be parameters of the leverage score models, $s\in\mathbb{R}^{n}$ be the input vector, $P=\operatorname{\mathtt{Leverage}}_{A}(s)=(p_{1},\ldots,p_{n})$, $Q=\operatorname{\mathtt{Leverage}}_{B}(s)=(q_{1},\ldots,q_{n})$.

For upper bounds for the leverage score model, we run into similar difficulties as for the softmax model.
Firstly, different matrices $A$ and $B$ could give rise to the same leverage score model. If $B=AR$ for some invertible matrix $R\in\mathbb{R}^{d\times d}$, then we have

$$ $\displaystyle q_{i}$ $\displaystyle=(B_{s}(B_{s}^{\top}B_{s})^{-1}B_{s}^{\top})_{i,i}/d$ $\displaystyle=(A_{s}R(R^{\top}A_{s}^{\top}A_{s}R)^{-1}R^{\top}A_{s}^{\top})_{i ,i}/d$ $\displaystyle=(A_{s}(A_{s}^{\top}A_{s})^{-1}A_{s}^{\top})_{i,i}/d=p_{i}.$ $$

Then $\operatorname{\mathtt{Leverage}}_{A}(s)=\operatorname{\mathtt{Leverage}}_{B}(s)$ for all $s\in(\mathbb{R}\backslash 0)^{n}$ and it is impossible to distinguish the two models.

Furthermore, there exist scenarios where $A$ and $B$ differ only in rows with very small probability weight under any input $s$.
We now give an example where $\|A_{1,*}^{\top}A_{1,*}-B_{1,*}^{\top}B_{1,*}\|=\Omega(1)$ but $\operatorname{TV}(\operatorname{\mathtt{Leverage}}_{A}(s),\operatorname{
\mathtt{Leverage}}_{B}(s))=O(1/n)$ for any $s$ satisfying $c\leq s_{i}^{2}\leq C$ for all $i\in[n]$.
Suppose $A=\begin{bmatrix}I_{d}&e_{1}&\cdots&e_{1}\end{bmatrix}^{\top}$ (that is, the first $d$ rows of $A$ is equal to $I_{d}$, and all remaining rows are equal to $e_{1}^{\top}=(1,0,\ldots,0)$).
Then for $s$ satisfying $c\leq s_{i}^{2}\leq C$ for all $i\in[n]$, the distribution $P=\operatorname{\mathtt{Leverage}}_{A}(s)$ has probability mass $O(1/n)$ on every element $i\in\{1,d+1,d+2\ldots,n\}$ (hiding constants depending on $c$ and $C$).
Now suppose $B$ differs with $A$ only in the first entry $(1,1)$, and $B_{1,1}=A_{1,1}+\Theta(1)$.
Then for fixed $s$, $q_{j}=p_{j}$ for $j\in\{2,\ldots,d\}$, $q_{1}\geq p_{1}$, and $q_{j}\leq p_{j}$ for $j\in\{d+1,\ldots,n\}$.
So
$H^{2}(P,Q)\leq\operatorname{TV}(P,Q)=q_{1}-p_{1}=\Theta(1/n)$.

This shows that the sample complexity may depend on $n$.

After discussing the difficulties in establishing an upper bound, we now show a local upper bound, which says for fixed $A$ and fixed direction $M$, there is an algorithm that distinguishes $\operatorname{\mathtt{Leverage}}_{A}$ and $\operatorname{\mathtt{Leverage}}_{A+\epsilon M}$ using $O(\epsilon^{-2})$ queries, for small enough $\epsilon>0$.

###### Theorem 4.3 .

Fix $A,M\in\mathbb{R}^{n\times d}$ where $\|M\|_{2\to\infty}=O(1)$.
For $\epsilon>0$, define $B_{\epsilon}=A+\epsilon M$. We consider the binary hypothesis testing problem with $\operatorname{\mathtt{Leverage}}_{A}$ and $\operatorname{\mathtt{Leverage}}_{B_{\epsilon}}$, for small $\epsilon$.
Let $\nu=\sup_{s}\operatorname{Var}_{\operatorname{\mathtt{Leverage}}_{A}(s)}(w_{s})$ where

$$ $\displaystyle w_{s}=\frac{\operatorname{diag}((I-A_{s}(A_{s}^{\top}A_{s})^{-1} A_{s}^{\top})(M_{s}(A_{s}^{\top}A_{s})^{-1}A_{s}^{\top}))}{\operatorname{diag} (A_{s}(A_{s}^{\top}A_{s})^{-1}A_{s}^{\top})}$ $$

where the division between vectors is entrywise division. Then for $\epsilon>0$ small enough, there is an algorithm that uses $O(\epsilon^{-2}\nu^{-1})$ queries and distinguishes between $\operatorname{\mathtt{Leverage}}_{A}$ and $\operatorname{\mathtt{Leverage}}_{B_{\epsilon}}$.

Proof of Theorem 4.3 is deferred to Appendix A.4.

Similarly to the softmax model case, Theorem 4.3 is also tight.

###### Theorem 4.4 .

Work under the same setting as Theorem 4.3.
For $\epsilon>0$ small enough, any algorithm that distinguishes between $\operatorname{\mathtt{SoftMax}}_{A}$ and $\operatorname{\mathtt{SoftMax}}_{B_{\epsilon}}$ must use $\Omega(\epsilon^{-2}\nu^{-1})$ energy-constrained queries.

###### Proof.

The proof is by combining the proof of Theorem 4.3 and Theorem 4.1. We omit the details.
∎

###### Theorem 4.3 .

###### Theorem 4.4 .

###### Proof.

## 5 Conclusion and Future Directions

Widely applied across various domains, softmax and leverage 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 escalating computational costs in current machine learning research, our work holds the potential to offer valuable insights and guidance for distinguishing between the distributions of different models.

We discuss a few possible directions for further research.

In Theorem 3.5 and Theorem 4.3, we determine the local sample complexity of the binary hypothesis testing problems for softmax models and leverage score models. In particular, the sample complexity is $\Theta(\epsilon^{-2}\nu)$, where $\nu$ is a certain function depending on $A$ and $M$ (where $B=A+\epsilon M$). The form of $\nu$ is an optimization problem over the space of possible inputs. An interesting question is to provide bounds on the quantity $\nu$, or to provide computation-efficient algorithms for determining the value of $\nu$ of finding the optimal input ($x$ for softmax, $s$ for leverage score). This will lead to computation-efficient algorithms for solving the binary hypothesis testing problem in practice.

In this paper we focused on the binary hypothesis testing problem, where the goal is to 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 a 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.

## Impact Statement

By conducting a rigorous theoretical analysis, we can minimize the need for repetitive experiments. Although our work may inadvertently result in unexpected carbon emissions, leveraging theoretical insights enables us to streamline experiments and address this issue. Additionally, we delve into system-level applications, leveraging our theoretical analysis to establish a robust foundation for successful evaluations.

## Appendix

## Appendix A Missing Proofs

### A.1 General Result for Softmax Model

###### Proof of Theorem 3.1 .

Lower bound.
If $\delta\geq 0.1$ then there is nothing to prove. In the following assume that $\delta<0.1$.
Suppose that there is an algorithm that successfully solves the binary hypothesis testing problem.
Suppose it makes queries $x_{1},\ldots,x_{m}\in\mathbb{R}^{d}$ where $x_{i}$ may depend on previous query results.
Let $Y_{1},\ldots,Y_{m}\in[n]$ denote the query results.
Let $P_{Y^{m}}$ and $Q_{Y^{m}}$ denote the distribution of $Y^{m}$ under $P$ and $Q$, respectively.
By definition of $\delta$, we have

$$ $\displaystyle H^{2}(P_{Y_{k}|Y^{k-1}},Q_{Y_{k}|Y^{k-1}})\leq\delta^{2}.$ $$

for any $k\in[m]$ and $Y^{k-1}$.
Then

$$ $\displaystyle~{}1-H^{2}(P_{Y^{m}},Q_{Y^{m}})$ $\displaystyle=$ $\displaystyle~{}\int\sqrt{P_{y^{m}}Q_{y^{m}}}\mathrm{d}y^{m}$ $\displaystyle=$ $\displaystyle~{}\int\sqrt{P_{y^{m-1}}Q_{y^{m-1}}}$ $\displaystyle~{}\left(\int\sqrt{P_{y_{m}|y^{m-1}}Q_{y_{m}|y^{m-1}}}dy_{m} \right)\mathrm{d}y^{m-1}$ $\displaystyle\geq$ $\displaystyle~{}\int\sqrt{P_{y^{m-1}}Q_{y^{m-1}}}(1-\delta^{2})\mathrm{d}y^{m- 1}.$ $$

Repeating this computation, in the end we get

$$ $\displaystyle 1-H^{2}(P_{Y^{m}},Q_{Y^{m}})\geq(1-\delta^{2})^{m}.$ $$

Because $\delta\leq 0.1$, we have $1-\delta^{2}\geq\exp(-2\delta^{2})$.
If $m\leq 0.01\delta^{-2}$,
then

$$ $\displaystyle 1-H^{2}(P_{Y^{m}},Q_{Y^{m}})$ $\displaystyle\geq\exp(-2\delta^{2}m)$ $\displaystyle\geq\exp(-0.02)>0.98,$ $$

and

$$ $\displaystyle H^{2}(P_{Y^{m}},Q_{Y^{m}})\leq 0.02.$ $$

This implies

$$ $\displaystyle\operatorname{TV}(P_{Y^{m}},Q_{Y^{m}})\leq\sqrt{2}H(P_{Y^{m}},Q_{ Y^{m}})\leq 0.2,$ $$

which implies the success rate for binary hypothesis testing cannot be $\geq\frac{2}{3}$.

In conclusion, any algorithm that successfully solves the hypothesis testing problem need to use $\Omega(\delta^{-2})$ queries.

Upper bound.
Take $x\in\mathbb{R}^{d}$ such that $\|x\|_{2}\leq E$ and $\delta=H(\operatorname{\mathtt{SoftMax}}_{A}(x),\operatorname{\mathtt{SoftMax}
}_{B}(x))$.
By Lemma 2.5, using $O(\delta^{-2})$ samples we can distinguish $\operatorname{\mathtt{SoftMax}}_{A}(x)$ and $\operatorname{\mathtt{SoftMax}}_{B}(x)$.
Therefore we can distinguish $\operatorname{\mathtt{SoftMax}}_{A}$ and $\operatorname{\mathtt{SoftMax}}_{B}$ in $O(\delta^{-2})$ queries by repeatedly querying $x$.
∎

###### Proof of Theorem 3.1 .

### A.2 Lower Bound for Softmax Model

Before giving the proof of Lemma 3.3, we prove a weaker version of the lemma.

###### Lemma A.1 .

Let $a,b\in\mathbb{R}^{n}$. Suppose there exists an $\epsilon\geq 0$ such that for every $i\in[n]$, $b_{i}-a_{i}\in\{0,\epsilon\}$.
Let $P$ be the distribution on $[n]$ with $p_{i}=\exp(a_{i})/\langle\exp(a),{\bf 1}_{n}\rangle$.
Let $Q$ be the distribution on $[n]$ with $q_{i}=\exp(b_{i})/\langle\exp(b),{\bf 1}_{n}\rangle$.
Then

$$ $\displaystyle H^{2}(P,Q)$ $\displaystyle=\frac{(1-\exp(\epsilon/4))^{2}}{1+\exp(\epsilon/2)}=O(\epsilon^{ 2}),$ $\displaystyle\operatorname{TV}(P,Q)$ $\displaystyle=\tanh(\epsilon/4)=O(\epsilon).$ $$

###### Proof.

Assume that $a$ and $b$ differ in $m$ coordinates.
By permuting the coordinates, WLOG assume that $b_{i}=a_{i}+\epsilon$ for $1\leq i\leq m$ and $b_{i}=a_{i}$ for $m+1\leq i\leq n$.

Write

$$ $\displaystyle s=\sum_{i=1}^{m}\exp(a_{i})$ $$

and

$$ $\displaystyle t=\sum_{i=m+1}^{n}\exp(a_{i}).$ $$

Then

$$ $\displaystyle H^{2}(P,Q)=$ $\displaystyle~{}1-\sum_{i\in[n]}\sqrt{p_{i}q_{i}}$ $\displaystyle=$ $\displaystyle~{}1-\frac{s\exp(\epsilon/2)+t}{\sqrt{(s+t)(s\exp(\epsilon)+t)}}.$ $$

For fixed $t$ and $\epsilon$, the above is maximized at

$$ $\displaystyle s=t\exp(-\epsilon/2).$ $$

Plugging in the above $s$, we get

$$ $\displaystyle H^{2}(P,Q)\leq$ $\displaystyle~{}1-\frac{2}{\sqrt{(\exp(-\epsilon/2)+1)(\exp(\epsilon/2)+1)}}$ $\displaystyle=$ $\displaystyle~{}\frac{(1-\exp(\epsilon/4))^{2}}{1+\exp(\epsilon/2)}.$ $$

For $\operatorname{TV}$, we have

$$ $\displaystyle\operatorname{TV}(P,Q)=$ $\displaystyle~{}\sum_{m+1\leq i\leq n}(q_{i}-p_{i})$ $\displaystyle=$ $\displaystyle~{}\frac{t}{s+t}-\frac{t}{s\exp(\epsilon)+t}.$ $$

For fixed $t$ and $\epsilon$ the above is maximized at $s=t\exp(-\epsilon/2)$.
Plugging in this $s$, we get

$$ $\displaystyle\operatorname{TV}(P,Q)\leq\tanh(\epsilon/4).$ $$

∎

###### Proof of Lemma 3.3 .

We first prove the case where $b_{i}\geq a_{i}$ for all $i\in[n]$.
Define $\epsilon_{i}=b_{i}-a_{i}$ for all $i\in[n]$.
By permuting the coordinates, WLOG assume that $\epsilon_{1}\leq\cdots\leq\epsilon_{n}$. Specially, define $\epsilon_{0}=0$.
For $0\leq k\leq n$, let $b^{k}\in\mathbb{R}^{n}$ denote the vector where $b^{k}_{i}=a_{i}+\min\{\epsilon_{i},\epsilon_{k}\}$ for all $i\in[k]$.
Then we can see that $b^{0}=a$ and $b^{n}=b$, and for every $0\leq k\leq n-1$, the pair $(b^{k},b^{k+1})$ satisfies the assumption in Lemma A.1.
For $0\leq k\leq n$, let $P^{k}$ denote the softmax distribution corresponding to $b^{k}$.
By Lemma A.1, for every $0\leq k\leq n-1$, we have

$$ $\displaystyle H(P^{k},P^{k+1})$ $\displaystyle=O(\epsilon_{k+1}-\epsilon_{k}),$ $\displaystyle\operatorname{TV}(P^{k},P^{k+1})$ $\displaystyle=O(\epsilon_{k+1}-\epsilon_{k}).$ $$

Because Hellinger distance and TV distance are both metrics, we have

$$ $\displaystyle H(P,Q)=$ $\displaystyle~{}H(P^{0},P^{n})$ $\displaystyle\leq$ $\displaystyle~{}\sum_{k=0}^{n-1}H(P^{k},P^{k+1})$ $\displaystyle=$ $\displaystyle~{}O(\epsilon),$ $$

and

$$ $\displaystyle\operatorname{TV}(P,Q)=$ $\displaystyle~{}\operatorname{TV}(P^{0},P^{n})$ $\displaystyle\leq$ $\displaystyle~{}\sum_{k=0}^{n-1}\operatorname{TV}(P^{k},P^{k+1})$ $\displaystyle=$ $\displaystyle~{}O(\epsilon).$ $$

This finishes the proof of the result when $b_{i}\geq a_{i}$ for all $i\in[n]$.

Now let us consider the general case.
Let $c\in\mathbb{R}^{n}$ be defined as $c_{i}=\max\{a_{i},b_{i}\}$ for all $i\in[n]$.
Then

$$ $\displaystyle\max\{\|a-c\|_{\infty},\|c-b\|_{\infty}\}\leq\|a-b\|_{\infty}\leq\epsilon.$ $$

Let $R$ be the softmax distribution corresponding to $c$.
By our previous discussion, we have

$$ $\displaystyle H(P,R),H(R,Q),\operatorname{TV}(P,R),\operatorname{TV}(R,Q)=O( \epsilon).$ $$

By metric property of Hellinger distance and TV distance, we get

$$ $\displaystyle H(P,Q),H(P,Q)=O(\epsilon)$ $$

as desired.

∎

###### Lemma A.1 .

###### Proof.

###### Proof of Lemma 3.3 .

### A.3 Local Upper Bound for Softmax Model

###### Proof of Theorem 3.5 .

We take an $x$ satisfying $\|x\|_{2}\leq E$ that maximizes $\operatorname{Var}_{\operatorname{\mathtt{SoftMax}}_{A}(x)}(Mx)$ and repeatedly query $x$.
We would like to apply Theorem 3.1.
To do that, we need to show that

$$ $\displaystyle H^{2}(\operatorname{\mathtt{SoftMax}}_{A}(x),\operatorname{ \mathtt{SoftMax}}_{B_{\epsilon}}(x))=\Omega(\epsilon^{2}\nu).$ $$

Let $P=\operatorname{\mathtt{SoftMax}}_{A}(x)=(p_{1},\ldots,p_{n})$, $Q_{\epsilon}=\operatorname{\mathtt{SoftMax}}_{B_{\epsilon}}(x)=(q_{\epsilon,1}
,\ldots,q_{\epsilon,n})$.
Write $Z_{A}=\langle\exp(Ax),{\bf 1}_{n}\rangle$, $Z_{B_{\epsilon}}=\langle\exp(B_{\epsilon}x),{\bf 1}_{n}\rangle$.

Then, it follows that

$$ $\displaystyle Z_{B}$ $\displaystyle=\sum_{j\in[n]}\exp(Ax)_{j}\exp(\epsilon(Mx)_{j})$ $\displaystyle=\sum_{j\in[n]}\exp(Ax)_{j}+\sum_{j\in[n]}\exp(Ax)_{j}(\exp( \epsilon(Mx)_{j})-1)$ $\displaystyle=\sum_{j\in[n]}\exp(Ax)_{j}+\sum_{j\in[n]}\exp(Ax)_{j}(\epsilon( Mx)_{j}+O(\epsilon^{2}))$ $\displaystyle=Z_{A}(1+\epsilon\langle p,Mx\rangle+O(\epsilon^{2})).$ (3) $$

where the initial step is because of $B=A+\epsilon M$, the second step is a result of simple algebra, the third step is a consequence of the Taylor expansion of $\exp(\cdot)$, assuming $\epsilon$ is sufficiently small and the fourth step is the result of the definition of $Z_{A}$ and involves the consolidation of addition, introducing the common term $Z_{A}$.

Then

$$ $\displaystyle q_{\epsilon,i}$ $\displaystyle=\frac{\exp(B_{\epsilon}x)_{i}}{Z_{B}}$ $\displaystyle=\frac{\exp(Ax)_{i}\exp(\epsilon Mx)_{i}}{Z_{A}(1+\epsilon\langle p ,Mx\rangle+O(\epsilon^{2}))}$ $\displaystyle=p_{i}(1+\epsilon((Mx)_{i}-\langle p,Mx\rangle)+O(\epsilon^{2})).$ (4) $$

where the initial step is because of the definition of $q_{\epsilon,i}$, the subsequent step is a result of Eq.(A.3), and the third step is due to the definition of $q_{i}$ along with the Taylor expansion of $f(x)=1/(1+x)$ and $\exp(\cdot)$, considering $\epsilon$ as a sufficiently small value.

So, we have that

$$ $\displaystyle H^{2}(P,Q_{\epsilon})$ $\displaystyle=\frac{1}{2}\sum_{i=1}^{n}(\sqrt{p_{i}}-\sqrt{q_{\epsilon,i}})^{2}$ $\displaystyle=\frac{1}{2}\sum_{i=1}^{n}p_{i}(\epsilon^{2}((Mx)_{i}-\langle p, Mx\rangle)^{2}+O(\epsilon^{3}))$ $\displaystyle=\frac{1}{2}\epsilon^{2}\operatorname{Var}_{P}(Mx)+O(\epsilon^{3})$ $\displaystyle=\frac{1}{2}\epsilon^{2}\nu+O(\epsilon^{3}).$ $$

where the first step is the result of Definition 2.2, the second step is because of Eq.(A.3), the third step the result of definition of $\operatorname{Var}_{P}(Mx)$ (See Definition 2.3) and the forth step follows from the expression $\nu=\sup_{x:\|x\|_{2}\leq E}\operatorname{Var}_{\operatorname{\mathtt{SoftMax}
}_{A}(x)}(Mx)$.

Applying Theorem 3.1 we finish the proof.
∎

###### Proof of Theorem 3.5 .

### A.4 Local Upper Bound for Leverage Score Model

###### Proof of Theorem 4.3 .

We take an $s$ satisfying $c\leq s_{i}^{2}\leq C$ and $\forall i\in[n]$ that maximizes $\sup_{s}\operatorname{Var}_{\operatorname{\mathtt{Leverage}}_{A}(s)}(w_{s})$ and repeatedly query $s$.
We need to show that

$$ $\displaystyle H^{2}(\operatorname{\mathtt{Leverage}}_{A}(s),\operatorname{ \mathtt{Leverage}}_{B_{\epsilon}}(s))=\Omega(\epsilon^{2}\nu).$ $$

Let $P=\operatorname{\mathtt{Leverage}}_{A}(s)=(p_{1},\ldots,p_{n})$, $Q_{\epsilon}=\operatorname{\mathtt{Leverage}}_{B_{\epsilon}}(x)=(q_{\epsilon,1
},\ldots,q_{\epsilon,n})$.
We can compute that

$$ $\displaystyle\frac{d}{d\epsilon}q_{\epsilon,i}=(2(I-A_{s}(A_{s}^{\top}A_{s})^{ -1}A_{s}^{\top})(M_{s}(A_{s}^{\top}A_{s})^{-1}A_{s}^{\top}))_{i,i}.$ $$

Define $W=(I-A_{s}(A_{s}^{\top}A_{s})^{-1}A_{s}^{\top})(M_{s}(A_{s}^{\top}A_{s})^{-1}A
_{s}^{\top})$.
Then

$$ $\displaystyle q_{\epsilon,i}=p_{i}+2W_{i,i}\epsilon+O(\epsilon^{2}).$ $$

Computing $H^{2}(P,Q_{\epsilon})$ we get

$$ $\displaystyle H^{2}(P,Q_{\epsilon})$ $\displaystyle=\frac{1}{2}\sum_{i\in[n]}(\sqrt{q_{\epsilon,i}}-\sqrt{p_{i}})^{2}$ $\displaystyle=\sum_{i\in[n]}p_{i}\left(\frac{W_{i,i}}{p_{i}}\epsilon+O( \epsilon^{2})\right)^{2}$ $\displaystyle=\sum_{i\in[n]}\frac{W_{i,i}\epsilon^{2}}{p_{i}}+O(\epsilon^{3})$ $\displaystyle=\epsilon^{2}\nu+O(\epsilon^{3}).$ $$

∎

###### Proof of Theorem 4.3 .

## Peer Reviews

confidence: 4
contribution: 2
initial_rating: 3
presentation: 1
questions: 1. Why do you say "asymptotically" in the abstract?
2. Can you explain the case of $\delta \geq 0.1$ for lower bound in Theorem 3.1.?
3. Why do you assume $m \leq 0.01 \delta^{-2}$? I don't see this assumption in the main body of the paper. Why would this assumption is meaningful in the context of binary hypothesis testing?
soundness: 1
strengths: The hypothesis testing lens to study properties of softmax models is an interesting idea.
summary: This paper studies the sample complexity of binary hypothesis testing in the context of softmax and leverage score models. First, the paper identifies the requirement of energy constraints for both problems as otherwise the testing problems are straightforward. Then, the lower and upper sample complexities are identified for the two problems.
weaknesses: 1. The write-up needs significant improvements. I find it hard to follow the introduction and the related work section on theoretical LLMs, which include many unrelated works. I am also skeptical of how the authors motivate the problem, focusing purely on LLMs.

2. It seems like the main result depends on the result from Polyanskiy & Wu, and the significance of results on top of these main results is not clear. I believe the key result is Theorem 3.1, which is invoked by controlling Hellinger distance under some perturbations. The upper bound in Theorem 3.1. is directly from Polyanskiy & Wu. So, I believe the main result is the lower bound in Theorem 3.1. Studying the analysis, the proof is straightforward (the contribution is mild) and contains an implicit assumption on the number of queries, $m$, not explained.

3. I believe the example in L261-268 is wrong for the leverage score model. Could you explain why $\delta > 0$ will put all mass on $2 \in [n]$ for $\mathrm{Leverage}_{B}(s)$? In addition, I understand that the problem is straightforward without the energy constraints, but this needs to be justified by motivating the problem in this setting.

---

confidence: 4
contribution: 1
initial_rating: 3
presentation: 2
questions: See weaknesses
soundness: 2
strengths: - The theoretical results seem sound. 
- The notations and exposition of the results is clear to follow.
summary: This paper analyzes the sample complexity of the binary hypothesis testing problem for softmax distributions and leverage scores, with the motivation of improving theoretical understanding of LLMs. The theoretical contribution of the paper is providing upper and lower bounds on the sample complexity, both for softmax operators and leverage scores, which are obtained by estimating the Hellinger distances between the distributions and then applying them in conjunction with prior results in hypothesis testing literature.
weaknesses: - The glaring weakness is that the motivation of the paper is largely unclear and disconnected from the work done in the paper. The motivation of the works is to study LLMs through a better understanding of the softmax attention. On the other hand, the analysis, which is about the sample complexity of distinguishing two softmax distributions in a hypothesis testing problem, seems largely tangential and the results are never connected back to the original motivation or explain how it serves to improve LLM understanding, either in theory or via simulations.
- The exposition on leverage scores seems to have been shoehorned and seems to have no connection to the motivation either, except some vague comments about their usefulnes. I understand that it might be of interest to show the similarities, but the authors need to explain why how this additional perspective connects to the question of interest. 
- Presentation Issues: The paper has some writing issues outside of the theoretical analysis, which makes the paper hard to follow. 
    - The motivation needs clarity, and the chose approach needs to be justified.
        - Line 53: _Can we distinguish different ability parts of large language models by limited parameters sampling?_ I am not sure what the authors mean by "ability parts" or "limited parameters sampling".
        - Line 60-63: I find it hard to follow as to how hypothesis testing and distinguishing one softmax distribution from another, can help improve the theoretical understanding of LLMs or determine which parameters are important for inference. 
   - The related work section is vague; it is not clear which references are relevant to the motivation or techniques used in this work. Similarly, in conclusions and future work, the exposition is largely about solving the hypothesis testing problem and does not substantiate on potential practical applications.
    - Lines 47-48, 56-58 need sentence restructuring.
- Overall, I believe that this work seems to be more hypothesis testing centric, and thus might be a better fit for a different venue both in terms of applicability of the results and audience interest.

---

confidence: 3
contribution: 2
initial_rating: 3
presentation: 2
questions: see weaknesses
soundness: 2
strengths: I’m not an expert in this field, but the lower and upper bounds seem like a novel results for softmax and leverage score models for the binary hypothesis testing problem.
summary: The authors derive upper bounds and lower bounds on the number of queries needed to distinguish between two different softmax or leverage score model distributions. This is also known as the binary hypothesis testing problem. The proofs require manipulating inequalities between the Hellinger distance and the total variation distance. Additional energy constraints on the input query is also needed for proving the upper bounds of sample complexity.
weaknesses: - This paper is not properly motivated, at least in how it’s written. The introduction sections touch on LLMs and how attention is an important component of LLMs. In the rest of the paper, the authors go on to prove bounds on number of samples needed for binary hypothesis testing for a generic softmax and leverage score model without circling back to how it relates to LLM. If the research question is understanding the sample complexity of softmax and leverage score model under the binary hypothesis testing problem, which I think it’s a worthwhile research question, the authors shouldn’t motivate it from LLMs without ever relating it to LLMs.
- Similar to the first point, I’m not sure if there are any interesting applications for the provided sample complexity bounds. It’s unclear to me if these bounds are tight or not or do they ever prescribe any meaning quantities in practice. Tentatively, I’m suggesting one experiment the authors can do in an application domain like LLM:
    - Suppose there are two LLMs. Given different input sequences, the next token distribution comes from a softmax over the logit vectors. Then one interesting question could be how many input sequences do we need to tell which LLMs we’re using based on the next token softmax distribution. This could be interesting in the context of knowledge distillation or some sort of toxic speech detection problems. Then the authors can plot the predicted number of samples using the bounds and also the empirical number of samples needed to actually distinguish between the two distributions.

---

confidence: 4
contribution: 2
initial_rating: 3
presentation: 2
questions: *Questions related to the weaknesses*
1) What are the practical, methodological, or theoretical implications of the results for LLMs, transformers, and neural networks? 
2) Could the authors think of experiments (even on synthetic data) to illustrate or showcase the importance of their theoretical results? (I feel the need to note that I have nothing against fully theoretical papers, but in its current form, the relevance of the theoretical contributions of this paper is limited and it lacks discussion to fully understand their potential implications in machine learning/deep learning).  
3) The authors mention an analogy between softmax and leverage score models in the abstract. What is the analogy or connection between them, except that both are parameterized by a matrix and take vectors as inputs?
4) In the attention mechanism, the softmax matrices depend on the input sequence of tokens ($\mathrm{softmax}(XW_Q^TW_KX/d_{\kappa}$). Hence, I am not sure the current analysis with a fixed matrix $\mathbf{A}$ (see Definitions 2.6/2.7) holds. Could the authors elaborate on this? In particular, what plays the role of $A$ and $x$ in LLMs and transformers?
5) Similarly, the authors justify the scaling of the input (Definition 2.8) by the use of batch-norm. However, in most transformers, including LLMs, LayerNorm and its variations are preferred instead of batch normalization. In addition, the product $Ax$ of Definition $2.6$ is rather a $XW_Q^TW_KX$ with learnable $W_Q, W_K$. Again, what plays the role of $A$ and of $x$, and why would it be justified to consider $x$ bounded in such a case? Could the authors elaborate on that matter?

*I list below potential typos and sentences I did not understand .*

- l034: missing reference replaced by a "?"
- l043: *"potent capabilities"* --> What does that mean? Do the authors mean "powerful capabilities"?
-l045: *"prevailing prevalence"* --> Is it a typo to have the adjective and noun combined? Do the authors simply mean "prevalence"?
-l047-l048: *"However, their is [...] of the whole"* --> I do not understand the sentence, it seems unfinished.
-l050-l051: *"as well as sparsity [...] above"* --> I do not understand this part of the sentence at all.
- l053: *"can we distinguish [...] sampling"* --> I do not understand the question nor its connection to the paragraph above it (l047-l051). Could the authors elaborate on that?
- l059-l081: 5 repetitions of the word "delve", use of complicated vocabulary (distinguishing ability, intricacies, inquiry, etc.) that hinders the meaning and understanding of the paragraph.
soundness: 2
strengths: - Studying the softmax as a sampling operation is interesting
- The focus on the binary hypothesis testing is original and could have a potential impact on machine learning and deep learning 
- The analysis and the proofs for both models are detailed
summary: This paper studies binary hypothesis testing, which identifies an unknown distribution given two possible candidates, for the softmax and the leverage score models. 

*Setup and tools*: The analysis focuses on the softmax model commonly used in deep learning and on the leverage score models used in graph theory and linear algebra. The authors conducted their proofs with information-theoretic tools and norm manipulation.

*Contributions*: The authors show that the sample complexity (in terms of queries) of the binary hypothesis testing is $\mathcal{O}(\varepsilon^2)$, where $\varepsilon$ is a distance-based measure between parameters, for both the softmax model and the leverage score models.
weaknesses: - The authors state the main problem with respect to LLMs (l053), but they do not explain the theoretical, methodological, or practical implications of their results for LLMs or neural networks. 
- Considering simple models for a proper theoretical study is valid, but in my opinion, studying the softmax operator as a standalone is an oversimplification, especially if the motivation is the use of the softmax in LLMs and neural networks. 
- In the attention mechanism, the softmax matrices depend on the input sequence of tokens ($\mathrm{softmax}(XW_Q^TW_KX/d_{\kappa}$). Hence, I don't think that the current analysis with a fixed matrix $\mathbf{A}$ (see Definitions 2.6/2.7) holds. Could the authors elaborate on this? In particular, what plays the role of $A$ and $x$ in LLMs and transformers?
- Similarly, the authors justify the scaling of the input (Definition 2.8) by the use of batch-norm. However, in most transformers, including LLMs, LayerNorm and its variations are preferred instead of batch normalization. In addition, the product $Ax$ of Definition $2.6$ is rather a $XW_Q^TW_KX$ with learnable $W_Q, W_K$. Again, what plays the role of $A$ and of $x$, and why would it be justified to consider $x$ bounded in such a case? Could the authors elaborate on that matter?
- The writing could be improved: several sentences are unclear to me and there are many repetitions in some paragraphs (e.g., "delve").
- The structure could be improved: currently, it does not highlight the strengths of the paper and makes it look more like a concatenation of results.

Meta-review: This paper considers the sample complexity of binary hypothesis testing for softmax models and leverage score models. Typically a statistical problem, the work is primarily motivated to improve understanding of the behavior of large language models. Reviewers found the work to be flawed: while the results are motivated by LLMs, no discussion of LLMs are present. While the findings are of statistical interest, it is unclear that this community would be especially receptive to them in their current form. It appears that some good feedback was provided to the authors, but I would recommend the authors take one of two approaches:

(1) Limit the discussion of LLMs as motivation, and resubmit the work to a statistical outlet. While the presented bounds constitute an interesting avenue for study, it may be too premature to tackle such a complicated use-case. I suspect this work may be better received as-is in a community receptive to studying hypothesis tests.

(2) Move the proofs into supplementary material and dedicate a significant portion of the document toward numerical investigations involving LLMs to link them in with the current material. Several reviewers had some good suggestions on how one might go about this. In this form, the paper may be better received at another machine learning outlet, e.g. ICML.

Decision: Reject