acceptodds
Under review as a conference paper at ICLR 2027

PrivCert: Certifying Statement Support under Differential Privacy

Abstract

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.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
Differential Privacy, Privacy-Preserving Reporting, Statement Support Certification, Private Text Generation

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_q5nSOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper introduces PrivCert, a framework for differentially private reporting with explicit statement-support certificates. It emits only statements whose lower support bounds exceed a pre-selected threshold. The paper also reveals privacy–honesty trade-offs, and a worst-case lower bound for multi-statement certification. Experiments on synthetic tasks, other real datasets show reduced unsupported emission compared with DP text-generation baselines.

Critical strengths
  1. The topic the paper focuses on is very interesting and important, which separates privacy and evidential support.
  2. Theoretical proof are given in the paper to show that the proposed PrivCert method is near optimal. Although I did not check the proof myself, my GPT Pro said that it did not discover obvious mathematical errors within them.
Critical weaknesses
  1. To me, the novelty is somewhat limited. The main implementation is standard DP statistical-query answering followed by a one-sided confidence bound and thresholding. Its value is primarily the reporting interface and application.
  2. Further more, I do not see any case demonstration of what final supported claims are drawn with the proposed method PrivCert and what claims are not supported. Without these demonstrations, readers cannot grab an intuition on what final claims can be produced.
Questions for authors
  1. Some of the implementation details are missing in the paper, including the complete schemas, claim parser, some dataset construction details, baseline configurations, and exact SVT/Gaussian calibration.
  2. Is there any tighter privacy budget composition than sampling summing them up (line 260)?
1 comment

Thank you for your constructive review and for recognizing the importance of distinguishing privacy guarantees from evidential support.

The central question of PRIVCERT is not simply how to generate differentially private text, but what a private report can actually substantiate about its underlying data. DP limits the influence of individual records, but does not automatically establish whether a reported statement is supported by those records. PRIVCERT addresses this evidence gap by formalizing explicit support certificates and emit-or-abstain decisions. Its contribution lies in characterizing the guarantees and fundamental trade-offs of this reporting contract, rather than introducing a new DP primitive.


W2: Concrete examples of emitted and abstained claims

Consider two illustrative candidates under a fixed support predicate, with reporting threshold θ=0.10\theta=0.10 and certification margin τ=0.08\tau=0.08.

  • Emit: "Reviews about delivery commonly mention delays in negative contexts." A noisy support estimate of 0.23 gives Ls=0.15L_s=0.15, exceeding the threshold.
  • Abstain: "Reviews about delivery commonly mention refunds in positive contexts." A noisy estimate of 0.15 gives Ls=0.07L_s=0.07, below the threshold.

These are schematic examples, not dataset-specific outputs. The essential distinction is that a statement is emitted only when its privacy-preserving lower certificate meets the reporting threshold.

The experiments also demonstrate nontrivial coverage. Across five runs, the tag-template proposer produces 404, 220, and 749 emission events on TAB, WildChat, and Yelp, respectively (Table 5), with FalseEmission of 0.010, 0.014, and 0.000 under the declared support semantics.


Q1: Implementation details

Appendix C.2 specifies the frozen DeBERTa-v3 NLI support model, premise–hypothesis construction, 384-token input limit, entailment-based support predicate, and privacy accounting. Appendix C.1 describes the experimental protocol.

We agree that complete proposal schemas, claim-parser details, and some baseline configurations could be documented more fully for exact reproducibility. These details concern the empirical implementation; the mathematical guarantees are stated in terms of explicit support and privacy assumptions.


Q2: Tighter privacy composition

We agree that basic sequential composition is conservative. However, Section 6.3 already evaluates alternative PRIVCERT implementations using contribution-bounded joint release (Hist), sparse-vector selection (SVT), and Gaussian certification.

