acceptodds
Under review as a conference paper at ICLR 2027

Graph Verification for LLM Agent Safety

Abstract

As large language models (LLMs) evolve into more capable agentic systems, their safety risks become increasingly diverse and consequential, calling for a reliable and verifiable safety assessment. Existing verification methods typically encode safety requirements into explicit rules or specifications, but the evidence needed to evaluate them remains scattered across complex execution trajectories. In this work, we first analyze common agent risks and characterize agent safety as a set of conditions on the sources and effects of each agent action. To better support the assessment of these conditions, we introduce **VEGAS**, a **VE**rifiable **G**raph for **A**gent **S**afety that organizes the complex trajectory contents into a unified graph representation, and formalizes the safety conditions as explicit graph properties. Furthermore, we also develop GraphGuard, a runtime realization of the above safety formalization that focuses on optimizing practical efficiency and enabling benign-task continuation after safety blocking. Experimental results show that our method substantially improves agent safety by reducing ASR of DeepSeek-V4-Pro from 45.3% to 0.0% on AgentDojo, while still maintaining a high benign-task performance. Our work demonstrates the potential of using graph representation to provide a structured and verifiable abstraction for agent safety.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
LLM Agent, Agent Safety, Safety Verification, Safety Guardrail

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_BJEVOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper introduces VEGAS, a graph representation of agent trajectories that records instructions, information sources, authorizations, constraints, and actions. GraphGuard checks this graph before execution and uses the resulting evidence to help the agent recover after blocking an unsafe action. Experiments across three benchmarks and three agent models report substantial reductions in attack success while retaining much of the original task utility.

Critical strengths

The reported safety gains cover several threat types and agent models. The MT-AgentRisk results are particularly strong: ASR falls from 75.0% to 5.6% for DeepSeek, 54.6% to 7.1% for GLM, and 20.4% to 0.5% for Kimi. This suggests practical value beyond defending against a single injection setting.

The graph provides explicit evidence for interventions, and the system is designed to continue benign work after a block. The impact-aware implementation also reduces reported per-step latency from 20.55 to 13.35 seconds. These are useful considerations for deploying a runtime guardrail.

Critical weaknesses

The contribution of the graph representation is not isolated. In Appendix F, the compiler still makes substantive judgments about harmfulness, authorization, and constraint satisfaction, while influence edges depend on the agent’s stated reasoning. The deterministic verifier checks these judgments after they have been encoded as graph facts. The conditional theorem is reasonable, but does not establish that this encoding makes the underlying judgments more reliable. Table 5 varies individual checks; it does not compare against the same model applying the same checks without a graph, with matched recovery and inference budgets.

The evidence for reliable compilation and fair utility comparisons is incomplete. Attribution accuracy is measured only on blocked actions, so it does not assess dangerous dependencies omitted from allowed actions. The 30-instance-per-benchmark audit lacks a clear annotation protocol, exact error counts, and independent validation details. The PDF also does not specify the main evaluation sample counts, attack configurations, or uncertainty estimates. Moreover, Appendix E terminates FormalJudge executions after a failed check, whereas GraphGuard can recover. This makes it difficult to separate representation gains from differences in continuation policy.

Questions for authors

Does GraphGuard retain its advantage over a graph-free implementation using the same compiler, safety rules, inference budget, and recovery policy? Please also separate the gains from graph construction and witness-guided recovery.

How were attribution and compilation correctness evaluated, and by whom? Please report errors on allowed as well as blocked actions, along with the benchmark sample counts, attack settings, and uncertainty estimates.

Equation 25 retains source ancestors but excludes intermediate action nodes. For an influence path u → b → v → a, with b an earlier action, the stated projection removes b and can break reachability, contradicting Lemma 1. Figure 6 appears to retain these nodes. Does the implementation use the full ancestor closure, and can the definition and proof be corrected accordingly?

4 comments
AuthorsOpenReview ↗

Response to Reviewer BJEV (1/3)

We sincerely thank the reviewer for the careful and constructive review. We particularly appreciate your recognition of our method's effectiveness across diverse threat settings, as well as the usefulness of witness-guided recovery and impact-aware implementation. Below, we carefully respond to your concerns in Weaknesses and Questions, and we hope you could find our responses satisfactory.


W1 & Q1. Does GraphGuard retain its advantage over a graph-free implementation? Please also separate the gains from graph construction and witness-guided recovery.

R1: To address this concern, we conduct two ablation studies to disentangle the contributions of our graph representation and witness-guided recovery.

