PaperlayerView exact revision on arXiv

Source-linked AI summary

PrivCert: Certifying Statement Support under Differential Privacy

Tsubasa Takahashi, Takumi Hiraoka

arXiv:2609.38934v1cs.CRcs.LG

TL;DR

Differentially private text can protect records without specifying how strongly its claims are supported by the data. PrivCert pairs privacy-preserving support certificates with emit-or-abstain decisions, and experiments report low unsupported emission for certification alongside low-support claims in free-text DP outputs. The paper also delineates the scope of those guarantees.

  • Problem

    Differential privacy limits individual records’ influence but does not specify what evidence a generated statement carries about dataset support.

    Source: §1 · pp. 1–2

  • Method

    PrivCert makes statement support explicit through privacy-preserving certificates and emit-or-abstain decisions, with PrivCert-PF separating data-independent candidate discovery from private support certification.

    Source: §1 · p. 2, §5 · p. 5

  • Results

    Across three datasets, PrivCert-PF UnsupportedEmit was [0.000, 0.008], below β = 0.05, while free-text DP outputs often contained low-support claims under the declared support semantics.

    Source: §6.2 · p. 8

  • Takeaways & Limitations

    The results recast privacy-preserving reporting as an evidence-design problem about what a private report can substantiate about its data.

    Source: §8 · p. 10

    Guarantees are relative to the declared reference data and support function, not matcher-independent semantic truth; proxy-data support does not certify support in the original data without an additional fidelity guarantee.

    Source: §7 · p. 9

Abstract

from arXiv · show

Differentially private (DP) text generation can protect individual records, but privacy alone does not specify what evidence a released statement carries about the underlying data. We identify this as an evidence gap: a private report may contain plausible claims without indicating whether they are strongly supported by the private dataset. We introduce PrivCert, a framework for privacy-preserving reporting that makes statement support explicit through privacy-preserving certificates and emit-or-abstain decisions. As a canonical instantiation, PrivCert-PF (Proposal-and-Filter) separates data-independent candidate discovery from private support certification, emitting only statements whose support passes a private evidence test. We provide theoretical grounding for this framework by characterizing the limits of implicit evidence under DP, deriving a sharp privacy--honesty frontier for single-statement certification, and establishing a worst-case cost for fine-grained multi-statement certification. Experiments on synthetic tasks and TAB, WildChat, and Yelp show that explicit certification maintains low unsupported emission, while free-text DP baselines frequently produce low-support claims under the same declared support semantics. We further show that the PrivCert contract can be realized with histogram, sparse-vector, and Gaussian mechanisms, and use DP synthetic data to illustrate an important boundary: support in a private proxy does not automatically certify support in the original data. Together, these results position privacy-preserving reporting as an evidence-design problem: not only how to generate private text, but what a private report can substantiate about its underlying data.

1 Introduction

Differential privacy protects records but does not show how strongly a released statement is supported by the private data. PrivCert makes support explicit through privacy-preserving evidence and emit-or-abstain decisions, with PrivCert-PF separating candidate discovery from private certification.

Motivation

  • DP text can sound plausible without showing whether claims reflect widespread support, rare observations, or information inherited from the model.The paper calls this mismatch between private text and explicit support evidence the evidence gap.Source: §1 · p. 2

Framework

  • PrivCert makes released statements carry privacy-preserving support evidence and subjects them to emit-or-abstain decisions.The framework separates candidate discovery, evidence construction, and release without prescribing a particular candidate generator or DP primitive.Source: §1 · p. 2

Contributions

  • PrivCert-PF combines data-independent proposals with private support certification, and its sharply calibrated single-statement half-emission threshold is within one supporting record of optimal.The paper also characterizes the worst-case cost of fine-grained multi-statement certification.Source: §1 · p. 2
  • The work reframes privacy-preserving reporting as making a report’s evidential basis explicit, not only generating private text.Its contributions include experiments on synthetic tasks and TAB, WildChat, and Yelp, including comparisons of PrivCert realizations and direct versus proxy-data certification.Source: §1 · p. 2

2 Related Work

Related work studies private text generation, aggregate reporting, faithfulness, abstention, and private query answering. This paper focuses on privately verifying candidate-statement support and tying it to certificates and abstention.

