PaperlayerView exact revision on arXiv

Source-linked AI summary

Struct-Bench: A Benchmark for Differentially Private Structured Text Generation

Shuaiqi Wang, Vikas Raunak, Arturs Backurs, Victor Reis, Pei Zhou, Sihao Chen, Longqi Yang, Zinan Lin, Sergey Yekhanin, Giulia Fanti

arXiv:2509.10696v1cs.CLcs.LG

TL;DR

Existing benchmarks do not explicitly evaluate structure in datasets that also contain natural-language fields, limiting their scope. Struct-Bench introduces a benchmark for such synthetic data and finds that current DP generators struggle to preserve structure alongside semantic performance, while a case study improves Private Evolution on these measures.

  • Problem

    Existing DP synthetic-data benchmarks either do not explicitly consider data structure or are limited to numerical and categorical data, leaving structured datasets with natural-language fields outside their scope.

    Source: §5 · p. 12

  • Method

    Struct-Bench is a composite benchmark for evaluating synthetic data derived from structured datasets containing natural language, with dataset structure represented using CFGs.

    Source: §1 · p. 2, §6 · p. 12

  • Results

    Across seven datasets, no single metric fully describes quality, and SOTA DP generators do not reliably capture structure without sacrificing semantic performance; a Private Evolution case study reaches nearly 100% structural-constraint compliance while improving semantic and statistical metrics.

    Source: §1 · p. 3

  • Takeaways & Limitations

    Struct-Bench’s diverse dataset collection may preclude algorithmic research from overfitting to only a few data types.

    Source: §6 · p. 12

    Struct-Bench is designed to measure similarity between synthetic and real datasets in the DP setting; its use for non-private synthetic data is left to future work.

    Source: §2 · p. 4

Abstract

from arXiv · show

Differentially private (DP) synthetic data generation is a promising technique for utilizing private datasets that otherwise cannot be exposed for model training or other analytics. While much research literature has focused on generating private unstructured text and image data, in enterprise settings, structured data (e.g., tabular) is more common, often including natural language fields or components. Existing synthetic data evaluation techniques (e.g., FID) struggle to capture the structural properties and correlations of such datasets. In this work, we propose Struct-Bench, a framework and benchmark for evaluating synthetic datasets derived from structured datasets that contain natural language data. The Struct-Bench framework requires users to provide a representation of their dataset structure as a Context-Free Grammar (CFG). Our benchmark comprises 5 real-world and 2 synthetically generated datasets, each annotated with CFGs. We show that these datasets demonstrably present a great challenge even for state-of-the-art DP synthetic data generation methods. Struct-Bench also includes reference implementations of different metrics and a leaderboard, thereby providing researchers a standardized evaluation platform to benchmark and investigate privacy-preserving synthetic data generation methods. Further, we also present a case study showing how to use Struct-Bench to improve the synthetic data quality of Private Evolution (PE) on structured data. The benchmark and the leaderboard have been publicly made available at https://struct-bench.github.io.

1 Introduction

Struct-Bench targets structured datasets that contain natural-language fields, where existing unstructured-text and tabular evaluation approaches do not capture both structure and content. It provides a CFG-based benchmark and uses it to assess DP generators and study improvements to Private Evolution.

1 Introduction

  • Existing text and tabular evaluation metrics do not naturally capture both structural relations and natural-language content in the same dataset.For example, semantically reasonable text can violate required format, while tabular marginal comparisons are not meaningful for natural language.Source: §1 · p. 2
  • Struct-Bench represents dataset structure with a user-provided CFG and measures syntactic and semantic properties of generated data against real data.Users select key nodes from parse trees to measure important correlations and properties.Source: §1 · p. 2
  • The framework includes a public leaderboard and extensible reference implementation for standardized benchmarking of DP synthetic data methods on additional datasets.Source: §1 · p. 3
  • Across seven diverse datasets, no single metric fully describes quality, and existing SOTA DP generators do not reliably preserve structure without sacrificing semantic performance.A case study improves Private Evolution [27] [60] [28], achieving nearly 100% structural-constraint compliance while also improving semantic and statistical metrics.Source: §1 · p. 3

2 Struct-Bench Framework and Evaluation Protocol

