Pith. sign in

REVIEW 3 major objections 5 minor 18 references

Multilinear and Linear Programs for Partially Identifiable Queries in Quasi-Markovian Structural Causal Models

T0 review · 3 major / 5 minor · reviewed 2026-08-15 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A new algorithm turns partially identifiable causal queries into small linear programs by exploiting observed distributions, with column generation replacing mechanism enumeration.

desk verdict 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. read the letter →

arxiv 2509.03548 v1 pith:JTBC3PK4 submitted 2025-09-02 cs.AI

João P. Arroyo , João G. Rodrigues , Daniel Lawand , Denis D. Mauá , Junkyu Lee , Radu Marinescu , Alex Gray , Eduardo R. Laurentino
show 1 more author
Fabio G. Cozman
This is my paper · ORCID
classification cs.AI
keywords partiallyidentifiablecausalqueriesquasi-Markovianstructuralmodelstightprobabilityboundsmultilinearprogramminglinearcolumngenerationdo-calculuseffect
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

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.

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 (3)
  1. [Section 4, Case C4 and Lemma 1] 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.
  2. [Section 4, proof of Theorem 1 for Case C4] 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.
  3. [Section 5.2, Table 1] 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.
minor comments (5)
  1. [Section 2] 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.
  2. [Example 6] 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.
  3. [Section 5.3] 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.
  4. [Section 5.1] The column-generation iteration does not state the stopping criterion (e.g., stop when the minimum reduced cost is non-negative).
  5. [Abstract and Section 5] 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.

Circularity Check

0 steps flagged · score 2.0 of 10

No significant circularity; the derivation rests on external results (Tian factorization, Pearl do-calculus, Shridharan-Iyengar), with only a non-load-bearing self-citation and a non-circular proof gap in Case C4.

full rationale

The paper's derivation chain is self-contained against external causal-inference results rather than against its own fitted values. Section 3 re-derives the Shridharan-Iyengar reduction using Tian's factorization (Equations (2)-(7)), and the constraints in Equation (6) are necessary and sufficient consequences of that factorization, not fitted parameters renamed as predictions. Section 4's Cases C1-C4 are justified by probability manipulations and Pearl's do-calculus; for example, Case C4 replaces an interventional conditional by the observed conditional cPr(yt|x, st) precisely because the stated d-separation conditions license Rule 2, so this is an application of a standard external theorem, not a circular definition. Section 5's column generation is standard LP/simplex methodology, and the single-program variant of Section 5.3 is fully specified by the displayed linearization constraints (0 <= alpha <= m, p+m-1 <= alpha <= p); the citation to Cozman and Fargoni di Ianni [2015] is only a precedent note, not the load-bearing justification, so it is a minor non-load-bearing self-citation. The genuine weakness flagged by the skeptical review is a possible proof gap, not circularity: Lemma 1 gives only a brief moral-graph sketch and Case C4 provides no constructive search for W_t nor an explicit statement excluding X from the separator St, even though the d-separation statements and Rule 2 application require the conditioned set not to contain X. That is a correctness-risk issue in an otherwise independent derivation; it does not make the theorem true by construction or reduce the output to the input. Score 2 reflects the one minor non-load-bearing self-citation; the central claim has independent content.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

No parameters are fitted to data; the input empirical distribution is taken as given. No new particles, forces, or latent variables are introduced; the bit encoding is a representation of existing mechanism variables, not a new entity.

assumptions (4)
  • domain assumption Each endogenous variable has at most one exogenous parent (quasi-Markovian assumption).
    The entire derivation, including the single-exogenous-per-c-component structure and the linear programming reduction, depends on this. See Sections 1 and 2.
  • domain assumption Endogenous variables are binary.
    The paper states this at the start of Section 3 to simplify indexes; the extension to categorical variables is claimed but not proven, and the bit encoding in Section 5 relies on binary values.
  • standard math Tian's c-component factorization holds (Expressions (2) to (5)).
    The constraints (6) and objective (7) are built from this prior result, which is an unproved background theorem.
  • domain assumption The observed distribution cPr(V) is feasible, meaning there exists at least one SCM with the given graph inducing it.
    The optimization is over extensions of the partially specified SCM; if the input distribution is not compatible with the graph, the feasible region is empty, as noted in footnote 1 of Section 3.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Multilinear and Linear Programs for Partially Identifiable Queries in Quasi-Markovian Structural Causal Models." pith.science (2026). https://pith.science/paper/JTBC3PK4

@misc{pith2026250903548,
  author       = {Pith},
  title        = {Pith review of: Multilinear and Linear Programs for Partially Identifiable Queries in Quasi-Markovian Structural Causal Models},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/JTBC3PK4}},
  note         = {Machine review of arXiv:2509.03548}
}
read the original abstract

