{"id":"fd8e9c2c-e55d-4833-8a9e-c5bd72a18363","arxiv_id":"2505.09640","paper_version":1,"verdict":"REJECT","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":3,"one_line_summary":"A feature is 'useful' if flipping its value can change a model's output; the paper proves this matches the logical notions of relevant and necessary features and analyzes the cost of computing them.","lead":"This paper studies logic-based feature importance, gives algorithms and complexity results for relevant and necessary features, and introduces 'usefulness' as a global importance measure. A generalist might read it to learn that a simple flip-test can decide whether a feature is necessary, without Shapley computations.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Proposition 24's non-necessity count is self-defeating: CT(A)+CT(¬A) is the full entity space, so the usefulness score and Section 5 experiments rest on an invalid formula.","rationale":"The reader's overall rejection is justified, and the reader's rationale correctly lists Proposition 24 and Algorithm 1/Proposition 21 among the errors. However, the reader's stated weakest assumption is the numerical discretization bridge in Section 4.2, whereas the most load-bearing flaw is the misuse of Theorem 18 in the usefulness scoring formula. Proposition 24 is not merely a missing proof or an overclaim: its two terms are complements, so the formula always outputs the entire entity space and the resulting usefulness score is identically zero for every feature in every model. This directly invalidates Corollary 25 and the experimental evidence in Section 5. Proposition 21 shows the same inversion in the FBDD case, declaring a feature necessary exactly when its two child evaluations agree, which by Theorem 18 is the condition for non-necessity. The discretization concern is real: the extension to numerical features and the abstract's neural-network claim rely on an unproved comparison-based reduction, and a general real-valued neural network is not comparison-based on raw features. But the decisive issue is internal inconsistency: the paper's own Theorem 18 contradicts the algorithms and the counting formula presented as its consequences. Credit should be given for the correct conceptual core, Lemma 10, Theorem 18, and Theorem 22, and the errors appear fixable in principle, but as written the advertised algorithms and experiments are not a reliable basis for the claims.","tokens_in":21064,"tokens_out":8961,"duration_ms":91377,"concrete_test":"Run the stated formula from Proposition 24 on the single-feature binary identity model M(x)=x over ent(X)={0,1}. Direct enumeration, using Theorem 18, gives zero entities for which x is not necessary: for both e=0 and e=1, flipping x changes the prediction. The paper's formula gives CT(M_{x=0}∧M_{x=1}) + CT(¬(M_{x=0}∧M_{x=1})) = CT(0)+CT(1) = 0+2 = 2. Replacing the second term with CT(∧_{b} ¬M_{x=b}) returns 0. Re-run the Section 5 experiments with the corrected formula; if any displayed usefulness score or ranking changes, the published experiments do not measure the stated quantity.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 18 is correct and is the conceptual core: x is necessary for M(e) iff some b changes the prediction, because X\\{x} is a reason exactly when all x-variants agree with e. Corollary 19 is valid for finite domains. The paper's trouble begins when it converts this characterization into counting and algorithmic claims. In Proposition 24, the paper counts entities for which x is not necessary as CT(∧_{b∈Dx} M_{x=b}) + CT(¬∧_{b∈Dx} M_{x=b}). The first term counts entities where all x-variants, including e itself, are classified 1. The second term is the complement of the first, so the sum is always the total number of entities, independent of M and x. The correct second term is CT(∧_{b∈Dx} ¬M_{x=b}), i.e. entities where all x-variants are classified 0. Because Corollary 25 and the Section 5 usefulness scores use Proposition 24, the reported scores are not the number of entities for which x is necessary. A related sign error appears in Proposition 21: the FBDD criterion states that x is necessary iff D_left(v)=D_right(v)=D(e), but Theorem 18 implies x is necessary precisely when the two child outputs differ. The paper's abstract and algorithmic claims therefore rest on an internally inconsistent application of its own main characterization.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies logic-based explanations for classification models, centered on the notions of relevant, necessary, and useful features. It proves a characterization of necessary features (Theorem 18) and of the new global notion of usefulness (Theorem 22), gives algorithms for decision trees and FBDDs, proves several NP-completeness and #P-completeness results, and reports experiments comparing a usefulness-based ranking with SHAP and with informal ground truth from Kaggle. The paper also claims, in the abstract, that necessity can be detected efficiently in complex models including neural networks.","tokens_in":21295,"tokens_out":8250,"duration_ms":87455,"significance":"The conceptual core of the paper is valuable: Theorem 18 gives a clean, correct characterization of necessity by a small number of model evaluations, and Theorem 22 correctly ties the global notion of usefulness to the local notions of relevancy and necessity. If the algorithmic and counting claims were correct, the paper would offer a practical scoring method for decision trees. However, several load-bearing results are wrong as stated: Proposition 24's counting formula is false, Proposition 21's FBDD criterion is inverted, and Algorithm 1 contains a recursion bug. The numerical-feature and neural-network claims are also unsupported. These issues must be fixed before the results can be relied upon.","major_comments":[{"comment":"The formula for the number of entities for which x is not necessary is incorrect. The paper states this number as CT(∧_{b∈Dx} M_{x=b}) + CT(¬∧_{b∈Dx} M_{x=b}). The second term is the complement of the first, so the sum is always |ent(X)|, independent of M and x. The correct second term is CT(∧_{b∈Dx} ¬M_{x=b}), i.e. the entities all of whose x-variants are classified 0. This is consistent with the k-class generalization given later in the same section, which uses the correct form. As a counterexample, for the one-feature identity model M(e)=e(x), x is necessary for every entity, so the not-necessary count should be 0, while the printed formula gives CT(x)+CT(¬x)=|ent(X)|. Corollary 25 and the usefulness score in Section 5 inherit this error, so the printed score definition is invalid.","section":"§4.3, Proposition 24"},{"comment":"The criterion for necessity in FBDDs is stated backwards. For the unique node v on the path P with feat(v)=x, D(e^{x=0}) = D_left(v)(e) and D(e^{x=1}) = D_right(v)(e). By Theorem 18, x is necessary precisely when D(e^{x=0}) ≠ D(e^{x=1}), i.e. when D_left(v)(e) ≠ D_right(v)(e). The printed condition D_left(v)=D_right(v)=D(e) identifies the opposite situation, where the feature has no effect on the prediction, and is therefore not a necessary feature unless the model is degenerate. The claimed linear-time FBDD algorithm is not correct as stated.","section":"§4.2, Proposition 21"},{"comment":"Algorithm 1 in Figure 3 contains a recursion bug: in line 13, both recursive calls use w1, the left child, so the right child is never explored for values above value(v). The second call should be on w2. The same function, in the categorical case (Algorithm 2 in Figure 4), tests 'value(v) ∈ (a, b)' on line 12 even though v is a categorical node; the condition should involve values(v), and the partition of Z should use values(v) and Dx \\ values(v). As printed, these algorithms do not justify the O(|X|+|T|) claim.","section":"§4.2, Proposition 20 and Algorithm 1"},{"comment":"The abstract's claim that necessity can be detected efficiently in 'complex models such as neural networks' is not supported by the paper. Corollary 19 applies only when each feature domain is small. The subsequent discussion covers 'comparison-based models' and relies on discretization 'using well-known ideas [14]' without a theorem, proof, or complexity bound, and neural networks are not comparison-based in the sense used there. The authors should either state a precise model class for which the discretization argument is proved or remove the neural-network claim from the abstract.","section":"Abstract and §4.2 (numerical features)"}],"minor_comments":[{"comment":"The proof of hardness cites 'Lemma 13' for the NP-hardness of deciding whether a minimal hitting set contains a given set of nodes, but Lemma 13 is an algorithmic result; the hardness result is Proposition 14. Please correct the reference.","section":"§4.1, Proposition 17"},{"comment":"The sentence 'the number of classes that have to be considered grows linearly with the number of nodes, and thus we conclude tractability' is stated informally. A formal statement of the discretization, including how to handle repeated thresholds and boundary cases, would strengthen the paper.","section":"§4.2, text after Corollary 19"},{"comment":"The notation 'B\\{x}' is used in the proof of Lemma 13, but the node under consideration is v, not x. This is a typo and should be fixed for readability.","section":"§3, Lemma 13"},{"comment":"The ground-truth rankings are taken from Kaggle posts and selected papers and are treated as authoritative. Since these are informal and may disagree with each other, the experiments would be more convincing if the comparison were formulated as a hypothesis test or at least accompanied by a sensitivity analysis over the choice of ground truth.","section":"§5, Ground truth"},{"comment":"It is stated without proof that 'there are no numerical nodes with labels of the form (x, Mx)'. This is a WLOG assumption that should be justified, because Mx can be finite and the comparison x ≤ Mx would then be tautological, which may affect the size of the tree after removing such nodes.","section":"§2, Definition 5"}],"recommendation":"major_revision","confidential_remarks":"I agree with the stress-test assessment that Proposition 24 is wrong as written, but the intended correction is local and the k-class generalization confirms the correct form. Proposition 21 and Algorithm 1 are also locally fixable. The authors should correct these points and verify whether the experiments in Section 5 used the corrected score; if they followed the printed formula, the reported numbers are not the usefulness scores and must be recomputed. The paper's main characterization theorems are sound and the notion of usefulness is interesting, so I see a viable path to publication after revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nRead this if you want a clean conceptual characterization wrapped in a manuscript that is not yet trustworthy. Theorem 18 is correct and actually useful: a feature is necessary exactly when flipping it can change the prediction. That gives Corollary 19 (necessity is easy for bounded-domain models) and anchors a sensible global \"usefulness\" notion, connected to relevancy and necessity in Theorem 22. The counting hardness results in Propositions 16 and 17 also look plausible, and the linear-time all-necessary-features algorithm for decision trees (Proposition 20) is a reasonable claim, though I did not fully verify its proof.\n\nBut there are two load-bearing errors. Proposition 24 counts the entities where a feature is not necessary as CT(A) + CT(¬A), with A = ∧_{b∈Dx} M_{x=b}. That sum is always the total number of entities, independent of M and x. The correct second term is CT(∧_{b∈Dx} ¬M_{x=b}). Corollary 25 and the Section 5 experiments use this formula, so the reported usefulness scores are not measuring what the paper says they measure.\n\nSecond, Proposition 21 says that in an FBDD a feature is necessary iff the two child outputs are equal to D(e). Theorem 18 says the opposite: necessity means flipping the feature changes the prediction, so the two children must differ. The criterion is inverted. Algorithm 1 also recurses on the same child twice for numerical splits, which further undermines the linear-time claims.\n\nThe abstract overreaches as well: the claim that necessity is tractable for neural networks rests on a discretization argument for \"comparison-based models.\" Real neural networks are not comparison-based in the relevant sense. That part should be withdrawn or sharply qualified.\n\nThe core idea is real, though. The characterization theorems are worth refereeing carefully, and the usefulness notion is a natural bridge between local and global feature importance. With the counting formula, the FBDD criterion, and the algorithm fixed, this could become a decent paper. As written, the algorithms and experiments cannot be trusted.\n\nRecommendation: send it to peer review rather than desk reject — the errors are identifiable and fixable — but tell the authors clearly that Proposition 24, Proposition 21, and Algorithm 1 must be corrected and the experiments re-run before the paper is publishable.","headline":"Theorem 18 is a genuinely neat characterization, but the paper undercuts itself with a wrong counting formula and an inverted FBDD criterion.","tokens_in":21852,"tokens_out":3920,"would_cite":false,"duration_ms":37834,"reading_group":"maybe","serious_thinker":"no","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"A feature is necessary for a prediction exactly when some counterfactual edit flips the model's output.","keywords":["feature relevancy","feature necessity","feature usefulness","sufficient reasons","hitting sets","explainable AI","decision trees","FBDD"],"falsifier":"Take a real-valued classifier that is not comparison-based, such as a small network with a periodic activation, and pick an entity near a decision boundary so that a tiny change in one feature flips the class but no threshold captured by the node set does; if the discretization route declares the feature non-necessary while the direct flip test $M(e)\\neq M(e^{x=b})$ succeeds for some real $b$, the numerical extension is not universal.","tokens_in":20814,"feed_emoji":"🎯","tokens_out":11293,"duration_ms":103212,"temperature":0.7,"pith_summary":"This paper studies logic-based feature importance: whether a feature is relevant to a given prediction (it appears in at least one minimal set of features that determines the prediction) or necessary (it appears in every such set). Its central result is a characterization: a feature is necessary exactly when changing that feature alone to some value changes the model's output, written $M(e)\\neq M(e^{x=b})$. That condition is a small set of model evaluations, so necessity becomes easy to certify for any efficiently evaluable model with bounded feature domains; the paper also gives linear-time procedures for decision trees and read-once binary decision diagrams (FBDDs). It then introduces a global notion, usefulness, and proves a feature is useful exactly when it is necessary, equivalently relevant, for some entity. Experiments on three public datasets indicate that the resulting feature-ranking score agrees with expected importance.","feed_headline":"A feature is necessary only when flipping it changes the prediction","feed_subtitle":"Necessity detection becomes a handful of model evaluations, and a new global usefulness score ties into it.","key_machinery":"The load-bearing mechanism is the sufficient-reason/hitting-set correspondence together with the new flip-test characterization. A sufficient reason is a minimal set of features that already determines the prediction; by the paper's Lemma 10, sufficient reasons are exactly the minimal hitting sets of the hypergraph formed by the clauses of the model restricted to the entity. That correspondence carries the relevancy algorithms and the hardness results. The new step is Theorem 18: $x$ is necessary exactly when $X\\setminus\\{x\\}$ is not a reason, which turns a set-membership question into one-feature counterfactual checks. For the linear-time bounds, the algorithm decomposes the tree path into intervals of values per feature and evaluates a tautology-checking recursion on each interval, while for FBDDs it uses the read-once property to inspect a single node per feature.","core_discovery":"On its own terms, the central discovery is that necessity is a flip test. For any model $M$, entity $e$, and feature $x$, the feature is necessary for the prediction $M(e)$ if and only if there is some value $b$ with $M(e)\\neq M(e^{x=b})$. The proof is minimality: if $X\\setminus\\{x\\}$ were a reason for the prediction, then some sufficient reason would avoid $x$; conversely, if flipping $x$ can change the output, every sufficient reason must contain $x$. This reduces necessity to direct model evaluations, $O(\\mathrm{eval}(M)|D_x|)$ for bounded domains, and it underlies the paper's linear-time all-necessary-features algorithms for decision trees and FBDDs. The same characterization drives the new global notion of usefulness: $x$ is useful exactly when it is necessary for some entity, equivalently when it is relevant for some entity, and deciding usefulness is equivalent to deciding model equivalence, giving tractability for decision trees and ordered binary decision diagrams (OBDDs) and coNP-completeness for disjunctive normal form formulas (DNFs).","pith_inferences":["Read narrowly: the abstract's claim that necessity is detectable efficiently in neural networks is supported only through the bounded-domain or comparison-based route; real-valued networks with arbitrary activations are not covered by the discretization argument.","If the flip-test characterization holds broadly, an exact model-agnostic necessity oracle is available by querying the original black box directly, without compiling it to a circuit or building a surrogate model, which could make local explanations cheaper than Shapley-value approximations in practice.","Counting entities where a single-feature flip changes the prediction yields a global importance ranking defined entirely from the classifier's behavior; this could serve as a sanity check for other importance scores, since it does not rely on cooperative-game axioms.","A testable next step is to compare usefulness rankings against leave-one-feature-out accuracy on datasets not used in the paper, which would separate ranking quality from agreement with reported importance."],"forward_implications":["For any model that can be evaluated in polynomial time and whose features have bounded domains, checking whether a feature is necessary costs $O(\\mathrm{eval}(M)|D_x|)$, so necessity queries stop being a search problem.","All necessary features of a decision tree with categorical and numerical features can be listed in $O(|X|+|T|)$ time, and the same linear bound holds for FBDDs and OBDDs.","A feature that is useful in the new global sense is one whose value matters for some prediction, and deciding usefulness is polynomial-time equivalent to model equivalence, yielding tractability for decision trees and OBDDs and coNP-completeness for DNFs.","The usefulness score, computed by counting entities for which a feature is necessary, is computable in quadratic time for boolean decision trees with two model-counting calls, and its ranking agrees with established importance on three public datasets."],"supporting_citations":[{"why":"introduced relevant and necessary features and the original decision-tree algorithms this work extends","marker":"[3]"},{"why":"established tractability of necessity when reason checking is cheap and hardness of relevancy for FBDDs, both used as baselines","marker":"[24]"},{"why":"supplies the comparison-based discretization idea and the decision-tree model with categorical and numerical features","marker":"[14]"},{"why":"provides the minimal-hitting-set machinery behind Lemma 10","marker":"[30]"},{"why":"provides the hitting-set dualization connection between reasons and hypergraphs","marker":"[41]"},{"why":"defines sufficient reasons and abductive explanation, the conceptual basis for all three notions","marker":"[34]"},{"why":"extended relevancy and necessity to categorical graph-based classifiers, the baseline generalized here","marker":"[27]"},{"why":"supplies the knowledge-compilation closure and model-counting facts used in the usefulness-score algorithm","marker":"[15]"}],"fun_headline_variants":["Necessity is a flip test, now fast for neural nets","Flip a feature, change the prediction: that's necessity","Global feature usefulness: just necessity for some input","Necessity detection: one flip per feature, even in deep nets","Relevancy, necessity, usefulness: all decided by flips"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The numerical-feature results assume that any comparison-based model can be discretized into finitely many intervals without changing its predictions (the paper's Section 4.2, citing [14] without proof or bounds); if that step fails, the results for continuous features and the abstract's neural-network claim lose their foundation.","fun_headline_variants_meta":{"raw":{"variants":["Necessity is a flip test, now fast for neural nets","Flip a feature, change the prediction: that's necessity","Global feature usefulness: just necessity for some input","Necessity detection: one flip per feature, even in deep nets","Relevancy, necessity, usefulness: all decided by flips"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001221,"raw_usage":{"total_tokens":5030,"prompt_tokens":964,"completion_tokens":4066,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":580,"completion_tokens_details":{"reasoning_tokens":3980}},"tokens_in":580,"tokens_out":4066,"duration_ms":28152,"temperature":1.0,"reasoning_tokens":3980,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T23:42:03.175191+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a real-valued classifier that is not comparison-based, such as a small network with a periodic activation, and pick an entity near a decision boundary so that a tiny change in one feature flips the class but no threshold captured by the node set does; if the discretization route declares the feature non-necessary while the direct flip test $M(e)\\neq M(e^{x=b})$ succeeds for some real $b$, the numerical extension is not universal.","supporting_citations":[{"cited_title":"Feature necessity & relevancy in ML classifier explanations","cited_arxiv_id":null,"evidence_quote":"established tractability of necessity when reason checking is cheap and hardness of relevancy for FBDDs, both used as baselines"},{"cited_title":"On the computation of necessary and sufficient explanations","cited_arxiv_id":null,"evidence_quote":"supplies the comparison-based discretization idea and the decision-tree model with categorical and numerical features"},{"cited_title":"Algorithms for computing minimal unsatisfiable subsets of constraints","cited_arxiv_id":null,"evidence_quote":"provides the minimal-hitting-set machinery behind Lemma 10"},{"cited_title":"A theory of diagnosis from first principles","cited_arxiv_id":null,"evidence_quote":"provides the hitting-set dualization connection between reasons and hypergraphs"},{"cited_title":"Logic-based explainability in machine learning","cited_arxiv_id":null,"evidence_quote":"defines sufficient reasons and abductive explanation, the conceptual basis for all three notions"},{"cited_title":"On Efficiently Explaining Graph-Based Classifiers","cited_arxiv_id":"2106.01350","evidence_quote":"extended relevancy and necessity to categorical graph-based classifiers, the baseline generalized here"},{"cited_title":"A knowledge compilation map","cited_arxiv_id":null,"evidence_quote":"supplies the knowledge-compilation closure and model-counting facts used in the usefulness-score algorithm"}],"review_version":1}