Measuring the Constant-Factor Trap in Instance-Optimal Identity Testing

Identity testing asks a simple question: given samples from an unknown distribution over $k$ symbols, does it equal a known reference distribution $q$, or is it at least $\varepsilon$ away in total variation, the largest difference in probability the two assign to any single event? In the worst case this takes about $\sqrt{k}/\varepsilon^2$ samples. Many references are much easier to test than that, though, including skewed token distributions, power laws, and distributions dominated by one outcome. "Instance-optimal" theory tries to predict the true cost for each specific $q$. The two leading predictions, a truncated $\ell_{2/3}$ quasinorm and an interpolation "K-functional," agree only up to a constant-factor shift in $\varepsilon$, such as comparing a bound at $\varepsilon$ with one at $\varepsilon/16$. For the Harmonic distribution $q(i)\propto 1/i$, that shift changes the predicted sample count by a polynomial factor (Open Problem: Tight Characterization of Instance-Optimal Identity Testing). Nobody has measured how large this gap is in practice. The open problem is stated entirely on paper.

This note proposes to measure it. We would build a protocol that estimates the empirical sample complexity $n^*(q,\varepsilon)$ for hundreds of reference distributions: synthetic power laws, token distributions from real corpora, and near-degenerate distributions where one outcome holds almost all the mass. We would then ask which closed-form functional tracks $n^*$ up to an absolute constant uniformly across instances and across $\varepsilon$. One candidate is new: a correction for near-degenerate references taken from the reverse Pinsker inequality. Pinsker's inequality says KL divergence (relative entropy) is at least $2V^2$, where $V$ is total variation. The reverse Pinsker result gives the minimum KL needed to move a given total-variation distance away from $q$, and that minimum grows sharply when $q$ is lopsided. Canonne flags this near-degenerate regime as the place where existing lower-bound proofs break. The deliverable is an empirical verdict on an open theoretical question, together with a concrete conjecture about which functional closes it.

Core Claim

The constant-factor trap is either a proof artifact or a real phenomenon, and a careful measurement can tell the two apart. If $n^*(q,\varepsilon)/\Phi(q,\varepsilon)$ stays within a narrow band for a candidate functional $\Phi$ across all instances and a decade of $\varepsilon$, the trap is an artifact and $\Phi$ becomes a concrete conjecture. If the ratio drifts systematically with $\varepsilon$ on Harmonic-like references, the trap is real and needs a new functional. We additionally hypothesize where the near-degenerate failure comes from.

The proposed functional takes the larger of an $\ell_{2/3}$-type term and a "heavy-atom" term. The heavy-atom term is calibrated by the minimum-KL quantity of A Reverse Pinsker Inequality and Minimum KL-Divergence on Complements of $L_{1}$ Balls. That quantity is

$$D^*(v,q)=\inf_{p:\ \|p-q\|_1\ge v} D(p\,\|\,q),$$

the smallest KL divergence $D$ at which a distribution $p$ can sit at $L_1$ distance $v$ from $q$. Those papers show $D^*(v,q)=v^2/2+O(v^4)$ when $q$ is balanced, meaning its mass can be split into two halves of about $1/2$ each. When $q$ is unbalanced, with balance coefficient $\beta>1/2$, they show

$$D^*(v,q)=\frac{v^2}{8\beta(1-\beta)}-O(v^3).$$

The motivation for using $D^*$ is that it also measures how hard it is to detect the cheapest deviation. A two-point (Le Cam) argument built on that deviation suggests a heavy-atom contribution scaling like $1/D^*(2\varepsilon,q)$. Unlike Pinsker's $v^2/2$, this term is sensitive to $\beta$. It is exactly where Pinsker is loose and exactly where Canonne's lower bounds fail.

We state honestly where this term matters and where it does not. Unigram token distributions are effectively balanced, so the correction is irrelevant there and Pinsker is already tight. The correction matters only for near-degenerate references. Those references occur in practice: next-token distributions of a language model conditioned on a context are often dominated by one token. This is where the Pinsker direction earns its place in the study.

Research Program

The first component is the measurement protocol. Sample complexity is a worst case over alternatives at distance $\varepsilon$, so no simulation can compute it exactly. We therefore bracket $n^*$ from two sides, and the measured quantity is this bracket.

The upper side comes from a battery of testers, each calibrated to a 5% false-alarm rate by Monte Carlo simulation under $q$. Simulation is possible because $q$ is known. For each instance we record the smallest $n$ at which the best tester in the battery reaches 2/3 power against every alternative in a pool.

The pool combines three ingredients:

The lower side comes from the same alternatives, mixed into the standard random-perturbation constructions. We compute exact or numerically integrated chi-square and Hellinger divergences between the induced sample distributions, which certifies that no tester can succeed below a given $n$. If the bracket stays within a small factor, we treat $n^*$ as measured. If it does not, we report the bracket width as a finding.

The second component is the set of instances. It includes:

  • the nine synthetic profiles of Data Amplification: Instance-Optimal Property Estimation, at support $10^4$;
  • the uniform and $1/i$ nulls at $d=2000$, matching Balakrishnan and Wasserman;
  • a Harmonic sweep in $k$;
  • a near-degenerate family $q=(1-\eta,\eta\cdot r)$, with $\eta$ ranging from $10^{-1}$ to $10^{-4}$ and tails $r$ that are uniform or Zipf;
  • real unigram token distributions from Reddit, Enron and MMLU text under GPT-2 and BERT tokenizers, the corpora used by Instance-Optimality for Private KL Distribution Estimation;
  • unigram distributions from a FineWeb sample (HuggingFaceFW/fineweb);
  • conditional next-token distributions on FineWeb contexts from a small open language model, which supply naturally near-degenerate references.