Specifically, we compare GraphGuard with two variants: (1) GraphGuard without graph representation, which removes graph construction and only uses the LLM to perform the same safety checks and identify unsafe sources using same safety rules, while retaining the same evidence-guided recovery policy, and (2) GraphGuard without witness-guided recovery, which retains graph-based safety verification but immediately terminates the agent conversion once an unsafe action is blocked. We report the ASR, UTL, and benign task success rate (Benign Suc).

AgentDojoASBMTA
ASR ↓UTL ↑Benign Suc ↑ASR ↓UTL ↑Benign Suc ↑ASR ↓Benign Suc ↑
GraphGuard0.085.389.715.764.688.25.691.7
GraphGuard w/o graph representation0.076.556.732.29.480.49.673.3
GraphGuard w/o witness-guided recovery0.045.486.514.247.188.25.186.7

Comparing to GraphGuard, removing the graph representation leads to substantial reductions in UTL and Benign Suc (e.g., Benign Suc on AgentDojo drops from 89.7% to 56.7%, while UTL on ASB drops from 64.6% to 9.4%). This result indicates that direct LLM-based judgment is struggle to accurately identify the unsafe sources, where our graph representation can mitigate this problem by explicitly structuring the semantics and relationships within agent trajectories

For removing witness-guided recovery, it has relatively little impact on ASR and benign task success, but leads to a substantial degradation in UTL. This indicates that ending the conversation once an unsafe action occurs may prevent the agent from completing its original objective, and our witness-guided recovery mechanism effectively mitigates this issue by providing the agent with explicit feedback about unsafe sources.

We've already added this ablation study to Section 4.3 of our revised version of manuscript.


W2 & Q2. (1) Attribution accuracy is insufficient for reliable compilation, omitting the dangerous dependencies from allowed actions (2) What are the annotation protocol, error counts and validation details of the trajectory audit experiment? (3) What are the sample counts, attack configuration and uncertainty estimations? (4) Terminating FormalJudge or AgentSpec without continuation policy may introduce unfairness in comparison.

R2-1: Clarification of Attribution Accuracy

Regarding that dangerous dependencies may be omitted from allowed actions, we extend our trajectory audit experiment in Appendix B.3 to examine this type of case. Specifically, for each sampled trajectory, we manually analyze the source and potential harmful effects of each allowed action, and examine whether the source edges and violation edges are completely constructed by GraphGuard. Among these 90 cases, we observe only one such omission, showing that such cases are rare and that our compilation remains reliable in practice. Moreover, our framework is highly compatible, and such rare cases can be further mitigated within our impact-aware design.

AuthorsOpenReview ↗

Response to Reviewer BJEV (2/3)

R2-2: Annotation Protocol, Validation Details, and Error Counts of the Audit Experiment

Our audit experiment consists of two complementary parts: the attribution accuracy audit on blocked actions (detailing the evaluation protocol and 150-case human validation), and the trajectory audit in Appendix B.3 (detailing the manual annotation protocol and 90-case error counts).

Attribution Accuracy Audit (Evaluation Protocol and Validation Details). To audit attribution accuracy on blocked actions, we use GPT-5.6 Sol as an LLM-based evaluator to review all blocked actions along two aspects:

  • Correctness of unsafe decisions, which examine whether the safety check that caused an action to be blocked was correctly triggered. Specifically, the evaluator analyzes the semantic relationship between the action and all instructions and information in the trajectory to assess source legitimacy, and examine the semantics and potential effects of the action to assess effect benignity.
  • Correctness of unsafe-source attribution: For actions that fail the source-legitimacy check, the evaluator examines whether the sources identified by GraphGuard are indeed illegitimate, and whether any other illegitimate sources that influenced the action were omitted from the attribution.

To validate the evaluator's reliability, we additionally manually review 50 sampled cases from each benchmark (150 in total). Given the relatively well-defined nature of the benchmark cases and the strong reasoning capabilities of GPT-5.6 Sol, the manual assessments remain consistent with the evaluator's judgments across the sampled cases, providing evidence for the reliability of our attribution evaluation.