Struct-Bench represents real datasets and their structural dependencies with user-specified CFGs, then evaluates synthetic data with structural, non-structural, and downstream-task metrics. Its comparisons are intended for DP synthesis, and its pairwise dependency metric does not cover higher-order relationships.

2 Struct-Bench Framework and Evaluation Protocol

  • The framework compares real and synthetic datasets by measuring how well the synthetic data matches the real data’s structure and content.Inputs include both datasets, a CFG, and optionally key nodes whose correlations matter.Source: §2 · pp. 3–4
  • Users encode structural dependencies in a CFG, which Struct-Bench uses to parse each sample; key nodes can identify node types expected to have strong dependencies.The authors choose CFGs over more expressive context-sensitive grammars because those require more domain knowledge and detail; KND assesses semantic dependencies empirically.Source: §2 · pp. 3–4
  • Struct-Bench is designed to measure similarity between synthetic and real datasets in the DP setting; applying its metrics to non-private synthesis is left for future work.Source: §2 · p. 4

2.1 Struct-Bench Metrics

  • Structural metrics assess parse validity, key-node-pair dependencies, and sample- or node-level attribute distributions.CFG-PR measures the fraction of samples that parse correctly, while KND and Attribute Match compare distributions between private and synthetic data.Source: §2.1 · pp. 4–5
  • KND measures node-pair dependencies, not higher-order relationships, which are omitted because they are more computationally intensive and dependency functions vary by scenario.Source: §2.1 · p. 4
  • Non-structural KNN precision and recall assess semantic quality and diversity, while downstream evaluation measures label-prediction accuracy on held-out real data.The downstream pipeline can use human- or LLM-generated labels, trains a model on synthetic data, and evaluates it using the TSTR setup.Source: §2.1 · p. 5

3 Benchmarking Differentially Private Synthetic Data

Struct-Bench evaluates synthetic data against real datasets with structural relations and natural-language fields, using diverse datasets and DP generation baselines. The results show that no single metric captures quality and that existing methods struggle to balance structural fidelity with semantic performance.

3.1 Struct-Bench Datasets

  • The benchmark includes graph-structured ShareGPT and ICLR reviews, three tabular datasets, and two synthetic datasets with controllable structural and semantic attributes.The tabular datasets are Water, Arena, and Adult; the synthetic datasets are Synthetic Reviews and Synthetic Grounding.Source: §3.1 · pp. 5–6

3.2 Struct-Bench Synthetic Data Generation Baselines

  • The evaluated generators include PE, instruction following, DP fine-tuning, and real-data fine-tuning, with instruction-conditioned variants of the fine-tuning baselines.PE uses a random-sampling API and iteratively applies private voting and variation; DP-FT uses DP-SGD, while FT has no privacy guarantee.Source: §3.2 · pp. 6–7

3.3 Experimental Results

  • No single metric describes synthetic-data quality; all baselines score below 0.2 CFG-PR on the more intricate ICLR dataset, while PE and IF can capture structure but have poor semantic performance.Figure 2 shows near-zero KNN-Recall for baselines on tabular and synthetic datasets; with GPT-4o, PE and IF achieve perfect CFG-PR on tabular and synthetic datasets.Source: §3.3 · p. 7, Figure 2 · p. 8
  • At ε = 4, DP fine-tuning alone scores 0 CFG-PR across datasets; non-private fine-tuning also fails to learn structure except on ShareGPT, where it scores 0.53.The paper suggests ShareGPT's fewer formatting tokens, compared with JSON tags in tabular datasets, may explain the exception.Source: §3.3 · p. 7
  • With GPT-2, Instruct DP-FT performs comparably to PE across most metrics on ShareGPT and ICLR, while PE can use state-of-the-art API models without model training.The authors note that the performance gap may reflect both foundation-model differences and instruction-guided generation.Source: §3.3 · p. 7

4 Case Studies

The ShareGPT case study uses Struct-Bench to diagnose structural-validity and semantic-diversity problems in Private Evolution (PE), then tests reformatting and node extraction as improvements. Combining the proposed methods raises CFG-PR while performing comparably or better on most reported metrics.

