acceptodds
Under review as a conference paper at ICLR 2027

Recovering Structural and Semantic Constraints for LLM Agent Anomaly Detection

Abstract

Large language model (LLM) agents increasingly rely on external tools to accomplish complex tasks, exposing their execution processes to failures and attacks that may alter tool invocation sequences or their semantic dependencies. Existing defenses often focus on predefined rules or individual interactions, making it difficult to identify diverse and previously unseen anomalous behaviors. In this work, we demonstrate that normal agent executions themselves can provide reusable constraints for anomaly detection. We present TraceAegis, a framework that recovers structural and semantic constraints from historical agent execution traces. TraceAegis first organizes recurring tool interactions into hierarchical execution units and recovers structural constraints that characterize valid invocation flows. It further summarizes semantic constraints over these units to capture the contextual conditions under which tool interactions remain consistent with the intended task. At detection time, TraceAegis detects anomalous executions by identifying violations of either structural consistency or semantic coherence, allowing it to capture both unseen execution paths and previously observed paths with abnormal semantic dependencies. To evaluate the effectiveness of TraceAegis, we introduce TraceAegis-Bench, a benchmark containing 2,600 benign and 600 abnormal execution traces across healthcare and corporate procurement scenarios, and further evaluate TraceAegis on execution traces collected from an internal red-team exercise at a technology company. Across five LLM backbones, TraceAegis achieves higher F1 scores than the corresponding LLM-based baseline detectors in both scenarios. With DeepSeek-V3, it achieves F1 scores of 0.965 for clinical triage and 0.932 for corporate procurement.

Primary area:
foundation or frontier models, including LLMs
Keywords:
AI Agent, Anomaly Detection, Defense

Reviews

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

This paper presents TRACEAEGIS, a method for finding unusual behavior in an LLM agent's tool-use logs. It learns normal call patterns from past logs and uses an LLM to summarize the conditions associated with those patterns. It then checks whether new logs follow the learned call structure and conditions. The authors test it on simulated clinical triage and procurement tasks with five detector models. It improves F1 over the corresponding direct LLM detectors in both tasks. In a separate, authorized internal red-team test, it detects 132 of 140 deliberately created abnormal paths.

Critical strengths
  1. The idea is easy to understand and addresses a useful problem. A tool call can be wrong because it happens in the wrong order or because its content does not fit the task. The method checks both, using tool-use logs without needing the agent's internal reasoning.

  2. The reported gains appear across five detector models and both benchmark tasks. Removing either the structural or semantic component reduces performance in the reported clinical-triage tests. The authors provide the data-generation process and rule prompts. They also clearly state that the clinical tasks are simulated and that the internal security tests were authorized.

Critical weaknesses
  1. The comparison does not show how the method performs against other tools designed for this problem. Table 2 compares TRACEAEGIS with direct LLM detectors, while Section 5 discusses other methods that analyze execution logs or tool dependencies. Without comparisons with suitable examples of those methods, it is difficult to judge how much the new design adds. The baseline's access to historical normal logs should also be made clear.

  2. The benchmark covers two fixed workflows. This is useful evidence for those tasks, but five detector models do not mean five different types of agent workflow. Section 4.1 states that the profiling and test logs are separate. It is less clear whether they also use different task templates and request patterns. Table 1 shows different average path lengths across normal and abnormal examples, which is worth checking with a simple comparison based on length.

  3. The internal red-team result mainly shows how many created anomalies were found. Detecting 132 of 140 abnormal paths does not tell us how often normal paths were wrongly flagged. The paper also reports 1,087 tool responses, but responses and complete execution paths are different counting units. More path-level counts are needed to judge false alarms in this test. This concern does not apply to the main benchmark, which does include normal test paths.

4.The component tests are narrower than the main comparison. Table 3 removes the structural and semantic components only for clinical triage with two detector models. These results support both components in that setting, but do not show whether the same pattern holds for procurement. The paper also does not give processing time or show how the results change when fewer normal logs are used to learn the rules. These details would help assess its practical use.

Questions for authors
  1. What information does the direct LLM baseline receive? Does it get normal examples or a summary of normal behavior from the same historical logs? If feasible, could you compare TRACEAEGIS with a suitable existing trace-based detector from Section 5?

  2. Do the profiling and test sets share request templates, even though their logs are separate? Could you also test a simple detector that uses only the number of tool calls, given the length differences in Table 1?

  3. In the internal red-team test, were normal traces also checked? If so, how many were checked and how many were wrongly flagged? Which LLM produced the reported 132/140 result?

  4. Table 3 tests the two components only on clinical triage. Could you repeat the same comparison on procurement with one of the same LLMs, removing each component in turn?

  5. How long does it take to learn the rules from the normal logs, and how long does it take to check one new trace? If you repeated the LLM-based steps, how much did the detection results change?