Trajectory Audit in Appendix B.3 (Annotation Protocol and Error Counts). In Appendix B.3, 90 cases are randomly sampled from the evaluation results, covering both allowed and blocked actions. Following the "safety-faithfulness" conditions described in Appendix B.2, we manually annotate each case along four dimensions:

  • Semantic Completeness: For each system / user prompt, and environmental observation in a trajectory, following the node semantics definition in Section 2.2, we examine whether all relevant information, instructions, and constraints are represented in corresponding nodes extracted by the compiler. For user prompts, we additionally examine whether authorization content are correctly extracted as nodes, including both explicit permissions (i.e., what the agent is allowed to do) and task-implied permissions concerning the information required to complete the task.
  • Attribute Correctness: For each extracted instruction, we manually examine whether it constitutes an explicitly harmful task and compare our judgment with the SaSa attribute assigned by the compiler.
  • Relationship Completeness: For each action, we examine its semantics and the semantics of the existing graph components, and manually verify whether the three types of relationships defined in Section 2.2 are correctly and completely constructed.
  • Constraint Coverage: For each harmful action, we examine whether our predefined global constraints cover the harmful consequences that the action may produce.

Among the 90 audited cases, only four cases are identified with errors, with the exact error counts and details summarized below:

Error TypeObserved Error Details
Semantic Completeness (2 cases)In the two cases, the compiler omitted relevant information and instruction nodes when decomposing an environmental observation and a system prompt, respectively.
Attribute Correctness (1 case)In the observed case, an instruction requesting the disclosure of private information was incorrectly classified as safe.
Relationship Completeness (1 case)In the observed case, the compiler omitted some influence edges.

We have incorporated these evaluation and annotation protocols into Appendix B.3 and Appendix G of our revised manuscript.

AuthorsOpenReview ↗

Response to Reviewer BJEV (3/3)

R2-3: Sample Counts, Attack Configurations, and Uncertainty Estimation

We have added more details about the benchmark configurations and the sample counts in Section 4.1 of our revised manuscript.

  • AgentDojo covers four scenario types: Workspace, Slack, Banking, and Travel, containing 939 test instances. For the attack strategy, we adopt the important_instructions method, which was reported as the most effective attack method in the original paper.
  • Agent Security Bench (ASB) covers ten application scenarios and four types of agent risk, including direct prompt injection, observation prompt injection, memory poisoning, and PoT backdoor attacks, containing 6760 test instances. For the prompt injection format, we adopt the combined_attack strategy, which was the most effective one in the original paper.
  • MT-AgentRisk contains 365 instances across five scenarios, such as filesystem, terminal, and browser. We adopt the multi-turn attack strategy, which shows better attack effectiveness comparing to single-turn strategy.

In addition, we calculate 95% confidence intervals (Wilson 95% CI) for the main experimental results to quantify the uncertainty of our experimental measurements. The results, reported in Appendix H of our revised manuscript due to space limitations, show that GraphGuard maintains its advantages in both ASR and UTL when accounting for statistical uncertainty, providing further evidence of the effectiveness of our approach.

R2-4: Fairness in Comparison

Actually, terminating FormalJudge and AgentSpec without continuation stems from their inherent designs rather than our evaluation setup. Specifically, FormalJudge is designed as a post-hoc auditing method, so it does not provide an online continuation mechanism, while for AgentSpec, its enforcement decisions are primarily based on rule-based inspection of Python code, making it difficult to derive appropriate unsafe-source witnesses that can be provided as actionable recovery feedback. Compared with these two methods, GraphGuard is a framework designed for runtime verification that can provide reliable attribution of unsafe actions to their underlying sources, enabling effective recovery and continued completion of the original benign tasks. This capability is also a practical advantage of our approach.


Q3. Equation 25 contains an error that the definition of influence ancestors retains source ancestors but excludes intermediate action nodes.

R3: We apologize for the false formulation in Equation 25. The influence closure includes not only source nodes but also all intermediate nodes along directed paths leading to the current action, including earlier action nodes, its correct definition should be

Ra={a}∪{v∈Vsrc∪Vact∣v⇝infa}R_{\boldsymbol{a}} = \lbrace \boldsymbol{a} \rbrace \cup \lbrace v \in \boldsymbol{V}^{\mathrm{src}} \cup \boldsymbol{V}^{\mathrm{act}} \mid v \rightsquigarrow_{\mathrm{inf}} \boldsymbol{a} \rbrace

However, as illustrated in Figure 6, our implementation of the source ancestor includes intermediate action nodes, so the experimental results are correct. Thanks for pointing out this error, and we've already revised the corresponding definitions in Appendix D!

AuthorsOpenReview ↗

Look Forward to Further Feedback

Dear Reviewer BJEV,

