acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

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 with . 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 at every finite query budget. For any -query adaptive policy and any , we construct a randomized non-adaptive procedure using 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 non-adaptive query complexity. Consequently, the worst-case fixed-error adaptivity gap is . 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.

Primary area:
learning theory
Keywords:
conditional sampling, hypothesis testing, adaptivity, query complexity, model evaluation

Reviews

Among:
Shape:
1234this paper, Bottom 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.25 over 4 reviews, above 49% of the others.
Reviewer_7BP9OpenReview ↗
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 (TT)-query adaptive tester can be simulated non-adaptively using (O(N2(T+log⁡(1/ρ)))O(N^2(T+\log(1/\rho)))) pairwise queries. A matching construction establishes a worst-case adaptivity gap of (Θε(N2)\Theta_\varepsilon(N^2)).

Critical strengths
  1. General hypothesis testing connection: The authors have provided a very first systematic investigations of Conditional queries in general hypotheses testing problems.

  2. 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 O(N2)O(N^2) multiplicative overhead in non-adaptive queries is sufficient to simulate an adaptive testing procedure using a sequence of preselected queries.

  3. 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 Θ(N2)\Theta(N^2) possibilities. This matches the upper bound in Section 4.

Critical weaknesses
  1. 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 (AA) using (EE), and and using Φ\Phi to map the elements of EE to the observed output yy when E⊆AE\subseteq A. The authors directly introduce the mapping Φ\Phi without first providing sufficient intuition for why this construction works.
  • Since AA and EE both denote query sets (adaptive and non-adaptive, respectively), it would be better to use consistent notation for them.
  • I presume that =d\overset{d}{=} in L362 is equivalent to L(HT∞)=L(HTπ)\mathcal{L}(H_T^\infty)=\mathcal{L}(H_T^\pi)? Can the authors please use consistent notation?
  • Furthermore, OεO_\varepsilon 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.
  1. Limited conceptual novelty of some results: The lower bound of the Ω(N2)\Omega(N^2) 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 (N2)\binom{N}{2}.

  2. 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

  1. From my understanding, what the authors prove in Section 4 is that TnaPairCOND≤Oε(N2)TadCONDT_{na}^{PairCOND} \leq O_\varepsilon(N^2) T_{ad}^{COND}. Interestingly, since PairCONDPairCOND is a restricted version of CONDCOND, we have TCOND≤TPairCONDT^{COND} \leq T^{PairCOND}. Therefore, this reduction also establishes an Oε(N2)O_\varepsilon(N^2) upper bound on the adaptivity gap when both adaptive and non-adaptive query oracles are restricted to PairCONDPairCOND, i.e., TnaPairCOND≤Oε(N2)TadPairCONDT_{na}^{PairCOND} \leq O_\varepsilon(N^2) T_{ad}^{PairCOND}. It would be helpful to mention this resulting PairCOND-versus-PairCOND adaptivity bound as well. Moreover, the authors should also explicitly state the relationship TCOND≤TPairCONDT^{COND} \leq T^{PairCOND}, since they also implicitly use it in their proof to argue that TnaCOND≤TnaPairCONDT_{na}^{COND} \leq T_{na}^{PairCOND}.

  2. Can substantially smaller adaptivity gaps be established for natural hypothesis classes, particularly standard identity or property-testing problems?

  3. L319 — What is ‘generic prompt-response kernel’? Can the authors clarify this term?

  4. In Algorithm 1, the line8, "return a valid TT-round completion under π\pi" is not sufficiently explained. What is done when the preselected sample stream is exhausted?

3 comments
AuthorsOpenReview ↗

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.**
AuthorsOpenReview ↗

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.

Reviewer_7BP9OpenReview ↗

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.

Reviewer_nATDOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies testing whether an unknown full-support distribution P on a finite space X belongs to one of two specified classes. A query to any nonempty A ⊆ X returns a sample from P(· | A). The authors show that uniform testing is possible exactly when the classes have positive separation in their pairwise conditional probabilities; a nonadaptive tester can then query every two-element set. They also show that pair queries fixed in advance can simulate the transcript of any T-query adaptive conditional tester, within total variation error ρ, using O(N²(T + log(1/ρ))) queries. A matching testing example shows that adaptivity can save a quadratic factor in N in the worst case.

Critical strengths

The results are well presented. The paper gives guarantees for a nonadaptive audit relative to an adaptive audit.

Critical weaknesses