2 comments
AuthorsOpenReview ↗

Response to Reviewer F8Vq

Response to Q1

The direct LLM baseline receives the candidate tool-call records, including inputs and outputs, together with a scenario-specific prompt describing the expected workflow and what constitutes anomalous behavior.

To address the difference in access to historical information, we added a RAG baseline that retrieves the top three complete normal traces from the same profiling corpus and provides them to the detector LLM. We also added comparisons with Inductive Miner and an adapted AgentArmor implementation. As reported in our response to common questions, TraceAegis achieves higher clinical F1 than these baselines with both backbones.

Response to Q2

Our profiling/test split is trace-level and may share request templates. As detailed in our response to Reviewer Cg4o on Data Generation and Generalization, normalized full-trace hashes do not overlap, and 41.33% of benign clinical test traces follow previously unseen complete tool-call paths. This establishes path variation, although it does not establish template-disjoint evaluation.

We also evaluated a length-only detector using the number of tool calls as its sole feature. For each scenario, we reserved 200 normal profiling traces for calibration and used the 2.5th and 97.5th length percentiles as bounds.

ScenarioRecallFPRF1
Clinical triage53.67%0.67%69.55%
Procurement36.67%0.00%53.66%

These results indicate that trace length can identify some anomalies, but its limited recall shows that length alone is insufficient for detecting the structural and semantic anomalies in the benchmark.

Response to Q3

The industry red-team results were obtained using DeepSeek-V3. The response-level FPR is 1.9% in the set of 1,087 tool responses. At the execution-path level, the evaluation includes only anomalous traces, of which TraceAegis detects 132/140 (94.3%). We therefore report recall at this level.

Response to Q4

We repeated the component ablation on procurement using GPT-OSS-120B. The results are shown below.

ConfigurationPrecisionRecallF1Accuracy
TraceAegis94.00%93.30%93.60%93.70%
w/o BC77.72%95.33%85.63%84.00%
w/o HS61.15%64.65%62.85%61.85%

Removing BC reduces F1 from 93.60% to 85.63%. Removing HS causes a larger decline to 62.85%, with both precision and recall decreasing. These results are consistent with the clinical ablation and support the contribution of both components in procurement.

Response to Q5

We measured the LLM request time for rule learning and detection separately on clinical triage using DeepSeek-V4.1-Flash-1017. Learning from 1,000 normal traces required an amortized 10.29 seconds per profiling trace, including batched extraction and shared rule summarization. Once the profile was built, detection required 23.79 seconds per test trace on average across the 600 test traces.

As reported in our response to Reviewer Cg4o on sensitivity, we repeated profiling and evaluation across different profiling sizes. The F1 standard deviations remained below 1.7 percentage points for both models, indicating consistent performance across repetitions.

Dear Reviewer F8Vq, thank you again for your helpful feedback, and we sincerely apologize for our late response. We would be grateful to learn whether our rebuttal resolves your concerns, and any further suggestions for improving the paper would be most welcome. Thank you for your time and consideration.

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

This paper presents TraceAegis, a framework designed to detect anomalous executions in LLM-based agents by enforcing structural and semantic constraints derived from historical benign tool-call traces. TraceAegis infers a global tool hierarchy, decomposes complex traces into fine-grained execution units, and leverages LLMs to extract, summarize, and verify semantic conditions. The authors also introduce TraceAegis-Bench, a benchmark comprising clinical triage and corporate procurement workflows, alongside a controlled industry red-team evaluation to demonstrate the system's effectiveness.

Critical strengths
  1. Practical Hybrid Architecture: Integrating structural profiling with LLM-based semantic checking provides a practical, automated approach to anomaly detection that significantly reduces reliance on manually written security policies.

  2. Empirical Effectiveness: The framework achieves consistent performance improvements over basic LLM detectors across evaluated scenarios, accompanied by thorough implementation details.

