Privacy-Preserving Data Deduplication for Enhancing Federated Learning of Language Models

Privacy-Preserving Data Deduplication for Enhancing Federated Learning of Language Models

Speakers: Vishnu Dasu, PhD student, Pennsylvania State University

Conference: NDSS Symposium

YouTube: https://www.youtube.com/watch?v=8yK3GbeuDSU

Overview

This talk, presented by Vishnu Dasu, a PhD student at the Pennsylvania State University, introduces a novel solution called Efficient Privacy-Preserving Multi-Party Deduplication (EPMPD). The core problem addressed is the pervasive issue of duplicated text sequences within vast datasets used to train large language models (LLMs). Such duplicates are known to significantly degrade LLM performance, increasing perplexity (a measure of model uncertainty) and extending training times. While deduplication is a straightforward task in centralized data settings, it becomes inherently complex and privacy-sensitive within the federated learning (FL) paradigm, where multiple clients collaboratively train a global model without sharing their raw data.

The research directly tackles this privacy challenge by developing a method to securely remove pairwise duplicates across client datasets in a federated setting. EPMPD leverages a new variant of Private Set Intersection (PSI) protocols, dubbed Group Private Set Intersection (GPSI), as its foundational building block. By enabling collaborative deduplication without revealing individual client data, EPMPD not only enhances the quality and efficiency of federated LLM training but also mitigates privacy risks associated with model memorization of repeated data.

The significance of this work extends to the practical deployment of LLMs in privacy-conscious environments. By improving model performance metrics like perplexity and reducing computational overhead, EPMPD offers a critical advancement for the responsible development and application of AI. The presented solution demonstrates substantial improvements in both training efficiency and model quality, making a compelling case for its adoption in real-world federated learning scenarios.

Background

▶ Watch: Introduction and problem: duplicated data impacts LLMs (0:00)

The quality of training data is paramount for the performance of machine learning algorithms, especially for large language models (LLMs) that ingest massive text datasets. A significant challenge in these datasets is the prevalence of duplicated or near-duplicated text sequences. Prior research has consistently shown that these duplicates negatively impact LLMs by increasing their perplexity and extending their training time. For instance, the C4 dataset, a common benchmark, was found to contain a specific 61-word sequence repeated approximately 61,000 times, with deduplication efforts leading to a 10% improvement in perplexity. Perplexity, in this context, serves as a metric for how well an LLM predicts subsequent words; lower perplexity generally indicates better performance.

The complexity of data deduplication escalates dramatically in federated learning (FL) environments. In FL, a central server orchestrates the training of a global model using datasets distributed across numerous clients. A fundamental tenet of FL is data privacy: the server only aggregates gradient updates and never directly accesses raw client data, nor do clients see each other's datasets. This setup makes traditional centralized deduplication approaches, which assume a single entity has access to all data, inherently incompatible due to privacy concerns. While prior work has addressed deduplication in centralized settings, the problem of privacy-preserving deduplication in a multi-party, federated context remained largely unsolved. The challenge lies in identifying and removing identical data entries across multiple clients without any client revealing their private data to others or to a central server. This privacy requirement necessitates cryptographic techniques to enable collaborative computation over encrypted or obfuscated data.

Key Findings

▶ Watch: Introducing EPMPD solution and Group Private Set Intersection (GPSI) (1:40)

The research introduces EPMPD (Efficient Privacy-Preserving Multi-Party Deduplication), a novel solution designed to securely remove all pairwise duplicates from datasets held by multiple clients in a federated learning setting. A cornerstone of EPMPD is the introduction of Group Private Set Intersection (GPSI), a new variant of the traditional Private Set Intersection (PSI) protocol, which serves as a fundamental building block.

The key findings and contributions include:

1. Introduction of Group Private Set Intersection (GPSI): This new cryptographic primitive extends the concept of PSI from two parties to two groups of parties, enabling all clients in one group to find the pairwise intersection of their sets with the sets of all clients in the other group, without revealing non-intersecting elements.
2. Development of Two GPSI Protocols (eGPSI1 and eGPSI2):

• eGPSI1 relies on private key encryption and a Trusted Execution Environment (TEE) for efficient processing of shared encrypted data.
• eGPSI2 utilizes public encryption and Oblivious Pseudo-Random Functions (OPRFs), also leveraging a TEE, but with a different computational trade-off.

