Content-Addressed Provenance Graphs for Derived Outputs

A directory listing at the end of an analysis contains files and no history. Which script wrote results/figure3.png, from which input, with which parameter value, under which environment — none of that survives in the filesystem unless something recorded it at the moment the file was written. Provenance is that record, and the design question is what to key it on.

Keying on names fails because names are reused and because a name does not identify content. Keying on timestamps fails because timestamps are unreliable across copies, restores, and filesystems with coarse granularity. Keying on content hashes is the design that survives all three, and it is the same design that underlies Git’s object store, container image digests, and every serious artifact cache.

The node is a hash of everything that determines the output

The invariant is simple to state: a step’s identity is a cryptographic digest over the complete description of that step, and the output is filed under that identity. Two executions with the same identity are, by construction, executions of the same computation; two executions with different identities are different computations even if they wrote to the same path.

“Complete description” is where the engineering lives. It has to include:

• the command or function to run, exactly as specified, with its arguments;
• the digests of every input, including inputs discovered at run time rather than declared;
• the values of parameters, including those that come from configuration files and those that come from the command line;
• the identity of the environment — an image digest, or a lockfile digest plus interpreter identification;
• the code, distinguished from the command line: a script’s contents, and the contents of every module it imports.

The last item is the one that gets omitted and the one that produces the most confusing failures. Hashing the top-level script but not its imports means that editing a helper module changes behaviour while the recorded identity stays fixed, so a cached output is silently reused for an input that has changed. Recording imported module digests turns that into a cache miss, which is correct.

The counter-problem is instability. If the identity includes everything reachable, incidental changes — a formatting-only edit to a module that is imported but whose changed function is never called, a reordered dictionary in a config file — invalidate the cache and force re-execution. Content addressing does not distinguish semantically irrelevant changes from relevant ones, and no general mechanism does. The practical compromise is to hash at the granularity of the unit that changes: individual files rather than whole directories, individual functions where the tooling supports it.

Graph construction and the shape of the record

Each execution consumes input identities and produces output identities. The set of all executions over a project forms a directed acyclic graph in which edges point from input to consumer, with each node carrying the command, the environment identity, and the mapping from input name to digest.

A minimal implementation is a few dozen lines: compute the hash, look for a directory with that name, and skip the work or perform it.

import hashlib, json, pathlib, subprocess, sys

def digest(path):
    h = hashlib.sha256()
    with open(path, "rb") as f:
        for chunk in iter(lambda: f.read(1 << 20), b""):  # 1 MiB blocks
            h.update(chunk)
    return h.hexdigest()

def step_id(cmd, inputs, params, env):
    payload = json.dumps({"cmd": cmd, "params": params, "env": env,
                          "in": {k: digest(v) for k, v in inputs.items()}},
                         sort_keys=True, separators=(",", ":"))
    return hashlib.sha256(payload.encode()).hexdigest()

key = step_id(["python", "fit.py"], {"data": "data/raw.csv"},
              {"rate": 0.05}, {"image": "sha256:3f9c..."})
out = pathlib.Path("cache") / key
if not out.exists():
    out.mkdir(parents=True)
    subprocess.run([sys.executable, "fit.py", "--out", str(out)], check=True)
print(out)

The canonical JSON form — sorted keys, no insignificant whitespace — is what makes the digest stable across runs and across machines; a JSON serialization with implementation-defined key order would produce different digests for the same logical content.

The env field above is a digest rather than a description. Recording the full environment inline would make each node large and would duplicate the same information across thousands of nodes; recording its digest and storing the description once, under that digest, is the same indirection a content-addressed store uses for file contents.

Why this design, and what the alternatives cost

Three alternatives are common, and each fails in a specific way.

Recording a run log. A log lists commands in order with timestamps. It answers “what did I run at 14:32” and not “which runs produced this file”. Reconstructing the second requires replaying timestamps against filesystem mtimes, which breaks for files copied, restored, or produced by a tool that does not update mtimes. Logs are append-only narrative; provenance needs an index from output to producer.