More fundamentally, Theorem 5 shows that the dependence on m/(nεtot)m/(n\varepsilon_{\mathrm{tot}}) is unavoidable in the specified worst-case overlapping-support regime. Thus, the privacy cost of certifying many statements is not merely an artifact of basic composition.

This is precisely why evidential support deserves separate treatment: making private reports trustworthy requires understanding not only their privacy guarantees, but also the attainable strength and coverage of their evidence.

Reviewer_qFGsOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper looks at how private text reports can tell readers how much support each statement actually has in the underlying data. They propose PRIVCERT, where every statement gets a private lower support certificate plus an emit/abstain decision. The main instantiation, PRIVCERT-PF, uses data-independent proposals and noisy support queries, and releases a statement only if its lower cert is above a reporting threshold.

Theory includes local indistinguishability bounds, an exact single-statement emission frontier under a dataset-wise honesty constraint, near-optimality of the Laplace half-emission threshold, and a worst case lower bound for fine grained multi-statement certification. Experiments cover synthetic tasks, TAB, WildChat and Yelp, looking at unsupported emission vs coverage, plus a bunch of extra analyses (other mechanisms, proposers, support models, whole-report calibration, synthetic proxies). The authors are clear that guarantees are relative to the chosen support predicate and reference dataset.

Critical strengths
  1. Nice, well scoped formulation. Privacy, support, candidate discovery and the release decision are kept seperate, and I liked the distinction between per-candidate honesty, unsupported fraction among emitted statements, and whole-report error control. Also good that they point out support on a synthetic proxy doesnt certify support on the real data. This helps anyone trying to understand what such a system actually guarantees.

  2. Theory is coherent. The single-statement frontier, the Laplace half-emission result and the multi-statement lower bound give a pretty clear picture of the privacy–coverage tradeoff. I didnt find any substantive error in the main proofs under the stated assumptions. C.7 (coverage cost of whole-report calibration) and C.6 (changing the predicate and rerunning vs. rescoring fixed outputs) were useful too.

Critical weaknesses
  1. Novelty vs. prior private testing work isnt clear enough. The recurrence in Thm 2 looks essentially the same as Lemma 4.3 in Awan & Slavković (NeurIPS 2018), which the paper cites. I understand dataset-wise honesty isnt the same as population-level type I error calibration, but the paper should say more explicitly which parts of the frontier are new and which come from adapting their construction. Several other guarantees follow fairly directly from noise tail bounds / composition / conditioning, so a sharper comparison would make the theory contribution easier to judge. Also p.5-6: the threshold-only output of the specific binary mechanism there doesnt really show a limitation of optimal noisy-count mechanisms in general. Would be good to clarify how optimal emission probabilities relate to quantitative certificates.

  2. Not sure what the certified support means in practice. Sec 5.3 proposes aggregate statements like "Reviews about {topic} commonly mention {aspect} in {sentiment} contexts", but C.2 checks entailment of teh full statement from single records and averages over the whole corpus. Theres limited evidence this matches what a reader would take from the aggregate statement (esp. the "commonly" and the conditioning part).

The robustness results are appreciated, but they also show strong dependence on evaluator and proposer. For frozen PRIVCERT-PF outputs on WildChat, FalseEmission goes from 0.014 (NLI) to 0.241 (Qwen) in Table 8, and Table 5 has EmitRate 0.024 w/ the public-LLM proposer vs 0.220 w/ tag-template. This doesnt break the operational guarantee, but the usefulness of the certified content is still kind of open.

Hard to dig further since the public schema, proposal prompts, claim parser and full corpus construction arent given. The doc-level baseline's aggregate queries and numerical privacy params are also unclear. (I do appreciate that Table 1 is framed as a diagnostic, not a controlled comparison.)

