On Provable Copyright Protection for Generative Models

Comparison with Differentially Private Prediction

In Section 3.2, we discussed relations between $k$-near access-freeness ($k$-NAF) and ${\varepsilon}$-differential privacy (${\varepsilon}$-DP). We now make a more detailed comparison with a more closely related variant of DP, namely privacy-preserving prediction [Dwork and Feldman, 2018], in which the aim is to protect the privacy of a single individual prediction (i.e., outputs) as opposed to the model itself. The setting is where a user can only access the model through its predictions. Here, a mechanism $\mathcal{T}$ is a randomized mapping that takes as input a dataset $\mathcal{D}$ and a prompt $x\in\mathcal{X}$ and returns a prediction $y\in\mathcal{Y}$. For example, $\mathcal{T}(\mathcal{D})(x)$ may be a procedure that first trains a model $q$ with $\mathcal{D}$ and then samples $y$ from $q(\cdot|x)$. We say $\mathcal{T}$ is ${\varepsilon}$-DP prediction preserving if for every input $x$ and output $y$

The probability in (1) is taken over the randomness used in the mechanism $\mathcal{T}$, with input $\mathcal{D}$ and $x$, e.g. the randomness is both over the training algorithm used to obtain $q$ and any randomness used in sampling $y$ from $q(\cdot|x)$. van der Maaten and Hannun review some DP prediction preserving algorithms, showing that in some cases these do not provide advantages over private training of the entire model.

Three important differences in our definition are: (1) our focus is solely on (conditional) generative models $p(\cdot|x)$, and our probabilities are only taken over the distributions induced by these models, while privacy-preserving prediction is concerned with the mechanism’s distribution, i.e. the distribution of $\mathcal{T}(\mathcal{D})(x)$ as a function of both $\mathcal{D}$ and $x$ (where, say to output a label $y$, $\mathcal{T}$ may require fully retraining on the dataset to learn a deterministic classifier $q(\cdot)$ to use on $x$), (2) our probability comparison is with respect to a given function safe (a choice left to the user) instead of being defined with respect to $\mathcal{T}(\mathcal{D}^{\prime})$, and (3) our definition’s bound is one sided (we only care about an upper bound on the probability of outputting a certain output). In particular, suppose we have an algorithm which, upon input $\mathcal{D}$, returns a model $p$ that is $k$-NAF with respect to some given function safe and for $\Delta=\Delta_{\text{max}}$ (e.g. CP-$\Delta$ and CP-k are such algorithms). This implies:

In Section 1.1 we give a setting where this difference between one sided and two sided is crucial for the feasibility of our algorithms.

Let us observe how we can obtain an ${\varepsilon}$-NAF model using an ${\varepsilon}$-DP prediction preserving mechanism $\mathcal{T}$. Define $p(y|x)$ as the probability that $\mathcal{T}(\mathcal{D})(x)$ outputs $y$, and let us take the safe function to be the leave-one-out-safe function, where $\mathcal{A}$ in Algorithm 1 is chosen to be $\mathcal{T}$ itself. Here, the guarantee in (1) immediately implies that $p$ is ${\varepsilon}$-NAF with respect to leave-one-out-safe and $\Delta=\Delta_{\text{max}}$. Importantly, note that the algorithm $\mathcal{A}$ used in leave-one-out-safe had to be chosen as $\mathcal{T}$ in order for this implication to hold. Conversely, the implication does not necessarily go in the other direction, i.e. a $k$-NAF model does not necessarily imply $O(k)$-differentially private prediction, even if we use the function leave-one-out-safe.

While this difference between (2) and (1) may seem minor at first glance, even here (like for the general notion of differential privacy), obtaining DP prediction preserving mechanisms often needs more sophisticated mechanisms while the condition in (2) is achievable with black box reductions that do not inject additional randomness.

We present here a concrete example where the difference between one sided (NAF) and two sided (DP) definitions manifests. Let $\mu$ be a small constant, suppose there is a generative learning algorithm which when trained on a dataset $D\cup\{y_{1}\}$ yields model $q_{1}$ and when trained on $D\cup\{y_{2}\}$ yields $q_{2}$. Suppose $q_{1}(y_{1})=q_{2}(y_{2})=\mu$ and $q_{1}(y_{2})=q_{2}(y_{1})=\mu^{2}$ and for all other $y$’s we have $q_{1}(y)=q_{2}(y)$. Intuitively, if the model sees the image $y_{i}$ during training then it outputs $y_{i}$ with probability $\mu$ which is $1/\mu$ times more likely than the probability of a model outputting $y_{i}$ which has not seen $y_{i}$. Depending on the setup this may be a clear case of copyright violation. It is also the case that the underlying learning algorithm only satisfies multiplicative DP with ${\varepsilon}=\log(q_{1}(y_{1})/q_{2}(y_{1}))=\log(1/\mu)$ which may be very large. On the other hand the TV distance between the two distributions is only $\approx\mu$ and as CP-$\Delta$ for $\Delta=\Delta_{\text{max}}$ can create a distribution $p$ which only outputs $y_{i}$ with probability $\approx\mu(1+\mu)$ which is only $1+\mu$ times more likely than the probability of a model outputting $y_{i}$ which has not seen $y_{i}$. Note that if our definition was two sided (for $\Delta=\Delta_{max}$) then for all $p$ we have that $\max\{p(y_{1})/q_{2}(y_{1}),q_{1}(y_{1})/p(y_{1})\}\geq 1/\sqrt{\mu}$ which possibly much bigger than $1+\mu$.

Introduction

Generative models for images, text, code, and other domains pose new challenges for ensuring their outputs are protected from copyright infringement. Such models are trained on a large corpus of data, where it is often impractical to ensure the training set is 100% free of copyrighted material. Furthermore, removing copyrighted material from training may also be undesirable. For example, a human author is free to read and use copyrighted material as inspiration for their work, as long as they do not copy it. Similarly, it may be beneficial to use copyrighted material when training in order to have more effective generative models.

Copyright infringement by generative models can potentially arise in (at least) two manners. First, in the training phase, the algorithm could directly access copyrighted material, and the learned model itself could implicitly contain (e.g. coded in its weights) verbatim copies of some of this material. The copyright issues arising during training share many similarities with other settings in which algorithms scrape significant amounts of data, including search-engine indexing and digitizing books. Here, the question of what constitutes a copyright infringement is largely a question of “fair use.” This work does not examine these fair use issues that arise in the training phase, and we refer the reader to the several legal precedents in this area [Samuelson, 2021].

The second notable source of potential infringement is in the deployment phase, where a user provides a prompt $x$ to the model to obtain some output $y$. Apriori, we cannot rule out the possibility that $y$ is either a verbatim copy or substantially similar to some copyrighted training data. Moreover, unlike search engines, generative models do not keep track of the provenance of their outputs. Hence, a user of such an output $y$ (e.g., a software company using generated code, or a designer using a generated image) has no easy way to verify that it does not infringe upon any copyrighted material. It is this issue of preventing deployment-time copyright infringement that is the focus of this work.

We give a formal definition — “near-access freeness” — bounding the extent to which a learned generative model’s output can be substantially influenced by a particular piece of copyrighted data that the model was trained on. We also give a procedure that transforms (under certain assumptions) any generative model learning algorithm $\mathcal{A}$ into an algorithm $\mathcal{A}_{k}$, which protects against violations under our definition. In particular, the model output by $\mathcal{A}_{k}$ will (1) be at most $k$-bits far from a “safe” model (which is not committing copyright infringement), and (2) will have performance reasonably close to the model output by the original algorithm $\mathcal{A}$ (in a quantifiable sense, based on properties of $\mathcal{A}$). Our algorithms have a relatively modest multiplicative overhead in training and inference compared to $\mathcal{A}$ itself.