The third component is functional fitting. For each candidate $\Phi$, we fit one global constant and report the spread of $\log(n^*/\Phi)$ across instances. We also report its slope against $\log\varepsilon$ within each instance. The candidates are:

  • the worst-case $\sqrt{k}/\varepsilon^2$;
  • the Valiant–Valiant truncated $\ell_{2/3}$ functional at $\varepsilon$, and separately at $\varepsilon/16$;
  • the Blais–Canonne–Gur K-functional;
  • the Balakrishnan–Wasserman local-minimax radius inverted into a sample count;
  • the proposed maximum of an $\ell_{2/3}$-type term and $1/D^*$.

The slope against $\varepsilon$ is the direct signature of the trap.

Baselines

The naive reference point is the worst-case predictor $\sqrt{k}/\varepsilon^2$, paired with classical Pearson chi-square and likelihood-ratio testers. We include it because "instance optimality is unnecessary in practice" is a live hypothesis. Balakrishnan and Wasserman report qualitatively that both classical tests degrade on sparse alternatives and power-law nulls. We found no reported rejection-rate number on Lacuna for this comparison, so our measurement supplies the first numbers. Beating this baseline means a log-spread of $n^*/\Phi$ at least several times smaller than the spread for $\sqrt{k}/\varepsilon^2$.

The strongest existing testers are the Truncated chi-square test and the Max Test of Hypothesis Testing For Densities and High-Dimensional Multinomials: Sharp Local Minimax Rates. They are the only instance-adaptive testers in the file with an empirical record, at $d=2000$ and $n=200$ under uniform and $1/i$ nulls, though only in qualitative form; no reported power value was found on Lacuna. We run them alongside a collision-based tester and an $\ell_{2/3}$-bucketed tester. Every tester gets the same Monte Carlo calibration, the same alternative pool and the same grid of $n$. Any truncation level is tuned on a held-out set of instances with an equal budget for every tester.

The strongest existing predictors are the $\ell_{2/3}$ functional and the K-functional. The proposed functional beats them if, on the near-degenerate family and on the conditional next-token references, it reduces the log-spread without increasing it on the balanced instances.

The key ablation replaces the $1/D^*$ heavy-atom term with the Pinsker-based term $2/\varepsilon^2$, which ignores $\beta$. If this ablation fits equally well, the reverse-Pinsker ingredient adds nothing. That outcome is likely on balanced references, and the test is decisive only on lopsided ones.

Why not just…?

Why not just calibrate every test by simulating the null, and skip functionals entirely? For deciding a single test, simulation is the right tool, and we use it for every tester. It answers "is this $p$ equal to this $q$." It does not answer how many samples a given $q$ requires before any data are collected. It also does not tell theorists which functional is correct. The open problem posed by Canonne concerns that prediction, and simulation is the instrument for checking it, not a replacement for it.

Why not just use the worst-case $\sqrt{k}/\varepsilon^2$ rate, since constants dominate at practical sizes anyway? This is the null hypothesis of the study, and it is not obviously false at moderate $k$. Evidence against it is qualitative so far. Balakrishnan and Wasserman show that power-law nulls behave differently from uniform ones, and Ye et al. show that minimax-calibrated estimators lose to instance-optimal ones on Reddit, Enron and MMLU, though for estimation rather than testing. Our log-spread metric settles the question directly.

Why not just use Pinsker's $v^2/2$, which Berend and Kontorovich prove is asymptotically exact for balanced references? On balanced references it is exact, and the $D^*$ term reduces to it, so we expect no gain on unigram vocabularies. We are not claiming otherwise. The claim is confined to near-degenerate references, where $1/(8\beta(1-\beta))$ diverges and Canonne's lower bounds fail. The Pinsker-versus-$D^*$ ablation on the $\eta$ sweep and on conditional next-token distributions is designed to show whether this matters. A null result there would be a clean negative finding.

Proposed Experiments and Decisive Checks

The first decisive check is the Harmonic sweep. For $k$ from $10^3$ to $10^5$ and $\varepsilon$ from 0.05 to 0.5, we test whether the slope of $\log(n^*/\Phi_{\ell_{2/3}})$ against $\log\varepsilon$ is distinguishable from zero. Evaluating the functional at $\varepsilon$ and at $\varepsilon/16$ shows which end of the trap reality sits on.

The second is the near-degenerate sweep. As $\eta\to 0$, the measured bracket on $n^*$ should follow $1/D^*$ and not the existing functionals, if the hypothesis holds. We also check that the lower-bound side of the bracket stays tight there, which would give empirical support for a repaired lower-bound construction.

The third is transfer to real data. A functional fitted on synthetic instances should predict $n^*$ on Reddit, Enron, MMLU, FineWeb unigrams and conditional next-token references within the same constant band.

All code, instance files and the brackets on $n^*$ would be released as a benchmark for instance-optimal testing. The empirical-validation gap documented across this literature is partly a missing shared testbed, and this release would supply one.