Differentially private text generation

  • Prior DP text-generation work focuses on producing useful private text, while this paper asks what evidence a released statement provides that private data support it.The cited approaches include private training [1], inference-time decoding [27] [26], synthetic text generation [29] [30], and structured-text evaluation [28].Source: §2 · p. 3

Private aggregate reporting

  • CLIO summarizes sufficiently large conversation clusters, and Urania uses private clustering, partition selection, and histogram release [19]; this paper privately verifies candidate statements.Source: §2 · p. 3

Faithfulness and abstention

  • Faithfulness research studies source support [16], and selective prediction and conformal methods use abstention [10] [2]; here, a privacy-preserving support test drives abstention.Source: §2 · p. 3

Private query answering, thresholding, and optimal mechanisms

  • The verifier connects statement support to DP query answering [13] [14], sparse vector techniques [20], private hypothesis testing [4], and staircase mechanisms.Its focus is the reporting interface between statements, support certificates, and abstention, with a frontier induced by the dataset-wise one-sided honesty contract.Source: §2 · p. 3

3 PrivCert: Private Reporting with Explicit Support Evidence

PrivCert formalizes what evidence statements carry about a private dataset through support semantics, privacy-preserving certificates, and an emit-or-abstain contract. Its guarantees depend on the declared support function and reference data.

Statements and evidence semantics

  • Support is defined relative to a fixed predicate, and empirical-frequency support has replace-one sensitivity at most 1/|R| when that predicate is independent of R.More general matchers may be used if their sensitivity and any private adaptation are included in privacy accounting.Source: §3 · p. 3
  • The support function specifies the operational evidence notion and θ specifies the reporting threshold; guarantees do not establish matcher-independent semantic truth.Source: §3 · p. 3

PrivCert interface

  • PrivCert associates each evaluated candidate with a statement, privacy-preserving support certificate, and emit-or-abstain decision.The interface separates candidate discovery, private evidence construction, and final release; it does not prescribe a particular mechanism for those roles.Source: §3 · p. 3

PrivCert contract

  • The PrivCert contract controls the probability of emitting an unsupported statement, while multi-statement reports must specify their error scope.Per-candidate validity alone does not control the probability that any unsupported statement appears in the complete report; the framework allows approximate-DP mechanisms as well as pure DP.Source: §3 · p. 4

4 Privacy Limits and Optimal Statement Certification

The section examines what ordinary DP outputs can reveal about statement support and how privacy constrains explicit certification. It derives a sharp single-statement emission frontier and uses it to assess PrivCert-PF’s near-optimality.

4.1 Limits of Implicit Evidence

  • For nearby datasets, a single DP output cannot provide arbitrarily reliable implicit evidence about statement support, though the bounds become weak when kε is large.For empirical-frequency support, changing support by ∆ requires at least ⌈n∆⌉ record replacements.Source: §4.1 · p. 4

4.2 Sharp Single-Statement Certification Frontier

  • Under the one-sided honesty condition, Theorem 2 upper-bounds emission probability by π_ds(R), and a count-based ε-DP mechanism attains the bound pointwise.The bound applies when 0 < β < 1/2 and both supporting and non-supporting records exist.Source: §4.2 · p. 5
  • The frontier gives an exact upper envelope on how quickly release can become more likely as support rises above the reporting threshold.The paper states that π_k ≤ βe^kε and that any certifier emitting with probability at least 1/2 must satisfy a further condition, whose expression is not included in the supplied passage.Source: §4.2 · p. 5
  • PrivCert-PF reaches the fundamental single-statement margin essentially optimally while providing a quantitative lower certificate on support, unlike the optimal count-based mechanism’s threshold-level certificate.Source: §4.2 · p. 5

5 A Canonical PrivCert Instantiation: Proposal-and-Filter

PrivCert-PF separates data-independent candidate discovery from private support certification, releasing only candidates whose lower support certificates clear the reporting threshold. Its analysis establishes per-candidate honesty, near-optimal single-statement calibration, discovery–coverage trade-offs, and a worst-case cost for fine-grained certification.

