acceptodds
Under review as a conference paper at ICLR 2027

ProtoGuard: Safe and Token-Efficient LLM Agent Interaction through Formal Protocols

Abstract

LLM agent teams are commonly coordinated through workflow graphs, yet structural and input/output type checks do not ensure interaction safety: agents may deadlock, fail to propagate decisions, or act prematurely. Even with a sound interaction plan, runtime deviations remain possible for LLM agents. We introduce ProtoGuard, a framework that specifies multi-agent interactions as formal protocols and connects static validation with runtime governance. Building on multiparty session types (MPST), a formalism for modelling interactions with rigorous guarantees of communication safety and progress, ProtoGuard uses an LLM to draft a global protocol, checks and refines it for formal validity under MPST, and derives a role-specific contract for each agent. The resulting contracts provide protocol-governed execution through agent prompts, deterministic monitoring, pre-delivery gating, and protocol-aware scheduling. Runtime enforcement keeps agent interaction within the validated protocol, preserving its guarantees by construction without constraining task-specific agent decisions. We evaluate protocol-governed execution on diverse multi-agent benchmarks and LLMs. Across the evaluated benchmark–model settings, macro-averaged goal-completion rate increases from 4.1% under the skills-only baseline (role-specific instructions without protocol support) to 98.9% under the full configuration, while runtime enforcement eliminates delivered protocol violations. Mean execution time decreases from 249.6s to 47.6s, and runtime token cost per trial run falls by 91.5%. These results demonstrate that validated and enforced interaction protocols can improve the correctness, safety, and efficiency of LLM-agent coordination, suggesting formal specifications as a principled execution layer for stochastic LLM agents.

Primary area:
neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)
Keywords:
LLM agents, multi-agent coordination, agent orchestration, formal protocols, multiparty session types, runtime enforcement

Reviews

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

This paper introduces ProtoGuard, a framework for coordinating LLM agents through formally validated interaction protocols. Each agent is assigned a local contract, against which its messages are checked before delivery. Protocol-aware scheduling invokes agents that are currently eligible to act, helping prevent premature decisions, missing notifications, and circular waiting.

The main contribution is the integration of static protocol validation with runtime enforcement. Multiparty session types provide the foundation for validating global protocols and deriving local contracts, which govern agent prompting, message verification, and scheduling. This makes protocols enforceable execution constraints rather than instructions that agents are expected to follow.

The authors evaluate four tasks using four LLMs across five configurations. The complete framework increases the macro-averaged completion rate from 4.1% to 98.9%, with no delivered protocol violations in the evaluated runs. The ablation results indicate that enforcement accounts for the primary reliability improvements, while scheduling reduces token consumption and execution time.

Critical strengths

The experimental design clearly distinguishes the effects of individual components across four tasks and four models. The ablations demonstrate that protocol instructions alone are insufficient. The authors also report that local contracts alone underperform global protocol context, providing a balanced assessment of the components.

Critical weaknesses

The experiments provide informative ablations but lack comparisons with established workflow orchestration or agent-governance methods. They demonstrate improvements over role-specific instructions alone and simpler protocol-based configurations, but do not establish ProtoGuard’s additional benefits over existing alternatives. Given the very low success rate of C1, a stronger external baseline would strengthen the empirical evidence.

Questions for authors
  1. Could the authors clarify the prompting and scheduling procedures used in C1, particularly whether the agent instructions include the coordination rules required for each task? This clarification would help explain the baseline’s low success rate.
2 comments
AuthorsOpenReview ↗

Response to Reviewer cTKR

We thank the reviewer for the constructive assessment and for recognising PROTOGUARD's static-to-runtime design and the value of our ablation studies. To address the reviewer's concerns, we conducted additional experiments and provide further clarifications below.

W1: Comparison with established workflow systems