We sincerely appreciate your thoughtful and constructive feedback, and we have carefully considered each of your comments. We have also made the necessary modifications to our revised version of manuscript. We hope you will find the response satisfactory and are eager to receive your further feedback.

Best, Authors

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

This paper introduces VEGAS and GraphGuard, a runtime safety verification framework for tool-using LLM agents. The authors formalize agent safety through two obligations, source legitimacy and effect benignity, and structure agent execution trajectories into a directed graph containing five semantic node types and three edge types. Safety verification is framed as four deterministic graph-connectivity checks. GraphGuard optimizes runtime execution via impact-aware deferred checking for read-only actions, action-local subgraph materialization, and witness-guided natural-language recovery feedback. Across AgentDojo, ASB, and MTA, GraphGuard substantially reduces ASR (e.g., from 45.3% to 0.0% on AgentDojo with DeepSeek-V4-Pro) while preserving benign utility.

Critical strengths
  • Consolidates provenance, dynamic user authorizations, instruction harmfulness, and outcome-oriented constraints into an evolving graph, mitigating exogenous attacks (injections, memory poisoning, backdoors) and direct harmful requests without requiring upfront per-task policy synthesis.
  • Shifting the auxiliary LLM from end-to-end trajectory judging to localized node and edge extraction prevents context clutter and maintains stable defense performance even when scaled down to a 4B parameter compiler.
  • Converting verification failure witnesses into actionable natural-language feedback resolves the over-termination bottleneck of rigid verifiers, allowing agents to recover and complete benign goals.
Critical weaknesses
  • The paper claims safety assessment is reduced to deterministic graph checks without open-ended LLM evaluation. However, the compiler prompts in Appendix F reveal that Violation edges (EviolE^{\text{viol}}), Authorization edges (EauthE^{\text{auth}}), and Harmfulness attributes (Sa\text{Sa}) are evaluated by prompting the compiler LLM at runtime as a zero-shot security judge.
  • "Safety-faithful" compilation (Equation 20) specifies forward completeness but omits bijectivity and soundness (absence of hallucinated nodes/edges), which is required for the bidirectional equivalence (  ⟺  \iff) in Theorem 1.
  • Deferring VharmV_{\text{harm}}, VconsV_{\text{cons}}, and data-level VtrusV_{\text{trus}} on read/search actions introduces blind spots for direct malicious reads (e.g., exfiltrating passwords via URL query parameters). Furthermore, Vtrus(i)\mathcal{V}_{\text{trus(i)}} is never formally defined in the paper.
Questions for authors
  • If an adaptive prompt injection instructs the agent to use untrusted data in a tool call while explicitly stating in its <think> trace that it is ignoring the data, how does GraphGuard prevent the Influence edge from being omitted?
  • How much of GraphGuard's utility advantage over FormalJudge and AgentSpec in Table 3 stems from the graph representation versus the witness-guided retry loop (i.e., what is GraphGuard's utility under hard termination)?
  • What are the exact predefined global constraints in VconsV^{\text{cons}}, and were baseline methods provided access to equivalent global rules?
4 comments
AuthorsOpenReview ↗

Response to Reviewer KB5v (1/3)

We sincerely thank the reviewer for the detailed and insightful review. We really appreciate your positive feedback on our graph design, its effectiveness and scalability, and its ability to preserve benign task completion through recovery. Below, we carefully address both sets of concerns in Weaknesses and Questions, and we hope you could find our responses satisfactory.


W1. The claim that "safety assessment is reduced to deterministic checks without open-ended LLM evaluation" is inappropriate. There are still many LLM usages.

R1: We are sorry for the unclear statements in our manuscript. We would like to clarify that the key contribution of our method is to transform complex agent trajectories into structured graph representations, which can facilitate reliable safety assessment. Compared with relying on an LLM for open-ended and end-to-end safety judgment, restricting the LLM's role to localized and structured semantic compilation, while reducing the final safety verification to deterministic graph-property checks, makes the overall verification process more structured and verifiable.

Furthermore, as reported in Appendix B.3, we randomly sample 30 cases from each benchmark (90 cases in total) and manually examined whether the LLM compiler correctly constructed the graph components, including EviolE^{viol} and EauthE^{auth} construction, as well as the harmfulness attraibutes judgment. The results are summarized below:

Error TypeNumber of Cases with Errors
EviolE^{viol} construction errors0
EauthE^{auth} construction errors1
Sa evaluation errors1

The results indicates that the LLM compiler is able to achieve high reliability in extracting and constructing the required graph components, supporting the effectiveness and reliability of our method.