5.1 Proposal-and-Filter

  • PrivCert-PF proposes candidates independently of the private data, privately estimates their support, and emits a statement only when its lower support certificate reaches θ.Candidate discovery does not establish evidential validity; a supported statement that is never proposed cannot be certified, and any final rendering must preserve the certified statement’s semantics.Source: §5 · p. 5, §5.1 · p. 5

5.2 Privacy, Honesty, and Near-Optimality

  • If a statement with support below θ is emitted only when its lower certificate reaches θ, its emission probability is at most β.The guarantee remains valid after candidate selection when certification noise is fresh and independent of the selection event; for m candidates, a union bound gives report-level failure probability at most mβ.Source: §5.2 · pp. 5–6
  • Under sharp Laplace calibration, PrivCert-PF reaches half-emission probability within one supporting record of the optimal threshold.The optimal staircase mechanism attains the exact binary release frontier but gives only a threshold-level certificate; PrivCert-PF also provides a quantitative lower certificate on support.Source: §5.2 · p. 6

5.3 Discovery and Coverage

  • Candidates with support at least θ + 2τ are emitted with probability at least 1 − β, while coverage depends on proposal mass in certifiable support regions.The tag-template proposer uses a fixed public schema and templates; its granularity trades statement specificity against the probability of clearing the reporting threshold.Source: §5.3 · p. 6

5.4 The Cost of Fine-Grained Certification

  • In the worst-case overlapping-support regime, fine-grained certification has linear dependence on m/(nε_tot), reflecting the cost of resolving many statement supports individually.This is a worst-case condition, not a claim about every semantic support model; additional structure, joint sensitivity, or selective release can improve the trade-off.Source: §5.4 · p. 7

6 Empirical Evaluation

Experiments test whether PrivCert-PF suppresses unsupported claims and follows predicted coverage behavior across synthetic and realistic corpora, then assess alternative mechanisms and proxy-data boundaries. Across these settings, certification maintains low unsupported emission, while free-text DP outputs often contain low-support claims.

6.1 Synthetic Validation

  • 0.002 mean and 0.038 maximum UnsupportedEmit in the synthetic sweep accompany EmitRate values within Theorem 4’s predicted interval in every tested cell, up to sampling slack.The sweep varies total privacy budget, threshold, candidate count, and honesty target over five seeds.Source: §6.1 · p. 7

6.2 Realistic Corpus Experiments

  • On realistic corpora, PrivCert-PF UnsupportedEmit is 0.000–0.008, while InvisibleInk FalseEmission ranges from 0.619 to 0.994 across datasets and backbones.Free-text DP outputs often contain low-support claims under the declared support semantics; the FalseEmission comparison is a diagnostic, not a causal estimate or general quality ranking.Source: Table 1 · p. 8, §6.2 · p. 8
  • On WildChat, increasing εtot from 1 to 20 raises EmitRate from 0.051 to 0.274 while UnsupportedEmit remains below 0.05.The sweep holds the proposer, support model, threshold, and per-candidate honesty target fixed.Source: Table 2 · p. 8, §6.2 · p. 8
  • Realistic tests use TAB, WildChat, and Yelp, comparing PrivCert-PF with no-data generation, aggregate-then-render DP, and InvisibleInk token-level DP at (εtot, δ) = (10, 10^-5).The support predicate uses a frozen public NLI cross-encoder and a tag-template proposer.Source: §6.2 · p. 8
  • All 15 per-seed EmitRates on realistic corpora fall within Theorem 4’s predicted expectation interval, though these finite-run checks are not per-run guarantees.Aggregate EmitRates are TAB 0.404, WildChat 0.220, and Yelp 0.749.Source: §6.2 · p. 8
  • With a report-level failure budget βtot = 0.05, EmitRate falls from 0.404 to 0.357 on TAB, 0.220 to 0.169 on WildChat, and 0.749 to 0.565 on Yelp.This allocation bounds the probability that any emitted statement is unsupported, unlike the per-candidate guarantee alone.Source: §6.2 · pp. 8–9

