Computer programs as SCMs: extracting synthetic causal data from code repositories
Technical note,
While working on Axiom, an open-weight transformer for causal discovery, I've been researching ways to create structural causal models to produce synthetic data.
Synthetic SCMs can range in complexity from the very simple to the very complex. A simple linear model where the target y is generated based on a coefficient α times treatment x plus noise is an SCM. The same but squashed via a logistic function is an SCM. A neural network, with independent noise injected at each unit, is an SCM.
Aside from tricks and adjustments added to the model, the performance of a causal discovery tool on real-world generative processes relies on the diversity and quality of the data used to train it, and in particular, the similarity the synthetic SCMs have to the real world. This got me thinking about sources of such data that are cheap to collect, correct by construction, and come with their own ground-truth causal graph.
This is easier said than done, because real-world data rarely comes with a known causal graph, and much of it is proprietary anyway. But if we zoom out a bit, and think of processes that mirror said real-world systems, program code comes to mind.
Consider a function in code. It has inputs, it has outputs. Its outputs change as inputs change, depending on its own internal logic. The logic may be deterministic, or stochastic to some degree. If we have access to the internals of the function, we can review exactly what is happening, and sketch the ground-truth causal graph exactly.
Take this function, for example:
def checkout_total(unit_price, quantity, is_member):
subtotal = unit_price * quantity
discount = 0.1 * subtotal if is_member else 0.0
shipping = 0.0 if subtotal >= 50 else 4.99
tax = 0.2 * (subtotal - discount)
return subtotal - discount + shipping + taxReading it line by line gives us the causal graph directly. We have three inputs: unit_price, quantity and is_member. Price and quantity both cause subtotal. subtotal causes the discount, but only for members: is_member switches the effect on if true. subtotal also causes shipping, through a threshold. tax is caused by both the subtotal and the discount, and the final total is caused by the subtotal, discount, shipping and tax together.
Hand-reviewing functions to find their ground-truth causal graph is tedious and off the table if you want to train on vast amounts of data. Can you find the data you need for training automatically? This wasn't immediately apparent to me, but yes, you can, via a few mechanisms: parsing, instrumented execution, and latent projection.
To parse the AST (in Python) and return a causal graph, we can use a function. Note that the following illustrative function is by no means complete; there are several issues: it doesn't handle all the ways Python can assign values, and it ignores control flow entirely.
import ast
def causal_graph(source):
func = ast.parse(source).body[0]
edges = set()
for node in ast.walk(func):
if isinstance(node, ast.Assign):
targets = [t.id for t in node.targets if isinstance(t, ast.Name)]
elif isinstance(node, ast.Return):
targets = ["output"]
else:
continue
causes = {n.id for n in ast.walk(node.value) if isinstance(n, ast.Name)}
edges |= {(cause, target) for cause in causes for target in targets}
return edgesWe now have a graph, but this is not enough by itself. A graph is the training label, but we also need the training data. To get that, you can run the function many times on random inputs and record every variable on every run.
This raises two issues. First, suppose we draw unit_price between 10 and 20 and quantity between 5 and 10. The subtotal is then always at least 50. Shipping in this case is always 0, yet our graph has an edge from subtotal to shipping. No algorithm can recover this edge from the data; the graph contains an edge whose effect never shows up for the input ranges we chose to generate training data from.
To fix this, we can (automatically) check every edge in the graph against the data we actually generated. For an edge from a parent to a child node, we take two runs, copy the parent's value from one run into the other, keep the child's other causes fixed, and recompute the child. If the child doesn't change across many such pairs, the edge must have no effect for these input ranges, and we drop it. This is a statistical check, so an effect confined to a very rare region of the inputs can slip through. With the narrow ranges, this removes subtotal → shipping and shipping → output and keeps the other edges intact.
The second issue has to do with coverage. With the solution so far, we assume that real-world data would record every variable. In practice, that never happens; a process might result in a dataset with a handful of columns, even though the underlying causal structure has more. So we hide some of the variables: the function still computes them, but we leave their columns out of any training data. This makes the problem setting more realistic, but the ground-truth graph must also change (we can't predict graphs with more nodes than the data covers). We can turn to the idea of latent projection, from Verma and Pearl (1990) to address this. Using two rules, we can turn the full graph into a correct graph over the visible columns:
- If a chain of arrows runs from one visible variable to another through hidden variables only, draw a direct arrow between them. Hiding
subtotal, for example, givesunit_price → output(among other edges). - If a hidden variable has such chains to two visible variables, mark the pair as confounded: related through a hidden common cause. For example, with wide enough inputs, hiding
subtotalresults indiscount ↔ shipping(and a few other pairs).
Two caveats apply here. First, the ↔ rule assumes each hidden variable carries its own noise. Second, the projected graph can contain both A → B and A ↔ B for the same pair, which may or may not be an issue depending on the type of graph you aim to produce.
All in all, the components in this note all point to it being possible to (automatically) source and preprocess training data for causal discovery from open source code repositories. If we assume that covering specialised code across a variety of fields (manufacturing, science, biology, you name it) yields signals relevant to real-world discovery tasks, we could have a scalable source that could help build the next generation of causal AI.