{"id":"ff911934-013f-4a74-97c6-9880f61a20d7","arxiv_id":"2509.03548","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The paper gives new algorithm simplifications and a column generation scheme for computing tight causal effect bounds in quasi-Markovian structural causal models.","lead":"This paper presents faster algorithms for computing the range of possible causal effects when hidden factors prevent an exact answer. It introduces simplified objectives and column generation to make existing linear programming methods for quasi-Markovian causal models scale to larger problems.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Case C4's d-separating set Wt is neither constructed nor guaranteed to exclude X, yet Theorem 1's correctness and the invocation of do-calculus Rule 2 depend on it.","rationale":"The reader identified Case C4 and Lemma 1 as the weakest assumption, and I agree that this is the load-bearing point of the paper. However, I would sharpen the concern: it is not merely that Lemma 1 is sketchy and no search for Wt is given; the formal statement of C4 allows X to enter St, which makes the d-separation condition ill-posed and the Rule 2 step invalid as written. Example 2 is strong evidence that the authors do use such a set, since cPr(z|x) appears without any other separator. This is a correctable gap rather than a demonstrated falsehood: an explicit X-free construction likely exists by taking endogenous ancestors of Y (or of Z ∪ {Y}) and excluding X and Y. Verifying that construction would close the gap. Because the reader's CONDITIONAL verdict already reflects the need for such repair, I do not move the verdict; the concern strengthens the rationale for making acceptance conditional on a complete proof of Lemma 1/C4 and on an explicit procedure for Wt.","tokens_in":16731,"tokens_out":38029,"duration_ms":380507,"concrete_test":"Independently rederive Lemma 1 with the explicit candidate W = (Anc(Z ∪ {Y}) ∩ V) \\ {X, Y}, and verify both required d-separations: (i) X and Y d-separated by W ∪ Z in G_X, and (ii) Y and U d-separated by W ∪ Z ∪ {X} in G. If the derivation succeeds, the lemma should be restated with X-free W and the construction made explicit. Complement this analytic check by a small exhaustive search over all quasi-Markovian DAGs with up to six endogenous nodes and all choices of X, Y, Z satisfying Lemma 1's assumptions, checking whether any valid X-free W exists; if one does not, construct a counterexample and compare the Section 4 bound with a direct evaluation of Equation (7).","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim (Theorem 1 plus the Section 5 column generation scheme) is valid only if Case C4 can always be applied as stated. C4 asks the algorithm to 'find' Wt satisfying two d-separation conditions, but no search procedure is given, and Lemma 1's proof is a brief moral-graph sketch. More concretely, the definition St = (Wt ∪ Yt) \\ {Yt, Ut} does not exclude X from Wt. If X ∈ Wt, then X ∈ St, so the condition 'Yt and X are d-separated by St in GX' is not a standard d-separation statement: the separated node should not be in the separator. In that case the subsequent application of Rule 2 of do-calculus, Pr(yt | yt+1, do(x)) = Pr(yt | x, yt+1), is also not formally justified because Rule 2 requires the conditioning set to be disjoint from the intervened variables. Example 2 appears to rely exactly on such a choice: the output Pr(z,u1|do(x)) = cPr(z|x) Pr(u1|do(x)) is natural only when St includes X. Lemma 1 does not state that X is excluded from W ∪ Z. Thus the proof has a genuine gap, and the algorithm as written is underspecified on the very case that drives the simplification. The gap is probably repairable, since an explicit X-free candidate such as Wt = (Anc(Yt) ∩ V) \\ {X, Yt} may satisfy the two d-separations, but the paper does not supply or prove such a construction.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies bounding of partially identifiable causal queries in quasi-Markovian structural causal models. Section 3 gives a new proof of Shridharan and Iyengar's result that tight bounds can be obtained from a multilinear program whose degree is the number of intervened c-components. Section 4 proposes an algorithm that, given an input distribution over endogenous variables, simplifies the objective function by repeatedly eliminating target variables via four cases (C1-C4); Theorem 1 claims that the resulting linear program, subject to Tian's factorization constraints (Equation (6)), yields tight bounds. Section 5 develops a column-generation scheme for the single-intervention case, representing each exogenous mechanism as a binary bit string and solving the reduced-cost problem with linear integer constraints, and Section 5.3 sketches a single-program alternative. Experiments compare the column-generation approach with a direct LP on a family of models.","tokens_in":17050,"tokens_out":16676,"duration_ms":142457,"significance":"The paper addresses an important problem: avoiding the exponential explosion in the construction of multilinear/linear programs for partially identifiable causal queries. The simplification algorithm is a promising way to exploit known observational probabilities, and the column-generation encoding of mechanisms via bits is elegant and may be practically valuable. The new proof of the Shridharan-Iyengar theorem is concise and helpful. However, because the correctness of the algorithm rests on Lemma 1, whose proof is incomplete and whose statement may be flawed, the central theoretical contribution is not yet established. The experimental comparison is useful but does not isolate the effect of column generation. If the lemma is repaired, the paper would be a solid contribution; in its current form, it requires substantial revision.","major_comments":[{"comment":"The algorithm requires finding Wt such that (i) Yt and X are d-separated by St in G_X and (ii) Yt and Ut are d-separated by St∪{X} in G. For these d-separation statements to be well-formed and for the subsequent use of do-calculus Rule 2, the separator must be disjoint from X. The definition St=(Wt∪Yt)\\setminus{Yt,Ut} does not guarantee X∉Wt, and Lemma 1's statement that W are 'ancestors of Z∪{Y}' does not exclude X either, since X is an ancestor of Y by Assumption (ii). The proof of Lemma 1 is a terse moral-graph argument that does not construct W or prove the two separation conditions simultaneously. Because Theorem 1's Case C4 relies entirely on this lemma, the correctness proof is incomplete. Please state and prove a corrected lemma with X∉W, give an explicit construction (e.g., W=(Anc(Yt)∩V)\\setminus{X,Yt} if that satisfies the separations), and describe how the algorithm obtains Wt.","section":"Section 4, Case C4 and Lemma 1"},{"comment":"The text invokes Rule 2 of do-calculus and justifies it by d-separation 'in the graph obtained by removing edges leaving X'. Rule 2 requires d-separation in the graph with edges entering X removed (G_{\\underline{X}}), not the graph with edges leaving X removed (G_{\\overline{X}}). As written, the exchange Pr(yt|yt+1,do(x))=Pr(yt|x,yt+1) is not justified. Additionally, the proof states that the separator is Yt+1, whereas the condition in C4 and Lemma 1 use St and W∪Z respectively; these sets may differ by the exogenous variable Ut. Please correct the graph direction and clarify which separator is actually used.","section":"Section 4, proof of Theorem 1 for Case C4"},{"comment":"The headline comparison is between column generation with the Section 4 simplified objective (CG) and a direct LP built from Expression (7) (LP). Since the simplifications alone can reduce the size of the objective enormously, the observed speedups do not isolate the value of column generation. To support the abstract's claim that column generation is superior, the authors should either compare CG against a direct LP that also uses the simplified objective on small instances, or explicitly frame the comparison as end-to-end and discuss the decomposition of the gains.","section":"Section 5.2, Table 1"}],"minor_comments":[{"comment":"The notation for the intervention graph and the graph with incoming edges removed is ambiguous; the plain text shows 'GX' for both. Please use G_{\\overline{X}} and G_{\\underline{X}} consistently.","section":"Section 2"},{"comment":"The text says 'Recall that [[fW (x,z,u ) = z]]', but this should be '[[fW (x,z,u ) = w]]' to match the definition of W.","section":"Example 6"},{"comment":"The phrase 'A is now the square matrix with the M columns just built' is incorrect in dimension: A has 2^M rows and M columns. Presumably the basis matrix of the simplex method is meant.","section":"Section 5.3"},{"comment":"The column-generation iteration does not state the stopping criterion (e.g., stop when the minimum reduced cost is non-negative).","section":"Section 5.1"},{"comment":"The phrase 'a representation with polynomial cardinality for exogenous variables' is imprecise; the per-column encoding is polynomial in the graph size, but the auxiliary programs in Section 8 still have exponential size in general. Please clarify the claim.","section":"Abstract and Section 5"}],"recommendation":"major_revision","confidential_remarks":"The manuscript has been accepted at a UAI workshop and appears to be a preliminary version; for a journal, the proof gap in Lemma 1 must be closed. The novelty is adequate and citations to previous work are appropriate. The experimental section would benefit from an ablation separating the simplification from column generation."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear colleague,\n\nBottom line: this is a genuinely useful algorithmic paper on computing causal effect bounds in quasi-Markovian models, but the main simplifier (Section 4, Case C4) has a proof gap that needs to be fixed before I'd trust Theorem 1 as stated. The gap looks repairable, so I'd send it to referees, not desk-reject.\n\nWhat's new: Section 4's algorithm uses the observed distribution to simplify the objective, and Section 5's column generation scheme encodes each exogenous mechanism as bits, solving the pricing problem as a linear integer program. The experiments show large speedups over direct LP. The new proof of the Shridharan–Iyengar reduction is clean and pedagogically nice, though it is a reinterpretation rather than a new result.\n\nThe soft spots, in proportion. The C4 step requires finding Wt such that Yt and X are d-separated by St in G_X, and Yt and Ut are d-separated by St ∪ {X} in G, where St = (Wt ∪ Yt) \\ {Yt, Ut}. Lemma 1 asserts existence with a brief moral-graph sketch, but it never gives a procedure to find Wt, and nothing prevents X from being in Wt. If X ∈ Wt, then X ∈ St, and \"Yt and X are d-separated by St\" is not a standard d-separation statement, because the conditioning set contains one of the separated nodes. The subsequent Rule 2 invocation also conditions on yt+1, which then contains X, making that step formally unjustified. Example 2 appears to rely on exactly such a degenerate choice. This is a genuine gap, not a manufactured quibble. It may be fixable with an explicit X-free construction, such as Wt = (Anc(Yt) ∩ V) \\ {X, Yt}, but the paper does not supply or prove such a construction.\n\nOther issues are softer. The experiments compare only against direct LP, not against reduced LPs from Sachs et al. or Shridharan and Iyengar, so the practical gain over state-of-the-art baselines is not fully established. No code or data are released yet. And the abstract's \"polynomial cardinality\" claim is imprecise: the auxiliary program still has O(2^{M+N}) variables and constraints. The citation pattern is fine; the self-citation to Cozman and Fargoni di Ianni is only for the bonus single-program construction and is not load-bearing.\n\nWho it's for: researchers working on causal effect bounds, credal networks, or automated causal inference. It deserves a serious referee; just don't pass Theorem 1 until C4 is fixed.\n\nRecommendation: accept for peer review, with the expectation of a major revision focused on C4.","headline":"Useful algorithmic advance for causal bounds, but Case C4's d-separating set can include X, leaving a real — likely fixable — gap in Theorem 1.","tokens_in":17621,"tokens_out":9493,"would_cite":true,"duration_ms":84059,"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":"A new algorithm turns partially identifiable causal queries into small linear programs by exploiting observed distributions, with column generation replacing mechanism enumeration.","keywords":["partially identifiable causal queries","quasi-Markovian structural causal models","tight probability bounds","multilinear programming","linear programming","column generation","do-calculus","causal effect bounds"],"falsifier":"Take a quasi-Markovian graph that satisfies Lemma 1's three hypotheses and, using a brute-force enumeration of every canonical exogenous mechanism, compute the true tight bound on $\\Pr(y\\mid do(x))$ by multilinear programming. Then run the paper's simplified linear program after applying the C4 rewrite with a candidate set $W_t$; if any graph yields a different optimum from the brute-force bound, or if exhaustive search over endogenous subsets shows that no $W_t$ satisfies both d-separation conditions, Theorem 1 is refuted.","tokens_in":16551,"feed_emoji":"🧮","tokens_out":8779,"duration_ms":79399,"temperature":0.7,"pith_summary":"The paper studies what can be learned about a causal effect when observational data do not identify it uniquely. In a quasi-Markovian structural causal model—one where every observed variable is confounded by at most one latent variable—it develops a way to compute tight lower and upper bounds on queries such as $\\Pr(y\\mid do(x))$. The central claim is that a new rewriting algorithm, driven by the observed distribution over endogenous variables, can build these bound programs with far fewer terms than the standard multilinear expression, and that in the single-intervention case column generation solves the resulting linear program without enumerating all possible latent mechanisms. If the claims are right, partial identifiability becomes substantially more tractable in practice, and the experiments on models drawn from an AI service-pipeline problem show order-of-magnitude speedups over direct linear programming.","feed_headline":"Causal bounds from small linear programs, no mechanism enumeration","feed_subtitle":"A rule-based decomposition uses observed data to cut the search for partially identifiable causal queries.","key_machinery":"The machinery is the intervened semi-marginal graph plus a bit-block encoding of mechanisms. The semi-marginal graph is obtained from the original causal graph by marginalizing the exogenous variables of non-intervened c-components, adding edges to preserve the induced dependencies, and then applying the usual intervention surgery to $X$. The four rewriting rules C1–C4 operate on this graph: each eliminates a target variable and outputs either an empirical conditional, a mechanism indicator, or a product of both, so the final objective references only the exogenous variable of the intervened c-component. For the column-generation stage, each value $u$ of that exogenous variable is written as a string of bits, one block per mechanism; evaluating every mechanism on every parent configuration pins down one bit, turning both the objective coefficient $\\gamma_u$ and each constraint column $a_u$ into products of bits. Those products are linearized with standard integer constraints, so the search for a minimized reduced cost is itself a linear integer program.","core_discovery":"The central discovery is that Shridharan and Iyengar's reduction—tight causal bounds in quasi-Markovian SCMs require only the exogenous variables attached to intervened c-components—can be made constructive and efficient. Starting from the target $Y$, the algorithm eliminates variables in reverse topological order using four do-calculus rules. In the two 'outside the intervention' cases it replaces a factor by an empirical conditional distribution; in the two descendant-of-$X$ cases it leaves only mechanism indicators for the intervened c-component's exogenous variable. Theorem 1 states that the resulting objective, minimized under Tian's linear constraints, gives tight bounds for $\\Pr(y\\mid do(x))$. The paper further claims that each possible value of that exogenous variable can be encoded as a block of bits so that the objective coefficient and constraint columns are products of bits, which makes the column-generation subproblem a linear integer program; hence a polynomial-cardinality representation of the exogenous variable suffices.","pith_inferences":["If Lemma 1 can be strengthened from an existence claim to a constructive procedure for finding $W_t$, the algorithm becomes fully automatic; the paper gives no method to search for that set, which is the main practical gap.","The bit-block encoding suggests a route to multiple interventions: each intervened c-component contributes its own bit blocks, and the reduced-cost objective would factor across them, though the paper leaves multiple interventions to future work.","The linear constraints are exactly Tian's factorization equations, so the same bounding polytope connects to credal-network inference; that connection may let the bounds be used in robust decision problems where the causal query is one linear objective among many."],"forward_implications":["For a single intervention, tight bounds on $\\Pr(y\\mid do(x))$ can be computed by a master linear program that keeps only a square basis of columns, with each pivot column found by a linear integer program, avoiding the doubly exponential enumeration of exogenous mechanisms.","The symbolic simplification can be exponentially more succinct than the naive expression: the paper's Example 3 shows a family where the standard expression has $|\\mathrm{val}(U_1)|^{2n}$ terms while the rewritten objective is the same small expression for every $n$.","The method covers quasi-Markovian graphs that the Sachs et al. symbolic-bound technique cannot handle, including the low-latency service pipeline model and the parameterized family built from it.","Because the feasible region is a closed polytope, minimizing and maximizing the same linear objective yields tight lower and upper bounds, and linear combinations such as average treatment effects are handled by the same program.","A single linear integer program with copied bits can compute the bound in one shot, offering a simpler non-iterative implementation at the cost of likely longer runtime than column generation."],"supporting_citations":[{"why":"Establishes the key reduction the paper reproves: tight causal bounds in quasi-Markovian SCMs need only exogenous variables of intervened c-components, giving linear programs for a single intervention.","marker":"Shridharan and Iyengar [2023b]"},{"why":"Gives the c-component factorization and the linear constraints (Equation 6) that define the feasible set for the bound programs.","marker":"Tian [2002]"},{"why":"Origin of linear-programming bounds for causal effects, the approach this paper extends to a larger class of quasi-Markovian graphs.","marker":"Balke and Pearl [1994]"},{"why":"Supplies do-calculus Rules 2 and 3 that justify the four rewriting cases in Theorem 1.","marker":"Pearl [2009]"},{"why":"Shows that optimizing over extensions under these constraints gives tight bounds and connects the problem to credal-network inference.","marker":"Zaffalon et al. [2024]"},{"why":"Provides the baseline symbolic-bound method and the example graph used for comparison.","marker":"Sachs et al. [2023]"},{"why":"Provides the revised-simplex and column-generation framework, including reduced costs and the big-M initialization scheme.","marker":"Bertsimas and Tsitsiklis [1997]"},{"why":"Supplies d-separation, moral graphs, and variable elimination used in Lemma 1's proof and the complexity comparison.","marker":"Koller and Friedman [2009]"},{"why":"Justifies canonicalization and the use of categorical exogenous variables whose values encode mechanisms, with cardinality bounds.","marker":"Zhang et al. [2022]"}],"fun_headline_variants":["Column generation makes causal bounds tractable","Tight causal bounds without enumerating mechanisms","Linear programs speed up causal bound search","A polynomial representation for causal bound computation"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is Lemma 1's assertion that in case C4, for every eliminated variable $Y_t$ there is a set of endogenous variables $W_t$ that simultaneously separates $Y_t$ from $X$ (after removing $X$'s outgoing edges) and $Y_t$ from $X$'s exogenous parent (when also conditioning on $X$); the proof is only a brief moral-graph sketch, and no method is offered to find $W_t$, so if the lemma fails or the set cannot be constructed the whole simplification collapses.","fun_headline_variants_meta":{"raw":{"variants":["Column generation makes causal bounds tractable","Tight causal bounds without enumerating mechanisms","Linear programs speed up causal bound search","A polynomial representation for causal bound computation"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000625,"raw_usage":{"total_tokens":2887,"prompt_tokens":934,"completion_tokens":1953,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":550,"completion_tokens_details":{"reasoning_tokens":1901}},"tokens_in":550,"tokens_out":1953,"duration_ms":14767,"temperature":1.0,"reasoning_tokens":1901,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T16:37:20.671327+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a quasi-Markovian graph that satisfies Lemma 1's three hypotheses and, using a brute-force enumeration of every canonical exogenous mechanism, compute the true tight bound on $\\Pr(y\\mid do(x))$ by multilinear programming. Then run the paper's simplified linear program after applying the C4 rewrite with a candidate set $W_t$; if any graph yields a different optimum from the brute-force bound, or if exhaustive search over endogenous subsets shows that no $W_t$ satisfies both d-separation conditions, Theorem 1 is refuted.","supporting_citations":[{"cited_title":"Tsitsiklis","cited_arxiv_id":null,"evidence_quote":"Provides the revised-simplex and column-generation framework, including reduced costs and the big-M initialization scheme."},{"cited_title":"Probabilistic Graphical Models: Principles and Techniques","cited_arxiv_id":null,"evidence_quote":"Supplies d-separation, moral graphs, and variable elimination used in Lemma 1's proof and the complexity comparison."},{"cited_title":"Partial counterfactual identification from observational and experimental data","cited_arxiv_id":null,"evidence_quote":"Justifies canonicalization and the use of categorical exogenous variables whose values encode mechanisms, with cardinality bounds."}],"review_version":2}