Exactly Computing do-Shapley Values — ICML 2026 Reproduction

1Compress the coalition powerset

Interventions with the same basis and closure have one value. The Shapley sum can therefore be regrouped without approximation.

Class decomposition$$\phi_i=\sum_{c=1}^{r}\nu(c)w_i(c)$$

Exact graph audits	$d$	Max error
108	5–10	$5.88\times10^{-15}$

Every compressed answer was checked against the literal $2^d$ Shapley definition using independent random class values.

2Singletons diagnose identifiability

The appendix's Boolean ID recursion was implemented on directed and bidirected observed graphs.

Theorem 5.1 consequence$$\bigwedge_{j=1}^{d}\operatorname{ID}(\{j\},Y)\iff\bigwedge_{S\subseteq[d]}\operatorname{ID}(S,Y)$$

Random ADMGs	Coalition queries	Violations
600	8,204	0

406 graphs contained a non-identifiable coalition; the bow-arc negative control was also correctly rejected.

3Closed-set removal powers traversal

For every closed set generated in all 108 graph instances, each basis element was removed and closure was recomputed from scratch.

Audit	Failures
Lemma removal property	0
Algorithm 2 vs brute classes	0
Duplicate class representatives	0

Consequence: the traversal visits one closure per class instead of scanning the powerset.

The independent comparator enumerated every coalition, canonicalized its basis–closure pair, and required exact set equality with Algorithm 2's output.

4Every boundary query is distinct

Algorithm 3 was tested at budgets below, at, and above $r$ on 90 independent DAGs.

Observed invariant$$|\mathcal C|=\min(m,r)$$

Budget checks	Duplicate / count failures
450	0

Each graph was checked at five budgets spanning one query, fractional lattice coverage, exactly $r$, and beyond $r$.

Queue exhaustion: at $m\geq r$, traversal returned each class exactly once.

5Structural phase transition ★ HEADLINE

Reduced diagnostic on a $d=9$, $r=133$ graph; 160 trials per budget ratio.

Exact class computation, boundary discovery, reduced phase transition, and sparse graph scaling

Bottom: boundary sampling spends every query on a new class and switches to the exact sum at $m=r$.

At $m=r$: boundary exact in 160/160 trials; random coalitions exact in 0/160.

5aWhat was—and was not—rerun

$m/r$	Boundary error	Random diagnostic
0.25	0.0947	0.3989
0.50	0.0304	0.3968
0.75	0.00725	0.3364
1.00	0	0.3404

These are partial class sums, not doRegressionMSR. The named estimator superiority remains Figure-5/source evidence because no author implementation was linked.

6Sparse graphs compress dramatically

$d=12$ family	Median $r$	$r/2^d$
Chain	13	0.0032
Sparse shortcuts	155.5	0.0380
Moderate shortcuts	946.5	0.2311

This independently verifies the sparsity mechanism over 648 synthetic DAGs. It does not replace the paper's 156 learned TALENT structures, whose machine-readable graphs were not released.

Synthetic audit supports the mechanism; the real-data trend remains source-only.

7Reproducibility boundary

Exact: Claims 1, 3, and 4 directly rerun from pseudocode.
ID consequence: Claim 2 checked over 600 ADMGs.
Partial: Claim 5 named estimator and Claim 6 real-data endpoint remain source-only.
Compute: 16.6 s, CPU only, seed 18355.

Bottom line: four claims directly supported; two empirical claims honestly bounded.

CLASSES · LATTICES · REPRODUCTION