We agree that comparisons beyond the original C1–C5 configurations are important. As detailed in our responses to Reviewer RC7s (W1/Q2) and Reviewer hWvs (W1/Q1), we added three baselines without validated workflows: C1-FSM, an LLM-generated Python state machine with deterministic control; C1-MAF (Microsoft Agent Framework); and C1-LangGraph. The latter two use LLM orchestrators. Each configuration ran 720 trials across four use cases and four models, including conditional branches and loops.

ConfigurationGCRTokens/success
C1 (original)4.1%3,492,995
C1-FSM22.6%599,124
C1-MAF18.2%4,264,845
C1-LangGraph6.3%11,083,067
PROTOGUARD (C5)98.9%23,968

The new baselines improve on C1 but remain substantially below PROTOGUARD.

These comparisons provide evidence for the value of validated coordination over LLM-generated workflows or orchestration alone. They do not establish superiority over an equivalently specified deterministic workflow. PROTOGUARD's distinctive contribution is validating the global protocol before execution and automatically deriving compatible role-local contracts and runtime enforcement and scheduling controls.

Q1: C1 prompting and scheduling procedures

C1 included meaningful task-specific coordination instructions, rather than relying on role descriptions alone. Agents received task-specific instructions, descriptions of all team roles, role-specific skills, a terminal condition, and a required output format. The coordination information varied across benchmarks:

  • Finance: Local skills specify dependencies between analysts, verification, approval, and final reporting.
  • AgenticPay: Skills name the settlement messages and give each role a reasonable rule: the Buyer pays only after delivery, and the Seller ships only after the funds are secured.
  • React 18: The full user intent and role skills describe migration phases, dependencies, and testing gates.
  • SDLC: Agents received the full intent, which specifies four reviews, revision, approval, and security-before-deployment requirements, and role guidance; C1 has no validated shared protocol or local contracts.

Thus, C1 includes meaningful coordination guidance, but does not provide a single validated global protocol or compatible projected local contracts. Its low completion rate should not be attributed to an absence of coordination instructions.

Scheduling and termination. C1 uses fixed round-robin polling, providing each selected agent with the shared interaction history. WAIT responses produce no delivered message. Attempts terminate after more than 2|R| consecutive non-progress polls (|R| = number of roles), upon reaching the terminal condition, or when the step budget is exhausted. Step budgets are 24 (Finance and AgenticPay), 44 (React 18), and 48 (SDLC). Finance and AgenticPay permit up to three attempts per trial, and React 18 and SDLC one. The new baselines do not rely on this polling: in C1-FSM the generated controller decides which roles may act, and in C1-MAF and C1-LangGraph the orchestrator chooses the next role, under the same step budgets.

C1–C4 use round-robin scheduling, whereas C5 selects roles with enabled sends using projected EFSM states. Within each benchmark, all configurations share the same step budgets. Their differences concern protocol information, enforcement, and scheduling.

The AgenticPay baseline illustrates the consequence of incompatible local instructions: 98/120 C1 trials were catastrophic, and in 93 of them an attempt froze with no delivered message. These results demonstrate the limitations of the evaluated skills-only configuration, not of all manually specified workflows.

We will incorporate the new external baselines and clarify C1's prompting, scheduling, and termination procedures in the revised manuscript. We will also provide the saved C1 system prompts for all 23 roles, their skills, and execution configurations in the supplementary material.

Thank you for the detailed response and for conducting the additional experiments. The inclusion of the new external baselines (C1-FSM, C1-MAF, and C1-LangGraph) along with the clarification on C1’s prompting, scheduling, and termination procedures thoroughly addresses my previous concerns.

Given that my questions have been resolved, I am happy to maintain my original rating of 3 (Weak Accept).

Reviewer_hWvsOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper presents ProtoGuard, a multi-agent coordination framework based on Multiparty Session Types (MPST). It uses an LLM to generate a global interaction protocol, checks its structural validity, and converts it into local rules for each agent. During execution, the system uses runtime enforcement and protocol-aware scheduling to prevent protocol violations and reduce unnecessary LLM calls. Experiments show that ProtoGuard can significantly improve task completion rates while reducing execution time and token costs.

