Research map / Learning theory and algorithms / Sample complexity
Binary Hypothesis Testing for Softmax Models and Leverage Score Models
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Studies binary hypothesis testing between two softmax models (attention-like) and two leverage score models, giving Hellinger-distance-based sample complexity bounds with matching local upper and lower bounds.
Problem
How many queries are needed to determine which of two known softmax models or leverage score models generated the observed outputs, given energy- or norm-constrained inputs.
Approach
Reduces hypothesis testing for softmax and leverage score models to Hellinger distance between output distributions under constrained inputs, yielding Theta(delta^-2) sample complexity; gives O(eps^-2) lower bound for softmax and local tight bounds via variance-type quantity nu.
Key results
- Softmax model hypothesis testing: lower bound Omega(eps^-2 E^-2) queries when ||A-B||_{2->inf} <= eps under energy constraint E.
- Local upper bound O(eps^-2 nu^-1) queries for B = A + eps M, with matching lower bound Omega(eps^-2 nu^-1) for softmax models.
- Leverage score model: lower bound Omega(c delta/(C eps)) queries (linear in 1/eps), leaving the quadratic gap open.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Bound the parameter difference by ||A-B||_{2→∞} ≤ ε | Softmax model binary hypothesis testing with input norm at most E · Softmax models | sample complexity lower bound: Ω(ε^{-2} E^{-2}) | Mixed |
| Perturb A along a fixed direction M to form A+εM | Local softmax testing · Softmax_A vs. Softmax_{A+εM} | sample complexity: O(ε^{-2} ν^{-1}); Ω(ε^{-2} ν^{-1}) | Mixed |
| Use a direction M whose variance under the softmax output is small | Local softmax testing · Softmax_A vs. Softmax_{A+εM} | sample complexity: O(ε^{-2} ν^{-1}) | Hurt |
| Use a direction M with high output variance | Local softmax testing · Softmax_A vs. Softmax_{A+εM} | variance ν: Ω(E^2) | Helped |
| Bound the sum of row outer-product differences by ε | Leverage score model binary hypothesis testing · Leverage models with AᵀA ⪰ δI | sample complexity lower bound: Ω(c δ / (C ε)) | Mixed |
| Perturb A along a fixed direction M to form A+εM | Local leverage score testing · Leverage_A vs. Leverage_{A+εM} | sample complexity upper bound: O(ε^{-2} ν^{-1}) | Mixed |
| Change a single row while keeping its row outer-product difference Ω(1) | Leverage score model · Constrained leverage queries | total variation distance: O(1/n) | No clear effect |
Surprising findings
- Sample complexity for softmax models can grow with the number of classes n when differing rows have small probability mass under all inputs.
- Distinct matrices A and B (e.g., differing by a column-wise shift 1 w^T) can induce identical softmax models, making them indistinguishable.
Limitations
- Leverage score lower bound is linear in 1/eps rather than quadratic, leaving a gap to the upper bound.
- Results are local (small perturbation B = A + eps M) and depend on an optimization over inputs that is not computed efficiently.
- Theoretical analysis only; no experiments on real LLM attention.
Experimental setup
Metrics: sample complexity
Builds on: classical binary hypothesis testing (Hellinger distance characterization)
Closest papers by meaning
- Breaking the Softmax Bottleneck via Learnable Monotonic Pointwise Non-linearities (ICML 2019 · similarity 0.86)
- Rethinking Approximate Gaussian Inference in Classification (NeurIPS 2025 · similarity 0.83)
- Tail Competition Explains Scaling in Best-of-N Sampling for Verifiable Problems (NeurIPS 2026 · similarity 0.83)
- Sequential Probability Assignment with Contexts: Minimax Regret, Contextual Shtarkov Sums, and Contextual Normalized Maximum Likelihood (NeurIPS 2024 · similarity 0.83)
- Hypothesis Testing for Generalized Thurstone Models (ICML 2025 · similarity 0.82)
- Peeking with PEAK: Sequential, Nonparametric Composite Hypothesis Tests for Means of Multiple Data Streams (ICML 2024 · similarity 0.82)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.