When we intervene softly on a system, for example by dialing a gene's expression up or down without switching it off, the data we collect constrain which way some causal arrows point. With hidden confounders, extracting all of that orientation information is hard. A known sound algorithm leaves many edge ends undecided. The one procedure proven to decide every edge end that can be decided works by listing every candidate graph, and it already times out at 100 variables. We propose to get the same complete answer without listing anything. For each undecided edge end, we ask a logic solver two yes/no questions: does some valid graph consistent with the data put an arrowhead here, and does some valid graph put a tail here? The expensive global rules that define "valid" are not written out in advance. The solver proposes a candidate graph, a fast polynomial-time checker finds the specific cycle or path the candidate violates, and only that one constraint is added before the solver tries again.
The bet is that the global constraints a completion actually needs are few and concentrated around the undecided marks. If so, the cost of an exact, complete answer would grow polynomially with graph size instead of super-exponentially. That would take complete soft-interventional orientation from toy graphs to hundreds of variables. A second, explicitly optional bet concerns which questions to ask first and which constraints to add before they are violated. A cheap learned ranking trained on small graphs, where the exact answer is computable, could make those choices on much larger graphs, because the solver only ever works on a small leftover subproblem.
Background and the gap
We work in the setting of Towards Completeness in Causal Discovery from Soft Interventions with Known Targets. Interventions are represented by indicator nodes ("F-nodes") attached to their known target variables. Causal structure with hidden confounders is summarized by a maximal ancestral graph (MAG), a mixed graph whose edges can end in arrowheads, tails, or undecided "circle" marks. The algorithm $\mathcal{I}$-FCI outputs a partial graph that is sound but incomplete. That paper proposes two remedies. FAST adds three polynomial-time local orientation rules at almost no cost. LIST enumerates all completions and filters them with an interventional realizability check, which makes it complete. The authors prove local rules cannot be complete, because some marks are forced only by inducing paths or almost-directed cycles that run through distant nodes. LIST, for its part, timed out at $n=100$. This paper motivates our proposal and supplies the problem definition, the correctness reference (LIST), and the cheap baseline (FAST).
Two lines of declarative causal discovery show why the obvious exact alternative fails. SAT-Based Causal Discovery under Weaker Assumptions encodes the whole structure-learning problem in Answer Set Programming (ASP), a logic language whose rules are expanded ("grounded") over all variable combinations before a satisfiability solver runs. Its strict-faithfulness encoding timed out at 10 variables, and its most scalable variant completed 95% of 10-variable runs with runtime growing exponentially. Integer Programming for Causal Structure Learning in the Presence of Latent Variables finds globally score-optimal mixed graphs, and beat greedy search in 53 of 60 instances, but it stalls near 18–20 variables. Both papers constrain our design. Grounding high-arity ancestral rules up front is a dead end. Both papers also attack the full structure-learning problem, whereas we keep $\mathcal{I}$-FCI's adjacencies and solve only the orientation-completion problem, which is much smaller.
The method itself comes from the grounding literature. Lazy Model Expansion: Interleaving Grounding with Search instantiates constraints only when the current assignment threatens them, which cut a reachability task from about 30 million ground atoms to 16,000. Bypassing the ASP Bottleneck: Hybrid Grounding by Splitting and Rewriting splits programs so that dense parts avoid naive grounding, and it solved over 2,000 traffic instances where standard grounders solved about 200. Neither has been applied to causal discovery. That paper itself warns that lazy grounding hides constraints from the solver's propagation and causes extra backtracking. This "informedness" cost is the specific failure we must measure. The optional learned component borrows one idea from BQ-NCO: Bisimulation Quotienting for Efficient Neural Combinatorial Optimization. That paper generalizes from 100-city to 1,000-city routing problems by describing each decision through the remaining subproblem rather than the growing solution, so large instances look locally like small ones.
Core Claim
Let $P$ be the augmented partial graph from $\mathcal{I}$-FCI, and let $[P]$ be the set of augmented MAGs that are valid and interventionally Markov-equivalent to it. Validity means no directed or almost-directed cycles and no inducing paths between non-adjacent nodes. A circle mark $m$ is compelled to an arrowhead exactly when no member of $[P]$ has a tail at $m$, and compelled to a tail exactly when no member has an arrowhead:
$$ m \text{ is decided} \iff \neg\,\exists G \in [P] : G(m)=\text{tail} \;\;\text{or}\;\; \neg\,\exists G \in [P] : G(m)=\text{arrowhead}. $$
Each existence question is a satisfiability query. Membership in $[P]$ can be checked for a single candidate graph in polynomial time, even though writing it out as clauses requires constraints over paths whose number explodes. We therefore ground only the cheap local part up front: the fixed skeleton, fixed unshielded colliders, the fixed marks from $\mathcal{I}$-FCI and FAST, and the F-node edges. Validity, the remaining equivalence conditions, and realizability are enforced lazily. Whenever the solver returns a candidate, the checker extracts one violating witness, such as a specific almost-directed cycle, inducing path, or discriminating-path collider mismatch, and adds a single clause forbidding it. Models found along the way are reused, so that one satisfying graph settles every mark it shows to be non-compelled.
The method returns the same answer as LIST, because each query terminates with either a certified valid graph or a certified unsatisfiable core. The claim that can be falsified is about cost. We predict that the number of added clauses grows roughly polynomially in $n$ on sparse random graphs. The reason is that each clause rules out a structure confined to the neighbourhood of undecided marks plus the paths connecting them, and in sparse graphs the circle-mark regions left after FAST are small.
Research Program
The first piece is the solver loop itself. It uses an incremental SAT/ASP backend, an exact polynomial-time validity and equivalence checker for augmented MAGs, and witness extraction that picks the shortest violating cycle or path, so that each clause is as general as possible. The second piece is an analysis of where the clauses come from. We will log every witness and measure its length, its distance from the queried mark, and whether it would have been found by a decomposition into connected circle components. This tells us how non-local soft-interventional completeness really is in practice, a question the FAST/LIST paper settles only in the worst case.
The third piece is the optional learned ordering. On graphs with $n \le 20$, where LIST finishes, we record which marks are compelled and which witnesses each query needed. We then train a small graph network to score marks and candidate witnesses. Its inputs describe only the residual subgraph around a mark: the circle component, nearby F-nodes, and bounded-length paths. By the quotienting argument from BQ-NCO, its inputs should look similar at $n=20$ and $n=500$. The network only orders queries and pre-adds likely clauses. The solver still certifies every answer, so a bad model can cost time but never correctness.
The fourth piece relaxes the "known targets" assumption. We will let some F-node edges be free variables, so that a query asks whether any valid graph with any admissible target assignment flips the mark. This is exactly where LIST cannot go.
Baselines
The do-nothing reference is $\mathcal{I}$-FCI's raw output, which scores zero on the "extra marks resolved" metric. The cheap strong baseline is FAST, $\mathcal{I}$-FCI plus the three transit-node rules from Towards Completeness in Causal Discovery from Soft Interventions with Known Targets. It is the strongest competitor on cost because it has almost no runtime overhead and scaled cleanly to $n=100$. We beat it if we resolve strictly more marks at a runtime that remains practical, which we define as within 100× of FAST at $n=100$. The exact baseline is LIST from the same paper, run with the same CI tests and $\mathcal{I}$-FCI output and the same wall-clock and memory limits. LIST is the strongest method on completeness. We beat it if we produce identical orientations wherever LIST finishes, and if we finish at sizes where LIST times out. The file reports only that FAST improved End-F1 and SHD at $n=5$, that LIST had the best orientation recovery there, and that LIST timed out at $n=100$. No reported numeric result was found on Lacuna for FAST or LIST orientation accuracy, so we will rerun both.
The fair exact-declarative baseline is our own query encoded with every validity, equivalence, and realizability constraint grounded up front in clingo, following the style of SAT-Based Causal Discovery under Weaker Assumptions. It uses the same solver and time budget and differs from our method only in when constraints are grounded. That paper's best reported figure is 95% completion at 10 variables for its scalable variant, on a harder problem. We beat it if our method has lower peak ground size and higher completion rate at every $n$.
The key ablations isolate the main ingredient. The first adds every violated constraint found in each round instead of only the shortest witness. The second solves each circle component independently with no global checks, which tests whether laziness rather than decomposition does the work. The third removes model reuse. For the learned ordering, the comparison is against a random query order and a simple degree-based order under identical solver settings.
Why not just…?
Why not just use FAST? FAST is provably incomplete, and the experiments measure the price in a single number: the fraction of LIST-resolvable marks that FAST leaves as circles. If that fraction is near zero on realistic sparse graphs, our method is not worth its cost there, and we will say so. The witness-locality analysis would then show where, if anywhere, the gap appears, for example in denser graphs or with more latents.
Why not ground everything up front with a standard ASP grounder? The SAT-based causal discovery results show this pattern breaking at 10 variables, and lazy expansion's 30-million-to-16,000 atom reduction shows how much is at stake. This is not assumed, though. The fully grounded baseline runs the identical query, so any advantage is measured directly as peak ground atoms and solve rate against $n$. The real threat runs the other way: lazy grounding may cause so much extra backtracking that the gain disappears on dense graphs. We report backtracks per query to expose this.
Why not run LIST separately on each circle component? This is the most serious alternative, because it might already be fast enough. With hidden confounders, though, components can interact through discriminating paths and inducing paths, so per-component answers can be wrong. We run this decomposition as an ablation and count its disagreements with the certified global answer. If it never disagrees on our benchmarks, the honest conclusion is that decomposed enumeration suffices in practice. In that case our contribution narrows to certifying that it is correct.
Why not use a scalable learner such as PACER or SCOUT instead? PACER scales to 1,000 nodes but assumes hard interventions and no hidden confounders. SCOUT handles soft interventions with unknown targets but also assumes no confounders and was tested up to 70 nodes. Neither outputs an equivalence class with certified compelled marks, which is the object we compute, so they answer a different question. We report them on Sachs only as context.
Proposed Experiments
The synthetic suite uses random sparse and scale-free ADMGs with latent confounders and shift-scale soft interventions on known targets, with $n \in \{5, 10, 20, 50, 100, 200, 500\}$. Each configuration has 30 seeds and runs under both oracle CI tests and finite-sample tests. Metrics are agreement with LIST where it finishes, extra marks resolved beyond FAST, End-F1 and SHD against the true MAG, runtime, peak ground atoms, and number of lazily added clauses. On real data we use the 11-protein Sachs perturbation set. There we compare orientations against the literature consensus network, where FAST and LIST reported only slight gains over $\mathcal{I}$-FCI. PACER is the context point; it was reported to be the only method ranked in the top two on all five metrics, with no scalar value in the file. As a runtime stress test only, we run 50–100-gene subsets of CausalBench K562 (CausalBench). That paper warns that subsetting loses global context, so we make no biological-accuracy claim there.
Four checks decide the proposal. The first is exactness: zero disagreements with LIST under oracle tests on every instance LIST completes. Any disagreement indicates a bug or a flawed checker. The second is scaling: the number of added clauses and the runtime grow polynomially in $n$, which we test by fitting a log-log slope over $n \le 500$. If clause counts grow exponentially on sparse graphs, the core claim is false. The third is finite-sample robustness. Under real tests, $\mathcal{I}$-FCI output can be internally inconsistent, echoing the 5% satisfiability of strict faithfulness reported in the SAT-based work. We therefore report the rate of unsatisfiable queries and a minimal-relaxation fallback rather than hiding it. The fourth is the learned ordering, trained at $n \le 20$. It must give at least a 2× median speedup at $n = 200$ over the degree heuristic; otherwise we drop it. The exactness and scaling results stand on their own either way.
References
- Towards Completeness in Causal Discovery from Soft Interventions with Known Targets
- SAT-Based Causal Discovery under Weaker Assumptions
- Integer Programming for Causal Structure Learning in the Presence of Latent Variables
- Lazy Model Expansion: Interleaving Grounding with Search
- Bypassing the ASP Bottleneck: Hybrid Grounding by Splitting and Rewriting
- BQ-NCO: Bisimulation Quotienting for Efficient Neural Combinatorial Optimization
- PACER: Acyclic Causal Discovery from Large-scale Interventional Data
- SCOUT: Cyclic Causal Discovery Under Soft Interventions with Unknown Targets
- CausalBench: A Large-scale Benchmark for Network Inference from Single-cell Perturbation Data