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

1 INTRODUCTION

• A disclosure acceptable in isolation can become unsafe through recipient-history aggregation or downstream propagation, while existing CI mechanisms largely judge transfers locally and leave task-structure-aware judgments underexplored.AgentSCOPE labels internal channels but evaluates each flow independently and provides no defense; trajectory-level privacy budgeting addresses cumulative risks, while downstream task structure remains comparatively underexplored.Source: §1 · pp. 1–2
• TG-CI evaluates each flow over a Multi-Agent Task Graph, preserving atomic Contextual Integrity judgments while accounting for intended propagation scope and recipients’ evolving disclosure states.It jointly considers direct, cumulative, and transitive disclosure risks.Source: §1 · p. 2
• Full-Scope blocks an item if any transfer in its complete downstream closure is inadmissible; Auto-Region contains it at the frontier of its maximal rooted admissible region.These policies avoid repeated contextual reevaluation along downstream routes and offer complementary trade-offs among privacy protection, computational cost, and task utility.Source: §1 · pp. 2–3
• MAPLE-Bench provides 144 cases across four application scenarios, varying MATG topologies, disclosure histories, and compromised-agent configurations for controlled privacy evaluation.Each case includes item-level memory, privacy policies, and ground-truth annotations for disclosure violations.Source: §1 · pp. 2–3

System model

• The workflow is a directed, labeled MATG whose edges represent planned, task-relevant delegations or information transfers, not merely technical communication links.The graph is G = (V, E, τ, π), with agents, planned edges, assigned subtasks, and edge transmission rules.Source: §2 · p. 3

Memory model

• Persistent memory stores items as subject, attribute, and value, and agents retrieve subsets through system-mediated access independent of whether memory is shared, agent-specific, or hierarchical.Every memory access is required to pass through a system-mediated interface.Source: §2 · p. 3

Adversary model

• Before execution, up to f agents may be compromised and arbitrarily manipulate monitored memory requests or messages; out-of-band channels and covert encodings are outside the threat model.The adversary observes information delivered to compromised agents and seeks protected information and inappropriate flows.Source: §2 · p. 3

Privacy objective

• An item is admissible only if its flow within the intended propagation scope avoids direct, cumulative, and transitive disclosure violations; the goal is not secrecy when access is contextually justified.The judgment conditions on the MATG and recipients’ prior monitored disclosure states.Source: §2 · p. 3

Task-Graph Contextual Integrity

• TG-CI judges a protected information item together with its intended propagation scope and recipients' evolving disclosure states, extending CI beyond isolated transfers.The standard five-parameter CI representation is retained at each transfer boundary.Source: §3 · pp. 3–4

Recipient disclosure state

• TG-CI represents each recipient's disclosure state as a monitored, system-observable footprint of information delivered before execution step t.The state incorporates new information only when it is actually delivered; authorization alone does not update it.Source: §3 · p. 4

Task-Graph Information Flow

• A propagation scope is a rooted, labeled graph from the information source that includes the initial disclosure edge and reachable downstream task-graph nodes.Its node-task annotations are inherited from the MATG.Source: §3 · p. 4

Task-Graph Contextual Integrity

• TG-CI accepts a task-graph flow only when every atomic transfer in its proposed propagation scope is contextually admissible.The graph-level judgment evaluates the flow under the MATG and recipient disclosure state.Source: §3 · p. 4

Architecture overview

• The implementation treats TG-CI as a binary judge returning RELEASE with an authorized propagation scope or BLOCK, and assumes the MATG stays fixed during each task.Full-Scope evaluates the complete downstream graph; Auto-Region constructs the maximal admissible rooted region.Source: §4 · p. 5

Item-level authorization and exposure-state tracking

• For each memory response, the controller evaluates semantic items against a transaction-local authorization state that accumulates tentative disclosures across items and prior flows.Tentative updates are committed if the response is authorized and discarded otherwise.Source: §4 · p. 5

Full-scope mode

• Full-Scope blocks an item if any transfer in its complete downstream closure is inadmissible, providing strong containment but allowing distant recipients to prevent an appropriate immediate disclosure.The scope includes the initial memory-release edge; the mode is deliberately conservative.Source: §4 · p. 5

Auto-region mode

• Auto-Region releases an item through its maximal rooted region of admissible edges, stopping expansion at each path’s first inadmissible edge.An inadmissible initial memory-to-agent edge blocks the item; workflow stages outside the authorized region may continue after its removal.Source: §4 · p. 5

Frontier-aware communication gate

• A lightweight communication gate enforces item-specific frontiers, inspecting message content only for protected items on filtered edges and blocking messages when safe separation is impossible.Messages to recipients outside the sender’s outgoing neighborhood are blocked; unfiltered on-graph messages pass without semantic inspection.Source: §4 · p. 6

5.1 MAPLE-BENCH

