---
name: checked-work-graph
description: Use when coordinating a large project with shared dependencies, explicit task contracts, checkable outputs, and repeated worker handoffs. Maintain a versioned work graph in which submitted artifacts carry evidence, unresolved obligations remain visible, and downstream work is rechecked when dependencies change.
version: 1.0.0
author: Srijan Shukla
license: MIT
metadata:
  tags: [agents, orchestration, dependency-graph, verification, migrations]
---

# Checked Work Graph

Break a large job into dependency-linked tasks with explicit contracts. Accept each result only after independent checks show that downstream work can build on it at the stated level of confidence.

A checked work graph has four distinct objects:

- **Node:** a versioned contract for one piece of work.
- **Edge:** a dependency on another node's contract or artifact.
- **Submission:** a candidate artifact for a node, with the exact dependency versions it used.
- **Check:** evidence that the submission satisfies its contract.

The graph is the durable source of project state. Chat can help workers reason, but it does not decide what is complete.

This pattern is adapted from Prove2Me's theorem-dependency workflow. In formal mathematics, a proof checker can provide unusually strong guarantees. In software, tests, builds, static analysis, review, and production observations provide narrower evidence. Record that distinction instead of calling every passing check a proof.

## When to use

Use a checked work graph when:

- The project contains shared blockers or reusable intermediate results.
- Several workers can proceed against stable contracts.
- Outputs can be checked independently of the worker that produced them.
- Work will span many context windows, sessions, or handoffs.
- A dependency change should trigger targeted rechecking downstream.

Good examples include large API migrations, language or framework upgrades, monolith decomposition, database migrations, compiler work, data pipelines, hardware verification, reproducible research, and formal proof development.

Use a checklist for small linear work. Use an experiment log when the goal is still unclear. A graph adds little when one person can finish the task in an afternoon or when taste and discovery dominate the work.

## Example: a large software migration

A migration from an old client library to a new versioned API might start as:

```text
Complete migration
├── Define client contract v2
├── Implement client v2
├── Migrate service A against contract v2
├── Migrate service B against contract v2
├── Migrate service C against contract v2
└── Pass system integration and rollout checks
```

The service migrations do not need to wait for the final client implementation. Workers can code against contract v2 and test with a contract fixture. Those results remain **conditional** because a fixture cannot establish compatibility with the finished client.

When the real client artifact arrives, the service nodes become ready for verification. Their integration checks run against the recorded client revision. The root migration becomes verified only after the required services, integration suite, deployment checks, and rollback checks pass together.

If contract v2 changes, create contract v3. Do not silently edit v2. Mark submissions built against v2 as stale or keep them pinned to v2 until they are migrated and rechecked.

## Store durable project state

Use the project's existing database or task system if it can represent the records below. A simple file-backed layout is enough to start:

```text
work-graph/
  goal.md
  graph.json
  nodes/
    <node-id>.md
  submissions/
    <submission-id>.json
  evidence/
    <submission-id>/
```

`goal.md` records the requested outcome, scope exclusions, root acceptance checks, and approval authority. `graph.json` records nodes, dependency edges, selected submissions, versions, states, and invalidations. Node files contain contracts and bounded working notes. Evidence directories contain logs and reports needed to reproduce a verdict.

Keep credentials, personal data, and large raw transcripts out of the graph. A graph entry cannot authorize deployment, publication, spending, access changes, or other consequential actions.

Use one coordinator or a transactional service to update the authoritative graph. Concurrent code writers should use isolated workspaces. Workers propose graph changes; they do not silently rewrite shared state.

## Define a node contract

Every node should contain:

- Stable node ID and contract version.
- Expected artifact and allowed write scope.
- Preconditions, dependencies, and required artifact versions.
- Functional requirements and explicit non-goals.
- Acceptance checks and their verification level.
- Required integration or human-review gates.
- Current state, selected submission, and owner or lease.

A useful contract is specific enough that a checker can reject an artifact. If the acceptance rule is "looks good," the node is not ready for independent execution.

Contracts can depend on interfaces rather than implementations. Record when a worker used a mock, fixture, stub, or unverified assumption. Those are unresolved obligations, not completed dependencies.

## Record submissions separately

A submission should contain:

- Submission ID and target node/contract version.
- Artifact paths plus an immutable identity such as a commit or content hash.
- Dependency versions and artifact revisions actually used.
- Mocks, placeholders, assumptions, and unresolved obligations.
- Check commands, working directory, toolchain, environment, exit codes, and bounded output.
- Verdict, checker identity, and check time.

Keep multiple submissions for a node. Selecting one does not erase the others. A rejected attempt should retain a short failure note and useful evidence so the next worker does not repeat it.

Alternative submissions may depend on different children:

```text
Node A
  submission s1 requires B AND C
  submission s2 requires D
```

A can complete through s1 or s2. Do not flatten the alternatives into a false requirement for B, C, and D. Pin the selected submission so scheduling and completion use the same dependency set.

