pith. sign in

arxiv: 2604.20516 · v1 · submitted 2026-04-22 · 📊 stat.ML · cs.LG

Efficient Symbolic Computations for Identifying Causal Effects

Benjamin Hollering , Pratik Misra , Nils Sturma This is my paper

Pith reviewed 2026-05-09 23:22 UTC · model grok-4.3

classification 📊 stat.ML cs.LG
keywords causal inferenceidentifiabilitysymbolic computationlinear structural causal modelscausal effectsalgorithmrational identification
0
0 comments X

The pith

An efficient algorithm finds the lowest-degree formulas that identify causal effects from data in linear models.

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

The paper develops a symbolic computation method to decide whether a causal effect can be identified from observational data when some variables are unobserved. It targets linear structural causal models and focuses on finding rational expressions of bounded degree that express the effect in terms of observable quantities. Standard Gröbner basis techniques for this task scale doubly exponentially and quickly become unusable. The new procedure instead returns a lowest-degree identifying formula in quasi-polynomial time whenever one exists within a user-specified degree bound. If correct, this shifts symbolic causal identification from a theoretical curiosity to a practical tool for graphs of moderate size.

Core claim

For linear structural causal models, rational identifiability of a causal effect is decidable by searching for polynomials of bounded degree that satisfy the required algebraic relations; the presented algorithm performs this search and returns the lowest-degree solution in quasi-polynomial time whenever such a solution of prespecified maximal degree exists.

What carries the argument

A bounded-degree symbolic search procedure that enumerates candidate polynomials satisfying the linear model constraints and extracts the resulting rational identifying formula for the target causal effect.

If this is right

  • Causal effects previously checked only on tiny graphs can now be tested on graphs with dozens of variables.
  • The returned formulas are the simplest possible within the degree limit, yielding compact expressions for effect estimation.
  • Rational identifiability becomes a routine computational check rather than a manual algebraic exercise.
  • The approach separates the question of existence of any identifying formula from the harder question of finding one of minimal complexity.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Combining the procedure with automated causal graph search could produce end-to-end pipelines that both discover structure and derive explicit effect estimators.
  • The same bounded-degree technique may extend to other algebraic identifiability problems outside causal inference, such as parameter recovery in linear systems.
  • In applied domains the method supplies ready-to-use algebraic expressions that can be plugged directly into estimation routines without numerical optimization.

Load-bearing premise

An identifying formula of bounded degree is assumed to exist for the effect of interest.

What would settle it

A concrete linear causal graph together with a known low-degree identifying formula for some effect, on which the algorithm either fails to return that formula or exceeds quasi-polynomial runtime.

Figures

Figures reproduced from arXiv: 2604.20516 by Benjamin Hollering, Nils Sturma, Pratik Misra.

