{"id":"93ef1943-8f49-4eb6-af22-8ca03ea7c17c","arxiv_id":"2506.04566","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":6,"one_line_summary":"Clustering seed texts and privately aggregating median token logits improves representativeness and reduces reported privacy cost for DP synthetic text generation.","lead":"This paper improves differentially private text generation by clustering seed examples into similar groups and aggregating the language model's next-token scores with a median instead of a mean. The result is synthetic text that better matches the original data, at a reported privacy cost that is lower but measured with a weaker ex-post guarantee.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The 'significantly lower privacy cost' claim compares the median mechanism's ex-post data-dependent epsilon with the mean baseline's worst-case epsilon; the median has no comparable worst-case bound, so the advertised privacy advantage is not established as an algorithm-level guarantee.","rationale":"The reader identified the clustering homogeneity assumption as the weakest point, and noted in the rationale that the 'lower privacy cost' claim compares ex-post with worst-case epsilon. My stress-test agrees with the latter concern and treats it as the most load-bearing issue because it directly affects the central claim ('significantly lower privacy cost') and is not dataset-specific: even if clustering works perfectly on a given dataset, the comparison is still between incomparable quantities. The median mechanism's worst-case epsilon is unbounded, so the low reported values are realized outcomes rather than guaranteed properties. This weakens the paper's headline contribution, though the algorithm itself is sound and the utility improvements are plausible. A concrete analytical check (deriving the worst-case median epsilon) would settle the issue. If the worst-case median epsilon is indeed larger than the baseline's worst-case epsilon, the paper should either compare against a data-dependent (ex-post) baseline, compute a high-probability bound on the median's epsilon, or reframe the claim to state that the privacy cost is low only for the tested datasets. My recommended verdict remains CONDITIONAL, as the concerns are addressable and do not invalidate the core technical work.","tokens_in":16279,"tokens_out":11685,"duration_ms":125212,"concrete_test":"Derive a worst-case upper bound on the median mechanism's epsilon: for logit vectors in [-c,c]^V with batch size b, compute the per-token gamma (Definition 3) maximized over all possible Z and x, multiply by n (output tokens), and compare this worst-case epsilon to the mean baseline's 10. If the worst-case median epsilon exceeds 10, the 'significantly lower privacy cost' claim is not an algorithm-level guarantee. Additionally, run the median-clustered pipeline on a private dataset deliberately chosen to be far from DBPedia (e.g., medical discharge notes) and record the realized epsilon distribution; if the maximum realized epsilon exceeds the mean baseline's epsilon, the advertised privacy advantage fails precisely in the regime identified by the reader.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Theorem 1 (Section 5) states a data-dependent ex-post DP guarantee with epsilon(D,X) = max over batches of summed per-token costs, where the per-token cost gamma (Definition 3, Appendix A) is a function of the actual logit vectors Z_i,t. This epsilon is a realized value that depends on the private data and the sampled output; it is not a worst-case bound. In contrast, the Mean Baseline's epsilon (10 or 3) is an unconditional worst-case guarantee that holds for every dataset and output. Comparing these two numbers in Table 3 and concluding 'significantly lower privacy cost' is therefore not a like-for-like comparison. Concretely, the median mechanism's worst-case sensitivity over logit vectors in [-c,c]^V is bounded only by the full range 2c; with c=6 and tau=1.5, an adversarial combination of logits can yield exp(2c/tau) per-token cost, which is astronomically larger than the reported 2.40, and summing over n~1000 tokens gives a worst-case epsilon that is effectively unbounded. Thus the algorithm provides no finite worst-case DP guarantee; the low reported numbers are empirical observations on the three evaluated datasets, all of which are news/review text that happens to align with the DBPedia public clusters. If a private dataset is heterogeneous or the public centers misalign (the reader's concern), the realized epsilon could exceed the mean baseline's worst-case epsilon, eliminating the claimed privacy advantage. The abstract also motivates uniform random sampling, whereas the experimental baseline already uses within-label batching, further obscuring the comparison. The privacy proof is not impugned; the issue is the interpretation of the privacy cost numbers.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies differentially private (DP) language model inference for synthetic text generation. It observes that uniform random batching of sensitive seed texts yields heterogeneous batches and poor representativeness, and proposes to group seeds by clustering before batching. For aggregation of next-token logits, it replaces the mean of clipped logit vectors with a component-wise median, and proves (Theorem 1) an epsilon-data-dependent ex-post DP guarantee whose per-token cost depends on the local sensitivity of the median on the realized logit set. The paper evaluates the method on AGNews, Yelp, and NYT Topics using DBPedia as public clustering data, reporting improvements in MAUVE and downstream BERT accuracy, and reporting lower realized privacy costs than a mean-aggregation baseline.","tokens_in":16564,"tokens_out":16523,"duration_ms":158675,"significance":"If the claims hold, this work makes a useful contribution: clustering improves the representativeness of DP-inference synthetic text, and the median local-sensitivity analysis is a legitimate extension of the DP-inference toolkit. The privacy proof is structurally sound, and the experimental protocol is detailed, with multiple seeds and clearly reported hyperparameters. However, the headline privacy-cost advantage is not established as a like-for-like comparison: the reported median epsilon is a realized ex-post value, not a worst-case bound, and the comparison is also confounded by different clipping constants. The paper's empirical contribution remains valuable, but the central privacy-cost claim needs substantial reframing and additional analysis.","major_comments":[{"comment":"The abstract and Section 8 claim 'significantly lower privacy cost' based on Table 3, but the comparison is between the median mechanism's realized ex-post epsilon (e.g., 2.40 + 0.16) and the mean baseline's worst-case unconditional epsilon (10 or 3). These are not comparable quantities: Theorem 1's epsilon(D,X) is a function of the actual logit vectors and the sampled output, while the baseline epsilon is an algorithm-level worst-case bound. The median mechanism has no useful worst-case bound: from Definition 3, the per-token cost gamma can grow linearly in c/tau for adversarial median gaps, and the sum in Theorem 1 over the realized sequence length (up to 733 tokens at epsilon=3 in Table 5) can be in the thousands, far exceeding the baseline's 10. The reported low values are empirical observations on the three evaluated datasets. The paper should either explicitly qualify the privacy-cost claim as a realized ex-post cost on these benchmarks, or provide a like-for-like comparison (e.g., a worst-case analysis of the median mechanism, or the realized ex-post cost of the mean baseline).","section":"Section 5, Table 3, Abstract"},{"comment":"The median runs use clipping constant c=6, while all mean-based runs use c=9. Because both the global sensitivity of the mean aggregation and the local sensitivity in Definition 3 depend on c, the difference in reported privacy cost between the median and mean methods is confounded with the choice of c. To attribute the improvement to median aggregation rather than to a smaller clipping range, the paper should match c across the compared methods or provide a sweep over c.","section":"Table 5"},{"comment":"The utility and the realized privacy cost both rely on the assumption that the public DBPedia centers, after rebalancing, assign the private data to semantically homogeneous clusters. The three target datasets (AGNews, Yelp, NYT Topics) are all Wikipedia-based or news/review text, so they are aligned with the public data. For a private domain far from Wikipedia-like text (e.g., medical records), the rebalanced clusters could remain heterogeneous, the median gaps would be large, and the realized epsilon could exceed the mean baseline's worst-case epsilon, eliminating the claimed advantage. The paper should test at least one non-Wikipedia-like domain, or provide an explicit limitation plus a quantitative relation between cluster heterogeneity and the realized epsilon.","section":"Section 4.1, Table 3"},{"comment":"The proof of Theorem 1 assumes the batch() function is fixed: it conditions on the random r and then argues that only one batch changes between neighboring datasets. The experimental pipeline 'public centers with rebalancing' (Section 4.1) selects the top-k' cluster centers using noisy counts of the private data, making batch() data-dependent. For neighboring datasets, the selected centers can change, so many seeds can be reassigned simultaneously and the 'single batch' step no longer holds. The paper should provide a formal composition argument: the rebalancing is an epsilon1-DP mechanism producing centers, and for every fixed center set, Algorithm 1 with the resulting batch() satisfies the ex-post guarantee; the total guarantee then follows by composition. As written, the theorem covers only the fixed-centers variant, not the exact procedure used in the experiments.","section":"Section 5, Theorem 1"}],"minor_comments":[{"comment":"In the even-cardinality case, 'right-median(Z)_x = c' refers to an undefined c; it should be b.","section":"Appendix A, Definition 2"},{"comment":"The notation for the neighboring batch's generated sequence is inconsistent: the text defines x'_{i,1},...,x'_{i,t} and later uses x'_{i,n}; please clarify the intended sequence length.","section":"Appendix A, Proof of Theorem 1"},{"comment":"The entries '2.40 + 0.16' in the Privacy epsilon column are easy to misread as a sum of two privacy parameters; consider writing e.g. '2.40 (inference) + 0.10 (rebalancing)' or explaining the additive term directly in the table caption.","section":"Table 3"},{"comment":"The word 'embarassingly' should be 'embarrassingly'.","section":"Section 8"},{"comment":"The Greek letter epsilon appears as a box glyph in the plain-text captions; please check the rendering in the compiled version.","section":"Figures 3-4"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is a credible empirical contribution, but the privacy accounting comparison will need careful editorial handling. The main risk is that the 'lower privacy cost' claim is overly strong given the ex-post vs worst-case mismatch. I would ask for a revised version that reframes the claim, addresses the clipping confound, and adds a formal composition statement for the rebalancing step."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know two things about this paper. First, it does something real: replacing mean aggregation with median aggregation in DP inference, combined with public-center clustering and DP rebalancing, produces synthetic text that is much better by MAUVE and downstream accuracy metrics. The privacy proof (Theorem 1, Appendix A) is structurally sound—the per-token cost function is a genuine local-sensitivity calculation, and the chain-rule composition is correct. Second, the headline claim that this comes 'at significantly lower privacy cost' is not apples-to-apples. The median mechanism's epsilon is data-dependent and ex-post; the mean baseline's is a worst-case guarantee. The paper is explicit about this distinction in Section 5, but the abstract and Table 3 compare the realized median epsilon (2.40) with the unconditional mean epsilon (10), which overstates the advantage.\n\nWhat's actually new here is the combination of clustering with median aggregation. Median aggregation alone is known, and DP clustering is known, but the way they use public DBPedia centers and rebalance with a small privacy budget (epsilon=0.1) is practical and clearly explained. The ablation of Baseline++ (pretrained model, two in-context examples) is honest—they separate the gains from clustering and from the median. The empirical improvements are consistent across AGNews, Yelp, and NYT Topics, which gives me some confidence.\n\nThe soft spots are in the framing and transparency. The worst-case sensitivity of the median over logits in [-c,c] is bounded by the full range 2c, which, at c=6 and temperature 1.5, gives a per-token cost around exp(12/1.5)~2981; summed over ~1000 tokens, the worst-case epsilon is effectively unbounded. The algorithm only provides a finite guarantee ex-post, for the realized data and output. That's fine for a research contribution, but the comparison in the abstract needs a clear caveat. There's also an inconsistency: the paper motivates its clustering by saying prior work samples batches uniformly at random, but its own baseline (Amin et al.) uses within-label batching. That weakens the 'uniform sampling degrades quality' motivation. No code is released, and the reported epsilon values come from one run without seed variance, so it's hard to know how brittle the 2.4 number is.\n\nBottom line: this is a solid paper worth a serious referee. The privacy proof holds, and the empirical improvements are real on the domains tested. But before the 'significantly lower privacy cost' claim is citable, the authors need to reframe the comparison as ex-post vs. worst-case, report the worst-case sensitivity of the median, and clarify the batching history. I'd suggest the editor send it out, with a request for revisions along those lines. After that, I'd cite it.","headline":"The median aggregation and clustering are genuine improvements, but the 'significantly lower privacy cost' claim compares an ex-post data-dependent epsilon to a worst-case one, so the paper needs reframing before it's citable.","tokens_in":17211,"tokens_out":4298,"would_cite":false,"duration_ms":43390,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper claims that clustering sensitive inputs before batching, and aggregating next-token logits with a private median instead of an average, yields differentially private synthetic text that is more representative and produced at…","keywords":["differentially private inference","synthetic text generation","median aggregation","clustering","data-dependent differential privacy","ex-post privacy","MAUVE","large language models"],"falsifier":"Run the method on a private corpus drawn from a domain far outside DBPedia's coverage, such as structured clinical notes or source code, with the same public centers from DBPedia, and compare the reported per-batch epsilon and MAUVE against the AGNews results. If the cluster-size distribution is highly skewed and the median-gap epsilon at matching output exceeds the mean-based unconditional epsilon, the claimed privacy advantage fails in that regime. A direct complementary test: compute the median gap for batches constructed from a single Yelp cluster versus batches sampled uniformly from all Yelp labels; if the uniform batches do not show a larger per-token gamma and a larger summed epsilon, the mechanism's central premise is falsified.","tokens_in":16043,"feed_emoji":"🛡️","tokens_out":7548,"duration_ms":62797,"temperature":0.7,"pith_summary":"The paper argues that the low quality of differentially private synthetic text comes from a fixable design choice: sampling sensitive seed texts uniformly at random forms batches that mix unrelated topics, so the aggregated rewrite averages distinct semantic clusters into mush. It proposes to first cluster the seeds, using centers learned from a public dataset (DBPedia) with a small privacy cost for rebalancing, and then to aggregate the LLM's next-token logits within each batch by a component-wise median of clipped logits rather than the mean used by prior work. This combination lets the authors state a data-dependent, ex-post differential privacy guarantee, Theorem 1, whose per-batch and per-token privacy cost shrinks when the batch's next-token predictions align. On AGNews, Yelp, and NYT Topics, the method improves MAUVE and maintains downstream BERT accuracy while reporting substantially lower epsilon than the mean-based baseline (e.g., about 2.4 vs 9.9 + 0.1 on AGNews at matched output). A reader should care because this is a path to generating large, useful, and formally private synthetic corpora from an off-the-shelf LLM without training.","feed_headline":"Medians, not averages, cut privacy cost of synthetic text","feed_subtitle":"Cluster-based median aggregation produces representative text at far lower reported privacy cost.","key_machinery":"The central object is the median aggregation rule over clipped logit vectors, $\\operatorname{aggregate}(Z) = \\operatorname{median}(\\{\\operatorname{clip}_c(z) : z \\in Z\\})$, paired with cluster-based batching, $\\operatorname{batch}(s) = (\\operatorname{cluster}(s), r)$, where the cluster assignment $\\operatorname{cluster}(s)$ uses public k-means centers in Gecko embedding space and a noisy rebalancing step chooses the top-$k'$ centers. Clipping maps each logit vector's maximum component to $c$, forcing alignment of the most likely token across inferences; the median's local sensitivity is then governed by the median gap, the distance from the median to its neighbors in each token component. The proof of Theorem 1 builds on Lemma 1, which bounds the median of a neighboring batch between the left- and right-medians of the original batch, sandwiching the ratio of next-token sampling probabilities and yielding the per-token privacy cost function $\\gamma(Z, x)$ defined in Appendix A.","core_discovery":"The central claim is that clustering before batching and using the median instead of the mean for per-token aggregation yields differentially private synthetic text that is both more representative and cheaper in privacy. More precisely, the authors prove that Algorithm 1 with cluster-based batching (Eq. 1) and median aggregation (Eq. 2) satisfies $\\varepsilon$-data-dependent ex-post differential privacy with $\\varepsilon(D, X) = \\max_{i \\in [m]} \\sum_{t=1}^{n} \\gamma(Z_{i,t}, x_{i,t})$, where the per-token cost $\\gamma$ is an increasing function of the median gap of the clipped logit scores for the sampled token. The mechanism of the proof is that clipping aligns the heads of predicted distributions, and the median's local sensitivity is small exactly when the batch's predictions are similar, so homogeneity converts directly into a privacy saving. The experiments separate the contributions: clustering alone improves MAUVE even with infinite epsilon, and median aggregation matches or exceeds mean-based quality while reporting a data-dependent epsilon about a quarter of the mean's unconditional epsilon in the best cases.","pith_inferences":["If the median's local sensitivity keeps falling as batches become more aligned, one could adaptively sub-cluster or merge clusters until a target per-batch epsilon is reached, spending a little more of the small rebalancing budget to save a larger amount of inference budget; the paper's own per-batch plots (median 1.41 vs max 2.40 on AGNews) suggest this headroom exists.","The public-center approach is a transferable prior: the same DBPedia centers are used for all three private datasets, so a natural extension is to combine public centers from multiple text domains, or to run the private rebalancing step on a proxy embedding summary, to widen the domain of applicability beyond Wikipedia-like text.","The requirement of logit access limits deployment on sampling-only APIs; a testable extension is to replace the median of logits with a private aggregation over top-k sampled tokens, which would trade some alignment for API compatibility.","Because the paper uses clustering only to form batches, the same public centers could be reused to condition prompts on cluster identity, potentially improving the generator's adherence to cluster-consistent style or topic without additional privacy cost."],"forward_implications":["Uniform random batching is the wrong default for DP inference: clustering inputs before batching improves MAUVE even at infinite epsilon, and the gain stacks with other improvements.","Median aggregation converts the homogeneity gained from clustering into a formal privacy saving: because local sensitivity shrinks as predictions align, the same synthetic data can be generated with a smaller data-dependent epsilon than the mean-based baseline.","Data-dependent and ex-post accounting changes what practitioners should report: epsilon is now a function of the actual batch and output, so the effective privacy cost can be much lower than a worst-case bound; the paper's own per-batch plots show many batches below the reported max.","The method achieves high MAUVE (e.g., about 0.7 versus lower baseline scores) and BERT accuracy comparable to mean-based methods, meaning synthetic data is useful for downstream training.","Because the bound in Theorem 1 is a max over batches, adaptive generation that allocates more noise or more tokens to high-epsilon batches could bring the reported worst-case epsilon closer to the median batch epsilon."],"supporting_citations":[{"why":"Supplies the baseline DP inference algorithm (mean of clipped logits) that this paper modifies and compares against.","marker":"[Amin et al., 2024]"},{"why":"Establishes data-dependent differential privacy, the notion the paper's ex-post guarantee extends.","marker":"[Papernot et al., 2017, 2018]"},{"why":"Defines ex-post differential privacy, which Theorem 1 instantiates.","marker":"[Ligett et al., 2017]"},{"why":"Provides the exponential mechanism perspective used to view token sampling as a privacy mechanism in the proof.","marker":"[McSherry and Talwar, 2007]"},{"why":"Defines MAUVE, the metric that reveals the representativeness failure of prior DP inference baselines.","marker":"[Pillutla et al., 2021]"},{"why":"Provides Gecko embeddings used both for clustering seeds and for computing MAUVE scores.","marker":"[Lee et al., 2024]"},{"why":"One of the DP clustering methods tested and found to produce imbalanced clusters in high dimension, motivating public centers.","marker":"[Chang and Kamath, 2021]"},{"why":"Another DP clustering method compared in the clustering study.","marker":"[Liebenow et al., 2024]"}],"fun_headline_variants":["Cluster-then-median pipeline cuts privacy cost for synthetic text","Median beats mean for cheaper private synthetic text","Clustering and medians cut DP text privacy cost","Private text: cluster then median for lower epsilon"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The utility and the low reported privacy cost both rest on the assumption that public DBPedia cluster centers, after DP rebalancing, partition the private data into semantically homogeneous clusters; if the private domain differs greatly from Wikipedia-style text (for instance specialized medical records), clusters become imbalanced, batches stay heterogeneous, and the median's local sensitivity — and hence the reported epsilon — would be large, erasing the privacy-cost advantage.","fun_headline_variants_meta":{"raw":{"variants":["Cluster-then-median pipeline cuts privacy cost for synthetic text","Median beats mean for cheaper private synthetic text","Clustering and medians cut DP text privacy cost","Private text: cluster then median for lower epsilon"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000583,"raw_usage":{"total_tokens":2756,"prompt_tokens":973,"completion_tokens":1783,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":589,"completion_tokens_details":{"reasoning_tokens":1721}},"tokens_in":589,"tokens_out":1783,"duration_ms":13387,"temperature":1.0,"reasoning_tokens":1721,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T10:39:31.742846+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the method on a private corpus drawn from a domain far outside DBPedia's coverage, such as structured clinical notes or source code, with the same public centers from DBPedia, and compare the reported per-batch epsilon and MAUVE against the AGNews results. If the cluster-size distribution is highly skewed and the median-gap epsilon at matching output exceeds the mean-based unconditional epsilon, the claimed privacy advantage fails in that regime. A direct complementary test: compute the median gap for batches constructed from a single Yelp cluster versus batches sampled uniformly from all Yelp labels; if the uniform batches do not show a larger per-token gamma and a larger summed epsilon, the mechanism's central premise is falsified.","supporting_citations":[{"cited_title":"Private prediction for large-scale synthetic text generation","cited_arxiv_id":null,"evidence_quote":"Supplies the baseline DP inference algorithm (mean of clipped logits) that this paper modifies and compares against."},{"cited_title":"Differentially private synthetic data via foundation model APIs 2: Text","cited_arxiv_id":null,"evidence_quote":"Provides Gecko embeddings used both for clustering seeds and for computing MAUVE scores."}],"review_version":1}