Critical strengths

S1. A practical solution to multi-agent coordination problems.

I think ProtoGuard addresses an important problem, including incorrect message ordering and deadlocks. By combining formal protocols with runtime enforcement, it can block invalid messages while still allowing agents to make their own decisions. Overall, I find the design clear and practical.

S2. Strong results with useful ablation studies.

The authors test ProtoGuard on multiple benchmarks and LLMs, achieving an average task completion rate of 98.9% while reducing execution time and token usage. The ablation studies also show that runtime enforcement improves protocol compliance, while scheduling reduces unnecessary agent calls. I think these results support the effectiveness of the method.

Critical weaknesses

W1. Limited novelty and weak baselines.

Most components, including MPST, static validation, runtime monitoring, and scheduling, are based on existing techniques. While I think their integration is practical, the technical novelty seems limited. Also, the experiments mainly compare the authors' own C1–C5 configurations, without strong existing workflow baselines. In particular, C1 only uses role-specific instructions. I would like to see comparisons with stronger baselines to better understand ProtoGuard's actual benefits.

W2. Limited evaluation of real-world correctness and end-to-end reliability.

Some benchmarks use fairly simple success criteria. For example, Appendix F notes that completing the React 18 task does not mean the build or tests passed, and some AgenticPay checks only examine message content. Also, the experiments use statically validated protocols without fully checking whether they match the original user requirements. I think the results mainly show reliable protocol execution, rather than the end-to-end correctness of real-world tasks.

Questions for authors

Q1. Could the authors compare ProtoGuard with existing agent workflow systems? For example, compared to systems that already support conditional branches and deterministic execution control, how much additional improvement does ProtoGuard provide in reliability and efficiency?

Q2. Could the authors provide stronger task success checks, such as actually checking the Build/Test results for React 18, or adding other metrics for task correctness? This would help show that the high completion rates reflect more than just following the correct interaction workflow.

2 comments
AuthorsOpenReview ↗

Response to Reviewer hWvs (W1/Q1)

We thank the reviewer for the constructive assessment and for recognising PROTOGUARD's practical value and experimental strengths. We conducted additional experiments and analyses to address the concerns below.

W1/Q1: Novelty and stronger workflow baselines

We agree that MPST, static validation, and runtime monitoring build on established techniques. PROTOGUARD's contribution is integrating them into a pipeline that validates a global protocol, derives compatible role-local contracts, and compiles runtime enforcement and scheduling controls.

As detailed in our response to Reviewer RC7s (W1/Q2), we added three baselines without validated workflows: C1-FSM, an LLM-generated Python state machine with deterministic control; C1-MAF (Microsoft Agent Framework); and C1-LangGraph. C1-FSM represents deterministic execution control, in which code decides every step; C1-MAF and C1-LangGraph are existing workflow frameworks with conditional branching, where an LLM orchestrator chooses the branch. Each ran 720 trials across four use cases and four models.

ConfigurationGCRTokens/success
C1-FSM22.6%599,124
C1-MAF18.2%4,264,845
C1-LangGraph6.3%11,083,067
PROTOGUARD (C5)98.9%23,968

These baselines improve on the original C1 (4.1% GCR), but remain below C5. They also take unsafe actions in 8.6%, 15.1% and 13.6% of trials on average, while C5 has no catastrophic trial.

These comparisons provide evidence for the value of validated coordination over workflow generation or LLM orchestration alone. They do not establish superiority over an equivalently specified deterministic workflow. Our SDLC experiment also shows that nuSCR detects protocol faults before execution, while projection automatically derives compatible local contracts and runtime controls.

AuthorsOpenReview ↗

Response to Reviewer hWvs (W2/Q2)

W2/Q2: Task correctness and end-to-end reliability

