# TriOpt: A Scalable Algorithm for Linear Causal Discovery

arXiv: https://arxiv.org/abs/2605.17465 · HTML: https://mlsanity.com/paper/2605.17465/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 26 references that are in the map.
- First posted on arXiv 17 May 2026.

## Builds on (most cited first, 10 of 10)

- [DAGs with NO TEARS: Continuous Optimization for Structure Learning](https://mlsanity.com/paper/1803.01422/) (2018)
- [On the Role of Sparsity and DAG Constraints for Learning Linear DAGs](https://mlsanity.com/paper/2006.10201/) (2020)
- [CAM: Causal additive models, high-dimensional order search and penalized regression](https://mlsanity.com/paper/1310.1533/) (2013)
- [DAGMA: Learning DAGs via M-matrices and a Log-Determinant Acyclicity Characterization](https://mlsanity.com/paper/2209.08037/) (2022)
- [Score matching enables causal discovery of nonlinear additive noise models](https://mlsanity.com/paper/2203.04413/) (2022)
- [Diffusion Models for Causal Discovery via Topological Ordering](https://mlsanity.com/paper/2210.06201/) (2022)
- [gCastle: A Python Toolbox for Causal Discovery](https://mlsanity.com/paper/2111.15155/) (2021)
- [Gradient Estimators for Implicit Models](https://mlsanity.com/paper/1705.07107/) (2017)
- [Adjustment Identification Distance: A gadjid for Causal Structure Learning](https://mlsanity.com/paper/2402.08616/) (2024)
- [Ordering-Based Causal Discovery for Linear and Nonlinear Relations](https://mlsanity.com/paper/2410.05890/) (2024)

## Abstract (arXiv)

Learning causal relations from observational data is challenging because the graph search space grows super-exponentially with the number of variables. Ordering-based methods reduce this space by first identifying the topological ordering, whereas continuous optimization methods explore most likely regions of the space by casting DAG learning as a differentiable objective with an acyclicity constraint. Despite their conceptual appeal, both paradigms face significant scalability limitations in high-dimensional settings, restricting their practical applicability. In this work, we introduce a new formulation for linear causal discovery that tightly integrates these two paradigms to achieve substantial gains in scalability without sacrificing accuracy. Our approach, TriOpt, decomposes the problem into two efficient stages. First, it recovers the topological ordering by exploiting the Sherman-Morrison rank-1 downdate together with the additive structure of linear kernels, enabling fast and scalable ordering estimation. Second, given this ordering, we reformulate structure learning as a convex continuous optimization problem that entirely avoids the need for enforcing costly acyclicity constraints. We theoretically show that, under the true ordering, TriOpt exactly recovers the underlying linear DAG. Empirically, across synthetic, semi-synthetic, and real-world datasets, TriOpt achieves orders-of-magnitude speedups over state-of-the-art linear causal discovery methods in high-dimensional regimes, while maintaining comparable or superior accuracy.