The paper should explain when this conditional-query paradigm is needed in practice and whether it is reasonable to assume access to these queries in the proposed setting. When would one need to distinguish two classes of distributions that can be arbitrarily close in total variation? Are there interesting classes of distributions and problem models for which the proposed pairwise conditional separation is a meaningful criterion?

Questions for authors

See weaknesses.

3 comments
AuthorsOpenReview ↗

Response to Reviewer nATD (1/2): framework and practical interfaces

Thank you for your understanding of our theoretical results and for recognizing our guarantees for nonadaptive evaluation relative to adaptive evaluation. We clarify the overall motivation and the role of each result. Some theoretical results establish the internal foundations of a framework; their practical relevance emerges through the framework as a whole, without each result necessarily corresponding to a separate application. We therefore explain the connection to evaluation before discussing the learnability characterization.

In real interactive evaluation, evaluators may adjust the range of behaviors examined based on earlier observations, while these adjustments may also change the model's response tendencies. Changes in the testing strategy and in the tested system are thus coupled. To separate these effects, we adopt an idealized model: evaluation restricts the range of observable behaviors without changing their relative probabilities within that range. The resulting response follows the original distribution conditioned on the selected set, giving our conditional-query model. We then ask whether choosing these sets based on previous observations, compared with fixing all sets in advance, changes learnability and how many queries it can save. This isolates the contribution of adaptive evaluation when the underlying response distribution remains fixed.

AI evaluation encompasses diverse systems and interfaces, some of which closely realize this setting. For example, output-layer action masking in RL retains the logits of allowed actions and renormalizes after excluding the others. At fixed observations and policy outputs, ideal hard masking implements conditional sampling from the original action distribution. This mechanism is studied in MicroRTS (Huang and Ontanon) and implemented numerically in MaskablePPO. We agree that this correspondence requires a specific interface: ordinary prompting does not automatically provide it. In many evaluations, interaction history changes the model's internal state and response distribution, and our conclusions do not directly extend to those settings.

The framework also asks: to what extent does the testing procedure change the model's response tendencies? When this effect is weak, conditional queries may provide a more suitable approximation. Quantifying this deviation, establishing robustness to it, and understanding how query selection interacts with model-state evolution are further research questions.

Behavioral representations and access interfaces also admit design choices. Outcomes need not be individual generated strings or complete trajectories; they can be task-relevant behavioral categories. Choosing groups that preserve the distinctions being tested and have positive probability throughout the relevant hypothesis classes can satisfy the support condition while controlling the number of categories NN. Arbitrarily small positive probabilities already satisfy full support, and individual zero-probability behaviors can belong to categories with positive mass. Where such a representation is appropriate and NN is moderate, a quadratic query overhead may be acceptable compared with an exponential one. Behavioral granularity therefore provides design flexibility for connecting the framework to concrete evaluation objectives.

AuthorsOpenReview ↗

Response to Reviewer nATD (2/2): learnability and theoretical contributions

The learnability characterization serves the paper's theoretical development: before asking how many queries adaptivity can save, we first determine which problems can be reliably solved and whether adaptivity changes this scope. This requires a complete characterization, beyond comparing query efficiency under an assumption of learnability.

Regarding classes arbitrarily close in TV, we do not claim that all practical evaluations need to handle such classes. They must nevertheless be considered to characterize the power of conditional queries. Distributions that are globally very close can still have markedly different relative probabilities within a selected subset, allowing conditional queries to distinguish them reliably. Our criterion determines precisely when such discrimination is possible. This establishes the scope of solvable problems and provides a foundation for studying query efficiency. Developing justified structured hypothesis classes for specific benchmarks and analyzing the criterion within them requires additional modeling and theoretical research.

Our contribution has two levels. Conceptually, we distinguish changes in the evaluation strategy from changes in model responses, using conditional sampling to isolate the former and make static versus adaptive evaluation amenable to rigorous analysis. Technically, we establish a necessary and sufficient learnability criterion, universal transcript simulation using preselected pairwise queries, and a matching worst-case lower bound. The framework identifies a mechanism for independent study, and the results characterize its power and limitations. Together, these advance our understanding of machine learning evaluation.

AuthorsOpenReview ↗

Follow-up to Reviewer nATD

We uploaded the revised manuscript on November 15. In response to your question about practical access, the revision explains how action masking can implement conditional sampling. Our response also clarifies the role of the learnability theorem within the framework: it establishes which testing problems can be solved before we ask how many queries adaptivity can save. We would appreciate your assessment of the revision.