We also show promising experiments on language and image generative models, demonstrating that our modified model does not degrade significantly in quality (and in fact, it may even improve in some cases). See Figure 1 for one example and Section 5 for more details.

Our definition satisfies a few notable properties:

Demonstrating a copyright infringement consists of showing both access to the copyrighted material and substantial similarity of the output to the material. Our definition separates these two aspects, considering an abstract access function (that can have several different practical realizations) and a quantitative measure of similarity.

Our framework defines similarity on the probability distributions of generative models rather than on particular outputs themselves. This enables using information-theoretic similarity measures, rather than being restricted to superficial notions of similarity such as Hamming or edit distance.

We measure the degree of similarity between our model’s output and some copyrighted data $C$, by comparing the likelihood of our model generating $y$ to that of some safe model, which was trained without access to $C$. This matches copyright law which (unlike patents) allows for accidental or “fortuitous” similarity (see quote above from Feist vs. Rural). In this sense, our definition bears some similarities to differential privacy, though there are significant differences as well; see Section 3.2.

Organization.

Section 3 presents our definition and discusses some motivations and implications; Section 4 provides provably efficient algorithms that modify a baseline training algorithm $\mathcal{A}$ into a version that is protected, under our definition; Section 5 provides a brief experimental validation; and Section 6 and 7 present prior work and our concluding remarks. All proofs not in the main body are deferred to the appendix.

Note / Disclaimer.

Generative models raise many legal and ethical issues. This paper focuses on copyright infringement by the outputs of generative models, which is only one of these issues. The concepts and tools we provide do not address issues related to other forms of intellectual property, including privacy, trademarks, patents, or fair use. Moreover, our work does not (and cannot) guarantee the absence of copyright infringement in all settings. However, we do hope it provides helpful tools and concepts that can be used by model creators and users, lawyers, and courts to reduce the task of determining if some types of infringements have occurred to well-defined, quantitative questions.

Near Access-Free Generative Modeling

Our setting is as follows: we assume there is an algorithm $\mathcal{A}$ which takes as input a dataset $\mathcal{D}=\{z_{1},\ldots z_{N}\}$ and returns a conditional generative model $p(\cdot|\cdot)\in\mathcal{M}$, where $\mathcal{M}$ is the space of conditional generative models. Here, the conditional generative model $p$ can take some prompt $x\in\mathcal{X}$ as input and then outputs $y\in\mathcal{Y}$ with probability $p(y|x)$. We can think of $x\in\mathcal{X}$, $y\in\mathcal{Y}$, and $z\in\mathcal{D}$ as program snippets, sequences of text, images, etc.

Some training samples in our dataset $\mathcal{D}$ may contain copyrighted material. We let $\mathcal{C}$ be the set of copyrighted material contained in $\mathcal{D}$, e.g. $C\in\mathcal{C}$ may be a snippet of code, text, or artwork that is contained in one or more training samples in $\mathcal{D}$. We are concerned that our algorithm may return a model $p$ that samples copyrighted material from $\mathcal{C}$ (or material substantially similar to that in $\mathcal{C}$) with non-trivial probability. That is, for $p=\mathcal{A}(\mathcal{D})$, the concern is that for some prompt $x$ and copyrighted material $C\in\mathcal{C}$, it holds that $y\sim p(\cdot|x)$ will be similar to $C$ with non-trivial probability. Our goal is to devise a procedure where this is not the case.

Under the laws of the U.S. and many other countries, to establish a copyright infringement, a plaintiff must prove that (1) “the defendant had access to the plaintiff’s copyrighted work”, (2) “there are substantial similarities between the defendant’s work and original elements of the plaintiff’s work.”See U.S. Courts for the 9th circuits, Model Civil Jury instructions, Section 17.17 Copying – Access and Substantial Similarity; emphases ours. Even if the access and substantial similarity tests pass, it may still be considered “fair use”, but since the fair use condition is more application-dependent, we do not consider it here, making our definition more conservative. Our definition is modeled around these two components of access and substantial similarity.

Informally, our goal is to provide a model $p$ such that, for any prompt $x$ and copyrighted element $C\in\mathcal{C}$, the distribution $p(\cdot|x)$ is within $k$-bits of information (measured under some divergence measure) to a “safe” generative model, which was trained without access to $C$. We now formalize this notion. We use the abstraction of a function safe that maps a datapoint $C\in\mathcal{C}$ into a generative model $\textsf{safe}(C)\in\mathcal{M}$ that is assumed to have been trained without any access to $C$. (For notational convenience, we sometimes overload notation by denoting $\textsf{safe}(C)$ as $\textsf{safe}_{C}$.) For example, the leave-one-out-safe function, shown in Algorithm 1, is one such example; in this construction, $\mathcal{D}_{-C}$ refers to the dataset where all datapoints that access $C$ have been removed.

Since $\textsf{safe}(C)$ is a generative model that was learned without access to $C$, in many realistic scenarios the probability that $\textsf{safe}_{C}(\cdot|x)$ generates material that is similar to $C$ itself will be exponentially small in the length of $C$ (though see Section 3.2 for when this may not be the case). Moreover, even if this unlikely event happened, this generation can be said to be fortuitous (see the quote from Feist vs. Rural above the abstract).

We now introduce our main criterion for copyright protection, which combines the notion of access, as provided through some prespecified function safe, with the notion of substantial similarity.

Let $\mathcal{C}$ a set of datapoints; let safe$:\mathcal{C}\rightarrow\mathcal{M}$; and let $\Delta$ be a divergence measure between distributions. We say that a generative model $p$ is $k_{x}$-near access-free ($k_{x}$-NAF) on prompt $x\in\mathcal{X}$ with respect to $\mathcal{C}$, safe, and $\Delta$ if for every $C\in\mathcal{C}$,

We say $p$ is $k$-NAF if the above holds for all $x\in\mathcal{X}$ with $k_{x}\leq k$.

When clear from context, we drop the $\mathcal{C}$, safe, and $\Delta$ dependence and simply say $p$ is $k_{x}$-NAF on input $x$.

Definition 1 reduces the task of determining a copyright infringement to (1) a quantitative question of the acceptable value of $k$, and (2) a qualitative question of providing a safe function that appropriately satisfies a no access condition. Both can be application-dependent: the number of bits that constitute copyrightable content differs between, e.g., poems and images, and the safe function could also differ based on application. However, with respect to an acceptable $k$ and a given function safe, a model satisfying Definition 1 provides a rigorous guarantee of no substantive similarity.

[Event bound, max-KL] Suppose model $p$ is $k_{x}$-NAF on prompt $x$ with respect to $\mathcal{C},\textsf{safe},\Delta=\Delta_{\text{max}}$. Then for any $C\in\mathcal{C}$ and any event $\mathcal{E}$,

The proof directly follows from the definition of $\Delta_{\text{max}}$.

By definition, $\Delta_{\text{max}}(p(\cdot|x)\|\textsf{safe}_{C}(\cdot|x))\leq k_{x}$ implies that for every $y$, $p(y|x)\leq 2^{k_{X}}\textsf{safe}_{C}(y|x)$. The result follows from summing over all $y\in\mathcal{E}$. ∎

