- Rating
- 2
- Confidence
- 3
- Informativeness
- 3
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper proposes Agentic Execution Petri Nets (AEPNs), a deterministic execution layer placed between an LLM agent and its tools. Operational facts such as approvals, budgets, capabilities, and locks are represented as marks, and consequential actions consume the corresponding marks when transitions fire. The paper combines this representation with supervisory control to synthesize a maximally permissive safe supervisor.
The main example is an autonomous deployment agent that must complete CI and security checks, obtain human approval, and then deploy. The paper presents a memory lower bound for enforcing one-approval-per-execution, a safety-transfer theorem under four assumptions, and experiments involving indirect prompt injections against several OpenAI models. The central empirical result is that models often still propose unauthorized deployments under attack, but the AEPN kernel prevents these actions from executing. The paper also evaluates structural constraints on ToolSandbox.
Critical strengths
The paper makes an important distinction between semantic defenses and operational enforcement. Detecting whether text is malicious is fundamentally different from determining whether an action is authorized in the current execution state. Treating the LLM as an untrusted proposer and placing a deterministic reference monitor below it is a sound and practically relevant direction.
Representing approvals and budgets as consumable marks is intuitive and well suited to preventing replay and enforcing resource constraints. The deployment experiments clearly illustrate the value of this design: prompt injection can successfully alter the model’s proposed behavior without causing the unauthorized action to execute. The paper is also commendably explicit about the assumptions needed to transfer formal guarantees to a concrete runtime, particularly complete mediation and correct grounding.
The work is informative and integrates theory, system design, and live-agent experiments. Even where the underlying formal machinery is classical, its application to LLM-agent execution security is useful and timely.
Critical weaknesses
1. The lower bound establishes the need for trusted state, not the necessity of Petri nets
The paper overstates what the memory lower bound establishes. The result shows that consumable authorization requires trusted operational state, or an equivalent count of prior approvals and executions. It does not establish that Petri nets are necessary: a transactional counter, immutable execution log, one-time capability, or hand-written stateful monitor can enforce the same property.
The related claim that one ordinary Petri-net place “attains the bound exactly” also requires clarification. The finite-horizon construction uses a saturated counter, whereas an ordinary unbounded place does not automatically saturate at .
2. The novelty relative to prior Petri-net work is insufficiently isolated
Consumable marks, place invariants, monitor places, controllable and uncontrollable transitions, and maximally permissive supervisory control are established techniques. The paper cites several Petri-net-based agent and autonomous-system frameworks, but does not provide a sufficiently detailed comparison establishing which runtime enforcement or synthesis capabilities are genuinely new.
The contribution appears closer to a valuable integration of classical Petri-net supervisory control into LLM-agent security than to a genuinely new formalism. The paper should more clearly distinguish its system-level and empirical contributions from established Petri-net and supervisory-control machinery.
3. Maximal permissiveness does not imply preservation of end-to-end agent capability
The paper does not adequately evaluate the capability cost of intervention. Maximal permissiveness holds only relative to the predefined net, action vocabulary, abstraction, and forbidden-state specification. It does not imply preservation of the closed-loop agent’s real-world capability.
A safe but unmodeled recovery strategy or tool composition may be rejected exactly like an unsafe action. Refusals also change the model’s subsequent trajectory, consume interaction budget, and may cause repeated calls or premature termination. The paper’s own ablation, where task completion falls from 0.84 to 0.39 under a less informative refusal, demonstrates that utility is sensitive to intervention. Since the experiments largely encode the intended workflow directly into the net, they do not establish whether stronger or more open-ended agents retain their capability ceiling.
Questions for authors
-
What does Theorem 1 establish beyond the need for trusted operational state? Can the authors provide a standard Petri-net construction showing how one place exactly realizes the finite-horizon saturated-state bound?
-
Is AEPN intended as a genuinely new formalism or as an agent-security-specific instantiation of colored Petri nets and classical supervisory control? What functionality is absent from the closest prior Petri-net-based agent systems?
-
What happens when an agent discovers a safe and useful strategy that has no corresponding transition or path in the predefined net? How does the framework distinguish unsafe behavior from behavior that was simply not anticipated by the model designer?
-
Can the authors evaluate capability preservation on clean, open-ended tasks with multiple safe workflows, dynamic failures, and fixed interaction budgets? A comparison against a hand-written stateful workflow monitor, and across plan-then-execute and ReAct-style agents, would help isolate the value and scope of the Petri-net formulation.
4 comments
Response to V4n5 (2/4): one place does not attain the bound; the two-place construction, three further errors we found and corrected, and what we checked
W1, second paragraph, and Q1, second part. "an ordinary unbounded place does not automatically saturate at ⌊H/2⌋", and: "Can the authors provide a standard Petri-net construction showing how one place exactly realizes the finite-horizon saturated-state bound?"
A. You are right: one place does not. Let . The place we meant is Corollary 2's counter. It enforces , but along it takes values. Two places attain the bound. Take with and a complement with . Let move a mark from to , and move it back. Add , also labelled , with a self-loop of weight on and no other arc. Then is the saturating counter. Without the net refuses the th approval, which allows, so that net is not transparent. The construction is therefore a labelled net with a weighted self-loop, not one ordinary place. The abstract and contribution (i) now say "two places" (p. 1, l. 020–021; p. 2, l. 091–092), and §4.1 and App K give the construction (p. 5, l. 251–257; p. 38, l. 2016–2032).
Checking your two points, and then re-checking the rest of the result, turned up three errors of ours, all corrected. Theorem 1's statement had the attaining monitor store \min\\{\\#\mathsf{ap}-\\#\mathsf{ex},K\\}, which the saturating counter does not hold. App K's proof said " equals the surplus whenever the surplus is at most ", which is false for ; a corrected argument reaches the same conclusion. And our -authority count was not what places hold; the bound is now , with its tightness not shown. We are grateful that your question led us to these.
What we checked, and what we did not. By enumerating all words over of length at most :
| Claim | Checked? |
|---|---|
| The saturating counter enforces the rule, with states | yes, |
| One place enforces it and takes values | yes, same range |
| The two-place net enforces it, with reachable markings | yes, same range |
| Without the net refuses | yes, same range |
| refutes both old sentences | yes, |
| The corrected App K argument | yes, same range |
| The fooling set, and counters saturating at | yes, |
| The place invariant, and that follows the counter step by step | no; App K argues both |
| That places, one per authority, enforce the policy | no; it follows from Corollary 2 |
The check script is in the revised supplementary material. Apart from these checks we ran nothing new.
Response to V4n5 (3/4): AEPN is an instantiation of colored Petri nets and classical supervisory control; the combination is what we claim
W2 and Q2, first question. "The contribution appears closer to a valuable integration of classical Petri-net supervisory control into LLM-agent security than to a genuinely new formalism." And: "Is AEPN intended as a genuinely new formalism or as an agent-security-specific instantiation of colored Petri nets and classical supervisory control?"
A. It is an instantiation, and thank you for putting the question so plainly. We agree, and the paper should have said so in those words; the revised PDF now does, in §7 (p. 10, l. 515–516). Definition 1's first eight components are a colored Petri net (l. 141). Labels, controllability, observability, monitor places (l. 263–266) and Theorem 2 (l. 291) are classical, and §7 says the lineage is classical (l. 474). We claim only the combination (§7, l. 483–486):
- run-time admission of model proposals in the tool-call path;
- the model as an untrusted proposer under indirect injection;
- consumable authority;
- uncontrollable events with supervisor synthesis;
- a transfer theorem with each of A1–A4 shown necessary (Theorem 3, Proposition 1);
- live attacks, in which the models are hijacked yet no unauthorized deployment executes (E2, E2b).
Read for agent guards, Theorem 1 and Corollary 1 then say this: a stateless guard is unsafe or useless, and one with fewer than states is unsafe or over-restrictive. That holds at any detector accuracy. Empirically, E1 finds that the defect is in the actuator, and six modules cover all 129 ToolSandbox scenarios (E5).
Q2, second question. "What functionality is absent from the closest prior Petri-net-based agent systems?"
A. The paper does not answer this system by system, and it should. The five Petri-net-based agent and autonomous-system frameworks we cite (l. 482–483) appear only in a list, and we would rather not characterize each of them from memory in this reply. We do not claim that each of them lacks all six elements above; we claim their combination. A per-system comparison along these six elements belongs in §7, and we will add it in the final version.
Response to V4n5 (4/4): maximal permissiveness is relative to the net — agreed, and now stated so; unmodelled safe actions are refused; what E2 does and does not show about capability
W3. "Maximal permissiveness holds only relative to the predefined net, action vocabulary, abstraction, and forbidden-state specification. It does not imply preservation of the closed-loop agent's real-world capability."
A. Thank you for stating this so exactly; we agree. Theorem 2 compares the safe supervisors of one net under full observation. It says nothing about actions the net does not model, about how a trajectory changes after a refusal, or about the abstraction. Four sentences in the paper claimed more (§4.3, l. 291–292; App D, l. 1005–1006; App J, l. 1877; §6, l. 415–416). The revised PDF replaces all four with the narrower statement, which is the correct one (p. 6, l. 308–312; p. 9, l. 446–447; p. 20, l. 1058–1061; p. 36, l. 1930–1932): under full observation, refuses no firing that some safe supervisor of the same net would allow. Capability lost to what the net does not model, or to how the agent reacts to refusals, is a separate quantity, and Theorem 2 does not bound it.
Our own numbers agree with you (Table 2, completion on injected episodes):
| Kernel | Best baseline | |
|---|---|---|
| Pooled over the four models | 0.84 | 0.73, the prompt policy |
| gpt-4.1 | 0.51 | 0.96, the prompt policy |
| Pooled, with the bare refusal instead of the informative one | 0.39 | — |
Pooled, the other two arms are further back, 0.16 with no mediation and 0.10 for the guardrail (l. 409–410). So the abstract's "task completion is higher than under any baseline" holds pooled over the four models, as the abstract says, and not per model. It also reflects the scoring: an executed unauthorized release ends the episode as a failure (l. 410–412). On gpt-4.1, after a refused deploy, the model stops under two payloads and keeps retrying under a third (l. 421–423).
Q3. "What happens when an agent discovers a safe and useful strategy that has no corresponding transition or path in the predefined net?"
A. It is refused exactly like an unsafe one: returns , so the first conjunct of (1) fails, while internal steps pass with the marking unchanged (l. 302–303). The conjuncts of (1) do tell a refusal for want of a model from a modelled hazard. They do not tell a safe unmodelled action from an unsafe one, and the paper does not report refusals by conjunct. The remedies we have are at design time: App M's library was refined by inspecting every refusal (l. 2262–2263), and App L sketches certified reconfiguration (l. 2129–2135).
Q4. "Can the authors evaluate capability preservation on clean, open-ended tasks with multiple safe workflows, dynamic failures, and fixed interaction budgets? A comparison against a hand-written stateful workflow monitor, and across plan-then-execute and ReAct-style agents, would help isolate the value and scope of the Petri-net formulation."
A. These are the right tests. We did not run new experiments for this revision, so we answer from what the paper already has, and on the first two parts the answer is that it does not show this. The new §8 states both as limitations (p. 10, l. 522–539).
Capability on clean, open-ended tasks is not shown. E2 is one workflow with episodes capped at 16 model turns (l. 2300), and the paper reports clean results only for the guardrail (l. 412–414). E5 is structural, since running agents through ToolSandbox "is not part of this paper" (l. 2560–2561).
No hand-written stateful monitor was run. By Theorem 1, a checker that tests the same preconditions and counts unspent approvals correctly, which §1 concedes "holds the same counter" (l. 082–083), should tie the kernel's zero on E2. Completion is another matter, since it turns on the refusal text. E2 also cannot separate spending an approval from only testing it: each episode has one change request, and no payload replays a spent approval (App N, l. 2298–2299 and 2313–2316).
The architecture is the one part we can answer. The guarantee does not depend on it: rule (1) reads only the proposed call and the marking (in E2, "the tool name and nothing else", l. 2353), and Theorem 3 assumes nothing about the proposer, only A1–A4. Utility does depend on it, and E2 ran one tool-calling loop (l. 396–397), so we have no utility figure for a plan-then-execute agent.
Thank you again for a review that corrected the paper's central result. We hope these answers are helpful, and we would be glad to clarify anything further.
Response to V4n5 (1/4): you are right — Theorem 1 shows a trusted count is needed, not a Petri net; what it does establish
Thank you for a precise and thoughtful review, and for your generous reading of the paper's direction. We agree with almost all of it, and your W1 is the point that sent us back to Theorem 1.
W1, first paragraph, and Q1, first part. "It does not establish that Petri nets are necessary: a transactional counter, immutable execution log, one-time capability, or hand-written stateful monitor can enforce the same property." And: "What does Theorem 1 establish beyond the need for trusted operational state?"
A. You are right, and we overstated it. Theorem 1 says how much memory enforcing the rule takes. It does not say what holds the memory. Any mechanism that keeps a correct count enforces the rule, including all four you name. Four sentences in the paper said more, and the revised PDF corrects all four. §4.1 now reads "proving it, with the threat model of §2, fixes the architecture, a trusted count, though not the formalism" (p. 5, l. 228–229 of the revised PDF). Its later "case for nets over state machines" is now a case for counters over finite-state machines (p. 5, l. 267). Corollary 2's title no longer adds that the guard is therefore not a state machine (p. 5, l. 262). Remark 2 in App K drops the same inference.
Beyond "state is needed", Theorem 1 gives three things.
It says nothing about trust. That the count must sit below the model comes from the threat model (§2, l. 136–139) and from A2 and A4.
Why we hold the count in a net is a separate argument, and not a consequence of Theorem 1. Whether an approval is spent or only tested is an arc (App E, l. 1160–1162). Invariants come from the incidence matrix with no enumeration, and hold for every initial marking of the same shape (App I, l. 1736–1738). A linear constraint becomes one monitor place (§4.2, l. 263–266). Six modules cover all 129 ToolSandbox scenarios (E5, l. 433–435). §1 makes the same point about a hand-written checker: it holds the same counter, but offers no synthesis, no reuse across tools and tasks, and no invariant valid for every initial marking (l. 082–085). What the paper does not show is that any of this matters at scale.