Reviewer_fuijOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies the trade-off between static (non-adaptive) and interactive (adaptive) model evaluations through the framework of conditional distribution testing. It models an evaluation over a finite set of potential behavioral outcomes, where an unknown model's behavior is represented by a probability distribution that assigns a non-zero probability to every outcome. Given two candidate families of distributions (i.e., hypothesis classes), an evaluator seeks to determine which family the model belongs to by repeatedly selecting a subset of outcomes and drawing a sample conditioned on the response falling within that subset. In this framework, the paper aims to solve two problems:

  1. Determining the exact conditions under which two families of distributions are learnable (i.e., that they can be reliably distinguished with arbitrarily small worst-case error as the number of queries grows)
  2. Quantifying the worst-case "adaptivity gap", i.e., the multiplicative increase in the number of queries required when an evaluator must fix all test subsets in advance rather than choosing them sequentially based on earlier responses. (Because the number of possible outcome subsets grows exponentially with the size of the outcome space, a naive static simulation of an interactive evaluation would require an exponential number of queries, leading to the question of whether interaction provides an exponential efficiency advantage over static benchmarks.)

To tackle these questions, the paper makes three contributions:

a) It establishes a necessary and sufficient criterion for learnability: two hypothesis classes can be reliably distinguished if and only if they exhibit a strictly positive separation in their pairwise conditional probabilities. When this pairwise separation is zero, the optimal worst-case error remains one-half (no better than random guessing) for any finite query budget, even for adaptive evaluators.

b) It constructs a universal randomized non-adaptive simulation procedure that uses only pre-selected two-outcome (pairwise) queries, scaling quadratically with the number of possible outcomes and linearly with the number of adaptive rounds, to accurately reproduce the full sequence of responses of any adaptive evaluation. This simulation works by composing random mappings built from pairwise samples until they coalesce into a single outcome, and its query overhead is independent of the complexity or separation of the hypothesis classes.

c) It proves a matching lower bound by constructing a family of distributions that an adaptive evaluator can distinguish in a constant number of queries (at a fixed target error rate), whereas any static evaluator requires a number of queries proportional to the square of the number of outcomes.

Taken together, these results prove that the worst-case adaptivity gap is quadratic in the size of the outcome space, demonstrating that interactive evaluation can reduce test counts by at most a quadratic factor rather than an exponential one.

Critical strengths

The paper gives an interesting conceptual connection between distribution testing and AI benchmarking. It provides a nice characterization of learnability, reducing the learnability of arbitrary distribution classes across an exponential number of possible subset queries entirely to pairwise comparisons between two outcomes at a time. It moreover gives a tight resolution of the worst-case adaptivity gap, through a quadratic upper bound with a matching quadratic information-theoretic lower bound. It’s also interesting that it shows a universal, distribution-free transcript simulation (rather than designing a specialized static test tied to a specific hypothesis class structure).

Critical weaknesses

The theoretical guarantees rely on the underlying distribution assigning strictly positive probability to every outcome and on the evaluator having exact sampling access when conditioning on any subset of outcomes. In practical AI evaluations, models frequently assign zero or negligible probability to certain behaviors, and restricting a generative model to sample cleanly from a conditioned pair without distorting its relative preferences seems non-trivial. While polynomial rather than exponential, a query count that scales quadratically with the number of outcomes can still be prohibitive in practice when the outcome space represents fine-grained behavioral categories, large label spaces, or multi-step action trajectories. Framing interactive evaluation as sequential conditional queries on a single static probability distribution captures adaptive question selection, but doesn’t seem to capture stateful multi-turn interaction, where a model's internal state and response distribution shift dynamically based on the conversation history. The quadratic lower bound relies on an adversarial construction where informative differences are hidden within a single target pair of outcomes. As acknowledged in the paper's limitations section, this worst-case minimax result does not reflect structured hypothesis classes common in real benchmarks (such as low-dimensional item-response models, where the adaptivity gap is typically much smaller), and the paper includes no numerical experiments or empirical demonstrations of the simulator on actual evaluation data. I feel that given the theoretical nature of the results, and the gap with respect to practical setups, the paper is better suited to a more theoretical conference such as COLT or ALT instead of ICLR.

Questions for authors

None.

2 comments
AuthorsOpenReview ↗

Response to Reviewer fuij: theoretical scope and practical interfaces

Thank you for your careful understanding of our theoretical contributions and for recognizing the learnability characterization, universal transcript simulation, and matching lower bound. We clarify the mechanism we isolate, its practical interfaces, and the flexibility of behavioral representations.