1. EPMPD Architecture for Multi-Party Deduplication: EPMPD employs a binary tree structure where leaf nodes represent clients. By iteratively invoking GPSI protocols on clusters formed at each level of the tree, EPMPD systematically removes all pairwise duplicates across all participating clients.
2. Significant Performance Improvements in Federated LLM Training: Experimental evaluation demonstrated substantial enhancements post-deduplication:

• Perplexity Improvement: Up to a 19.6% reduction in perplexity (observed with the SThePlace dataset and GPT2 medium), indicating a significantly better-performing language model.
• GPU Training Time Reduction: Up to a 27.9% decrease in GPU training time (observed with the Sonnets dataset and GPT2 medium), leading to more efficient resource utilization.

1. Scalability and Efficiency: EPMPD exhibited remarkable scalability, achieving up to a 14x speedup compared to a naive approach of running N-choose-2 two-party PSI protocols, especially as the number of clients increased (from 10 to 50).
2. Enhanced Privacy Guarantees: Beyond efficiency, the research highlights that privacy-preserving deduplication helps mitigate risks associated with LLM memorization, thereby decreasing the success rate of membership inference attacks or data extraction attacks.

These findings collectively present a robust and practical solution for a critical problem in federated learning, offering both performance and privacy benefits for LLM development.

Technical Deep Dive

▶ Watch: Detailed explanation of the novel Group PSI (GPSI) concept (2:50)

The core innovation of this work lies in its approach to privacy-preserving deduplication in a multi-party federated learning setting, building upon the well-established cryptographic primitive of Private Set Intersection (PSI).

Private Set Intersection (PSI) Protocols:

At its foundation, a PSI protocol allows two mutually distrustful parties, say Alice and Bob, to compute the intersection of their private sets of elements without revealing any elements beyond the intersection to either party. For example, if Alice has {1, 2, 3} and Bob has {1, 3, 4, 5, 9}, after a PSI computation, both learn that the intersection is {1, 3}. Crucially, Bob learns nothing about Alice's 2, and Alice learns nothing about Bob's 4, 5, 9. This basic concept is extended to address the multi-party deduplication challenge.

Group Private Set Intersection (GPSI):

To scale PSI to multiple clients in a federated setting, the authors introduce Group Private Set Intersection (GPSI). Unlike traditional PSI which operates on two individual parties, GPSI operates on two groups of users or clients. The functionality allows all clients in one group (G0) to find the pairwise intersection of their individual sets with the sets of all clients in the other group (G1).

Formally, if G0 contains clients with sets S01, S02, ..., S0M and G1 contains clients with sets S11, S12, ..., S1M, the output of the GPSI protocol for each client is a vector containing the intersection of its set with the sets of clients in the other group. This means client S0i would learn S0i ∩ S1j for all j, and S1j would learn S1j ∩ S0i for all i. This collective, yet private, intersection discovery is central to EPMPD.

The paper details two concrete protocols that implement GPSI:

1. eGPSI1 (Private Key Encryption based):

• This protocol relies on private key encryption.
• Clients in both groups first engage in a pairwise key exchange.
• They then compute a pseudorandom permutation of their set elements to encrypt them.
• These encrypted elements are shared with a Trusted Execution Environment (TEE).
• The TEE's role is to find the shared encrypted data (the intersection) and send the corresponding shared data back to the clients in each group.
• Clients can then decrypt this shared data to identify common elements with clients in the other group.
• eGPSI1 requires the TEE primarily for identifying the shared encoded data and generally demands relatively little processing time from the TEE itself.

1. eGPSI2 (Public Key Encryption based):

• This protocol utilizes public key encryption and Oblivious Pseudo-Random Functions (OPRFs).
• Clients use a TEE at the beginning to compute the OPRF evaluation of their set elements. This step encrypts the data in a way that allows for private comparison.
• Once the OPRF evaluations are performed, clients can exchange their encrypted elements with clients from the other group.
• This exchange allows them to find common intersections without further TEE involvement.
• While eGPSI2 might require more initial processing time for the OPRF evaluation by the TEE, it eliminates the need for the TEE in subsequent comparison steps.

Crucially, the security assumptions regarding the TEE are conservative. The TEE is assumed to be a semi-honest server that does not collude with the clients, meaning it honestly executes the protocol but might try to infer information if it could. The flexibility exists to replace the TEE with any other semi-honest server that meets this non-collusion criterion.

EPMPD Architecture for Deduplication:

