cs.CROct 29, 2026

Judging Before Propagation: Task-Graph Contextual Integrity for Multi-Agent Privacy

Authors: Hengyu Wu, Blaise Delattre, Yang Cao

Organizations: Department of Computer Science, School of Computing, Institute of Science Tokyo

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

Multi-agent LLM systems increasingly rely on persistent memory and inter-agent communication. These capabilities create privacy risks that extend beyond individual interactions: a release appropriate in isolation may become inappropriate when combined with information previously disclosed to a recipient or propagated to downstream agents along the planned workflow. Existing Contextual Integrity (CI) mechanisms for agentic systems typically rely on local judgments that assess each disclosure in isolation, with or without regard to the recipient's history, but do not account for how information propagates downstream. However, compliance at the current boundary does not guarantee appropriateness across the workflow. We introduce Task-Graph Contextual Integrity (TG-CI), to our knowledge the first task-graph-native formalization of Contextual Integrity for multi-agent systems. TG-CI represents a workflow as a Multi-Agent Task Graph (MATG) and extends CI from atomic transfers to stateful, graph-level information flows by jointly considering an item's intended propagation scope and recipients' evolving disclosure states. We operationalize TG-CI through propagation-scoped authorization under two complementary policies: Full-Scope, which requires admissibility across the complete downstream scope, and Auto-Region, which confines each item to its maximal admissible region using lightweight frontier gates. We further introduce MAPLE-Bench, a benchmark of 144 cases across four scenarios that jointly vary MATG topology, disclosure history, compromised-agent placement, and item-level privacy policies. In our primary experimental configuration, TG-CI reduces the mean unauthorized disclosure count by 85.8-94.1% relative to the Local-History CI baseline, while retaining 93.6-96.1% of the baseline's task accuracy, with the two enforcement policies providing complementary privacy--cost--utility trade-offs.

Figures & tables

Figure 1: Three failure patterns in multi-agent systems. Direct disclosure violations occur when the current transfer itself is contextually inappropriate. Sequential Cumulative disclosure violations occur when a current disclosure combined with previous disclosures could reveal inappropriate sensitive information. Transitive disclosure violation occurs when an initially appropriate disclosure would propagate to an inappropriate downstream recipient along the foreseeable task workflow.
PaperCI GroundedDirect DisclosureCumulative DisclosureTransitive Disclosure
AirGapAgent ( Bagdasarian et al., 2024 )YYNN
The Sum Leaks ( Patil et al., 2025 )NNYN
OCELOT ( Xie & Li, 2026 )YYYN
Minim ( Yu et al., 2026 )YYNN
CAMP ( Panjwani, 2026 )NYYN
TG-CI (Ours)YYYY
Table 1: Comparison of related work on multi-agent privacy evaluation and protection.
Figure 2: Overview of the operationalization of TG-CI and two enforcement policies.
Figure 3: Privacy–cost trade-off across four application scenarios. Stacked bars decompose the mean Unauthorized Disclosure Count into mutually exclusive direct, cumulative, and transitive violations (left axis). The dashed line reports Judge Execution Token Count (right axis).
Figure 4: Mean number of distinct inappropriate memory items exposed to compromised agents across four application scenarios.
 Haiku–LunaHaiku–HaikuLuna–Luna
ConditionUtility Scorevs. NP / LH-CIUtility Scorevs. NP / LH-CIUtility Scorevs. NP / LH-CI
No Protection80.97%(—,97.25%)81.04%(—,103.82%)94.72%(—,98.55%)
Local-History CI83.26%(102.83%,—)78.06%(96.32%,—)96.11%(101.47%,—)
Online Atomic CI80.69%(99.65%,96.91%)74.04%(91.36%,94.85%)88.47%(93.40%,92.05%)
TG-CI Auto-Region80.00%(98.80%,96.08%)68.40%(84.40%,87.62%)92.22%(97.36%,95.95%)
TG-CI Full-Scope77.92%(96.23%,93.58%)62.22%(76.78%,79.72%)88.06%(92.96%,91.62%)
Table 2: Task utility across agent–judge model assignments. Utility Score denotes mean multiple-choice accuracy in percentage points. Values in parentheses report score relative to No Protection and Local-History CI, respectively.
Figure 5: Mean unauthorized disclosure count (left axis) across chain, tree, and branching MATG topologies for four application scenarios.
Appendix figures & tables9 assets