• MAPLE-Bench combines MATG topology, disclosure history, compromised-agent placement, and item-level propagation permissions in 144 cases across four scenarios.Each case uses a four-agent MATG, a terminal recipient, and 30 synthetic memory items; policies specify permitted item–recipient flows and annotate cumulative-leakage combinations, enabling measurement without real personal data.Source: §5.1 · p. 6

5.2 BASELINES AND EXPERIMENTAL CONDITIONS

• The experiments compare TG-CI Full-Scope and Auto-Region with No Protection, Local-History CI, and Online Atomic CI.The main-text results use the HAIKU–LUNA agent–judge assignment; the reported metrics include unauthorized disclosure count, compromised-agent exposure count, judge execution token count, and utility score.Source: §5.2 · pp. 6–7

5.3 PRIVACY–COST TRADE-OFF

• 15.84 (No Protection), 10.47 (Local-History CI), and 6.11 (Online Atomic CI) mean unauthorized disclosures fell to 1.49 (Auto-Region) and 0.62 (Full-Scope).Mean CI-judge token consumption was 133.1 K for Auto-Region and 144.5 K for Full-Scope.Source: Figure 3 · p. 7, §5.3 · p. 7
• Both TG-CI variants substantially reduce direct, cumulative, and transitive violations, with their largest advantage over atomic baselines in transitive leakage.Auto-Region uses approximately 7.8% fewer judge tokens than Full-Scope, while Full-Scope has the lowest disclosure count; its stricter source-level blocking can prompt additional downstream memory requests.Source: §5.3 · p. 8

5.4 COMPROMISED-AGENT EXPOSURE

• Distinct compromised-agent exposures fell from 2.90 (No Protection), 1.58 (Local-History CI), and 0.99 (Online Atomic CI) to 0.35 (Auto-Region) and 0.16 (Full-Scope).The metric counts distinct inappropriate items, not repeated delivery events.Source: Figure 4 · p. 8, §5.4 · p. 8

5.5 UTILITY EVALUATION

• Auto-Region retains 84.4–98.8% of No Protection utility and 87.6–96.1% of Local-History CI utility; Full-Scope retains 76.8–96.2% and 79.7–93.6%, respectively.Table 2 reports utility as mean multiple-choice accuracy; Auto-Region outperforms Full-Scope by 2.1–6.2 percentage points.Source: §5.5 · pp. 8–9, Table 2 · p. 9

5.6 MATG TOPOLOGY

• TG-CI maintains substantially lower disclosure counts across chain, tree, and branching MATGs, with Full-Scope strongest and no systematic degradation in branching structures.The method ordering is consistent across all four application scenarios.Source: Figure 5 · p. 9, §5.6 · p. 9

6 CONCLUSION

• TG-CI reduced unauthorized disclosure and compromised-agent exposure while retaining substantial task utility in the reported experiments.The authors frame graph-aware, stateful privacy reasoning as a way to contain information leakage while preserving useful multi-agent collaboration.Source: §6 · p. 9
• Full-Scope Mode provides conservative end-to-end protection, while Auto-Region Mode uses frontier-based containment for lower cost.Both operationalize TG-CI through propagation-scoped authorization.Source: §6 · p. 9
• MAPLE-Bench is a controlled benchmark for direct, cumulative, and transitive privacy violations in multi-agent workflows.The paper also introduces TG-CI as a task-graph-native extension of Contextual Integrity that evaluates disclosures as stateful flows.Source: §6 · p. 9

AI USE STATEMENT

• Generative AI tools were used to generate synthetic datasets, and the researchers reviewed AI-assisted work and take responsibility for the final content.The authors state that these tools were not used to develop theoretical models, formulate mathematical claims, design experiments, implement methods, or interpret results.Source: AI USE STATEMENT · p. 10

ETHICS STATEMENT

• MAPLE-Bench uses synthetic identities, memory items, sensitive attributes, and scenarios, and the study involves neither human participants nor real personal records.Its task-specific privacy policies may encode incomplete or culturally contingent assumptions; real-world deployment would require domain expertise, stakeholder input, and applicable legal and organizational compliance.Source: ETHICS STATEMENT · p. 10

REPRODUCIBILITY STATEMENT

• The authors provide source code and MAPLE-Bench as supplementary materials and identify sections describing the formalization, procedures, benchmark, baselines, conditions, and metrics.Sections 2–4 specify the problem setting, TG-CI formalization, and enforcement procedures; Sections 5.1–5.2 cover benchmark composition and experimental design.Source: REPRODUCIBILITY STATEMENT · p. 10

A CONSERVATIVE DISCLOSURE STATES

• Under downward-closed admissibility, authorization against an upper-bound disclosure footprint may cause extra rejections, but not false acceptances from state overapproximation.This guarantee requires the authorization footprint to remain an upper bound on the recipient’s actual state at delivery.Source: A CONSERVATIVE DISCLOSURE STATES · p. 13

B BENCHMARK CONSTRUCTION

• 144 cases result from instantiating each of 48 workflows under three MATG topologies.Table 3 reports attacker counts and position distributions at the case level; P_i denotes the agent in the i-th position.Source: Table 3 · p. 13