4 Case Studies

  • The case study uses ShareGPT and Llama3-8b for cost and accessibility, focusing on structural validity and semantic diversity while deferring KND analysis.The authors note GPT-4o might achieve stronger performance.Source: §4 · p. 9

Problem 1: Structural Validity (CFG-PR) is low

  • Vanilla PE’s CFG-PR stays below 60% when ϵ ≤ 4 and reaches about 63% without added noise.The authors suggest smaller foundation models such as Llama3-8B may not capture even simple structural constraints.Source: §4 · p. 9, Figure 3 · p. 9
  • Reformatting can restore valid structure while distorting meaning, and reformatting before voting may bias selection against semantically consistent but structurally invalid samples.After-voting reformatting applies to highly voted samples without another selection stage.Source: §4 · p. 9, Figure 5 · p. 10
  • Over 20% CFG-PR improvement over vanilla PE: both reformatting approaches improve compliance, with reformatting after voting performing best.The comparison is at ϵ = 4.Source: Figure 4 · p. 9, §4 · p. 9

Problem 2: Semantic diversity (KNN-Recall) is low

  • As ϵ increases, vanilla PE’s KNN-Precision rises from 0.56 to 0.69, while KNN-Recall remains around 0.35.The paper interprets this pattern as vanilla PE focusing on semantic quality while sacrificing diversity.Source: §4 · p. 10

Solution 2: Node extraction & auto-generation can improve semantic diversity

  • Node extraction blank-fills selected nodes and lets the LLM generate remaining nodes with fewer semantic constraints, without additional privacy cost.The user specifies which nodes to extract; the remaining nodes are generated from those extracted nodes and their blank-filled variations.Source: §4 · p. 10, Figure 7 · p. 11
  • Extract Query improves both KNN-Recall and KNN-Precision, while Extract Response does not improve recall; node extraction also raises CFG-PR over vanilla PE.The authors attribute the recall difference to semantic diversity depending mainly on responses, while queries are fairly constrained for a given response.Source: §4 · p. 10, Figure 8 · p. 11

Combination of our solutions achieves the best performance on most metrics

  • Up to 94% CFG-PR: PE + Reformat + Extract Query outperforms or matches the other methods on most reported metrics.These include KNN-Precision, KNN-Recall, and AM on response token length and number of nodes.Source: Figure 9 · p. 12, §4 · p. 12

5 Related Work

Prior DP synthetic-data work spans several data types, and Private Evolution methods can use pretrained models without training on private data. Existing evaluation benchmarks, however, do not explicitly address structure across data types or are limited to numerical and categorical data.

Related work

  • Struct-Bench is situated within synthetic-data generation and evaluation under differential-privacy constraints.Source: §5 · p. 12

Differentially Private (DP) Synthetic Data Generation

  • Private Evolution methods leverage pretrained models or non-neural tools, and prior work [27] [60] [28] finds PE competitive with DP fine-tuning without training on private data.The passage lists additional PE references as [27] [60] [28] [22] [68] [23] [57].Source: §5 · p. 12

DP Synthetic Data Evaluation

  • Prior DP synthetic-data benchmarks cover images, text, tabular data, time series, and graphs, but either omit explicit structure or are limited to numerical and categorical data.The paper argues a unified evaluation framework can provide fine-grained signals on algorithmic progress.Source: §5 · p. 12

6 Conclusion

Struct-Bench is presented as a composite benchmark for evaluating differentially private synthetic data derived from structured datasets containing natural language. Its evaluations characterize limitations of existing methods and include a case study on improving them.

6 Conclusion

  • To the authors’ knowledge, Struct-Bench is the first benchmark to comprehensively evaluate DP synthetic data derived from structured datasets containing natural language.Its diverse dataset collection is intended to preclude algorithmic research from overfitting to only a few data types.Source: §6 · p. 12
  • The evaluations characterize limitations of existing state-of-the-art DP synthetic data generation methods.The conclusion also reports a case study showing how Struct-Bench insights can improve those methods.Source: §6 · pp. 12–13
  • The paper conducts a case study to show how to improve state-of-the-art methods using insights from Struct-Bench.Source: §6 · p. 13

A Metric Definitions and Instantiation Guidelines

