Hypothesis Testing with Conditional Queries: Learnability and the Value of Interaction

Preprint

H YPOTHESIS T ESTING WITH C ONDITIONAL Q UERIES : L EARNABILITY AND THE VALUE OF I NTERACTION Zonghuan Xu Fudan University 2430xh10002@m.fudan.edu.cn

arXiv:2608.06262v1 [cs.LG] 6 Aug 2026

A BSTRACT Model evaluations may fix all tests before observing any responses or select later tests using earlier responses. We study this choice in a conditional-query model on a finite outcome space X with |X | = N . We first ask which pairs of distribution classes can be reliably distinguished. We then ask how many additional queries are required to match an adaptive tester when all queried events must be fixed in advance. We show that learnability holds if and only if the two classes have positive separation in their pairwise conditional probabilities. When this separation is zero, the optimal worst-case error is exactly 1/2 at every finite query budget. For any T -query adaptive policy and any ρ ∈ (0, 1),
we construct a randomized non-adaptive procedure using O N 2 (T + log(1/ρ)) pair queries chosen before any response is observed. Its simulated transcript is within ρ in total variation of the adaptive transcript, uniformly over all distributions in the model. We also construct a matching family with constant adaptive query complexity and Ωε (N 2 ) non-adaptive query complexity. Consequently, the worst-case fixed-error adaptivity gap is Θε (N 2 ). Thus interaction can reduce the required number of tests by a quadratic factor, but the apparent exponential branching of an interactive evaluation does not yield an exponential query advantage.

1

I NTRODUCTION

Model evaluations take both static and interactive forms. Widely used benchmark suites typically fix their items before a model is evaluated (Hendrycks et al., 2021; Srivastava et al., 2023; Liang et al., 2023). Dynamic benchmark projects instead create or refresh data using model behavior over successive development cycles (Kiela et al., 2021; Nie et al., 2020; Potts et al., 2021). Behavioral testing broadens what benchmark items probe, while interactive platforms evaluate open-ended or multi-turn behavior (Ribeiro et al., 2020; Thrush et al., 2022; Zheng et al., 2023). Live benchmarks update questions over time to limit contamination (White et al., 2025). These approaches change evaluation design at different timescales. We focus on adaptivity within a single evaluation. A static benchmark fixes all tests before observing any response. An interactive evaluation lets earlier responses determine which tests are asked later. A static design avoids sequential rounds, but it may need to prepare tests for many possible response histories. An interactive evaluation can wait to see which history occurs before selecting the next test. Interaction may therefore reduce the number of tests at the cost of sequential evaluation. How large can this reduction be? In particular, can a fixed test suite match any interactive evaluation with a polynomial, rather than exponential, increase in size? Conditional distribution testing studies algorithms that may sample from a distribution after conditioning on a chosen event (Chakraborty et al., 2013; Canonne et al., 2015; 2014). Existing results establish problem-specific upper and lower bounds for identity, equivalence, uniformity, support-size, and tolerant testing (Acharya et al., 2018; Falahatgar et al., 2015; Narayanan, 2021). The area is surveyed by Canonne (2020). Most closely related to our efficiency question, Kamath & Tzamos (2019) develop non-adaptive conditional-sampling algorithms, and Chakraborty et al. (2024) study bounded adaptivity for equivalence testing. The timing of experimental choices also appears in active hypothesis testing. This line begins with sequential experiment design and studies how actions chosen from past observations affect testing 1

Preprint

performance (Chernoff, 1959; Naghshvar & Javidi, 2013b; Nitinawarat et al., 2013). In particular, Naghshvar & Javidi (2013a) compare adaptive and non-adaptive action selection for a specified finite collection of hypotheses, actions, and observation laws. Their guarantees depend on the given observation model. Adaptive question selection has a long history in psychometrics and computerized testing (Weiss, 1982; Gershon, 2005; Ghosh & Lan, 2021). Item-response models have also been used to analyze the difficulty and discriminative value of NLP evaluation examples (Lalor et al., 2016; Rodriguez et al., 2021; Maia Polo et al., 2024). Recent model-evaluation work uses predicted item difficulty or current model performance to choose questions more efficiently (Truong et al., 2025; Zhuang et al., 2025; Ding et al., 2026), and active estimators reduce the number of benchmark items needed for score estimation (Wu et al., 2026). These works either fix a particular testing objective or a specified hypothesis-and-action model. They do not characterize learnability for arbitrary pairs of distribution classes under conditional queries, or determine the worst-case cost of fixing all queries in advance. We address both questions. We study this question through conditional distribution testing on a finite outcome space X = [N ]. The N outcomes are the behavior categories distinguished by an evaluation, such as answer choices, tool actions, or judge labels. The unknown object is a full-support distribution P on X . A binary testing target specifies two hypothesis classes, P0 and P1 , with the promise that P ∈ P0 ∪ P1 . The tester must determine which class contains P . We compare adaptive and non-adaptive testers under the same conditional-query model. Both may select any nonempty event A ⊆ X and receive a sample from P (· | A). The only difference is when the queried events are chosen. A non-adaptive tester fixes all events before observing any samples, whereas an adaptive tester may select each event from the observed history. The model raises two questions. First, which pairs (P0 , P1 ) are learnable at all, in the sense that their worst-case error can be driven arbitrarily close to zero as the query budget grows? Second, among learnable pairs, how many additional queries are needed when all queried events must be fixed in advance? Since X has 2N − 1 nonempty events, a non-adaptive tester could sample every event sufficiently many times and then replay any finite-round adaptive policy. This elementary argument gives an exponential upper bound, but does not reveal the true cost of removing adaptive rounds. We seek both an exact learnability criterion and the smallest worst-case increase in query count. We call the ratio between the optimal non-adaptive and adaptive query complexities at a common error level the adaptivity gap. Our contributions are summarized below. • An exact characterization of conditional-query learnability. Define the pairwise conditional map Θ by Θij (P ) = P (i | {i, j}). A pair of hypothesis classes is learnable if and only if its two images under Θ have positive pairwise separation. When this separation is zero, the optimal worst-case error under either adaptive or non-adaptive testing is exactly 1/2 for every finite query budget. • A universal non-adaptive simulation bound. For any T -round adaptive policy and any
ρ ∈ (0, 1), we construct a randomized non-adaptive procedure using O N 2 (T + log(1/ρ)) pair queries whose simulated transcript is within ρ in total variation of the adaptive transcript, uniformly over all full-support distributions. The entire pair sequence is chosen before any response is observed, and the bound does not depend on the cardinality or pairwise separation of the hypothesis classes. • Tightness of the non-adaptive simulation bound. We construct a family whose adaptive query complexity is independent of N at fixed error, while every non-adaptive test requires Ωε (N 2 ) queries. This example shows that the quadratic dependence on N in the preceding simulation bound is unavoidable and gives the exact worst-case rate GN (ε) = Θε (N 2 ). Our results replace the exponential enumeration argument with a tight quadratic guarantee. A static
conditional benchmark can match any T -query adaptive evaluation using O N 2 (T + log(1/ρ)) pair queries chosen in advance, up to transcript error ρ, and the lower bound shows that the quadratic dependence on N can be unavoidable. Thus, within this model, interaction can reduce the required number of tests by a quadratic factor, but cannot produce a larger worst-case gain from adaptive 2