We agree that protocol completion does not necessarily establish task correctness. The original React 18 benchmark evaluates message coordination, not actual builds or tests. We therefore conducted a real-code experiment and introduced additional outcome-based checks.

1. Real React 18 build/test experiment. The same six roles migrated a real web application from React 17 to React 18: a small order-handling web page (ten source files) that shows an order with its customer, stock level and prices, and lets the user edit a note and reserve stock. An isolated runner built the code and executed 12 hidden tests, which open the page in a simulated browser and click and type as a user would, with final code independently checked for build success, all tests, and warnings. Using GPT-5.4, we ran 30 trials per configuration with identical code, tests, and limits. C1-T, C3-T, C4-T and C5-T denote C1, C3, C4 and C5 run on this real build and test implementation.

MetricC1-TC3-TC4-TC5-T
No false "all tests pass" report96.7%100%100%100%
GCR10.0%100%100%100%
Catastrophic trials26.7%0%0%0%
Protocol completedn/a46.7%100%100%
Tokens/successful trial (GCR, and final code passes the real check)3,888,229769,583968,708251,593

In this React 18 experiment, every C4-T and C5-T trial completed the protocol, left code that passes the real check, and sent no false test report. Without a protocol, C1-T reaches GCR in only 10.0% of trials and 26.7% are catastrophic. Although C3-T achieved 100% GCR, only 46.7% of its trials completed the full protocol, distinguishing GCR from protocol completion. Per successful trial, C5-T used 74% fewer tokens than C4-T and 94% fewer than C1-T.

2. Task correctness. GCR checks the interaction, not whether the result is right. We therefore add one metric. A trial is task-correct when it passes GCR and its outcome is right; task correctness is the share of all trials of a configuration that are task-correct. A program decides this from the recorded trial, with one condition per benchmark:

  • SDLC: the trial passes GCR, the release decision equals the answer key fixed by the defects of the reviewed artifact, and no catastrophic action occurs.
  • AgenticPay: the trial passes GCR and the settlement is consistent (one deposit and one release of the same amount, the steps in order, none repeated).
  • Finance: the trial passes GCR, and the expense figure and the revenue figure in the final report equal the inputs.
  • React 18: the trial passes GCR and its final code builds, passes all 12 tests and gives no warning. The original React 18 trials have no code, so this row is the real build and test experiment above.

For SDLC, AgenticPay and Finance we applied the check to the original trials, without rerunning any model.

Task correctnessC1C3C4C5
SDLC4.7%37.5%94.4%95.3%
AgenticPay0%75.8%97.5%100%
Finance5.0%69.2%99.2%99.2%
React 18 (real build and tests, C1-T to C5-T)10.0%100%100%100%

Under enforcement, task correctness reaches 94.4–100% across these benchmarks. These checks verify recorded outcomes, not external financial transactions or real deployments. They demonstrate that the improvements extend beyond protocol conformance, while preserving the distinction between interaction safety and semantic correctness.

3. Intent fidelity. Static validity does not by itself establish that a protocol captures the user's requirements, so we checked fidelity separately. First, an audit of the four protocols against their intents, requirement by requirement, finds that SDLC, AgenticPay and Finance represent every coordination requirement (who sends what to whom, in which order, on which branch, including fan-out to several roles and fan-in of their replies), and that React 18 represents its phase order, repeated testing and sign-off. Second, when an LLM drafts protocols from the intent with checker feedback, 71 of the 72 protocols that nuScr accepts keep the intent. The audit checks the coordination fidelity of the four evaluated protocols, and the runtime experiments measure execution under those validated protocols.

We will incorporate these baselines, the build/test results and the task-correctness metrics into the revised manuscript, and report the intent-fidelity checks in the supplementary material.

Reviewer_RC7sOpenReview ↗
Rating
2
Confidence
2
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

This paper presents PROTOGUARD, a safety framework that uses multiparty session types (MPST) to specify multi-agent LLM communication protocols, validate them with νSCR, project them into role-local contracts, and enforce these contracts through runtime monitoring, pre-delivery gating, and role scheduling.