Questions for authors
  1. Novelty: how does Thm 2 go beyond Awan & Slavković Lemma 4.3, apart from recalibrating the boundary to dataset-wise honesty? Could a rounded one-sided lower bound from a Tulap-noised count reach the frontier on supported counts and still give a quantitative certificate? If yes, how is that different from Laplace PRIVCERT-PF?

  2. Support semantics: how is a single record supposed to entail a dataset-level statement from the tag-template proposer? How do "commonly" and "Reviews about {topic}" map to the threshold and the full-corpus denominator? Some example emitted statements with certificates and supporting/non-supporting records would help a lot, ideally with a small independently annotated check.

  3. Where does the practical value come from? What explains the big coverage gap between the two proposers in Table 5, and how were the schema/templates picked without looking at the private corpus? A controlled analysis on a fixed candidate pool (unsupported emission + supported recall) would help separate the effect of certification from candidate construction.

  4. Reproducibility: please add corpus sizes and selection, exact schema/templates/prompts, the claim extraction procedure, and baseline privacy params. C.6 says only 7 of the 15 original Table 1 output sets could be recovered exactly. What happened to the rest, and could the frozen outputs and candidate-level logs go into the anonymous supp material?

1 comment

Thank you for your careful review. We appreciate your comments on optimal DP testing, support semantics, and the scope of the empirical evaluation.

The motivation of PRIVCERT is a fundamental distinction between privacy and evidence. Differential privacy constrains how individual records influence an output, but does not by itself certify that the statements appearing in that output are supported by the private dataset. We study how such evidence can be made explicit, what guarantees it can provide, and what limitations privacy imposes on its availability.

This reporting-level question, rather than a new DP testing primitive, is the central contribution of PRIVCERT.


W1 / Q1: Relationship to optimal DP testing

We agree that the constraints underlying Theorem 2 are closely related to established optimal DP testing, including Awan and Slavković. We also recognize that Tulap-based methods can produce quantitative confidence bounds.

Our contribution is therefore not the claim that optimal binary testing or quantitative certification is new.

Instead, PRIVCERT integrates these ideas into an explicit reporting contract and characterizes several distinct aspects of it: the sharp emission frontier under dataset-wise honesty (Theorem 2), near-optimal Laplace certification under the stated calibration (Corollary 1), proposal-dependent coverage (Theorem 4), and the worst-case cost of fine-grained multi-statement certification (Theorem 5).

These results collectively characterize the guarantees and limitations of attaching evidence to statements in private reports.


W2 / Q2: Support semantics

We agree that operational support and natural-language truth must be distinguished.

PRIVCERT certifies empirical support fs(R)f_s(R) under a declared, fixed predicate σ(r,s)\sigma(r,s). It does not claim matcher-independent semantic truth. In particular, aggregate expressions such as "commonly" require a defined quantitative interpretation to support stronger semantic claims.

Appendix C.6 explicitly investigates this dependence. When PRIVCERT is rerun with a frozen Qwen3-8B support predicate, UnsupportedEmit remains below the target β=0.05\beta=0.05, although the emitted statements differ. This demonstrates that certificate validity is preserved relative to the specified support function, while certified content remains semantics-dependent.


Q3: Candidate-proposal dependence

We agree that candidate discovery strongly influences coverage. Rather than treating this as incidental, Theorem 4 explicitly characterizes its effect on EmitRate.

For example, Table 5 reports EmitRates of 0.220 and 0.024 on WildChat for the tag-template and public-LLM proposers, respectively, using the same verifier. Section 6.3 separately evaluates certification mechanisms on matched candidate spaces.

Thus, PRIVCERT distinguishes the discovery of potentially useful claims from the privacy-preserving verification of their support.


Q4: Reproducibility

Appendices C.1–C.3 provide the experimental protocol, support model, privacy accounting, and alternative mechanism definitions. We acknowledge that some proposal, parsing, and baseline specifications remain insufficient for exact reproduction.

Appendix C.6 also explicitly restricts its frozen-output cross-evaluation to the seven recoverable cells, rather than presenting regenerated outputs as equivalent observations.