In real interactive evaluation, evaluators may adjust the range of behaviors examined based on earlier observations, while these adjustments may also change the model's response tendencies. Changes in the testing strategy and in the tested system are thus coupled. To separate these effects, we adopt an idealized model: evaluation restricts the range of observable behaviors without changing their relative probabilities within that range. The resulting response follows the original distribution conditioned on the selected set, giving our conditional-query model. We then ask whether choosing these sets based on previous observations, compared with fixing all sets in advance, changes learnability and how many queries it can save. This isolates the contribution of adaptive evaluation when the underlying response distribution remains fixed.

AI evaluation encompasses diverse systems and interfaces, some of which closely realize this setting. For example, output-layer action masking in RL retains the logits of allowed actions and renormalizes after excluding the others. At fixed observations and policy outputs, ideal hard masking implements conditional sampling from the original action distribution. This mechanism is studied in MicroRTS (Huang and Ontanon) and implemented numerically in MaskablePPO. We agree that this correspondence requires a specific interface: ordinary prompting does not automatically provide it. In many evaluations, interaction history changes the model's internal state and response distribution, and our conclusions do not directly extend to those settings.

The framework also asks: to what extent does the testing procedure change the model's response tendencies? When this effect is weak, conditional queries may provide a more suitable approximation. Quantifying this deviation, establishing robustness to it, and understanding how query selection interacts with model-state evolution are further research questions.

Behavioral representations and access interfaces also admit design choices. Outcomes need not be individual generated strings or complete trajectories; they can be task-relevant behavioral categories. Choosing groups that preserve the distinctions being tested and have positive probability throughout the relevant hypothesis classes can satisfy the support condition while controlling the number of categories NN. Arbitrarily small positive probabilities already satisfy full support, and individual zero-probability behaviors can belong to categories with positive mass. Where such a representation is appropriate and NN is moderate, a quadratic query overhead may be acceptable compared with an exponential one. Behavioral granularity therefore provides design flexibility for connecting the framework to concrete evaluation objectives.

We agree that the lower bound does not imply a quadratic gap for typical benchmarks or low-dimensional structured classes. Its theoretical significance is that differences concentrated in a hidden pair already suffice to create a quadratic gap, precluding a universally smaller bound in our general setting. Together with the simulation upper bound, this tightly characterizes the worst-case value of adaptivity. Identifying structures that yield smaller gaps requires justified hypothesis classes and access models for particular benchmarks, followed by analysis of their effects on query complexity. Connecting this analysis to empirical evaluation on real data is a substantive new research direction requiring substantial additional modeling, theory, and experiments, beyond the scope of this paper.

Finally, ICLR explicitly includes learning theory in its scope, and its reviewer guidelines recognize theoretical findings and call for assessing value and impact according to the work's objectives. Our contribution has two levels. Conceptually, we distinguish changes in the evaluation strategy from changes in model responses, using conditional sampling to isolate the former and make static versus adaptive evaluation amenable to rigorous analysis. Technically, we establish a necessary and sufficient learnability criterion, universal transcript simulation using preselected pairwise queries, and a matching worst-case lower bound. The framework identifies a mechanism for independent study, and the results characterize its power and limitations. Together, these advance our understanding of machine learning evaluation.

AuthorsOpenReview ↗

Follow-up to Reviewer fuij

We uploaded the revised manuscript on November 15. In response to your concerns about practical evaluation, we clarify when action masking implements conditional sampling and how grouping behaviors can reduce the number of outcomes. We also distinguish adaptive test selection from interactions that change the model’s response distribution. Our response explains why the quadratic gap is a worst-case bound and leaves the gap for structured benchmarks open. We would appreciate your assessment of the revision.

Reviewer_7SZwOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies hypothesis testing using conditional queries, comparing adaptive and non-adaptive testing. The authors show that both have the same conditions for learnability, but the number of queries needed can be very different. In particular, they show that any adaptive testing procedure can be simulated non-adaptively with a quadratic overhead in the number of queries, and they construct a matching lower bound showing that this overhead is tight in the worst case.

Critical strengths

The paper is well written and organized; it is interesting, and I enjoyed reading it.

  1. The paper gives what seems to be a strong result about the quadratic overhead in the number of samples in the non-adaptive scenario, showing that this bound is tight.
  2. The paper gives us a complete characterization of learnability in the conditional case, showing that adaptive and non-adaptive testing have the same conditions for learnability.
