{"id":"dd3bc0c2-da13-4004-8d0e-c0a32dcb0dc0","arxiv_id":"2502.07672","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Binning data and permuting bin labels preserves exactness and minimax power of U/V-statistic permutation tests while reducing permutation cost to B s^2 operations.","lead":"Permutation tests become far cheaper when data are first grouped into bins and only bin labels are permuted, while still controlling false positives exactly and keeping the statistical power of standard permutation tests. For common statistics like MMD and HSIC, the added cost of running the permutation test no longer grows with sample size once the original test statistic is computed.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Power proofs analyze a bin-level U-statistic (App. A.1 Eq. 30) not shown to equal the bin-permuted QTS computed by Alg. 1; without this identity, Thms. 1-4 do not apply to the implemented cheap test.","rationale":"The reader's CONDITIONAL verdict identifies two fragile premises: integer divisibility of bins and the unproven equivalence between the bin-aggregated statistic in Alg. 1 and the bin-level U/V-statistic analyzed in the proofs. I agree that the equivalence is the more serious issue, because it sits directly under the main power theorems. Divisibility is a real but easily fixable assumption; the equivalence gap is structural. If the auxiliary sequence used in Prop. 2 and Lemma B.2 is not the sequence actually used to set the critical value, then the quantile comparison method does not yield power guarantees for Alg. 1. The paper has substantial independent support in its reproducible experiments and the exactness argument, and I am not claiming the central result is false; rather, the proof as written appears to analyze a different test. A small symbolic or enumerative check would settle whether the two permutation distributions coincide, and if they do not, the power proofs need an additional argument or a modification of the algorithm. This is why I keep the verdict CONDITIONAL rather than moving to REJECT: the gap is concrete and checkable, but no contradiction with the claimed rates has been established yet.","tokens_in":84138,"tokens_out":9280,"duration_ms":89102,"concrete_test":"Take s = 4, n1 = n2 = 2m with m = 2 (so s1 = s2 = 2), let g(y,z) = I(y = z), and fix a dataset with all distinct values. Enumerate all 4! bin permutations and compute (i) T_b exactly as in Alg. 1 from the Phi sums and (ii) U^{pi,s} from Eq. (30). If the multisets {T_b} and {U^{pi,s}} differ, the App. A.1 equivalence is false; then re-derive the power bound of Thm. 1 using E[Var(T_b | X)] in place of E[Var(U^{pi,s} | X)] and check whether the stated threshold gamma_{n1,n2,s} still holds. If the two multisets coincide exactly, the concern is refuted.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The load-bearing step is the asserted equivalence between what Alg. 1 actually computes and the statistic whose permutation distribution the proofs analyze. Alg. 1 (Sec. 3.2) computes, for each bin permutation pi, the quadratic test statistic T_b of the permuted point partition: for a homogeneity U-statistic base, this is exactly the point-level U-statistic U_{n1,n2} of the permuted samples. The cheap-power proofs (Thm. 1 and App. B.2.2) instead control the conditional variance of the bin-level object U^{pi,s}_{n1,n2} defined in App. A.1 Eq. (30), a U-statistic whose atoms are bins and whose kernel is H_{ho,m}. The only bridge is the sentence in App. A.1 saying the substitutions 'help us to frame' the cheap test as a standard U-statistic permutation test on bins; no identity, distributional equality, or stochastic dominance is proved. The two objects are not algebraically equal: for s1=s2=1, T_b is the point-level U_{m,m}, whereas the bin-level object is H_{ho,m}, and the discrepancy persists for s >= 4 as a mixture of within-bin and cross-bin terms that Eq. (35) does not track. Since Prop. 2 requires the auxiliary sequence to be the actual sequence generating the critical value, the quantile comparison argument as written proves power for a different procedure than Alg. 1. This gap is load-bearing: if it is not closed, the central claim that Alg. 1 inherits the stated cheap power thresholds is unsupported.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes 'cheap permutation tests': instead of permuting individual datapoints, one partitions the sample into s bins and permutes the bins. For quadratic test statistics (QTS), including homogeneity U-statistics and independence V-statistics, the paper shows that the bin-permuted statistics can be computed in O(B s^2) time after an O(n^2) precomputation, using O(s^2) sufficient statistics. The paper claims that these cheap tests inherit the exact finite-sample level of standard permutation tests and that their power matches standard permutation power up to constants, with the same minimax separation rates. The main theorems (Thms. 1-4) give explicit separation thresholds for cheap and standard tests, and Section 5 derives minimax optimality corollaries. Experiments compare cheap MMD, RFF, WMW, and HSIC tests against their standard and asymptotic counterparts.","tokens_in":84473,"tokens_out":21724,"duration_ms":195108,"significance":"If the power results hold for the implemented algorithms, this is a valuable contribution: it offers exact, finite-sample valid tests whose permutation overhead is independent of n, together with refined power guarantees for standard permutation tests. The exactness argument (Prop. 1) and the computational complexity statements are straightforward and convincing. The power proofs are substantial and introduce a quantile comparison method (Prop. 2) that improves on previous two-moments analyses. The experiments are extensive and the code is publicly available. However, the central power theorems are proven for a bin-level U/V-statistic that is not shown to equal the statistic actually computed by Algs. 1 and 2; this mismatch is load-bearing for the paper's main claim.","major_comments":[{"comment":"The power analysis for cheap homogeneity testing is carried out for the bin-level U-statistic U^{pi,s}_{n1,n2} defined in Eq. (30), not for the statistic T_b computed by Alg. 1. For m = n/s > 1 these objects differ: Eq. (30) averages H_ho,m over ordered quadruples of distinct bins, so it includes only point quadruples whose two Y-points and two Z-points lie in distinct bins, under the normalization (s1)_2(s2)_2; the QTS in Alg. 1, by contrast, is the point-level U-statistic U_{n1,n2} of the permuted point sample, whose normalization is (n1)_2 (n2)_2 and which additionally includes within-bin Y-Y and Z-Z point pairs. The sentence in App. A.1 that the substitutions 'help us to frame' the cheap test as a standard U-statistic test on bins is not a proof of equality, and no distributional identity or stochastic dominance is supplied. Since Prop. 2 requires the auxiliary sequence to be the actual sequence generating the critical value, Theorems 1-4 and Propositions 3-6 currently establish power for a different procedure than the one implemented and benchmarked. This gap is load-bearing for the paper's central claim and must be closed, either by proving that T_b has the same permutation distribution as (30) (up to a term whose effect on the quantile comparison is controlled) or by redefining the algorithm to compute the analyzed statistic and re-running the experiments.","section":"App. A.1, Eq. (30); Alg. 1, lines 7-8"},{"comment":"The independence power theorems have the same mismatch. Alg. 2's T_b is the point-level independence V-statistic of Def. 3 evaluated on bin-permuted Z-blocks, while the proofs analyze V^{pi,s}_n of Eq. (32), which replaces h_in by the bin-averaged kernel H_in,m. For m > 1 these statistics are not equal: the bin-averaged kernel treats all m^4 point combinations within the four selected bins, including within-bin point pairs, whereas the point-level V-statistic uses the normalization n^4 and the original kernel h_in. Consequently the bounds of Thm. 3, Cor. 2, and Thm. 4 do not apply to the implemented Alg. 2 without an additional equivalence argument.","section":"App. A.2, Eq. (32); Alg. 2, lines 16-17"}],"minor_comments":[{"comment":"The homogeneity algorithm assumes that n is divisible by s and that s1 = s n1/n is an integer, but this is only implicit in the main text and in App. A.1. State these assumptions explicitly, as is done for the independence setting in Sec. 3.4.","section":"Sec. 3.2 / Alg. 1"},{"comment":"The phrase 'final-sample validity' appears to be a typo for 'finite-sample validity'; please correct it in the two places where it occurs.","section":"Secs. 6.1.2 and 6.2.2"},{"comment":"The displayed expression for eps_{n1,n2,s} contains a line break and missing parentheses that make the formula hard to parse; please re-typeset it so that the nested radicals are unambiguous.","section":"Cor. 1, Eq. (12)"},{"comment":"The text states that Prop. 2 requires only B >= 1/alpha - 1 permutations, but this condition is not included in the proposition statement. Add it explicitly, since it is needed for the quantile comparison argument.","section":"Sec. 4.3, Prop. 2"},{"comment":"The proof of Lemma D.5 relies on a distributional construction cited from [29, Sec. 6.1]; since this is central to the sub-Gaussian threshold bound, a self-contained statement of the construction would improve readability.","section":"App. D.6"}],"recommendation":"major_revision","confidential_remarks":"The paper is potentially useful and the exactness and complexity results are solid. The main obstacle is the mismatch between the statistic analyzed in the power proofs and the statistic computed by Algs. 1 and 2. If the authors can prove the required equivalence, or restructure the algorithm and theorems so that they align, the paper could be acceptable. I would also encourage the editor to ask for an explicit statement of the divisibility assumptions, since they affect the definitions of the algorithms."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The core idea is simple and attractive: bin the data, permute bins, and reuse bin-level sufficient statistics so each permutation costs O(s^2) instead of O(n^2). The exactness claim is correct by exchangeability, and the runtime savings are real. The paper also contributes a sharper quantile-comparison lemma and refined variance bounds for standard permutation tests, and the experiments are thorough and reproducible.\n\nThe soft spot is load-bearing. The power proofs (Thm. 1 through Thm. 4) analyze the bin-level U/V-statistic defined in App. A.1 (Eq. 30 and Eq. 32), where the kernel is H_ho,m or H_in,m and the atoms are bins. But Alg. 1 computes, for each bin permutation, the ordinary quadratic test statistic of the bin-permuted point samples. For a homogeneity U-statistic that is exactly the point-level U-statistic of the permuted points, not the bin-level statistic. The paper says the substitutions \"help to frame\" the cheap test as a permutation test on bins, but it never proves an identity or stochastic dominance between the two objects. For s1=s2=1 the two clearly differ, and for larger s there is a mixture of within-bin and cross-bin terms that Eq. (35) does not track. Without equality, Prop. 2's requirement that the auxiliary sequence be the actual sequence generating the critical value is not met, so the theorems do not establish power for the implemented test.\n\nThis is not a small technicality. The central claim of the paper is that cheap permutation tests inherit the power and minimax rates of standard tests; the proof of that claim currently applies to a different procedure. The gap may be fixable—the point-level statistic likely has similar variance behavior—but fixing it requires real work, not just a remark.\n\nMinor issue: the homogeneity test assumes s divides n evenly but never states it in Alg. 1 or App. A, and no rounding correction is given; the independence section is explicit about this, the homogeneity section is not.\n\nWho is this paper for? Statisticians and ML researchers interested in fast permutation tests. The runtime idea is worth knowing, and the quantile comparison method is a useful tool on its own. But as a contribution about cheap permutation testing, it needs a corrected proof or a revised algorithm. I would not cite it as-is, though I would send it to a serious referee: the issue is substantive and the paper contains enough solid material that a revision could be valuable.","headline":"The paper has a genuinely promising idea and a lot of careful work, but as written the power theorems do not apply to the algorithm they implement: the proofs analyze a bin-level statistic that is not shown to equal the statistic computed in Alg. 1.","tokens_in":84967,"tokens_out":8013,"would_cite":false,"duration_ms":68205,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["62G10","62G09","62C20"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper claims that permutation tests can be made nearly free by permuting pre-computed bins of data points: each bin-permuted statistic costs time independent of the sample size, while the test keeps exact level control, power close…","keywords":["Permutation testing","nonparametric","minimax optimality","homogeneity","independence","quadratic test statistics","U-statistics","V-statistics"],"falsifier":"Take a small instance (for example $s=4$, $n_1=n_2=8$) with a fixed kernel $g$, enumerate all $s!$ bin permutations, and compute the full permutation distribution of the statistic produced by Algorithm 1; compare its level-$\\alpha$ acceptance region and rejection probability against the distribution of the binned U/V-statistic analyzed in the proofs—any mismatch in rejection probability would show the implemented and analyzed statistics differ. A second check uses $n$ not divisible by $s$ (e.g., $n=10$, $s=4$): simulate the claimed exact $\\alpha$ level and the theorem's predicted power threshold to see whether the equal-bin assumption is genuinely load-bearing.","tokens_in":83958,"feed_emoji":"⚡","tokens_out":8606,"duration_ms":82495,"temperature":0.7,"pith_summary":"This paper claims that permutation tests—the standard, exact way to test for distributional difference or dependence—can be accelerated dramatically by permuting pre-grouped bins of data points rather than individual points. For the quadratic test statistics that cover MMD, HSIC, energy distance, distance covariance, and Wilcoxon-Mann-Whitney, it proves that bin-permuted tests keep the exact finite-sample level of the standard test, and that their power matches the standard test's: the separation thresholds differ by at most constants, and for independence testing even $s=2$ bins preserve the rate. The key is storing bin-level sufficient statistics, so after one initial computation each permuted statistic costs time depending only on the number of bins, not on $n$. If correct, this gives practitioners exact minimax-optimal tests that run at roughly the cost of a single test-statistic evaluation, and the same analysis sharpens the existing power guarantees for standard permutation tests.","feed_headline":"Binned permutations match full-test power at near-zero cost","feed_subtitle":"Permuting data bins preserves minimax rates and makes each permuted statistic cost $O(s^2)$, independent of $n$.","key_machinery":"Two devices carry the argument. The first is bin-level sufficient statistics: for a homogeneity quadratic test statistic, the $3s^2$ block sums $\\Phi^w_{ij} = \\sum_{a\\in I_i}\\sum_{b\\in I_j} \\phi_w(X_a, X_b)$ for $w \\in \\{n_1, n_2, (n_1,n_2)\\}$, so every bin-permuted statistic is a quadratic form in these blocks; for an independence V-statistic, the $s^2/2$ aggregated terms $(D_{ii}, D_{i(i+s/2)})$ and $(S_{ij\\cdot})$ built from centered kernel products play the same role. These reduce the per-permutation cost from $\\Theta(Bn^2)$ to $\\Theta(Bs^2)$ with $\\Theta(s^2)$ memory, after a one-time $\\Theta(c_\\phi n^2)$ or $\\Theta(c_g n^2)$ precomputation. The second is the quantile comparison method, a two-moment argument that bounds the test statistic's fluctuations around its mean and the permutation threshold's conditional quantile using only $B \\geq 1/\\alpha - 1$ permutations, and whose refinement needs only variance components; these variance components are exactly what the power theorems evaluate for binned and unbinned U- and V-statistics.","core_discovery":"The central discovery is that a binned permutation test is both cheap and statistically equivalent to the standard test in the senses that matter. For a homogeneity quadratic test statistic or an independence V-statistic, permuting $s$ bins instead of $n$ points yields an exact level-$\\alpha$ test, with each permuted statistic computable in $\\Theta(s^2)$ elementary operations once $O(n^2)$ sufficient statistics are precomputed. For power, the separation thresholds for cheap tests are $\\Theta$ of the standard thresholds—$\\gamma_{n_1,n_2,s} = \\Theta(\\gamma_{n_1,n_2})$ for homogeneity when $s \\geq \\sqrt[3]{24(1-\\alpha^\\star)/(\\beta\\alpha^\\star \\rho_{n_1n_2})}$, and $\\gamma_{n,s} = \\Theta(\\gamma_n)$ for independence for any $s$—with asymptotic equivalence (ratio tending to $1$) as soon as $s$ grows, and these thresholds feed minimax-optimality results for discrete and H\\\"older $L_2$ homogeneity and independence. The analysis is carried by a new quantile comparison method that controls permutation-test power using only $B \\geq 1/\\alpha - 1$ permutations, which also improves the guarantees for standard permutation tests.","pith_inferences":["The equal-bin assumption ($m = n/s$ and $s_1 = s n_1/n$ integral) is explicit for the independence test but only implicit for homogeneity; if rounding is needed for arbitrary $n$, a direct analysis of unequal bins or a rounding correction would be the natural next step.","Because the permuted-statistic overhead is independent of $n$, cheap permutation can be stacked on sequential or early-stopping permutation schemes to make the entire testing process cost independent of sample size—a combination the paper notes but does not develop.","For low-rank feature kernels (e.g., random Fourier features), the cheap scheme's cost drops to $\\Theta(Bsr)$ with $\\Theta(sr)$ memory, which suggests the approach is especially favorable for high-dimensional kernel testing where $O(n^2)$ memory is prohibitive."],"forward_implications":["Independence testing with any fixed bin count—even $s=2$—keeps the standard test's separation rate, so the cheap version can be adopted with no rate loss.","For homogeneity, a bin count of order $\\sqrt[3]{1/(\\beta\\alpha^\\star\\rho_{n_1n_2})}$ preserves the rate, and any unboundedly growing $s$ makes the cheap threshold asymptotically equal to the standard one.","The quantile comparison method lowers the permutation requirement for standard Monte Carlo permutation tests to $B \\geq 1/\\alpha - 1$, improving on earlier constraints such as $B \\geq 8\\alpha^{-2}\\log(4/\\beta)$.","After precomputing bin sufficient statistics, the entire permutation loop costs $\\Theta(Bs^2)$ independent of $n$, so a slow-growing or constant $s$ makes total runtime comparable to evaluating the original statistic once.","Exactness holds for every sample size and data distribution, matching the standard permutation test's finite-sample validity rather than a large-sample approximation."],"supporting_citations":[{"why":"Supplies the exchangeability argument that makes both standard and binned permutation tests exactly level $\\alpha$.","marker":"[26]"},{"why":"Provides the standard-permutation power thresholds and minimax rates that cheap tests are required to match.","marker":"[29]"},{"why":"Defines the wild bootstrap scheme for degenerate independence tests that the cheapness construction accelerates by binning.","marker":"[12]"},{"why":"Pioneers the two-moments (quantile comparison) approach to non-asymptotic permutation power that Prop. 2 refines.","marker":"[20]"},{"why":"Contributes the tighter quantile-comparison argument that Prop. 2 generalizes, along with prior binned-permutation runtime gains.","marker":"[15]"},{"why":"Supplies the U-statistic variance decomposition used in the homogeneity power proofs.","marker":"[35]"},{"why":"Renders the homogeneity U-statistic as squared maximum mean discrepancy, connecting the abstract thresholds to kernel two-sample testing.","marker":"[24]"}],"fun_headline_variants":["Permute bins, not points: keep power, cut cost","Binning makes permutation tests cheap without losing power","Cheap permutation testing: bin the data, keep the power","Binned permutations: exact tests at a fraction of cost","O(s²) cost via binning: permutation power unaffected"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole edifice rests on clean bin geometry: the analysis assumes $n$ is divisible by $s$, that $s_1 = s n_1/n$ is an integer, and that the binned statistic studied in the proofs is exactly the statistic that the algorithms compute; when one of these fails, the equal-bin and statistic-identity premises of the theorems no longer hold.","fun_headline_variants_meta":{"raw":{"variants":["Permute bins, not points: keep power, cut cost","Binning makes permutation tests cheap without losing power","Cheap permutation testing: bin the data, keep the power","Binned permutations: exact tests at a fraction of cost","O(s²) cost via binning: permutation power unaffected"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001864,"raw_usage":{"total_tokens":7359,"prompt_tokens":1025,"completion_tokens":6334,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":641,"completion_tokens_details":{"reasoning_tokens":6252}},"tokens_in":641,"tokens_out":6334,"duration_ms":47987,"temperature":1.0,"reasoning_tokens":6252,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-08T11:58:25.289071+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a small instance (for example $s=4$, $n_1=n_2=8$) with a fixed kernel $g$, enumerate all $s!$ bin permutations, and compute the full permutation distribution of the statistic produced by Algorithm 1; compare its level-$\\alpha$ acceptance region and rejection probability against the distribution of the binned U/V-statistic analyzed in the proofs—any mismatch in rejection probability would show the implemented and analyzed statistics differ. A second check uses $n$ not divisible by $s$ (e.g., $n=10$, $s=4$): simulate the claimed exact $\\alpha$ level and the theorem's predicted power threshold to see whether the equal-bin assumption is genuinely load-bearing.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the exchangeability argument that makes both standard and binned permutation tests exactly level $\\alpha$."},{"cited_title":"and W ASSERMAN , L","cited_arxiv_id":null,"evidence_quote":"Provides the standard-permutation power thresholds and minimax rates that cheap tests are required to match."},{"cited_title":"P., SEJDINOVIC , D","cited_arxiv_id":null,"evidence_quote":"Defines the wild bootstrap scheme for degenerate independence tests that the cheapness construction accelerates by binning."},{"cited_title":"and R EYNAUD -BOURET , P","cited_arxiv_id":null,"evidence_quote":"Pioneers the two-moments (quantile comparison) approach to non-asymptotic permutation power that Prop. 2 refines."},{"cited_title":"and M ACKEY, L","cited_arxiv_id":null,"evidence_quote":"Contributes the tighter quantile-comparison argument that Prop. 2 generalizes, along with prior binned-permutation runtime gains."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the U-statistic variance decomposition used in the homogeneity power proofs."},{"cited_title":"M., R ASCH , M","cited_arxiv_id":null,"evidence_quote":"Renders the homogeneity U-statistic as squared maximum mean discrepancy, connecting the abstract thresholds to kernel two-sample testing."}],"review_version":1}