- Rating
- 2
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 3(+1)
- Soundness
- 3(+1)
Read review
Paper summary
The paper studies binary hypothesis testing under conditional sampling access, with a focus on the power difference between adaptive and non-adaptive queries. It establishes a necessary and sufficient condition for learnability in terms of separation under pairwise conditional probabilities. The main result on adaptive vs non adapticve is a universal simulation theorem showing that any ()-query adaptive tester can be simulated non-adaptively using () pairwise queries. A matching construction establishes a worst-case adaptivity gap of ().
Critical strengths
-
General hypothesis testing connection: The authors have provided a very first systematic investigations of Conditional queries in general hypotheses testing problems.
-
Adaptive query simulation with a quadratic gap: Section 4 provides a nice construction for simulating adaptive queries from a set of prechosen non-adaptive queries. The authors show that an multiplicative overhead in non-adaptive queries is sufficient to simulate an adaptive testing procedure using a sequence of preselected queries.
-
An interesting lower-bound construction: The construction in Section 5 is quite elegant: the authors construct a family of distributions where an adaptive tester can identify a hidden low-probability informative pair using a constant number of queries, whereas a non-adaptive tester essentially needs to guess the correct pair among possibilities. This matches the upper bound in Section 4.
Critical weaknesses
- Poor writing: Though the results are interesting, the writing quality makes it difficult and time-consuming for a reader to understand the underlying ideas. See the following examples:
- In the construction of Section 4, it is quite hard to understand the very natural idea that the authors are trying to hit () using (), and and using to map the elements of to the observed output when . The authors directly introduce the mapping without first providing sufficient intuition for why this construction works.
- Since and both denote query sets (adaptive and non-adaptive, respectively), it would be better to use consistent notation for them.
- I presume that in L362 is equivalent to ? Can the authors please use consistent notation?
- Furthermore, is never explicitly defined.
- Section 5 also starts directly with the construction without providing a proper high-level overview or intuition for why the authors choose this particular construction.
-
Limited conceptual novelty of some results: The lower bound of the adaptivity gap is quite natural (though the construction is nice). Think of an adaptive algorithm as being smart enough to identify the relevant pair in a constant number of queries, whereas a non-adaptive algorithm, in the worst case, needs to try all possible pairs .
-
The worst-case gap may not reflect natural testing problems: While this worst-case construction gives a quadratic adaptivity gap, it is not clear how this extends to natural distribution testing problems, such as uniformity testing or equivalence testing. For example, uniformity, identity, and equivalence testing have at most a polylogarithmic adaptivity gap, as follows from the non-adaptive upper bounds of Kamath and Tzamos (2018). It would be interesting to understand whether the quadratic gap can arise for more natural hypothesis classes.
Questions for authors
Question and comments
-
From my understanding, what the authors prove in Section 4 is that . Interestingly, since is a restricted version of , we have . Therefore, this reduction also establishes an upper bound on the adaptivity gap when both adaptive and non-adaptive query oracles are restricted to , i.e., . It would be helpful to mention this resulting PairCOND-versus-PairCOND adaptivity bound as well. Moreover, the authors should also explicitly state the relationship , since they also implicitly use it in their proof to argue that .
-
Can substantially smaller adaptivity gaps be established for natural hypothesis classes, particularly standard identity or property-testing problems?
-
L319 — What is ‘generic prompt-response kernel’? Can the authors clarify this term?
-
In Algorithm 1, the line8, "return a valid -round completion under " is not sufficiently explained. What is done when the preselected sample stream is exhausted?
3 comments
Follow-up to Reviewer 7BP9
We uploaded the revised manuscript on November 15. In response to your presentation comments, Sections 4 and 5 now explain the intuition before each construction, and we have clarified the terminology, definitions, and notation you flagged. Algorithm 1 now specifies what happens when the sample stream runs out. Following your suggestion, Corollary 4.2 now states both the PairCOND-to-COND comparison and the adaptivity bound when both testers use PairCOND. Section 5 clarifies what the lower bound establishes in the worst case, and our response discusses the smaller gaps known for identity and uniformity testing. We would appreciate your assessment of these revisions.
Thank you for the detailed response
Thank you for the detailed response and for revising the manuscript. I can see the improvements in the new version. The revision now addresses many of my complaints. Because of this, I am increasing my Presentation and Soundness scores.
However, my primary concern regarding the significance of the quadratic adaptivity gap still stands. The lower bound construction is nice, but the underlying intuition is a rather natural worst-case searching procedure. Also, as the results of Kamath and Tzamos (2019) imply substantially smaller adaptivity gaps for standard distribution-testing problems, I am not sure about the broader significance of the quadratic separation beyond the worst-case construction. I, therefore, would like to keep my score.
Response to Reviewer 7BP9: adaptivity gaps, PairCOND, and clarifications
Thank you for recognizing the theoretical results. We address the role of the lower bound, the query interfaces, and the gaps for natural tasks below.
1. The lower bound primarily establishes the worst-case tightness of universal simulation. We agree that locating a target pair and then querying it has an intuitive search interpretation. The construction must additionally ensure that a nonadaptive tester, even with arbitrary subset queries, cannot efficiently examine many candidates simultaneously through larger sets. We therefore control the information provided by every non-target set, establishing that the quadratic overhead cannot be universally improved for general hypothesis testing. This does not imply that natural evaluation tasks typically exhibit a quadratic gap.
2. Nonadaptive PairCOND incurs at most quadratic overhead even relative to adaptive full COND. We agree that this stronger comparison between interfaces deserves emphasis: the simulator uses only preselected pair queries, yet simulates adaptive policies that may query arbitrary subsets. At a fixed error rate, after a constant number of repetitions for error reduction,
\le T_{\mathrm{na}}^{\mathrm{PairCOND}} \le C_\varepsilon N^2 T_{\mathrm{ad}}^{\mathrm{COND}} \le C_\varepsilon N^2 T_{\mathrm{ad}}^{\mathrm{PairCOND}}.$$ The quadratic PairCOND-versus-PairCOND adaptivity-gap upper bound is also an immediate consequence. All complexities above concern the same hypothesis classes and error rate $\varepsilon$. **3. Classical tasks already admit smaller gaps and fit directly within our framework.** For example, setting $$\mathcal P_0=\lbrace Q\rbrace,\qquad \mathcal P_1=\lbrace P\in\Delta_{+}([N]):d_{\mathrm{TV}}(P,Q)\ge\eta\rbrace$$ gives identity testing against a known full-support distribution $Q$; choosing $Q=U_N$ gives uniformity testing. For fixed distance threshold and error rate, the nonadaptive upper bounds of Kamath and Tzamos (2019) imply adaptivity-gap upper bounds of $\widetilde O(\log^2 N)$ and $\widetilde O(\log N)$, respectively. A preprint by Kamath (2026), released after our submission, further improves the identity-testing upper bound to near-logarithmic. [Kamath and Tzamos (2019)](https://arxiv.org/abs/1807.06168); [Kamath (2026)](https://arxiv.org/abs/2610.11145). For AI evaluation, a more directly relevant follow-up question is whether behavioral structures such as tool hierarchies or permission relationships permit similar improvements. **Formalizing these practical requirements as structured hypothesis classes and characterizing their adaptivity gains requires further modeling and theoretical research; our paper provides a unified framework and a worst-case benchmark.** **4. Exhaustion of the sample stream is treated as a low-probability failure event.** At exhaustion, the simulation may still be incomplete, and the available information need not suffice for a correct decision. Our choice of budget $L$ ensures that this event has probability at most $\rho$. Before exhaustion, the simulation agrees with the exact reconstruction using an infinite stream. Upon exhaustion, the transcript can be completed by a fixed rule: retain the completed rounds, assign the smallest element of the current query set as its response, and select subsequent queries according to $\pi$ on the completed history, again responding with the smallest element of each query set. Even if these fallback responses lead to an incorrect decision, their additional contribution to the overall error probability is at most $\rho$. **5. Regarding presentation, we will address your comments together with those from the other reviewers in the revised manuscript, adding intuition for the constructions, clarifying terminology, and making the notation consistent.**