# OffRoadTranSeg: Semi-Supervised Segmentation using Transformers on OffRoad
environments

Anukriti Singh1, Kartikeya Singh1, and P.B. Sujit The authors are with the
IISER Bhopal. ∗ Equal contribution.

###### Abstract

We present OffRoadTranSeg, the first end-to-end framework for semi-supervised
segmentation in unstructured outdoor environment using transformers and
automatic data selection for labelling. The offroad segmentation is a scene
understanding approach that is widely used in autonomous driving. The popular
offroad segmentation method is to use fully connected convolution layers and
large labelled data, however, due to class imbalance, there will be several
mismatches and also some classes may not be detected. Our approach is to do
the task of offroad segmentation in a semi-supervised manner. The aim is to
provide a model where self supervised vision transformer is used to fine-tune
offroad datasets with self-supervised data collection for labelling using
depth estimation. The proposed method is validated on RELLIS-3D and RUGD
offroad datasets. The experiments show that OffRoadTranSeg outperformed other
state of the art models, and also solves the RELLIS-3D class imbalance
problem.

##  I Introduction

An autonomous outdoor navigation [1, 2] system for unstructured environment
[3] can be built using semantic segmentation network. It has applications in
areas like inspection, exploration, rescue, and reconnaissance. But scene
semantic segmentation in off-road environments is challenging due to absence
of a defined boundaries between classes and terrain structure. This leads to
challenges like class imbalance when algorithms are deployed in real
environments. However, class imbalance problem is highly environment specific
and becomes more severe when its within a dataset, like in RELLIS-3D [4]. This
makes semantic segmentation in off-road classes challenging as compared to
urban environments. Presently, Convolutional Neural Networks (CNNs) [5] in
semantic segmentation [6] have achieved state-of-the-art results for
unstructured outdoor environments like RELLIS-3D. However, CNNs require dense
annotated datasets, which is costly and takes time specially in off-road
environments where classes that are only visible in few frames can be
important for autonomous decision making and navigation planning.

CNNs typically fail to produce accurate masks when the content of the images
are complicated. For example in RELLIS-3D off-road dataset Jiang et al. [4]
used HRNet for semantic segmentation. They successfully segmented classes like
sky, grass, tree, etc. but there were some exceptions like log, water, and
building where the mIOU was 0. Guan et al. [7] and Viswanath et al. [8]
performed segmentation after classifying groups of terrain classes based on
traversal regions. [7] used group attention network with transformers for
segmentation and [8] used color clustering. However, since both of them pooled
classes they did not have to face the challenge of class imbalance. Recently,
it was proposed to use transformers for vision based tasks [9] like semantic
segmentation [10, 11, 12] after their success in Natural Language
Processing(NLP). Jin et al. [13] showed how transformers based model can
perform better for semantic segmentation on two datasets: RUGD and Cityscape.
Although, their method was completely supervised and required all the images
in the dataset to be annotated. Caron et al. [14] proposed DINO to use self
supervised pretraining on vision transformers, which can benefit segmentation
as well as classification tasks in vision. DINO is pretrained on ImageNet
dataset and uses knowledge distillation [15].

Figure 1: Our framework consists of two stages: Fine-tuning self supervised
vision transformer to get the attention maps and automatically selecting
labelled images for evaluating the network for semi supervised semantic
segmentation

### Main Results:

Annotations for off road datasets is particularly challenging since the
boundaries are mixed and not well defined, it takes a lot of time and
increases stress leading to mislabelling. In this paper, we present a novel
semi-supervised approach for offroad semantic segmentation. The approach
involves fine-tuning the DINO network with no labelled data and evaluating it
with the automatic selected data. Our method is general and is particularly
designed for unstructured outdoor environments. Semi-supervised sequence
segmentation requires to provide the mask of the first image in the sequence
and the network segments the subsequent frames based on that. We instead
propose to do an automatic data selection, where the selected images are
labelled instead of just the first frame. In summary, the main contributions
of our proposed method are :

  * •

A novel model for semi-supervised semantic segmentation in unstructured
outdoor environment using self attention in vision transformers.

  * •

Completely solving class imbalance problem by obtaining mIoU value for all the
classes in RELLIS-3D dataset. We also test our model on other offroad datasets
like RUGD and obtain IoU values for multiple classes better than those
reported in RUGD [16].

  * •

Significantly reducing the amount of labelled data required for training and
evaluating using an algorithm to automatically select the most diverse set of
images per sequence. We used less than 25 annotated images during training.

We evaluate our method on RELLIS-3D [4] which contains 20 classes and 13, 556
images and RUGD [16] dataset with 24 classes and over 29, 000 images.
OffRoadTranSeg outperforms the networks used in [4] and [16] in the semi
supervised fashion.

Figure 2: Both the columns highlight the raw image, ground truth, performance
of SOTA algorithm and our approach on RELLIS-3D and RUGD dataset. We observe
that OffRoadTranSeg is able to segment all the classes of the image as present
in the raw image.

##  II Related Work

###  II-A Semi-supervised semantic segmentation

Segmentation is a widely studied area using convolutional neural network as
well as the present growing transformer networks. The semantic segmentation
tasks can be supervised, semi supervised and self supervised. A number of
architectures have been proposed to perform segmentation, like PSPnet [17],
HRNETV2+OCR [18], BiSeNetV2 [19] in CNNs and DETR [12], SETR [11] in
transformer based networks. However, the CNNs based network performs well in
urban navigation where the roads and structure is defined, they lack in
performance in offroad unstructured areas due to undefined, overlapping
boundaries and convoluted area.

###  II-B Transformers

Transformers were initially proposed for their use in Natural Language
Processing (NLP). With their increasing good performance, transformers were
then introduced in computer vision with CNNs, making a hybrid model in DETR
[12]. Later ViT [9] was proposed which proved to be a successful transformer
network for vision tasks like object classification. Transformer based network
have benefits over purely CNN architectures since they have high accuracy with
less computation time for training. TrSeg[20] used transformer based network
for segmentation in urban area dataset like cityscape and offroad dataset RUGD
, however their network performs supervised segmentation. DINO is a self
supervised network which predicts attention in the images and can also be used
in semantic segmentation. Our network is based on DINO, which makes
segmentation in unstructured environments semi supervised. It has explicit
information about the semantic segmentation of an image, which does not emerge
as clearly with supervised ViTs, nor with convnets.

###  II-C Dataset

Navigation is an important part in perception module of urban and unstructured
offroad regions. Latest datasets on offroad are RELLIS-3D and RUGD which are
especially tailored for semantic segmentation in a variety of natural,
unstructured semi-urban areas. RELLIS-3D is the latest dataset which is hugely
derived from RUGD and has additionally added unique terrain classes which
aren’t present in RUGD . Both these datasets have rich ontology and large
annotations of their ground truths. RELLIS-3D dataset also includes 3-D lidar
data and their annotations. We use both these latest datasets to evaluate the
performance of our proposed framework.

IoU Distribution for RELLIS-3D on OffRoadTranSeg
---
Sky | Bush | Building | Log | Grass | Person | Tree | Asphalt | Rubble | Mud | Fence | Puddle | Concrete | Barrier | Vehicle | Object | Pole
97% | 96% | 92% | 96% | 92% | 40% | 82% | 97% | 77% | 97% | 88% | 92% | 98% | 90% | 98% | 77% | 87%
IoU Distribution for RELLIS-3D on HRNet
98% | 78% | 1% | 0% | 93% | 89% | 91% | 67% | 77% | 96% | 88% | 64% | 92% | 67% | 42% | 50% | 49%

TABLE I: Class-wise IoU distribution for RELLIS-3D dataset on OffRoadTranSeg
and HRNet.

Class | Dirt | Rockbed | Sand | Grass | Log | Bicycle | Tree | Mulch | Pole | Fence | Bush | Sky | Sign | Vehicle | Rock | Concrete | Bridge | Asphalt | Gravel | building |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
IoU | 88% | 94% | 92% | 97% | 89% | 91% | 82% | 86% | 94% | 90% | 76% | 96% | 88% | 72% | 86% | 88% | 91% | 96% | 89% | 93%

TABLE II: Class-wise IoU distribution for RUGD dataset on OffRoadTranSeg .

Class | Dirt | Rockbed | Sand | Grass | Log | Bicycle | Tree | Mulch | Pole | Fence | Bush | Sky | Sign | Vehicle | Rock | Concrete | Bridge | Asphalt | Gravel | building |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
IoU | 0% | 10% | 27% | 77% | 10% | - | 83% | 45% | 19% | 45% | 27% | 81% | 11% | 60% | 9% | 83% | 0% | 13% | 38% | 73%

TABLE III: Class-wise IoU distribution for RUGD dataset taken from their
benchmark method 4(ResNet50+UperNet).

##  III OffRoadTranSeg

The proposed OffRoadTranSeg architecture is illustrated in Fig. 2 and it
contains two major component : Self-Supervised Transformer and Automatic Data
Selection. With OffRoadTranSeg off-terrain unstructured environment is
semantically segmented using self supervised attention maps and automatic data
selection. Our framework is motivated by DINO[14] a state of the art self
supervised attention mechanism based on student teacher transformer network
which performed well on ImageNet dataset and DAVIS-2017 video instance
segmentation benchmark [21]. This framework takes the advantage of attention
in transformers and addresses the class imbalance problem which was introduced
with RELLIS-3D dataset in semantic segmentation of offroad images. The details
of our OffRoadTranSeg model for semi supervised semantic segmentation will be
described in the following subsections.

###  III-A Transformer

OffRoadTranSeg is based on a fully transformer-based architecture, partially
borrowed from knowledge distillation[15] and self-supervised approaches used
in DINO. Knowledge distillation has two network: student network and a teacher
network. The student network $S_{\Theta_{s}}$ is trained to match the output
of a given teacher network $S_{\Theta_{t}}$, parameterised by $\Theta_{s}$ and
$\Theta_{t}$ respectively. When given an input image $x$, probability
distribution $P_{s}$ and $P_{t}$ from both the networks are calculated as an
output over the dimension $K$. The output of the network, probability $P$ is
normalized using a softmax function described below:

$P_{s}(x)^{(i)}=\frac{\exp(S_{\Theta_{s}}(x)^{(i)}/T_{s})}{\sum_{k=1}^{K}\exp(S_{\Theta_{s}}(x)^{(k)}/T_{s})}$
(1)

Where the temperature parameter $T_{s}>0$ controls the sharpness of the output
distribution. The similar equation holds true for probability distribution
$P_{t}$. In DINO both the student and the teacher architecture $S$ share the
same network with different set of parameters, $\Theta_{s}$ and $\Theta_{t}$.
This self supervised vision transformer network has two types of backbone
architectures $f$, ViT[9] and ResNet-50[22] and a projection head $h$. For
unstructured terrain image dataset we use both these networks as backbone. The
projection head $h:g=h\textopenbullet f$, which works best for this network
consists of a three layer multi-layer perceptron with 2048 hidden dimension
followed by $l_{2}$ normalization and a weight normalized fully connected
layer. Also, The DINO network does not have batch normalizations (BN) by
default.

###  III-B Automatic Data selection (ADS)

Self-supervised monocular depth estimation(SDE) [23] a type of label selection
method which makes the process of selecting the image to annotate automatic.
Recently, manually labelling data is starting to get replaced with self
supervised learning. Segmentation is tightly connected with depth estimation.
The leverage of this is taken to improve semantic segmentation in unstructured
environments with self supervised depth estimation. Labelling images in
offroad is particularly hard because it requires fine grained segmentation.
With this approach we come up with a way which requires comparatively less
number of annotated images and improve the performance of segmentation. Self
supervised depth estimation is used as a pretext task for our offroad data,
which has $N$ number of total samples and $N_{s}$ are selected for annotation.
Here we denote, $R$ as total number images in the data, $R_{A}$ as the subset
of images selected for annotation and $R_{U}$ as the un-selected images
subset. Initially, all data is un-selected and hence, $R=R_{U}$ and selected
images for annotation is empty. For the selection of images we first do
diversity sampling, to make sure most diverse set of images are selected and
which cover different scenes in off-trail image datasets. The set of images
choosen for annotation should be diverse enough so that they represent the
entire dataset. The intermediate layer of SDE network calculates features
$\Phi_{j}^{SDE}$ over which we calculate L2 distance and do iterative farthest
point sampling. At step t, for each of the samples at that point, we choose
the image from $R_{U}$ which has the largest distance to the current
annotation set $R_{A}$. The selected sample of images $R_{A}$ is iteratively
expanded by moving one image at a time from $R_{U}$ to $R_{A}$ until the
required number of images are collected:

$i=\underset{I_{i}\epsilon R_{U}}{\arg\max}\underset{I_{i}\epsilon
R_{A}}{\min}\left\|\Phi_{i}^{SDE}-\Phi_{j}^{SDE}\right\|\\\ $ (2)