For some copyrighted text $C\in\mathcal{C}$, let $V_{C}$ be the event that the output is substantially similar to $C$. Lemma 3.1 implies that

As we expect the probability of $V_{C}$ under $\textsf{safe}_{C}(\cdot|x)$ to be exponentially small in the length of the output (since $\textsf{safe}_{C}$ was trained without access to $C$, though see Section 3.2), this would then imply that $p$ itself has a small violation probability.

The relation between the bounds of Lemma 3.1 and Lemma 3.1 is somewhat analogous to the relation between ${\varepsilon}$-differential privacy and $({\varepsilon},\delta)$-differential privacy [Dwork et al., 2014].

2 Further Discussion of the Definition

In many settings, we expect $\textsf{safe}_{C}(V_{C}|x)$ to be small due to $V_{C}$ corresponding to a “monkeys on typewriter” event, whereby a process with no access to $C$ produced a copy of $C$ by accident. However, consider the prompt $x=$ "print the following text:$C$", where the text in $C$ itself has been inserted into the prompt. In such a case, even the “safe” model $\textsf{safe}_{C}$ will output $C$ on $x$ with high probability and so $\textsf{safe}_{C}(V_{C}|x)$ will not be exponentially small. Yet our definition can still be satisfied (and in particular it vacuously holds that $p(V_{C}|x)$ is not much larger than $\textsf{safe}_{C}(V_{c}|X)$). We view this as a reasonable outcome because the behavior of $p$ is similar to that of a procedure which had no access to $C$. Crudely, an analogy would be to copy-paste a copyrighted text into a word processor, which would not be considered a copyright violation due to the word processor software.

We view subtle cases like this as a strength of the framework, as our definition serves as means to quantitatively discuss such questions.

Comparison with Differential Privacy.

At first look, it may seem that near access-freeness (NAF) is equivalent to the well-known notion of differential privacy (DP) [Dwork et al., 2006], with the parameter $k$ playing the role of ${\varepsilon}$. But in fact, there are crucial differences between the two, which we now discuss.

First, the goals of privacy and copyright protection, while related, differ in important ways. Privacy is focused on an individual and the attributes of that individual while copyright protection is only for a specific piece of work. Moreover, copyright only protects the specific expressions of that work, and not the ideas present in it.This is known as the idea/expression dichotomy whereas copyright only protects a particular expression of an idea rather than the idea itself [Samuelson, 2007]. The Copyright Act of 1976 asserts that “In no case does copyright protection for an original work of authorship extend to any idea, procedure, process, system, method of operation, concept, principle, or discovery, regardless of the form in which it is described, explained, illustrated, or embodied in such work” and the legislative history clarifies that “copyright does not preclude others from using the ideas or information revealed by the author’s work.” For example, if the output of a machine-learning procedure leaks a particular piece of information (e.g., medical diagnosis) about an individual, then this is a privacy violation no matter how the information is expressed, while the form of an expression is crucial in the context of copyright. This difference is also translated into quantitative terms: if any particular generative output leaks even a few bits about a training sample, this could still be a significant privacy violation. In contrast, a few bits of leakage are unlikely to constitute a copyright violation since copyright requires a minimum amount of information content.Indeed, the U.S. Copyright Office states [U.S. Copyright Office, 2021] that “Words and short phrases, such as names, titles, and slogans, are uncopyrightable because they contain an insufficient amount of authorship.” More generally, privacy requires that the output of a mechanism does not reveal whether or not an individual’s data was in the database. For copyright protection, we only need to ensure that no particular output is substantially similar to a copyrighted work to which it had access, and it is explicitly allowed for the model to use “ideas or information” revealed by the copyrighted works it was trained on.

Given the above differences, it is not surprising that the algorithms to ensure privacy and copyright protection would differ and also exhibit different performance tradeoffs. This is indeed the case. To elaborate more, we recall the definition of differential privacy. Let $\mathcal{T}$ be a mechanism that maps datasets to generative models. We say that $\mathcal{T}$ is differentially private (DP) if for every datasets $\mathcal{D}$ and $\mathcal{D}^{\prime}$ that differ by at most one point, and every model $p\in\mathcal{M}$ in the support of $\mathcal{T}$,

The probability in (4) is taken over the randomness used in the mechanism $\mathcal{T}$, with input $\mathcal{D}$. The Near-Access-Free condition is not explicitly concerned with the model itself, but only with outputs from the model. For example, a neural model whose weights encode the entire training set would completely violate differential privacy, but, so long as the model never generates particular outputs that are similar to the copyrighted data, it may very well not violate copyright. In that sense, our definition is closer to privacy-preserving prediction [Dwork and Feldman, 2018], which aims to protect the privacy of individual predictions (i.e., outputs) as opposed to protecting the model itself. Even here there are important technical distinctions, which we discuss in Appendix 1.

It is worth noting that these differences have important algorithmic implications. Achieving privacy-preserving mechanisms often requires the use of carefully constructed mechanisms (which inject additional randomness into the models and/or training). In contrast, as our main results show, near-access-freeness is achievable with black-box reductions, requiring only some base learning algorithm $\mathcal{A}$ (and no additional randomness). Also, a series of papers have been exploring the effectiveness of privacy-preserving methods using neural models, which suggest either better features are needed or that more sophisticated approaches are required (e.g. tramer2021differentially, li2021large, ghazi2021deep). Of course differential privacy provides stronger privacy guarantees while near-access-freeness is only designed to protect against copyright infringement.

The safe function in practice.

There can be a number of different ways to define the safe function in practice. The “leave-one-out” example is one, but it requires the training of $|\mathcal{C}|$ different models. We describe a far more efficient implementation in Section 4. In both cases, it is important that when we omit a datapoint $x$ it does not share copyrighted content with many other datapoints that were included in the training set. If we assume that datapoints that share the same copyrighted content are near-duplicates we could achieve this by deduplication. But in general this may not be the case, in such situations we could cluster the dataset by content or by metadata such as authorship so that all works which are close (and hence possibly share copyrighted content) are omitted together. If we can ensure this then we can use our implementations as is. In practice, such processes will be likely approximate, still we think that they should be sufficient for most copyrighted works. For simplicity, we will assume in Sections 4.1 and 4.2 all copyrighted works occur at most one datapoint and we will relax our assumption to $m$ datapoints in Section 4.3. While we will implement safe by partitioning the dataset $\mathcal{D}$ into two (or more, see Section 4.3) parts, there may be other ways to ensure safety. For example, the output of safe might be a model trained “golden dataset” which is much smaller but was carefully scrutinized to ensure that all material in it is not copyrighted or properly licensed. Another way to ensure that a model is safe for $C$ is to train it only on data that was generated before $C$’s creation.

What is 𝒞𝒞\mathcal{C}?

In our discussions, we refer to $C\in\mathcal{C}$ abstractly as a “piece of copyrighted data”, but do not specify it in more detail. For example, in an image generative model, does $C$ correspond to a single artwork, or the full collected arts of some artists? The answer is the former. The reason is that if a generative model generates data that is influenced by the full collected artworks of X, but not by any single piece, then it is not considered a copyright violation. This is due to that it is not possible to copyright style or ideas, only a specific expression. Hence, we think of $C$ as a piece of content that is of a similar scale to the outputs of the model.

Comparison with law.