Ultimately, PRIVCERT asks not merely whether a report is private, but what its readers are justified in believing about the private data based on the evidence that the report provides. Our theoretical and empirical contributions are intended to formalize this distinction and its unavoidable trade-offs.

Reviewer_jpsYOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper identifies an evidence gap in differentially private (DP) text generation: privacy guarantees do not establish how strongly the generated statements are supported by the underlying private dataset. To address this, the authors introduce PRIVCERT, a reporting framework that associates candidate statements with privacy-preserving support certificates and emit-or-abstain decisions.

The paper formalizes statement support through record-level predicates and derives theoretical results on the limitations of implicit evidence under DP, a sharp single-statement emission frontier, and the worst-case cost of fine-grained multi-statement certification. The proposed PRIVCERT-PF instantiation combines data-independent candidate generation with Laplace-based support certification, achieving a near-optimal half-emission threshold under the stated assumptions.

Experiments on synthetic tasks and TAB, WildChat, and Yelp examine unsupported emissions and coverage, compare different DP certification mechanisms, and investigate the distinction between certification against original data and DP synthetic proxies.

Critical strengths

S1. Well-motivated distinction between privacy and evidential support

The paper identifies an important limitation of privacy-preserving text generation: a DP guarantee alone does not establish whether a generated statement is supported by the underlying data. The proposed reporting contract makes this distinction explicit through support certificates and emit-or-abstain decisions (Section 3). This provides a clear conceptual framework for reasoning about evidence in private reporting, beyond conventional privacy guarantees.

S2. Explicit characterization of certification guarantees and their limitations

The paper provides a systematic theoretical treatment of certification under DP, including the sharp single-statement emission frontier (Theorem 2), the near-optimality of PRIVCERT-PF under sharp calibration (Corollary 1), and the worst-case cost of fine-grained certification (Theorem 5). The experiments additionally examine alternative DP mechanisms, whole-report failure control, and the limitations of certification using synthetic-data proxies (Section 6 and Appendix C). These analyses help clarify both what the proposed certification contract guarantees and where its limitations arise.

Critical weaknesses

W1. Limited expressiveness and a gap between the motivating problem and the technical contributions

The paper motivates the challenging problem of evidence certification for private natural-language reporting, but its primary formulation operationalizes statement support as the empirical frequency of a fixed record-level Boolean predicate (Section 3, Eq. 1). Although Section 3 allows more general semantic matchers subject to appropriate sensitivity and privacy accounting, the paper does not demonstrate how to certify more complex comparative, relational, or conditional statistical claims requiring evidence across multiple records. The realistic-corpus experiments also rely on averages of record-level binary support judgments. Consequently, the extent to which the framework addresses the broader challenges of natural-language evidence certification remains unclear.

This gap also raises questions about the significance of the theoretical contributions. Theorem 1 applies a standard consequence of group privacy, as the authors acknowledge, while Theorem 3 follows directly from a one-sided noise-tail bound. Theorem 2 establishes a sharp emission frontier, Corollary 1 demonstrates near-optimality within one supporting record, and Theorem 5 provides a worst-case multi-statement lower bound. These are meaningful characterizations, but their strongest optimality results concern restricted count-based settings. Similarly, PRIVCERT-PF combines standard DP support estimation with threshold filtering. It remains unclear what substantially new theoretical insight or certification capability these results provide for the more general reporting problem motivating the paper.

W2. Limited evidence of practical reporting utility

Table 1 reports substantially lower FalseEmission for PRIVCERT-PF than for free-text DP baselines. However, the methods differ in candidate generation, output structure, and abstention. As the authors acknowledge (Section 6.2), this comparison is diagnostic rather than causal. Without matched comparisons of useful reporting output, including claim counts, coverage, and informativeness, it remains unclear whether the improved evidential reliability justifies the loss of reporting utility.

