COSMIC: Scalable Causal Discovery via Nyström Macro-Tier Peeling

Recovering causal graphs from purely observational data is essential when experimental interventions are constrained by ethical or logistical barriers. However, ordering-based approaches face severe computational bottlenecks due to repeated kernel computations that scale cubically with sample size and quadratically with graph dimension. We introduce COSMIC, a highly scalable causal discovery framework for nonlinear additive noise models. Our approach integrates a low-rank Nyström Stein approximation with adaptive macro-tier peeling to eliminate batches of candidate sinks simultaneously, drastically reducing both the size and frequency of kernel computations. To combine ordering evidence across scales and inform intra-tier evidence allocation, COSMIC utilizes a Tri-Band Harmonic Stein Ensemble and evaluates leave-one-macro-tier-out parent scores with local coupling confidence. We support this framework by formally showing that terminal-block removals preserve the underlying Additive Noise Model structure. Extensive benchmarking demonstrates that COSMIC scales topological ordering and candidate parent screening to $d=500$ variables in minutes, a regime where existing non-parametric methods stall. In full end-to-end discovery (including non-parametric regression pruning), COSMIC completes graphs through $d=100$ before downstream GAM pruning reaches an empirical timeout at $d=200$. Across small synthetic and biological benchmarks ($d=10$–$20$), COSMIC achieves competitive recovery accuracy while evaluating candidate edges orders of magnitude faster than continuous-DAG and non-parametric baselines.