Supplementary material from the paper’s appendix.

Appendix

(a) Domain distribution
DomainWorkflowsCasesOne attackerTwo attackers
Healthcare1236279
Finance1236279
Corporate HR1236279
Lifestyle1236279
Total4814410836
Appendix
Table 3: MAPLE-Bench composition and statistics. Each of the 48 workflows is instantiated under three MATG topologies, yielding 144 cases. Attacker counts and position distributions are reported at the case level. PiP_{i} represent agent in i -th position.
ComponentContent
TaskPlease confirm my agreed return date, the first-week hours, and whether my fit note is signed. Find a rehabilitation review-call slot that fits my availability and the right place and day to collect my own paperwork copies.
Two-fact questionWhich offered rehabilitation review call slot meets both the patient’s availability and the service timetable?
Answer optionsA. Thursday at 10:30 B. Thursday at 15:30 C. Tuesday at 15:30 D. Tuesday at 10:30
Memory item 1appointment_availability Storage: owner-private; owner: records_agent . “For the rehabilitation review call, the patient can attend on Thursday only. Either 10:30 or 15:30 is acceptable on that day.”
Memory item 2appointment_slot_catalog Storage: shared. “The rehabilitation review call service currently offers 15:30 on both Tuesday and Thursday. It offers no 10:30 slot on either day.”
Correct answerB: Thursday at 15:30.
Appendix
Table 4: Example of two-fact question answering in MAPLE-Bench. The correct answer requires combining the patient’s availability with the service timetable. Memory storage types and ownership are shown alongside the original item contents.
Figure 6: Privacy–cost trade-off result under Haiku–Haiku agent-judge configuration. Stacked bars decompose the mean Unauthorized Disclosure Count into mutually exclusive direct, cumulative, and transitive violations (left axis). The dashed line reports Extra Execution Token Count relative to No Protection (right axis).
Figure 7: Privacy–cost trade-off result under Luna–Luna agent-judge configuration. Stacked bars decompose the mean Unauthorized Disclosure Count into mutually exclusive direct, cumulative, and transitive violations (left axis). The dashed line reports Extra Execution Token Count relative to No Protection (right axis).
Figure 8: Mean number of distinct inappropriate memory items exposed to compromised agents under Haiku–Haiku agent-judge configuration.
Figure 9: Mean unauthorized disclosure count (left axis) across chain, tree, and branching MATG topologies under Haiku–Haiku agent-judge configuration.
Figure 10: Mean number of distinct inappropriate memory items exposed to compromised agents under Luna–Luna agent-judge configuration.
Figure 11: Mean unauthorized disclosure count (left axis) across chain, tree, and branching MATG topologies under Luna–Luna agent-judge configuration.
Model labelManuscript aliasModel identifier
GPTLUNAgpt-5.6-luna
ClaudeHAIKUclaude-haiku-4-5-20251001
Appendix
Table 5: Model identifiers and their corresponding manuscript aliases.
More in this topic

Privacy Protection for LLM Agents

See all 37 papers

Explore similar work

CardsList
Oct 13, 2026

AgentCIScope: Grounded Contextual Integrity Evaluation for LLM Agents

