- 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
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 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 Type | Observed 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.
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_instructionsmethod, 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_attackstrategy, 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
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!
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
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
WeaknessesandQuestions, 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).
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.