Coverage also depends heavily on candidate generation. In Appendix C.4, replacing the tag-template proposer with a public LLM reduces EmitRate from 0.404 to 0.003 on TAB, 0.220 to 0.024 on WildChat, and 0.749 to 0.018 on Yelp. On TAB, only three statements are emitted across five runs, all classified as unsupported. Although this small sample does not contradict per-candidate honesty, it raises concerns about the reliability of nonempty reports. Appendix C.7 evaluates family-wise calibration only for tag-template proposals, leaving its coverage cost in this low-yield setting unclear.

Furthermore, PRIVCERT-SVT performs private selection from predefined candidates rather than data-dependent generation of new statements. The practical trade-off between DP candidate discovery and subsequent certification under a shared privacy budget remains unexplored, limiting the demonstrated applicability beyond carefully designed candidate spaces.

Questions for authors

Q1. Expressiveness of certification. Can the authors provide a concrete example of certifying a comparative or relational claim that requires combining evidence across multiple records? How would its support function and sensitivity be defined, and which theoretical guarantees would continue to apply?

Q2. Theoretical contribution and calibration. How do the sharp emission frontier and near-optimality results differ from established DP hypothesis-testing and threshold-testing results, particularly DP tests for binomial data? Also, since Corollary 1 uses sharp Laplace calibration while the main experiments use a more conservative margin (Appendix C.2), how should the theoretical near-optimality claim be interpreted in relation to the evaluated implementation?

Q3. Practical utility and candidate discovery. Can the authors provide more directly comparable measures of useful reporting output, such as the number and informativeness of supported claims, alongside FalseEmission? Given the substantial proposer dependence in Appendix C.4, how would DP-based data-dependent candidate generation compare with the current data-independent proposal approach under a shared privacy budget?

1 comment

Thank you for your constructive review.

We believe the key contribution of PRIVCERT is to identify and formalize a missing guarantee in privacy-preserving reporting. Existing DP text-generation methods protect individual records, but privacy alone does not tell a reader whether a particular statement reflects the private dataset or merely the model's prior knowledge. This distinction becomes particularly important when the original records cannot be inspected.

PRIVCERT makes evidential support explicit and studies the resulting trade-offs among privacy, certificate validity, and report coverage.


W1 / Q1: Expressiveness of support certificates

Our empirical implementation uses a fixed Boolean record-level predicate because it provides an auditable support definition with sensitivity 1/n1/n. However, the PRIVCERT reporting contract does not require this particular predicate.

For example, comparative claims could be supported through privately estimated differences between bounded statistics, with appropriately calibrated one-sided certificates. More complex relational claims require corresponding sensitivity analyses.

Theorem 3 provides the general certificate-validity argument when the required one-sided error bound holds. We do not claim that our current experiments or binary-count optimality results automatically extend to all such statements.


W2 / Q3: Practical utility and candidate discovery

We agree that low FalseEmission alone is insufficient to characterize report utility. This motivates our explicit treatment of coverage.

Theorem 4 relates EmitRate to the proposal distribution's mass on sufficiently supported statements. In the realistic experiments, the tag-template proposer achieves EmitRates of 0.404, 0.220, and 0.749 on TAB, WildChat, and Yelp.

Section 6.3 further compares alternative certification mechanisms on matched candidate spaces. Table 1 is intended as a diagnostic of the evidence gap, not a controlled comparison of overall language-generation quality.

The framework permits data-dependent discovery when its privacy cost is accounted for. Our current implementation uses data-independent proposals to isolate the certification problem.


Q2: Relationship to prior DP theory

We fully acknowledge that private thresholding and optimal DP testing are established techniques.

Our novelty is not the underlying thresholding primitive, but the formulation and characterization of evidentially accountable private reporting. Theorem 2 characterizes the emission frontier under dataset-wise honesty; Theorem 4 connects certification to discovery-dependent coverage; and Theorem 5 establishes the worst-case cost of fine-grained multi-statement certification.


Together, these results address a question distinct from private text generation itself: what evidence can a private report provide for its individual statements, and at what privacy cost?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.