Discovering cause-and-effect relationships from observational data is a fundamental challenge in science. Traditional constraint-based methods, such as the PC or FCI algorithms, operate procedurally: they perform statistical independence tests and apply a fixed sequence of orientation rules to reconstruct the underlying causal graph.
However, this step-by-step approach suffers from a major vulnerability: if a single statistical test returns an error due to noise, that error cascades through subsequent steps, leading to incorrect orientations. Furthermore, adapting these procedural algorithms to accommodate complex real-world conditions—such as feedback loops (cycles), hidden confounders, or datasets with non-overlapping variables—often requires designing entirely new algorithms from scratch.
To overcome these limitations, a powerful paradigm reframes causal discovery as a constraint satisfaction problem. Instead of executing a step-by-step recipe, this approach translates statistical observations and structural assumptions into a system of logical rules. By leveraging general-purpose Boolean satisfiability (SAT) or Answer Set Programming (ASP) solvers, it finds the causal models that are globally consistent with the data.
The Core Mechanism: Mapping Graphs to Logic
To understand why this approach works, we must look at how a graph search is converted into a logic puzzle.
First, the structure of the causal graph is represented by Boolean variables. For every pair of variables $X$ and $Y$ in a system, we can define propositional variables to represent potential structural relationships:
- $E_{xy}$ is true if there is a directed edge from $X$ to $Y$.
- $C_{xy}$ is true if there is a latent confounder (an unmeasured common cause) acting on both $X$ and $Y$.
Next, the rules of causal graph theory—specifically the principles of d-separation and d-connection, which link graph topology to statistical independence—are encoded as logical constraints. For example, if two variables $X$ and $Y$ are found to be statistically independent given some set $Z$, d-separation dictates that there cannot be an active causal path between $X$ and $Y$ conditioned on $Z$. This requirement can be written as a set of logical clauses involving our edge variables $E$ and $C$.
As Tom Claassen et al. demonstrated in A Logical Characterization of Constraint-Based Causal Discovery, observed conditional independencies can be directly manipulated using deductive reasoning rules to infer causal links without ever needing to construct a concrete graphical model step-by-step.
When a full graph search is required, Antti Hyttinen et al. showed in Discovering Cyclic Causal Models with Latent Variables: A General SAT-Based Procedure that these d-separation rules can be systematically encoded into a SAT solver. The solver then evaluates the entire search space at once, identifying the "backbone" of the causal graph—the specific edges whose presence or absence is logically necessitated across every single valid solution.
[Statistical Data] ------> [Independence Tests]
|
v
[Prior Knowledge] ------> [Logical Constraints] ------> [SAT / ASP Solver] ------> [Consistent Causal Graphs]
(e.g., d-separation)
This formulation also makes it trivial to integrate background knowledge. In many scientific domains, researchers already know that certain causal links are impossible (e.g., a future event cannot cause a past event). In a procedural algorithm, incorporating these rules requires custom modifications. In a logic-based framework, as Giorgos Borboudakis et al. detailed in A constraint-based approach to incorporate prior knowledge in causal models, prior beliefs are simply appended as additional hard logical clauses, immediately pruning large swaths of the search space.
Handling Real-World Noise via Optimization
In an ideal world with infinite data, statistical tests would be perfect, and a standard SAT solver would easily find a graph that satisfies every constraint. In reality, statistical tests are noisy and frequently contradict one another (e.g., testing pairs locally might suggest an edge exists, but a conditional test might suggest it does not). A pure SAT solver faced with conflicting constraints will simply declare the formula "unsatisfiable" and fail.
To handle real-world noise, the framework shifts from strict constraint satisfaction (SAT) to weighted constraint satisfaction (Max-SAT) or Answer Set Programming (ASP) optimization.
Instead of treating every statistical test result as an absolute truth, each test is treated as a soft constraint paired with a weight. This weight reflects the reliability of the test, typically derived from p-values or log-likelihood ratios. Structural axioms (such as acyclicity, if assumed) remain hard constraints that cannot be broken.
Sara Magliacane et al. leveraged this optimization strategy in Ancestral Causal Inference. By minimizing the sum of the weights of violated constraints, the solver performs a global optimization. If a handful of localized statistical tests are incorrect due to noise, the solver can choose to overrule them if satisfying them would break a larger, more confident web of globally consistent relationships.
This global error-correction capability allows the framework to scale to highly complex settings. For instance, Patrick Forré et al. applied declarative logic optimization in Constraint-based Causal Discovery for Non-Linear Structural Causal Models with Cycles and Latent Confounders to successfully resolve constraints in non-linear systems containing both feedback loops and hidden variables.
Modularity and Weaker Assumptions
One of the most elegant features of logic-based causal discovery is its modularity. In traditional causal discovery, changing an underlying assumption—such as moving from an acyclic system to a cyclic one, or relaxing the "faithfulness" assumption—requires rewriting the entire execution logic of the algorithm.
In a logic-based framework, the search engine (the solver) remains exactly the same; only the input constraints change.
This flexibility is highly apparent when dealing with the "faithfulness" assumption, which states that every statistical independence in the data matches a d-separation in the true graph. Because weak faithfulness or unfaithfulness can occur in real-world data (e.g., when two causal paths cancel each other out), Jiji Zhang et al. demonstrated in SAT-Based Causal Discovery under Weaker Assumptions that researchers can seamlessly swap out strict faithfulness for weaker, more robust variants by simply altering the logical clauses given to the solver.
Similarly, Zhalama et al. extended this to semi-Markovian models in ASP-based Discovery of Semi-Markovian Causal Models under Weaker Assumptions, showing that ASP can efficiently navigate the space of graphs under relaxed assumptions. By encoding Markov properties directly as logical rules, as explored by José M. Peña 0001 in Alternative Markov and Causal Properties for Acyclic Directed Mixed Graphs, these methods perform exact searches that avoid the local optima traps common to greedy heuristic searches.
Solving Fragmented Data and Planning Experiments
The declarative nature of logic solvers makes them uniquely suited for two advanced tasks in causal discovery: integrating fragmented datasets and planning future experiments.
Overlapping Variable Sets
Often, scientists cannot measure every variable of interest in a single study. Instead, they must rely on multiple historical datasets that measured different, overlapping subsets of variables. Procedural algorithms struggle here because they cannot compute a single joint distribution.
Logic solvers handle this naturally. As Sofia Triantafillou et al. demonstrated in Learning Causal Structure from Overlapping Variable Sets, independence constraints collected from completely separate studies can be pooled into a single SAT instance. The solver then searches for a global graph structure that simultaneously satisfies the constraints of all individual datasets. In Constraint-based causal discovery from multiple interventions over overlapping variable sets, Sofia Triantafillou further showed that this approach seamlessly scales to handle a mix of observational and experimental data across fragmented studies.
Active Experiment Selection
When existing data is insufficient to resolve a causal graph down to a single unique structure, a logic solver can output the entire set of remaining viable graphs. This capability can be used to determine what experiment should be performed next.
In Experiment Selection in Meta-Analytic Piecemeal Causal Discovery, Nicholas J. Matiasz et al. showed that by calculating the "degrees of freedom" remaining among the satisfying graph structures, an ASP solver can systematically select the next optimal intervention to perform. This formalization prevents researchers from overlooking valid alternative hypotheses due to cognitive biases or memory limits, a concept applied to neuroscience experiment design by Nicholas J. Matiasz et al. in Computer-Aided Experiment Planning toward Causal Discovery in Neuroscience.
Downstream Applications: Do-Calculus and Time Series
The utility of logic-based constraint solving extends beyond finding the graph itself; it can be applied directly to downstream causal reasoning tasks.
For example, if we want to estimate the quantitative effect of an intervention using Judea Pearl's do-calculus, we traditionally need to know the exact causal graph. If the graph is unknown, we might have to enumerate every possible graph in an equivalence class and check if the effect is identifiable in each one—a computationally prohibitive task.
Antti Hyttinen et al. solved this in Do-calculus when the True Graph Is Unknown by encoding the graphical properties required for a do-calculus estimator's validity directly into the logic solver. When the solver finds a valid estimator for one graph, it extracts the underlying graphical properties that made it work and instructs the solver to instantly prune all other graphs in the search space that share those identical properties. This allows for the direct identification of causal effects across entire equivalence classes without exhaustive enumeration.
[Equivalence Class of Graphs]
|
v
[Find Valid Estimator for Graph A]
|
v
[Extract Core Graphical Properties]
|
v
[Prune All Graphs Sharing Properties] ---> (Massive Search Space Reduction)
Finally, this framework can resolve structural challenges in time-series analysis. When time-series data is subsampled (measured too slowly compared to the underlying system's actual frequency), the true causal paths become obscured by apparent simultaneity and confounding. As Antti Hyttinen et al. demonstrated in Causal Discovery from Subsampled Time Series Data by Constraint Optimization, declarative constraints can map observed, slow-paced measurement dependencies back to the true, high-frequency system-level graphs, achieving processing speeds orders of magnitude faster than specialized iterative algorithms.
Key Foundational Work
A constraint-based approach to incorporate prior knowledge in causal models (2011) — contributed 3 concept elements to this direction.
Learning Causal Structure from Overlapping Variable Sets (2010) — contributed 2 concept elements to this direction.
A Logical Characterization of Constraint-Based Causal Discovery (2011) — contributed 2 concept elements to this direction.