Figure 1
Figure 1. Figure 1: Mixed graph corresponding to a conditionally randomized trial with imperfect adherence. [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Mixed graph for the instrumental variable model. [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Another mixed graph. Definition 2.8. Let ≺ be a total order on θ. We say that gq ∈ I is an identifying polynomial for q ∈ θ with respect to the order ≺ if there is a subset θid ⊆ θ with s ≺ q for all s ∈ θid such that gq is of the form gq = qa(θid, σ) − b(θid, σ) with a, b ∈ R[θid, σ] and a ̸∈ I ∩ R[θid, σ]. If an identifying polynomial gq exists for all q ∈ θ with respect to the order ≺, then we say that … view at source ↗
Figure 4
Figure 4. Figure 4: Boxplots of computing times of the Garcia-Puente algorithm (GP) and Algorithm [PITH_FULL_IMAGE:figures/full_fig_p014_4.png] view at source ↗
read the original abstract

Determining identifiability of causal effects from observational data under latent confounding is a central challenge in causal inference. For linear structural causal models, identifiability of causal effects is decidable through symbolic computation. However, standard approaches based on Gr\"obner bases become computationally infeasible beyond small settings due to their doubly exponential complexity. In this work, we study how to practically use symbolic computation for deciding rational identifiability. In particular, we present an efficient algorithm that provably finds the lowest degree identifying formulas. For a causal effect of interest, if there exists an identification formula of a prespecified maximal degree, our algorithm returns such a formula in quasi-polynomial time.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The manuscript presents an efficient algorithm for symbolic computation of rational identifying formulas for causal effects in linear structural causal models with latent confounding. It claims that, given a prespecified maximal degree, if an identifying formula of that degree exists then the algorithm returns the lowest-degree such formula in quasi-polynomial time, offering a practical improvement over the doubly-exponential complexity of Gröbner basis methods.

Significance. If the central claims hold, the work would meaningfully advance practical causal inference by making symbolic identifiability checks feasible on larger graphs where Gröbner bases become intractable. The conditional efficiency guarantee, focus on lowest-degree formulas, and restriction to linear SCMs with rational identifiability constitute a clear algorithmic contribution; any accompanying formal proofs or reproducible implementations would further strengthen its value.

minor comments (3)
  1. The abstract and introduction would benefit from a brief, self-contained example of a low-degree identifying formula to illustrate the output of the algorithm.
  2. §4 (complexity analysis): the quasi-polynomial bound is stated clearly but the dependence on the maximal degree parameter could be made more explicit for readers.
  3. Table 2 (runtime comparisons): adding a column for the degree of the returned formula would help readers assess whether the efficiency gain preserves the lowest-degree property.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary of the manuscript, recognition of its potential practical impact, and recommendation for minor revision. No major comments were provided in the report.

Circularity Check

0 steps flagged

No significant circularity; algorithmic result is self-contained

full rationale

The paper presents a new algorithm for computing lowest-degree rational identifying formulas for causal effects in linear SCMs, with a quasi-polynomial runtime guarantee conditional on existence within a bounded degree. This is positioned as a practical improvement over the doubly-exponential cost of Gröbner bases. The derivation relies on standard symbolic algebra and complexity arguments that are external to the paper; no step reduces by construction to a fitted parameter, self-definition, or load-bearing self-citation. The central claim is scoped explicitly to the linear/rational setting and does not rename or smuggle in prior results as new derivations.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper operates within the established framework of linear structural causal models and symbolic algebra for identifiability; no new free parameters, ad-hoc axioms, or invented entities are introduced in the abstract.

axioms (2)
  • domain assumption Linear structural causal models admit decidable rational identifiability via symbolic computation
    Stated directly in the abstract as the setting where identifiability is decidable.
  • standard math Gröbner basis methods have doubly exponential complexity
    Invoked to motivate the need for a more efficient algorithm.

pith-pipeline@v0.9.0 · 5406 in / 1325 out tokens · 39109 ms · 2026-05-09T23:22:58.968050+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

37 extracted references · 37 canonical work pages

  1. [1]

    M., and Robbiano, L

    Abbott, J., Bigatti, A. M., and Robbiano, L. (2017). Implicitization of hypersurfaces. Journal of Symbolic Computation , 81:20--40

    work page 2017

  2. [2]

    Améndola, C., Puente, L. D. G., Pons, R. H., Kuznetsova, O., Motwani, H. J., Petrovic, S., Stillman, M., and Sullivant, S. (2020). GraphicalModels: discrete and Gaussian graphical models. Version 2.0 . A Macaulay2 package available at https://github.com/Macaulay2/M2/tree/stable/M2/Macaulay2/packages

    work page 2020

  3. [3]

    Bollen, K. A. (1989). Structural equations with latent variables . Wiley Series in Probability and Mathematical Statistics: Applied Probability and Statistics. John Wiley & Sons, Inc., New York

    work page 1989

  4. [4]

    Bowden, R. J. and Turkington, D. A. (1984). Instrumental variables , volume 8 of Econometric Society Monographs in Quantitative Economics . Cambridge University Press, Cambridge

    work page 1984

  5. [5]

    Chen, B., Kumor, D., and Bareinboim, E. (2017). Identification and model testing in linear structural equation models using auxiliary variables. In Proceedings of the 34th International Conference on Machine Learning , pages 757--766. JMLR

    work page 2017

  6. [6]

    Chen, B., Pearl, J., and Bareinboim, E. (2016). Incorporating knowledge into structural equation models using auxiliary variables. In Proceedings of the 25th International Joint Conference on Artificial Intelligence , pages 3577--3583. AAAI Press

    work page 2016

  7. [7]

    H., Leiserson, C

    Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. (2009). Introduction to algorithms . MIT Press, Cambridge, MA, third edition

    work page 2009

  8. [8]

    A., Little, J., and O'Shea, D

    Cox, D. A., Little, J., and O'Shea, D. (2015). Ideals, varieties, and algorithms . Undergraduate Texts in Mathematics. Springer, Cham, fourth edition

    work page 2015

  9. [9]

    Dettling, P., Homs, R., Am\'endola, C., Drton, M., and Hansen, N. R. (2023). Identifiability in continuous L yapunov models. SIAM Journal on Matrix Analysis and Applications , 44(4):1799--1821

    work page 2023

  10. [10]

    o rfler, J., van der Zander, B., Bl\

    D\" o rfler, J., van der Zander, B., Bl\" a ser, M., and Li\' s kiewicz, M. (2024). On the complexity of identification in linear structural causal models. In Advances in Neural Information Processing Systems , volume 37, pages 100108--100130. Curran Associates, Inc

    work page 2024

  11. [11]

    and Weihs, L

    Drton, M. and Weihs, L. (2016). Generic identifiability of linear structural equation models by ancestor decomposition. Scandinavian Journal of Statistics. Theory and Applications , 43(4):1035--1045

    work page 2016

  12. [12]

    and Herzog, J

    Ene, V. and Herzog, J. (2012). Gr\"obner bases in commutative algebra , volume 130 of Graduate Studies in Mathematics . American Mathematical Society, Providence, RI

    work page 2012

  13. [13]

    Faug\'ere, J.-C. (1999). A new efficient algorithm for computing G r\"obner bases (F_4) . Journal of Pure and Applied Algebra , 139(1-3):61--88

    work page 1999

  14. [14]

    Faug\`ere, J.-C. (2002). A new efficient algorithm for computing G r\"obner bases without reduction to zero (F_5) . In Proceedings of the 2002 I nternational S ymposium on S ymbolic and A lgebraic C omputation , pages 75--83. ACM, New York

    work page 2002

  15. [15]

    Faug\`ere, J.-C., Safey El Din, M., and Verron, T. (2016). On the complexity of computing G r\"obner bases for weighted homogeneous systems. Journal of Symbolic Computation , 76:107--141

    work page 2016

  16. [16]

    Finch, S. R. (2019). Mathematical constants. II , volume 169 of Encyclopedia of Mathematics and its Applications . Cambridge University Press, Cambridge

    work page 2019

  17. [17]

    Foygel, R., Draisma, J., and Drton, M. (2012a). Half-trek criterion for generic identifiability of linear structural equation models. The Annals of Statistics , 40(3):1682--1713

    work page

  18. [18]

    Foygel, R., Draisma, J., and Drton, M. (2012b). Supplement to half-trek criterion for generic identifiability of linear structural equation models. The Annals of Statistics , 40(3)

    work page

  19. [19]

    D., Spielvogel, S., and Sullivant, S

    Garcia-Puente, L. D., Spielvogel, S., and Sullivant, S. (2010). Identifying causal effects with computer algebra. In Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence . AUAI Press

    work page 2010

  20. [20]

    Grayson, D. R. and Stillman, M. E. (2025). Macaulay2, a software system for research in algebraic geometry. Version 1.25.11, available at https://www.macaulay2.com

    work page 2025

  21. [21]

    and Robins, J

    Hernán, M. and Robins, J. (2025). Causal Inference: What If . Chapman & Hall/CRC Monographs on Statistics & Applied Probab. CRC Press

    work page 2025

  22. [22]

    and Robbiano, L

    Kreuzer, M. and Robbiano, L. (2005). Computational commutative algebra. 2 . Springer-Verlag, Berlin

    work page 2005

  23. [23]

    Kumor, D., Chen, B., and Bareinboim, E. (2019). Efficient identification in linear structural causal models with instrumental cutsets. In Advances in Neural Information Processing Systems , volume 32, pages 12477--12486. Curran Associates, Inc

    work page 2019

  24. [24]

    Kumor, D., Cinelli, C., and Bareinboim, E. (2020). Efficient identification in linear structural causal models with auxiliary cutsets. In Proceedings of the 37th International Conference on Machine Learning , volume 119 of Proceedings of Machine Learning Research , pages 5501--5510. PMLR

    work page 2020

  25. [25]

    Mayr, E. W. (1997). Some complexity results for polynomial ideals. Journal of Complexity , 13(3):303--325

    work page 1997

  26. [26]

    Pearl, J. (2009). Causality . Cambridge University Press, Cambridge, second edition

    work page 2009

  27. [27]

    Spirtes, P., Glymour, C., and Scheines, R. (2000). Causation, prediction, and search . Adaptive Computation and Machine Learning. MIT Press, Cambridge, MA, second edition

    work page 2000

  28. [28]

    Sturma, N., Kranzlmueller, M., Portakal, I., and Drton, M. (2026). Matching criterion for identifiability in sparse factor analysis. Psychometrika , page 1–20

    work page 2026

  29. [29]

    Sullivant, S. (2018). Algebraic statistics , volume 194 of Graduate Studies in Mathematics . American Mathematical Society, Providence, RI

    work page 2018

  30. [30]

    Sullivant, S., Talaska, K., and Draisma, J. (2010). Trek separation for G aussian graphical models. The Annals of Statistics , 38(3):1665--1685

    work page 2010

  31. [31]

    Tian, J. (2005). Identifying direct causal effects in linear models. In Proceedings of the 20th National Conference on Artificial Intelligence , pages 346--352. Association for the Advancement of Artificial Intelligence, AAAI Press

    work page 2005

  32. [32]

    Tian, J. (2009). Parameter identification in a class of linear structural equation models. In Proceedings of the 21st International Joint Conference on Artificial Intelligence , pages 1970--1975. AAAI Press

    work page 2009

  33. [33]

    Voros, A. (1987). Spectral functions, special functions and the Selberg zeta function . Communications in Mathematical Physics , 110(3):439 -- 465

    work page 1987

  34. [34]

    I., Nguyen, N., Robeva, E., and Drton, M

    Weihs, L., Robinson, B., Dufresne, E., Kenkel, J., Kubjas Reginald McGee II, K., Reginald, M. I., Nguyen, N., Robeva, E., and Drton, M. (2017). Determinantal generalizations of instrumental variables. Journal of Causal Inference , 6(1)

    work page 2017

  35. [35]

    Wright, P. G. (1928). Tariff on Animal and Vegetable Oils . Macmillan Company, New York

    work page 1928

  36. [36]

    Wright, S. (1921). Correlation and causation. Journal of agricultural research , 20(7):557 -- 585

    work page 1921

  37. [37]

    Wright, S. (1934). The method of path coefficients. The Annals of Mathematical Statistics , 5(3):161–215

    work page 1934