- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper argues that existing Contextual Integrity (CI) defenses for LLM agents judge each disclosure locally, possibly with the recipient's history, and so miss "transitive" leaks, where a disclosure that is fine at the first hop later travels to an inappropriate downstream agent. It proposes Task-Graph Contextual Integrity (TG-CI). The workflow is modeled as a fixed Multi-Agent Task Graph (MATG). A memory item is judged together with its intended propagation scope P (a rooted subgraph), and it is admissible only if every atomic CI flow on every edge of P is admissible given the recipient's disclosure state D_t (Eq. 11). Two enforcement policies are given. Full-Scope releases an item only if the entire downstream closure of the requester is admissible. Auto-Region releases the item over the maximal rooted admissible region and installs "frontier" filters on the edges where the region ends. These filters use MiniLM similarity plus DeBERTa NLI to strip matching claims from inter-agent messages. The authors also release MAPLE-Bench: 144 synthetic cases (48 workflows x 3 topologies) in four domains, each with 4 agents, 30 memory items, an item-recipient policy matrix, 2 cumulative fact-pair rules, and 5 multiple-choice questions. In the main HAIKU-LUNA setting, averaged over scenarios, the mean unauthorized disclosure count is 15.84 (No Protection), 10.47 (Local-History CI), 6.11 (Online Atomic CI), 1.49 (Auto-Region) and 0.62 (Full-Scope) (Section 5.3). Utility stays at 93.6-96.1% of Local-History CI. The cost is a higher judge-token count.
Critical strengths
- Relevant, well-motivated problem: Privacy leaks across multi-hop agent workflows (direct, cumulative and transitive, Figure 1) are a real and growing concern. Separating transitive disclosure as its own failure mode is a useful framing.
- Conceptual separation: The paper keeps three things apart: the MATG, the per-item propagation scope, and the recipient disclosure state. Atomic five-parameter CI is kept at each edge (Eqs. 8-11). The conservative-state argument (Appendix A) and the transaction-local tentative state for items within one response (Section 4).
- Practical design: Auto-Region with item-specific frontier gates is a sensible engineering idea. It does costly semantic inspection only on edges where a protected item must be removed. Messages to non-MATG neighbors are blocked outright.
- Reasonable reporting breadth: The paper decomposes leaks into direct, cumulative and transitive parts (Figure 3). It reports compromised-agent exposure as distinct items rather than events (Figure 4), breaks results down by topology (Figure 5), and covers three agent-judge model pairings (Table 2, Appendix C). It provides the judge rubric and schema (Appendix F) and promises code and data.
Critical weaknesses
Even with the strengths the work has the following limitations:
-
Limited technical novelty: TG-CI is the conjunction of per-edge CI checks over a reachable subgraph (Eq. 11). Auto-Region is a reachability expansion that stops at the first inadmissible edge (Eq. 13). Binding a label or authorized scope to data and enforcing it at downstream boundaries is the central idea of classic information-flow control and taint tracking. The paper itself cites agent IFC systems that do this (Costa et al., 2025; Debenedetti et al., 2025). The paper does not explain what TG-CI adds over "IFC labels whose allowed sinks are decided by an LLM CI judge", and it does not compare against such systems. There are no theorems or guarantees beyond the short monotonicity argument in Appendix A. The "first task-graph-native formalization" claim therefore rests mostly on notation. Table 1, which marks only TG-CI as covering transitive disclosure, leaves out IFC-based agent defenses.
-
Possible circularity between the judge's inputs and the ground truth: The ground truth is the policy matrix Y (Y_{i,v} = 1 iff v may receive m_i) written by the benchmark authors (Section 5.1). The judge receives "applicable norms" and a recipient task for every edge (Appendix F, Listing 2). The paper does not say how these norms are produced per case, or whether they are derived from, or written alongside, Y. If the norms encode Y nearly directly, the judge becomes close to an oracle lookup, and the large gains mostly reflect the fact that TG-CI queries that lookup on every downstream edge. The paper also never measures the judge's own accuracy (precision/recall of Adm_t against Y), so we cannot tell how much of the result comes from the graph mechanism and how much from the judge.
-
The comparison with Online Atomic CI is unclear and may be confounded: Online Atomic CI "applies the same edge-level atomic CI used by TG-CI independently at every realized memory and inter-agent transfer" (Section 5.2). If every realized transfer is checked with the same judge, it is not clear why transitive leaks remain its "dominant residual source" (Section 5.3).
-
The cost argument does not fit the results: Contribution (2) says the design "avoids expensive and repeated contextual re-evaluation along downstream routes". Yet both TG-CI modes use more judge tokens than Online Atomic CI in every scenario. In Healthcare, for example, the counts are 117.3K (Online Atomic CI), 126.8K (Auto-Region) and 130.6K (Full-Scope) (Figure 3a). The cost metric also leaves out MiniLM/DeBERTa inference (Section 5.2). No latency or wall-clock numbers are given. The efficiency claim is not supported as stated.
-
The utility cost is understated: The abstract and Section 5.5 stress 93.6-96.1% retention, but this holds only for HAIKU-LUNA. Under HAIKU-HAIKU, Full-Scope falls to 62.22%, compared with 78.06% for Local-History CI and 81.04% for No Protection, which is about 77% of No Protection utility (Table 2). The paper should report, and analyze, false blocking (task-necessary items wrongly withheld), using the "7 necessary" items annotated in Table 3.
-
The threat model is not instantiated in the experiments: Section 2 describes compromised agents that "deviate arbitrarily", issue overbroad memory requests, misrepresent task necessity, and transform content. Section 5 never says how compromised agents are implemented: what prompts, what attack strategies, and whether they adapt to the defense. Two points matter in particular. (a) The frontier gate relies on fixed thresholds (cosine 0.35, NLI 0.70; Appendix D), and an adaptive adversary could paraphrase or combine items to evade it. (b) Appendix E admits that semantic transformations by intermediate agents are not modeled. Without adaptive attacks, the "compromised-agent exposure" results (Figure 4) say little about robustness.
-
Strong assumptions limit applicability: The MATG must be fixed and known before execution, with no dynamic replanning (Section 4). Each node's subtask and each edge's transmission rule are trusted. Memory must be split into clean <subject, attribute, value> items. In practice, task graphs in agent systems are often emergent, and an attacker who can influence planning or subtask descriptions can widen the authorized scope. None of these assumptions are stress-tested.
-
The benchmark is narrow and designed around the method: The benchmark has 4 agents per case, shallow graphs, 2 cumulative rules per case, and items, policies and questions synthesized with generative AI (AI Use Statement). It was built to exhibit exactly the three failure modes TG-CI targets, which favors the method. No existing benchmark is used for evaluation, although several are discussed (AgentLeak, PiSAs, AgentSCOPE, MAMA; Section 5.1). Results on at least one external benchmark would greatly increase confidence.
-
Missing baselines: OCELOT and CAMP are skipped because no public code was available (Section 5.2). Both are described in papers and could be reimplemented in simplified form. Other natural baselines are also missing: a static IFC/label baseline that enforces Y directly, AirGapAgent-style minimization, and a "downstream-aware prompt" baseline where the local judge sees the downstream task graph in one call.
Questions for authors
See weaknesses
3 comments
Author Response (2/2): Additional Experimental Analysis and Clarification
W5. Utility retention and false-blocking analysis.
We thank the reviewer for highlighting. The retention reported in the abstract corresponds to our designated primary Haiku–Luna setting. We additionally measured Full-Scope task-necessary item withholding rates: 18.45% (Claude/GPT), 34.16% (Claude/Claude), and 17.07% (GPT/GPT). With Claude agents fixed, the Claude judge exhibits substantially higher false blocking and lower Full-Scope utility, despite nearly identical unprotected task accuracy. These findings suggest that judge reliability is an important factor in the privacy–utility trade-off, motivating improvements in judge capability and calibration. We will incorporate this analysis alongside the W2 judge evaluation in the revision.
W6. Threat-model instantiation and adversarial robustness.
We conducted a prompt-induced paraphrasing stress test, where mean unauthorized disclosures increased from 1.488 to 1.727 for Auto-Region and 0.624 to 0.637 for Full-Scope. Both variants retain substantial containment, with Full-Scope showing greater resilience. TG-CI's conservative disclosure-state accounting tracks authorized items independently of wording, while Full-Scope additionally prevents inappropriate information from entering the workflow. However, we acknowledge fixed MiniLM/NLI thresholds remain vulnerable to semantic evasion, and this preliminary test does not establish robustness against fully adaptive adversaries.
Our focus is TG-CI's formalization, framework, and proof-of-concept validation, while systematic robustness evaluation and enforcement are for future work. We will include these results and clarify the attack scope and limitations in the revised manuscript.
W7. Fixed workflow and structured memory assumptions.
We acknowledge these assumptions and clarify their scope. As stated in the paper, supporting dynamic replanning is left to future work, as it would require an additional trusted graph-monitoring mechanism to detect changes and update authorizations. Our present work instead focuses on the formulation, enforcement framework, and empirical validation of TG-CI under a predefined, trusted MATG. Regarding structured memory, the <subject, attribute, value> representation does not necessarily require manually curated records: such information can often be extracted from contextual descriptions or existing memory using information-extraction techniques. We will clarify these assumptions and limitations in the revision.
W8. Benchmark representativeness and external validation.
Our benchmark is designed to jointly evaluate direct, cumulative, and transitive privacy leakage in task-driven multi-agent workflows. MAMA primarily studies topology-dependent private-memory extraction, making its evaluation focus different from ours. Nevertheless, we adapted the MAMA dataset to our framework to examine whether our findings generalize beyond our constructed scenarios. Mean unauthorized disclosures per run on 150 runs:
| Method | Memory | On-graph | Final | Off-graph | Total ↓ | Utility ↑ |
|---|---|---|---|---|---|---|
| No Protection | 3.240 | 4.573 | 0.993 | 2.100 | 10.907 | 71.85% |
| Local-History CI | 0.000 | 0.093 | 0.053 | 0.180 | 0.327 | 67.75% |
| Online Atomic CI | 0.000 | 0.020 | 0.000 | 0.073 | 0.093 | 69.95% |
| TG-CI Auto-Region | 0.000 | 0.040 | 0.020 | 0.000 | 0.060 | 70.08% |
| TG-CI Full-Scope | 0.000 | 0.000 | 0.000 | 0.000 | 0.000 | 69.00% |
The results follow the similar trend as our original benchmark. Auto-Region reduces leakage by 35.7% relative to Online Atomic CI with comparable utility, while Full-Scope achieves zero observed violations. Utility reductions relative to No Protection remain modest; as explained in our response to KAfd–Q5, less privacy filtering does not guarantee that agents retrieve or correctly use the required information. These findings provide complementary evidence of TG-CI's privacy–utility benefits, although the two benchmarks are not directly comparable due to their different evaluation objectives. We will include the results and adaptation details in the revision.
W9. Comparison with additional privacy defenses.
We thank the reviewer for suggesting additional baselines. Our IFC comparison is addressed in W1. We additionally implemented an AirGapAgent-style data minimization baseline within our multi-agent framework. Under Claude/GPT, it incurred 15.652 unauthorized disclosures per run (5.937 memory, 8.413 off-graph, and 1.302 on-graph/final), consuming 34.1K defense LLM tokens.
We skip OCELOT and CAMP as OCELOT relies on a specialized fine-tuned defender model whose checkpoint was unavailable for reproduction, while CAMP targets cumulative PII exposure in multi-turn conversations through retroactive masking, rather than recipient-specific information flows across agents. We will incorporate the AirGapAgent-style comparison in the revised manuscript.
Thank you again for your valuable comments and constructive suggestions. We have carefully addressed your concerns in our rebuttal and provided additional clarifications where necessary. As the discussion period is limited, we would be most grateful if you could find a moment to look over our response and let us know whether our explanations have adequately addressed your questions. Should any concerns remain, we would be very happy to provide further clarification. Since our experiments take considerable time to complete, an early reply would be of great help in allowing us to prepare any additional results you may wish to see within the remaining discussion period. We sincerely appreciate your time and effort in reviewing our paper.
Author Response (1/2): Contribution, Norm Provenance, Leakage Analysis, and Cost Clarification
W1. Contribution and relationship to IFC.
We thank the reviewer for the opportunity to clarify the contribution. TG-CI contributes a contextual authorization formulation that makes downstream propagation and recipients’ evolving disclosure states part of the current privacy decision. For example, Full-Scope can withhold an otherwise locally admissible release because its downstream scope is inadmissible. TG-CI integrates this reasoning with flow enforcement, addressing both the determination and enforcement of disclosure permissions.
Our additional FIDES-based static reader-set baseline, supplied with oracle per-item permissions from Y, still incurs 1.688 unauthorized disclosures per run from combinations of individually permitted fragments. This exposes a limitation of static per-item permissions alone and motivates TG-CI’s history-conditioned judgments. We will revise the introduction to acknowledge IFC’s established propagation controls and distinguish them from TG-CI’s contextual authorization contribution.
W2. Norm provenance and atomic-judge evaluation.
Our norms were authored from common-sense privacy expectations and relevant legal principles to model organizational privacy requirements. They were neither copied nor derived from Y (specific item–recipient permission labels), which is excluded from runtime judgment. For example, Appendix F supplies: “Disclose only information appropriate for arranging the requested service, and no more revealing than needed.” Norms and annotations necessarily express the intended privacy objective, but this policy consistency is distinct from supplying the answers. Moreover, Online Atomic CI receives the same norm inputs, as discussed in response to reviewer KAfd - W4&Q3, so TG-CI does not obtain privileged access to evaluation labels.
We additionally evaluated Full-Scope's atomic judgments against Y, treating permit as the positive class:
These results demonstrate substantial but imperfect agreement with benchmark permissions. Under Claude/GPT, among 79 candidate releases incorrectly permitted by the immediate atomic judgment, Full-Scope prevented 24 (30.4%) through downstream CI vetoes. These observations provide direct evidence that prospective downstream adjudication can prevent some unauthorized releases that would otherwise pass immediate atomic CI checks, demonstrating additional protection beyond immediate judge accuracy.
W3. Leakage breakdown & analysis.
We thank the reviewer for identifying this potential confound. We conducted an additional channel-level audit and evaluated Online Atomic CI with the same MATG route guard used by TG-CI (see detailed results in our response to KAfd - W3&Q1). Under Online Atomic CI, 78.9% of unauthorized disclosures occur through off-graph messages (disclosures along sender–recipient routes absent from the approved MATG), despite per-transfer CI checking. Adding the TG-CI route guard eliminates off-graph leakage, demonstrating the value of explicit route restriction as an integral component of TG-CI’s enforcement.
Importantly, Full-Scope provides substantial additional protection even after controlling for route enforcement. Compared with route-guarded Online Atomic CI, Full-Scope reduces 51.7% unauthorized disclosures, including a 56.0% reduction in memory-release leakage and a 42.7% reduction in on-graph/final-output leakage, with only a 0.69-percentage-point utility decrease. Auto-Region instead offers a different privacy–utility trade-off: it preserving more utility than the guarded atomic baseline (78.61%) at the cost of slightly higher residual leakage. We will incorporate the analysis into the revised manuscript.
W4. Computational efficiency and token cost.
We thank the reviewer for highlighting this ambiguity. Avoiding repeated per-edge CI judgments does not necessarily reduce overall execution cost. TG-CI reuses prospective authorizations to avoid redundant downstream adjudication, but total cost also depends on the number of prospective edges evaluated, the natural information-exchange rate of the workflow, and changes in agents’ retrieval and communication behavior. For example, stricter source-level blocking may trigger additional memory requests. Accordingly, our results in Sec. 5 explicitly demonstrate a privacy–token-cost trade-off, with TG-CI achieving stronger privacy protection at moderately higher CI-judge token cost. We will refine our efficiency claim to emphasize the reduction of repeated downstream judgments without implying lower overall computational cost.