Recording versions in the file itself. Embedding a provenance record in each output — a comment in a CSV header, a metadata field in an image — works for single-file artifacts and fails for anything whose format has no place to put it. It also duplicates the code and environment description in every output, and it cannot express the graph, only the immediate parent.

Declaring a pipeline and trusting it. A workflow definition states what depends on what. It describes intent, not what ran. A step that was skipped, a manual intervention, a run with an override argument — none are visible in the declared graph, and the declared graph is what a reader will find when they look for the record.

Content addressing is not free either. It costs a hashing pass over inputs, which for large datasets is a sequential read; hashing a terabyte at a few hundred megabytes per second is a matter of minutes, and doing it on every run is a real expense. It costs storage, because intermediate artifacts are retained under content keys rather than overwritten. And it costs discipline, because an input read through a mechanism the tooling does not intercept — a database query, a network fetch, a file opened by a library that the instrumentation does not see — escapes the record entirely.

The storage cost is mitigated by deduplication, which is the reason content addressing and caches co-occur: two steps with the same input digest share the stored bytes, and the marginal cost of an additional node is often near zero.

Provenance that is checked rather than asserted

A record that is written alongside execution and never verified against the produced artifact decays into a claim. The countermeasure is to hash the outputs too and to store the output digest in the node.

With outputs hashed, three checks become possible. Re-execution yields the same output digest, which is the strongest form of computational reproduction and is achievable only for deterministic steps. The stored output still matches its digest, which detects bit rot, partial writes, and accidental modification. The graph is consistent: every input digest appearing as an edge source either exists in the store or is an external input named in the record, and no node’s inputs are missing.

The middle check is the one that catches the common contamination: a figure regenerated by hand, a CSV edited in a spreadsheet and saved back to its path. Once that happens the file at the path and the record of how it was made disagree, and without hashes the disagreement is invisible.

Determinism is the boundary condition. Steps that depend on a random seed produce the same digest only if the seed and the generator configuration are part of the node identity, which is why Seeds, Generator State, and Reproducible Random Streams treats the generator configuration as an input rather than as a detail of the code. Steps that depend on thread count, wall clock, or hardware floating-point behaviour produce digests that differ across machines, and for those the node has to record the observed divergence and the tolerance under which it is accepted, which Conditioning, Tolerance, and the Digits a Reproduction Can Demand develops.

Where the record has to live

The store has to outlive the working directory, because a provenance record kept only inside a checkout disappears with the checkout. Three placements are common.

Beside the code, in version control. The graph is serialized as text and committed. Diffs show the analysis changing over time, review is possible, and the record travels with the repository. The cost is that large output digests and long parameter sets produce unwieldy diffs, and that committing a graph after every run is a discipline that fails silently.

In a remote artifact store. Outputs and their nodes are pushed to a store keyed by digest, and the code repository holds only the entry points. This scales to large artifacts and makes the record inseparable from the bytes it describes, at the cost of a dependency on the store’s continued operation.

In an archival repository with a persistent identifier. The record is deposited as a dataset with a DOI, which gives it a citation and a commitment to persistence that a working directory does not. The FAIR principles state the case: findable, accessible, interoperable, reusable artifacts require persistent identifiers and rich metadata, and a provenance graph with output digests is exactly such metadata. The practical failure mode is granularity — a deposited snapshot is a point in time, and the graph continues to evolve afterwards.

The choice is not exclusive; the common arrangement commits a small manifest, pushes artifacts to a store, and deposits a tagged snapshot. What matters is that the graph is durable and that the pointers in it — image digests, package hashes, input checksums — resolve to bytes that still exist. A record that names a mutable tag or an unversioned URL has recorded an intention rather than an identity, and Bit Rot, Link Rot, and Replaying an Analysis Years Later takes up what can still be recovered when those pointers stop resolving.