Preprint

selection alone. The apparent exponential branching of an interactive evaluation does not translate into exponential query savings.

2

P ROBLEM S ETUP

We model an evaluated system by an unknown distribution P over a finite set of observable outcomes. The evaluation must distinguish between two alternatives, P ∈ P0 and P ∈ P1 , using samples from conditional distributions selected by the tester. Choosing every conditioning event before observing any responses gives the non-adaptive protocol, while allowing later events to depend on earlier observations gives the adaptive protocol. This section defines both protocols and the quantities used to compare them. Hypotheses and conditional queries.

Let X be a finite outcome space with |X | = N , and let

∆+ (X ) := {P ∈ ∆(X ) : P (x) > 0 for every x ∈ X } . The testing problem is specified by two nonempty hypothesis classes P0 , P1 ⊆ ∆+ (X ). These classes may be arbitrary subsets of ∆+ (X ) and need not be finite. Under a hidden label b ∈ {0, 1}, the unknown distribution P is selected from Pb . The tester observes P only through conditional queries and must estimate b. The query family is the collection of nonempty events A := 2X \ {∅}. A query A ∈ A returns a fresh observation from P (x)1{x ∈ A} PA (x) := P (x | A) = . P (A) Full support ensures that every nonempty event is a valid conditional query. Adaptive and non-adaptive testers. An adaptive tester may select each event after observing the responses to its earlier queries. After t − 1 queries, the complete observed history is Ht−1 := (A1 , X1 , . . . , At−1 , Xt−1 ). A randomized adaptive policy selects At ∼ πt (· | Ht−1 ),

Xt ∼ PAt ,

where πt (· | Ht−1 ) is a probability distribution on A. After T queries, a possibly randomized decision rule outputs bb ∈ {0, 1}. A non-adaptive tester instead draws the entire query vector A1:T before observing any samples. The queries may be randomized, correlated, and repeated, but their joint distribution cannot depend on the observations. Risk, learnability, and the adaptivity gap. The minimax risk records the smallest worst-case error achievable with a fixed query budget. The adaptive minimax risk at horizon T is RTad (P0 , P1 ) :=

max sup Pr(bb ̸= b).

inf

adaptive testers b∈{0,1} P ∈Pb P

The non-adaptive risk RTna (P0 , P1 ) is defined by restricting the infimum to non-adaptive testers. Therefore 1 RTad (P0 , P1 ) ≤ RTna (P0 , P1 ) ≤ . 2 Learnability asks whether this risk can be made arbitrarily small as the query budget grows. We call (P0 , P1 ) adaptively conditionally learnable if RTad (P0 , P1 ) → 0 as T → ∞. Non-adaptive conditional learnability is defined in the same way using RTna . For a target error ε ∈ (0, 1/2), define  ⋆ Tad (ε; P0 , P1 ) := inf T ≥ 0 : RTad (P0 , P1 ) ≤ ε , ⋆ and define Tna (ε; P0 , P1 ) analogously. The infimum of an empty set is ∞.

For a class pair with finite adaptive query complexity at error ε, its fixed-error adaptivity gap is Gapε (P0 , P1 ) := 3

⋆ Tna (ε; P0 , P1 ) ⋆ (ε; P , P ) . Tad 0 1

Preprint

For a fixed outcome-space size N , the worst-case adaptivity gap is GN (ε) :=

sup P0 ,P1 ⊆∆+ (X ) ⋆ 1≤Tad (ε;P0 ,P1 )<∞

Gapε (P0 , P1 ).

We count conditional queries and place no restriction on the computation used to choose the queries or form the final decision.

3

E XACT C HARACTERIZATION OF C ONDITIONAL -Q UERY L EARNABILITY

This section gives an exact criterion for conditional-query learnability. The response law to a query on {i, j} depends on P only through the relative weight P (i)/P (j), and the collection of all such ratios determines P . We show that two hypothesis classes are learnable precisely when their images under this pairwise representation have a positive uniform separation. Sufficiency follows by estimating every pair in advance. Necessity follows by showing that pairwise closeness controls every conditional query and therefore every finite adaptive transcript. Pairwise
representation and main theorem. Fix an arbitrary labeling X = {1, . . . , N } and let M := N2 . For 1 ≤ i < j ≤ N , define
P (i) , Θ(P ) := θij (P ) i<j ∈ (0, 1)M . P (i) + P (j) For i < j, these coordinates determine the ratio P (i) θij (P ) = . P (j) 1 − θij (P ) P The reverse ratio is its reciprocal. Together with the normalization i P (i) = 1, these ratios determine P . The same pairwise normalization underlies classical probabilistic models for paired comparisons (Bradley & Terry, 1952; Ford, 1957; Hunter, 2004). For P, Q ∈ ∆+ (X ), write θij (P ) := P (i | {i, j}) =

dpair (P, Q) := ∥Θ(P ) − Θ(Q)∥∞ . The pairwise separation between the two hypothesis classes is ∆pair (P0 , P1 ) :=

inf

P ∈P0 , Q∈P1

dpair (P, Q).

Theorem 3.1 (Exact learnability criterion). Suppose N ≥ 2. The following statements are equivalent. 1. ∆pair (P0 , P1 ) > 0. 2. RTna (P0 , P1 ) → 0 as T → ∞. 3. RTad (P0 , P1 ) → 0 as T → ∞. If ∆pair (P0 , P1 ) = 0, then for every finite T , RTad (P0 , P1 ) = RTna (P0 , P1 ) =

1 . 2

If ∆ := ∆pair (P0 , P1 ) > 0, then for every ε ∈ (0, 1/2),   8 2M ⋆ Tna (ε; P0 , P1 ) ≤ M log . ∆2 ε Sufficiency: positive separation gives a non-adaptive test. Suppose ∆ := ∆pair (P0 , P1 ) > 0. b collect the empirical frequencies. For b ∈ {0, 1}, Query every pair the same number of times and let Θ define b − Θ(Q)∥∞ , Db := inf ∥Θ Q∈Pb

b − Θ(P )∥∞ < ∆/4, and output the label with smaller Db . If the true distribution P ∈ Pb satisfies ∥Θ then Db < ∆/4. The triangle inequality gives D1−b ≥ ∆ − ∆/4 = 3∆/4. Hoeffding’s inequality and a union bound over the M pairs give this event with probability at least 1 − ε using the number of queries stated in the theorem. Thus positive separation already yields a non-adaptive test. 4

Preprint

Necessity: pairwise closeness controls every query. Fix P, Q ∈ ∆+ (X ) and let d := dpair (P, Q). Pairwise closeness first bounds the response laws under every conditional query. Applying this bound at each round then controls the law of the entire adaptive transcript: dpair (P, Q) = d

=⇒ =⇒

max TV(PA , QA ) ≤ (N − 1)d,
TV LP (HT ), LQ (HT ) ≤ T (N − 1)d. ∅̸=A⊆X

