{"id":"14235994-6257-4594-bc40-c994a96e636e","arxiv_id":"2501.00154","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"For linear classifiers, a relaxed notion of probabilistic sufficient reasons, (δ, ε)-SR, can be computed in polynomial time with high probability, despite exact computation being #P-hard.","lead":"This paper introduces a new type of probabilistic explanation for machine learning models, called (δ, ε)-sufficient reasons, which allows the probability guarantee to be off by a small amount ε. It shows that for linear models these explanations can be computed efficiently, the first such positive result for any model class.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Proof of Theorem 2 overclaims exact minimality for the sampled δ*; the E_k event fails on flat regions of the probability curve, so the binary search can return a non-minimal explanation.","rationale":"The reader identified the uniform-completion distribution as the weakest assumption, which is an acknowledged limitation of the model class rather than a flaw in the proof. The more load-bearing issue is internal to the main theorem's proof: Theorem 2 as proven requires the algorithm to output a minimum δ*-SR for the sampled δ*, and the E_k/F_k argument is supposed to guarantee that the binary search crossing is the true crossing. But when the greedy probability sequence is sufficiently flat, the final queried point is always within the Monte Carlo tolerance of δ*, so E_k fails deterministically for that query. In that case the comparison is dominated by sampling noise, and the returned k can be far from the true minimum k*. The proof's elaborate conditioning on the query set I does not rescue the argument because the intersection ∩_{k∈I}E_k is empty in this regime. This is a concrete, technical gap in the central result. The existential (δ,ε)-min-SR theorem might still be salvageable, since off-by-many explanations in a flat region can have probability within ε of δ, but that is a different statement from what the proof establishes. Therefore the paper should either repair the proof, add a separation condition on the p_k sequence, or weaken the algorithm's output guarantee to the existential definition. Given the central claim depends on this proof, the appropriate verdict is conditional acceptance pending this repair or clarification.","tokens_in":29699,"tokens_out":42107,"duration_ms":441799,"concrete_test":"Use n = 10^5 unit weights, threshold n/2 + √n, instance x = 1^n, δ = 0.5, ε = 0.5, and failure parameter η = 0.2. For many random δ* drawn uniformly from [δ−ε, δ+ε], run Algorithm 1 with m ≈ 3·10^4 Monte Carlo samples and compare the returned index k with the true minimum k* computed exactly from binomial tail probabilities. If the returned k differs from k* for a non-negligible fraction of trials, Algorithm 1 is not computing a minimum δ*-SR. Then separately check whether the returned k still satisfies the existential (δ,ε)-min-SR condition by testing whether p_k ∈ [δ−ε, δ+ε] and p_{k−1} < p_k; this distinguishes a proof gap from a counterexample to the existential theorem.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The correctness proof of Theorem 2 (Section 3, proof of Theorem 2) requires that for every queried k the event E_k: |δ* − p_k| ≥ εδ/log n holds, so that the Monte Carlo comparison p̂_k vs δ* agrees with the true comparison p_k vs δ*. This is not guaranteed in flat regions. For a linear model with n unit weights and threshold n/2 + c√n, instance x = 1^n, the greedy probabilities p_k have increments Θ(1/√n). For n large enough that 1/√n < εδ/log n, the final binary-search query lands at an index whose p_k is within εδ/log n of δ*, so E_k fails with probability 1 for every δ*. Meanwhile p̂_k has standard deviation ~εδ/(log n · √log log n), so the comparison at that query is essentially a coin flip; Algorithm 1 can return an index different from the true minimum k* for the sampled δ*. This contradicts the proof's conclusion and Algorithm 1's output line that the returned explanation is a minimum δ*-SR. The failure is not covered by the probability bound: in this regime ∩_{k∈I}E_k is empty, so the claimed lower bound Pr(∩_{k∈I}E_k) ≥ (1−δ)^2 in the proof cannot hold. The existential (δ,ε)-min-SR claim may still be true because a wrong index in a flat region has p_k within ε of δ*, but the argument given proves a stronger, false statement and therefore does not establish the main theorem as written.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces (δ, ε)-sufficient reasons, a two-parameter relaxation of the classical probabilistic sufficient reasons of Wäldchen et al., and proves that for linear models a (δ, ε)-min-SR can be computed in polynomial time, specifically in O~(n/(ε^2 δ^2)) time with success probability 1−δ. The algorithm samples a threshold δ* uniformly from [δ−ε, δ+ε], sorts features by a score, and binary-searches over the number of fixed features using Monte Carlo estimates of the acceptance probability. The paper also proves that locally minimal δ-SRs are subset-minimal for linear models under product distributions (Theorem 3), and gives a lower bound showing that a small change in δ can force a very large change in the minimum explanation size (Proposition 2). The structural lemma (Lemma 1) that the top-scoring features are optimal is proved carefully in the appendix.","tokens_in":30023,"tokens_out":21948,"duration_ms":234136,"significance":"If the main algorithmic claim is correct, it is a meaningful positive result in formal XAI: linear models would be the first model class for which approximate minimum probabilistic sufficient reasons can be computed efficiently, in contrast to the strong hardness results for decision trees and neural networks. The structural characterization of feature selection (Lemma 1 and its supporting Lemmas 6–10) is elegant and appears correct. The paper also provides a good summary of the hardness landscape and a useful size-gap lower bound. However, the proof of the central theorem, as written, proves a stronger statement than the theorem needs and that stronger statement is false; this is a load-bearing issue that must be fixed before the main contribution can be accepted.","major_comments":[{"comment":"The proof requires the event ∩_{k∈I} E_k, where E_k is |δ* − p_k| ≥ εδ/log n and I is the set of indices queried by the binary search. The flaw is that I is not independent of δ*: whenever the search behaves correctly, I contains the boundary index k* = min{k : p_k ≥ δ*}, and for that index p_{k*} is within one step of the sequence {p_k} of δ*. Consider a linear model with n unit weights, threshold n/2 + c√n, and instance x = 1^n. The probabilities p_k have increments Θ(1/√n). For n large enough that 1/√n < εδ/log n, the boundary index satisfies |δ* − p_{k*}| < εδ/log n for every δ*, so E_{k*} fails with probability 1. Hence Pr(∩_{k∈I} E_k) = 0, contradicting the lower bound claimed in the proof. A union bound over a fixed set of size ≤ log n cannot repair this, because I is random and contains exactly the index where the event is most likely to fail. Since the proof's correctness argument depends entirely on this intersection, Theorem 2 is not established as written.","section":"Section 3, proof of Theorem 2 (events E_k and F_k)"},{"comment":"The proof introduces a set I* defined as the binary-search path conditioned on all events E_k and F_k holding, and then uses Pr(I = I* | ∩ E_k ∩ ∩ F_k) = 1 to lower-bound Pr(∩_{k∈I} E_k). This step is circular: I* is defined by conditioning on the very events whose probability is being estimated, and it is not a fixed set independent of the random estimates and δ*. The transition from Equation (2) to the final bound silently replaces a sum over all possible sets I' by one particular set I*, without a lower bound on the conditional probability of I = I*. Thus the claimed lower bound of (1−δ)^2 is not derived from the preceding inequalities.","section":"Section 3, proof of Theorem 2, Eq. (2)–(4)"},{"comment":"The output specification of Algorithm 1 and the proof assert that the returned explanation is a minimum δ*-SR for the sampled value δ*. The boundary-index phenomenon described above shows that this stronger assertion is false: in the flat-region example, the Monte Carlo comparison at the final queried index is essentially a coin flip (since the estimator's standard deviation is larger than εδ/log n), so the algorithm can return an index adjacent to k*, which is not the minimum δ*-SR. Theorem 2 as stated only requires the existential condition of Definition 4—that the returned explanation be a minimum δ' -SR for some δ' ∈ [δ−ε, δ+ε]—and that weaker claim may be salvageable. But the current proof establishes only the stronger and false claim, and it provides no separate argument for the existential guarantee. Therefore the main theorem is not proven by the manuscript as it stands.","section":"Algorithm 1 and Theorem 2 statement"}],"minor_comments":[{"comment":"The symbol δ is overloaded: it denotes both the probability threshold in (δ, ε)-SR and the failure probability in Theorem 2 and in the sample size ρ in Algorithm 1. This makes the theorem and the algorithm difficult to read; use a separate symbol, e.g., β, for the failure probability.","section":"Section 3 and Theorem 2"},{"comment":"Definition 4 should restrict δ* to [0,1], or the theorem should assume ε ≤ min(δ, 1−δ). Otherwise the interval [δ−ε, δ+ε] can contain values outside [0,1], where the notion of a δ*-SR is not defined, and the algorithm samples δ* from that invalid interval.","section":"Definition 4"},{"comment":"In Appendix .1, the bound '2 · 1014' should read '2 · 10^{-14}'; in Section 6, the phrase 'the feature selection argument of ?? no longer holds' contains an unresolved cross-reference. These should be corrected.","section":"Appendix .1 and Section 6"}],"recommendation":"major_revision","confidential_remarks":"The paper makes a genuinely interesting contribution, and the structural lemmas in the appendix are solid. The main issue is that the proof of Theorem 2 overclaims minimality for the sampled δ*, and the probabilistic argument for the intersection of the E_k events is invalid. I believe the existential (δ, ε)-min-SR claim may still be true and repairable, but the authors need to rework the correctness proof substantially. I would not reject the paper on the basis of this single flaw if it can be fixed within a revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Worth a look, but the main theorem's proof is not sound. The (δ,ε)-SR relaxation is a good idea, and Lemma 1's greedy feature selection for linear models under the uniform distribution is a clean, genuinely useful result. The paper also gives a nice survey of the hardness landscape and an interesting theorem about locally minimal δ-SRs under product distributions. Credit where due: the appendix is serious, and the examples are helpful.\n\nThe soft spot is Theorem 2. The correctness proof relies on events E_k: |δ* − p_k| ≥ εδ/log n holding for every queried k, so that Monte Carlo comparisons agree with truth. But there are linear models where this fails deterministically for the final binary-search query. Take n unit weights, threshold n/2 + c√n, and x = 1^n. The probabilities p_k rise in steps of Θ(1/√n). For n large relative to (εδ/log n)^2, the boundary index k* for the sampled δ* has |δ* − p_{k*}| < εδ/log n, so E_{k*} fails with probability 1. The proof's claim that ∩_{k∈I}E_k has probability ≥ (1−δ)^2 is then false for this instance, because I always contains k*. The conditioning argument breaks: conditioning on the binary search path reveals information about δ* that voids the uniform union bound. The algorithm can return a non-minimal explanation for the sampled δ*. The existential (δ,ε)-min-SR claim may still be true—a wrong index in the flat region is usually a minimum δ'-SR for some nearby δ'—but the proof as written does not establish the theorem. This is a load-bearing gap, not a typo.\n\nOther soft spots are minor: the uniform-completion assumption is restrictive and the paper admits it; the runtime dependence on 1/ε^2 δ^2 is heavy. The citation pattern looks fair.\n\nWho is this for? Researchers in formal XAI and anyone who wants a first positive algorithmic result for probabilistic explanations on linear models. I would send it to a serious referee, but the referee should be told to focus on the proof of Theorem 2. If the proof can be patched, the paper is a solid contribution; if not, the main claim needs to be scaled back.","headline":"Promising ideas and a likely-true result, but the proof of the main theorem has a real gap that a referee needs to confront.","tokens_in":30508,"tokens_out":6223,"would_cite":true,"duration_ms":61873,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that for linear models, a small set of features that determines the model's decision with high probability can be computed in randomized polynomial time, making them the first classifier family with this guarantee.","keywords":["formal XAI","sufficient reasons","probabilistic explanations","linear models","(δ, ε)-min-SR","Monte Carlo estimation","feature scores","explanation complexity"],"falsifier":"Fix a small linear model, say $n=4$ with weights $(1,-2,3,-1)$ and threshold $0$, and an instance $x=(1,1,1,0)$; enumerate all subsets to compute the exact agreement probability of every partial instance under the uniform distribution. If, for some $k$, the top-$k$ prefix by score does not achieve the maximum agreement probability among all $k$-feature subsets, Lemma 10 is false and the algorithm's guarantee collapses. Alternatively, with the same model, draw $\\delta^*$ uniformly from $[0.4,0.6]$ and compare the greedy answer to the brute-force minimum $\\delta^*$-SR; any size mismatch for a $\\delta^*$ more than $\\varepsilon$ away from a threshold value would be a counterexample.","tokens_in":29535,"feed_emoji":"💡","tokens_out":16523,"duration_ms":132093,"temperature":0.7,"pith_summary":"This paper tries to establish that linear models are the first class of classifiers for which small probabilistic sufficient reasons can be computed efficiently. It introduces the $(\\delta,\\varepsilon)$-min-SR relaxation—an explanation that is a minimum $\\delta^*$-SR for some $\\delta^*$ within $\\varepsilon$ of the requested confidence $\\delta$—and proves that for any linear model and input, a $(\\delta,\\varepsilon)$-min-SR can be produced with high probability in time polynomial in the number of features, $1/\\varepsilon$, and $1/\\delta$. A sympathetic reader should care because the relaxation matches how people actually use confidence thresholds: a user who asks for a 95% explanation would not notice a 94.9997% one, but she would notice an explanation that is suddenly 250 times larger. This positive result contrasts sharply with decision trees, where even approximating small $\\delta$-SRs is hard unless SAT can be solved in quasi-polynomial time.","feed_headline":"Linear models get small probabilistic explanations in polynomial time","feed_subtitle":"Small, high-confidence feature subsets that justify a linear model's decision are now provably easy to find.","key_machinery":"The machinery has three pieces. First, the feature score $s_i = w_i (2x_i-1)(2\\mathcal{L}(x)-1)$ encodes whether feature $i$ helps or hurts the classification and by how much; under the uniform completion distribution, adding features in decreasing score order never decreases the agreement probability (Lemma 1). Second, because of Lemma 1, the minimum $\\delta^*$-SR is exactly the shortest score-sorted prefix whose agreement probability reaches $\\delta^*$, so the search reduces to a binary search over $k$. Third, the agreement probabilities are estimated by Monte Carlo sampling (Fact 1, via Hoeffding's inequality), and the algorithm randomizes $\\delta^*$ uniformly over $[\\delta-\\varepsilon, \\delta+\\varepsilon]$ to avoid the finitely many 'hard' thresholds where the probability is within $O(\\varepsilon\\delta/\\log n)$ of $\\delta^*$; the proof shows the estimates are accurate enough on the visited prefixes with probability $1-\\delta$. The randomization over $\\delta^*$ is what breaks the #P-hardness of the exact problem.","core_discovery":"The paper's central claim is Theorem 2: given a linear model $\\mathcal{L}$ and an input $x$, a $(\\delta,\\varepsilon)$-min-SR can be computed successfully with probability at least $1-\\delta$ in $\\tilde{O}(n/(\\varepsilon^2 \\delta^2))$ randomized time. The algorithm samples a target confidence $\\delta^*$ uniformly at random from $[\\delta-\\varepsilon, \\delta+\\varepsilon]$, sorts features by the score $s_i = w_i (2x_i-1)(2\\mathcal{L}(x)-1)$, and uses binary search with Monte Carlo estimates of the agreement probability of the top-$k$ prefixes; Lemma 1 guarantees that the top-$k$ prefix is the minimum $\\delta^*$-SR exactly when it is the first prefix whose agreement probability reaches $\\delta^*$. The paper also proves (Theorem 3) that under any product distribution every locally minimal $\\delta$-SR is subset-minimal for linear models, and (Proposition 2) that approximating $\\delta$ does not approximate explanation size: the minimum size can jump by a factor of $n^{1/2-\\varepsilon_0}$ when $\\delta$ is raised by $\\varepsilon$.","pith_inferences":["The random-$\\delta^*$ trick is transferable: any model class whose score-sorted prefixes have non-decreasing agreement probabilities would inherit the same Monte Carlo plus binary search template; decision trees fail this property, which is exactly why they stay hard.","A testable weakening: replace the uniform distribution with feature-dependent Bernoulli parameters; a majorization or convexity condition on the weights might restore the greedy ordering for some product distributions, a direction the paper leaves open.","The sample count grows like $1/(\\varepsilon^2 \\delta^2)$, so the authors' own example ($n=500$, $\\varepsilon=0.1$, $\\delta=0.01$) is expensive; importance sampling or quasi-Monte Carlo could shrink the constant without changing the asymptotic bound.","Because Proposition 2 shows that moving $\\delta$ by $\\varepsilon$ can enlarge the minimum explanation by a large factor, any deployed system should pair the explanation with its achieved confidence, not just the requested one."],"forward_implications":["Banks and other users of linear scoring models can now ask for a small, high-confidence explanation of a decision—say, 'your loan was rejected because of these three features, with 95% confidence'—and compute it in randomized polynomial time.","Linear models are the first class of classifiers for which a $(\\delta,\\varepsilon)$-min-SR is efficiently computable; for decision trees the problem remains inapproximable in polynomial time unless SAT is quasi-polynomially solvable.","The relaxation gives both sides what they want: a user receives an explanation no larger than the minimum $(\\delta-\\varepsilon)$-SR, while a model owner can enforce a strict $\\delta$ guarantee by computing a $(\\delta+\\varepsilon/2,\\varepsilon/2)$-min-SR.","For linear models under any product distribution, every locally minimal $\\delta$-SR is also subset-minimal, so local-search heuristics that find locally minimal explanations are actually finding globally subset-minimal ones.","Because $\\delta$-approximation and size-approximation are decoupled, systems should report the achieved confidence level explicitly rather than silently substituting the requested $\\delta$."],"supporting_citations":[{"why":"introduces δ-SRs and shows computing them for neural networks is hard, defining the problem this paper relaxes.","marker":"Wäldchen et al. (2021)"},{"why":"proves minimum 1-SRs are polynomial-time solvable for linear models and exact probability is #P-hard, underpinning Lemma 1 and Proposition 1.","marker":"Barceló et al. (2020)"},{"why":"proves decision-tree hardness of δ-SRs and supplies the local-minimality argument that Theorem 3 generalizes.","marker":"Arenas et al. (2022)"},{"why":"gives the decision-tree inapproximability for (δ, ε)-min-SR (Theorem 1) that motivates and contrasts with the paper's positive result.","marker":"Kozachinskiy (2023)"},{"why":"provides the concentration inequality behind Fact 1, which the Monte Carlo estimator relies on.","marker":"Hoeffding (1963)"},{"why":"introduces locally minimal probabilistic explanations and the Monte Carlo estimation idea used in the algorithm.","marker":"Izza et al. (2024)"},{"why":"defines sufficient reasons, the deterministic notion that the paper extends probabilistically.","marker":"Darwiche and Hirth (2020)"},{"why":"supplies Erdős' bound on the central binomial coefficient used in Proposition 2's size-jump construction.","marker":"Komjáth (2013)"}],"fun_headline_variants":["Tiny subsets, high confidence: efficient probabilistic explanations for linear models","Randomized sampling finds provably small explanations for linear classifiers","Linear models get fast, high-confidence minimal explanations","Small subsets, big confidence: probabilistic proofs for linear decisions","Efficient randomized explanations for linear models with guaranteed confidence"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the random completion of an explanation is drawn uniformly over all binary completions (or, more generally, that every feature is an independent Bernoulli variable with the same parameter); the greedy score ordering is provably optimal only under that assumption, and the paper itself notes that extending to arbitrary product distributions is not straightforward.","fun_headline_variants_meta":{"raw":{"variants":["Tiny subsets, high confidence: efficient probabilistic explanations for linear models","Randomized sampling finds provably small explanations for linear classifiers","Linear models get fast, high-confidence minimal explanations","Small subsets, big confidence: probabilistic proofs for linear decisions","Efficient randomized explanations for linear models with guaranteed confidence"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000558,"raw_usage":{"total_tokens":2728,"prompt_tokens":1093,"completion_tokens":1635,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":709,"completion_tokens_details":{"reasoning_tokens":1555}},"tokens_in":709,"tokens_out":1635,"duration_ms":10418,"temperature":1.0,"reasoning_tokens":1555,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T22:58:00.957842+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Fix a small linear model, say $n=4$ with weights $(1,-2,3,-1)$ and threshold $0$, and an instance $x=(1,1,1,0)$; enumerate all subsets to compute the exact agreement probability of every partial instance under the uniform distribution. If, for some $k$, the top-$k$ prefix by score does not achieve the maximum agreement probability among all $k$-feature subsets, Lemma 10 is false and the algorithm's guarantee collapses. Alternatively, with the same model, draw $\\delta^*$ uniformly from $[0.4,0.6]$ and compare the greedy answer to the brute-force minimum $\\delta^*$-SR; any size mismatch for a $\\delta^*$ more than $\\varepsilon$ away from a threshold value would be a counterexample.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"proves decision-tree hardness of δ-SRs and supplies the local-minimality argument that Theorem 3 generalizes."},{"cited_title":"Inapproximability of sufficient reasons for decision trees","cited_arxiv_id":"2304.02781","evidence_quote":"gives the decision-tree inapproximability for (δ, ε)-min-SR (Theorem 1) that motivates and contrasts with the paper's positive result."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"provides the concentration inequality behind Fact 1, which the Monte Carlo estimator relies on."},{"cited_title":"S., and Marques-Silva, J","cited_arxiv_id":null,"evidence_quote":"introduces locally minimal probabilistic explanations and the Monte Carlo estimation idea used in the algorithm."},{"cited_title":"and Hirth, A","cited_arxiv_id":null,"evidence_quote":"defines sufficient reasons, the deterministic notion that the paper extends probabilistically."}],"review_version":1}