EPMPD leverages GPSI as a fundamental building block to remove all pairwise duplicates across multiple clients. It employs a binary tree structure for this purpose:

• Leaf Nodes: Represent individual clients participating in federated learning.
• Clustering: At each level of the binary tree, clients are organized into clusters. Within each cluster, the left and right subtrees logically represent the two groups (G0 and G1) required for a GPSI protocol.
• Iterative Invocation: Starting from the lowest level (leaves), EPMPD iteratively invokes GPSI protocols on these clusters as it moves up the tree.
• Lowest Level: Each cluster consists of two groups, each containing a single client (e.g., Client C1 in G0 and Client C2 in G1). They engage in GPSI to find and remove duplicates between C1 and C2.
• Mid-Levels: Clusters now contain multiple clients in each group (e.g., C1-C2 in G0 and C3-C4 in G1). GPSI is invoked to find duplicates between any client in the first group and any client in the second group.
• Root Level: At the root, the entire set of clients is divided into two large groups (e.g., C1-C4 in G0 and C5-C8 in G1). A final GPSI invocation ensures all remaining pairwise duplicates across these larger groups are identified and removed.
• Completion: Once the root of the tree is reached, all pairwise duplicates that existed across any combination of client datasets have been securely identified and removed.

End-to-End Functionality in Federated Learning:

The complete EPMPD workflow within a federated learning context involves three main steps:

1. Local Deduplication: Each client first performs simple local deduplication on its own dataset. This step is trivially private as it involves only the client's data.
2. EPMPD for Pairwise Deduplication: After local duplicates are removed, clients collectively run the EPMPD protocol (utilizing GPSI) to remove all pairwise duplicates that exist across their respective datasets.
3. Federated Model Training: Once all duplicates (both local and cross-client) have been removed, the clients can then proceed to join any chosen federated learning protocol to train their language model on the now clean, deduplicated datasets.

This multi-stage approach ensures that the training data is optimized for quality and efficiency while strictly adhering to the privacy requirements of federated learning.

Demo / Proof of Concept

▶ Watch: EPMPD's binary tree structure for pairwise deduplication (6:00)

While the talk did not feature a live, interactive demonstration, the research included a comprehensive experimental evaluation acting as a proof of concept for EPMPD's efficacy and efficiency. The evaluation involved implementing EPMPD and assessing its performance in a simulated federated learning environment.

Implementation Details:

The EPMPD protocol was implemented in Python.

• For the eGPSI1 variant, AES 128 CBC was used as the pseudorandom permutation for encryption.
• For the eGPSI2 variant, ECOP RF (Elliptic Curve Oblivious Pseudo-Random Function) was employed.

Federated Learning Setup:

• The experiments simulated a federated learning environment with 10 clients.
• Seven diverse text datasets were used to fine-tune language models.
• The percentage of duplicates within the datasets was varied, ranging up to 30%, to observe the impact of different levels of data redundancy.
• The language models used for fine-tuning were GPT2 medium and GPT2 large.

Evaluation Metrics and Comparison:

The primary metrics for evaluating EPMPD's impact were:

1. Perplexity: A measure of how well an LLM predicts a sample, with lower perplexity indicating better performance.
2. GPU Training Time: The computational time required to train the models, reflecting efficiency.

EPMPD's performance (using both eGPSI1 and eGPSI2 variants) was compared against a "naive approach" for multi-party deduplication. This naive approach involved running a traditional two-party PSI protocol n choose 2 times, where n is the number of clients, to find all pairwise intersections.

Experimental Results:

• Scalability and Speedup: When varying the client count from 10 to 50, with a fixed dataset size of 2^19 elements, EPMPD demonstrated significant speedups. The variant utilizing the faster eGPSI1 achieved up to a 14-time speedup with 50 clients compared to the naive n choose 2 PSI approach. Even the EPMPD variant using the slower eGPSI2 (based on OPRF) was still faster than the naive method. This highlights EPMPD's efficiency gains, especially as the number of participants in federated learning grows.
• Perplexity Improvement: The evaluation showed a clear trend: perplexity increased with a higher percentage of duplicates. After deduplication with EPMPD, significant improvements were observed. The best improvement was a 19.6% reduction in perplexity for the SThePlace dataset when fine-tuning GPT2 medium. This indicates that EPMPD leads to more accurate and better-performing language models.
• GPU Training Time Improvement: Similarly, deduplication drastically reduced training times. The most substantial improvement was observed for the Sonnets dataset with GPT2 medium, where a 27.9% reduction in total GPU training time was achieved. This demonstrates EPMPD's ability to enhance computational efficiency and reduce resource consumption in federated LLM training.