Critical weaknesses
  1. Missing Comparisons with Relevant Systems: While the empirical results demonstrate clear gains over direct LLM detection, the paper does not sufficiently position TraceAegis against existing trace- or policy-based agent monitoring frameworks (e.g., AgentArmor, SentinelAgent). These closely related systems are discussed in related work, but are neither evaluated empirically nor accompanied by an explanation of why they cannot be adapted to the evaluation setting.

  2. Limited Benchmark Realism and Workflow Diversity: Although TraceAegis-Bench provides per-category results and separates profiling from testing traces, the underlying task structures are relatively static—the clinical triage workflow is rigid, the procurement domain is strictly tree-structured, and the red-team setting follows a deterministic stage order. These environments offer limited validation for highly dynamic agent behaviors involving execution loops, retries, context-dependent tool roles, or novel legitimate execution paths. Furthermore, splitting benign and test sets at the individual trace level rather than at the task-template level risks optimistic evaluation.

Questions for authors
  1. Decomposition Assumptions: In Appendix B.1, under what rationale are tools DD and CC treated as same-level siblings despite not observing their reverse execution order? Under what formal assumptions does this decomposition reliably preserve precedence and dependency constraints?

  2. Semantic Verification expressiveness: How does the semantic checker distinguish between disjunctive (alternative) conditions and conjunctive (jointly necessary) constraints? Has the checker been evaluated against edge cases such as missing prerequisites, conflicting conditions, cross-call parameter associations, or null wildcard values?

  3. Ablation Clarity (w/o BC\text{w/o BC}): What exact components remain active in the "without Behavioral Constraint" (w/o BC\text{w/o BC}) ablation variant? Could you report its performance on AT-C1 and AT-C2 anomaly categories separately, and clarify whether AT-C2 traces adhere to the inferred structural profile?

  4. Baseline Parity and Comparison Scope: Do the baseline detectors receive access to the same benign profiling corpus and equivalent inference/token budgets? Could you include comparisons against a retrieval-augmented detection baseline or an existing structural/trace-based detector?

  5. Data Generation and Generalization: How are benign and anomalous traces generated, validated, and partitioned beyond simple trace-ID splitting? Specifically, what proportion of benign test traces contains previously unseen execution paths or novel execution-unit structures?

  6. False-Positive Rates and Sensitivity: What are the false-positive rates (FPR) on benign execution streams, particularly within the industry red-team setting? How sensitive are the detection metrics to variations in the size of the benign profiling set and stochasticity across repeated LLM runs?

2 comments
AuthorsOpenReview ↗

Response to Reviewer Cg4o

Response to Q1

C and D are assigned to the same level through level propagation. The path A → B → C establishes C’s level; when processing A → B → D → C → E, the algorithm places D at the same level as C to reconcile both paths. Thus, same-level assignment does not require observing both execution orders, nor does it prove that the tools are semantically independent.

Our method targets workflows with relatively stable tool-level ordering. Convergence ensures that the profiling paths are consistent with the recovered hierarchy, but does not guarantee recovery of all true dependencies.

Response to Q2

Our checker uses disjunction within each condition set and conjunction across the condition sets of an execution unit. For example, knee pain and arm pain are alternative conditions for an orthopedic referral. However, every condition set aligned with a tool-call position must match for the execution unit to pass.

Our dataset construction also includes corner cases such as missing prerequisites, where a tool invocation occurs without the required preceding step. These cases test whether the detector can identify violations of the expected execution structure or semantic constraints.

Response to Q3

The w/o BC variant retains hierarchy-based decomposition and applies direct LLM judgment to the resulting execution units. It removes behavioral-rule extraction and comparison against the learned constraints. The LLM can identify semantic anomalies from tool inputs and outputs.

Using GPT-OSS-120B on clinical triage, we report the category-level results.

VariantBenign correctly acceptedAT-C1 detectedAT-C2 detectedOverall F1
w/o BC257/300135/150141/15089.2%
TraceAegis277/300142/150149/15094.8%

Adding BC reduces false alarms on benign traces from 43 to 23 and improves detection in both anomaly categories.

AT-C2 traces are designed to adhere to the structural profile while violating semantic constraints. They follow valid tool-invocation patterns but introduce inconsistencies between tool inputs and outputs. Their detection requires semantic assessment, which remains active through direct LLM judgment in the w/o BC variant.

Response to Q4

We have added comparisons with a history-aware RAG baseline, Inductive Miner, and an adapted AgentArmor implementation, using the same designated benign profiling corpus and test split with method-specific inference settings. The details are provided in our response to common questions.

Response to Q5

We generate benign traces by executing valid tasks in clinical triage and procurement environments. AT-C1 traces are induced through out-of-scope requests or manipulated tool responses that alter execution flows, while AT-C2 traces introduce semantic inconsistencies, such as incorrect symptom-to-department mappings. For each scenario, 1,000 benign traces are used for profiling, and a separate set of 300 benign and 300 anomalous traces is used for testing.

We further audited the fixed clinical split by comparing complete ordered tool-call sequences against the profiling set:

