{"id":"b93e6675-8149-4c5f-8b3e-70c3ef0121db","arxiv_id":"2507.07857","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"Beam-search algorithms approximate Halpern-Pearl actual causes in discrete causal models via a user-supplied oracle, with adjustable precision and polynomial expected runtime.","lead":"This paper presents approximate search algorithms that find actual causes (counterfactual explanations) in causal models, including systems that are non-boolean, black-box, or stochastic. The methods trade more computation time for more precise and exhaustive cause lists, and the code is provided.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Beam pruning can report non-minimal causes even with a perfect oracle, so the central 'adjustable precision' claim is unsupported without a bound linking beam size to error.","rationale":"The reader's verdict is CONDITIONAL, and my analysis supports keeping that verdict. The reader identifies the oracle assumption as the weakest point; I agree that it is practically limiting, but I find a more formal vulnerability: even with a perfect oracle, beam pruning can violate AC3 by reporting a superset of an unevaluated φ=0 subset. This directly threatens the 'identifies HP causes with adjustable precision' claim and is not an artifact of unobservable counterfactuals. The paper does acknowledge that the algorithms are approximate and demonstrates empirically that larger beam sizes improve F1 on SMK variants, but it provides no correctness or approximation theorem. My concern sharpens the reader's note about 'absence of formal guarantees connecting beam size to precision or exhaustiveness' into a concrete failure mode. Since the paper's contribution is explicitly approximate and the experiments show a tradeoff, this does not warrant rejection; it does warrant the conditional stance and, ideally, a systematic check on small exact-reference instances. The proposed test would settle whether the false-positive mechanism actually occurs and whether the advertised precision adjustment is reliable outside the tested SMK family.","tokens_in":26750,"tokens_out":8567,"duration_ms":113930,"concrete_test":"Construct 50 random Boolean SCMs with 6-8 variables and known exogenous contexts, compute the exact HP cause set by exhaustive enumeration of all interventions, then run Algorithm 1 with beam sizes b=1,2,3 and a deliberately misleading heuristic (e.g., reward nodes that avoid the variables of a known true cause). Instrument the search to record every evaluated intervention. Check two things: (1) whether any reported cause is a strict superset of an evaluated or unevaluated intervention e' with e'_C ⊂ e_C and φ(e')=0; (2) whether precision/recall improve monotonically as b increases. Finding a single reported superset of a φ=0 subset that was never visited demonstrates that the algorithm can output non-HP causes even with a perfect oracle, separating this failure mode from oracle dependence.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's central claim is that Algorithm 1 identifies HP causes with adjustable precision. This requires that a reported cause e_C with φ(e)=0 is actually minimal in the sense of AC3. Section 4.3.1 asserts that elements with φ(e)=0 'either have a minimal e_C and are causes, or do not have a minimal e_C and are discarded.' That dichotomy is only valid if every proper subset of e_C has been evaluated. Beam search does not guarantee this: at each depth only the b best nodes are expanded, so a true HP cause C' can be pruned and never evaluated. Later, a superset e with e_C ⊇ C' can be generated from a different beam branch, evaluate to φ(e)=0, and be reported as a cause because filterMinimality only checks against the already identified Cs. The result is a false positive (AC3 violation) and a missed true cause, without any oracle error. No theorem in the paper bounds this error as a function of beam size, heuristic, or depth, and no monotonicity guarantee is given that larger b strictly improves precision or recall. The complexity bound in Section 4.3.4 also treats N_C as a free parameter, so the asserted polynomial runtime is only output-sensitive. Thus even granting the oracle, the identification step itself is an unverified heuristic; the load-bearing gap is not just oracle availability but the absence of any correctness or approximation guarantee for the search.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes three algorithms for identifying Halpern-Pearl (HP) actual causes in structural causal models: a beam-search base algorithm that explores interventions with an oracle for the target predicate, an iterative sub-instance identification (ISI) variant that uses the causal graph, and a LUCB-based stochastic evaluation method. The authors claim polynomial complexity and an adjustable precision-exhaustiveness tradeoff, and present experiments on Boolean, non-Boolean, black-box, and stochastic versions of the 'Steal Master Key' scenario. The paper is clearly written and includes code, but the central approximation guarantee is not established, and the evaluation for the non-Boolean and black-box cases relies on reference sets built from the algorithms' own outputs.","tokens_in":27010,"tokens_out":3647,"duration_ms":45833,"significance":"If the claims held, the work would fill a real gap: practical identification of HP actual causes in non-Boolean, black-box, and stochastic systems, beyond the Boolean logic-formula setting of ILP-based approaches. Strengths include the explicit oracle-based formulation, the concrete algorithmic descriptions, the availability of code, and the use of an exact exhaustive reference set for the base and noisy SCMs. The empirical comparison with ILP is useful. However, the central notion of 'adjustable precision' is not backed by any formal bound relating beam size to precision or recall, and the experiments for non-Boolean and black-box systems use circular reference sets. The polynomial complexity claim is output-sensitive and not a worst-case guarantee. These gaps are load-bearing for the paper's main contributions, but they are fixable within the manuscript's scope by either adding guarantees, weakening the claims, or providing independent ground truth for small instances.","major_comments":[{"comment":"The central claim that Algorithm 1 identifies HP causes with adjustable precision is not supported. In Section 4.3.2, filterMinimality only discards an element if a subset of its cause set has already been identified as a cause. Because beam search prunes nodes at each depth, a true HP cause can be pruned before being evaluated, and a superset of it can later be generated from another branch, evaluate to φ(e)=0, and be reported as a cause. This yields both false positives (AC3 violations) and false negatives even with a perfect oracle. No theorem or bound is given that relates precision or recall to the beam size b, the heuristic ψ, or the search depth. The experiments in Annex H quantify 'Overshoot' (non-minimal causes) and show it does not clearly decrease with beam size, confirming that the issue is real. Without such a bound, the phrase 'adjustable precision' is not justified.","section":"4.3.1-4.3.2, Algorithm 1"},{"comment":"The reference sets for the non-Boolean and black-box SCMs are constructed by running the algorithms themselves: the text states that for these models the reference set combines all identified causes across beam sizes and then filters non-minimal ones, and that precision and recall are 'an upper bound instead of being exact.' Annex H further notes that a recall value of 1 in the non-Boolean SCM is an artifact of this computation method. This circularity means the experimental results cannot support the abstract's claim that the algorithms identify causes for non-Boolean and black-box systems. The exact reference set used for the base and noisy SCMs (via unlimited beam) is a genuine benchmark and should be emphasized, but the broader claim needs either an independent ground truth for small instances or a clear statement that the non-Boolean and black-box results are illustrative only.","section":"5.6.2"},{"comment":"The claimed polynomial complexity is output-sensitive and not a worst-case guarantee. The stated bound O(|V|^2 × |D_max| × b × N_C × |C_max|) depends on N_C, the number of identified causes, which can be exponential in |V|. Section 4.3.4 acknowledges that 'N_C depends on the parameter of interest in an unclear way' but still concludes expect polynomial complexity. Annex C's empirical regressions are specific to the SMK scenario and show several regimes with low R² values (e.g., 0.099, 0.121, 0.283 in Fig. C.2), so they do not substantiate a general polynomial bound. The complexity claim should be restated as output-sensitive, or a bound on N_C should be provided under stated assumptions.","section":"4.3.4 and Annex C"},{"comment":"The LUCB algorithm is presented as a way to 'control the reliability' of stochastic cause identification, but no correctness or high-probability guarantee is proved. The stop conditions (1)-(3) are expressed in terms of sample averages and confidence bounds, yet there is no theorem showing that when the conditions are met, the true Bernoulli parameters satisfy the corresponding inequalities with the stated tolerance and confidence. The user-specified maximum number of samples in Algorithm 4 can terminate the procedure before the conditions are met, and the experimental results in Section 6.4 show LUCB sometimes performing worse than naive sampling. Without an analysis, the stochastic extension does not provide a formal reliability guarantee.","section":"4.5 and Annex F"}],"minor_comments":[{"comment":"The name 'Halpren and Hitchcock' should be 'Halpern and Hitchcock'.","section":"2.3"},{"comment":"Equation (4) defines a distribution for X but does not explain the temporal dependence: the text says the value is flipped 'each time it is set,' which suggests a process over time, but the equation is given as a static conditional distribution. Please clarify the relationship between the flipping process and the equation.","section":"5.4"},{"comment":"The functions updateUB and updateLB are referenced in Algorithms 5-7 but never defined; the confidence-bound formulas should be given explicitly so the reader can see how the bounds are computed and how they depend on the step t.","section":"Annex F, Algorithm 4"},{"comment":"The label 'Base SMC' should read 'Base SCM'.","section":"6.1"},{"comment":"The heuristic name 'okham' should be 'Occam' for consistency with the text.","section":"Figure H.7"}],"recommendation":"major_revision","confidential_remarks":"The paper's main contribution is framed as 'the first algorithm that can perform actual cause identification in non-boolean, black box, and stochastic systems.' The scope is broad, but the missing approximation guarantee and the circular evaluation for two of the four system categories make the current manuscript unsuitable for acceptance. I would encourage the editor to invite a revision that either provides formal bounds for the beam-search approximation, or substantially weakens the claims to describe a heuristic method with empirical support on exact benchmarks. The base/noisy exact-reference experiments are a solid starting point for such a revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: this is a useful engineering paper, not a theoretical one. It delivers working approximate algorithms for HP actual causes in settings no one else handles — non-boolean, black-box, and stochastic systems — backed by code and experiments. The stress-test's core concern is valid: beam search can report non-minimal causes even with a perfect oracle, because pruned subsets are never evaluated. The paper does not prove a bound on this error, so the 'adjustable precision' claim is empirical, not formal.\n\nWhat's genuinely new: the beam search over interventions, the ISI decomposition for DAG-structured systems, and the LUCB wrapper for stochastic oracles. The experimental setup is honest — they benchmark the Boolean base case against an exhaustive reference, compare to ILP, and explicitly flag that their black-box and non-boolean reference sets are built from the algorithms' own outputs, so precision/recall there are upper bounds. The code is public, which counts as real evidence.\n\nWhere it's soft: the minimality filter only checks against causes already found, and pruning can remove true causes before they are ever seen. The paper's own Annex H reports 'overshoot' — supersets of expected causes being reported — which is exactly the failure mode your stress-test identifies. No theorem bounds overshoot as a function of beam size, heuristic, or depth. Given the abstract's 'adjustable precision' promise, the lack of any formal handle on precision is the main gap. Also, the oracle is load-bearing and hard to satisfy for real counterfactual worlds; the authors acknowledge this in Section 7.3, so it's a stated limitation, not hidden. The complexity claim is output-sensitive, with N_C free, so the 'polynomial' phrasing needs that caveat.\n\nBottom line: a solid, honest empirical contribution with shipped code. It deserves a serious referee, but the approximation-guarantee language should be dialed back or supplemented with a formal analysis of beam-search error, even for a restricted class of systems. I'd send it to review, and I'd cite it if I were working on approximate actual causation.","headline":"A useful, honest engineering contribution to approximate HP actual causes; the formal precision claim is weaker than advertised, but the empirical scope is new and the code is real.","tokens_in":27544,"tokens_out":2543,"would_cite":true,"duration_ms":28724,"reading_group":"maybe","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 claims that Halpern-Pearl actual causes can be identified by a beam search over counterfactual interventions, using a user-supplied oracle, in polynomial time with adjustable precision.","keywords":["actual causation","Halpern-Pearl causes","beam search","counterfactual reasoning","structural causal models","explainable AI","stochastic systems","approximate algorithms"],"falsifier":"Take a small Boolean SCM whose HP-cause set is known by exhaustive enumeration, run the base algorithm with an exact oracle and a beam wide enough to keep every candidate at every depth, and compare the output; if the output differs from the enumeration, the claimed intervention-space encoding or the minimality filter is wrong.","tokens_in":26512,"feed_emoji":"🔍","tokens_out":11549,"duration_ms":111211,"temperature":0.7,"pith_summary":"This paper tackles the problem of identifying actual causes—facts that, if they had not occurred, would have prevented a given outcome—as opposed to general causal relationships. Its target is the Halpern-Pearl (HP) definition of actual cause, which has been computationally hard to use in practice. The authors propose a beam search over the space of counterfactual interventions that reports minimal causes, using a user-supplied answer function (oracle) to decide whether the outcome would still hold under each intervention. They claim the search runs in expected polynomial time in the number of variables, can be tuned by a beam-size parameter to trade runtime against precision and exhaustiveness, and works for non-Boolean, black-box, and stochastic systems. The paper demonstrates the approach on a Boolean scenario from the literature and on non-Boolean, black-box, and noisy variants of it.","feed_headline":"Beam search finds actual causes in polynomial time","feed_subtitle":"A beam-size knob trades runtime for precision on black-box, non-Boolean, and stochastic systems.","key_machinery":"The central object is the space of interventions $E$: each element is a set of variable-value pairs, split into the counterfactual pairs $e_C$ and the actual-value contingency pairs $e_W$. An HP cause $C$ with contingency set $W$ is exactly the counterfactual part of some intervention $e$ that cancels the target predicate ($\\phi(e)=0$) and is minimal under inclusion. The search itself is a beam search: at each depth it keeps only the $b$ most promising partial interventions according to a heuristic $\\psi$, uses the oracle $\\phi$ to decide whether the target still holds, and discards candidates that are supersets of causes already found. The ISI variant exploits the causal graph by replacing variables in a found cause with their parents and searching smaller sub-instances, and the LUCB variant replaces the deterministic oracle with confidence-bounded sampling when evaluations are stochastic.","core_discovery":"The paper's central claim is that every HP cause of a target fact can be represented as an intervention $e$ in the space of variable-value assignments, where the variables set to counterfactual values form the cause $e_C$ and the variables kept at their actual values form the contingency set $e_W$. Finding the HP causes therefore reduces to finding interventions for which the target no longer holds ($\\phi(e)=0$) and whose counterfactual part is minimal under inclusion. The base algorithm performs a beam search guided by a heuristic, evaluates candidates through the oracle $\\phi$, and prunes any candidate that is a superset of an already found cause; the ISI algorithm repeats this search on sub-instances built from the causal graph; and the LUCB algorithm estimates $\\phi(e)$ by confidence-bounded sampling when the system is stochastic. The authors claim this yields a polynomial-time approximation of the full HP-cause set, with complexity $O(|V|^2 \\times |D_{\\max}| \\times b \\times N_C \\times |C_{\\max}|)$, and that the beam size $b$ is an adjustable precision-exhaustiveness-runtime tradeoff.","pith_inferences":["If the oracle is a learned counterfactual model, its errors propagate directly into the reported causes; a natural next experiment is measuring how oracle noise degrades precision and recall.","The intervention-space encoding connects minimal HP causes to $L_0$-distance counterfactual explanations, suggesting the same beam search could serve as an explanation engine for black-box classifiers.","The confidence-bounds machinery in LUCB points toward a formal anytime guarantee: as the sample budget grows, the estimated $\\bar\\phi(e)$ converges to $\\phi^*(e)$, so a PAC-style statement of the search's precision is a testable extension.","Because the reference sets for the non-Boolean and black-box experiments are assembled from the algorithms' own outputs, an independent exact enumeration for those settings would be a natural follow-up."],"forward_implications":["Actual-cause identification no longer requires explicit structural equations: any system that can answer counterfactual queries, such as a simulator or a hand-built expert model, can be searched directly.","Non-Boolean discrete domains are handled natively, so causes can be reported as variable-value facts rather than only as boolean on/off events.","For stochastic systems, repeated sampling and confidence bounds turn the search into approximate identification with user-set tolerances and sample budgets.","The beam-size parameter is a practical control: larger beams increase precision and exhaustiveness at roughly linear runtime cost.","When the causal graph is known, the ISI algorithm generally improves both accuracy and runtime by decomposing the search into smaller sub-instances."],"supporting_citations":[{"why":"Supplies the version of the HP definition used here, including the contingency set W the search must recover.","marker":"[12]"},{"why":"Introduces the Halpern-Pearl structural-model account of actual causation that the target definition builds on.","marker":"[14]"},{"why":"Provides the ILP-based cause-identification baseline and the 'Steal Master Key' scenario used as the experimental base.","marker":"[21]"},{"why":"Supplies the beam search procedure that the base algorithm adapts to navigate the intervention space.","marker":"[27]"},{"why":"Supplies the confidence-bounds bandit method that the LUCB algorithm adapts for stochastic oracle evaluation.","marker":"[25]"},{"why":"Establishes the NP-completeness of structure-based causality, the hardness result the approximation is designed to bypass.","marker":"[2]"},{"why":"Provides the structural causal model and intervention formalism on which the oracle and the intervention encoding rest.","marker":"[32]"}],"fun_headline_variants":["Beam search finds actual causes with adjustable precision","Polynomial-time causal search with a precision dial","Actual causes in polynomial time via beam search","Causal explanation: beam search that trades speed for precision","Adjustable-precision beam search locates actual causes"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"Correctness depends entirely on the user-supplied answer function: it must truthfully report whether the target outcome would still happen under every conceivable intervention, including counterfactual worlds that may be unrealistic or unobservable.","fun_headline_variants_meta":{"raw":{"variants":["Beam search finds actual causes with adjustable precision","Polynomial-time causal search with a precision dial","Actual causes in polynomial time via beam search","Causal explanation: beam search that trades speed for precision","Adjustable-precision beam search locates actual causes"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000165,"raw_usage":{"total_tokens":1256,"prompt_tokens":960,"completion_tokens":296,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":576,"completion_tokens_details":{"reasoning_tokens":223}},"tokens_in":576,"tokens_out":296,"duration_ms":3935,"temperature":1.0,"reasoning_tokens":223,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T18:30:20.430190+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a small Boolean SCM whose HP-cause set is known by exhaustive enumeration, run the base algorithm with an exact oracle and a beam wide enough to keep every candidate at every depth, and compare the output; if the output differs from the enumeration, the claimed intervention-space encoding or the minimality filter is wrong.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the version of the HP definition used here, including the contingency set W the search must recover."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduces the Halpern-Pearl structural-model account of actual causation that the target definition builds on."},{"cited_title":"Ibrahim and A","cited_arxiv_id":null,"evidence_quote":"Provides the ILP-based cause-identification baseline and the 'Steal Master Key' scenario used as the experimental base."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the beam search procedure that the base algorithm adapts to navigate the intervention space."},{"cited_title":"Kaufmann and S","cited_arxiv_id":null,"evidence_quote":"Supplies the confidence-bounds bandit method that the LUCB algorithm adapts for stochastic oracle evaluation."},{"cited_title":"Aleksandrowicz, H","cited_arxiv_id":null,"evidence_quote":"Establishes the NP-completeness of structure-based causality, the hardness result the approximation is designed to bypass."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the structural causal model and intervention formalism on which the oracle and the intervention encoding rest."}],"review_version":1}