Critical strengths
  • The paper presents a coherent static-to-runtime story. The use of projected role-local contracts is a noticeable design choice. It gives each agent only its own interaction obligations, while a deterministic monitor can enforce a common communication model. The paper also correctly distinguishes interaction conformance from semantic correctness of content in Section 4 and Section 6, rather than overstating MPST as a solution to factuality or policy quality.
  • The progressive C1–C5 experimental design is useful. In particular, the C3-to-C4 comparison isolates the impact of pre-delivery enforcement, and the C4-to-C5 comparison isolates scheduling. The reported jump from C3 to C4 in Section 5.3, from 76.7% to 98.0% macro-averaged GCR, is consistent with the claim that merely exposing a protocol to an LLM is not equivalent to enforcing it.
Critical weaknesses
  • The experiments show that enforcement and scheduling help, but I am less convinced that they establish the added value of MPST over a conventional deterministic workflow. C4 adds pre-delivery enforcement, and C5 adds scheduling based on which roles are allowed to send. A manually encoded state machine could also enforce the same fan-in requirements, branch conditions, and role eligibility. Comparing against such a baseline would help clarify what MPST validation and projection contribute beyond these runtime controls. The formal approach may be valuable for detecting protocol errors and deriving compatible local contracts, but the current evaluation provides limited evidence of those benefits.

  • I found the headline efficiency results harder to interpret across benchmarks. Section 5.2 reports a 99.3% reduction in pooled tokens per success, but success has a different definition in each task, and this metric reflects both token consumption and completion rate. AgenticPay also allows multiple attempts per trial, while some React 18 cells have fewer trials. These choices are disclosed and do not by themselves invalidate the comparison. Still, I would like to see whether the pooled result holds under equal weighting of benchmark–model pairs, alongside uncertainty estimates and per-attempt costs. This would make it easier to judge how broadly the headline reduction applies.

Questions for authors
  • Section 4.2 says that rejected actions return diagnostics without changing the live monitor state. What happens if an agent keeps proposing invalid actions? Is there a retry limit or recovery procedure, and what scheduler fairness assumptions are needed for progress?

  • Can you compare PROTOGUARD with a deterministic workflow or state-machine baseline that enforces the same fan-in, branch conditions, value guards, and role eligibility? Alternatively, can you provide evidence of the construction-time benefits of MPST validation and projection, such as detecting protocol errors or reducing the effort needed to implement compatible roles?

  • Figure 5 provides confidence intervals for individual completion rates. Can you also quantify uncertainty in the aggregate GCR differences and efficiency results, particularly the small C4-to-C5 completion gain? For AgenticPay, how do the cost comparisons change when reported per attempt rather than per trial?

1 comment
AuthorsOpenReview ↗

Response to Reviewer RC7s

We thank the reviewer for the constructive assessment and for recognising PROTOGUARD's benefits. We conducted additional experiments and analyses to address the concerns below.

W1/Q2: MPST vs deterministic workflows

We agree that a deterministic state machine can enforce the same protocol rules as PROTOGUARD. MPST adds pre-execution validation of the global protocol and automatic derivation of compatible role-local contracts and runtime controls, avoiding independently implemented checks.

We evaluated three baselines without MPST validation: C1-FSM, an LLM-generated Python state machine with deterministic control; C1-MAF (Microsoft Agent Framework); and C1-LangGraph. The latter two use LLM orchestrators. Each configuration ran 720 trials (four use cases, four models).

ConfigurationGCRTokens/success
C1-FSM22.6%599,124
C1-MAF18.2%4,264,845
C1-LangGraph6.3%11,083,067
PROTOGUARD (C5)98.9%23,968

These results illustrate that deterministic execution alone cannot guarantee workflow correctness. The baselines lack a validated global protocol; we do not claim superiority over an equivalently specified FSM.

