Technical Summary: PAAC (Privacy-Aware Agentic Device-Cloud Collaboration)

Problem Statement

Large Language Model (LLM) agents face a fundamental structural tension: cloud-based agents offer superior reasoning and planning capabilities but require transmitting sensitive user data (PII) to remote servers, creating significant privacy risks. Conversely, on-device agents preserve privacy through local isolation but suffer from limited computational resources and reasoning capabilities, often failing at complex, multi-step agentic tasks.

Existing device-cloud collaboration paradigms treat the boundary between device and cloud primarily as a compute split (e.g., routing or fixed pipelines) rather than a trust boundary suited for agentic workloads. Furthermore, current privacy sanitization methods force a trade-off between flexibility and structural fidelity:

• Rule-based methods (e.g., NER + regex) are reliable but bound to fixed taxonomies, failing to protect user-defined or domain-specific entities (e.g., order IDs, custom product names).
• LLM-driven rewriting methods offer policy flexibility but often strip the structural cues necessary for the cloud agent to formulate precise tool calls, breaking the agentic workflow.

This leads to two core research questions:

1. How should reasoning and execution be partitioned across device and cloud so that cloud capability is utilized without sensitive data crossing the boundary?
2. How can sensitive spans be identified under arbitrary user policies and abstracted into proxy tokens that preserve both the semantic role for cloud reasoning and the structural fidelity for on-device tool execution?

Methodology: The PAAC Framework

PAAC (Privacy-Aware Agentic Device-Cloud Collaboration) addresses these challenges through a decoupled architecture that aligns role specialization with the device-cloud trust boundary.

1. Trust-Boundary-Aligned Architecture

PAAC adopts a Cloud-Reason-and-Plan, Device-Execute-and-Judge paradigm:

• Cloud Agent (Reasoner): Operates exclusively on sanitized representations. It receives the task description and tool sets with sensitive values replaced by typed placeholder tokens (e.g., {BALANCE: 1234} becomes {BALANCE: TOKEN_1}). The cloud reasons over these tokens to generate plans and tool calls without ever seeing the underlying values.
• On-Device Agent (Sanitizer, Judge, Final Answer Generator):
  • Sanitization: Identifies sensitive spans based on user-defined policies and proposes candidate substitutions.
  • Execution: Restores real values locally to execute tool calls (e.g., querying a local database or API).
  • Judge: Evaluates the execution outcome and distills it into compact key findings (e.g., "Balance is sufficient") rather than transmitting raw execution logs. This prevents the accumulation of long, sensitive reasoning traces on the device.
  • Final Answer: Synthesizes the final response using the original user input, the distilled key findings, and the desanitized cloud suggestions.

Consensus Termination: To handle the asymmetry where the cloud sees the full plan but not real outcomes, and the device sees real outcomes but not the full plan, PAAC requires consensus termination. Both agents must signal completion; if they disagree, the device's feedback guides the cloud's revision.

2. Proposer–Verifier–Registry Sanitization

To solve the flexibility vs. fidelity trade-off, PAAC reframes the on-device LLM's role from a full sanitizer to a proposer:

• Proposer: The on-device LLM identifies sensitive spans and proposes a mapping to semantic proxy tokens (e.g., {NAME_FIRST_1}).
• Verifier: An alignment check verifies that the proposed sanitized text can be perfectly reversed to the original input. If the LLM hallucinates or misaligns, the system falls back to a safe subset of verifiable mappings.
• Deterministic Registry: A regex-based, append-only registry handles all actual substitution and reversal. This registry is initialized on the first turn and persists across the session.
  • Structural Fidelity: Because substitution is deterministic and regex-based, the cloud agent receives structurally valid tool calls (e.g., subtract(BALANCE_TOKEN, RENT_TOKEN)), ensuring the cloud can reason correctly.
  • Privacy Guarantee: The registry ensures that once an entity is masked in the first turn, it remains masked even if the on-device LLM is later compromised. The LLM only proposes; the registry enforces.

3. Context Management

PAAC avoids the "trajectory-coupled context growth" problem where context length explodes with each step. The on-device agent only processes the current step's execution results, distilling them into key findings. The cloud agent maintains its own reasoning context over sanitized tokens. This keeps per-step inputs compact for both agents.

Key Contributions

1. Decoupled Agentic Architecture: PAAC aligns the planner-executor decomposition with the device-cloud trust boundary. The cloud reasons over typed proxy tokens, while the device judges and distills outcomes. This design makes role specialization itself a privacy mechanism and keeps agent inputs compact.
2. Proposer–Verifier–Registry Sanitization: The framework confines the on-device LLM to proposing sanitization pairs, gates commits via alignment verification, and delegates all substitution to a deterministic registry. This preserves tool-call structural fidelity, ensures cross-round referential consistency, and structurally bounds the impact of any subsequent compromise of the on-device LLM.
3. Experimental Validation: PAAC was evaluated on three agentic benchmarks (τ2-Bench Airline, τ2-Bench Retail, GAIA) and 17 additional tasks across 10 domains (Math, Science, Finance, etc.).

Results

Under strict privacy settings, PAAC dominates the Pareto frontier of privacy and accuracy:

• Accuracy: PAAC improves average accuracy by 15–36% compared to state-of-the-art device-cloud baselines (e.g., PAPILLON, PRISM).
• Leakage: It reduces average privacy leakage by 2–6×.
• Robustness: PAAC maintains high accuracy and stable token costs even as privacy policies tighten (from P0 to P3). In contrast, baselines degrade significantly in accuracy or suffer high leakage.
• Generalization: PAAC excels particularly on open-vocabulary categories (e.g., custom product IDs, non-standard names) where pattern-based sanitization fails. It achieves near-zero leakage on these categories while maintaining tool-call fidelity.
• Ablation Studies:
  • The architectural gain (decoupling) alone improves performance even without sanitization.
  • The sanitization mechanism (LLM proposer + deterministic registry) significantly outperforms pattern-based methods on open-vocabulary tasks.
  • PAAC's performance is robust across different cloud reasoning paradigms (ReAct, Plan-and-Solve, RecurrentGPT).

Significance and Claims

The paper claims that PAAC represents a shift from treating the device-cloud boundary as a mere compute partition to treating it as a trust boundary where role specialization inherently enforces privacy.

• Structural Privacy: By replacing sensitive values with typed proxy tokens, PAAC structurally forces the cloud agent to dispatch computations to tools rather than reasoning over raw numbers in-context, preventing semantic inference attacks.
• Policy Flexibility without Fidelity Loss: Unlike rewriting-based approaches that break tool-call structures, PAAC's deterministic registry ensures that the cloud agent receives inputs that are semantically rich enough for planning but structurally identical to what a non-sanitized agent would see.
• Scalability: The decoupled architecture allows the system to scale with the complexity of the task without overwhelming the on-device agent with growing context lengths.

The authors note a limitation: PAAC presupposes a sufficiently comprehensive on-device tool environment. If a task requires external tools (e.g., web search) that the cloud cannot access because the query is sanitized, the cloud cannot fall back on parametric knowledge for those specific entities. However, within the scope of defined tool sets, PAAC achieves a favorable privacy-performance trade-off unattainable by existing single-agent or device-cloud baselines.