We investigate partially identifiable queries in a class of causal models. We focus on acyclic Structural Causal Models that are quasi-Markovian (that is, each endogenous variable is connected with at most one exogenous confounder). We look into scenarios where endogenous variables are observed (and a distribution over them is known), while exogenous variables are not fully specified. This leads to a representation that is in essence a Bayesian network where the distribution of root variables is not uniquely determined. In such circumstances, it may not be possible to precisely compute a probability value of interest. We thus study the computation of tight probability bounds, a problem that has been solved by multilinear programming in general, and by linear programming when a single confounded component is intervened upon. We present a new algorithm to simplify the construction of such programs by exploiting input probabilities over endogenous variables. For scenarios with a single intervention, we apply column generation to compute a probability bound through a sequence of auxiliary linear integer programs, thus showing that a representation with polynomial cardinality for exogenous variables is possible. Experiments show column generation techniques to be superior to existing methods.

Figures

Figures reproduced from arXiv: 2509.03548 by the authors.

Figure 1
Figure 1. (a) An example proposed by Sachs et al. [2023]. (b) The factorization of the (marginal) distribution for endogenous [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Graphs for quasi-Markovian SCMs, used in exam [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. A parameterized expansion of the graph in Figure [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: Left: a quasi-Markovian model. Right: the intervened semi-marginal graph for [PITH_FULL_IMAGE:figures/full_fig_p013_4.png]

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

18 extracted references · 16 canonical work pages

  1. [1]

    Balke and J

    A. Balke and J. Pearl. Counterfactual probabilities: Computational methods, bounds and applications. In Proceedings of the Tenth International Conference on Uncertainty in Artificial Intelligence, pages 46--54, 1994

    work page 1994

  2. [2]

    Balke and J

    A. Balke and J. Pearl. Bounds on treatment effects from studies with imperfect compliance. Journal of the American Statistical Association, 92: 0 1171--1176, 1997

    work page 1997

  3. [3]

    Tsitsiklis

    Dimitris Bertsimas and John N. Tsitsiklis. Introduction to Linear Optimization. Athena Scientific, 1997

    work page 1997

  4. [4]

    Fabio G. Cozman. Credal networks. Artificial Intelligence, 120 0 (2): 0 199--233, 2000

    work page 2000

  5. [5]

    Cozman and Lucas Fargoni di Ianni

    Fabio G. Cozman and Lucas Fargoni di Ianni. Probabilistic satisfiability and coherence checking through integer programming. International Journal Approximate Reasoning, 58 0 (C): 0 57–70, 2015. ISSN 0888-613X

    work page 2015

  6. [6]

    An automated approach to causal inference in discrete settings

    Guilherme Duarte, Noam Finkelstein, Dean Knox, Jonathan Mummolo, and Ilya Shpitser. An automated approach to causal inference in discrete settings. Journal of the American Statistical Association, 119 0 (547): 0 1778–1793, 2024

    work page 2024

  7. [7]

    An axiomatic characterization of causal counterfactuals

    David Galles and Judea Pearl. An axiomatic characterization of causal counterfactuals. Foundations of Science, 3 0 (1): 0 151--182, 1998

    1998

  8. [8]

    Joseph Y. Halpern. Axiomatizing causal reasoning. Journal of Artificial Intelligence Research, 12: 0 317–337, 2000

    work page 2000

Show all 18 references
  1. [9]

    Probabilistic Graphical Models: Principles and Techniques

    Daphner Koller and Nir Friedman. Probabilistic Graphical Models: Principles and Techniques. MIT Press, 2009

    2009

  2. [10]

    Causality

    Judea Pearl. Causality. Cambridge University Press, 2009

    2009

  3. [11]

    Sachs, Gustav Jonzon, Arvid Sjölander, and Erin E

    Michael C. Sachs, Gustav Jonzon, Arvid Sjölander, and Erin E. Gabriel. A general method for deriving tight symbolic bounds on causal effects. Journal of Computational and Graphical Statistics, 32 0 (2): 0 567--576, 2023

    2023

  4. [12]

    Scalable computation of causal bounds

    Madhumitha Shridharan and Garud Iyengar. Scalable computation of causal bounds. Journal of Machine Learning Research, 24 0 (237): 0 1--35, 2023 a

    2023

  5. [13]

    Causal bounds in quasi- M arkovian graphs

    Madhumitha Shridharan and Garud Iyengar. Causal bounds in quasi- M arkovian graphs. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, Proceedings of the 40th International Conference on Machine Learning, volume ...

    2023

  6. [14]

    J. Tian. Studies in Causal Reasoning and Learning. PhD thesis, UCLA, 2002

    2002

  7. [15]

    Tian and J

    J. Tian and J. Pearl. Probabilities of causation: Bounds and identification. Annals of Mathematics and Artificial Intelligence, 28: 0 287--313, 2000

    2000

  8. [16]

    Zaffalon, A

    M. Zaffalon, A. Antonucci, R. Caba\ nas, D. Huber, and D. Azzimonti. Efficient computation of counterfactual bounds. International Journal of Approximate Reasoning, pages 1--24, 2024

    2024

  9. [17]

    Structural causal models are (solvable by) credal networks

    Marco Zaffalon, Alessandro Antonucci, and Rafael Caba \ n as. Structural causal models are (solvable by) credal networks. In International Conference on Probabilistic Graphical Models, pages 581--592. PMLR, 2020

    2020

  10. [18]

    Partial counterfactual identification from observational and experimental data

    Junzhe Zhang, Jin Tian, and Elias Bareinboim. Partial counterfactual identification from observational and experimental data. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, Proceedings of the 39th International Conferen...

    2022

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.