Sharp Privacy Profiles for Bounded Validation Retries
Xiaoyu Li ⋅ Zheng Gao ⋅ Penghao Jiang ⋅ Zhicheng Bao ⋅ Jiaojiao Jiang
Abstract
Inference pipelines often generate an answer, validate it, and retry up to $K$ times before reporting failure. With a differentially private generator every attempt reads the private data afresh; what does the loop cost when only the final answer or failure message is released? For pure $\varepsilon$-DP generators and a trusted validator that reads no private data, the exact worst-case privacy profile at every budget reduces to a two-variable optimization attained by a three-output generator. For budgets $E \ge 2\varepsilon$ accepted answers contribute nothing: the profile is that of the failure message, with a closed-form worst case. Hiding the rejected drafts gains nothing over optimal composition when $E \ge (K-2)\varepsilon$, but for $E \ge 2\varepsilon$ keeps $\delta$ bounded away from one as $K$ grows, whereas composition tends to one. That bound has a positive limit: a larger cap is no privacy fix, while a certified acceptance floor or a random cap is. An enumerable example shows when exact accounting makes retries worthwhile, and when one call is better.
Chat is not available.
Successful Page Load