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

arXiv: https://arxiv.org/abs/2608.06262 · HTML: https://mlsanity.com/paper/2608.06262/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 21 of its 42 references that are in the map.
- First posted on arXiv 6 Aug 2026.

## Builds on (most cited first, 21 of 21)

- [Judging LLM-as-a-Judge with MT-Bench and Chatbot Arena](https://mlsanity.com/paper/2306.05685/) (2023)
- [Measuring Massive Multitask Language Understanding](https://mlsanity.com/paper/2009.03300/) (2020)
- [Beyond the Imitation Game: Quantifying and extrapolating the capabilities of language models](https://mlsanity.com/paper/2206.04615/) (2022)
- [Beyond Accuracy: Behavioral Testing of NLP models with CheckList](https://mlsanity.com/paper/2005.04118/) (2020)
- [Adversarial NLI: A New Benchmark for Natural Language Understanding](https://mlsanity.com/paper/1910.14599/) (2019)
- [Dynabench: Rethinking Benchmarking in NLP](https://mlsanity.com/paper/2104.14337/) (2021)
- [tinyBenchmarks: evaluating LLMs with fewer examples](https://mlsanity.com/paper/2402.14992/) (2024)
- [LiveBench: A Challenging, Contamination-Limited LLM Benchmark](https://mlsanity.com/paper/2406.19314/) (2024)
- [DynaSent: A Dynamic Benchmark for Sentiment Analysis](https://mlsanity.com/paper/2012.15349/) (2020)
- [Position: AI Evaluation Should Learn from How We Test Humans](https://mlsanity.com/paper/2306.10512/) (2023)
- [Reliable and Efficient Amortized Model-based Evaluation](https://mlsanity.com/paper/2503.13335/) (2025)
- [BOBCAT: Bilevel Optimization-Based Computerized Adaptive Testing](https://mlsanity.com/paper/2108.07386/) (2021)
- [Efficient Evaluation of LLM Performance with Statistical Guarantees](https://mlsanity.com/paper/2601.20251/) (2026)
- [Dynatask: A Framework for Creating Dynamic AI Benchmark Tasks](https://mlsanity.com/paper/2204.01906/) (2022)
- [Faster Algorithms for Testing under Conditional Sampling](https://mlsanity.com/paper/1504.04103/) (2015)
- [Perfect Sampling from Pairwise Comparisons](https://mlsanity.com/paper/2211.12868/) (2022)
- [A Chasm Between Identity and Equivalence Testing with Conditional Queries](https://mlsanity.com/paper/1411.7346/) (2014)
- [Anaconda: A Non-Adaptive Conditional Sampling Algorithm for Distribution Testing](https://mlsanity.com/paper/1807.06168/) (2018)
- [On Distribution Testing in the Conditional Sampling Model](https://mlsanity.com/paper/2007.09895/) (2020)
- [AutoJudger: An Agent-Driven Framework for Efficient Benchmarking of MLLMs](https://mlsanity.com/paper/2505.21389/) (2025)
- [Equivalence Testing: The Power of Bounded Adaptivity](https://mlsanity.com/paper/2403.04230/) (2024)

## Abstract (arXiv)

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(N2(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 Omega_varepsilon(N2) non-adaptive query complexity. Consequently, the worst-case fixed-error adaptivity gap is Theta_varepsilon(N2). 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.