acceptodds
Withdrawn from ICLR 2027

Certifying Persistent Agent Workflows with Sharp Risk Bounds

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

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.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
AI agents, multi-agent systems, workflow safety, safety certification, persistent state

Reviews

Among:
Shape:
1234this paper, Bottom 2%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.33 over 3 reviews, above 2% of the others.
Reviewer_CqY8OpenReview ↗
Rating
1
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

The paper looks at setups where several AI agents work together through shared state. Each agent does something it is allowed to do but together they can still cause something unauthorized like deploying to the wrong place. The authors measure how often each individual step happens and use a linear program to get a worst-case bound on how often the bad outcome can happen. They test thiis on three synthetic workflows they built themselves.

Critical strengths

I believe the problem posed in the paper is crucial and worth studying. The paper is fairly transparent about its assumptions and includes cases where the method fails.

Critical weaknesses
  • The paper is hard to read, with a lot of custom terms. I had a hard time seeing what's new. The core math seems to be a known technique (probabilistic satisfiability) applied to agents.
  • The setup feels contrived. In every example the real issue is a missing authorization check at the end, and the author’s own simple fix brings unsafe outcomes to zero. It is not clear why someone would want a risk bound instead of just adding the check.
  • The method assumes you already know every possible route to a bad outcome. If you know that, you could probably block those routes directly.
  • The experiments are small and synthetic. Onene model and ~50-60 test cases per study and workflows built to fail on purpose. So it mostly confirms the math works out and not that the method helps on real practical agents.
Questions for authors

What's the main new contribution beyond the existing LP technique? When would someone use this instead of just adding the missing check? 
 How would you get a complete list of routes in a real agent system? Could you test this on a real agent benchmark?

Reviewer_TfBdOpenReview ↗
Rating
1
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

The paper formulates unsafe-completion risk in persistent multi-agent workflows as a probabilistic-satisfiability linear program. It combines declared workflow structure with replay-derived event bounds and replay-to-live allowances, yielding a sharp conditional risk bound whose dual weights identify important events and unsafe routes. The framework is evaluated on synthetic workflows.

Critical strengths

The paper addresses an important safety issue in multi-agent workflows and provides a systematic way to estimate unsafe-completion risk.

Critical weaknesses

The proposed framework largely builds on established probabilistic-satisfiability and optimization techniques, without clearly demonstrating what fundamentally new insights or practical capabilities their adaptation to agent workflows provides.

The experiments rely heavily on human constructed workflows and predefined unsafe routes. Its agent behavior largely follows some generator guided evidence. These settings do not sufficiently demonstrate the framework's effectiveness in handling complex or real agent interactions, limiting the support for its broader certification claims.

Questions for authors
  1. What new insights into agent systems or practical certification capabilities does the proposed framework offer beyond existing probabilistic-satisfiability methods?

  2. How can the authors demonstrate that the framework remains effective when agent behavior is not largely determined by the experimental construction?

  3. Can the authors clarify exactly which workflow configurations are being certified and how the reported risk bounds relate to the observed unsafe completion rates? The current presentation makes the paper difficult to follow.

Reviewer_vdrdOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

The paper develops worst-case risk certificates and proofs for persistent agent workflows using probability bounds on declared events. The core motivation is that agents can, when working together, do unallowed tasks even when individual agents do permitted tasks. A finite-history moment problem yields an LP certificate, with fractional-cover and flow formulations for structured cases.

The contributions of the work are, as the author declared,:

  • A sharp bound for agent workflows from partial measurements.
  • An operational certification loop.
  • Controlled end-to-end validation.
Critical strengths
  1. The distinction between empirical observations & a certificate over an explicitly declared workflow is valuable and clearly motivated.
  2. The mathematical formulation is interpretable.
  3. The manuscript states its coverage and transport assumptions and includes negative controls where certification fails.
  4. It's an interesting problem to tackle with & think.
Critical weaknesses
  1. The practical novelty still needs sharper positioning. The paper acknowledges probabilistic satisfiability and moment/LP formulations. The contribution for me reads as to show the operational composition for agent workflows.
  2. The experiments provide very limited evidence beyond closed, planted authorization failures. Missing-role and missing-comparison fixtures are useful sanity checks, but here they do not establish performance when model behavior is variable, the workflow abstraction is imperfect, or deployment changes action probabilities.
  3. The price of certification is not fully characterized. For Sensitive Release, the certificate is substantially above the known risk, and direct held-out outcome bounds are tighter. This makes observation cost, sample allocation, and the availability of outcome labels central.
  4. Coverage is the key deployment bottleneck. A concrete executable abstraction/conformance example would help show how users can conservatively cover real unsafe executions without enumerating a closed fixture by hand.
Questions for authors
  • Under equal observation cost, when do precursor certificates outperform direct outcome estimation?
  • Can you demonstrate a shift that changes behavior and quantify the resulting transport penalty?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.