Critical weaknesses
  1. It feels that the conditioning model is too strong, and its relation to the real use case is not as strong as the author mentions, because he does not account for the cost of sampling in this model, which is evident in his construction of the lower bound.

  2. If we view it as a theoretical paper, it is clear and interesting, but I feel that the comparison to previous papers is not strong enough to understand how significant the new results really are. One way to improve the paper is to explain which open questions their results answer, or to pose new interesting questions that follow from their work.

Unimportant Issues

  1. In line 87, the authors use Θij\Theta_{ij} for the entries of Θ\Theta, but later, in line 181, they use θij\theta_{ij}. It would be better to keep the notation consistent.

  2. In line 221, the authors use LP(HT)L_P(H_T) without explicitly defining what LPL_P means.

Questions for authors

No

4 comments
AuthorsOpenReview ↗

Response to Reviewer 7SZw: practical scope and sampling costs (1/2)

Thank you for recognizing our theoretical results and for raising the connection between the conditional-query model and practical evaluation. We agree that the availability of conditional sampling and its implementation cost matter when applying this framework to a concrete evaluation. The mechanism we isolate is how much adaptivity in the evaluation strategy can help, given conditional access and with cost measured by the number of queries. The cost of implementing the conditional-sampling interface is a separate dimension. We take this access mechanism as given so that the role of query selection can be analyzed independently.

In real interactive evaluation, evaluators may adjust the range of behaviors examined based on earlier observations, while these adjustments may also change the model's response tendencies. Changes in the evaluation strategy and in the evaluated system are therefore coupled. To separate these effects, we adopt an explicit idealized model: evaluation restricts the range of behaviors observed in a query without changing their relative probabilities within that range. The resulting response follows the original distribution conditioned on the selected set, giving our conditional-query model. Within this model, we ask whether selecting these sets based on previous observations, rather than fixing all sets in advance, changes learnability and how many queries it can save. This makes the contribution of adaptive query selection amenable to rigorous analysis while the underlying response distribution remains fixed.

AI evaluation encompasses diverse systems and interfaces, some of which closely realize this setting. For example, output-layer action masking in RL retains the logits of allowed actions and renormalizes after excluding the others. At fixed observations and policy outputs, ideal hard masking implements conditional sampling from the original action distribution. This mechanism is studied in MicroRTS (Huang and Ontanon) and implemented numerically in MaskablePPO. This correspondence requires a specific interface: ordinary prompting does not automatically satisfy this condition. In many practical evaluations, interaction history changes the model's internal state and response distribution, and our conclusions do not directly extend to those settings.

AuthorsOpenReview ↗

Response to Reviewer 7SZw: practical scope and sampling costs (2/2)

We count obtaining one conditional sample as one query, and leave the internal cost of implementing that sample outside the model. The lower-bound construction therefore allows the evaluator to query low-probability events directly: an event being rare under the original distribution does not mean that a conditional query must wait for it to occur naturally. For example, output-layer action masking allows direct renormalization and sampling among the permitted actions. If a system can only sample from the original distribution and retain outcomes that fall in an event AA, obtaining one conditional sample requires 1/P(A)1/P(A) original samples on average, making low-probability events more costly. These two interfaces implement the same conditional distribution but incur different actual costs. Our question is how many calls adaptive query selection can save once conditional access is available. Applying this result to a concrete system additionally requires analyzing the total cost under its sampling implementation and whether the cost comparison between adaptive and nonadaptive strategies changes accordingly.

The framework also suggests two directions for further analysis: how much the testing procedure changes the model's response tendencies, and how much it costs to implement different conditional queries. When changes in response tendencies are weak and conditional access can be implemented efficiently, the model may more closely approximate the practical interface. Applying the theory to a concrete system requires analysis tailored to its response mechanism and access costs; studying the value of adaptivity under approximate conditional access and different query costs is a substantive problem requiring additional modeling and theoretical work.

Behavioral representations and access interfaces themselves also admit design choices. Outcomes can be task-relevant behavioral categories, rather than individual generated strings or complete trajectories. Choosing groups that preserve the distinctions being tested and have positive probability throughout the relevant hypothesis classes can satisfy the support condition while controlling the number of categories NN. The connection between the theoretical framework and concrete evaluation objectives can therefore also be developed through the choice of behavioral granularity and access interface.

Conceptually, we distinguish changes in the evaluation strategy from changes in model responses, and separate the implementation cost of conditional access from the efficiency of query selection, thereby isolating a mechanism that can be studied rigorously. Our results characterize the power and limitations of adaptivity within this mechanism and provide a theoretical starting point for incorporating changes in responses and access costs.