As discussed earlier to show a copyright violation has occurred the plaintiff must prove that“there are substantial similarities between the defendant’s work and original elements of the plaintiff’s work” (assuming access). It’s negation would be to show that defendant’s work is not substantially similar to the original elements of the plaintiff’s work. Our approach would instead correspond to showing that the defendant’s work is close to a work which was produced without access to the plaintiff’s work. While we think this is a stronger guarantee, to what extent the courts (or lawmakers / regulators) will embrace it is an open question.

Other choices for divergence measure.

The divergence measure $\Delta$ need not be Max-KL or KL. Other choices include the following:

It is possible to combine the two aspects above, and define $\Delta(\rho\|\mu)$ as the minimum of $\Delta_{\text{max}}(\rho^{\prime}\|\mu)$ over all $\rho^{\prime}$ that are of at most some earthmover distance $D$ to $\rho$. This can combine the advantages of both metrics. Of course, the acceptable value for $D$ would be application dependent.

If the models generate very long sequences of information (e.g., several pages of text, or a full program), then it may be appropriate to consider definitions that look at subsequences of the reference and safe model. For example, it may be appropriate for 10 pages of a generated output to include 100 words from some copyrighted data, as long these are “spread out” and not part of (say) a 200-word subsequence.

The right choice of the metric will be context dependent. While $\Delta_{\text{max}}$ is very stringent and gives a hard bound in terms of entropy on the amount of non-accidental copying, it might be too stringent in some applications, ruling out models that are arguably still safe.

Algorithms for Copyright Protection

We now show there exist algorithms for learning a conditional generative model $p$ that can satisfy the $k$-NAF condition, for reasonable choices of $k$. For the intuition of our construction, note that for large datasets we may expect that $\textsf{leave-one-out-safe}(C)\approx\textsf{leave-one-out-safe}(C^{\prime})$, for all $C,C^{\prime}\in\mathcal{C}$. The algorithmic challenge would then be to find a model $p$ which agrees, under $\Delta$, with $\textsf{leave-one-out-safe}(C)$ for all choices of $C$, and, thus, the model $p$ itself should be close to a model that has been trained without access to any $C\in\mathcal{C}$. This may be computationally difficult because $\textsf{leave-one-out-safe}(C)$ is one of $|\mathcal{C}|$ different models.

Now let us see how to make this approach more tractable. For simplicity, in Section 4.1, we assume that each copyrighted piece of data $C$ appears in at most a single datapoint in the dataset. While in some settings this can be achieved via deduplication, our constructions extend naturally to the case that each copyrighted work appears in no more than $m>1$ points (see Section 4.3). Proceeding under this assumption, we use the function sharded-safe (see Algorithm 2). Given a dataset of $N$ points, sharded-safe trains two models, each on $N/2$ disjoint points. In contrast to leave-one-out-safe, we have that, for all $C\in\mathcal{C}$, $\textsf{sharded-safe}(C)$ is only one of two models, either $q_{1}$ or $q_{2}$, corresponding to the model which was not trained on $C$. Our algorithmic challenge is now to find a $p$ which approximately but simultaneously agrees, under $\Delta$, with both $q_{1}$ and $q_{2}$.

Section 4.1 starts by providing algorithms which satisfy the $k$-NAF property for both the $\Delta_{\text{max}}$ and $\Delta_{\text{KL}}$ divergences with respect to the sharded-safe function. In both cases, the quantity $k$ will be controlled by a distance between the distributions $q_{1}$ and $q_{2}$; the relevant distance will be the total variation distance when $\Delta=\Delta_{\text{max}}$ and the squared Hellinger distance when $\Delta=\Delta_{\text{KL}}$. Also, in both cases, we only need the distributions to have very mild overlap (i.e., distance slightly bounded away from $1$) to ensure a meaningful bound on $k$. Section 4.2 then considers a more practical, black box approach to achieving copyright protection. Section 4.3 extends our sharded-safe construction so that it is applicable if each $C\in\mathcal{C}$ possibly appears in up to some $m>1$ points in $\mathcal{D}$.

This section assumes each copyrighted piece of data $C$ appears in at most a single datapoint in the dataset. The CP-$\Delta$ Algorithm is presented in Algorithm 3. Here, $\Delta$ is chosen to be either the $\Delta_{\text{max}}$ or $\Delta_{\text{KL}}$ divergences. Recall that the total variation distance between distributions $p$ and $q$ is defined as $\mathsf{TV}(p,q)=\tfrac{1}{2}\sum_{y}|p(y)-q(y)|$ and the Hellinger squared distance is defined as $\mathsf{H}^{2}(p,q)=1-\sum_{y}\sqrt{p(y)q(y)}$.

[CP-$\Delta$ ] Let $p$ be the model returned by CP-$\Delta$, and $q_{1}$ and $q_{2}$ be the models returned by sharded-safe. We have that $p$ is $k_{x}$-NAF with respect to $\mathcal{C}$, sharded-safe, and $\Delta$, whereThe factor of $2$ in the case of $\Delta=\Delta_{\text{KL}}$ is not inherent, and can be eliminated in several cases. Whenever that is the case, the bound on $k_{x}$ is better since for every two distributions, the squared Hellinger distance is upper bounded by the total variation distance.

By Lemma 3.1, for the case of $\Delta_{\text{max}}$, we have that for all $C\in\mathcal{C}$ and events $\mathcal{E}$,

In other words, provided $q_{1}$ and $q_{2}$ have total variation distance only non-trivially bounded away from $1$ and if the probability of a fortuitous copy is small, then $p$ will also copy with only a small probability.

Before providing the proof, let us provide an illustrative example, which also shows our bound is tight. See Figure 2 for another example.

Consider the promptless case (i.e. $\mathcal{X}=\emptyset$), where there are two (distinct) copyright elements, $\mathcal{C}=\{C_{1},C_{2}\}$, appearing only once each in our dataset $\mathcal{D}$; $\mathcal{D}$ may contain other training datapoints. Let $\mathcal{D}_{1}$ and $\mathcal{D}_{2}$ be the dataset split, where $\mathcal{D}_{i}$ contains $C_{i}$ for $i\in\{1,2\}$ (and $\mathcal{D}_{i}$ does not contain $\mathcal{C}_{-i}$). Let $q_{i}=\mathcal{A}(\mathcal{D}_{i})$ be the model returned by our algorithm on $\mathcal{D}_{i}$. Suppose that $q_{i}(y)=0.5\cdot I(y=C_{i})+0.5\cdot q(y)$, where we interpret $q$ to be the common part learned by both $\mathcal{A}(\mathcal{D}_{1})$ and $\mathcal{A}(\mathcal{D}_{2})$. As such, we expect $q(\mathcal{C})$ to be extremely small, and for simplicity, we assume $q(C_{1})=q(C_{2})=0$. Each of the models $q_{1},q_{2}$ outputs a copyrighted text with probability $1/2$, and yet one can verify that both the distribution proportional to $\min\{q_{1},q_{2}\}$ and the one proportional to $\sqrt{q_{1}q_{2}}$ will simply be $q$. Hence, the output model of CP-$\Delta$ will never output $C_{1},C_{2}$. For every $y$ in the support of $q$ and for $i\in\{1,2\}$, $q(y)/q_{i}(y)=2$ and so $\Delta_{\text{max}}(q(\cdot),q_{i}(\cdot))=\Delta_{\text{KL}}(q(\cdot),q_{i}(\cdot))=\log 2$. On the other hand, it is easy to see that $\mathsf{TV}(q_{1},q_{2})=\mathsf{H}^{2}(q_{1},q_{2})=1/2$. Hence, the bound $\Delta_{\text{max}}(q,p_{i})\leq-\log(1-\mathsf{TV}(q_{1},q_{2}))$ is tight and the bound $\Delta_{\text{KL}}(q,p_{i})\leq-2\log(1-\mathsf{H}^{2}(q_{1},q_{2}))$ is loose by a factor of two. A more general case of how both algorithms apply to two “spiked” distributions is illustrated in Figure 2.