The next selection criteria is uncertainty sampling. When the model is trained
on $R_{A}$, the images with high uncertainties near the decision boundary are
favoured.For uncertainty sampling, we need to train and update the model with
$R_{A}$. It is inefficient to repeat this every time a new image is added. To
make it more efficient, the selection is divided into T steps and the model is
trained T times. In each step t, the required number of images are selected
and moved from unselected subset to selected images for annotation. With
uncertainty Sampling the aim is to select difficult samples, i.e., samples in
$R_{U}$ that the model trained on the current $R_{A}$ cannot handle well since
the dataset of offroad is very diverse and uncertain. The equation is then
updated :

$i=\underset{I_{i}\epsilon R_{U}}{\arg\max}\underset{I_{i}\epsilon
R_{A}}{\min}\left\|\Phi_{i}^{SDE}-\Phi_{j}^{SDE}\right\|-\lambda_{E}E(i)$ (3)

Using automatic data selection we get a set of selected annotated data. To
perform semi-supervised sequence segmentation a full mask of the object(s) of
interest in the first frame of a video sequence has to be given and the
network produce the segmentation mask for that object(s) in the subsequent
frames. We leverage automatic data selection in semi supervised video
segmentation, where instead of giving annotation of only the first frame we
select the most diversed frames $n_{t}$ from a sequence and divide it in
batches.

##  IV Experiments and Results

In this section we provide the implementation details of OffRoadTranSeg and
describe the experiments performed to highlight the two main components of our
approach.

Arch |  mIoU |  Split
---|---|---
ViT_small |  88% |  $R_{a}$
ViT_base |  72% |  $R_{a}$
ViT_tiny |  66% |  $R_{a}$
ResNet50 |  36% |  $R_{a}$
TABLE IV: Performance of OffRoadTranSeg using different architectures. Framework |  mIoU
---|---
OffRoadTranSeg |  88%
HRNet |  67%
FPN |  87%
TABLE V: Mean-IoUs for RELLIS-3D dataset. Framework |  mIoU
---|---
OffRoadTranSeg |  89%
TABLE VI: Mean-IoUs for RUGD dataset.

###  IV-A Implementation Details

####  IV-A1 Dataset:

We evaluate our OffRoadTranSeg on two recent off-road datasets RELLIS-3D and
RUGD . RELLIS-3D dataset consists of 20 classes and 6,235 labelled images. The
original resolution of the image is $1920~{}\times~{}1600$ but for training
purposes we downscale the image to $512~{}\times~{}512$. With RELLIS-3D
dataset we segment unique classes like rubble, mud, and man-made barriers
which weren’t present in RUGD .

RUGD dataset has 7,456 labelled images, that is for every fifth frame in the
sequence. It has 24 different classes including categories like sign, rock and
bridge. The original size of the image is $688~{}\times~{}550$. Among these
thousands of images We use the automatic data selection algorithm to select
the most diverse set of images and provide only their annotation for semi-
supervised video sequence segmentation in both these datasets.

####  IV-A2 Training Details:

We follow DINO [14] and fine tune the network on RELLIS-3D without labels. The
training is completely unsupervised and is performed with AdamW optimizer[24]
and 5 batch size using the ViT-8 model. The output patch tokens are then
evaluated on two offroad datasets RELLIS-3D and RUGD for semantic
segmentation. For the semi supervised video sequence segmentation instead of
providing label of only the first frame in the sequence, we run ADS for each
sequence to select the most diversed images and provide their label. For ADS
we follow [23], it has a slimmed network architecture with a ResNet50 encoder
and fewer decoder channels. We iterate the number of selected sample for
labelling as 25 and 744. For both subsets, a student depth error is calculated
when the student depth network is trained from scratch for 4k and 20k
iterations.

Figure 3: (a) Training parameters for loss degradation of using different
backbones in DINO transformer network in RELLIS-3D dataset. (b) Representation
of mIoUs obtained from only transformer network and transformer with ADS.
Figure 4: Segmentation results: $b_{1}$ represents the outputs from batch 1 of
during semi supervised segmentation. Whereas, $b_{n}$ represents the outputs
from the last batch.

###  IV-B Ablation studies

To evaluate the performance of our proposed OffRoadTranSeg approach we
calculate the individual class IoU on RELLIS-3D dataset and compare it with
the the convolutional network based network HRNet. Table I shows that
OffRoadTranSeg solves the class imbalance problem by giving the IoU value of
$96\%$ which was $0\%$ in CNN based network HRNet as provided in the RELLIS-3D
benchmark. The comparison also shows that with our approach we get state of
the art IoU values in majority of the categories. We evaluate OffRoadTranSeg
on one another dataset, RUGD and the get the values for all different
categories as shown in table II compared with table III. Figure 2 shows the
visible differences in the performance of different networks. The RELLIS-3D
dataset raw image has 7 classes and HRNet is only able to segment 4 of those
classes whereas with OffRoadTranSeg we segment all classes including log,
rubble and barrier. The mean-IoU(mIoU) value for the two datasets in table V
and table VI shows that using transformer and automatic data selection can
give the state of the art values in segmentation of unstructured outdoor
environments. We also analyze how different backbones of the self-supervised
transformer network impact the segmentation performance in the offroad
datasets by using four different architectures $ViT_{small}$, $ViT_{base}$,
$ViT_{tiny}$ and $ResNet-50$. We fine-tune off-road RELLIS-3D dataset in an
unsupervised fashion using vision transformer architectures and CNN
architecture. The performance is shown in table IV. Using our data selection
approach with four different architectures we see that $ViT_{small}$ gives the
best performance with $88\%$ mIoU and on the other hand with ResNet-50 has
$36\%$ mIoU value. Figure 3 summarizes these results with different number of
epochs in a form of graph.

We run ADS algorithm on each image sequence and select the best set of 25
images in RELLIS-3D and RUGD . For semi-supervised video segmentation instead
of providing the label for only the first image in the sequence, we provide
label masks for all these 25 images and divide the sequence into 25 batches.
Since, these selected images are well diversed with all the features we see
significant improvement in segmentation of offroad images. We show the
comparison in figure 4 where $b_{1}$ represents first batch of the sequence
and $b_{n}$ represents the last batch. We used the transformer based network
DINO to evaluate video segmentation on RELLIS-3D and RUGD , however, when the
label for only the first image of the sequence is provided we see good
performance in $b_{1}$ but the performance is poor as we proceed to the last
batch $b_{n}$ of the sequence. It shows that introducing ADS algorithm with
transformer based network can significantly improve the segmentation even for
the last batch, for example the last batch of the RUGD dataset in the figure
successfully segments log with grass and bush.

##  V Conclusion

In this work, we have explored transformer based approach for semi-supervised
segmentation in unstructured outdoor environments along with handling the
class imbalance problem in two most famous offroad datasets. We show how the
scene layout information present in the features of vision transformer can be
used for semi-supervised segmentation in offroad datasets. Annotation is an
important part of the segmentation task in off-trail environments because the
performance of the network depends on how precisely the data is labelled. But
on the same hand labelling an offroad dataset is particularly challenging
because of undefined boundaries. Hence in our approach, we propose to use an
Automatic Data Selection algorithm based on depth estimation which selects the
most feature rich images. This significantly reduces the number of annotated
images needed while training and evaluating with increase in performance. The
experiment results show that by introducing OffRoadTranSeg we get state-of-
the-art results in unstructured environments. But our approach also has some
limitations, it requires a human in loop to annotate the images after getting
the most diversed set of images selected for semi-supervised segmentation, for
future work the labelling process in between the loop can be automated which
will further reduce the chances inaccuracy.

## References

  * [1] M. Cordts, M. Omran, S. Ramos, T. Rehfeld, M. Enzweiler, R. Benenson, U. Franke, S. Roth, and B. Schiele, “The cityscapes dataset for semantic urban scene understanding,” in _Proc. of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2016.
  * [2] H. A. Alhaija, S. K. Mustikovela, L. Mescheder, A. Geiger, and C. Rother, “Augmented reality meets computer vision: Efficient data generation for urban driving scenes,” _International Journal of Computer Vision_ , vol. 126, no. 9, pp. 961–972, 2018.
  * [3] M. J. Procopio, J. Mulligan, and G. Grudic, “Learning terrain segmentation with classifier ensembles for autonomous robot navigation in unstructured environments,” _Journal of Field Robotics_ , vol. 26, no. 2, pp. 145–175, 2009.
  * [4] P. Jiang, P. Osteen, M. Wigness, and S. Saripalli, “Rellis-3d dataset: Data, benchmarks and analysis,” _arXiv preprint arXiv:2011.12954_ , 2020.
  * [5] Y. Lecun, L. Bottou, Y. Bengio, and P. Haffner, “Gradient-based learning applied to document recognition,” _Proceedings of the IEEE_ , vol. 86, no. 11, pp. 2278–2324, 1998.
  * [6] J. Long, E. Shelhamer, and T. Darrell, “Fully convolutional networks for semantic segmentation,” in _2015 IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2015, pp. 3431–3440.
  * [7] T. Guan, D. Kothandaraman, R. Chandra, and D. Manocha, “Ganav: Group-wise attention network for classifying navigable regions in unstructured outdoor environments,” _arXiv preprint arXiv:2103.04233_ , 2021.
  * [8] K. Viswanath, K. Singh, P. Jiang, S. Saripalli, _et al._ , “Offseg: A semantic segmentation framework for off-road driving,” _IEEE Conference on Automation Science and Engineering_ , 2021.
  * [9] A. Dosovitskiy, L. Beyer, A. Kolesnikov, D. Weissenborn, X. Zhai, T. Unterthiner, M. Dehghani, M. Minderer, G. Heigold, S. Gelly, _et al._ , “An image is worth 16x16 words: Transformers for image recognition at scale,” _arXiv preprint arXiv:2010.11929_ , 2020.
  * [10] R. Strudel, R. Garcia, I. Laptev, and C. Schmid, “Segmenter: Transformer for semantic segmentation,” _arXiv preprint arXiv:2105.05633_ , 2021.
  * [11] S. Zheng, J. Lu, H. Zhao, X. Zhu, Z. Luo, Y. Wang, Y. Fu, J. Feng, T. Xiang, P. H. Torr, _et al._ , “Rethinking semantic segmentation from a sequence-to-sequence perspective with transformers,” _arXiv preprint arXiv:2012.15840_ , 2020.
  * [12] X. Zhu, W. Su, L. Lu, B. Li, X. Wang, and J. Dai, “Deformable detr: Deformable transformers for end-to-end object detection,” _arXiv preprint arXiv:2010.04159_ , 2020.
  * [13] Y. Jin, D. Han, and H. Ko, “Trseg: Transformer for semantic segmentation,” _Pattern Recognition Letters_ , vol. 148, pp. 29–35, 2021.
  * [14] M. Caron, H. Touvron, I. Misra, H. Jégou, J. Mairal, P. Bojanowski, and A. Joulin, “Emerging properties in self-supervised vision transformers,” _arXiv preprint arXiv:2104.14294_ , 2021.
  * [15] G. Hinton, O. Vinyals, and J. Dean, “Distilling the knowledge in a neural network,” _arXiv preprint arXiv:1503.02531_ , 2015.
  * [16] M. Wigness, S. Eum, J. G. Rogers, D. Han, and H. Kwon, “A rugd dataset for autonomous navigation and visual perception in unstructured outdoor environments,” in _2019 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_. IEEE, 2019, pp. 5000–5007.
  * [17] H. Zhao, J. Shi, X. Qi, X. Wang, and J. Jia, “Pyramid scene parsing network,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2017, pp. 2881–2890.
  * [18] J. Wang, K. Sun, T. Cheng, B. Jiang, C. Deng, Y. Zhao, D. Liu, Y. Mu, M. Tan, X. Wang, _et al._ , “Deep high-resolution representation learning for visual recognition,” _IEEE transactions on pattern analysis and machine intelligence_ , 2020.
  * [19] C. Yu, C. Gao, J. Wang, G. Yu, C. Shen, and N. Sang, “Bisenet v2: Bilateral network with guided aggregation for real-time semantic segmentation,” _arXiv preprint arXiv:2004.02147_ , 2020.
  * [20] Y. Jin, D. Han, and H. Ko, “Trseg: Transformer for semantic segmentation,” _Pattern Recognition Letters_ , vol. 148, pp. 29–35, 2021. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S016786552100163X
  * [21] J. Pont-Tuset, F. Perazzi, S. Caelles, P. Arbeláez, A. Sorkine-Hornung, and L. V. Gool, “The 2017 davis challenge on video object segmentation,” 2018.
  * [22] K. He, X. Zhang, S. Ren, and J. Sun, “Deep residual learning for image recognition,” _CoRR_ , vol. abs/1512.03385, 2015. [Online]. Available: http://arxiv.org/abs/1512.03385
  * [23] L. Hoyer, D. Dai, Y. Chen, A. Köring, S. Saha, and L. Van Gool, “Three ways to improve semantic segmentation with self-supervised depth estimation,” _arXiv preprint arXiv:2012.10782_ , 2020.
  * [24] I. Loshchilov and F. Hutter, “Fixing weight decay regularization in adam,” 2018\.


# CPR: Retrieval Augmented Generation for Copyright Protection