Moreover, we agree that several statements in the paper could be made more precise. For example, sentences around lines 85 and 121 may give readers the impression that our method does not rely on LLMs. We have already revised these statements in our manuscript. Thank you again for the reminder!


W2. The proof for "safety-faithful compilation" in Appendix B is incomplete, omitting soundness such as hallucinated nodes or edges.

R2: We thank the reviewer for pointing out the incompleteness of our proof in Appendix B. A faithful graph representation should indeed satisfy two complementary properties: component completeness (already discussed in Appendix B) ensures that the graph captures all relevant content contained in the trajectory, while component soundness ensures that no graph components are introduced without supporting evidence from the trajectory. Together, these two properties can establish the semantic equivalence between the graph representation and the original trajectory. We've already updated Appendix B.2 by adding the definitions of both semantic soundness and relationship soundness in our revised manuscript.

As for the hallucinated nodes and edges that cannot be supported by evidence in the trajectories, we also make this examination in our manual audit of the 90 sampled cases in Appendix B.3. We find only one such case among the 90 samples, which provides empirical evidence that the compiler can achieve good reliability in preserving the soundness of graph constructions.


W3. There might be potential blind spots for direct malicious reads, and Vtrus(i)V_{trus(i)} is never formally defined.

R3: Thanks for pointing out this important case. After carefully reviewing the test cases in our evaluated benchmarks, we did not identify tasks requiring such tool calls, indicating this type of case rarely occurs in the agent safety evaluation settings. However, we acknowledge that such cases can arise in real-world agent deployments and may introduce security blind spots. Therefore, we will refine our impact-aware verification mechanism accordingly. We have also refined the definitions of low- and high-impact actions and related statements in Section 3.1 and Appendix C of our revised manuscript.

We've also added the formal definition of the instruction-only trustworthy check Vtrus(i)\boldsymbol{\mathcal{V}}_{\mathrm{trus(i)}} in Appendix A in the revised version:

Vtrus(i)(G,a)  ⟺  ∀ u∈Ancinst(a),Tr(u)= untrusted  ⟹  ∃ z∈Vauth, s.t. z→authu\boldsymbol{\mathcal{V}}_{\mathrm{trus}(i)}(G, \boldsymbol{a}) \iff \forall\ u \in \mathrm{Anc}_{\mathrm{inst}}(\boldsymbol{a}),\mathbf{Tr}(u) = \ \mathsf{untrusted} \implies \exists\ z \in \boldsymbol{V}^{\mathrm{auth}},\ \text{s.t. } z \xrightarrow{\mathbf{auth}} u

which evaluates only the instruction source nodes is trusted or explicitly authorized. Thanks for pointing out our omission!

AuthorsOpenReview ↗

Response to Reviewer KB5v (2/3)

Q1. How can GraphGuard prevent omitting influence edges when the agent deceives in their reasoning?

R4: Thanks for your thoughtful question. Regarding your concerns that agents may deliberately deceive users for ignoring malicious instructions while actually following it, we randomly sampled 150 trajectories from each evaluated models (450 in total), and manually examined the agent reasoning and their actual actions. In these sampled trajectories, we did not observe this type of case where an agent explicitly claimed to ignore a malicious instruction while actually following it. Besides, prior studies have also demonstrated that language models generally struggle to deliberately deceive in their reasoning under standard settings, and such deception becomes even more difficult in complex agent tasks [1, 2].

Moreover, as our response to Reviewer F1f3's first question, a fallback variant of GraphGuard without using agent reasoning can still provide effective safety protection, which can also avoid being misled in this type of case. We've already added this discussion and related experiments to Section 4.4 of our revised manuscript.

[1] Emmons, S., Jenner, E., Elson, D. K., Saurous, R. A., Rajamanoharan, S., Chen, H., Shafkat, I., & Shah, R. (2025). When chain of thought is necessary, language models struggle to evade monitors.

[2] Yueh-Han, C., McCarthy, R., Lee, B. W., He, H., Kivlichan, I., Baker, B., Carroll, M., & Korbak, T. (2026). Reasoning models struggle to control their chains of thought. ICML 2026.


Q2. How much of GraphGuard's utility advantage over FormalJudge and AgentSpec stems from the graph representation and the witness-guided recovery (i.e., what is GraphGuard's utility under hard termination)?

R5: To address this concern, we conduct two ablation studies to disentangle the contributions of our graph representation and witness-guided recovery to the task utility (UTL).