We start by relating $k_{x}$, in each case, to the corresponding partition function $Z(x)$. First, for $\Delta=\Delta_{\text{max}}$, observe that, by construction, $p(y|x)\leq q_{i}(y|x)/Z(x)$ for all $y\in\mathcal{Y}$, $i\in\{1,2\}$. Hence, $\log(p(y|x)/q_{i}(y|x))\leq\log(1/Z(x))$, and this directly implies that $p$ is $\log(1/Z(x))$-NAF. For $\Delta=\Delta_{\text{KL}}$, we have that:

where the last step follows by the definition of $Z(x)$.

The proof is then completed with the following bound on the partition function $Z(x)$ of Algorithm 3:

In Algorithm 3 with $\Delta=\Delta_{\text{max}}$ we have $p(y|x)=\frac{m(y)}{Z(x)}$ where $m(y)=\min\{q_{1}(y|x),q_{2}(y|x)\}$. Hence, $Z(x)=\sum_{y}m(y)$. For every $y$, $|q_{1}(y|x)-q_{2}(y|x)|=(q_{1}(y|x)-m(y))+(q_{2}(y|x)-m(y))$, since depending on whether $q_{1}(y|x)>q_{2}(y|x)$ or vice versa, one of the terms is $|q_{1}(y|x)-q_{2}(y|x)|$ and the other is zero. Hence,

In Algorithm 3 with $\Delta=\Delta_{\text{KL}}$ we have $p(y|x)=\frac{\sqrt{q_{1}(y|x)q_{2}(y|x)}}{Z(z)}$. So

where the last equality follows from the definition of $\mathsf{H}^{2}$. ∎

For $\Delta=\Delta_{\text{max}}$, the proof of this lemma follows from a standard probability mass argument using properties of the total variation distance, and, for the $\Delta_{\text{KL}}$ case, the lemma directly follows from the definition of the Hellinger distance. See the Appendix 4.1.

Bounded degradation.

Our goal is to not only prevent copyright infringement but, importantly, to also maintain high-quality generative models when $\mathcal{A}(\mathcal{D})$ itself is a high-quality model. The following lemma formalizes this, showing that CP-$\Delta$ does not substantially degrade the quality of the model (in comparison to a model trained on half the data).

[Bounded Degradation] Let $p$ be the model returned by CP-$\Delta$, and $q_{1}$ and $q_{2}$ be the models returned by sharded-safe. For $i\in\{1,2\}$ and for $\Delta=\Delta_{\text{max}}$,

and for $i\in\{1,2\}$ and for $\Delta=\Delta_{\text{KL}}$,

For $\Delta=\Delta_{\text{max}}$ by Lemma 4.1 we have that p(y|x)=\frac{\min\{q_{1}(y|x),q_{2}(y|x)\}}{1-\mathsf{TV}\bigl{(}q_{1}(\cdot|x),q_{2}(\cdot|x)\bigr{)}} . Hence,

where the second last inequality follows from the fact that for $a\geq 0,b\geq 0$ we have $|a-b|\leq\max\{a,b\}$.

Using arguments similar to those used in the proof of Lemma 4.1 it is easy to see that

A symmetric statement holds for \mathsf{TV}\bigl{(}p(\cdot|x),q_{2}(\cdot|x)\bigr{)} implying that for $i\in\{1,2\}$ and for $\Delta=\Delta_{\text{max}}$,

For $\Delta=\Delta_{\text{KL}}$ we have that $k_{x}=\max_{i\in\{1,2\}}\mathsf{KL}(p(\cdot|x),q_{i}(\cdot|x))$ and by Theorem 4.1 we have that k_{x}\leq-2\log\left(1-\mathsf{H}^{2}\bigl{(}q_{1}(\cdot|x)\,,\,q_{2}(\cdot|x)\bigr{)}\,\right). Hence,

In particular, if $q_{1}$ and $q_{2}$ are ${\varepsilon}$ close to each other in total variation then $p$ will be ${\varepsilon}$ close to both $q_{1}$ and $q_{2}$ in total variation. Thus $p$ is not much worse in quality in comparison to $q_{1}$ and $q_{2}$. (Our experiments actually show $p$ can even be higher quality, possibly due to CP-$\Delta$ having a model averaging effect). The benefit now is that $p$ itself will (essentially) no longer sample copyrighted material (i.e. it does so only $1/(1-{\varepsilon})\approx 1+{\varepsilon}$ times more than the safe model). As an illustrative case, suppose $q_{1},q_{2}$ are $0.01$ close to each other in total variation, but this $1\%$ difference corresponds to a chance that each model $q_{i}$ outputs, verbatim, some copyrighted material that is not accessed (in training) by the other model. Hence, we expect the probability under $q_{2}$ of outputting copyrighted material output by $q_{1}$ to be exponentially small, and vice versa. Our algorithm transforms these models into a new model $p$, which is $\approx.01$ close to either of the original models in total variation, but $p$ now outputs copyrighted material with an exponentially small probability. While a $1\%$ performance degradation may be tolerable in many settings, outputting copyrighted material $1\%$ of the time is very likely not acceptable (e.g. due to resulting liabilities).

2 Black-Box Oracle Algorithms

There are a number of modifications worth considering for practical deployments. First, implementing CP-$\Delta$ may be computationally difficult in practice, e.g. if $q_{1}$ and $q_{2}$ are neural models for text sequences or image generation. Second, as CP-$\Delta$ is parameter free, it may be worthwhile to introduce a parameter based version for greater protection. Finally, it may be desirable to use a reduction based approach, where we can more directly modify any model $p$ to make it access-free, e.g. we may want to directly utilize a model $p=\mathcal{A}(\mathcal{D})$ that was trained on all of the data.

Let us say $\mathcal{V}=\{q_{1},\ldots q_{n}\}$ is a cover of the function safe if for all $C\in\mathcal{C}$, there exists some $q\in\mathcal{V}$ such that $\textsf{safe}(C)=q$. Section 4.3 provides a construction for a safe function leading to a cover whose size is greater than $2$, for the $m>1$ case. The CP-k Algorithm, presented in Algorithm 4, takes as input any model $p$, a cover $\mathcal{V}$, and a threshold $k$ and returns a model $p_{k}$, which has quantifiable access-free guarantees with respect to safe. CP-k assumes access to an oracle where we can both compute conditional probabilities and obtain samples under the models $p$ and $q\in\mathcal{V}$.

The intuition of CP-k is as follows: we first sample $y\sim p(\cdot|x)$ and only accept this output if it satisfies a desired upper bound with regards to the function safe, the latter of which can be efficiently checked using the cover $\mathcal{V}$ of safe. One potentially undesirable property of this algorithm is that it is discontinuous: an output with probability slightly above the acceptance threshold in (6) will be rejected. The smooth-CP-k Algorithm, presented in Algorithm 5, provides a modification where the acceptance probability is a continuous function of $p(\cdot|x)$ (leading to a slightly improved efficiency bound in Theorem 4.2).