Aditya Golatkar Alessandro Achille Luca Zancato
Yu-Xiang Wang Ashwin Swaminathan Stefano Soatto
AWS AI Labs
{agolatka,aachille,zancato,yuxiangw<EMAIL_ADDRESS>

###### Abstract

Retrieval Augmented Generation (RAG) is emerging as a flexible and robust
technique to adapt models to private users data without training, to handle
credit attribution, and to allow efficient machine unlearning at scale.
However, RAG techniques for image generation may lead to parts of the
retrieved samples being copied in the model’s output. To reduce risks of
leaking private information contained in the retrieved set, we introduce Copy-
Protected generation with Retrieval (CPR), a new method for RAG with strong
copyright protection guarantees in a mixed-private setting for diffusion
models. CPR allows to condition the output of diffusion models on a set of
retrieved images, while also guaranteeing that unique identifiable information
about those example is not exposed in the generated outputs. In particular, it
does so by sampling from a mixture of public (safe) distribution and private
(user) distribution by merging their diffusion scores at inference. We prove
that CPR satisfies Near Access Freeness (NAF) which bounds the amount of
information an attacker may be able to extract from the generated images. We
provide two algorithms for copyright protection, CPR-KL and CPR-Choose. Unlike
previously proposed rejection-sampling-based NAF methods, our methods enable
efficient copyright-protected sampling with a single run of backward
diffusion. We show that our method can be applied to any pre-trained
conditional diffusion model, such as Stable Diffusion or unCLIP. In
particular, we empirically show that applying CPR on top of unCLIP improves
quality and text-to-image alignment of the generated results (81.4 to 83.17 on
TIFA benchmark), while enabling credit attribution, copy-right protection, and
deterministic, constant time, unlearning.

Figure 1: RAG vs CPR image generation. Images generated using the given prompt
for a fixed random seed using different methods. Safe Model: Pre-trained model
with no access to the retrievable data store, Retrieval-Score: Image generated
using Eq. 7, Retrieval-Mix-Score: Image generated using Eq. 8, CPR-KL, CPR-
Min, CPR-Alt: Images generated using our algorithms in Algorithm 1 Sec. 5.2.1
and Algorithm 2 Sec. 5.2.1. Images generated without CPR bear more resemblance
to the retrieved image, compared to the CPR generated images, which are
different from the retrieved image, while preserving the underlying concept in
the prompt (for example the astronaut seems to be on Moon, Big Ben is more
textured with different design).

##  1 Introduction

Foundation model users may need to adapt large-scale Diffusion Models to their
use cases, like personalization, editing, content creation etc. However, fine-
tuning the model on the user data is often not an option. This is in part due
to the steep cost of fine-tuning models, but also because user data is a
mutable entity: new data is constantly added, and low-quality data may often
be filtered out. Moreover, data owners may, at any point, change their mind
and demand that their data be removed.

Retrieval Augmented Generation (RAG) has emerged as a promising method to
handle these situations. Rather than using the user data to fine-tune the
model, supporting samples are retrieved from it at inference time to guide the
generation of new samples. Data may be easily added or removed from the
retrieval data store without changes to the model, and users may access
different subsets of the data based on their access-right. However, RAG
methods are double edged, direct access to retrieved reference images often
significantly improves the quality of generated samples but as we depict in
Fig. 1, RAG models are prone to copy information from the retrieved examples
into the model output, potentially resulting in significant leak of private
information. We formalize this observation in Sec. 5 and we show that applying
RAG on top of a public model, while retrieving private user data at inference
time, cannot satisfy even the weaker notion of privacy.

To remedy this, we introduce Copy-Protected Generation with Retrieval (CPR).
CPR retrieves multiple private examples from the private user data pool.
Information from all these samples is combined to generate a “private”
diffusion flow which uses common information of those samples while discarding
any unique and identifiable information. The resulting private flow is then
optimally combined with the “public” flow generated by the base model to
generate new outputs which still benefit from the retrieved samples, but
minimize the risk of information leak.

In particular, we show that our method satisfies the recently proposed notion
of copyright protection using Near Access Freeness (NAF) [62], a relaxation of
differential privacy aimed at protecting specific attribute of the training
data. Differently from previously proposed methods like [62] that realize NAF
with a computationally expensive rejection sampling method, CPR does so by
construction during the generation. Hence making our method significantly
faster than the previous baselines and while also keeping inference cost
deterministic.

Theoretically, we formally prove in Lemmas 1 and 2 that CPR offers strong
protection guarantees by ensuring that the generated samples contain at most
$k$-bits of unique information about retrieved samples, where $k$ can be tuned
by the user as required by the application. Empirically, we show that CPR can
use private data to improve quality of the generated images ($81.4\to 83.17$
TIFA score) while maintaining privacy guarantees on the retrievable data.

The rest of the paper is organized as follows. In Sec. 2 we provide a study of
the relevant related works in RAG and privacy. In Sec. 3 we define the
necessary notations, and in Sec. 4 show how to perform RAG with pre-trained
text-to-image diffusion models by formulating inference over mixture of
public-private distribution. In Sec. 5 we provide our CPR algorithm, along
with its theoretical guarantees, provide empirical evaluation of our method in
Sec. 6, followed by some discussion in Sec. 7.

##  2 Related Works

##### Retrieval Augmented Generation

Retrival Augmented Generation (RAG) methods have been successfully applied to
large language models (LLMs) [31, 54, 45, 24, 42]. RAG has been shown to
outperform even LLMs trained jointly on the training set and the retrievable
data pool. RAG have also been explored for image synthesis [2, 50, 69, 9, 67,
53, 7]. However, rather than reusing existing models, current methods require
training of retrieval-specific architectures which — unlike the standard text-
to-image diffusion models [49, 46, 47, 68] — can be prompted with several
retrieved images along with conditional information, such as text, as inputs.
Instead, we explore RAG using more generic pre-trained text-to-image diffusion
models. [2, 50, 69] train a diffusion-based image retrieval model that can be
prompted with latent image embeddings, while [9, 67] use autoregressive
generative models inspired from LLMs.

##### Image Manipulation

Several recent works [18, 35, 51, 40, 4, 25, 41, 63] have provided methods for
image manipulation, editing by either fine-tuning or changing the cross-
attention values at inference. With an appropriate retrieval function, and
database such methods can be used to perform retrieval augmented generation by
merging diffusion scores [23, 12, 38]. However, the manipulation methods
significantly lower inference speed. Instead, we opt to use the unCLIP model
[47] to generate a backward flow using the retrieved images, and merge it with
the flow generated by a base text-to-image diffusion model at inference [23,
38, 12, 49].

##### Privacy

Recent works [5, 6, 56, 57] have shown that such models are able to memorize
their training data. This raises several privacy challenges, including:

Unlearning: Machine unlearning [20, 3] enables users to delete their data from
the weights of trained models [17, 43]. [14, 23, 3, 19, 34, 39] provide
training methods which makes unlearning efficient, for example by breaking the
dataset into multiple shards and training separate models on each, followed by
ensembling at inference. Despite their improved privacy utility trade-offs
compared to a single model, such approaches still require frequent re-
training/fine-tuning. On the other hand, we propose splitting the training
dataset into a core safe dataset [21] used to train a core model, and a user
owned private data store used to retrieve samples. This allow instantaneous
forgetting of any private sample without having to retrain the model. This
strategy also improve performance (alignment), and enables easy continual
learning by simply adding new data to the data store. Moreover, privacy of
data which are never retrieved is completely preserved, unlike unlearning or
differential privacy [15, 22] methods which mix information about the entire
dataset in the weights.

Copyright Protection: Memorization in foundation models also increases the
risk of copying, style mimicry and copyright [5, 6, 52] at inference. [62]
proposed a definition for copying in generative models using near access
freeness (NAF), and provided the CP-$\Delta$ algorithm for copy-protected
generation. CP-$\Delta$ uses two generative models, trained on two disjoint
splits of the data, and then at inference samples from the product and the
minimum of the two distributions. However, using it directly out-of-the-box
for diffusion models is challenging. Instead, they propose another algorithm,
CP-$k$, based on rejection sampling. Diffusion models however tend to have
slow inference speed, and adding rejection sampling further aggravates the
speed problem. To address this, we introduce CPR, which provides a method to
sample using CP-$\Delta$ (satisfies NAF) in a single run, without the need for
rejection sampling.

##  3 Preliminaries

Let $p_{0}(x_{0})$ be a data distribution over images, which we seek to model
using a diffusion model [60, 58, 27]. Score based diffusion models models [60]
define a (variance preserving) forward flow through a SDE, which transforms
the distribution $p_{0}(x_{0})$ at time $t=0$ in a reference distribution
$p_{1}(x_{1})=N(0,I)$ at time $t=1$:

$dx_{t}=-\dfrac{1}{2}\beta_{t}x_{t}dt+\sqrt{\beta_{t}}d\omega_{t}$ (1)

where $x_{t}$ is the diffused input at time $t$, $d\omega_{t}$ is a standard
Wiener process, and $\beta_{t}$ are time varying coefficients (in practice
implemented through linear or cosine scheduling), which determine the
transition kernel and amount of noise added over time. The intermediate result
$p_{t}(x_{t})$ of the diffusion process at time $t$ equivalently expressed as
the result of applying a Gaussian kernel
$p_{t}(x_{t}|x_{0})=\mathcal{N}(x_{t};\gamma_{t}x_{o},\sigma^{2}_{t}I)$ to
$p_{0}(x_{0})$, resulting in
$p_{t}(x_{t})=\int_{x_{0}}p_{t}(x_{t}|x_{0})p_{0}(x_{0})dx_{0}$, where
$\gamma_{t}=\exp(-\frac{1}{2}\cdot\int_{0}^{t}\beta_{t}dt)$ and
$\sigma^{2}_{t}=1-\gamma^{2}_{t}$.

The forward process in Eq. 1 can be inverted through a corresponding backward
process [37, 60]. In particular, this process can be used to generate samples
of $p_{0}(x_{0})$ starting from a sample of $p_{1}(x_{1})=N(0,I)$:

$dx_{t}=\big{(}-\dfrac{1}{2}\beta_{t}x_{t}-\nabla_{x_{t}}\log
p_{t}(x_{t})\big{)}dt+\sqrt{\beta_{t}}d\omega_{t}$ (2)

where $\nabla_{x_{t}}\log p_{t}(x_{t})$ is the score function of data
distribution at $t$. Efficiently computing the score function is difficult.
Instead, it can be approximated $\nabla_{x_{t}}\log p_{t}(x_{t})\approx
s_{\theta}(x_{t},t)$ using a deep network $s_{\theta}(x_{t},t)$, _i.e_., a
diffusion model. In practice, diffusion models are often trained to take
additional inputs $s_{\theta}(x_{t},t,c)$ in order to model a conditional
distribution $p_{0}(x_{0}|c)$, where the conditioning $c$ provides additional
information about the sample to generate, such as textual prompts [11, 26].
Given samples of the joint distribution $p_{0}(x_{0},c)$, a diffusion model
$s_{\theta}(x_{t},t,c)$ can be trained by minimizing the score-matching
objective:

$\mathbb{E}_{(x_{0},c)\sim
p_{0}(x_{0},c)}\mathbb{E}_{t}\big{[}\|s_{\theta}(x_{t},t,c)-\nabla_{x_{t}}\log
p_{t}(x_{t}|x_{0})\|\big{]}$ (3)

Directly generating samples using the backward flow modeled by
$s_{\theta}(x_{t},t,c)$ can result into poor alignment [12, 27, 58]. This can
be improved through classifier-free guidance [26], which uses the modified
score:

$s_{\theta}(x_{t},t,\phi)+\lambda(s_{\theta}(x_{t},t,c)-s_{\theta}(x_{t},t,\emptyset)),$

where the hyper-parameter $\lambda$ controls the guidance scale, and
$\emptyset$ denotes that no conditioning is fed to the model.

Table 1: Improved text-to-tmage alignment with retrieval: We compute the TIFA
score [29] which measures the text-to-image alignment on a set of prompts
(Higher is better). We use a subset of MSCOCO [36] (2k images with high
aesthetic score) as the private data store. We show that simply using the
retrieval-score (in Eq. 7) is not enough to improve alignment, instead using
the retrieval-mixture-score (in Eq. 8) is important to generate aligned and
well composed images. CPR-KL, CPR-Min, CPR-Alt, meaningfully improve the text-
to-image alignment across different retrieval settings compared to the base
model while protecting the private data store.

##  4 Mixed-Privacy RAG

In this section, we introduce a method for privacy-enabled RAG that is based
on the notion of mixed-privacy [21, 22].

Let $D=\\{x^{i},c^{i}\\}_{i=1}^{N}\sim p(x,c)$ be a safe training dataset —
meaning that samples are considered public in the differential-privacy sense
(see [21, 22]). We assume $D$ is used to train a core public diffusion model
$s_{\theta}(x_{t},t,c)$, that accepts $c$ as conditioning information. We
shall also assume that $c$ is the output of a CLIP encoder
$c=\operatorname{CLIP}(\texttt{<prompt>})$ fed with either a text prompt or an
image prompt. Furthermore, let
$D_{\text{private}}=\\{x^{i},c^{i}\\}_{i=1}^{M}$ be a private dataset which
may require frequent unlearning, or may require privacy or copyright
protection. We shall consider $D_{\text{private}}$ as our data store for
retrieval.

##### Retrieval

At inference time, given a user prompt $c_{\text{test}}$ we retrieve a set of
$m$ relevant examples
${D_{\text{retr}}}=\\{(x_{i},\phi(c_{i},c_{\text{test}})\\}_{i=1}^{m}\subset
D_{\text{private}}$ to aid the generation process. For simplicity, we simply
retrieve the closest $m$ samples based on $L_{2}$-CLIP similarity score:

$\text{score}=\|c_{\text{test}}-c_{i}\|+\|c_{\text{test}}-\operatorname{CLIP}(x_{i})\|.$

Note however that in ${D_{\text{retr}}}$ we are modifying the prompt of the
retrieved samples through a function
$\phi(c_{i},c_{\text{test}})=c_{i}+c_{\text{test}}$ in order to align them
better with the user prompt.

##### Mixture-of-Distribution

Retrieved samples are used to improve the generation of new samples. Formally,
the goal of CPR is to modify the sampling backward process in order to
generate samples from a weighted mixture of the distribution of $D$ and
${D_{\text{retr}}}$ [23, 38, 12]:

$p(x|c)=w_{0}p_{D}(x|c)+w_{1}p_{{D_{\text{retr}}}}(x|c)$ (4)

where the weights $w_{0}=\lambda$ and $w_{1}=1-\lambda$ allow the user to
control the contribution of the retrieved samples at inference time through an
hyperparameter $0<\lambda<1$.

##### Mixture-of-Score

To sample from this mixture distribution, we need to compute its score
function $\nabla\log p_{t}(x_{t})$ at time $t$ (see eq. 2). From Sec. 3 we
have:

$\displaystyle p_{t}(x_{t}|c)=\int
p_{t}(x_{t}|x_{0})\big{[}w_{0}p_{D}(x_{0}|c)+w_{1}p_{D_{\text{retr}}}(x_{0}|c)\big{]}dx_{0}$
(5)

where $p_{t}(x_{t}|x_{0})=\mathcal{N}(x_{t};\gamma_{t}x_{0},\sigma^{2}_{t}I)$
is a Gaussian kernel. The following proposition expresses the score of the
mixture as a function of the score of the individual components:

######  Proposition 1.

Let $p_{t}(x_{t}|c)$ be as in Eq. 5, then $\nabla_{x_{t}}\log p_{t}(x_{t}|c)$
is given by:

$\displaystyle\nabla_{x_{t}}\log p_{t}$
$\displaystyle=\hat{w}^{t}_{0}\nabla_{x_{t}}\log
p^{t}_{D}(x_{t}|c)+\hat{w}^{t}_{1}\nabla_{x_{t}}\log
p^{t}_{D_{\text{retr}}}(x_{t}|c)$

where we have defined:

$\displaystyle\hat{w}^{t}_{0}$
$\displaystyle=w_{0}\dfrac{p^{t}_{D}(x_{t}|c)}{p_{t}(x_{t}|c)},\ \
\hat{w}^{t}_{1}=w_{1}\dfrac{p^{t}_{D_{\text{retr}}}(x_{t}|c)}{p_{t}(x_{t}|c)}.$

and $p^{t}_{D}(x_{t}|c)$ denotes the forward flow of the distribution
$p_{D}(x_{t}|c)$ at time $t$ (and similarly for
$p^{t}_{D_{\text{retr}}}(x_{t}|c)$) and
$p_{t}(x_{t}|c)=p^{t}_{D}(x_{t}|c)+p^{t}_{D_{\text{retr}}}(x_{t}|c)$.

While $\hat{w}^{t}_{0}$ and $\hat{w}^{t}_{1}$ could be computed exactly, we
find that treating them as fixed hyper-parameters simplifies the
implementation and performs well. The scores $\nabla_{x_{t}}\log
p_{D}(x_{t}|c)$ can be approximated empirically by a diffusion model
$s_{\theta_{0}}(x,t,c)$ trained on $D$. However, we do not have a model
trained on the retrieved data ${D_{\text{retr}}}$ to estimate
$\nabla_{x_{t}}\log p_{D_{\text{retr}}}(x_{t}|c)$. To solve the issue, recall
that such a diffusion model $s_{\theta_{1}}$ that minimizes the loss:

$\displaystyle s_{\theta_{1}}=\arg\min_{s_{\theta}}\mathbb{E}_{(x_{0},c)\sim
p_{{D_{\text{retr}}}}}\mathbb{E}_{x_{t}}\big{[}\|s_{\theta}(x_{t},t,c)$
$\displaystyle\hskip 30.00005pt-\nabla_{x_{t}}\log\big{(}\int
p_{t}(x_{t}|x_{0})p_{{D_{\text{retr}}}}(x_{0},c)\big{)}\big{\|}\big{]}$ (6)

Since $|{D_{\text{retr}}}|\ll|D|$, we expect the minimizer $\theta_{1}$ to be
a small small perturbation $\theta_{1}=\theta_{0}+\Delta\theta_{1}$. However,
fine-tuning $s_{\theta_{0}}(x,t,c)$ to find such $\Delta\theta_{1}$ for every
inference request is computationally prohibitive.

Instead of fine-tuning, we approximate the expected behavior of
$s_{\theta_{1}}$ through prompting. Textual inversion and prompt tuning have
been shown to perform comparably to fine-tuning on small datasets while using
orders of magnitute less parameters [18, 35, 65, 55]. However, despite the
reduction, it is still cumbersome to fine-tune at inference. Instead we
propose manually modifying the user prompt $c_{\text{test}}$ using the CLIP
embeddings of the retrieved samples, and define the retrieval-score function:

$\displaystyle\hat{s}_{\theta_{0}}(x_{t},t,c_{\text{test}})\triangleq
s_{\theta_{0}}\Big{(}x_{t},t,\frac{1}{m}\sum_{x_{i}\in{D_{\text{retr}}}}\text{CLIP}(x_{i})\Big{)}$
(7)

We visualize in Fig. 1 the results of sampling with Eq. 7. This definition is
motivated by the following proposition, which bounds the distance of Eq. 7
from the optimal.

######  Proposition 2.

Assume that $s_{\theta}$ is Lipschitz in $\theta$ and $c$. Let
$s_{\theta_{0}+\Delta\theta_{1}}(x_{t},t,c)$ be the optimal solution to Eq. 6
and let ${D_{\text{retr}}}$ the private samples retrieved using
$c_{\text{test}}$. Then

$\displaystyle\|s_{\theta_{1}}(x_{t},t,c)-\hat{s}_{\theta_{0}}(x_{t},t,c_{\text{test}})\|$
$\displaystyle\leq$ $\displaystyle
l_{\theta}\|\Delta\theta_{1}\|+l_{c}\Big{\|}c_{\text{test}}-\frac{1}{m}\sum_{x_{i}\in{D_{\text{retr}}}}\operatorname{CLIP}(x_{i})\Big{\|}$

Above result shows that we can approximate the optimal diffusion model trained
on retrieved data using the engineered prompt
$\frac{1}{m}\sum_{x_{i}\in{D_{\text{retr}}}}\operatorname{CLIP}(x_{i})$, which
only requires computing the CLIP embeddings of the retrieved images. Combining
Proposition 1 and Proposition 2, we finally obtain an expression for the score
function of retrieval-augmented mixture of distributions, which we call
retrieval-mixture-score:

$\displaystyle
s_{RAG}(x_{t},t,c_{\text{test}};D_{\text{private}})\triangleq\hat{w_{0}}s_{\theta_{0}}(x_{t},t,c_{\text{test}})$
$\displaystyle\hskip
40.00006pt+\hat{w_{1}}s_{\theta_{0}}\Big{(}x_{t},t,(1/m)\sum_{x^{i}\in{D_{\text{retr}}}}\text{CLIP}(x^{i})\Big{)}$
(8)

Eq. 8 allows us any pre-trained CLIP-based diffusion model to generate
retrieval augmented samples without any further changes (see Fig. 1). In Tab.
1 we show that Eq. 8 improves text-to-image alignment (TIFA goes from 81.4 to
82.21). Parallelly, the retrieval-mixture score function already has immediate
application to privacy, since it makes it trivial to unlearn examples
contained in $D_{\text{private}}$ in constant time: these samples are not used
to train any parameter, and hence can be forgotten by simply removing them
from disk. However, samples retrieved at inference time can still leak private
information, which tackle this next.

Input: $\nabla_{x_{t}}\log\int q_{t}(x_{t}|x_{0})q^{(1)}(x|c)dx_{0}$,
$\nabla_{x_{t}}\log\int q_{t}(x_{t}|x_{0})q^{(2)}(x|c)dx_{0}$, T, N,
$c_{\text{test}}$

Output: $x_{0}$

1 $x_{T}\sim\mathcal{N}(0,I)$

2for  _$t=T\cdots 0$_ do

3 for  _$i=1\cdots N$_ do

4

5
$x_{t}=x_{t}+\dfrac{\epsilon_{t}}{2}\cdot\dfrac{1}{2}\Big{(}\nabla_{x_{t}}\log\int
q_{t}(x_{t}|x_{0})q^{(1)}(x|c_{\text{test}})dx_{0}+\nabla_{x_{t}}\log\int
q_{t}(x_{t}|x_{0})q^{(2)}(x|c_{\text{test}}dx_{0})\Big{)}+\sqrt{\epsilon_{t}}z$
where $z\sim\mathcal{N}(0,I)$

6 $x_{t-1}=x_{t}$

Algorithm 1 CPR-KL

##  5 Copy-Protected Generation

In this section, we will provide algorithms for copyright protected generation
— in the Near-Access Freeness sense of [62] — using our mixed-privacy RAG
method.

##### Near-Access Freeness

Let $D_{\text{private}}$ be a set of private samples, whose information we
want to protect, and let $\Delta$ be a divergence measure between probability
distributions, such as the KL-divergence $\Delta_{KL}$ or thr max-divergence
$\Delta_{\text{max}}$ (that is, the Renyi Divergence as
$\alpha\rightarrow\infty$). Let
$\operatorname{safe}:D_{\text{private}}\rightarrow\mathcal{M}$ be a function
which maps a sample $x^{i}\in D_{\text{private}}$ to a generative model
trained without using that $x^{i}$. The Near Access-Free (NAF) criteria is
defined as:

######  Definition 1 (NAF Definition 2.1 in [62]).

We say that a generative model $p(x|c)$ is $k_{c}$-near access-free (or
$k_{c}$-NAF) on a prompt $c$ with respect to $D_{\text{private}}$, and
$\Delta$, $\operatorname{safe}$, if for all $x^{i}\in D_{\text{private}}$ we
have $\Delta\Big{(}p(x|c)||\operatorname{safe}_{x^{i}}(x|c)\Big{)}\leq k_{c}$.

In practice, $\operatorname{safe}_{x^{i}}$ can be a model trained with leave-
one-out, or be sharded-safe [62], or simply be the safe core diffusion model
$s_{\theta_{0}}(x_{t},t,c)$. The above definition says that to perform safe
generation the output sample must be close in distribution to a model which
did not have access to the private samples in $D_{\text{private}}$.

Input: $c_{\text{test}}$, $\widetilde{s}(x_{t},t,c;q^{(1)})$,
$\widetilde{s}(x_{t},t,c;q^{(2)})$, $J$, $\text{reverse-update}(x_{t},s_{t})$

Output: $x_{0}$

1 $x_{T}\sim\mathcal{N}(0,I)$

2for  _$t=T\cdots,0$_ do

3 if  _$t\in J$_ then

4 $s(x_{t},t,c_{\text{test}})=\widetilde{s}(x_{t},t,c_{\text{test}};q^{(2)})$

5

6 else if  _$t\not\in J$_ then

7 $s(x_{t},t,c_{\text{test}})=\widetilde{s}(x_{t},t,c_{\text{test}};q^{(1)})$

8 $x_{t-1}=\text{reverse-update}(x_{t},s(x_{t},t,c_{\text{test}}))$

Algorithm 2 CPR-Choose Figure 2: (A) We plot the histogram of
$\Delta_{\text{max}}=\log\dfrac{p(x|c)}{\operatorname{safe}(x|c)}$ as we vary
the contribution of the retrieval-score ($\hat{w_{1}}$ in Eq. 8). We use
$\hat{w_{1}}$ as a user tunable parameter which controls the amount of bits
the generated images are different from $\operatorname{safe}$. We show that as
we reduce $\hat{w_{1}}$, empirical $k_{c}$ (max value on the x-axis with non-
zero probability) decreases. (B) Comparison to baseline, [62], with k=1500
using rejection sampling. Smaller k leads to slow generation which is evident
from the distribution.

###  5.1 CPR-KL

We first report here Theorem 3.1 from [62] which provides a simple procedure
to generate NAF-protected samples with respect to KL-divergence.

######  Theorem 1.

(Theorem 3.1 [62]) Given a dataset $\widetilde{D}$, and copyrighted samples
$\mathcal{C}\in\widetilde{D}$, split $\widetilde{D}$ into two disjoint shards
$D_{1},D_{2}$, and train two generative models $q^{(1)},q^{(2)}$ on each
respectively. Given the two models return a new model which satisfies
$k_{c}$-NAF wrt $\Delta_{KL}$

$\displaystyle p(x|c)=\dfrac{\sqrt{q^{(1)}(x|c)q^{(2)}(x|c)}}{Z(c)}$ (9)

where $k_{c}=-2\log{(1-\text{H}^{2}(q^{(1)}(x|c),q^{(2)}(x|c)))}$, H is the
Hellinger distance.

However, for diffusion models we do not have access to $q^{(1)}$ and
$q^{(2)}$, but only to the scores $\nabla_{x_{t}}\log\int
q_{t}(x_{t}|x_{0})q^{(1)}(x|c)dx_{0}$ and $\nabla_{x_{t}}\log\int
q_{t}(x_{t}|x_{0})q^{(2)}(x|c)dx_{0}$ respectively, where $q_{t}(x_{t}|x_{0})$
is a variance preserving Gaussian distribution.

We therefore extend Theorem 1 to generative models by extending it to models’
scores.

Given score functions, we define the CPR-KL algorithm in Algorithm 1 where we
average the two scores at every step during backward diffusion using Langevin
Dynamics [12, 59, 64, 8, 44]. In the following result we prove that sampling
using Algorithm 1 indeed ensures $k_{c}-$NAF.

######  Lemma 1.

Let $x_{0}$ be the output of Algorithm 1. Under certain regularity conditions
(see Supplementary Material), $x_{0}$ is $k_{c}-$NAF w.r.t.
$\operatorname{safe}$, $\mathcal{C}$, $\Delta_{\text{KL}}$.

By the previous result, Algorithm 1 enables us to generate samples from Eq. 9,
as $T,N$ increases and $\epsilon_{t}$ decreases. However, in practice we do
not have access to the optimal scores, but instead approximations which use
DNNs. In our setting we shall consider having the safe model
$s_{\theta_{0}}(x_{t},t,c)$, and the RAG score on the private datastore
$s_{RAG}(x_{t},t,c_{\text{test}};D_{\text{private}})$. In practice, although
combining the two scores as in Algorithm 1 can produce better results, it also
doubles the computation cost at inference time. To circumvent this we now
describe CPR-Choose (Algorithm 2) which approximates Algorithm 1 without
increasing computational complexity.

Figure 3: Concept similarity with CPR: In this figure we show the CLIP
similarity between CPR generated images and the textual prompt (Syn-Cap) and
the retrieved images (Syn-Ret) respectively. We show that while the CPR
generated image preserves the concept presented in the textual prompt (their
similarity with the caption is high), they do not copy the private retrieved
images (their similarity with the retrieved samples is low).

###  5.2 CPR-Choose

We now propose another CPR algorithm which does not incur in higher
computational cost of CPR-KL. First we recall a result on the likelihood
estimation of samples with MMSE denoisers, then we show how to use it to
define an efficient NAF algorithm w.r.t. $\Delta_{\text{max}}$.

Estimating sample likelihood with MMSE denoiser Recently, [32, 33] provided a
simple method for estimating the probability of individual samples by
computing the Minimum mean square error (MMSE) using pre-trained text-to-image
diffusion models. Let $x_{t}=\gamma_{t}x_{0}+\sigma_{t}\epsilon$, $x_{0}\sim
p(x_{0}|c)$ where $\epsilon\sim\mathcal{N}(0,I)$, and
$\alpha(t)=\log\dfrac{\gamma^{2}_{t}}{\sigma^{2}_{t}}$ be the log SNR. Then
the MMSE denoiser for a distribution $p$ can defined as:

$\displaystyle\widetilde{s}(x_{t},t,c;p)\triangleq\text{argmin}_{s(\cdot)}\mathbb{E}_{p(x_{0}|c),\epsilon}\|\epsilon-s(x_{t},t,c)\|^{2}$
$\displaystyle=\mathbb{E}_{p(x_{0}|x_{t},c)}\Big{[}\dfrac{x_{t}-\gamma_{t}x_{0}}{\sigma_{t}}\Big{]}$
(10)

Using the MMSE denoiser, [32, 33] provide a simple expression for estimating
the log probability of $x_{0}$.

$\displaystyle\log
p(x_{0}|c)=-\int\mathbb{E}_{\epsilon}\|\epsilon-\widetilde{s}(x_{t},t,c;p)\|^{2}\alpha^{\prime}(t)dt+const$
(11)

where $\alpha^{\prime}(t)$ is the time-derivative of $\alpha(t)$. Note that
$\widetilde{s}(x_{t},t,c;p)$ is also equivalent to the diffusion score we
obtained in the previous sections.

This result shows that to obtain NAF w.r.t. $\Delta_{\text{max}}=\log
p(x|c)/\operatorname{safe}(x|c)$, all we need to do is bound the difference in
MMSE at each time step $t$. We can bound this by choosing
$p(x|c)=\operatorname{safe}(x|c)$ for majority of $t$, while using
$D_{\text{private}}$ intermittently for remaining $t$.

Using these results we will provide another algorithm for copy-protected
generation. Let $q^{(1)},q^{(2)}$ be the models obtained using $D_{1},D_{2}$
respectively. And assume that we shard the total data in such a way that
$D_{1}$ contains the safe data, while $D_{2}$ contains the copy-protected
data. We let $q^{(1)}$ be our $\operatorname{safe}$-model. In practice, we
will have access to the score function or the MMSE denoiser,
$\widetilde{s}(x_{t},t,c;q^{(1)})$, $\widetilde{s}(x_{t},t,c;q^{(2)})$.

NAF $\Delta_{max}$ algorithm Let $J=\\{[t_{i},t_{i+1}]|t_{i+1}\leq
t_{i+2},i\in\\{0,2,4,\cdots,N\\},t_{0}\geq 0,t_{N+1}<\infty,N<\infty\\}$ be a
subset of disjoint time-intervals on the real line. Using the set $J$, let us
define a new distribution,

$\displaystyle\widetilde{q}(x_{0}|c,t)=q^{(1)}(x_{0}|c)\mathbbm{1}_{t\not\in
J}+q^{(2)}(x_{0}|c)\mathbbm{1}_{t\in J}$ (12)

This new distribution is a time-dependent, which essentially selects a
distribution at time $t$ to sample $x_{t}$. The benefit of such an approach is
that it enables the user to select one of the two model during backward
diffusion at each time-step, which is similar to [1] which has shown to
empirically improve generation quality. Towards this end we have the following
result,

######  Proposition 3.

Let $\widetilde{s}(x_{t},t,c;\widetilde{q})$ be the MMSE denoiser for Eq. 12,
then we can show that

$\displaystyle\widetilde{s}(x_{t},t,c;\widetilde{q})=\widetilde{s}(x_{t},t,c;q^{(1)})\mathbbm{1}_{t\not\in
J}+\widetilde{s}(x_{t},t,c;q^{(2)})\mathbbm{1}_{t\in J}$

This result states the fact that optimal MMSE denoiser for Eq. 12 will choose
one of the two denoisers depending on the time-step, where the choice of $J$
can be completely user dependent. Using these observations we propose interval
based CPR algorithm (CPR-Choose), Algorithm 2

######  Lemma 2.

Let $x_{0}$ be the output of Algorithm 2. Under certain regularity conditions
(see Supplementary Material), $x_{0}$ is $k_{c}-$NAF w.r.t.
$\operatorname{safe}$, $\mathcal{C}$, $\Delta_{\text{max}}$.

Figure 4: (a) Plot of the utility (generation quality) for increasing values
of copyright protection, on samples from the MS-COCO dataset. (b) The TIFA
score of CPR increases as the size of the retrieval dataset grows. (c)
Computational costs of CPR (ours) and CP-K[62] compared to the base model.

####  5.2.1 Time-Discretization

Often in practice we model the diffusion process using a discrete markov chain
[27, 58] whose continuous limit is SDE[60]. For discrete markov chains
discrete in $t$ we can denote the output of models $q^{(1)}$
($\operatorname{safe}$-model), $q^{(2)}$ using the entire trajectory,
$\\{x_{0},\cdots,x_{T}\\}$) [62]. The set of intervals $J$ becomes a set of
discrete time-steps. During backward diffusion, at each $t$ the user can use
one of the two models to generate the score for updating $x_{t}$. Depending on
the choice of $J$, we can generate completely safe images ($J$ to be empty) or
no protection ($J$ is the entire domain of $t$).This leads to two CPR-Choose
algorithms, depending on the choice of J.

##### CPR-Min

In this setting, we choose $J$ such that at each $t$, we choose the model with
the larger MSE, which can be considered as choosing the worst model at each
$t$. This will generate samples from a distribution which approximates the
minimum of the two distributions. Under certain conditions we can show that
this algorithm is NAF protected (In the appendix). This in intuitive because,
for time-stamps when we choose $q^{(1)}$ (which is the $\operatorname{safe}$
model), we incur no loss for $\Delta_{\text{max}}$, and it is only for the
remaining terms that we need to bound $\Delta_{\text{max}}$.

##### CPR-Alt

Similarly, we can choose $J$ to alternate between the two models by choosing
$q^{(2)}$ (private model) at regular intervals, like _e.g_. every
$\widetilde{t}$ steps, or in the most simplest case, in an alternating
fashion. Using this approach, we will only need to compute the
$\Delta_{\text{max}}$ at every $\widetilde{t}$ steps to bound $k_{c}$.

In our experiments, we will let $q^{(1)}$ be the $s_{\theta_{0}}(x_{t},t,c)$
which is trained on the safe-core data, while $q^{(2)}$ be the
$s_{\text{RAG}}(x_{t},t,c;D_{\text{private}})$ which uses the private data at
inference using retrieval.

##  6 Experiments

We use the Stable-Diffusion 2.1 model [49] as our safe base model, and use the
Stable-Diffusion unCLIP model [49, 47] (without the prior model) as our
retrieval-score model. Using the unCLIP model enables better control of the
generation with the retrieved images ${D_{\text{retr}}}\subset
D_{\text{private}}$. We use top 2k samples (based on the aesthetic score) from
MSCOCO [36] as our private data store and use the TIFA score [29] to measure
the text-image alignment and quality.

##### Improved text-to-image alignment

Retrieval is often used to improve the text-to-image alignment of the
diffusion model. In Tab. 1, we use TIFA benchmark to evaluate the alignment of
different methods. We observe that retrieving images from the data store
indeed improves the alignment from 81.4 to 83.17. Interestingly, CPR
regularizes the inference, resulting in even better TIFA (with protection).

##### Comparing privacy leakage

In Fig. 2, we plot the $\Delta_{\text{max}}$ (whose upper bound is $k_{c}$)
for various methods against $\operatorname{safe}$ (on images generated with
TIFA prompts). We use the control parameter $\hat{w}_{1}$ (Eq. 8 to vary the
retrieval contribution. We show that increasing $\hat{w}_{1}$, makes the model
generate more similar images to $D_{\text{private}}$, resulting in larger
$\Delta_{\text{max}}$ (log prob. ratio w.r.t. safe). This is unlike the
CP-$\Delta$ [62] which does not allow the user to tune the NAF constant
$k_{c}$. We also compare with CP-K [62], which uses rejection sampling on the
outputs generated by a Stable Diffusion model fine-tuned on the private
database $D_{\text{private}}$. We set k=1500, and observe that $\log
p(x|c)/\operatorname{safe}(x|c)$ is almost uniformly distributed, which
results in much slower (5-10x) rejection sampling for the same privacy level
as our CPR algorithms.

##### Concept similarity with CPR

In Fig. 3, we plot the CLIP-score between the image generated using TIFA
prompts (Syn in Fig. 3) and the input captions (Cap in Fig. 3), retrieved
images from $D_{\text{private}}$ (Ret in Fig. 3) respectively. We show that
CPR reduces the similarity between the synthesized images and the retrieved
images, while improving the similarity to the textual prompts. This implies
that CPR generates images corresponding to the concept present in the prompt
(with the help of the retrieved image), but ensures that the synthesized image
is different from the retrieved image (prevents copying/memorization).

##### Ablations

In Fig. 4 we provide additional experiments where we ablate the size of the
retrieval store, show the privacy utility trade-off, and compare the
computations cost of various methods.

##  7 Discussion and Limitations

##### Relation between $k_{c}$ and retrieval function

The NAF bound $k_{c}$ relates to the private data store through the retrieval
function, which in our case is the $L_{2}$ distance between the CLIP
embeddings. Functions that retrieve images which explain the concept
underlying the $c_{\text{test}}$ instead of its exact expression, can further
help in improving privacy.

##### Classifier-free guidance for privacy protected generation

We can redefine the expression in Eq. 9, to represent a more general form like
$p(x|c)\propto q_{1}^{\alpha}(x|c)q_{2}^{1-\alpha}(x|c)$, which when
substituted with appropriate $\alpha$ provides the expression for the classic
classifier free guidance (CFG) [26], which implies that replacing the marginal
in CFG with a safe model, and using the RAG model in place of the conditional
results in private generation with appropriate scaling of $k_{c}$. Thus CFG
with appropriate model selection can be considered a good candidate for NAF
generation.

##### Unlearning, adapters, and RAG

A direct consequence of copied generation is the request to remove the
appropriate training samples from the dataset (in our case
$D_{\text{store}}$). Such unlearning requests can be efficiently handled by
our CPR framework as it allows for cost free removal of private samples.
However, in certain settings, if the private data store contains out-of-
distribution (OOD) examples, simply using Eq. 8 may not be enough to obtain
high fidelity images. In such situations we may train separate adapters [30,
55, 13, 14, 28] corresponding to the OOD samples (a subset of
$D_{\text{store}}$. Hence at inference, we would first retrieve a private
adapter, and then a set of samples from $D_{\text{store}}$. Upon a forgetting
request, we discard both the adapter, and the samples in $D_{\text{store}}$.

##### Limitations

One of the major limitation of diffusion model based methods is the inability
to compute the exact probability values (this is not the case for auto-
regressive or flow based models). For instance, in Proposition 1,
$\hat{w_{0}}$, or even the computation of the true NAF parameter depends on
the actual probability values.

## References

  * Balaji et al. [2022] Yogesh Balaji, Seungjun Nah, Xun Huang, Arash Vahdat, Jiaming Song, Karsten Kreis, Miika Aittala, Timo Aila, Samuli Laine, Bryan Catanzaro, et al.  ediffi: Text-to-image diffusion models with an ensemble of expert denoisers.  _arXiv preprint arXiv:2211.01324_ , 2022.
  * Blattmann et al. [2022] Andreas Blattmann, Robin Rombach, Kaan Oktay, Jonas Müller, and Björn Ommer.  Retrieval-augmented diffusion models.  _Advances in Neural Information Processing Systems_ , 35:15309–15324, 2022.
  * Bourtoule et al. [2021] Lucas Bourtoule, Varun Chandrasekaran, Christopher A Choquette-Choo, Hengrui Jia, Adelin Travers, Baiwu Zhang, David Lie, and Nicolas Papernot.  Machine unlearning.  In _2021 IEEE Symposium on Security and Privacy (SP)_ , pages 141–159. IEEE, 2021.
  * Brooks et al. [2023] Tim Brooks, Aleksander Holynski, and Alexei A Efros.  Instructpix2pix: Learning to follow image editing instructions.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 18392–18402, 2023.
  * Carlini et al. [2021] Nicholas Carlini, Florian Tramer, Eric Wallace, Matthew Jagielski, Ariel Herbert-Voss, Katherine Lee, Adam Roberts, Tom Brown, Dawn Song, Ulfar Erlingsson, et al.  Extracting training data from large language models.  In _30th USENIX Security Symposium (USENIX Security 21)_ , pages 2633–2650, 2021.
  * Carlini et al. [2023] Nicolas Carlini, Jamie Hayes, Milad Nasr, Matthew Jagielski, Vikash Sehwag, Florian Tramer, Borja Balle, Daphne Ippolito, and Eric Wallace.  Extracting training data from diffusion models.  In _32nd USENIX Security Symposium (USENIX Security 23)_ , pages 5253–5270, 2023.
  * Chen et al. [2023] Jian Chen, Ruiyi Zhang, Tong Yu, Rohan Sharma, Zhiqiang Xu, Tong Sun, and Changyou Chen.  Label-retrieval-augmented diffusion models for learning from noisy labels.  _arXiv preprint arXiv:2305.19518_ , 2023.
  * Chen et al. [2014] Tianqi Chen, Emily Fox, and Carlos Guestrin.  Stochastic gradient hamiltonian monte carlo.  In _International conference on machine learning_ , pages 1683–1691. PMLR, 2014.
  * Chen et al. [2022] Wenhu Chen, Hexiang Hu, Chitwan Saharia, and William W Cohen.  Re-imagen: Retrieval-augmented text-to-image generator.  _arXiv preprint arXiv:2209.14491_ , 2022.
  * Cheng and Bartlett [2018] Xiang Cheng and Peter Bartlett.  Convergence of langevin mcmc in kl-divergence.  In _Algorithmic Learning Theory_ , pages 186–211. PMLR, 2018.
  * Dhariwal and Nichol [2021] Prafulla Dhariwal and Alexander Nichol.  Diffusion models beat gans on image synthesis.  _Advances in neural information processing systems_ , 34:8780–8794, 2021.
  * Du et al. [2023] Yilun Du, Conor Durkan, Robin Strudel, Joshua B Tenenbaum, Sander Dieleman, Rob Fergus, Jascha Sohl-Dickstein, Arnaud Doucet, and Will Sussman Grathwohl.  Reduce, reuse, recycle: Compositional generation with energy-based diffusion models and mcmc.  In _International Conference on Machine Learning_ , pages 8489–8510. PMLR, 2023.
  * Dukler et al. [2023a] Yonatan Dukler, Alessandro Achille, Hao Yang, Varsha Vivek, Luca Zancato, Ben Bowman, Avinash Ravichandran, Charless Fowlkes, Ashwin Swaminathan, and Stefano Soatto.  Introspective cross-attention probing for lightweight transfer of pre-trained models.  _arXiv preprint arXiv:2303.04105_ , 2023a.
  * Dukler et al. [2023b] Yonatan Dukler, Benjamin Bowman, Alessandro Achille, Aditya Golatkar, Ashwin Swaminathan, and Stefano Soatto.  Safe: Machine unlearning with shard graphs.  _arXiv preprint arXiv:2304.13169_ , 2023b.
  * Dwork [2006] Cynthia Dwork.  Differential privacy.  In _International colloquium on automata, languages, and programming_ , pages 1–12. Springer, 2006.
  * Erdogdu and Hosseinzadeh [2021] Murat A Erdogdu and Rasa Hosseinzadeh.  On the convergence of langevin monte carlo: The interplay between tail growth and smoothness.  In _Conference on Learning Theory_ , pages 1776–1822. PMLR, 2021\.
  * Fabbrini and Celeste [2020] Federico Fabbrini and Edoardo Celeste.  The right to be forgotten in the digital age: The challenges of data protection beyond borders.  _German law journal_ , 21(S1):55–65, 2020.
  * Gal et al. [2022] Rinon Gal, Yuval Alaluf, Yuval Atzmon, Or Patashnik, Amit H Bermano, Gal Chechik, and Daniel Cohen-Or.  An image is worth one word: Personalizing text-to-image generation using textual inversion.  _arXiv preprint arXiv:2208.01618_ , 2022.
  * Gandikota et al. [2023] Rohit Gandikota, Joanna Materzynska, Jaden Fiotto-Kaufman, and David Bau.  Erasing concepts from diffusion models.  _arXiv preprint arXiv:2303.07345_ , 2023.
  * Golatkar et al. [2020] Aditya Golatkar, Alessandro Achille, and Stefano Soatto.  Eternal sunshine of the spotless net: Selective forgetting in deep networks.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 9304–9312, 2020.
  * Golatkar et al. [2021] Aditya Golatkar, Alessandro Achille, Avinash Ravichandran, Marzia Polito, and Stefano Soatto.  Mixed-privacy forgetting in deep networks.  In _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ , pages 792–801, 2021.
  * Golatkar et al. [2022] Aditya Golatkar, Alessandro Achille, Yu-Xiang Wang, Aaron Roth, Michael Kearns, and Stefano Soatto.  Mixed differential privacy in computer vision.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 8376–8386, 2022.
  * Golatkar et al. [2023] Aditya Golatkar, Alessandro Achille, Ashwin Swaminathan, and Stefano Soatto.  Training data protection with compositional diffusion models.  _arXiv preprint arXiv:2308.01937_ , 2023.
  * Guu et al. [2020] Kelvin Guu, Kenton Lee, Zora Tung, Panupong Pasupat, and Mingwei Chang.  Retrieval augmented language model pre-training.  In _International conference on machine learning_ , pages 3929–3938. PMLR, 2020.
  * Hertz et al. [2022] Amir Hertz, Ron Mokady, Jay Tenenbaum, Kfir Aberman, Yael Pritch, and Daniel Cohen-Or.  Prompt-to-prompt image editing with cross attention control.  _arXiv preprint arXiv:2208.01626_ , 2022.
  * Ho and Salimans [2022] Jonathan Ho and Tim Salimans.  Classifier-free diffusion guidance.  _arXiv preprint arXiv:2207.12598_ , 2022.
  * Ho et al. [2020] Jonathan Ho, Ajay Jain, and Pieter Abbeel.  Denoising diffusion probabilistic models.  _Advances in neural information processing systems_ , 33:6840–6851, 2020.
  * Hu et al. [2021] Edward J Hu, Yelong Shen, Phillip Wallis, Zeyuan Allen-Zhu, Yuanzhi Li, Shean Wang, Lu Wang, and Weizhu Chen.  Lora: Low-rank adaptation of large language models.  _arXiv preprint arXiv:2106.09685_ , 2021.
  * Hu et al. [2023] Yushi Hu, Benlin Liu, Jungo Kasai, Yizhong Wang, Mari Ostendorf, Ranjay Krishna, and Noah A Smith.  Tifa: Accurate and interpretable text-to-image faithfulness evaluation with question answering.  _arXiv preprint arXiv:2303.11897_ , 2023.
  * Jia et al. [2022] Menglin Jia, Luming Tang, Bor-Chun Chen, Claire Cardie, Serge Belongie, Bharath Hariharan, and Ser-Nam Lim.  Visual prompt tuning.  In _European Conference on Computer Vision_ , pages 709–727. Springer, 2022.
  * Khandelwal et al. [2019] Urvashi Khandelwal, Omer Levy, Dan Jurafsky, Luke Zettlemoyer, and Mike Lewis.  Generalization through memorization: Nearest neighbor language models.  _arXiv preprint arXiv:1911.00172_ , 2019.
  * Kong et al. [2023a] Xianghao Kong, Rob Brekelmans, and Greg Ver Steeg.  Information-theoretic diffusion.  _arXiv preprint arXiv:2302.03792_ , 2023a.
  * Kong et al. [2023b] Xianghao Kong, Ollie Liu, Han Li, Dani Yogatama, and Greg Ver Steeg.  Interpretable diffusion via information decomposition.  _arXiv preprint arXiv:2310.07972_ , 2023b.
  * Kumari et al. [2023a] Nupur Kumari, Bingliang Zhang, Sheng-Yu Wang, Eli Shechtman, Richard Zhang, and Jun-Yan Zhu.  Ablating concepts in text-to-image diffusion models.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pages 22691–22702, 2023a.
  * Kumari et al. [2023b] Nupur Kumari, Bingliang Zhang, Richard Zhang, Eli Shechtman, and Jun-Yan Zhu.  Multi-concept customization of text-to-image diffusion.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 1931–1941, 2023b.
  * Lin et al. [2014] Tsung-Yi Lin, Michael Maire, Serge Belongie, James Hays, Pietro Perona, Deva Ramanan, Piotr Dollár, and C Lawrence Zitnick.  Microsoft coco: Common objects in context.  In _Computer Vision–ECCV 2014: 13th European Conference, Zurich, Switzerland, September 6-12, 2014, Proceedings, Part V 13_ , pages 740–755. Springer, 2014.
  * Lindquist and Picci [1979] Anders Lindquist and Giorgio Picci.  On the stochastic realization problem.  _SIAM Journal on Control and Optimization_ , 17(3):365–389, 1979.
  * Liu et al. [2022] Nan Liu, Shuang Li, Yilun Du, Antonio Torralba, and Joshua B Tenenbaum.  Compositional visual generation with composable diffusion models.  In _European Conference on Computer Vision_ , pages 423–439. Springer, 2022.
  * Liu et al. [2023] Tian Yu Liu, Aditya Golatkar, and Stefano Soatto.  Tangent transformers for composition, privacy and removal.  _arXiv preprint arXiv:2307.08122_ , 2023.
  * Lu et al. [2023] Shilin Lu, Yanzhu Liu, and Adams Wai-Kin Kong.  Tf-icon: Diffusion-based training-free cross-domain image composition.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pages 2294–2305, 2023.
  * Ma et al. [2023] Jian Ma, Junhao Liang, Chen Chen, and Haonan Lu.  Subject-diffusion: Open domain personalized text-to-image generation without test-time fine-tuning.  _arXiv preprint arXiv:2307.11410_ , 2023.
  * Min et al. [2023] Sewon Min, Suchin Gururangan, Eric Wallace, Hannaneh Hajishirzi, Noah A Smith, and Luke Zettlemoyer.  Silo language models: Isolating legal risk in a nonparametric datastore.  _arXiv preprint arXiv:2308.04430_ , 2023.
  * Nakashima [2020] Mika Nakashima.  The legal frameworks of the right to request the deletion of personal data in the eu, the us and japan and the right to be forgotten: A study focusing on search businesses.  In _Human-Centric Computing in a Data-Driven Society: 14th IFIP TC 9 International Conference on Human Choice and Computers, HCC14 2020, Tokyo, Japan, September 9–11, 2020, Proceedings 14_ , pages 29–40. Springer, 2020\.
  * Neal [2001] Radford M Neal.  Annealed importance sampling.  _Statistics and computing_ , 11:125–139, 2001.
  * Ram et al. [2023] Ori Ram, Yoav Levine, Itay Dalmedigos, Dor Muhlgay, Amnon Shashua, Kevin Leyton-Brown, and Yoav Shoham.  In-context retrieval-augmented language models.  _arXiv preprint arXiv:2302.00083_ , 2023.
  * Ramesh et al. [2021] Aditya Ramesh, Mikhail Pavlov, Gabriel Goh, Scott Gray, Chelsea Voss, Alec Radford, Mark Chen, and Ilya Sutskever.  Zero-shot text-to-image generation.  In _International Conference on Machine Learning_ , pages 8821–8831. PMLR, 2021.
  * Ramesh et al. [2022] Aditya Ramesh, Prafulla Dhariwal, Alex Nichol, Casey Chu, and Mark Chen.  Hierarchical text-conditional image generation with clip latents.  _arXiv preprint arXiv:2204.06125_ , 2022.
  * Roberts and Tweedie [1996] Gareth O Roberts and Richard L Tweedie.  Exponential convergence of langevin distributions and their discrete approximations.  _Bernoulli_ , pages 341–363, 1996.
  * Rombach et al. [2022a] Robin Rombach, Andreas Blattmann, Dominik Lorenz, Patrick Esser, and Björn Ommer.  High-resolution image synthesis with latent diffusion models.  In _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ , pages 10684–10695, 2022a.
  * Rombach et al. [2022b] Robin Rombach, Andreas Blattmann, and Björn Ommer.  Text-guided synthesis of artistic images with retrieval-augmented diffusion models.  _arXiv preprint arXiv:2207.13038_ , 2022b.
  * Ruiz et al. [2023] Nataniel Ruiz, Yuanzhen Li, Varun Jampani, Yael Pritch, Michael Rubinstein, and Kfir Aberman.  Dreambooth: Fine tuning text-to-image diffusion models for subject-driven generation.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 22500–22510, 2023.
  * Shan et al. [2023] Shawn Shan, Jenna Cryan, Emily Wenger, Haitao Zheng, Rana Hanocka, and Ben Y Zhao.  Glaze: Protecting artists from style mimicry by text-to-image models.  _arXiv preprint arXiv:2302.04222_ , 2023.
  * Sheynin et al. [2022] Shelly Sheynin, Oron Ashual, Adam Polyak, Uriel Singer, Oran Gafni, Eliya Nachmani, and Yaniv Taigman.  Knn-diffusion: Image generation via large-scale retrieval.  _arXiv preprint arXiv:2204.02849_ , 2022.
  * Shi et al. [2023] Weijia Shi, Sewon Min, Michihiro Yasunaga, Minjoon Seo, Rich James, Mike Lewis, Luke Zettlemoyer, and Wen-tau Yih.  Replug: Retrieval-augmented black-box language models.  _arXiv preprint arXiv:2301.12652_ , 2023.
  * Sohn et al. [2023] Kihyuk Sohn, Huiwen Chang, José Lezama, Luisa Polania, Han Zhang, Yuan Hao, Irfan Essa, and Lu Jiang.  Visual prompt tuning for generative transfer learning.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 19840–19851, 2023.
  * Somepalli et al. [2023a] Gowthami Somepalli, Vasu Singla, Micah Goldblum, Jonas Geiping, and Tom Goldstein.  Diffusion art or digital forgery? investigating data replication in diffusion models.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 6048–6058, 2023a.
  * Somepalli et al. [2023b] Gowthami Somepalli, Vasu Singla, Micah Goldblum, Jonas Geiping, and Tom Goldstein.  Understanding and mitigating copying in diffusion models.  _arXiv preprint arXiv:2305.20086_ , 2023b.
  * Song et al. [2020a] Jiaming Song, Chenlin Meng, and Stefano Ermon.  Denoising diffusion implicit models.  _arXiv preprint arXiv:2010.02502_ , 2020a.
  * Song and Ermon [2019] Yang Song and Stefano Ermon.  Generative modeling by estimating gradients of the data distribution.  _Advances in neural information processing systems_ , 32, 2019.
  * Song et al. [2020b] Yang Song, Jascha Sohl-Dickstein, Diederik P Kingma, Abhishek Kumar, Stefano Ermon, and Ben Poole.  Score-based generative modeling through stochastic differential equations.  _arXiv preprint arXiv:2011.13456_ , 2020b.
  * Vempala and Wibisono [2019] Santosh Vempala and Andre Wibisono.  Rapid convergence of the unadjusted langevin algorithm: Isoperimetry suffices.  _Advances in neural information processing systems_ , 32, 2019.
  * Vyas et al. [2023] Nikhil Vyas, Sham Kakade, and Boaz Barak.  Provable copyright protection for generative models.  _arXiv preprint arXiv:2302.10870_ , 2023.
  * Wang et al. [2023] Ruichen Wang, Zekang Chen, Chen Chen, Jian Ma, Haonan Lu, and Xiaodong Lin.  Compositional text-to-image synthesis with attention map control of diffusion models.  _arXiv preprint arXiv:2305.13921_ , 2023.
  * Welling and Teh [2011] Max Welling and Yee W Teh.  Bayesian learning via stochastic gradient langevin dynamics.  In _Proceedings of the 28th international conference on machine learning (ICML-11)_ , pages 681–688, 2011.
  * Wen et al. [2023] Yuxin Wen, Neel Jain, John Kirchenbauer, Micah Goldblum, Jonas Geiping, and Tom Goldstein.  Hard prompts made easy: Gradient-based discrete optimization for prompt tuning and discovery.  _arXiv preprint arXiv:2302.03668_ , 2023.
  * Yang and Wibisono [2022] Kaylee Yingxi Yang and Andre Wibisono.  Convergence in kl and rényi divergence of the unadjusted langevin algorithm using estimated score.  In _NeurIPS 2022 Workshop on Score-Based Methods_ , 2022.
  * Yasunaga et al. [2023] Michihiro Yasunaga, Armen Aghajanyan, Weijia Shi, Richard James, Jure Leskovec, Percy Liang, Mike Lewis, Luke Zettlemoyer, and Wen-tau Yih.  Retrieval-augmented multimodal language modeling.  2023\.
  * Yu et al. [2022] Jiahui Yu, Yuanzhong Xu, Jing Yu Koh, Thang Luong, Gunjan Baid, Zirui Wang, Vijay Vasudevan, Alexander Ku, Yinfei Yang, Burcu Karagol Ayan, et al.  Scaling autoregressive models for content-rich text-to-image generation.  _arXiv preprint arXiv:2206.10789_ , 2022.
  * Zhang et al. [2023] Mingyuan Zhang, Xinying Guo, Liang Pan, Zhongang Cai, Fangzhou Hong, Huirong Li, Lei Yang, and Ziwei Liu.  Remodiffuse: Retrieval-augmented motion diffusion model.  _arXiv preprint arXiv:2304.01116_ , 2023.

CPR: Retrieval Augmented Generation for Copyright Protection

Supplementary Material

##  Appendix A Proofs of the Propositions and Lemmas

###  A.1 Proposition 1

###### Proof.

of Proposition 1.

$\displaystyle\nabla_{x_{t}}\log p_{t}(x_{t}|c)$
$\displaystyle=\nabla_{x_{t}}\log\int
p_{t}(x_{t}|x_{0})\big{[}w_{0}p_{D}(x_{0}|c)+w_{1}p_{D_{\text{retr}}}(x_{0}|c)\big{]}dx_{0}$
$\displaystyle=\dfrac{1}{\int
p_{t}(x_{t}|x_{0})\big{[}w_{0}p_{D}(x_{0}|c)+w_{1}p_{D_{\text{retr}}}(x_{0}|c)\big{]}dx_{0}}\Big{[}\nabla_{x_{t}}\int
p_{t}(x_{t}|x_{0})w_{0}p_{D}(x_{0}|c)dx_{0}$ $\displaystyle+\nabla_{x_{t}}\int
p_{t}(x_{t}|x_{0})w_{1}p_{D_{\text{retr}}}(x_{0}|c)dx_{0}\Big{]}$
$\displaystyle=\dfrac{1}{p_{t}(x_{t}|c)}\Big{[}\nabla_{x_{t}}\int
p_{t}(x_{t}|x_{0})w_{0}p_{D}(x_{0}|c)dx_{0}+\nabla_{x_{t}}\int
p_{t}(x_{t}|x_{0})w_{1}p_{D_{\text{retr}}}(x_{0}|c)dx_{0}\Big{]}$
$\displaystyle=\dfrac{1}{p_{t}(x_{t}|c)}\Big{[}w_{0}\int
p_{t}(x_{t}|x_{0})p_{D}(x_{0}|c)dx_{0}\nabla_{x_{t}}\log\int
p_{t}(x_{t}|x_{0})p_{D}(x_{0}|c)dx_{0}$ $\displaystyle+w_{1}\int
p_{t}(x_{t}|x_{0})p_{D_{\text{retr}}}(x_{0}|c)dx_{0}\nabla_{x_{t}}\log\int
p_{t}(x_{t}|x_{0})p_{D_{\text{retr}}}(x_{0}|c)dx_{0}\Big{]}$
$\displaystyle=\dfrac{w_{0}\int
p_{t}(x_{t}|x_{0})p_{D}(x_{0}|c)dx_{0}}{p_{t}(x_{t}|c)}\nabla_{x_{t}}\log\int
p_{t}(x_{t}|x_{0})p_{D}(x_{0}|c)dx_{0}$ $\displaystyle+\dfrac{w_{1}\int
p_{t}(x_{t}|x_{0})p_{D_{\text{retr}}}(x_{0}|c)dx_{0}}{p_{t}(x_{t}|c)}\nabla_{x_{t}}\log\int
p_{t}(x_{t}|x_{0})p_{D_{\text{retr}}}(x_{0}|c)dx_{0}\ $

∎

###  A.2 Proposition 2

###### Proof.

of Proposition 2. Let $s_{\theta_{1}}(x_{t},t,c)\triangleq
s_{\theta_{0}+\Delta\theta_{1}}(x_{t},t,c)$ be the optimal solution to the
retrieval optimization problem. We use $\operatorname{CLIP}$ embeddings of the
retrieved images for generation, and bound its difference from the optimal.

$\displaystyle\|s_{\theta_{1}}(x_{t},t,c)-\hat{s}_{\theta_{0}}(x_{t},t,c_{\text{test}})\|$
$\displaystyle=\|s_{\theta_{1}}(x_{t},t,c)-s_{\theta_{0}}\Big{(}x_{t},t,\frac{1}{m}\sum_{x_{i}\in{D_{\text{retr}}}}\text{CLIP}(x_{i})\Big{)}\|$
$\displaystyle=\|s_{\theta_{1}}(x_{t},t,c)-s_{\theta_{0}}(x_{t},t,c)+s_{\theta_{0}}(x_{t},t,c)-s_{\theta_{0}}\Big{(}x_{t},t,\frac{1}{m}\sum_{x_{i}\in{D_{\text{retr}}}}\text{CLIP}(x_{i})\Big{)}\|$
$\displaystyle\leq\|s_{\theta_{1}}(x_{t},t,c)-s_{\theta_{0}}(x_{t},t,c)\|+\|s_{\theta_{0}}(x_{t},t,c)-s_{\theta_{0}}\Big{(}x_{t},t,\frac{1}{m}\sum_{x_{i}\in{D_{\text{retr}}}}\text{CLIP}(x_{i})\Big{)}\|$
$\displaystyle\leq\|s_{\theta_{0}+\Delta\theta_{1}}(x_{t},t,c)-s_{\theta_{0}}(x_{t},t,c)\|+\|s_{\theta_{0}}(x_{t},t,c)-s_{\theta_{0}}\Big{(}x_{t},t,\frac{1}{m}\sum_{x_{i}\in{D_{\text{retr}}}}\text{CLIP}(x_{i})\Big{)}\|$
$\displaystyle\leq
l_{\theta}\|\Delta\theta_{1}\|+l_{c}\|\frac{1}{m}\sum_{x_{i}\in{D_{\text{retr}}}}\text{CLIP}(x_{i})\|$
(13)

∎

###  A.3 Lemma 1

###### Proof.

of Lemma 1. [62] proved in Theorem 3.1, that sampling from Eq. 9 produces
samples which are copy-protected. In Algorithm 1, we sample using the score
function: $0.5(\nabla_{x_{t}}\log\int
q_{t}(x_{t}|x_{0})q^{(1)}(x|c)dx_{0}+\nabla_{x_{t}}\log\int
q_{t}(x_{t}|x_{0})q^{(2)}(x|c)dx_{0}$, which smoothly interpolates between
$\mathcal{N}(0,I)$ at $t=T$, and Eq. 9 at $t=0$. We need to show that using
Langevin based backward diffusion in Algorithm 1 indeed generates samples from
the desired distribution. The convergence results for Langevin dynamics have
been well studied in practice [44, 10, 16, 61], [48] has shown that Langevin
dynamics converge exponentially fast to the distribution estimated by the
gradients. Theorem 2.1 from [48] provides the result on the convergence of
Langevin dynamics in continuous time. For the sake of completeness we will
extend the results from [66] to show that Algorithm 1 generates samples from
Eq. 9.

We will re-state the assumptions from [66], for a distribution
$\nu_{t}(x_{t})$, and score estimator $s_{t}(x_{t})$. In our case
$\nu_{t}(x_{t})=0.5(\nabla_{x_{t}}\log\int
q_{t}(x_{t}|x_{0})q^{(1)}(x|c)dx_{0}+\nabla_{x_{t}}\log\int
q_{t}(x_{t}|x_{0})q^{(2)}(x|c)dx_{0})$, and $s_{t}(x_{t})$ is the average of
the safe diffusion flow and retrieval mixture score.

  1. 1.

LSI: For any probability distribution $\rho$, $C_{0}>0$,
$\int\rho_{t}\log\dfrac{\rho_{t}}{\nu_{t}}dx\leq\dfrac{1}{2C_{0}}\int\rho_{t}\Big{\|}\nabla\log\dfrac{\rho_{t}}{\nu_{t}}\Big{\|}dx$

  2. 2.

L-Smoothness: $-\log\nu_{t}$ is L-smooth

  3. 3.

Lipschitz score estimator: $s_{t}(x_{t})$ is $L_{s}$-lipschitz

  4. 4.

MGF error assumption:
$M_{t}=\sqrt{\mathbb{E}_{\nu_{t}}[\exp{r\|\nabla\log\nu_{t}(x_{t})-s_{t}(x_{t})\|^{2}}]}\leq\infty$

Then from Theorem 1 in [66] we know that

$\displaystyle\operatorname{KL}(\rho_{t}(x_{t})||\nu_{t}(x_{t}))\leq\exp{(-\dfrac{1}{4}C_{0}hN)}\operatorname{KL}(\rho_{t+1}(x_{t+1})||\nu_{t+1}(x_{t+1}))+C_{1}\epsilon_{t}+C_{2}M_{t}$
(14)

where $N$ is from the Algorithm 1, $C_{1}=O(\dfrac{dLL^{2}_{s}}{C_{0}})$,
$C_{2}=\dfrac{16}{3}$. Eq. 14 result is the obtain by running the inner loop
in Algorithm 1. Using the previous equation recursively for Algorithm 1, we
obtain that,

$\displaystyle\operatorname{KL}(\rho_{0}(x_{0})||\nu_{0}(x_{0}))$
$\displaystyle\leq\exp{(-\dfrac{1}{4}C_{0}hNT)}\operatorname{KL}(\rho_{T}(x_{T})||\nu_{T}(x_{T}))$
$\displaystyle+\sum_{t=1}^{T}\exp{(-\dfrac{1}{4}C_{0}hN(T-t))}\epsilon_{t}C_{1}+\sum_{t=1}^{T}\exp{(-\dfrac{1}{4}C_{0}hN(T-t))}M_{t}C_{1}$
(15)

where $\nu_{0}(x_{0})$ is the distribution in Eq. 9. Since we use DNNs with
sufficient capacity, we can assume that $M_{t}\rightarrow 0$, then as
$\epsilon_{t}\rightarrow 0$, and $T\rightarrow\infty$, we have that
$\operatorname{KL}(\rho_{0}(x_{0})||\nu_{0}(x_{0}))\rightarrow 0$, which
implies that Algorithm 1 generates samples from Eq. 9. ∎

###  A.4 Proposition 3

###### Proof.

of Proposition 3 Let
$\widetilde{s}(x_{t},t,c;\widetilde{q})=\mathbb{E}_{\widetilde{q}(x_{0}|x_{t},c)}\Big{[}\dfrac{x_{t}-\gamma_{t}x_{0}}{\sigma_{t}}\Big{]}$,
where $\widetilde{q}(x_{0}|c,t)=q^{(1)}(x_{0}|c)\mathbbm{1}_{t\not\in
J}+q^{(2)}(x_{0}|c)\mathbbm{1}_{t\in J}$.

$\displaystyle\widetilde{s}(x_{t},t,c;\widetilde{q})$
$\displaystyle=\mathbb{E}_{\widetilde{q}(x_{0}|x_{t},c)}\Big{[}\dfrac{x_{t}-\gamma_{t}x_{0}}{\sigma_{t}}\Big{]}$
$\displaystyle=\int\widetilde{q}(x_{0}|x_{t},c)\Big{[}\dfrac{x_{t}-\gamma_{t}x_{0}}{\sigma_{t}}\Big{]}dx_{0}$
$\displaystyle=\int\Big{(}q^{(1)}(x_{0}|c)\mathbbm{1}_{t\not\in
J}+q^{(2)}(x_{0}|c)\mathbbm{1}_{t\in
J}\Big{)}\Big{[}\dfrac{x_{t}-\gamma_{t}x_{0}}{\sigma_{t}}\Big{]}dx_{0}$
$\displaystyle=\int q^{(1)}(x_{0}|c)\mathbbm{1}_{t\not\in
J}\Big{[}\dfrac{x_{t}-\gamma_{t}x_{0}}{\sigma_{t}}\Big{]}dx_{0}+\int
q^{(2)}(x_{0}|c)\mathbbm{1}_{t\in
J}\Big{[}\dfrac{x_{t}-\gamma_{t}x_{0}}{\sigma_{t}}\Big{]}dx_{0}$
$\displaystyle=\widetilde{s}(x_{t},t,c;q^{(1)})\mathbbm{1}_{t\not\in
J}+\widetilde{s}(x_{t},t,c;q^{(2)})\mathbbm{1}_{t\in J}$

∎

###  A.5 Lemma 2

###### Proof.

of Lemma 2 We use Proposition 3 in Algorithm 2 for CPR-generation. Let
$q^{(1)}$ be the safe model in accordance with the assumptions in Sec. 5. To
show that Algorithm 2 is NAF, we need to bound $\Delta_{\text{max}}$. To show
that $\widetilde{q}(x_{0}|c,t)$ satisfies NAF we need to bound:

$\displaystyle\log\dfrac{\widetilde{q}(x_{0}|c)}{q^{(1)}(x_{0}|c)}$
$\displaystyle=\int\mathbb{E}_{\epsilon}\|\epsilon-\tilde{s}(x_{t},t,c;q^{(1)})\|^{2}\alpha^{\prime}(t)dt-\mathbb{E}_{\epsilon}\|\epsilon-\tilde{s}(x_{t},t,c;\widetilde{q})\|^{2}\alpha^{\prime}(t)dt$
$\displaystyle=\int\mathbb{E}_{\epsilon}\big{(}\|\tilde{s}(x_{t},t,c;q^{(1)})\|^{2}-\|\tilde{s}(x_{t},t,c;\widetilde{q})\|^{2}\big{)}\alpha^{\prime}(t)dt$
$\displaystyle=\sum_{j\in J}\int_{t\in
j}\mathbb{E}_{\epsilon}\big{(}\|\tilde{s}(x_{t},t,c;q^{(1)})\|^{2}-\|\tilde{s}(x_{t},t,c;\widetilde{q})\|^{2}\big{)}\alpha^{\prime}(t)dt$
$\displaystyle=\sum_{j=[t_{i},t_{i+1}]\in J}\int_{t\in
j}\mathbb{E}_{\epsilon}\big{(}\|\tilde{s}(x_{t},t,c;q^{(1)})\|^{2}-\|\tilde{s}(x_{t},t,c;q^{(2)})\|^{2}\big{)}\alpha^{\prime}(t)dt$
$\displaystyle=\sum_{j=[t_{i},t_{i+1}]\in J,t^{\prime}\in
j}\mathbb{E}_{\epsilon}\big{(}\|\tilde{s}(x_{t}^{\prime},t^{\prime},c;q^{(1)})\|^{2}-\|\tilde{s}(x_{t}^{\prime},t^{\prime},c;q^{(2)})\|^{2}\big{)}\alpha^{\prime}(t^{\prime})(t_{i+1}-t_{i})$
$\displaystyle=\sum_{j=[t_{i},t_{i+1}]\in J,t^{\prime}\in
j}\mathbb{E}_{\epsilon}\big{(}\|\tilde{s}(x_{t}^{\prime},t^{\prime},c;q^{(1)})\|^{2}-\|\tilde{s}(x_{t}^{\prime},t^{\prime},c;q^{(2)})\|^{2}\big{)}\alpha^{\prime}(t^{\prime})(t_{i+1}-t_{i})$
$\displaystyle\leq\text{max}_{t^{\prime}\in
J}\mathbb{E}_{\epsilon}\big{(}\|\tilde{s}(x_{t}^{\prime},t^{\prime},c;q^{(1)})\|^{2}-\|\tilde{s}(x_{t}^{\prime},t^{\prime},c;q^{(2)})\|^{2}\big{)}\alpha^{\prime}(t^{\prime})\sum_{j=[t_{i},t_{i+1}]\in
J,t^{\prime}\in j}(t_{i+1}-t_{i})$ $\displaystyle=k_{c}$ (16)

$J$ is our control parameter in CPR-Choose which controls $k_{c}$. If a
conservative approach is to be followed, then $J$ should be chosen such that
$\sum_{j=[t_{i},t_{i+1}]\in J,t^{\prime}\in j}(t_{i+1}-t_{i})$ is small, which
bounds $k_{c}$, the copy-protection leakage.

##### CPR-Min, CPR-Alt

In practice we discretize the time-steps of the backward diffusion process. In
this setting we protect the entire sequence $\\{x_{T},\cdots,x_{0}\\}$ instead
of protecting only the final prediction $x_{0}$. The probability of the
sequence $\\{x_{T},\cdots,x_{0}\\}$ is denoted by
$\widetilde{q}(x_{0}|x_{1},c)\cdots\widetilde{q}(x_{T-1}|x_{T},c)\widetilde{q}(x_{T}|c)$
using the chain rule of probability. To show that the method satisfies NAF, we
need to bound:

$\displaystyle\log\dfrac{\widetilde{q}(\\{x_{0},\cdots,x_{T}\\}|c)}{q^{(1)}(\\{x_{0},\cdots,x_{T}\\}|c)}$
$\displaystyle=\log\prod_{t}\dfrac{\widetilde{q}(x_{t}|x_{t+1},c)}{q^{(1)}(x_{t}|x_{t+1},c)}$
$\displaystyle=\log\prod_{t\in
J}\dfrac{q^{(2)}(x_{t}|x_{t+1},c)}{q^{(1)}(x_{t}|x_{t+1},c)}$
$\displaystyle=\sum_{t\in
J}\log\dfrac{q^{(2)}(x_{t}|x_{t+1},c)}{q^{(1)}(x_{t}|x_{t+1},c)}$
$\displaystyle=\sum_{t\in
J}\log\dfrac{\mathcal{N}(x_{t};\alpha_{1,t}x_{t+1}+\alpha_{2,t}\widetilde{s}(x_{t+1},t+1,c,q^{(2)}),\sigma^{2}_{t}I)}{\mathcal{N}(x_{t};\alpha_{1,t}x_{t+1}+\alpha_{2,t}\widetilde{s}(x_{t+1},t+1,c,q^{(1)}),\sigma^{2}_{t}I)}$
$\displaystyle=\sum_{t\in
J}\dfrac{1}{\sigma^{2}_{t}}\Big{(}\|x_{t}-\alpha_{1,t}x_{t+1}+\alpha_{2,t}\widetilde{s}(x_{t+1},t+1,c,q^{(1)})\|^{2}$
$\displaystyle-\|x_{t}-\alpha_{1,t}x_{t+1}+\alpha_{2,t}\widetilde{s}(x_{t+1},t+1,c,q^{(2)})\|^{2}\Big{)}$
$\displaystyle\leq\text{max}_{t}\Big{(}\|x_{t}-\alpha_{1,t}x_{t+1}+\alpha_{2,t}\widetilde{s}(x_{t+1},t+1,c,q^{(1)})\|^{2}$
$\displaystyle-\|x_{t}-\alpha_{1,t}x_{t+1}+\alpha_{2,t}\widetilde{s}(x_{t+1},t+1,c,q^{(2)})\|^{2}\Big{)}\sum_{t\in
J}\dfrac{1}{\sigma^{2}_{t}}$ $\displaystyle\leq b\sum_{t\in
J}\dfrac{1}{\sigma^{2}_{t}}$ $\displaystyle=k_{c}$ (17)

where $\alpha_{1,t},\alpha_{2,t},\sigma^{2}_{t}$ are the coefficients using
the backward diffusion depending on the choice of sampler, for eg. DDPM [27],
DDIM [58], Langevin dynamics [12], $b$ is an upper bound on the maximum
difference between the MSE for the two diffusion processes. Similar to the
previous derivation, $\sum_{t\in J}\dfrac{1}{\sigma^{2}_{t}}$ through $J$
provides a control knob to the user to control the $\Delta_{\text{max}}$ for
copy-protected generation. ∎

##  Appendix B Implementation Details

We use the Stable diffusion [49] and Stable diffusion unCLIP [47] model for
all the experiments in the paper. We use the Stable diffusion model to
generate safe flow corresponding to the safe distribution $q^{(1)}$, and the
Stable diffusion unCLIP model to generate the retrieval mixture score
$q^{(2)}$. We use classifier free guidance with a guidance scale of 7.5 in all
the results. We use 2k samples from the MSCOCO dataset [36] as our private
retrieval data store.

##  Appendix C Additional Figures

Figure 5:  Figure 6:  Figure 7: