{"id":"0a550425-584c-446e-a986-f93b583d68e9","arxiv_id":"2508.19183","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"Tower robustness measures a model's expected accuracy over random perturbations within an Lp ball and comes with computable lower and upper bounds based on exact binomial tests.","lead":"This paper proposes Tower robustness, a probabilistic measure of how often a model predicts correctly under random small input perturbations, and derives statistical lower and upper bounds for it using exact binomial hypothesis tests. The authors argue it gives a global, comparable guarantee that existing robustness metrics cannot offer.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Type II error guarantee asserted in §4.1 is unsatisfiable for a fixed-size exact binomial test near the boundary; unproved inequalities (26)-(27) invalidate the upper bound (33) and the claimed simultaneous error control.","rationale":"The reader's weakest_assumption identifies exactly the unproved type II error control in (26)-(27), and I agree that this is the most load-bearing flaw in the upper-bound argument. My partial disagreement is that the lower bound (40), which is the more practically important 'global guarantee', does not actually require the type II bound: starting from (30), P(a1)=(P(a2)−b)/(1−c+b) with b=P(a2|¬a1)≤α and c=P(¬a2|a1)≥0 implies P(a1)≥(P(a2)−α)/(1+α), using only type I control. The paper's proof of Lemma 4.1 invokes both inequalities, but the lower-bound conclusion is salvageable with a corrected proof. The upper bound (33) is genuinely invalid as stated because near the boundary p⊺=κ−δ the type II error of any fixed-size exact test tends to 1−α, so (26) cannot hold. This makes the paper's headline claim of two-sided 'global bounds' overstate what is established. The experiments also lack error bars and code, but that is secondary. The conditional verdict already captures 'addressable correctness risk', and the required fix is clear: state the lower bound with only type I error, and either drop the upper-bound theorem or replace it with a valid sequential/confidence-based procedure that explicitly controls both error rates. Thus I do not move the verdict; I would keep CONDITIONAL with the revision requirement sharpened toward §4.1 and Theorem 4.2.","tokens_in":1067,"tokens_out":987,"duration_ms":136103,"concrete_test":"Simulate the §4.1 decision rule: with κ=0.1, α=0.05, n=100, reject H0:p⊺>0.1 iff the exact binomial lower-tail p-value P(K≤k | Bin(100,0.1)) ≤ 0.05. Evaluate at true p⊺=0.099 (so a1 holds). Compute the empirical frequency of failing to reject H0 over ≥10^4 repeated samples. If that frequency is close to 1−α≈0.95 (i.e., not <α), inequality (26) fails and the proof of upper bound (33) collapses. Repeat with n obtained from formula (25), noting p̂⊺ must be specified and the formula is only asymptotic.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's statistical core is the assertion, after eq. (25), that the exact binomial test per input satisfies P(¬a2|a1)<α and P(a2|¬a1)<α (inequalities (26)-(27)), where a1 means the local misprediction probability p⊺ is ≤κ. The second inequality is ordinary type I error and can be controlled. The first is a type II error guarantee for the composite alternative H1: p⊺≤κ, and it cannot hold uniformly at a fixed sample size: as p⊺ approaches κ from below, the power of any level-α test converges to α (by continuity of the binomial CDF), so the type II error tends to 1−α, which is not <α for α<1/2. Formula (25) is an asymptotic sample-size calculation involving the unknown p̂⊺, not a uniform guarantee over the composite alternative. Lemma 4.1's upper bound P(a1) (P(cPRA)−α)/(1+α) into (43) yields ((1−κ)(P(cPRA)−α))/(1+α), not ((1−κ)P(cPRA)−α)/(1+α) as written in (44). The displayed bound (40) is numerically weaker and happens to be valid, but only if one adds an extra inequality; the proof as written is incorrect. Please correct the substitution or make the weakening step explicit.","section":"§4.2.2, Theorem 4.3, Eq. (44)"},{"comment":"The claim that κ and α have been 'eliminated' is not correct: both parameters appear explicitly in (40) and (33), and cPRA is itself defined using κ and α. The further claim that one may freely choose different (κ,α) for different models and still compare lower bounds is not justified; reducing κ or α changes the event cPRA and the value of P(cPRA) in a model-dependent way, and no monotonicity theorem is proved. This affects the paper's central 'fair comparison' and 'global guarantee' narrative.","section":"§4.2.2, after Eq. (40)"},{"comment":"The reported lower/upper bounds are computed from an empirical estimate of P(cPRA) (the sample mean over the test set), but the paper does not provide confidence intervals or finite-sample concentration bounds for this estimate. Since a 'pre-deployment guarantee' must hold with respect to the true cPRA probability, the plotted values are point estimates rather than guaranteed bounds. Please state the sampling procedure, perturbation sample sizes, and how estimation uncertainty is accounted for.","section":"§5, Figure 2"}],"minor_comments":[{"comment":"The p-value formula is notated inconsistently: 'P(k > k)' is written but the displayed sum is P(K ≤ k). Please correct the tail direction and notation.","section":"§4.1, Eq. (22)"},{"comment":"Formula (25) uses z_α, but for α<1/2, z_α is negative; as written the numerator can be negative and the formula is ambiguous. Please define the quantiles and the intended error rates.","section":"§4.1, after Eq. (25)"},{"comment":"The notation P_{||x'-x||_p≤ε}(h(x')=y) is not formally defined. Please specify the underlying random experiment: x,y drawn from D, then x' drawn uniformly from the ε-neighborhood of x.","section":"§3.2, Definition 3.1"},{"comment":"The decision rule for combining the two one-sided tests for a single input-label pair is not specified. Please state exactly when a2, ¬a2, or neither is declared.","section":"§4.1, 'Both left- and right-tailed tests'"},{"comment":"No details are given on the number of perturbations sampled per input, the significance level used in the experiments, or the computation of cPRA from the test set. Figure 2 has no error bars. The abstract's 'extensive comparative evaluation' is overstated given the absence of baseline comparisons.","section":"§5"}],"recommendation":"major_revision","confidential_remarks":"The upper-bound contribution cannot be accepted as is: the type II error guarantee in §4.1 is fundamental and cannot be patched by a simple correction. The authors should either provide a valid uniform type II error construction (e.g., via a sequential or confidence-interval approach) or remove the upper-bound theorem and revise the title/abstract accordingly. The lower-bound idea is worth pursuing in a revised manuscript, but the current proofs and experimental reporting are not yet at publishable standard."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The first thing you should know: the proposed Tower robustness, P(h(x')=y) under random neighbor sampling, is not a new quantity. It is the same smoothed accuracy used in randomized smoothing, which the paper itself cites. What is marginally new is the attempt to bound it by first testing each point's misprediction rate with an exact binomial test and then aggregating via Markov/Tower. That aggregation idea is not crazy, and the paper does a decent job of surveying why attack-based and certification-based metrics disagree. I'll also credit the exact binomial test over Agresti-Coull as a more principled choice for small samples.\n\nThe soft spots are serious. The upper bound in Theorem 4.2 depends on inequality (27), the claim that the type II error P(¬a2|a1) < α for each point. That cannot be true for a fixed-size exact binomial test: as the true misprediction probability approaches κ from below, the test's power approaches its size α, so the type II error tends to 1−α, which is not < α for α<0.5. So (27) is not a uniform guarantee. That kills the upper bound as stated. The lower bound (40) may survive because it only needs type I control, but I think there is an algebraic slip in Theorem 4.3: substituting the lower bound (P(cPRA)−α)/(1+α) into (43) should give ((1−κ)(P(cPRA)−α))/(1+α), not ((1−κ)P(cPRA)−α)/(1+α). So expression (40) as written is off by a factor on the α term. Somebody should check whether they meant something else.\n\nThe experiments are illustrative only: no sample sizes, no error bars, no baselines, and the GitHub repo is a placeholder, so the practical claim is unsubstantiated. Also the 'elimination' of κ and α is cosmetic; they remain free choices and the paper does not justify that differing choices give comparability.\n\nWho is this for? A practitioner looking for a quick probabilistic robustness score might find the corrected lower bound useful as a heuristic. But as it stands, the global guarantee is not established. It should go to peer review because the topic matters and the errors are fixable, but it needs major revision and re-derivation of the bounds.","headline":"Tower robustness is smoothed accuracy with a binomial-test wrapper; the upper bound rests on an unreliable type II error guarantee and the lower bound has an algebraic slip.","tokens_in":19199,"tokens_out":3166,"would_cite":false,"duration_ms":32660,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["62F03","68T07"],"pacs":[],"model":"deepseek-v4-flash","headline":"One probability now bounds any model's perturbation robustness","keywords":["tower robustness","probabilistic robustness","adversarial robustness","exact binomial test","hypothesis testing","robustness certification","Tower Law","deep neural networks"],"falsifier":"Simulate the per-point test: for many points whose true misprediction probability is exactly kappa, or slightly above or below it, draw the prescribed number of perturbation samples and count how often the left-tailed and right-tailed tests make each error. If either empirical error rate exceeds alpha, inequalities (26) and (27) fail and the global bounds are not guaranteed. A second check is to enumerate all neighbors exactly for a small model and compare the true Tower robustness against the paper's lower bound; any violation of inequality (40) would refute the method as stated.","tokens_in":18324,"feed_emoji":"🛡️","tokens_out":8717,"duration_ms":85571,"temperature":0.7,"pith_summary":"The paper proposes Tower robustness, defined as the probability that a model's prediction is correct on a randomly perturbed input inside an epsilon ball, and argues this single scalar is the natural global measure of perturbation robustness. It shows how to estimate a computable lower bound and a computable upper bound on this quantity from a finite test set, using an exact binomial test on each input-label pair and then eliminating the two helper parameters kappa and alpha with the Tower Law, total probability, and Markov's inequality. If the argument is right, a model's pre-deployment robustness can be reported as one certified number, different models can be compared even when evaluated under different settings, and deterministic and probabilistic verification results can be combined without losing the guarantee.","feed_headline":"One number now bounds any model's perturbation robustness","feed_subtitle":"Exact binomial tests yield provable lower and upper bounds, so models can be compared fairly.","key_machinery":"Tower robustness (Definition 3.1) is the central object: P(h(x')=y | ||x'-x||_p ≤ epsilon). The proof chain uses the Tower Law E[E[b|a]]=E[b] to express it as an expectation of per-neighborhood correctness; the law of total probability to remove the significance level alpha; and Markov's inequality, with a known upper bound on per-neighborhood misprediction, to remove the tolerance kappa. Per test point, an exact binomial test with both left- and right-tailed rejection decides whether the neighborhood's misprediction probability is at most kappa. Inequalities (26) and (27), which bound the two directions of test error by alpha, carry the global guarantee.","core_discovery":"The paper claims that perturbation robustness is a single probabilistic quantity: Tower robustness, P(h(x')=y | ||x'-x||_p ≤ epsilon), the chance a model is correct on a random input drawn from the epsilon-neighborhood of a random natural input. Deterministic certifiable robust accuracy is an unbiased estimator of its lower bound. Using an exact binomial test per point plus the Tower Law, total probability, and Markov's inequality, the paper gets global bounds independent of helper parameters kappa and alpha: lower ((1-kappa)P(cPRA)-alpha)/(1+alpha), upper kappa P(cPRA)/(1-alpha)-kappa+1; cPRA means the per-point event that misprediction probability is certified below kappa. These bounds are","pith_inferences":["The decomposition suggests a direct generalization: replace the uniform (p, epsilon)-ball with any perturbation distribution, and the same Tower-Law structure will express expected correctness under that distribution as an expectation of per-point conditional correct probabilities, potentially certifying robustness to rotations, brightness, or other semantic perturbations.","A testable extension is to partition the input space and report a Tower robustness bound per class or per region; the Tower Law should make the global bound a weighted average of local bounds, giving practitioners a localization of where robustness fails.","Because the bounds use only the model's predicted labels, the same certificate should apply to black-box decision rules such as ensembles or non-differentiable pipelines, a generality the paper does not spell out."],"forward_implications":["Model robustness can be reported as a single certified scalar instead of an attack-dependent accuracy, so rankings no longer depend on which adversarial attack was used.","Two models evaluated with different kappa and alpha values can be compared fairly through the same lower- and upper-bound formulas.","Deterministic certified robustness and probabilistic robustness can be combined in one framework, with deterministic verification covering some cases and probabilistic testing covering the rest.","Tightening kappa or alpha raises the reported lower bound without invalidating it, removing the incentive to inflate robustness scores by choosing loose helper parameters.","The upper bound, while not a safety certificate, can expose when a model's actual robustness may be far worse than its lower bound suggests."],"supporting_citations":[{"why":"Supplies the probabilistic robustness condition c_PR (misprediction probability at most kappa) that the per-point test checks, and the MLE-based baseline the paper contrasts with its exact binomial test.","marker":"[29]"},{"why":"Introduces PRoA, the prior probabilistic robustness assessment using Agresti-Coull confidence intervals, which the paper extends and corrects with an exact test.","marker":"[42]"},{"why":"Cited to support the claim that Agresti-Coull approximations can produce incorrect inferences near probabilities 0 or 1, motivating the exact binomial approach.","marker":"[1]"},{"why":"Provides the systematisation of certified robustness that the paper uses to situate deterministic and probabilistic robustness in one landscape.","marker":"[22]"},{"why":"Source of the sequential-test sample-size methodology cited for choosing the number of perturbation samples in the binomial test.","marker":"[35]"},{"why":"Companion reference for sample-size estimation in the hypothesis test, grounding the practical computability of the bounds.","marker":"[26]"}],"fun_headline_variants":["Probabilistic robustness: one number with exact global bounds","Tower robustness: exact bounds, no helper parameters","Global bounds on robustness via binomial tests","Robustness as probability: tight global guarantees","One metric, exact bounds: tower robustness"],"cache_read_input_tokens":2688,"weakest_assumption_plain":"The entire guarantee rests on the claim that a single per-point test, on a fixed number of sampled neighbors, keeps both kinds of mistakes below the chosen small rate alpha; the paper states this as a fact but does not prove it.","fun_headline_variants_meta":{"raw":{"variants":["Probabilistic robustness: one number with exact global bounds","Tower robustness: exact bounds, no helper parameters","Global bounds on robustness via binomial tests","Robustness as probability: tight global guarantees","One metric, exact bounds: tower robustness"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000544,"raw_usage":{"total_tokens":2395,"prompt_tokens":656,"completion_tokens":1739,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":400,"completion_tokens_details":{"reasoning_tokens":1668}},"tokens_in":400,"tokens_out":1739,"duration_ms":11897,"temperature":1.0,"reasoning_tokens":1668,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T15:53:27.974787+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Simulate the per-point test: for many points whose true misprediction probability is exactly kappa, or slightly above or below it, draw the prescribed number of perturbation samples and count how often the left-tailed and right-tailed tests make each error. If either empirical error rate exceeds alpha, inequalities (26) and (27) fail and the global bounds are not guaranteed. A second check is to enumerate all neighbors exactly for a small model and compare the true Tower robustness against the paper's lower bound; any violation of inequality (40) would refute the method as stated.","supporting_citations":[{"cited_title":"Pappas, and Hamed Hassani","cited_arxiv_id":null,"evidence_quote":"Supplies the probabilistic robustness condition c_PR (misprediction probability at most kappa) that the per-point test checks, and the MLE-based baseline the paper contrasts with its exact binomial test."},{"cited_title":"Fieldsend","cited_arxiv_id":null,"evidence_quote":"Introduces PRoA, the prior probabilistic robustness assessment using Agresti-Coull confidence intervals, which the paper extends and corrects with an exact test."},{"cited_title":"SoK: Certified Robustness for Deep Neural Networks","cited_arxiv_id":"2009.04131","evidence_quote":"Provides the systematisation of certified robustness that the paper uses to situate deterministic and probabilistic robustness in one landscape."},{"cited_title":"In Advances in Neural Information Processing Systems , M","cited_arxiv_id":null,"evidence_quote":"Source of the sequential-test sample-size methodology cited for choosing the number of perturbation samples in the binomial test."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Companion reference for sample-size estimation in the hypothesis test, grounding the practical computability of the bounds."}],"review_version":1}