6.3 Alternative PrivCert Instantiations

  • PrivCert-Hist, PrivCert-SVT, and Gaussian PrivCert-PF keep UnsupportedEmit below 0.05, showing compatibility with different evidence constructions and privacy mechanisms.Theorem 4 does not apply unchanged to Hist and SVT, while the Gaussian variant changes only the DP backend.Source: §6.3 · p. 9, Table 3 · p. 9
  • Support on DP synthetic data does not certify original-data support: at θ = 0.10, original-data UnsupportedEmit is 0.092 for the proxy backend versus 0.001 for direct certification.Original-data certification therefore requires an additional fidelity guarantee.Source: §6.3 · p. 9

7 Discussion and Limitations

PrivCert’s guarantees are scoped to the declared reference data and support function, and statement-level honesty does not ensure a complete or logically consistent report.

7 Discussion and Limitations

  • Certificates are relative to the declared support function, not matcher-independent semantic truth; changing support models can change coverage and certified content.Statements not proposed cannot be certified, and proxy-data support needs an additional fidelity guarantee to apply to the original dataset.Source: §7 · p. 9
  • Privacy noise, conservative certification, and limited discovery may cause abstention, while statement-level certificates do not guarantee logical consistency across the report.Source: §7 · p. 9

8 Conclusion

The conclusion frames privacy-preserving reporting as an evidence-design problem: differential privacy protects records but does not establish what a released statement is supported by. PrivCert makes support explicit, with theoretical and empirical results characterizing its guarantees and boundaries.

8 Conclusion

  • Differential privacy limits individual records’ influence but does not specify what evidence a released statement carries about the underlying data.Source: §8 · p. 9
  • PrivCert makes statement support explicit through privacy-preserving certificates and emit-or-abstain decisions, with theory covering privacy–honesty limits and fine-grained certification cost.The analysis also shows sharply calibrated PrivCert-PF operates near the single-statement optimum.Source: §8 · p. 10
  • Experiments across multiple datasets and DP mechanisms characterize the evidence gap and demonstrate alternative contract realizations while clarifying their scope and boundaries.Source: §8 · p. 10

A Proofs for Section 4

These proofs establish limits on inferring support from DP outputs, characterize private emission under an honesty constraint, and connect PrivCert-PF’s decisions to privacy and report-level error bounds.

A.1 Proof of Theorem 1 and Support-Estimation Consequence

  • Group privacy bounds distinguishability between output distributions, limiting binary tests and the accuracy of support estimation.The proof reduces support estimation to distinguishing datasets with different support values.Source: §A.1 · p. 13

A.2 Proof of Theorem 2

  • Theorem 2’s proof bounds emission probability by iterating the DP recurrence from β across support counts, and a count-based mechanism attains the bound.The construction also attaches the threshold as the certificate when it emits.Source: §A.2 · p. 14

A.3 Extension to Approximate Differential Privacy

  • Under approximate DP, local testing bounds include accumulated δk slack and may become weak when kε or δk is large.Setting δ = 0 recovers the pure-DP bounds.Source: §A.3 · p. 14

B.1 PrivCert-PF Algorithm

  • PrivCert-PF samples candidates, computes noisy lower support certificates, and emits a candidate only when its certificate reaches θ; otherwise it abstains.Final rendering of emitted statements is optional.Source: §B.1 · p. 15

B.2 Privacy and Honesty

  • Support queries compose for privacy, while certificates and release decisions are post-processing; unsupported emissions are bounded per candidate and, by a union bound, across the report.With uniform β_j = β, the report-level bound is mβ, without requiring independent candidate-level events.Source: §B.2 · p. 15

B.3 Proof of Theorem 4

  • Theorem 4’s proof combines per-candidate bounds: below-threshold candidates emit with probability at most β, while qualifying candidates emit with probability at least 1−β.These cases yield bounds on the proposal-averaged emission rate.Source: §B.3 · p. 16

B.4 Proof of Corollary 1

The appendix develops a single-statement emission-distance consequence, a hard-instance construction for fine-grained certification, and implementation details on support evaluation and alternative mechanisms. Its proposer comparison finds low unsupported emission alongside substantial coverage variation.

B.4 Proof of Corollary 1

  • Theorem 2 implies that reaching emission probability 1/2 requires distance at least k⋆ from the relevant support boundary.The proof derives the distance for Laplace PrivCert-PF from the emission probability at successive support counts.Source: §B.4 · p. 16