We also tested construction-time error detection in SDLC. Removing the Merger-to-DevOps notification on revision/rejection branches produces a protocol that nuScr rejects before execution. In agent runs, affected branches can leave roles waiting until termination, while all trials on the unaffected approval branch succeeded. Testing only the approval branch would miss this fault, whereas nuScr checks every branch and rejects the protocol before any run.

After validation, MPST projection derives compatible role-local contracts, which are compiled into gate and scheduler state machines without separately implementing runtime controls.

W2: Efficiency and cross-benchmark comparability

We acknowledge that pooled tokens/success depends on completion rates, task definitions and trial counts. We recomputed efficiency with equal weight across 16 benchmark–model cells.

MetricC1C5Reduction
Equal-cell tokens/success5.486M19.3K99.65%
Equal-cell tokens/trial223.3K19.0K91.47%

The original pooled reduction was 99.31%. Savings persist with equal weighting and in raw tokens/trial, independently of success normalisation. Equal-cell tokens/success is mean tokens/trial divided by mean GCR, not the average of cell-level ratios.

Common-subset analyses estimate C5-versus-C1 reductions of 99.67% (14 cells; 95% bounds [99.37%, 99.85%]) and 99.47% (11 cells; [98.96%, 99.77%]). The subsets exclude SDLC cells with missing token records and, additionally, incomplete React 18 cells. These are sensitivity bounds, not full 16-cell intervals. Costs cover recorded runtime tokens, excluding the one-time protocol construction.

Q1: recovery, retry limits and fairness

Rejected proposals leave the live monitor state and accepted trace unchanged. Agents receive diagnostics on their next scheduled turn and can retry. C4 polls roles round-robin; C5 rotates among roles with enabled sends. Rejected, missing, unparsable and WAIT actions increment a consecutive no-progress counter, reset by an accepted message. An attempt terminates when the counter exceeds 2|R| (|R| = number of roles); accepted-message step budgets and up to three attempts also apply.

C5 gives each role that is allowed to send a turn in rotation, so no such role is skipped forever, provided model calls return. This guarantees safety, not completion: the run moves forward only if agents propose valid actions within the limits above; otherwise the attempt ends as a recorded failure, and no invalid message is delivered.

Q3: Aggregate uncertainty and per-attempt costs

Using 100,000 independent binomial resamples per benchmark–model–configuration cell, we estimated macro-GCR differences and 95% intervals:

ComparisonDifference95% interval
C4 − C3+21.32 pp[+19.44, +23.19]
C5 − C4+0.90 pp[−0.14, +2.01]
C5 − C1+94.82 pp[+93.04, +96.44]

The C3-to-C4 gain supports pre-delivery enforcement. Because the C4-to-C5 interval includes zero, we do not claim a statistically established completion gain from scheduling; its demonstrated benefit is primarily efficiency. Aggregate-count rather than paired-trial resampling may understate uncertainty in all-success cells.

For AgenticPay, C5 uses 4,638 tokens per trial, against 34,665 (C1) and 8,632 (C4). Recorded tokens divided by total attempts give 11,555 tokens/attempt (C1), 7,788 (C4) and 4,418 (C5); per attempt, C5's savings remain 61.8% versus C1 and 43.3% versus C4, so savings are not solely due to fewer attempts.

We will incorporate these new baselines, construction-time evidence, additional analyses, and clarifications into the revised manuscript.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Overall Response to Reviewers

We sincerely thank all reviewers for their constructive feedback and valuable suggestions. We have addressed each reviewer's comments in separate, reviewer-specific responses.

Based on this feedback, we have submitted a revised manuscript that incorporates new external baselines, including a deterministic state machine and existing agent workflow frameworks, alongside additional experiments, analyses, and methodological clarifications. These revisions aim to strengthen the empirical evaluation and address the reviewers' concerns.

We have also submitted updated supplementary materials that integrate the new experiments and supporting analyses with the original supplementary content.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.