Trace categorySeen complete pathUnseen complete pathOther structural violations
Benign1761240
AT-C118069
AT-C291410

Among benign test traces, 124/300 (41.33%) follow unseen complete paths composed entirely of known execution-unit types. No normalized full-trace hashes overlap between profiling and testing. The anomalous traces cover structural deviations and semantic inconsistencies, allowing us to evaluate both acceptance of valid path variations and detection of execution anomalies.

Response to Q6

We added a profiling-size sensitivity study on clinical triage using DeepSeek-V4.1-Flash-1017 and GPT-OSS-120B, varying the number of normal profiling traces from 50 to 1,000 while keeping the test set fixed. As shown in the table, increasing the profiling set substantially reduces false positives and improves F1.

DeepSeek-V4.1-Flash-1017

NRecallFPRF1
5098.99%81.78%70.24%
10098.54%57.22%76.84%
25098.31%27.78%86.84%
50098.31%12.33%93.27%
100098.31%1.67%96.45%

GPT-OSS-120B

NRecallFPRF1
5098.54%77.22%71.20%
10098.31%52.11%78.32%
25098.09%29.11%86.22%
50097.97%18.00%90.63%
100096.28%3.33%96.45%

We repeated profiling and evaluation multiple times across different profiling sizes. The F1 standard deviations remain below 1.7% for both models, indicating consistent performance across repetitions.

For the industry red-team evaluation, the response-level FPR is 1.9% in the set of 1,087 tool responses. At the execution-path level, the evaluation includes only anomalous traces, so we report recall.

Dear Reviewer Cg4o, thank you once more for your insightful comments, and we apologize for the delay in our response. We would greatly appreciate knowing whether our rebuttal has addressed your concerns, and we would be glad to hear any further suggestions you may have for improving the paper. Thank you for your time.

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

The paper proposes TraceAegis, a method for detecting abnormal LLM-agent behavior from tool execution traces. It assumes that normal traces can be used to learn valid behavior patterns. The method learns tool-call structures and uses LLMs to extract semantic rules. New traces are flagged if they break these rules. The authors introduce TraceAegis-Bench, with 2,600 normal and 600 abnormal traces from two simulated tasks. They test five LLM backbones and report F1 scores of 0.965 and 0.932 using DeepSeek-V3. Ablation studies test the two main components. An internal red-team test also detects 132 of 140 crafted anomalies.

Critical strengths
  1. The paper attempts to address an important problem in LLM-agent safety by detecting abnormal tool interactions without requiring access to internal reasoning or prompts.

  2. The method combines structural and semantic checks to detect both unusual tool sequences and inconsistencies between tool inputs and outputs.

  3. The experiments show consistent improvements over LLM-based baselines across five backbone models. The ablation studies and internal red-team evaluation provide further evidence of the method's effectiveness.

Critical weaknesses

1. Normal vs. abnormal behavior

The proposed framework follows a one-class anomaly detection approach. But how can the learned constraints reliably separate normal and abnormal agent behavior? Their execution patterns may overlap, and the paper does not really discuss how to handle this.

2. Reliability of learned constraints

The structural and semantic rules come from historical observations, not actual task requirements or planning rules. Just because a tool sequence appears often does not mean it is correct. Similarly, a new sequence is not necessarily abnormal. It is unclear whether these learned rules can reliably represent valid agent behavior.

3. Limited novelty

The method seems quite similar to existing work on log anomaly detection, process mining, and specification mining. The paper needs to better explain what is actually new here, beyond applying these ideas to LLM agents.

4. Benchmark and evaluation concerns

Why is TraceAegis-Bench needed in the first place? The paper does not clearly explain what existing benchmarks are missing. Also, the new benchmark is built around the same structural and semantic anomalies that the proposed method is designed to detect. This may favor the method in evaluation.

More importantly, there are no comparisons with established anomaly detection methods or evaluations on independent benchmarks. This makes it hard to tell how much improvement the method really brings or how well it would work in other agent environments.

Questions for authors
  1. How can the authors show that the structural and semantic constraints learned from historical traces reflect actual task requirements rather than just commonly observed patterns? How does the method handle legitimate but unseen behaviors?

  2. Why is TraceAegis-Bench needed when existing agent benchmarks are available? Since its anomaly categories closely match the proposed method, how can the authors show that the evaluation is not biased toward their approach?

  3. What is fundamentally new in TraceAegis compared with existing log anomaly detection, process mining, and specification mining methods? Which technical component provides the main novelty?

2 comments
AuthorsOpenReview ↗

Response to Reviewer so8j