From pairs to arbitrary events. Fix a nonempty event A and write p = PA and q = QA . For distinct i, j ∈ A, conditioning once more on {i, j} gives pi |pi qj − qi pj | qi ≤ d. = − (pi + pj )(qi + qj ) pi + p j qi + qj Let I+ := {i : pi ≥ qi } and I− := A \ I+ . Total variation can be written as the mass transported across this cut: X X TV(p, q) = (pi qj − qi pj ) i∈I+ j∈I−

≤d

X

(pi + pj )(qi + qj )

{i,j}⊆A

! = d 1 + (|A| − 2)

X

pi qi

≤ (|A| − 1)d.

i∈A

Consequently, max TV(PA , QA ) ≤ (N − 1)dpair (P, Q).

∅̸=A⊆X

(1)

From events to adaptive transcripts. Couple two executions of the same tester under P and Q. As long as their histories agree, use the same internal randomness, so the tester selects the same next event in both executions. Couple the two conditional observations optimally. Equation (1) bounds the probability that they first disagree at any round by (N − 1)dpair (P, Q). A union bound over T rounds therefore gives
TV LP (HT ), LQ (HT ) ≤ T (N − 1)dpair (P, Q). Zero separation forces risk 1/2. Suppose ∆pair (P0 , P1 ) = 0 and fix any finite T -query adaptive tester. The conclusion is immediate for T = 0. For T ≥ 1 and every η > 0, there exist P ∈ P0 and Q ∈ P1 with dpair (P, Q) < η/[T (N − 1)]. Their transcript distributions are then less than η apart in total variation. For any decision rule, its error probabilities under P and Q sum to at least 1 − η, so its worst-case error is at least (1 − η)/2. Letting η tend to zero and comparing with a fair random guess gives the exact minimax risk 1/2. Appendix A supplies the concentration details and the full formal proof. Thus pairwise separation exactly characterizes conditional-query learnability. We now compare the query counts of adaptive and non-adaptive tests on the learnable problems.

4

N ON -A DAPTIVE S IMULATION OF A DAPTIVE Q UERIES

The proof uses the coupling-from-the-past (CFTP) idea of Propp & Wilson (1996), in the read-once form of Wilson (2000). Fix one round after the adaptive policy has selected an event A. We have only pair samples collected before A was known, and we need one draw from PA . Estimating the pair profile and reconstructing P is possible but unnecessary: each pair sample instead gives a random map on A. One such map leaves the law PA unchanged, and once a composition of maps sends every starting state to the same output, that output itself has law PA . We first formalize this one-round construction, then bound its cost and apply it successively to all T adaptive rounds. 5

Preprint