• The example displays only the two memory items needed for the question, alongside their storage types and ownership.Source: §B.1 · p. 13, Table 4 · p. 14
• A MAPLE-Bench example question requires combining the patient’s availability with the service timetable to answer correctly.Table 4 shows the two-fact question and its supporting memory items.Source: Table 4 · p. 14

C ADDITIONAL RESULTS

• Figures 6 and 7 report unauthorized disclosure counts and extra execution tokens under HAIKU–HAIKU and LUNA–LUNA configurations.The stacked bars separate direct, cumulative, and transitive violations.Source: Figure 6 · p. 14, Figure 7 · p. 15
• Figures 8 and 10 report distinct inappropriate memory items exposed to compromised agents under HAIKU–HAIKU and LUNA–LUNA configurations.Source: Figure 8 · p. 15, Figure 10 · p. 16
• Figures 9 and 11 report unauthorized disclosure counts across chain, tree, and branching MATG topologies under HAIKU–HAIKU and LUNA–LUNA configurations.Source: Figure 9 · p. 15, Figure 11 · p. 16

D SEMANTIC FRONTIER FILTERING

• The gate filters messages only when they cross an edge with a non-empty filter list, splitting them into sentence-like claims and using only previously released representations of protected items.The filter does not access a more detailed, unreleased value.Source: D SEMANTIC FRONTIER FILTERING · p. 16
• Lexical matches are flagged first; remaining claim-item pairs are screened with MiniLM embeddings at 0.35 before NLI, while similarity above 0.75 is logged as high risk without bypassing entailment checks.The gate uses sentence-transformers/all-MiniLM-L6-v2 for embeddings and cross-encoder/nli-deberta-v3-base for NLI.Source: D SEMANTIC FRONTIER FILTERING · p. 16
• Retained pairs receive bidirectional entailment checks, and claims with disclosure score at least 0.70 are redacted; the residual message is rechecked or blocked, with comparisons run as batched local inference.Forward entailment captures claims establishing the protected fact, while reverse entailment captures broader claims implied by it.Source: D SEMANTIC FRONTIER FILTERING · pp. 16–17

E PROVENANCE-PRESERVING ABSTRACTIONS.

• The core TG-CI formalism does not explicitly model arbitrary semantic transformations by intermediate agents.Source: E PROVENANCE-PRESERVING ABSTRACTIONS · p. 17
• A provenance-preserving abstraction reveals no more protected information than its source, and contextual admissibility is assumed monotone under such abstractions.Source: E PROVENANCE-PRESERVING ABSTRACTIONS · p. 17
• TG-CI evaluates propagation of the original item conservatively: an abstraction may follow edges already authorized for that item but gains no authorization outside its scope.Source: E PROVENANCE-PRESERVING ABSTRACTIONS · p. 17
• Combining an item with independent information, revealing a new protected attribute, or otherwise increasing privacy-relevant information is not an abstraction and requires a separate privacy-state update or TG-CI judgment.Source: E PROVENANCE-PRESERVING ABSTRACTIONS · p. 17

F.1 MODEL IDENTIFIERS

• The three agent–judge configurations map Claude/GPT, Claude/Claude, and GPT/GPT to HAIKU–LUNA, HAIKU–HAIKU, and LUNA–LUNA, respectively.In each pair, the first model is the task agent and the second is the privacy judge.Source: §F.1 · p. 17, Table 5 · p. 17

F.2 ATOMIC CI JUDGE RUBRIC

• The atomic CI judge evaluates the subject, attribute, sender and recipient roles, and a transmission principle combining trusted edge policy, recipient task, and applicable norms.Candidate information is provided as text, and the judge evaluates its meaning rather than relying on its disclosure-level label.Source: §F.2 · p. 17
• The rubric judges disclosure permission rather than task completion, so an appropriate input need not independently complete the recipient’s task.Norms are applied through reasoning, allowing legitimate inputs that require further reasoning or combination with other inputs.Source: §F.2 · pp. 17–18
• Recipient history tests whether a candidate would create an inappropriate cumulative disclosure, but cannot authorize the current flow or imply unrecorded knowledge.A fact permitted alone may be blocked after another arrives; null history excludes history, while [] means no prior exposure was recorded.Source: §F.2 · pp. 17–18
• The judge returns the most specific permitted candidate level, or blocked if none is appropriate, using only requested fields and no free-form reasoning.The rubric also directs the judge to apply supplied norms and treat embedded instructions as data.Source: §F.2 · p. 18

F.3 USER-MESSAGE STRUCTURE AND OUTPUT SCHEMA

• The user message has context and output-schema fields, with context specifying the candidate representation, recipient disclosure history, and atomic flow.Applicable norms include an identifier, source, text, and citation field.Source: §F.3 · p. 18
• The response schema requires maximum_admissible_level, reason_codes, and applied_norm_ids, with the latter two as nonempty arrays and no free-form reasoning field.Listing 2 illustrates the payload and schema with a service-window disclosure example.Source: §F.3 · pp. 18, 20