We first evaluate the contribution of witness-guided recovery by comparing GraphGuard with and without this mechanism.

UTL ↑AgentDojoASB
GraphGuard (w/o witness-guided recovery)45.447.1
GraphGuard (Full)85.364.6
Utility Improvement+39.9 pp+17.5 pp

The results show that terminating the entire conversation once detecting an unsafe action may prevent the agent from completing its original benign objective due to a single safety violation, resulting in lower task utility. In contrast, witness-guided recovery provides the agent with explicit feedback about the source of the violation, allowing it to avoid unsafe behavior while continuing to pursue its original benign objective.

Second, to investigate the contribution of VEGAS's graph representation on the utility advantage, we remove the graph-based representation, using the same underlying LLM to perform the same safety checks and identify the unsafe sources. The identified sources are then provided to the agent as feedback to facilitate recovery.

UTL ↑AgentDojoASB
LLM Judge (w/ witness-guided recovery)76.59.4
GraphGuard (Full)85.364.6
Utility Improvement+8.8 pp+55.2 pp

The results demonstrate that our graph representation also contributes a lot to task utility, particularly on ASB, which encompasses more diverse and complex attack types (direct / observation-based prompt injection, memory poisoning, and PoT backdoor attacks). By explicitly representing the semantics and relationships among the trajectory, the graph enables more precise identification of unsafe sources. In contrast, direct LLM-based judgment provides less effective source attribution feedback, making it more difficult for the agent to avoid the unsafe action while continuing its original benign objective. The findings highlight the advantage of our graph-based unsafe source attribution in supporting effective agent recovery.

We've already added this ablation study to Section 4.3 in our revised version of manuscript.

AuthorsOpenReview ↗

Response to Reviewer KB5v (3/3)

Q3. What are the exact predefined global constraints in VconsV^{cons}, and were baseline methods provided access to equivalent global rules?

R6: We thank the reviewer for raising this important question. For global constraints in VconsV^{cons}, we summarize the most common harmful outcomes of agent actions based on recent agent security surveys [3]. Our constraints focus on four key dimensions, covering most common risks posed by current agents to individuals, private information, and local and external resources. Due to space limitations, we've already provided the exact predefined constraints in Appendix F of our revised manuscript.

Importantly, these constraints are predefined and task-independent, capturing common agent harmful action outcomes rather than enumerating all possible risks. Our experimental results also demonstrate that these constraints are already enough to provide substantial safety improvements. Moreover, VEGAS is flexible and extensible: when new risks are identified, additional harmful action outcomes can be incorporated into the constraint set to provide more comprehensive protection.

Regarding baseline fairness, model-based guardrails are trained using their own curated rules and associated rule libraries, so the exact rules are difficult for us to reconstruct. Prompt-injection-specific defenses focus on analyzing the relationships between agent actions and their associated content, without relying on a specific set of safety rules. For verification-based methods, including FormalJudge and AgentSpec, we use their officially provided rules in our main experiments. Here, for a more fair comparison, we additionally evaluate the two methods using our predefined global rules. As shown in the table below, although our constraints improve their performance, GraphGuard still achieves substantially better performance, suggesting that advantages of our method stem primarily from its graph-based representation and verification design, rather than merely from the safety constraints it employs.

AgentDojoASBMTA
ASR ↓UTL ↑ASR ↓UTL ↑ASR ↓
FormalJudge32.951.738.741.440.3
FormalJudge w/ VEGAS's rules22.843.635.120.415.3
AgentSpec37.056.334.348.059.2
AgentSpec w/ VEGAS's rules18.642.523.739.443.9
GraphGuard0.085.315.764.65.6

[3] Kim, J., Guo, W., Song, D., Berkeley, U. C., & Santa Barbara, U. C. (2026). Sok: Attack and defense landscape of agentic AI systems. USENIX Security 2026.

AuthorsOpenReview ↗

Look Forward to Further Feedback

Dear Reviewer KB5v,

We sincerely appreciate your thoughtful and constructive feedback, and we have carefully considered each of your comments. We have also made the necessary modifications to our revised version of manuscript. We hope you will find the response satisfactory and are eager to receive your further feedback.

Best, Authors

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

The paper introduces VEGAS, a graph representation of agent trajectories that captures instructions, information, authorizations, constraints, and actions. It formulates safety as source legitimacy and effect benignity, checked through explicit graph properties. Its runtime implementation, GraphGuard, incorporates impact-aware verification and witness-guided recovery. Experiments across three benchmarks and three agent backbones show reduced attack success rates while largely preserving benign-task utility.