AuthorsOpenReview ↗

Response to Reviewer 7SZw: relation to prior work and research motivation

Regarding the relationship between this paper and prior work, our questions arose from our own thinking about the difference between static and interactive evaluation: if later tests can be adjusted based on earlier results, does this change which problems can be solved, and how much efficiency can it offer? The starting point was not an open problem posed in a particular paper. After developing the research, we situated its contributions through comparison with the related literature; our search has not identified a previously stated open problem that directly corresponds to our results.

Prior work has established detailed conditional-query complexity bounds for standard testing tasks and provided tools for exact sampling from pairwise comparisons. Relative to these results, our paper characterizes uniform learnability for arbitrary pairs of hypothesis classes of full-support distributions and extends the pairwise-sampling mechanism to simulate the entire transcript of any adaptive conditional-query policy, with a uniform budget guarantee independent of the minimum probability. The matching lower bound further shows that this quadratic overhead cannot be universally improved for general hypothesis testing, even when nonadaptive testers may query arbitrary subsets.

Specifically:

  • Canonne, Ron, and Servedio (2015) develop conditional-sampling algorithms for several standard distribution-testing tasks, reducing query complexity to polylogarithmic in the domain size, and for some tasks removing dependence on the domain size altogether, demonstrating the power of conditional access relative to ordinary sampling. Testing Probability Distributions Using Conditional Samples

  • Kamath and Tzamos (2019) give polylogarithmic query upper bounds for uniformity, identity, and equivalence testing under nonadaptive conditional access, establishing the efficiency achievable for these specific tasks when queries are fixed in advance. Anaconda: A Non-Adaptive Conditional Sampling Algorithm for Distribution Testing

  • Fotakis, Kalavasis, and Tzamos (2022) study how to use observations obtained by sampling between only two options at a time to generate a sample from the original distribution over all options; our paper instead uses such pairwise samples collected in advance to simulate an entire interaction: each round selects a new range of options based on previous results and generates a conditional response within that range, with a uniform budget guarantee for the whole process that is independent of the minimum atom probability. Perfect Sampling from Pairwise Comparisons

AuthorsOpenReview ↗

Follow-up to Reviewer 7SZw

We uploaded the revised manuscript on November 15. On sampling costs, we clarify that our bounds count calls to a conditional sampler. Action masking can sample directly from the allowed actions, whereas rejection sampling must wait for an allowed outcome to occur. On prior work, we explain how we build on results for specific testing problems and on exact sampling from pairwise comparisons: we characterize which pairs of full-support hypothesis classes are uniformly testable and show how preselected pair queries can simulate the entire transcript of any adaptive conditional test. We also address the two notation issues you flagged. We would appreciate your assessment of the revision.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Revised manuscript uploaded: summary of changes

We have uploaded a revised manuscript incorporating the reviewers' feedback on presentation, the scope of the model, and the relationship to prior work. The main changes are as follows.

  1. Intuition for the core constructions. In Section 4, before introducing the random maps, we explain how preselected pair queries simulate conditional sampling on a selected set and why coalescence of the maps determines the simulated output. Section 5 now begins with the rationale for the lower-bound construction: concentrate the information needed to distinguish the two hypotheses in a hidden target pair, make queries to larger sets containing that pair provide only negligible information, and provide location information that allows an adaptive tester to find the pair.

  2. Details of the simulator and query models. Algorithm 1 now specifies a concrete completion rule when the preselected sample stream is exhausted, and the appendix explains how this event is accounted for in the simulation error. Corollary 4.2 explicitly states that non-adaptive pair queries can simulate an adaptive tester allowed to query arbitrary sets with a quadratic overhead. It also states the resulting adaptivity-gap upper bound when both testers are restricted to pair queries.

  3. Connections to applications and prior work. The revision more clearly distinguishes adaptive query selection under a fixed response distribution from changes in model responses caused by interaction. It explains the interface requirements for conditional access, the role of behavioral grouping, and the distinction between query counts and the cost of implementing conditional sampling. We also clarify the comparison with prior work on conditional testing and sampling from pairwise comparisons, distinguishing the tools we use from our learnability characterization, universal transcript simulation, and matching lower bound.

We have also made the notation for pairwise conditional probabilities, query sets, and probability laws consistent, supplied previously missing definitions, and revised the organization of related work and transitions between paragraphs.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.