Dependency-Aware Privacy Protection for Multi-Turn LLM Agents

The paper proposes RootGuard, a privacy protection method for multi-turn LLM agents that sanitizes root values only once so that the privacy guarantee does not decay with the number of interaction turns. Existing metric differential privacy-based prompt sanitizers add noise independently to each release, and an adversary can merge multiple releases to recover private attributes; the paper's analysis shows that when a private attribute is the root of a computation graph, adding noise independently to derived values can amplify the root's distinguishability by at most the Lipschitz constant of the derived function, which in nonlinear workflows such as healthcare and finance can far exceed the nominal privacy parameter. RootGuard deterministically computes subsequent releases from the noised root; by the post-processing theorem, the privacy guarantee depends only on the initial sanitization and is independent of the adversary's function and the number of turns, and derived values inherit privacy at zero marginal cost; the method also uses structured domain knowledge (e.g., computing BMI from height and weight) to allocate budget among roots to improve the privacy-utility tradeoff.