The appendix defines metrics for comparing synthetic and original data distributions and offers guidelines for selecting key nodes, attributes, and downstream labels. Together, these metrics assess structural, attribute-level, and task performance properties.

A.1 Key Node Dependency (KND)

  • KND measures the Wasserstein-2 distance between distributions of embedding cosine similarities for selected node pairs in synthetic and original data.Users can designate key nodes; otherwise, all CFG-parsed nodes are treated as key nodes by default.Source: §A.1 · p. 18

A.2 Attribute Match (AM)

  • AM measures attribute distribution distance, using Wasserstein-2 for numeric attributes and total variation distance for categorical attributes.Users may select semantic or statistical attributes relevant to downstream tasks, including topic, sentiment, and token length.Source: §A.2 · p. 18

A.3 Downstream Evaluations (DE)

  • For downstream evaluations, labels may be extracted from samples or generated from relevant sample- or node-level properties.The guidelines recommend a prompt template to discourage prompt gaming by data uploaders.Source: §A.3 · p. 18

B Data Modeling and Evaluation Items of Each Dataset

The appendix illustrates ShareGPT’s CFG-based data modeling, describes the benchmark datasets and evaluation items, and reports implementation and cross-dataset benchmarking setup. The dataset collection includes real-world and controllable synthetic data.

B.1 Examples on ShareGPT

  • ShareGPT conversations are modeled as repeated query-response rounds, with HUMAN and GPT prefixes delimiting query and response text.The example shows a multi-round exchange represented by the conversation grammar.Source: §B.1 · p. 19

B.2 Dataset Descriptions

  • The datasets span ShareGPT conversations, ICLR reviews and rebuttals, Water reviews, Arena conversation pairs, Adult census data, and two synthetic datasets.Synthetic Reviews contains extreme positive or negative examples; the Synthetic Grounding Dataset varies source consistency and query relevance, with balanced splits on those attributes.Source: §B.2 · pp. 19–20

B.3 Data Modeling of Each Dataset

B.4 Evaluation Metrics of Each Dataset

  • The evaluation items are summarized in Table 5, including dataset-specific KND, AM, and downstream prediction accuracy measures for ShareGPT and ICLR.ShareGPT evaluates query-response semantic similarity, query token-length distance, and topic prediction; ICLR evaluates review-rebuttal semantic similarity, review token-length distance, and research-area prediction.Source: §B.4 · p. 20, Table 5 · p. 22

C Additional Results on Struct-Bench

  • The additional-results experiments used eight H100 GPUs and took approximately 400 GPU hours; instruction fine-tuning ran for 20 epochs with batch size 32.The fine-tuning setup used weight decay 0.01 and learning rate 10^-4, with instructions prepended to each training sample.Source: C Additional Results on Struct-Bench · pp. 20, 23

C.1 Benchmarking DP Synthetic Data Generation Across Datasets

  • The cross-dataset benchmarking results at ϵ = 4 are reported in Table 6, using GPT-2 for FT and DP-FT and GPT-4o for IF and PE.Source: §C.1 · p. 23, Table 6 · p. 23

C.2 Benchmarking DP Synthetic Data Generation with Varying Privacy Budget

The appendix plots PE and DP-FT performance across privacy budgets on ShareGPT and ICLR, then examines instruction-guided generation on ShareGPT. In that comparison, Instruct DP-FT is similar to PE on most metrics and slightly better on CFG-PR.

C.2 Benchmarking DP Synthetic Data Generation with Varying Privacy Budget

C.3 Benchmarking DP Synthetic Data Generation on ShareGPT using Llama2-7b

  • For radar-plot comparisons, CFG-PR=0 or a dataset-inapplicable structure-related metric scores 0; other metric values are rescaled from 20 (worst among all methods) to 100 (synthetic-data performance upper bound).Source: §C.3 · p. 24

D Detailed analysis of the case study on PE

C.3 Benchmarking DP Synthetic Data Generation on ShareGPT using Llama2-7b

  • Instruct DP-FT achieves similar performance to PE on most metrics and has a slight edge in CFG-PR on ShareGPT using Llama2-7b with ϵ = 4.DP-FT does not learn structural information according to CFG-PR.Source: §C.3 · p. 24, Figure 13 · p. 25