The experimental results robustly validate EPMPD as an effective and efficient solution for privacy-preserving data deduplication in federated learning, providing concrete evidence of its benefits in terms of model quality and training efficiency.

Defensive Implications

▶ Watch: Concrete example: EPMPD deduplication with an 8-client binary tree (6:30)

The research on privacy-preserving data deduplication has significant defensive implications for organizations and individuals involved in federated learning, particularly concerning the security and privacy of sensitive data. Beyond the immediate benefits of improved model performance and reduced training time, EPMPD directly addresses several critical privacy risks inherent in federated learning.

One of the most crucial defensive implications stems from the direct link between data duplicates and model memorization. Language models, when exposed to highly repeated sequences in their training data, are prone to "memorizing" these sequences verbatim. This memorization can inadvertently create serious privacy vulnerabilities. As Vishnu Dasu explained during the Q&A, increased memorization in LLMs can significantly increase the success rate of membership inference attacks and data extraction attacks.

• Membership Inference Attacks: In these attacks, an adversary attempts to determine whether a specific data record was part of the model's training dataset. If a model has memorized unique or rare data points due to repetition, it becomes easier for an attacker to infer membership. By removing duplicates, EPMPD reduces the likelihood of such explicit memorization, thereby making it harder for attackers to confidently assert that a particular user's data was included in the training set. This strengthens the privacy guarantees for individual data contributors.

• Data Extraction Attacks: These attacks aim to reconstruct or extract specific training data records directly from the model. If a model has overfit or memorized repeated sensitive information, an attacker might be able to query the model and extract parts of the original training data. Deduplication, by ensuring that the model is not over-exposed to redundant sensitive information, makes it more challenging for attackers to successfully reconstruct or extract private data. This directly protects the confidentiality of client data.

Therefore, defenders should consider integrating privacy-preserving deduplication techniques like EPMPD into their federated learning pipelines as a fundamental privacy-enhancing technology. It acts as a proactive measure to:

1. Reduce Model Vulnerabilities: By preventing LLMs from memorizing redundant data, it inherently reduces the attack surface for privacy-oriented adversarial attacks.
2. Enhance User Trust: Implementing such measures demonstrates a commitment to protecting user data, which is crucial for building and maintaining trust in AI systems.
3. Improve Data Utility: While primarily a defensive measure for privacy, the improved data quality resulting from deduplication also leads to more robust and generalized models, indirectly enhancing the utility of the federated learning system.

In essence, EPMPD offers a dual benefit: it optimizes model training for performance and simultaneously hardens the model against privacy breaches by reducing the risk of unintended data leakage through memorization.

Key Takeaways

• Duplicates Harm LLM Performance: Redundant data in large text datasets significantly increases language model perplexity and training time, as shown by examples like the C4 dataset.
• EPMPD for Privacy-Preserving Deduplication: The proposed Efficient Privacy-Preserving Multi-Party Deduplication (EPMPD) protocol enables secure removal of all pairwise duplicates across client datasets in federated learning without compromising data privacy.
• Group Private Set Intersection (GPSI) is a Key Innovation: EPMPD is built upon a novel cryptographic primitive called Group Private Set Intersection (GPSI), which allows groups of clients to find common elements without revealing non-intersecting data.
• Significant Performance Gains: Deduplication with EPMPD leads to substantial improvements: up to a 19.6% reduction in perplexity and up to a 27.9% decrease in GPU training time. It also offers up to a 14x speedup over naive N-choose-2 PSI.
• Mitigation of Privacy Risks: By reducing model memorization caused by repeated data, EPMPD helps decrease the success rate of membership inference attacks and data extraction attacks, thereby enhancing data privacy in federated learning.
• Future Work on Near Duplicates: The current work focuses on exact duplicates, with future research avenues including the challenging problem of identifying and removing "near duplicates" (e.g., parts of sentences or slightly altered text sequences).

About the Speaker(s)

The presenter of this talk is Vishnu Dasu, a PhD student studying computer science at the Pennsylvania State University. His research focuses on privacy-preserving techniques in machine learning, particularly within the context of federated learning and language models. His work, as demonstrated in this presentation, aims to enhance the efficiency and privacy of AI systems by addressing fundamental data quality challenges.