Response to Q1

We assume that a large collection of normal execution traces captures the structural and semantic constraints of expected behavior, following prior work on log-based anomaly detection in software and system security (Zeng et al., 2022; Du et al., 2017). The key challenge is to extract general behavioral patterns from complex agent executions. We therefore recover a tool hierarchy, split traces into execution units, and summarize their semantic constraints. These constraints provide an empirical reference for task requirements.

For legitimate but unseen behavior, a new path can still pass if it combines known execution units and satisfies their constraints. We also acknowledge that genuinely unprofiled behavior may trigger false alarms. However, in industrial deployments, particularly for business agents with established workflows, such deviations warrant closer inspection. Once confirmed as legitimate, these behaviors can be incorporated into the profile.

Response to Q2

We introduced TraceAegis-Bench because existing benchmarks primarily focus on prompt injection, while our goal is to examine broader anomalies in agent execution, including complex invocation flows and semantic inconsistencies without explicit injected instructions. We built two MCP-based agent environments to capture these behaviors and released the data to support further research on agent anomaly detection.

To evaluate beyond our constructed workflows, we also added comparisons on an AgentDojo-derived subset covering banking, Slack, travel, and workspace tasks. As reported in the common response, TraceAegis achieves an F1 of 97.93%, matching RAG and exceeding the other two baselines. These results provide additional evidence beyond TraceAegis-Bench.

Response to Q3

We connect agent anomaly detection with log-based anomaly detection in software and system security. Our main technical contribution is the hierarchical structure recovery and execution-unit decomposition algorithm. It extracts recurring operations from complex traces, allowing us to learn more specific behavioral constraints instead of summarizing several mixed operations as one behavior.

We further view semantic checking as an information-flow check: within each execution unit, we summarize conditions from tool inputs and outputs and check whether their relationships remain consistent with the task. This detects semantic anomalies even when the tool-call pattern is familiar. The combination of hierarchical decomposition and semantic constraint learning provides a concrete way to apply the log-analysis perspective to agent executions.

Dear Reviewer so8j, thank you again for your valuable feedback, and we apologize for our late response. We would be grateful to know whether our rebuttal addresses your concerns, and we would sincerely welcome any further suggestions for improving the paper. Thank you for your time.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Response to common questions

Additional baseline comparisons and evaluation across datasets

To address the shared concerns about baseline strength and generalization beyond the two benchmark workflows, we conducted additional comparisons with three baselines:

  • Retrieval-augmented detection (RAG): This baseline retrieves the three most relevant complete normal traces using TF-IDF fitted exclusively on the profiling corpus. The retrieved traces, including tool inputs and outputs, are provided alongside the candidate trace to the detector LLM.
  • Inductive Miner: We use PM4Py for process discovery and alignment-based conformance checking. We additionally incorporate a TF-IDF attribute check over tool inputs and outputs, allowing this baseline to assess both execution structure and content.
  • AgentArmor: We implement an adapted version incorporating offline dependency inference, integrity and confidentiality propagation, policy inspection, and application-specific workflow checks to enable fair comparison.

We evaluate these methods on the clinical triage dataset and an AgentDojo-derived subset covering banking, Slack, travel, and workspace tasks. Within each comparison, methods share the designated profiling and test split. In addition to GPT-OSS-120B, we evaluate DeepSeek-V4.1-Flash-1017 as a second detector backbone.

Clinical triage — GPT-OSS-120B

MethodPrecisionRecallF1
TraceAegis96.56%96.23%96.40%
RAG88.93%79.79%84.12%
Inductive Miner92.78%83.56%87.93%
AgentArmor94.51%58.90%72.57%

Clinical triage — DeepSeek-V4.1-Flash-1017

MethodPrecisionRecallF1
TraceAegis98.31%98.31%98.31%
RAG89.25%84.12%86.61%
Inductive Miner92.88%83.78%88.10%
AgentArmor95.24%81.08%87.59%

AgentDojo-dataset— DeepSeek-V4.1-Flash-1017

MethodPrecisionRecallF1
TraceAegis97.26%98.61%97.93%
RAG97.26%98.61%97.93%
Inductive Miner96.15%69.44%80.65%
AgentArmor85.71%100.00%92.31%

On clinical triage, TraceAegis achieves the highest F1 with both backbones, outperforming the strongest competing baseline by 8.47 and 10.21 percentage points, respectively. On the AgentDojo-derived subset, TraceAegis also achieves strong results, although the gains are smaller than those on TraceAegis-Bench. This is expected, as the attacks in this subset are simpler and easier to detect.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.