Theorem 4.1 (Universal transcript simulation). Let N ≥ 2, let T
≥ 1, and let π be any randomized adaptive policy using T conditional queries. Write M = N2 . For every ρ ∈ (0, 1), there is a randomized non-adaptive procedure that makes at most    1 L := 8M T + log (2) ρ e T such that, for every P ∈ ∆+ (X ), pair queries and produces a T -round simulated transcript H
e T ), LP (H π ) ≤ ρ. TV LP (H T Consequently, any decision rule with error at most ε under π has error at most ε + ρ when applied to the simulated transcript. Construction. The procedure first collects a fixed random sequence of pair samples. After a later event A is selected, a stored sample (e, y) defines ΦA e,y : A → A by  y, e ⊆ A and x ∈ e, ΦA x ∈ A. e,y (x) := x, otherwise, It merges the endpoints of e at y when e ⊆ A and is otherwise the identity. Algorithm 1 composes unused maps until every possible starting state has the same output. Samples are never reused; if the stream is exhausted, a fixed rule completes a valid transcript without querying P . Algorithm 1 Simulating a T -round adaptive policy from pair samples chosen in advance Require: policy π, stream length L Precommitted data collection
1: Draw E1:L i.i.d. uniformly from X2 , submit all queries, and store Ys ∼ PEs . Offline reconstruction e 0 ← ∅. 2: Set s ← 1 and H 3: for t = 1, . . . , T do e t−1 ). 4: Draw At ∼ πt (· | H 5: Set G ← idAt . 6: while G is not constant on At do 7: if s > L then 8: return a valid T -round completion under π. 9: end if t 10: G ← G ◦ ΦA Es ,Ys and s ← s + 1. 11: end while et be the common value of G on At . 12: Let X e t ← (H e t−1 , At , X et ). 13: Set H 14: end for eT 15: return H Step 1: one pair sample preserves the target law. Fix A and one unused pair sample (e, Y ). If e ̸⊆ A, then ΦA e,Y is the identity. If e ⊆ A, let X ∼ PA be independent of Y ∼ Pe . For z ∈ e,
P (e) P (z) Pr ΦA = PA (z). e,Y (X) = z = PA (e)Pe (z) = P (A) P (e) For z ∈ A\e, the mass is unchanged. Thus every unused map preserves PA . Equivalently, conditional on X ∈ e, the law of X is exactly the law Pe used to redraw the pair. This uses the nested-conditioning relation PA (· | e) = Pe for e ⊆ A; it need not hold for a generic prompt-response kernel. A Step 2: coalescence produces an exact sample. Write ΦA 1 , Φ2 , . . . for the successive maps used for A and set A A CnA := ΦA 1 ◦ Φ2 ◦ · · · ◦ Φn ,

τA := inf{n : CnA is constant on A}. 6

Preprint

A Interpret ΦA 1 as the update from time −1 to the present, Φ2 as the update from time −2 to time −1, and so on. Thus CnA maps a state at time −n to the fixed present. For analysis, start with an independent Zn ∼ PA at time −n. Repeated application of Step 1 gives CnA (Zn ) ∼ PA .

If CnA is constant, its output no longer depends on the unavailable initial state Zn . The order of composition ensures more: if CnA ≡ w, then CnA ◦ ΦA n+1 ≡ w. We are extending the starting time farther into the past while keeping the present fixed, so an already determined present value cannot change. Let WA be this common value when coalescence first occurs. On {τA ≤ n}, CnA (Zn ) = WA . Step 3 shows that τA < ∞ almost surely, and therefore TV(L(WA ), PA ) ≤ Pr(τA > n) → 0. Hence WA ∼ PA . Step 3: how many pair samples are needed. The right-composition order above is convenient for exactness but awkward to count. For each fixed n, the maps are i.i.d., so reversing them does not change their joint law. We may therefore run the same maps forward and track the set of possible states. If k states remain, the next map reduces this number to k − 1 exactly when its uniform pair has both endpoints in that set, an event of probability
k pk =

2

M

.

It follows that, for |A| ≥ 2, d

τA =

|A| X

Gk ,

Gk ∼ Geom

k=2

k 2

! independently.

M

(3)

Consequently, EτA < 2M,

E exp

τ

A



8M

≤ e.

The final transition, from two possible states to one, already has expected waiting time M = N2 . This explains the quadratic scale. Appendix B gives the geometric-waiting-time and exponentialmoment calculations. Step 4: from one response to the adaptive transcript. Let Ht∞ be the reconstruction from an infinite pair-sample stream and let St be the total number of samples consumed through round t. After round t − 1, the unused suffix is still i.i.d. and independent of the simulated history because St−1 is a stopping time. Conditional on the next selected event At , Steps 1–2 therefore give ∞ Xt∞ | Ht−1 , At ∼ PAt . d

Induction gives HT∞ = HTπ . The conditional exponential-moment calculation in Appendix B also gives    1 Pr ST > 8M T + log ≤ ρ. ρ Couple the finite and infinite reconstructions using the same policy randomness and first L pair samples. They agree on {ST ≤ L}, so with the choice of L in equation (2),
e T ), LP (HTπ ) ≤ Pr(ST > L) ≤ ρ. TV LP (H This proves Theorem 4.1. Corollary 4.2 (Quadratic upper bound on the adaptivity gap). For every fixed ε ∈ (0, 1/2), GN (ε) = Oε (N 2 ). Repeat an ε-error adaptive tester Oε (1) times so that its majority vote has error at most ε/2, then apply Theorem 4.1 with ρ = ε/2. This proves the corollary. The exact finite-error bound and the case of an unattained minimax infimum appear in Appendix B. The next section shows that the quadratic factor cannot be improved. 7

Preprint

5

A M ATCHING Q UADRATIC L OWER B OUND

Corollary 4.2 shows that an O(N 2 ) increase in query count is always sufficient to remove adaptive rounds. We now show that this factor is sometimes necessary. The unknown distribution will be indexed by a class label b ∈ {0, 1} and two additional indices (j, k) ∈ [m]2 . The tester must output b; it need not output j or k. Queries to two fixed sets determine j and k but have the same law under both labels. Once those indices are known, one particular pair distinguishes the labels. Construction of the hard family. I = {a1 , . . . , am },

Fix m ≥ 2, let N = 4m, and partition the outcome space into

J = {b1 , . . . , bm },

U = {u1 , . . . , um },

V = {v1 , . . . , vm }.

For every b ∈ {0, 1} and (j, k) ∈ [m]2 , we define a distribution Pb,j,k . Write Bjk := {uj , vk }. The construction is chosen to produce the following three conditional laws. Query I J Bjk

Conditional behavior Pb,j,k (aj | I) = 3/4 for both labels Pb,j,k (bk | J) = 3/4 for both labels P0,j,k (uj | Bjk ) = 3/4, P1,j,k (uj | Bjk ) = 1/4

What it determines index j index k label b

The following masses realize these laws. On I, set Pb,j,k (aj ) =

3 , 16

Pb,j,k (ar ) =

1 16(m − 1)

(r ̸= j),

and define the masses on J analogously with bk in place of aj . Each of I and J has total mass 1/4, independently of the label. For the remaining points, let η = m−4 and Z = 2m − 2 + 4η. Every point in U ∪ V outside {uj , vk } has mass 1/(2Z). On Bjk , define    

3η η η 3η P0,j,k (uj ), P0,j,k (vk ) = , , P1,j,k (uj ), P1,j,k (vk ) = , . 2Z 2Z 2Z 2Z All masses are positive and sum to one. The two distributions with the same (j, k) differ only at uj and vk . The label signal is hidden in one very light pair Bjk . Conditioning exactly on Bjk cancels its small total mass and reveals the constant 3/4-versus-1/4 bias. If a query contains any additional ordinary atom, that atom dilutes the label-dependent discrepancy to O(η). We choose η = m−4 so that even O(m2 ) off-target queries contribute only o(1) total KL divergence; therefore a non-adaptive tester essentially has to guess which of the m2 target pairs to query. Define (m)

Pb

:= {Pb,j,k : j, k ∈ [m]}.

Theorem 5.1 (Matching quadratic lower bound). For every m ≥ 2 and ε ∈ (0, 1/2), write nε := ⌈8 log(3/ε)⌉. There is a constant cε > 0 depending only on ε such that (m)

⋆ Tad (ε; P0

(m)

, P1

) ≤ 3nε ,

(m)

⋆ cε m2 ≤ Tna (ε; P0 2

(m)

, P1

) ≤ (m2 + 2)nε .

(4)

2

Hence this family has adaptivity gap Θε (m ) = Θε (N ). After padding the construction with at most three common atoms, GN (ε) = Ωε (N 2 ) for every N ≥ 8. Step 1: locate the target pair adaptively. Query I independently nε times and let b j be the unique index whose atom appears more than nε /2 times, using an arbitrary fallback if no such index exists. Since aj appears with probability 3/4, Hoeffding’s inequality gives Pr(b j ̸= j) ≤ e−nε /8 . The same procedure on J produces b k with the same error bound. After observing these samples, query Bbj bk another nε times and output zero if ubj appears more than nε /2 times. Conditional on b j = j and b k = k, this final decision has error at most e−nε /8 . Since this quantity is at most ε/3, a union bound proves the adaptive bound in equation (4). 8

Preprint

Step 2: only the target pair has a constant separation. Fix s = (j, k), write Pb,s := Pb,j,k , and abbreviate P0 = P0,s , P1 = P1,s , and Bs = Bjk . On the target pair,

1 KL (P0 )Bs ∥ (P1 )Bs = KL (3/4, 1/4) ∥ (1/4, 3/4) = log 3 =: d0 . 2 For A ̸= Bs , the two conditional laws either coincide or A contains a common atom whose mass dominates the total discrepancy on uj and vk . The normalization calculation in Appendix C, along with the fact that every conditional likelihood ratio lies between 1/9 and 9, gives

TV (P0 )A , (P1 )A ≤ 16η, KL (P0 )A ∥ (P1 )A ≤ 32(log 9)η =: C0 η (A ̸= Bs ). (5) Thus a query to Bs has a constant KL divergence, whereas every other query has divergence of order m−4 . Step 3: some target pair receives at most T /m2 queries. Consider any randomized non-adaptive tester using T queries. For each s = (j, Pk), let Ns count how many submitted queries are exactly Bs . For every realized query vector, s∈[m]2 Ns ≤ T . The distribution of this query vector is the same for every unknown Pb,j,k . Averaging over the m2 indices therefore gives one s such that ENs ≤ T /m2 . This is the point at which nonadaptivity is used: after observing responses from I and J, an adaptive tester may choose a different target pair for each (j, k). Step 4: worst-case accuracy requires T = Ω(m2 ). For the selected s, the KL chain rule and equation (5) give  
d0 C0 KL LP0,s (HT ) ∥ LP1,s (HT ) ≤ d0 ENs + C0 ηT ≤ T + 4 . m2 m If the tester has worst-case error at most ε, then its error on both P0,s and P1,s is at most ε. Their transcript laws must therefore have total variation distance at least 1 − 2ε. Pinsker’s inequality, one of the standard relations between statistical divergences (Ali & Silvey, 1966; Reid & Williamson, 2011; Sason & Verdú, 2016), yields 2(1 − 2ε)2 T ≥ ≥ cε m2 . (6) log 3 32 log 9 + 2m2 m4 For the matching upper bound, query I, J, and every Brs exactly nε times, then apply the same majority rules to the stored samples. This uses (m2 + 2)nε queries and completes equation (4). Appendix C verifies the off-target bound, a valid value of cε , and padding to every N ≥ 8.

6

S COPE AND L IMITATIONS

The upper and lower bounds identify the exact worst-case quadratic cost of removing adaptivity in this model. The model assumes a finite full-support outcome space and exact conditional sampling from every nonempty event. It therefore applies directly when an evaluation has a finite outcome representation and can implement the required conditional queries. Query complexity counts conditional samples, not the cost of specifying or realizing a conditioning event. Finally, the lower bound is worst-case and does not imply that typical evaluation tasks attain a quadratic gain from adaptive selection. AI USE STATEMENT Generative AI tools assisted with developing the theoretical formulation, formulating and checking mathematical claims, proof development, literature search, and manuscript drafting and editing. All AI-assisted arguments, citations, and text were manually reviewed. The authors take responsibility for the final content of this work, including all text and claims produced with the aid of generative AI. R EPRODUCIBILITY STATEMENT The formal model and all assumptions are stated in Sections 2 and 3. Complete proofs of the learnability criterion, the non-adaptive simulation bound, and the quadratic lower bound are provided in the appendix. 9

Preprint

R EFERENCES Jayadev Acharya, Clément L. Canonne, and Gautam Kamath. A chasm between identity and equivalence testing with conditional queries. Theory of Computing, 14(19):1–46, 2018. doi: 10.4086/toc.2018.v014a019. Syed M. Ali and Samuel D. Silvey. A general class of coefficients of divergence of one distribution from another. Journal of the Royal Statistical Society: Series B, 28(1):131–142, 1966. doi: 10.1111/j.2517-6161.1966.tb00626.x. Ralph Allan Bradley and Milton E. Terry. Rank analysis of incomplete block designs: I. the method of paired comparisons. Biometrika, 39(3/4):324–345, 1952. doi: 10.2307/2334029. Clément L. Canonne. A survey on distribution testing: Your data is big. but is it blue? Theory of Computing, 9, 2020. doi: 10.4086/toc.gs.2020.009. Clément L. Canonne, Dana Ron, and Rocco A. Servedio. Testing equivalence between distributions using conditional samples. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1174–1192, 2014. doi: 10.1137/1.9781611973402.87. Clément L. Canonne, Dana Ron, and Rocco A. Servedio. Testing probability distributions using conditional samples. SIAM Journal on Computing, 44(3):540–616, 2015. doi: 10.1137/130945508. Diptarka Chakraborty, Sourav Chakraborty, Gunjan Kumar, and Kuldeep S. Meel. Equivalence testing: The power of bounded adaptivity. In Proceedings of the 27th International Conference on Artificial Intelligence and Statistics, pp. 3592–3600, 2024. Sourav Chakraborty, Eldar Fischer, Yonatan Goldhirsh, and Arie Matsliah. On the power of conditional samples in distribution testing. In Proceedings of the 4th Innovations in Theoretical Computer Science Conference, 2013. doi: 10.1145/2422436.2422497. Herman Chernoff. Sequential design of experiments. The Annals of Mathematical Statistics, 30(3): 755–770, 1959. doi: 10.1214/aoms/1177706205. Xuanwen Ding, Chengjun Pan, Zejun Li, Jiwen Zhang, Siyuan Wang, and Zhongyu Wei. AutoJudger: An agent-driven framework for efficient benchmarking of MLLMs. In Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics, pp. 15009–15034, 2026. Moein Falahatgar, Ashkan Jafarpour, Alon Orlitsky, Venkatadheeraj Pichapati, and Ananda Theertha Suresh. Faster algorithms for testing under conditional sampling. In Proceedings of the 28th Conference on Learning Theory, volume 40, pp. 607–636, 2015. Lester R. Ford. Solution of a ranking problem from binary comparisons. The American Mathematical Monthly, 64(8):28–33, 1957. doi: 10.2307/2308513. Richard C. Gershon. Computer adaptive testing. Journal of Applied Measurement, 6(1):109–127, 2005. Aritra Ghosh and Andrew S. Lan. BOBCAT: Bilevel optimization-based computerized adaptive testing. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, pp. 2410–2417, 2021. doi: 10.24963/ijcai.2021/332. Dan Hendrycks, Collin Burns, Steven Basart, Andy Zou, Mantas Mazeika, Dawn Song, and Jacob Steinhardt. Measuring massive multitask language understanding. In International Conference on Learning Representations, 2021. David R. Hunter. MM algorithms for generalized Bradley–Terry models. The Annals of Statistics, 32 (1):384–406, 2004. doi: 10.1214/aos/1079120141. Gautam Kamath and Christos Tzamos. Anaconda: A non-adaptive conditional sampling algorithm for distribution testing. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 679–693, 2019.

10

Preprint

Douwe Kiela, Max Bartolo, Yixin Nie, Divyansh Kaushik, Atticus Geiger, Zhengxuan Wu, Bertie Vidgen, Grusha Prasad, Amanpreet Singh, Pratik Ringshia, Zhiyi Ma, Tristan Thrush, Sebastian Riedel, Zeerak Waseem, Pontus Stenetorp, Robin Jia, Mohit Bansal, Christopher Potts, and Adina Williams. Dynabench: Rethinking benchmarking in NLP. In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics, pp. 4110–4124, 2021. doi: 10.18653/v1/2021.naacl-main.324. John P. Lalor, Hao Wu, and Hong Yu. Building an evaluation scale using item response theory. In Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, pp. 648–657, 2016. doi: 10.18653/v1/D16-1062. Percy Liang, Rishi Bommasani, Tony Lee, Dimitris Tsipras, Dilara Soylu, Michihiro Yasunaga, Yian Zhang, Deepak Narayanan, Yuhuai Wu, Ananya Kumar, et al. Holistic evaluation of language models. Transactions on Machine Learning Research, 2023. Felipe Maia Polo, Lucas Weber, Leshem Choshen, Yuekai Sun, Gongjun Xu, and Mikhail Yurochkin. tinyBenchmarks: Evaluating LLMs with fewer examples. In Proceedings of the 41st International Conference on Machine Learning, volume 235, pp. 34303–34326, 2024. Mohammad Naghshvar and Tara Javidi. Sequentiality and adaptivity gains in active hypothesis testing. IEEE Journal of Selected Topics in Signal Processing, 7(5):768–782, 2013a. Mohammad Naghshvar and Tara Javidi. Active sequential hypothesis testing. The Annals of Statistics, 41(6):2703–2738, 2013b. doi: 10.1214/13-AOS1144. Shyam Narayanan. On tolerant distribution testing in the conditional sampling model. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, pp. 357–373, 2021. doi: 10.1137/1. 9781611976465.23. Yixin Nie, Adina Williams, Emily Dinan, Mohit Bansal, Jason Weston, and Douwe Kiela. Adversarial NLI: A new benchmark for natural language understanding. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pp. 4885–4901, 2020. doi: 10.18653/ v1/2020.acl-main.441. Sirin Nitinawarat, George K. Atia, and Venugopal V. Veeravalli. Controlled sensing for multihypothesis testing. IEEE Transactions on Automatic Control, 58(10):2451–2464, 2013. doi: 10.1109/TAC.2013.2261188. Christopher Potts, Zhengxuan Wu, Atticus Geiger, and Douwe Kiela. DynaSent: A dynamic benchmark for sentiment analysis. In Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics, pp. 2388–2404, 2021. doi: 10.18653/v1/2021.acl-long.186. James Gary Propp and David Bruce Wilson. Exact sampling with coupled markov chains and applications to statistical mechanics. Random Structures & Algorithms, 9(1–2):223–252, 1996. Mark D. Reid and Robert C. Williamson. Information, divergence and risk for binary experiments. Journal of Machine Learning Research, 12:731–817, 2011. Marco Tulio Ribeiro, Tongshuang Wu, Carlos Guestrin, and Sameer Singh. Beyond accuracy: Behavioral testing of NLP models with CheckList. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pp. 4902–4912, 2020. doi: 10.18653/v1/2020. acl-main.442. Pedro Rodriguez, Joe Barrow, Alexander Hoyle, John P. Lalor, Robin Jia, and Jordan Boyd-Graber. Evaluation examples are not equally informative: How should that change NLP leaderboards? In Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics, pp. 4486–4503, 2021. doi: 10.18653/v1/2021.acl-long.346. Igal Sason and Sergio Verdú. f -divergence inequalities. IEEE Transactions on Information Theory, 62(11):5973–6006, 2016. doi: 10.1109/TIT.2016.2603151. Aarohi Srivastava, Abhinav Rastogi, Abhishek Rao, et al. Beyond the imitation game: Quantifying and extrapolating the capabilities of language models. Transactions on Machine Learning Research, 2023. 11

Preprint

Tristan Thrush, Kushal Tirumala, Anmol Gupta, Max Bartolo, Pedro Rodriguez, Tariq Kane, William Gaviria Rojas, Peter Mattson, Adina Williams, and Douwe Kiela. Dynatask: A framework for creating dynamic AI benchmark tasks. In Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics: System Demonstrations, pp. 174–181, 2022. doi: 10.18653/v1/2022.acl-demo.17. Sang T. Truong, Yuheng Tu, Percy Liang, Bo Li, and Sanmi Koyejo. Reliable and efficient amortized model-based evaluation. In Proceedings of the 42nd International Conference on Machine Learning, volume 267, pp. 60238–60265, 2025. David J. Weiss. Improving measurement quality and efficiency with adaptive testing. Applied Psychological Measurement, 6(4):473–492, 1982. doi: 10.1177/014662168200600408. Colin White, Samuel Dooley, Manley Roberts, Arka Pal, Benjamin Feuer, Siddhartha Jain, Ravid Shwartz-Ziv, Neel Jain, Khalid Saifullah, Sreemanti Dey, Shubh-Agrawal, Sandeep Singh Sandha, Siddartha Venkat Naidu, Chinmay Hegde, Yann LeCun, Tom Goldstein, Willie Neiswanger, and Micah Goldblum. LiveBench: A challenging, contamination-limited LLM benchmark. In International Conference on Learning Representations, 2025. David Bruce Wilson. How to couple from the past using a read-once source of randomness. Random Structures & Algorithms, 16(1):85–113, 2000. Skyler Wu, Yash Nair, and Emmanuel J. Candès. Efficient evaluation of LLM performance with statistical guarantees. arXiv preprint arXiv:2601.20251, 2026. Lianmin Zheng, Wei-Lin Chiang, Ying Sheng, Siyuan Zhuang, Zhanghao Wu, Yonghao Zhuang, Zi Lin, Zhuohan Li, Dacheng Li, Eric P. Xing, Hao Zhang, Joseph E. Gonzalez, and Ion Stoica. Judging LLM-as-a-judge with MT-Bench and Chatbot Arena. In Advances in Neural Information Processing Systems, volume 36, pp. 46595–46623, 2023. doi: 10.52202/075280-2020. Yan Zhuang, Qi Liu, Zachary Pardos, Patrick C. Kyllonen, Jiyun Zu, Zhenya Huang, Shijin Wang, and Enhong Chen. Position: AI evaluation should learn from how we test humans. In Proceedings of the 42nd International Conference on Machine Learning, Position Paper Track, 2025.

12

Preprint

A

P ROOF OF THE L EARNABILITY C RITERION

We first prove the stability relation used in Section 3. Lemma A.1 (Pairwise stability of conditional queries). For any P, Q ∈ ∆+ (X ) and any nonempty A ⊆ X, TV(PA , QA ) ≤ (|A| − 1)dpair (P, Q). Consequently, equation (1) holds. Proof. The claim is immediate when |A| = 1. Suppose |A| = m ≥ 2 and write p = PA , q = QA , and d = dpair (P, Q). For every distinct i, j ∈ A, conditioning p and q again on {i, j} gives the same pairwise conditionals as conditioning P and Q directly. Hence |pi qj − qi pj | ≤ d. (pi + pj )(qi + qj )

(A.1)

Let I+ := {i ∈ A : pi ≥ qi } and I− := A \ I+ . Then X X TV(p, q) = (pi qj − qi pj ) i∈I+ j∈I−

≤d

X X

(pi + pj )(qi + qj )

i∈I+ j∈I−

≤d

X

(pi + pj )(qi + qj ).

{i,j}⊆A

The final sum equals (m − 1)

X i

pi qi +

X

pi qj = 1 + (m − 2)

X

pi qi ≤ m − 1.

i

i̸=j

This proves the lemma. Lemma A.2 (Adaptive transcript stability). Fix any randomized adaptive tester using T queries. If LP (HT ) and LQ (HT ) denote its transcript laws under P and Q, then
TV LP (HT ), LQ (HT ) ≤ T (N − 1)dpair (P, Q). Proof. Couple the two executions one round at a time. As long as their histories agree, use the same private randomness to select the same event At , then couple the two observations optimally. Lemma A.1 bounds the conditional probability that the observations first differ at round t by (N − 1)dpair (P, Q). A union bound over the T rounds bounds the probability that the transcripts differ. The coupling characterization of total variation gives the result. Proof of Theorem 3.1. First suppose ∆pair (P0 , P1 ) = 0. The case T = 0 follows directly from the absence of observations. For T ≥ 1 and every η > 0, choose P ∈ P0 and Q ∈ P1 such that dpair (P, Q) <

η . T (N − 1)

Lemma A.2 makes the two transcript laws closer than η in total variation. For any decision rule, the sum of its error probabilities under P and Q is at least 1 − η. Its worst-case error is therefore at least (1 − η)/2. Letting η tend to zero gives an adaptive minimax risk of at least 1/2. A fair random guess achieves 1/2, so the adaptive risk is exactly 1/2. The same conclusion follows for non-adaptive testing from RTad ≤ RTna ≤ 1/2. Now suppose ∆ := ∆pair (P0 , P1 ) > 0 and fix δ ∈ (0, 1/2). Query every pair   8 2M n := log ∆2 δ 13

Preprint

b = (θbij )i<j . times. Let θbij be the empirical frequency of outcome i from queries to {i, j}, and let Θ Hoeffding’s inequality and a union bound give     ∆ n∆2 b Pr ∥Θ − Θ(P )∥∞ ≥ ≤ 2M exp − ≤ δ. P 4 8 For b ∈ {0, 1}, define b − Θ(Q)∥∞ , Db := inf ∥Θ Q∈Pb

b − Θ(P )∥∞ < ∆/4, then Db < ∆/4 while and output a label minimizing Db . If P ∈ Pb and ∥Θ D1−b ≥ 3∆/4. The decision is therefore correct with probability at least 1 − δ, uniformly over both classes. The test is non-adaptive and uses M n queries. This proves the finite-sample bound and all three equivalences.

B

P ROOF OF THE U NIVERSAL T RANSCRIPT S IMULATION

Fix P ∈ ∆+ (X ). Let ωs = (Es , Ys ), s ≥ 1, be an i.i.d. source with   X Es ∼ Unif , Ys | Es = e ∼ Pe . 2 For a nonempty event A, let FsA := ΦA Es ,Ys be the random map defined in Section 4. Lemma B.1 (Stationarity of the pairwise maps). If X ∼ PA is independent of FsA , then FsA (X) ∼ PA . Proof. Condition on Es = e. If e ̸⊆ A, the map is the identity. If e ⊆ A, it fixes every state outside e and replaces a state in e by an independent draw from Pe . For z ∈ e, the resulting mass at z is P (e) P (z) = PA (z). P (A) P (e)

PA (e)Pe (z) =

The mass of each z ∈ A \ e is unchanged. Thus every conditional map kernel preserves PA , and averaging over Es proves the claim. Interpret F1A as the map from time −1 to time 0, F2A as the map from time −2 to time −1, and so on. Define CnA := F1A ◦ F2A ◦ · · · ◦ FnA ,

τA := inf{n ≥ 0 : CnA is constant on A}.

When τA < ∞, write WA for the common value of CτAA . Lemma B.2 (Exactness and coalescence cost). For every nonempty A ⊆ X , τA < ∞ almost surely and WA ∼ PA . If a := |A| ≥ 2, then
! a k X d 2 independently. (B.1) τA = Gk , Gk ∼ Geom M k=2

Consequently,  EτA = 2M and E exp

1 1− a

τ

A

8M For a = 1, the same conclusions hold with τA = 0.



 < 2M,

≤ e.

Proof. For each fixed n, reversal invariance of the i.i.d. maps gives d

F1A ◦ · · · ◦ FnA = FnA ◦ · · · ◦ F1A . 14

(B.2)

(B.3)

Preprint

Consider the forward image process S0 = A and Sr = FrA (Sr−1 ). If |Sr−1 | = k, its size decreases by one exactly when both endpoints of Er lie in Sr−1 . This event has probability
k pk :=

2

M

.

If the pair contains at most one state in the current image, the map either fixes that image or replaces one state by another and its size stays k. Thus the forward time to reach a singleton is the sum of independent geometric waiting times in equation (B.1). The reversal identity shows that this hitting time has the same distribution as τA . It is finite almost surely. Lemma B.1 also proves exactness by the standard coupling-from-the-past argument (Propp & Wilson, 1996). For completeness, let Zn ∼ PA be independent of the first n maps. Applying the maps from the oldest to the most recent gives CnA (Zn ) ∼ PA . On {τA ≤ n}, this value equals WA for every Zn . Hence TV(L(WA ), PA ) ≤ Pr(τA > n), and the right-hand side tends to zero. The mean follows from   a X 1 1 .
=2 1− k a 2

k=2

It remains to prove the exponential moment. Set s = 1/(8M ). If G ∼ Geom(p) on {1, 2, . . .}, then EesG =

pes es = , 1 − (1 − p)es 1−u

u :=

(1 − p)(es − 1) . p

For every p = pk , we have s ≤ p/8. Since s ≤ 1/8 and es − 1 ≤ 2s, it follows that u ≤ 1/4. Therefore 4s 4 log EesG = s − log(1 − u) ≤ s + u ≤ . 3 p Using independence in equation (B.1), log EesτA ≤ 4s =

1 2

a X 1

k=2 a X k=2

pk 1
k 2

1 = 1 − ≤ 1, a which proves equation (B.3). Proof of Theorem 4.1. First allow an infinite i.i.d. source (ωs )s≥1 . Draw the private randomness of π independently. At round t, the policy chooses At from the simulated history. Starting at the next et = WA . unused source element, run the construction above until its maps coalesce on At , and set X t The number of elements read is a stopping time for the fresh source segment. The strong Markov property of an i.i.d. sequence implies that the unused tail is again i.i.d. and independent of the maps already consumed. This is the read-once coupling-from-the-past construction of Wilson (2000). By et ∼ PA . Induction over t therefore shows that Lemma B.2, conditionally on the simulated history, X t the infinite-stream simulated transcript has exactly the same law as HTπ . PT Let τt be the number of source elements consumed at round t and let ST = t=1 τt . Equation (B.3) holds conditionally on every past simulated history, uniformly over the selected event. Iterating conditional expectations gives   ST ≤ eT . E exp 8M 15

Preprint

Markov’s inequality now yields      1 1 T Pr ST > 8M T + log ≤ exp −T − log e ρ ρ = ρ.

(B.4)

The finite simulation chooses the L pairs in equation (2) before observing any response and runs the same construction until either all T rounds are simulated or the source is exhausted. In the latter case a fixed completion rule returns a valid T -round transcript. Couple it to the infinite construction using the same first L source elements. Their transcripts agree unless ST > L, an event of probability at most ρ by equation (B.4). The coupling characterization of total variation proves the theorem. Applying the same decision rule changes its error by at most ρ. Proof of Corollary 4.2. Suppose a T -query adaptive tester has worst-case error at most ε < 1/2. For any δ ∈ (0, 1/2), let Kε,δ be the smallest odd integer at least 2 2 log . (1 − 2ε)2 δ Run K = Kε,δ independent copies and take a majority vote. Hoeffding’s inequality gives error at most   δ K(1 − 2ε)2 exp − ≤ . 2 2 This amplified tester uses KT adaptive queries. Apply Theorem 4.1 with ρ = δ/2. The simulated tester has error at most δ and uses at most    2 8M Kε,δ T + log (B.5) δ pair queries. ⋆ For the fixed-error gap, set T = Tad (ε; P0 , P1 ) and δ = ε. If the minimax infimum at horizon T is not attained, choose a T -query adaptive tester with error below any fixed ε̄ ∈ (ε, 1/2) and apply the same argument with Kε̄,ε . Since the definition
of GN (ε) restricts to T ≥ 1, division by T gives a N constant depending only on ε times M = 2 .

C

P ROOF OF THE Q UADRATIC L OWER B OUND

Proof of Theorem 5.1. Fix m ≥ 2 and ε ∈ (0, 1/2), and write nε = ⌈8 log(3/ε)⌉. The masses in the construction are positive. Moreover, 2m − 2 + 4η 1 1 Pb,j,k (U ∪ V ) = = , Pb,j,k (I) = Pb,j,k (J) = , 4 2Z 2 so each Pb,j,k is a full-support probability distribution. Conditional on I, the distinguished atom aj has probability 3/4. Let b j be the unique index whose atom appears more than nε /2 times among nε samples from Pb,j,k (· | I), with a fixed fallback when no such index exists. Hoeffding’s inequality gives
Pr(b j ̸= j) ≤ Pr Bin(nε , 3/4) ≤ nε /2 ≤ e−nε /8 . The same procedure using J gives Pr(b k ̸= k) ≤ e−nε /8 . Conditional on b j = j and b k = k, thresholding the frequency of uj in nε samples from Bjk at 1/2 has error at most e−nε /8 under either label. Since 3e−nε /8 ≤ ε, the adaptive tester uses 3nε queries and has worst-case error at most ε. A non-adaptive tester obtains the same error by querying I and J nε times each and every pair Brs = {ur , vs } nε times before observing any response. It then uses the samples from Bbj bk . This proves both upper bounds in equation (4). It remains to prove the non-adaptive lower bound. Fix s = (j, k), write Pb,s := Pb,j,k , and abbreviate P0 = P0,s , P1 = P1,s , and Bs = Bjk . The target pair satisfies

1 d0 := KL (P0 )Bs ∥ (P1 )Bs = KL (3/4, 1/4) ∥ (1/4, 3/4) = log 3. 2 16

Preprint

We next bound every other query. For a nonempty event A, let µA = (P0 )A and νA = (P1 )A . The unconditional likelihood ratio P0 (x)/P1 (x) belongs to {1/3, 1, 3}, which implies µA (x) 1 ≤ ≤9 9 νA (x)

(x ∈ A).

For positive finite measures α and β on A, set a = α(A) and b = β(A). Then X α(x)

2 TV(αA , βA ) =

a

x∈A

−

β(x) b

P ≤ Since |a − b| ≤

x∈A |α(x) − β(x)|

a

+

|a − b| . a

P

x∈A |α(x) − β(x)|, and the same inequality holds after exchanging a and b,

P TV(αA , βA ) ≤

x∈A |α(x) − β(x)| . min{α(A), β(A)}

The distributions P0 and P1 differ only at uj and vk , with unconditional ℓ1 discrepancy 2η/Z. If A contains neither active atom, or if it is a singleton active atom, then µA = νA . In every other case with A ̸= Bs , the event A contains a common atom. Every common atom has mass at least 1/[16(m − 1)] under both labels. For inactive atoms in U ∪ V , this follows from Z ≤ 8(m − 1). Since Z ≥ 2(m − 1), the preceding normalization inequality gives TV(µA , νA ) ≤

2η/Z ≤ 16η 1/[16(m − 1)]

(A ̸= Bs ).

If two distributions µ and ν have likelihood ratios in [1/R, R], then X µ(x) KL(µ∥ν) + KL(ν∥µ) = (µ(x) − ν(x)) log ν(x) x ≤ 2(log R) TV(µ, ν). Consequently, KL(µA ∥νA ) ≤ 32(log 9)η =: C0 η

(A ̸= Bs ).

Now fix an arbitrary randomized non-adaptive tester using T queries. Its query vector A1:T has the PT 2 same law s = t=1 1{At = Bs }. P under every distribution in the two classes. For s ∈ [m] , let N Since s∈[m]2 Ns ≤ T for every realized query vector, there is an s ∈ [m]2 for which ENs ≤ T /m2 . Conditional on the query vector, the responses are independent. The KL chain rule therefore gives
KL LP0,s (HT ) ∥ LP1,s (HT ) " T # X
=E KL (P0,s )At ∥ (P1,s )At t=1

 ≤ d0 ENs + C0 ηT ≤ T

d0 C0 + 4 m2 m

 .

If the tester has worst-case error at most ε, data processing through its decision rule implies that these transcript laws have total variation at least 1 − 2ε. Pinsker’s inequality yields   d0 C0 2 2(1 − 2ε) ≤ T + 4 . m2 m For m ≥ 2,

1 log 3 + 8 log 9 d0 C0 + 4 ≤ 2 . 2 m m m2

Thus equation (6) holds with 2(1 − 2ε)2 . 2 log 3 + 8 log 9

cε := 1

17

Preprint

Since a zero-query test has worst-case error at least 1/2, the adaptive query complexity of this family is at least one. Combining this fact with the three bounds in equation (4) shows that its adaptivity gap is Θε (m2 ) = Θε (N 2 ). Finally, let N ≥ 8, set m = ⌊N/4⌋, and write r = N − 4m. The case r = 0 is already covered. If r > 0, add atoms c1 , . . . , cr and define 7 Peb,j,k (x) = Pb,j,k (x) 8

(x ∈ I ∪ J ∪ U ∪ V ),

1 Peb,j,k (cℓ ) = . 8r

e(N ) = {Peb,j,k : j, k ∈ [m]}. The masses sum to 7/8 + 1/8 = 1, so these are full-support Let P b distributions on an outcome space of size N . Conditional laws on events contained in the original four blocks are unchanged, so the adaptive upper bound and the target-pair divergence remain unchanged. Every off-target event that distinguishes the labels contains a common atom. Each such atom has mass at least 7/(128m). Indeed, this follows from the original masses for atoms in I ∪ J, from Z ≤ 8m for inactive atoms in U ∪ V , and from r ≤ 3 and 1/(8r) ≥ 7/(128m) for the new atoms. The unconditional ℓ1 discrepancy is 7η 7η 7 2η = ≤ , 8Z 4Z 4m where Z ≥ m. Hence every off-target conditional total variation is at most 32η. The conditional likelihood ratios remain in [1/9, 9], so every off-target KL divergence is at most 64(log 9)η. For es count the queries equal to Bs . Since any randomized non-adaptive tester with T queries, let N P e 2 2 e N ≤ T , there is an s ∈ [m] such that E N ≤ T /m . The KL chain rule then gives s s s  
d0 64 log 9 KL LPe0,s (HT ) ∥ LPe1,s (HT ) ≤ T + . m2 m4 If the tester has worst-case error at most ε, Pinsker’s inequality implies   d0 64 log 9 2 + 2(1 − 2ε) ≤ T , m2 m4 and therefore T = Ωε (m2 ). The adaptive tester above still uses at most 3nε queries. Since m = ⌊N/4⌋ ≥ N/8, the padded family has adaptivity gap Ωε (N 2 ). This proves the theorem.

18

Related documents

• Statistical Data Integration in Survey Sampling: A Review#215440
• A Framework for Characterization of Optimal Decision Rules in Hypothesis-Testing Problems.#315677
• Individual Survey#207595
• Correction to: FIT as a Comparator for Evaluating the Effectiveness of New Non‑invasive CRC Screening Test#676763
• The material and the suppositional conditional#716017