Reject cycles in the completion graph. Extract a shared interface, introduce a combined integration node, or revise the decomposition. Do not hide a cycle by marking one side complete.

## Use explicit states

| State | Meaning |
| --- | --- |
| open | Available for work; no accepted current submission. |
| working | A worker holds the node or a time-bounded lease. |
| submitted | An artifact exists and awaits independent checks. |
| conditional | Local checks passed with recorded unresolved obligations. |
| ready-for-verification | Required dependency artifacts exist at the pinned versions. |
| verified | The selected artifact passed the contract's required checks against recorded inputs. |
| stale | A dependency or contract change invalidated existing evidence. |
| blocked | Work cannot proceed; the blocker and required action are recorded. |

For software, completing dependencies usually moves a parent to `ready-for-verification`. Run its integration checks before moving it to `verified`. Automatic completion propagation is appropriate only when the checker establishes the composition itself.

## Run the loop

1. Read the root goal, current graph, node contracts, selected submissions, and relevant failure notes.
2. Find feasible unresolved nodes. Prefer work that unblocks selected parent submissions, adjusted for effort, risk, and scarce expertise.
3. Claim one bounded node with a lease, workspace, and write scope.
4. Give the worker the contract version, pinned dependencies, acceptance checks, artifact destination, and known failed attempts.
5. Require a submission record with artifacts and evidence. The worker may propose new nodes or contract revisions, but cannot make them authoritative.
6. Run the required checks independently. A trusted test runner can provide independence; a second model is not always necessary.
7. Mark the submission verified, conditional, rejected, blocked, or stale according to the evidence.
8. Update affected parents and run any newly enabled integration checks.
9. Repeat until the root contract passes or the graph records a specific blocker.

A useful scheduling signal is **closability**: how many selected ancestor submissions would have their remaining dependency obligations discharged by completing a leaf. In engineering projects this often means the ancestors become ready for verification, not verified. Closability also ignores task duration, so it should inform priority rather than control it.

## Checks need levels

Record what a check can establish:

| Level | Example | Claim supported |
| --- | --- | --- |
| Formal | Proof assistant or model checker | Property follows from formal assumptions. |
| Deterministic | Compiler, schema validator, reproducible transformation | Artifact satisfies the encoded rule. |
| Test-backed | Unit, integration, compatibility, or end-to-end tests | Tested behavior passed under recorded conditions. |
| Observational | Benchmark, canary, production telemetry | Measured behavior met a threshold during the observation. |
| Human-reviewed | Design, security, legal, editorial, or visual review | Named reviewer accepted the artifact within a stated scope. |

Do not promote evidence to a stronger level than the checker supports. Passing unit tests against mocks does not verify a production integration. Human review does not become independent because a worker wrote "reviewed" in its own report.

## Handle revisions and invalidation

Never edit a depended-on contract without creating a new version. Record why it changed and which nodes need migration or rechecking.

When a selected dependency artifact changes:

1. Find submissions that consumed the old revision.
2. Decide whether their contract or checks establish safe substitution.
3. Mark unsupported evidence stale.
4. Re-run only the required downstream checks.
5. Preserve the earlier evidence with its original snapshot.

Formal substitution may allow reuse without broad rechecking. Test-backed software usually requires affected integration checks. The graph should make this difference visible.

On restart, load the graph rather than reconstructing progress from chat. Check expired leases, missing artifacts, inconsistent selections, stale evidence, and unrecorded working-tree changes before assigning new work.

## Finish the root

Mark the root verified only when:

- A selected submission satisfies the current root contract.
- Its transitive obligations are discharged at recorded versions.
- Required integration, rollout, rollback, or end-to-end checks passed.
- Evidence and artifacts are present and identify their inputs.
- Required human approvals are recorded.
- Residual risks are explicit.

Report the verification level, artifact paths, commands run, versions checked, and known limits. If the root remains conditional or blocked, say so.

## Common mistakes

- Treating a worker's success message as verification.
- Treating a mock as the completed dependency.
- Letting workers weaken acceptance criteria to fit their output.
- Marking every ancestor verified after one leaf passes tests.
- Mixing dependencies from alternative submissions.
- Treating closability as a shortest-path calculation.
- Calling test-backed evidence a proof.
- Changing a contract without invalidating consumers.
- Keeping the only record of status or failure inside chat.
- Using the graph for exploratory work before contracts can be stated.

## Sources

- [Anthropic: Formalizing Fermat's Last Theorem](https://www.anthropic.com/research/formalizing-fermats-last-theorem)
- [Prove2Me workspace and agent documentation](https://github.com/prove2me/prove2me_workspace)
- [Proof submissions and reductions](https://github.com/prove2me/prove2me_workspace/blob/main/references/prove.md)
- [Mission frontier and closability](https://github.com/prove2me/prove2me_workspace/blob/main/references/missions.md)

The name, engineering states, migration example, file layout, and invalidation rules above are recommendations for applying the pattern. They are not claims about Prove2Me's hosted implementation.