D.1 Analyzing Vanilla PE on ShareGPT Dataset

On ShareGPT, vanilla PE’s structural and semantic performance varies with privacy level, and its structural metrics remain weak at ε ≤ 4. The CFG reformat prompt specifies how conversations are organized into alternating user and assistant turns.

D.1 Analyzing Vanilla PE on ShareGPT Dataset

  • The ShareGPT evaluation covers semantic and statistic metrics, CFG-PR, and KNN-Precision and KNN-Recall across ε ∈ {1, 2, 4, ∞}; ε = 0 is excluded because its CFG-PR is 2%.The metrics are listed in Table 7.Source: §D.1 · p. 26, Table 7 · p. 26
  • CFG-PR falls below 60% when ε ≤ 4, and PE mainly preserves non-structural semantic quality while performing poorly on semantic diversity and structure-based properties.Only CFG-PR and KNN-Precision improve as ε increases; KNN-Recall remains around 0.35, while other semantic metrics and all statistic metrics do not necessarily improve with relaxed privacy.Source: §D.1 · p. 26

D.2 CFG Reformat Prompt

  • The CFG reformat prompt represents ShareGPT conversations as one or more rounds, each containing a user request followed by a GPT response.Turns alternate, conversations begin with a user prompt, and the prompt instructs reformatting without changing conversation content.Source: §D.2 · p. 26

D.3 Further Analysis on CFG Reformat as Self-debugging

The appendix tests CFG reformatting and fixed format tokens as ways to improve PE’s structural and semantic properties. The interventions involve trade-offs: reformatting can lower semantic and statistic performance, while fixing tokens can constrain blank-filling.

D.3 Further Analysis on CFG Reformat as Self-debugging

  • CFG reformatting after voting raises CFG-PR but lowers semantic and statistic performance when reformatted samples are used directly as outputs or seeds for the next PE iteration.The comparison is between vanilla PE and PE with CFG reformat on ShareGPT.Source: §D.3 · pp. 26, 28, Figure 15 · p. 28

D.4 Improving Node Dependency (KND): Fix Format Token in Variation API

  • Fixed format tokens improve KND on query-response and response-query pairs and CFG-PR; fixing all tokens performs better on KND than fixing 65%.Keeping format tokens prevents node merging, which helps preserve node semantic dependencies and structural validity.Source: §D.4 · p. 28
  • Fixing all format tokens makes blank-filling less flexible, and its performance on most statistic properties is worse than vanilla PE and the 65%-fixed variant.Existing format tokens ensure the number of nodes after blank-filling will not decrease.Source: §D.4 · p. 28

D.5 Further Analysis on Node extraction & Auto-generation

Across the compared ShareGPT methods, the strongest results differ by metric: a combined query-extraction method leads on several structural, semantic, and statistic properties, while another combination performs best on KND. Node extraction results also vary by the node type and method combination.

D.5 Further Analysis on Node extraction & Auto-generation

  • Extract Query has a higher Type to Token Ratio than vanilla PE, and its sample embeddings overlap more with private-data embeddings, indicating higher semantic quality and diversity.Type to Token Ratio measures unique tokens divided by total tokens; higher values indicate more diverse vocabulary.Source: §D.5 · pp. 28, 30, Figure 18 · p. 29, Figure 19 · p. 30
  • Extract Query outperforms vanilla PE on most statistic properties, CFG-PR, KNN-Precision, KNN-Recall, and response-query KND; query extraction also outperforms response extraction.Extract Query & Reformat & Fixed Selected Token performs as well as or better than other node-extraction variants on CFG-PR, most statistic metrics, and most semantic metrics.Source: §D.5 · p. 30, Figure 20 · p. 31

D.6 Performance Comparison between Different Methods

  • Extract Query & Reformat & Fixed Selected Token leads on CFG-PR, KNN-Precision, KNN-Recall, conversation-round AM, and response-token-length AM, while Fixed Token & Reformat leads on KND for both node pairs.The paper notes that no single compared method leads on all evaluation metrics.Source: §D.6 · p. 30, Figure 21 · p. 31
Loading 2509.10696v1…