Certifying Persistent Agent Workflows with Sharp Risk Bounds

Persistent state can let separately launched agents complete an action nobody authorized, even when each agent’s local action is permitted. Controlled replay, which reruns one agent on a stored input, bounds how often individual precursor events occur but not how they combine after handoffs. We show that the sharpest bound on unsafe completion is a probabilistic-satisfiability linear program over the executions a declared workflow allows, with event bounds that include allowances for the change from replay to live execution. Without workflow structure, the same event bounds allow risk one; with it, the optimal weights form a route cover that identifies which measurements and routes limit the bound and guides protected fields and path controls. In synthetic multi-agent workflows, persistent handoffs composed locally permitted actions into unsafe completions that isolated agents never produced, and every certificate frozen before outcomes bounded its held-out unsafe rate, including across a paired change of input format. Because these workflows fix the true risk by design, they validate the procedure end to end against a known answer. The guarantee requires justified live event bounds and a workflow model that includes every real unsafe route.