Critical strengths
  1. The graph representation explicitly separates behavioral sources, authorizations, and outcome constraints. Combining source legitimacy with effect benignity provides a useful framework for analyzing different agent risks and tracing the evidence behind safety decisions.
  2. Witness-guided recovery enables the agent to continue benign objectives after an unsafe action is blocked. This is practically valuable, and the reported results demonstrate a promising balance between attack prevention and task completion.
Critical weaknesses

The construction of influence edges relies on the agent’s reasoning text to identify what caused an action and its argument choices (Section 3.2 and Appendix F). Such explanations may be incomplete or unfaithful to the actual influences on behavior. Consequently, a malicious dependency could be omitted from the graph and escape subsequent deterministic checks. Although the paper acknowledges compiler limitations, the reported attribution accuracy on blocked actions does not directly establish robustness against this failure mode. This leaves uncertainty about the reliability of a central component.

Questions for authors
  1. How are influence edges constructed when the agent’s reasoning is unavailable, incomplete, or inconsistent with its action? Is there a fallback beyond relying on the reasoning text?

  2. Have you evaluated cases where malicious content affects an action but is absent from, or explicitly denied in, the agent’s reasoning?

5 comments
AuthorsOpenReview ↗

Response to Reviewer F1f3 (1/2)

We sincerely thank the reviewer for the thoughtful and constructive feedback. We especially appreciate your positive remarks on the usefulness of our graph representation on analyzing and tracing agent risks, as well as the practical value of witness-guided recovery. Below, we carefully address your concerns in Weaknesses and Questions, and we hope you could find our responses satisfactory.


Weakness & Q2. The construction of influence edges relies on the agent reasoning, but such reasoning may be incomplete or unfaithful to the actual influences on behavior. Have you evaluated these cases?

R1: To address your concern on reliability and faithfulness of influence-edge construction using agent reasoning, we randomly sample 50 trajectories from the experimental results of each model on each benchmark (450 in total). For each agent action in trajectories, we manually examine the instructions it follows and the information it uses, based on the semantics of the action and the choices of its arguments. In particular, we mainly focus on three commonly discussed aspects of agent reasoning faithfulness: completeness (whether the reasoning omits important information), soundness (whether the reasoning introduces fabricated or unsupported information), and deceptiveness (whether the reasoning deliberately provides misleading information) [1, 2, 3].

  • Type 1 (Completeness): The reasoning fails to mention an followed instruction or a piece of used information for a specific action.
  • Type 2 (Soundness): The reasoning incorrectly identifies an instruction or a piece of information as a source of the action, and it does not actually influence the action.
  • Type 3 (Deceptiveness): The reasoning indicates that an instruction or a piece of information is not a source of the action, but the action still follows that instruction or uses that information.

We then count the number of trajectories where these three types of reasoning errors occur.

DeepSeekGLMKimi
Type16 / 1503 / 1502 / 150
Type20 / 1501 / 1502 / 150
Type30 / 1500 / 1500 / 150

The results suggest that, in the vast majority of cases, agent reasoning can faithfully reflect the sources of its actions, with only a small fraction of cases exhibiting source omissions or false attributions. Moreover, among the 450 sampled trajectories, we do not observe any cases as illustrated in Q2, where an agent action is influenced by malicious or injected content and the reasoning either omits this source or explicitly denies relying on it. This observation is consistent with prior studies showing that the reasoning traces of current models struggle to hide their thought in the reasoning, and can provide useful signals for monitoring agent behaviors under standard evaluation settings [4, 5].

Nevertheless, we still acknowledge that discrepancies between an agent reasoning and the actual sources of its actions may occasionally occur and potentially affect the correctness of our method. Accordingly, we've already incorporated this limitation into our revised version of manuscript (Appendix J). Meanwhile, improving the faithfulness and monitorability of agent reasoning remains an active research direction in AI safety [5, 6], and we will also continue exploring this direction to improve agent monitorability and strengthen runtime safety protection.

[1] Chen, Y., Benton, J., Radhakrishnan, A., Uesato, J., Denison, C., Schulman, J., Somani, A., Hase, P., Wagner, M., Roger, F., Mikulik, V., Bowman, S. R., Leike, J., Kaplan, J., & Perez, E. (2025). Reasoning models don't always say what they think.

