Suppose you want to check whether a sampler over long binary strings is within some total variation distance of a reference. The sampler might be a SAT-solution generator, a logic-circuit sampler, or a model that generates one bit at a time. With ordinary independent samples this is hopeless: a domain of $2^n$ strings needs roughly $2^n/n$ samples. A richer kind of access changes the picture. Subcube conditioning lets you fix some coordinates of the string and sample the rest. Under this access, exact-match tests become cheap: uniformity testing needs only about $\sqrt{n}/\epsilon^2$ queries (Random Restrictions of High-Dimensional Distributions and Uniformity Testing with Subcube Conditioning). The question practitioners actually ask is different. They want to know whether the sampler is close enough, with distance at most $\epsilon_1$ versus at least $\epsilon_2$. This is tolerant testing, and for it the best known algorithm uses $\tilde{O}(n^3/\epsilon^5)$ queries, against a lower bound of only $\Omega(n/\log n)$ (Distance Estimation for High-Dimensional Discrete Distributions).
This note proposes to measure how much tolerance costs in this high-dimensional conditional model. It also asks whether that cost depends on how much we know about the reference. We study three problems of increasing difficulty. The first is tolerant uniformity. The second is tolerant identity testing against a reference whose probabilities we can evaluate exactly, as with a compiled circuit or an autoregressive model. The third is tolerant equivalence, where both distributions are black boxes. The algorithmic idea is simple. The cubic cost appears to come from estimating every coordinate's conditional probability to the same fine accuracy. We instead estimate the per-string log-likelihood ratio by randomly subsampling coordinates, and we exploit the fact that total variation depends on that ratio only through a single kink at zero. If this works, it shows two things. First, tolerant testing under subcube conditioning sits much closer to the $n$ lower bound than current algorithms suggest. Second, the identity-versus-equivalence gap known for general conditional queries has a measurable counterpart here.
Core Claim
Our hypothesis concerns asymmetric access, where one distribution $Q$ can be evaluated pointwise and the other, $P$, can only be queried by subcube conditioning. In that setting, tolerant distance estimation should cost $\tilde{O}(n^2/\epsilon^4)$ queries rather than $\tilde{O}(n^3/\epsilon^5)$. The savings come from two sources that we can separate:
- replacing uniform per-coordinate accuracy with an unbiased coordinate-subsampled estimate of the log-ratio;
- a smoothing argument showing that per-string log-ratio errors of order $\sqrt{\epsilon}$, rather than $\epsilon$, suffice when the log-ratio is not heavily concentrated near zero.
We further conjecture that when both sides are black boxes, one additional normalization step is unavoidable. This would reproduce, in the tolerant subcube setting, the identity/equivalence chasm that A Chasm Between Identity and Equivalence Testing with Conditional Queries proved for general conditioning in the exact-match case. We also plan to test whether tolerant uniformity is already nearly linear in $n$. That would be the subcube analogue of the jump from sublinear to near-linear cost that The Price of Tolerance in Distribution Testing and Exploring the Gap between Tolerant and Non-tolerant Distribution Testing proved under ordinary sampling.
How This Relates to Prior Work
Two lines of work set up the question, and neither answers it.
The price-of-tolerance papers work only with ordinary independent samples over a flat domain of size $n$. The Price of Tolerance in Distribution Testing shows that tolerant identity testing costs $\tilde{\Theta}(\sqrt{n}/\epsilon_2^2 + \tfrac{n}{\log n}\max\{\epsilon_1/\epsilon_2^2, (\epsilon_1/\epsilon_2^2)^2\})$. It also shows that tolerance is "free" only when $\epsilon_1 \lesssim \min(1/\sqrt{n}, \epsilon_2/n^{1/4})$. Exploring the Gap between Tolerant and Non-tolerant Distribution Testing catalogs properties where tolerance forces near-linear cost. Both motivate our question, but neither considers conditional access.
The conditional-query papers handle tolerance only on one-dimensional domains. On Tolerant Distribution Testing in the Conditional Sampling Model gets tolerant identity testing under arbitrary conditioning down to $\tilde{O}(\epsilon^{-4})$, independent of domain size, using a geometric-waiting-time trick to estimate probability ratios. However, arbitrary conditioning sets are not implementable over $\{0,1\}^n$, and that paper does not treat tolerant equivalence. We borrow its idea of estimating ratios by counting outcomes until a target appears, but we do so coordinate by coordinate.
Two papers supply the methods we reuse and try to beat. Distance Estimation for High-Dimensional Discrete Distributions, with its companion Tolerant Testing of High-Dimensional Samplers with Subcube Conditioning, introduced DistEstimate. DistEstimate "tames" conditional marginals below $\epsilon/8n$, writes each string's probability as a product of $n$ conditional marginals, and estimates each marginal by repeated querying until the target outcome occurs. It assumes symmetric black-box access to both distributions. We keep its taming step and drop the demand that all $n$ marginals be estimated to uniform accuracy.
Efficient Distance Approximation for Structured High-Dimensional Distributions via Learning. estimates distance by averaging density ratios over fresh samples, once both densities can be evaluated. It needs a known structure, such as a Bayesian network with bounded in-degree, so that the densities can be learned. We use the same ratio-averaging estimator, but we obtain $P$'s density from conditional queries instead of from learning.
Testing Probabilistic Circuits solves tolerant closeness in about 294 samples, but only when both sides support approximate counting and sampling. It is the white-box endpoint of our access spectrum.
Research Program
The estimator. Write $L(x) = \log P(x) - \log Q(x)$ for the log-likelihood ratio at string $x$. Total variation distance can be written as
$$d_{TV}(P,Q) = \mathbb{E}_{x \sim P}\big[\,(1 - e^{-L(x)})_+\,\big],$$
where $(\cdot)_+$ keeps only positive values. By the chain rule, $L(x) = \sum_{i=1}^n \ell_i(x)$. Each term $\ell_i(x)$ is the log-ratio of the two distributions' conditional probabilities of bit $x_i$ given the earlier bits, and each can be estimated from subcube queries that fix those earlier bits.
The estimator works in three steps:
- Draw $x$ from $P$.
- Pick $k$ coordinates at random, with probability tilted toward coordinates whose terms are likely to be large. Estimate each chosen $\ell_i$ with a negative-binomial count, as in DistEstimate.
- Combine these into an unbiased estimate of $L(x)$, then pass it through a smoothed version of the kinked function above.
When $Q$ can be evaluated, the $Q$ half of each $\ell_i$ is exact and only $P$ needs queries. When $Q$ is also a black box, both halves are estimated. That is the extra cost we expect to separate identity from equivalence.
Only conditioning on prefixes in a fixed coordinate order is needed. This is weaker than full subcube conditioning, which matters for deployment on samplers that generate one bit at a time.
The analysis. There are two error sources. First, subsampling has variance that is governed by how the $\ell_i$ are spread across coordinates. After taming, each term is bounded by $O(\log(n/\epsilon))$, so the variance is at most about $n \sum_i \ell_i^2$. That is small when the terms are spread out and large when a few coordinates dominate. Second, the kink contributes bias. If $L$ is observed with noise of size $\sigma$, the bias in $(1-e^{-L})_+$ is of order $\sigma^2$ times the density of $L$ near zero, because the function is piecewise smooth with a single kink. This is why accuracy of order $\sqrt{\epsilon}$ could suffice.
Instances where a few coordinates dominate are the obvious threat to the first saving. We handle them with a hybrid: a cheap preliminary pass flags the coordinates with large terms, those coordinates are estimated exhaustively, and the rest are subsampled. Whether this hybrid can be made worst-case optimal is the main theoretical risk.
The lower bounds. On the lower-bound side, we will try to extend the moment-matching construction of The Price of Tolerance in Distribution Testing to product-like families on the hypercube. The goal is to build "close" and "far" families that no subcube-query algorithm with $o(n)$ queries can tell apart, even when the reference is uniform. For the equivalence case, we will embed the normalization hardness from Tight Lower Bound on Equivalence Testing in Conditional Sampling Model into a single coordinate block, and check whether it survives the addition of tolerance.
Baselines
The naive reference point is the plug-in estimator: draw independent samples from both distributions, build empirical histograms, and report their total variation distance. Testing Closeness With Unequal Sized Samples showed that this estimator fails in the undersampled regime even over a flat vocabulary, where it could not separate "wolf" from "wolf" versus "wolf" from "fox" on Google Books n-grams. We include it at matched query budgets to confirm that it saturates near 1 for $n \ge 30$.
The strongest existing method is DistEstimate from Distance Estimation for High-Dimensional Discrete Distributions. On ISCAS89 circuits with up to 37 variables, using the STS and CMSGen samplers, it reports a mean absolute difference from the true total variation distance of 0.09 at tolerance $\epsilon = 0.3$. On random Boolean instances with $n = 70$, it reports a $10^7\times$ speedup over non-conditional estimators, which would need about $10^{18}$ queries. We will rerun DistEstimate ourselves on the same circuit instances, samplers, random seeds, and hardware, with the same query-counting convention. Beating it means one of two things: reaching mean absolute error at or below 0.09 at $\epsilon = 0.3$ with at least five times fewer queries, or showing a smaller empirical scaling exponent in $n$ at fixed error.
The ablation that isolates our main ingredient is DistEstimate with the $Q$-side estimates replaced by exact evaluation. This gives DistEstimate the same asymmetric access we use, but no coordinate subsampling and no kink smoothing. If our estimator beats DistEstimate only by about a factor of two and does no better than this ablation, the saving comes entirely from access and not from the method. We add two further ablations: our estimator without subsampling, and our estimator without smoothing. These attribute any gain to one of the two claimed sources.
We include two further references on the instances where they apply. Teq from Testing Probabilistic Circuits reports 100% decision accuracy on 475 pairs and 294 samples at $\epsilon = 0.01, \eta = 0.2$; we run it on the d-DNNF pairs with the reported parameters as a white-box upper reference. The learn-then-compare method of Efficient Distance Approximation for Structured High-Dimensional Distributions via Learning. is run on synthetic Bayesian networks with known in-degree, where its assumptions hold. Both get the same total query budget as our method.
Why not just…?
Why not just run DistEstimate with the reference evaluated exactly? This is the most direct alternative. It is a real threat if the cubic cost is mostly symmetric overhead. However, exact evaluation removes only one of the two per-coordinate estimates, so by the structure of DistEstimate's analysis it should save a constant factor and leave the $n^3$ scaling intact. This is exactly the ablation above. If it matches our estimator's scaling, we will conclude that the savings come from access alone and report the proposal's algorithmic claim as refuted.
Why not just use a non-tolerant subcube tester with a small $\epsilon$? The uniformity tester of Random Restrictions of High-Dimensional Distributions and Uniformity Testing with Subcube Conditioning costs only about $\sqrt{n}/\epsilon^2$. In the flat setting, The Price of Tolerance in Distribution Testing shows that such testers tolerate only $\epsilon_1$ up to roughly $\epsilon_2/n^{1/4}$. We will measure the subcube analogue directly. We plant samplers at known distance 0.05 to 0.1 from the reference and check whether the non-tolerant tester rejects them. We expect it to, and that would be the practical failure.
Why not just learn both distributions and compare? Learning works when the structure is known and has low degree, but its cost grows like $|\Sigma|^{d+1} n$ in the in-degree $d$ (Efficient Distance Approximation for Structured High-Dimensional Distributions via Learning.). The distributions over solutions of a circuit have no known sparse graph. The Bayesian-network experiments will show how narrow the regime is where learning wins.
Why not just use Teq? Teq needs approximate counting on both sides. The file notes it fails for general DNNFs and for black-box samplers such as STS and CMSGen. It remains the reference where it applies.
Proposed Experiments
The testbeds are those already in the literature:
- ISCAS89 circuits with up to 37 variables, and random 3-CNF formulas with $n$ from 20 to 70, sampled by STS and CMSGen (Distance Estimation for High-Dimensional Discrete Distributions);
- d-DNNF circuits with one-variable perturbations (Testing Probabilistic Circuits), where exact counting provides pointwise evaluation of the reference.
Ground-truth distance is computed by exact counting where feasible.
The first decisive check is the scaling exponent. For each estimator, we find the queries needed to reach mean absolute error 0.09 at $\epsilon = 0.3$ as $n$ grows, and fit a log-log slope. The target is a slope of at most about 2, against roughly 3 for DistEstimate.
The second check targets the weak point of the theory. We build adversarial samplers whose log-ratio is concentrated on a few coordinates, and samplers whose log-ratio piles up near zero. On these instances plain subsampling and smoothing respectively should degrade. The hybrid and a fallback to $\epsilon$-accuracy should recover. If they do not, the claimed $n^2/\epsilon^4$ rate is not worst-case.
The third check probes the lower bounds. On our candidate hard families, with tolerant uniformity and one-block normalization hardness for equivalence, we measure the best achievable error per query for identity access versus equivalence access. A persistent gap would be empirical evidence for the tolerant subcube chasm.
The note succeeds if it delivers two things: an algorithm with provably better scaling in $n$ and $\epsilon$ for the asymmetric case, and a matching or near-matching lower bound that states which of the three problems, if any, is inherently near-linear.
References
- Random Restrictions of High Dimensional Distributions and Uniformity Testing with Subcube Conditioning
- Distance Estimation for High-Dimensional Discrete Distributions
- A Chasm Between Identity and Equivalence Testing with Conditional Queries
- The Price of Tolerance in Distribution Testing
- Exploring the Gap Between Tolerant and Non-Tolerant Distribution Testing
- On Tolerant Distribution Testing in the Conditional Sampling Model
- Efficient Distance Approximation for Structured High-Dimensional Distributions via Learning
- Testing Probabilistic Circuits
- Tight Lower Bound on Equivalence Testing in Conditional Sampling Model
- Testing Closeness With Unequal Sized Samples