Why don’t locally valid steps guarantee a viable workflow?
An AI-generated workflow can pass every check it is given and still be impossible to finish.
The tasks are valid. The connections between them are allowed. Every step clears the rules we wrote for steps. And yet somewhere during construction, one accepted addition quietly removes the last route to a workflow that satisfies its own requirements. Nothing reports an error, because nothing was, locally, an error.
That possibility is the subject of our latest paper, Proof-Carrying Streamed Workflow Graphs. It is an uncomfortable idea for anyone building business automation, because checking the parts feels like it ought to give you confidence in the whole. Why would a sequence of individually acceptable steps arrive somewhere unacceptable?
The same change, two different outcomes
The question came out of our work on the Opus Work Knowledge Graph, which organises reusable tasks alongside the context and evidence they carry. Two workflows assembled from the same tasks can still hold different obligations.
Take a supplier-payment workflow with two routes to approval: the standard path, and an authorised exception review. In one context, the authorisation that the exception route depends on can be supplied. In another, it cannot.
Now suppose an addition permanently closes the standard route. Suppose it passes every local check, and that no later addition can reopen the route or loosen the authorisation constraint. The first workflow is fine — it finishes through exception review. The second has just lost its only acceptable way forward.
The proposed change is identical in both cases. Its consequences are not. So the question worth asking is broader than whether a new task or connection is valid on its own terms: after we accept this change, can we still finish building an acceptable workflow?
Carry the evidence alongside the workflow
The paper calls that property completion viability. A partially built workflow is viable when some finite sequence of further additions can still produce an acceptable finished one.
The approach we propose carries a certificate alongside the construction state. The certificate stands for the future additions known to preserve viability, and every admitted addition updates both the workflow and its certificate. Begin with a sound, non-empty certificate, hold those properties through checked updates, and you have established something concrete: an acceptable completion remains possible after every addition you have accepted.
That reframes the engineering problem usefully. Rather than asking a generating agent to reassure us that its proposal makes sense, we can ask what evidence would justify accepting it.
What does the system need to remember?
The research also pins down what exact incremental checking demands of a system’s memory. Two construction states have to be kept distinct whenever the same future additions could leave one viable and the other unable to finish. A shared “viable” label is not enough when the remaining possibilities behind it differ.
That is a sharp test for any proposed summary of workflow state, ours included. Does the summary preserve the distinctions the next decision depends on, or has it already discarded something that will matter later?
Why this matters for Opus
Opus is built around reusable agents, integrations, code, human tasks and sub-workflows, with versioning, permissions and policy evaluation around them. That is what lets teams assemble and revise automation without rebuilding every component from scratch — and it is precisely why accepting a change deserves to be treated as an engineering problem in its own right. A proposed improvement should be judged against the obligations of the workflow it changes, not only the component it introduces.
The result has clear boundaries, and they are worth stating plainly. It preserves the possibility of completing construction — not eventual completion, and not successful execution. It does not establish that checking a certificate is necessarily faster than recomputing viability from scratch in all cases.
What it does give us is a more precise decision. Before committing a change to a workflow, ask what supports the claim that the remaining work can still be completed.
That is a stronger basis for building automation than finding the dead end after everything has passed its own checks.