[2] Arcuschin, I., Janiak, J., Krzyzanowski, R., Rajamanoharan, S., Nanda, N., & Conmy, A. (2025). Chain-of-thought reasoning in the wild is not always faithful. ICML 2026

[3] Walden, W. (2026). Reasoning Models Will Blatantly Lie About Their Reasoning.

[4] Emmons, S., Jenner, E., Elson, D. K., Saurous, R. A., Rajamanoharan, S., Chen, H., Shafkat, I., & Shah, R. (2025). When chain of thought is necessary, language models struggle to evade monitors.

[5] Guan, M. Y., Wang, M., Carroll, M., Dou, Z., Wei, A. Y., Williams, M., Arnav, B., Huizinga, J., Kivlichan, I. D., Glaese, A., Pachocki, J., & Baker, B. (2025). Monitoring monitorability. ICML 2026.

[6] Yuan, W., Lin, C., Chen, J., Xu, J., Wang, X., & Ngai, E. C. H. (2026). Verify before you commit: Towards faithful reasoning in llm agents via self-auditing. ACL 2026.

AuthorsOpenReview ↗

Response to Reviewer F1f3 (2/2)

Q1. Are there any fallback methods beyond relying on agent reasoning?

R2: We also conduct an additional experiment to investigate whether our method can remain effective without relying on agent reasoning. Specifically, we disable agent reasoning to the GraphGuard compiler, and instead require the compiler to identify the source instructions and information only from the agent observable outputs and actions.

With DeepSeek-V4-Pro as a representative agent backbone, we evaluate the effectiveness of this fallback method using the same evaluation metric in our main experiment (attack success rate, ASR, and original task utility, UTL). In addition, we randomly sample 50 cases from each benchmark and manually inspect the constructed influence edges, counting the cases where edge construction contains errors.

AgentDojoASBMTA
ASR ↓UTL ↑Influence Edge Errors ↓ASR ↓UTL ↑Influence Edge Errors ↓ASR ↓Influence Edge Errors ↓
GraphGuard0.085.33 / 5015.764.62 / 505.63 / 50
GraphGuard (without reasoning)0.084.63 / 5016.866.33 / 509.16 / 50

The results show that this fallback method maintains GraphGuard's overall effectiveness with only a modest degradation, while still keeping the influence-edge construction errors relatively low, indicating that compiler is able to infer the action's influence source without reasoning, and can therefore construct reliable influence edges to enable effective safety protection even when the reasoning is unavailable.

The above analysis has already been added to Section 4.4 and Appendix J in our revised manuscript.

AuthorsOpenReview ↗

Look Forward to Further Feedback

Dear Reviewer F1f3,

We sincerely appreciate your thoughtful and constructive feedback, and we have carefully considered each of your comments. We have also made the necessary modifications to our revised version of manuscript. We hope you will find the response satisfactory and are eager to receive your further feedback.

Best, Authors

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of Responses and Changes in the Manuscript.

We sincerely thank all reviewers for the time and thoughtful feedback. We are encouraged that most reviewers appreciate the effectiveness of our graph-based representation design, as well as the practical usefulness of our witness-guided recovery design.

Besides the responses to all reviewers, we also carefully considered their suggestions and revised our manuscript accordingly. All changes are highlighted in blue in our revised manuscript. The details of these modifications are as follows:

  1. We have revised several statements to more precisely clarify the role of LLMs in our framework. (Section 1)

  2. We have refined the definitions of high- and low-impact actions to address potential security blind spots arising from malicious read/search queries. (Section 3.1 and Appendix C)

  3. We have provided additional details on the evaluated benchmarks, the evaluation protocols for attribution accuracy and compilation reliability, and the predefined global constraints. We have also included additional compilation reliability results to improve reproducibility. (Section 4.1, Appendix B.3, Appendix F, and Appendix G)

  4. We have conducted additional ablation studies to disentangle the contributions of graph-based representation and witness-guided recovery, along with further analysis of the reliability of agent reasoning. (Sections 4.3 and 4.4, and Appendix J)

  5. We have added uncertainty estimates to assess the statistical robustness of our experimental results, providing further evidence of GraphGuard's effectiveness when accounting for statistical uncertainty. (Appendix H)

  6. We have added definition of instruction-only trustworthy check, addressed the theoretical incompleteness of the proof of safety-faithful compilation, and corrected the definition typo of Influence closure. (Appendix A, Appendix B.2 and Appendix D).

We hope our responses have satisfactorily addressed your concerns and welcome any further comments or discussions!

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.