LLM agents are becoming increasingly capable of handling daily workspace tasks by interacting with application environments through tool calls. However, as agents read and write sensitive user data across email, documents, and other applications, a central privacy question is whether they preserve contextual integrity (CI), that is, whether the information flows they produce comply with context-specific disclosure constraints. Existing work either focuses on model-level privacy leakage or evaluates agents in limited application environments with manually constructed disclosure constraints. In this work, we introduce AgentCIScope, a unified platform and benchmark for evaluating agent-level contextual integrity through executable, multi-step tasks across diverse, realistic application environments. AgentCIScope transforms public and synthetic privacy cases into executable agent tasks, with disclosure constraints grounded in three criteria: governing privacy policies, persona-based agreement, and a predefined sensitive-attribute taxonomy. Based on AgentCIScope, we evaluate 12 agents on 936 tasks and find that strong task-completion capability does not guarantee contextual-integrity preservation: single-run leakage rates range from 32.5% to 94.4%, while repeating each task five times further increases leakage by 4-19 percentage points. Leakage varies substantially across attributes: personal preferences and booking details have average leakage rates of 84.7% and 76.5%, compared with 17.1% for credit-card information and 29.4% for SSNs; environments: calendar has the highest average leakage rate as an information source, while WhatsApp ranks highest as an information destination; and governing privacy policies. AgentCIScope provides deep insights into agent privacy leakage and serves as a unified testbed for developing privacy-preserving agents.

Chengquan Guo, Zhaorun Chen, Zinan Lin +2

University of Chicago · Microsoft Research · University of Illinois Urbana-Champaign

Privacy Protection for LLM AgentsContextual IntegrityLLM Agent EvaluationLLM Agent SecurityAI Agent Security Benchmarks
AskPDF
Jul 6, 2026

PiSAs: Benchmarking Contextual Integrity in Multi-User Agentic Systems

As LLM agents evolve from single-user assistants into shared organizational infrastructure, new privacy risks emerge: inappropriate information may not only be exposed through outputs for external recipients, but also internally across users through inter-agent messages, shared memory and user-agent interactions. These data spillage risks are not captured by existing privacy benchmarks grounded in contextual integrity (CI) as they focus primarily on either single-user settings or interactions between independently owned agents. We introduce PiSAs (Privacy in Shared Agentic Systems), a benchmark for assessing unintentional leaks with dual CI annotations: whether a piece of information is appropriate for the task, and which users may legitimately access it. This enables direct measurement of cross-user spillage across agentic system components and interfaces, such as outputs, inter-agent communication, and memory. PiSAs is system-agnostic and supports evaluation across different agent topologies and memory regimes. We find that, although system design improves CI compliance, results are bottlenecked by incorrect LLM judgment calls: even state-of-the-art models fail to reliably filter inappropriate content or restrict transmission to authorized users. Our findings underscore the need for privacy-preserving strategies, beyond those studied in this work.

Shubham Gupta, Nazanin Mohammadi Sepahvand, Abhinav Kumar +6

ServiceNow AI Research · Mila – Quebec AI Institute · Université Laval +2

Multi-Agent LLM SystemsContextual IntegrityAI Agent SecurityAI Agent Security Benchmarks
AskPDF
Mar 5, 2026

AgentSCOPE: Evaluating Contextual Privacy Across Agentic Workflows

Agentic systems are increasingly acting on users' behalf, accessing calendars, email, and personal files to complete everyday tasks. Privacy evaluation for these systems has focused on the input and output boundaries, but each task involves several intermediate information flows, from agent queries to tool responses, that are not currently evaluated. We argue that every boundary in an agentic pipeline is a site of potential privacy violation and must be assessed independently. To support this, we introduce the Privacy Flow Graph, a Contextual Integrity-grounded framework that decomposes agentic execution into a sequence of information flows, each annotated with the five CI parameters, and traces violations to their point of origin. We present AgentSCOPE, a benchmark of 62 multi-tool scenarios across eight regulatory domains with ground truth at every pipeline stage. Our evaluation across seven state-of-the-art LLMs show that privacy violations in the pipeline occur in over 80% of scenarios, even when final outputs appear clean (24%), with most violations arising at the tool-response stage where APIs return sensitive data indiscriminately. These results indicate that output-level evaluation alone substantially underestimates the privacy risk of agentic systems.

Ivoline C. Ngong, Keerthiram Murugesan, Swanand Kadhe +3

University of Vermont · IBM Research

AI Agent EvaluationAgentic WorkflowsContextual Integrity
AskPDF