Let $\nu_{k}(x)$ be the probability that $y$ is accepted on input $x$ in any iteration of the while statement in CP-k or smooth-CP-k (the attempts are i.i.d.). The guarantee for both algorithms are as follows:

[Guarantees for CP-k and smooth-CP-k ] Let $p_{k}$ be the model returned by either CP-k or smooth-CP-k when input with a model $p$; a cover $\mathcal{V}$ for safe, and a threshold $k\geq 0$. Let $\nu_{k}(x)$ be the probability that the sampled $y$ is accepted in a single iteration of the while loop. We have that:

(Near Access-Freeness) $p_{k}$ is $\widetilde{k}_{x}$-NAF on prompt $x$ with respect to safe and $\Delta=\Delta_{\text{max}}$, where:

(Model Degradation) $p_{k}$ satisfies the following bound:

(Oracle Complexity) Sampling $y\sim p_{k}(\cdot|x)$ requires $O(1/\nu_{k}(x))$ iterations, where each iteration involves obtaining one sample from $p$ and doing $|\mathcal{V}|+1$ probability computations from either $p$ or $q\in\mathcal{V}$.

We start with bounding $\widetilde{k}_{x}$. For CP-k $y$ is sampled in a single iteration of the while loop if $p(y|x)\leq\min_{q\in\mathcal{V}}2^{k}q(y|x))$. Hence, the probability of sampling $y$ in a single iteration of while statement is $\leq\min_{q\in\mathcal{V}}2^{k}q(y|x))$. For smooth-CP-k the probability of sampling $y$ in a single iteration of while statement is $\leq\min\{p(y|x),\min_{q\in\mathcal{V}}2^{k}q(y|x))\}\leq\min_{q\in\mathcal{V}}2^{k}q(y|x))$. Hence, for both CP-k and smooth-CP-k the probability of sampling $y$ in a single iteration of while statement is $\leq\min_{q\in\mathcal{V}}2^{k}q(y|x))$.

This implies that the overall probability of sampling $y$ i.e $p_{k}(y|x)$ is $\leq\min_{q\in\mathcal{V}}2^{k}q(y|x))/\nu_{k}(x)$. By definition of NAF we have that $p_{k}$ is $\widetilde{k}$-NAF where $\widetilde{k}=\max_{y,q\in\mathcal{V}}\log(p(y|x)/q(y|x))$. Using $p_{k}(y|x)\leq\min_{q\in\mathcal{V}}2^{k}q(y|x))/\nu_{k}(x)$ we get that $\widetilde{k}\leq\log(2^{k}/\nu_{k}(x))=k+\log(1/\nu_{k}(x))$.

We now move to bounding model degradation. For CP-k, since $p_{k}(\cdot|x)$ is just renormalized $p(\cdot|x)$ on a subset with mass $\nu_{k}(x)$ we have that

For smooth-CP-k, let $w_{x}(y)=\min\{p(y|x),2^{k}\min_{i}(q_{i}(y|x))\}$. Note that $p_{k}(y|x)=w_{x}(y)/\nu_{k}(x)$ and $\sum_{y}w_{x}(y)=\nu_{k}(x)$. We have that,

Because $k$ appears on the right-hand side of (6), the higher we set the parameter $k$, the higher the probability $\nu_{k}(x)$ that $y$ is accepted. Hence, making $\widetilde{k}_{x}$ acceptably small involves balancing the two components. One heuristic would be to choose $k$ as the median of the left-hand side of (6), which would ensure that $\nu_{k}(x)=1/2$, hence loosing only an additive factor of $1$ in the bound on $\widetilde{k}_{x}$; here, $p_{k}$ could then substantially provide different samples in comparison to $p$. Using a percentile instead of the median is a natural way to tune this tradeoff.

As before, by Lemma 3.1, for the case of $\Delta_{\text{max}}$, we have that for all $C\in\mathcal{C}$ and events $\mathcal{E}$,

Now let us understand the efficiency of this approach and also consider a few natural choices for $p$, e.g. choosing $p=q_{1}$ itself or choosing $p=\mathcal{A}(\mathcal{D})$, the model trained with all the data.

As shown in Theorem 4, the quantity $\nu_{k}(x)$ is critical because it governs $\widetilde{k}_{x}$, the model degradation, and the oracle complexity. We now characterize $\nu_{k}(x)$ based on a particular “distance” measure between $p$ and the set $\mathcal{V}$. In the extreme case, where $p(\cdot|x)$ and all $q(\cdot|x)\in\mathcal{V}$ are equal to each other, then $p_{k}=p$ and the sampling succeeds at every attempt, i.e. $\nu_{k}(x)=1$. Let us now quantify the impact of when these distributions are not all equal to each other. Define:

where $|\cdot|_{+}$ is the function which thresholds negative inputs to . It is straightforward to observe that $0\leq d_{x}(p,\mathcal{V})\leq 1$. For an interpretable upper bound on $d_{x}(p,\mathcal{V})$, we have that:

which shows that $d_{x}(p,\mathcal{V})$ will be small if $p$ and all $q\in\mathcal{V}$ are close to each other.

The following theorem presents our characterization of the efficiency of CP-k and smooth-CP-k, through bounding $\nu_{k}(x)$.

[Bounds on $\nu_{k}(x)$] Fix a model $p$, a function safe, and a prompt $x$. Let $\mathcal{V}=\{q_{1},\ldots q_{n}\}$ be a cover for safe. Let $d=d_{x}(p,\mathcal{V})$ and assume $d<1$. Let $p_{k}$ be the model returned by either CP-k or smooth-CP-k with input $p$, $\mathcal{V}$, and a threshold $k$. We have that:

For CP-k and provided k\geq\log\big{(}2/(1-d)\big{)}, the acceptance probability is bounded as:

For smooth-CP-k and for $k\geq 0$, the acceptance probability is bounded as:

Let $\mathcal{E}_{x}$ be the event that a sample $y$ is rejected and $m_{x}(y)=\min\{q_{1}(y|x),\ldots q_{n}(y|x)\}$. For CP-k, as sample $y$ is rejected i.e. $y\in\mathcal{E}_{x}$ if and only if:

and so, summing over $y\in\mathcal{E}_{x}$, leads to:

and our setting of k=\log\big{(}2/(1-d)\big{)} gives:

which is our claimed bound on $\nu_{k}(x)$.

For smooth-CP-k a sample $y$ is rejected only if $p(y|x)>2^{k}m_{x}(y)$ and in that case it is rejected with probability $p(y|x)-p(y|x)\cdot\frac{2^{k}m_{x}(y)}{p(y|x)}=p(y|x)-2^{k}m_{x}(y)$. Hence we have:

and using $\widetilde{k}_{x}=k+\log(1/\nu_{k}(x))$ leads to the claimed bound on $\widetilde{k}_{x}$. ∎

A few points are in order. First, to better understand the restriction $d<1$, it is not difficult to construct a case where $d=1$ and where the acceptance probability $\nu_{k}(x)$ is . For example, consider a case where $|\mathcal{V}|=2$ and, for all $y\in\mathcal{Y}$, $\min\{q_{1}(y|x),q_{2}(y|x)\}=0$. Furthermore, in such a case, there exists no distribution $p$ which is $k$-NAF (for finite $k$) with respect to this safe function. Second, while the above bound on $\nu_{k}(x)$ is not shown to be increasing in $k$, we expect this to happen in practice (see (7) in the Appendix 4.2 for a sharp expression for $\nu_{k}(x)$, which does increase with $k$).