B.5 Proof of Theorem 5

  • The multi-statement lower-bound construction encodes support patterns in nearby datasets and uses separated codewords to force distinguishable outputs.The proof uses a rich record domain so each binary support pattern can be realized.Source: §B.5 · p. 17

C.1 Experimental Protocol and Metrics

  • The synthetic protocol isolates the private filter using a finite statement universe with oracle supports; the reported metrics include unsupported emission and emitted fraction.The parameter sweep covers εtot ∈ {1, 4, 10, 20}, θ ∈ {0.05, 0.1, 0.2}, m ∈ {50, 200, 1000}, and β ∈ {0.01, 0.05, 0.1}, with five seeds per configuration.Source: §C.1 · p. 18

C.2 Support Evaluation, Proposals, and Privacy Accounting

  • Operational support uses a frozen public NLI matcher; with a fixed predicate, empirical-frequency support has replace-one sensitivity at most 1/|R|.Both tag-template and public-LLM proposals are independent of the private dataset, so they incur no privacy cost; proposals affect discovery, not the verifier’s per-candidate honesty guarantee.Source: §C.2 · pp. 18–19

C.4 Proposer Comparison

  • UnsupportedEmit stays below 0.01 across all six proposer-comparison cells, while coverage changes substantially with the proposal distribution and the verifier stays fixed.The comparison changes only the proposer.Source: Table 5 · p. 20, §C.4 · p. 20

C.3 Alternative PrivCert Mechanisms

  • Histogram, sparse-vector, and Gaussian alternatives realize the reporting contract, but differing sensitivity and selection structures change coverage; contribution caps can remove genuine support, and SVT’s dependencies mean Theorem 4 does not apply unchanged.Contribution-bounded certificates remain conservative relative to the original support function.Source: §C.3 · pp. 19–20

C.5 DP Synthetic Data as a Boundary Case

The Yelp comparison shows that support in a DP synthetic proxy does not automatically establish support in the original corpus. It also identifies a fidelity condition needed to transfer a proxy certificate.

C.5 DP Synthetic Data as a Boundary Case

  • Support in the synthetic proxy certifies that proxy, not automatically the original dataset.An original-data lower certificate requires an additional fidelity guarantee.Source: §C.5 · p. 20
  • At θ = 0.10, the synthetic backend has similar coverage but substantially larger UnsupportedEmit measured against the original corpus.The repetition units differ, so run-level counts are not matched failure-probability estimates.Source: §C.5 · p. 20, Table 6 · p. 21
  • Under the stated fidelity condition, a proxy support lower bound adjusted by γ+ implies original support at least θ except with probability η; an oracle correction reduces EmitRate to approximately 0.14–0.28 but is not deployable.The correction inspects original-corpus support directly.Source: §C.5 · p. 21

C.6 Robustness to the Support Model

Certification behavior persists across support-model choices, but which statements are certified depends on the operational support model. Whole-report control is also available at a coverage cost.

C.6 Robustness to the Support Model

  • With an LLM-based support model, UnsupportedEmit remains well below β = 0.05, and all 15/15 finite-run EmitRates are empirically consistent with Theorem 4’s expectation interval, though emitted sets differ, especially on WildChat.PrivCert’s guarantees are defined relative to a fixed support function.Source: §C.6 · p. 21
  • Across exactly recoverable cross-evaluation cells, PrivCert-PF and free-text baseline ordering persists on all three datasets; the gap remains large on TAB and WildChat but narrows on Yelp.The diagnostic’s magnitude remains support-model dependent.Source: §C.6 · p. 22
  • Re-scoring frozen PrivCert-PF outputs with Qwen does not preserve the original β-honesty guarantee, which was defined under the NLI support function.The cross-evaluation is a robustness diagnostic.Source: §C.6 · p. 22

C.7 Whole-Report Guarantee

  • Whole-report calibration bounds the probability of any unsupported emission by 0.05 and reduces coverage on all three datasets; per-candidate calibration offers higher coverage.No unsupported report was observed in the evaluated runs.Source: §C.7 · p. 22
Loading 2609.38934v1…