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.
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 $\mathcal{X}$ with $|\mathcal{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 $\rho \in (0,1)$, we construct a randomized non-adaptive procedure using $O(N^2(T + \log(1/\rho)))$ pair queries chosen before any response is observed. Its simulated transcript is within $\rho$ 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(N^2)$ non-adaptive query complexity. Consequently, the worst-case fixed-error adaptivity gap is $\Theta_\varepsilon(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.
Oracle routing measures how much a pool of language models could gain from per-query selection, but the diagnostic has two flaws: testing against a best fixed model selected on the same examples invalidates paired inference, and a full-information oracle sees outcomes no deployable router observes. We separate three estimands (outcome-oracle opportunity, the Bayes-optimal gain from a declared pre-answer signal, and the held-out gain of a learned router) and prove selection-valid confidence intervals that survive choosing the best fixed model or the best member of a router family, a signal-information sandwich, and a $(1-1/e)$ greedy guarantee for building compact pools from submodular complementary coverage. On eight checkpoints from six families over four benchmarks, selection-valid intervals certify a population oracle gap of $9.7$--$30.7$ points on every task, yet the strongest deployable prompt router recovers only $7.5$--$14.4\%$ of it, and the simultaneous interval for the best of eleven tested policies has lower limit zero throughout. The realizable share of oracle opportunity is small and certifiable: strong routers beat the best fixed model, and most of the gap remains.
Ibne Farabi Shihab, A. Ahsan, Md Najmus Swaqeeb· 0 citations
Motivated by learning from heterogeneous and overlapping data providers, we study a stylized model of distribution learning from restricted conditional samples. The goal is to learn an unknown distribution $p$ on a finite domain $[n]$. The learner is given a fixed family of queryable sets $\mathscr{S} \subseteq 2^{[n]}$, and each query to $S \in \mathscr{S}$ returns an independent sample from the conditional distribution $p(\cdot \mid S)$. Learnability is governed by the co-occurrence graph associated with $\mathscr{S}$: two domain elements are adjacent if they appear together in some queryable set. Pointwise consistency is achievable when this graph is connected on the target support. PAC learning requires more: it is possible when the co-occurrence graph is complete. The optimal sample complexity of PAC learning ranges from nearly linear to quadratic. Every query family with complete co-occurrence graph admits sample complexity $\widetilde O(n^2/\epsilon^2)$, and this bound is tight in the worst case. On the other hand, if $[n]$ is queryable then ordinary sampling improves the bound to $\Theta(n/\epsilon^2)$, and this cannot be improved further even if every set is queryable. More generally, we identify hierarchical comparabilityas a sufficient structural condition on $\mathscr S$ under which the optimal complexity is nearly linear, $\widetilde \Theta(n/\epsilon^2)$, with pairwise query families as a canonical example. Finally, the full range of polynomial rates between linear and quadratic is attainable: for every $\alpha \in (1,2)$, there exists a query family with optimal PAC rate $\widetilde \Theta(n^\alpha/\epsilon^2)$.
Jon Kleinberg, Amin Saberi, Xizhi Tan et al.· 1 citation· ⚡1
We study the round complexity of learning a hidden partition $\mathcal{P}$ of an $n$-element universe using PAIR queries: PAIR($x,y$) tells us whether $x$ and $y$ belong to the same part of the partition or not. While it is easy to learn using $n|\mathcal{P}|$ queries using a basic algorithm and this query complexity is optimal, this basic algorithm is highly sequential. Black, Mazumdar, and Saha [COLT 2025] recently gave tight deterministic round/query tradeoffs when the number of parts of $\mathcal{P}$ is known. In particular they prove $\Theta(\log\log n)$ rounds are sufficient and necessary to limit the number of queries to $n|\mathcal{P}|$. They leave proving a randomized lower bound as an open direction. We show that randomization dramatically changes the picture. When the number of parts $k = |\mathcal{P}|$ is known, we give a simple 3-round randomized algorithm using $O(nk\log n)$ queries with high probability, and prove that 2 rounds require $\Omega(n^{4/3}k^{2/3})$ queries -- the same as deterministic algorithms. We also study a more general setting where the number of parts is unknown. In this case, we give a 4-round randomized algorithm using $O(n|\mathcal P|\log^2 n)$ queries with high probability, and prove that 3-rounds cannot achieve near-optimal query complexity. Furthermore, we show an even bigger separation in this regime between randomized and deterministic algorithms: for the latter, $\Theta(\log n/\log\log n)$ rounds are necessary and sufficient to obtain near-optimal query complexity.
Deeparnab Chakrabarty, Aditi Dudeja, David Saulpic· 0 citations
We study the query complexity of recovering a planted assignment from a random constraint-satisfaction instance with one-sided noise. We consider the following 1-CNF recovery problem: an unknown binary string with $n/2$ ones and $n/2$ zeros is queried at individual variables. A query to a $1$-variable returns"$1$"with probability $p$ and"$0$"otherwise, while a $0$-variable always returns"$0$"(each query is a fresh noisy draw). The goal is to recover the binary string with probability at least $1 - \delta$. While the naive counting argument may suggest a query complexity of $\log_2 \binom{n}{n/2}=\Theta(n)$, we show that the query complexity is $(1+o(1))c(p) \frac{n}{2} \left( \log_2 n + \log_2(1/\delta)\right)$, where $c(p) = \tfrac{1}{-\log_2(1-p)}$. We then study planted $k$-CNF satisfaction with one-sided noise. Each $k$-set containing a $1$-variable is included as a clause independently with probability $p$, and an algorithm may ask whether any given $k$-set is a clause. Unlike the $1$-CNF case, a clause-existence query is one-shot: each $k$-set either is or is not a clause, so repeating yields no new information. The model is one-sided because an observed clause certifies that at least one queried variable is assigned 1, whereas its absence does not certify all are assigned 0. The goal is to recover the planted assignment with probability at least $1 - \delta$. The counting baseline is $\Theta(n)$, yet we prove a query complexity of $(1+o(1))\,c(p,k)\, \frac{n}{2}\left( \log_2 n + \log_2(1/\delta)\right)$, where $c(p,k) = \tfrac{1}{k(-\log_2(1-p))}$. These bounds are for adaptive algorithms. We also prove bounds for nonadaptive algorithms, showing that for fixed $p$, adaptivity gives a factor $\exp(\Theta(k))$ improvement. Our results also imply lower bounds for noisy sorting of $\{0,1\}$-valued strings, and we study a variant of the model with negations.
Cassandra Marcussen, Elchanan Mossel, Colin Sandon· 0 citations
In this note, we introduce the notion of ranked spreadness, a strengthening of the usual spread condition in which the elements of each member can be ordered so that their one-coordinate marginals decay geometrically with their rank. This additional structure removes the dependence on the maximum set size in random-containment estimates. We prove width-free hitting and weighted-concentration theorems for ranked-spread set systems, together with an elementary kernel-extraction theorem showing that ranked spreadness arises naturally in arbitrary distributions on small sets. Our main application is to the simulation of nonadaptive property testers by sample-based testers. If a one-sided tester has average query complexity $d$ and rejects every far input with probability at least $\delta$, then, for every integer $c>d/\delta$, it admits a one-sided sample-based simulation with expected sample complexity $O_{d,\delta,|\Sigma|}\bigl(n^{1-1/c}\bigr)$. More generally, if positive inputs are rejected with probability at most $\gamma$ and far inputs with probability at least $\delta>\gamma$, the same conclusion holds for every $c>d/(\delta-\gamma)$. In particular, for constant-query nonadaptive testers we obtain an exponent $1-\Theta(1/q)$, matching, up to the dependence on the rejection gap, the exponent conjectured by Fischer, Lachish, and Vasudev.
This work invert a family of test supermartingales and proposes several mixture querying rules that combine growth-oriented querying, prediction refinement, and uniform exploration, trying to mitigate the effects that slow the shrinkage rate.