Let us consider the special case where our cover has two elements, i.e. $\mathcal{V}=\{q_{1},q_{2}\}$, as would be the case if we used sharded-safe, and where we choose $p=q_{1}$. In such a case, the following corollary shows that smooth-CP-k is as effective as CP-$\Delta$, for $\Delta=\Delta_{\text{max}}$ (and CP-k looses a constant additive factor in $\widetilde{k}_{x}$).

Suppose $\mathcal{V}=\{q_{1},q_{2}\}$ is a cover of safe (e.g. if sharded-safe is used). Let $p=q_{1}$. We have:

Therefore, the claims in Theorem 4.2 hold with d=\mathsf{TV}\bigl{(}q_{1}(\cdot|x),q_{2}(\cdot|x)\bigr{)}. This implies that, for $k=0$ and for smooth-CP-k, we recover the guarantees of CP-$\Delta$ with $\Delta=\Delta_{\text{max}}$. Furthermore, in this case, we have that $p_{k}$ is equal to the distribution $\min\{q_{1}(y|x),q_{2}(y|x)\}/Z(x)$ itself.

Substituting $k=0$ and d=\mathsf{TV}\bigl{(}q_{1}(\cdot|x),q_{2}(\cdot|x)\bigr{)} in the guarantees of smooth-CP-k from Theorem 4, 4.2 we get that,

which are exactly the guarantees we obtained from CP-$\Delta$ for $\Delta=\Delta_{\text{max}}$. This is not a coincidence since we now show that in this case $p_{k}(y|x)=\min\{q_{1}(y|x),q_{2}(y|x)\}/Z(x)$. For $k=0$ the probability of sampling $y$ in a single iteration of while loop in smooth-CP-k is

Normalizing this gives us that $p_{k}(y|x)=\min\{q_{1}(y|x),q_{2}(y|x)\}/Z(x)$.

Provided $d$ is non-trivially bounded away from $1$, say $d=1-\delta$, we expect this to be a strong guarantee on the violation probability (as per the discussion in Section 3.1), though now $\nu_{k}(x)$ may be as small as $\delta$, making the sampling costly for very small $\delta$. However, for moderately small values of $\delta$, both algorithms will be efficient to implement.

3 Handling Multiple Accessing Datapoints: The m>1𝑚1m>1 Case.

Recall that $m$ denotes the number of datapoints that can access a single copyrighted data $C$. When $m>1$, it may be the case that a datapoint $z\in\mathcal{D}$ has copyrighted more than one work in $\mathcal{C}$ (e.g. some training datapoint substantially contains material from two copyrighted works), so simply deduplicating $\mathcal{D}$ may not result in a dataset with $m=1$. Hence, an algorithm for $m>1$ may be desired. The more general sharded-safe Algorithm is presented in Algorithm 6. The algorithm sharded-safe first partitions $\mathcal{D}$ into disjoint shards $\mathcal{D}_{1},\ldots\mathcal{D}_{m+1}$. By the pigeonhole principle, this ensures that each copyrighted work does not appear in at least one dataset $\mathcal{D}_{i}$. Of course, depending on the dataset, it may be possible to use less than $m+1$ partitions, even for the $m>1$ case.

The guarantees for CP-k Algorithm already extend to using sharded-safe; for example by taking $p=\mathcal{A}(\mathcal{D})$, we then have a black box procedure for copyright protection using only the algorithm $\mathcal{A}$. Even though CP-k is a natural algorithm to use, it may still be conceptually worthwhile to modify the CP-$\Delta$ algorithm to handle the $m>1$ case Here, we see show how a certain log partition function governs $k_{x}$. For $\Delta=\Delta_{\text{max}}$, CP-$\Delta$ can be modified to return:

and, for $\Delta=\Delta_{\text{KL}}$, CP-$\Delta$ can be modified to return:

This algorithm enjoys the following guarantee:

[CP-$\Delta$, $m>1$] Let $p$ be the model defined above. We have that $p$ is $\widetilde{k}_{x}$-NAF with respect to sharded-safe, where $\widetilde{k}_{x}\leq-\log Z(x)$ if $\Delta=\Delta_{\text{max}}$ and $\widetilde{k}_{x}\leq-(m+1)\log Z(x)$ if $\Delta=\Delta_{\text{KL}}$.

First, for $\Delta=\Delta_{\text{max}}$, observe that, by construction, $p(y|x)\leq q_{i}(y|x)/Z(x)$ for all $y\in\mathcal{Y}$, $i\in\{1,\dots,m+1\}$. Hence, $k_{x}=\max_{i,y}\log(p(y|x)/q_{i}(y|x))\leq\log(1/Z(x))=-\log Z(x)$.

For $\Delta=\Delta_{\text{KL}}$, we have that

The proof is analogous to the $m=1$ case and is provided in the Appendix 4.2.

Experiments

We now provide experimental validation for both language and image generative models. While there is significant room for the optimization of this approach and for the use of large datasets, this is not our focus. Instead, our experiments are for validation and demonstrating that our algorithms lead to minimal performance degradation while providing rigorous bounds on the distance from the access-free models. Qualitatively, we also observe that applying our algorithm can transform models, each of which has significant chance of outputting some fixed memorized element, into a combined model where this probability is greatly reduced. These experiments should be considered as proof of concept, meant to highlight that the approach is both viable and simple to implement. There are several natural modifications for reducing the quantitative bounds on $k_{x}$ as well as improving performance, which we leave to future work. All our experiments use the sharded-safe function (Algorithm 2). That is, we split the dataset $\mathcal{D}$ into two disjoint parts $\mathcal{D}_{1}$ and $\mathcal{D}_{2}$, and train two separate models $q_{1},q_{2}$ on those.

Our theoretical results (Theorem 4.2) show that the bound on $\widetilde{k}$ depends on how close the underlying models $q_{1},q_{2}$ and $p$ are. To encourage model similarity during finite-sample training, we use the same values of noise in the diffusion process (while training) for all the models (ensured by using the same random seed in training $q_{1},q_{2}$ and $p$); this does not invalidate the access-free property of the safe models because the noise sequence is chosen independently of the training images. Figure 1 displays the model generations, for $p,q_{1},q_{2}$, using the same noise sequence on the diffusion paths for the corresponding images. Here, we can see that these models produce similar (but not identical) images when given the same noise sequence. The rightmost figure, which shows samples from $p_{k}$, is exactly the same images as leftmost figure, which are samples from $p$, except when the image fails to meet the threshold criteria, in which case the image was continually re-sampled until the threshold criteria is met.

The data-processing inequality and interpreting k~~𝑘\widetilde{k}:

The value of $\widetilde{k}\approx 500$ may look pessimistic at first glance. A few points are in order here. First, our guarantees (Theorems 4,4.2) apply to the whole sequence $y$ rather than just to $x_{0}$, where our guarantees are on events defined on the sequences $(x_{T},x_{T-1},\ldots,x_{0})$ themselves. Ultimately, we are only interested in the marginal probabilities of the images $x_{0}$, and, by the data-processing inequality, our bounds also hold directly on $x_{0}$. In particular, for any image $x_{0}$ generated by $p_{k}$, we have $p_{k}(x_{0})\leq 2^{501}\cdot\textsf{safe}_{x_{0}}(x_{0})$. Part of the reason for a large value of $k$ may be due to our inability to directly run our algorithm on the marginal probabilities of the images. This is due to the difficulty in directly computing marginal likelihoods with diffusion modelsSuch an issue does not arise for language models since the whole path serves as the output i.e. there is no need for appealing to the data-processing inequality. It also would not arise for flow based (invertible) generative models, which requires summing over different paths $y$ which end in $x_{0}$.

Finally, it is sometimes the case that theoretically grounded methods work better in practice then their bounds suggest. However, that we plausibly obtain non-vacuous bounds even when running our algorithms on the full sequence along the diffusion path is encouraging.

2 A Language Model Experiment

We use the C4 dataset c4dataset and train decoder-only transformers similar to GPT models (specifically mosaic-llm) on two disjoint partsThe amount of data used to train each $q_{i}$ follows the default values in mosaic-llm, which uses the Chinchilla (chinchilla) compute-optimal values. in to obtain models $q_{1},q_{2}$. We then transform $q_{1},q_{2}$ to a model $p$ using the CP-$\Delta$ algorithm for both $\Delta=\Delta_{\text{max}}$ and $\Delta=\Delta_{\text{KL}}$. Our motivation is to understand how the CP-$\Delta$ algorithm, used as is (on a token level), fares in terms of $k_{x}$ and the model degradation. As shown in Table 1 (top), the resulting models have somewhat improved cross-entropy loss compared to each one of the original models. For $\Delta=\Delta_{\text{KL}}$, this is perhaps expected since CP-$\Delta$ corresponds to a model averaging algorithm in logit space.

We also investigate the effectiveness of CP-$\Delta$ by looking at the implied $k_{x}$ at the token level. Here, we look at the expected value of $k_{x}$, where $x$ is a random prefix of the training data. We show that the expected value of $k_{x}$ is significantly smaller than the total entropy of the tokens (see Table 1 (bottom).Theorem 4.1 uses the bound k_{x}\leq\sum_{i=1}^{2}\Delta_{\text{KL}}\big{(}p(\cdot|x)\,\|\,q_{i}(\cdot|x)\big{)} in the case $\Delta=\Delta_{\text{KL}}$. Instead of using that we explicitly report in Table 1 (bottom) the expectation of the true quantity k_{x}=\max_{i\in\{1,2\}}(\Delta_{\text{KL}}\big{(}p(\cdot|x)\,\|\,q_{i}(\cdot|x)\big{)}).). Interestingly, even the relative bounds on the expect value of $k_{x}$, compared to the total entropy, improve as the model scales up, though this should be investigated for larger models.

Related works

There have been several studies of copyright issues in machine learning and data mining in the law literature, though most of them focus on potential infringements in the training phase. sag2018new surveys the question of whether data mining and machine learning on copyrighted text falls under “fair use” and states that “allowing [text data mining] and other similar non-expressive uses of copyrighted works without authorization is entirely consistent with the fundamental structure of copyright law.”. sag2018new also states that under U.S. law “extracting a short phrase or snippet of text from one work and using it in another does not amount to a reproduction of the work if the localized similarity is not substantial, is not quantitatively or qualitatively significant, or is otherwise de minimis.” (However, European courts have a stricter threshold for the amount of similarity.) sobel2018artificial also discusses the issue of “fair use” in training. While he mentions the issue of output generation, the article does not focus on it since (at the time) “works generated by Al are fascinating and entertaining, but today they remain novelties rather than mainstream sources of entertainment or compelling substitutes for human expression.” gillotte2020copyright studies copyright infringement in AI-generated artworks and concludes that regarding the training phase “an engineer may use copyrighted works to train an Al program to generate artwork without incurring infringement liability.” hristov2016artificial considers a separate issue regarding AI and copyright: whether it should be possible to grant copyright to AI-authored works. Current rulings (copyright-office-ai) by the U.S. copyright review board state that wholly AI generated works cannot be considered for copyright.

Memorization of training samples is considered undesirable for many reasons apart from copyright. LeeINZECC22 show that deduplication can significantly reduce memorization, but not eliminate it (see also bottom row of Table 1 in [KandpalWR22]). IppolitoTNZJLACC22 state that “deduplication does not guarantee that a model will not still memorize individual (deduplicated) examples, necessitating defenses that operate at inference-time”. They also show that simply stopping models from outputting training samples verbatim does not prevent memorization and can give a “false sense of security.” [LeeLCL22, TirumalaMZA22, CarliniIJLTZ22] show that memorization becomes worse with model size and data reuse. The deterioration with growing model size holds even in the single-epoch (no data reuse) case; see in particular Figures 1 and 8 in [TirumalaMZA22].

As discussed in Section 3.2, our work is related to, but also substantially different than, differential privacy [DworkMNS06]. Elkin-Koren study the differences between copyright and privacy anf find that “if privacy is adopted as standard for copyright infringement, it may undermine copyright law intended purposes”. PonomarevaBV22 train a small (60m parameters) differentially private language model, while li2021large fine-tune large models in a differentially private fashion. We discuss additional relevant works on differential privacy in Appendix 1. carlini2021extracting show a reconstruction attack of training data from model weights for GPT-2, while very recently carlini2023extracting gave training-points reconstruction attacks for diffusion models. We note that while a reconstruction attack has strong privacy implications, it does not prevent copyright protection for the generated outputs.

The work of scheffler2022 is closely related to our work. While the goals are different (they analyze prior cases, while we want to build tools to prevent future infringement), the two works are similar on a technical level. Specifically, our Definition 1 of $k$-NAF can be interpreted in their framework since $\log(1/\Pr[y])$ for a generative model corresponds to the description length of the randomness used to generate $y$. Plugging this in we get that our parameter $k$ in near access-freeness corresponds to their notion of empirical derivation similarity. Our setup is more directly applicable to generative models due to its probabilistic nature. This is what allows us to give transformations in Section 3 which can ensure $k$-NAF.

Discussion

This work provided a precise definition for quantifying the extent in which a generative-model copies protected material. As discussed, applying our definition in practice requires making application-specific choices on the admissible bound $k$, the information measure $\Delta$, and ensuring that $\textsf{safe}(C)$ truly maps to a model that did not access $C$. However, by making these choices explicit, we hope this can advance the current state of using, at best, heuristic protections against memorizing inputs. We also hope that this work can help to form a basis for discussions between content creators, model designers, model users, and legal scholars about the appropriate choices.

Our work puts into stark relief the difference between the issues of privacy, memorization, trademarks, patents, fair use, and copyright, showing that solution concepts for the latter goal need not address the former goals. Indeed, our algorithms use the underlying models as black-boxes, and so our resulting model may include a full description of the underlying training data it is based on. In particular, our approach makes no attempt to prevent reconstruction of the training-set from the model description, as that is unnecessary for investigating inference-time copyright infringement. Neither do our algorithms attempt to address trademark; it may be possible to prompt an LLM go generate material that would be considered an infringement of trademark.

Our algorithms are practical, but we believe there is more room for optimizations in both training and inference.

Acknowledgements and Funding

We thank the reviewers for their insightful comments.

This work has been made possible in part by a gift from the Chan Zuckerberg Initiative Foundation to establish the Kempner Institute for the Study of Natural and Artificial Intelligence. Sham Kakade acknowledges funding from the Office of Naval Research under award N00014-22-1-2377 and the National Science Foundation Grant under award #CCF-2212841. Nikhil Vyas acknowledges funding from NSF grant DMS-2134157 and DOE grant DE-SC0022199. Boaz Barak acknowledges funding from a Simons Investigator Fellowship, NSF grant DMS-2134157, DOE grant DE-SC0022199 and DARPA grant W911NF2010021.

References