## Reviewer 3BoX

**1. Can the defense methods work on longer datasets, such as Yelp?**

Yes, the table below, which shares the same settings as Table 2 in the manuscript, demonstrates that our CR-UTP method is also effective on the longer dataset such as Yelp dataset. The results indicate a consistent trend with those presented in Table 2. Our CR-UTP method showcases significant improvements over previous defenses. Specifically, on the Yelp dataset, it enhances the CACC and the PACC by 9.52% and 13.5%, respectively. Additionally, it reduces the ASR by 10.35%.

| | CACC | ASR | PACC |
|:------------:|:-----:|:---------:|:-----:|
| w/o Defense | 95.42 | 91.66 | 51.42 |
| Prior Defense (Our baseline) | 76.10 | 67.18 | 69.35 |
| Our CR-UTP | 85.62 | 56.83 | 82.85 |

**2. Why a mask ratio 70% is used, besides the implicit information in Figure 2?**

Defending against universal attacks necessitates a high mask ratio in the context of UTPs, where the presence of any UTP token in the masked input guarantees the attack's success. To ensure that the smoothed function g(x) consistently produces accurate results, the adversarial token must be masked with a probability greater than 50%, as detailed in Section 3.1 and illustrated in Figure 2. Moreover, a higher mask ratio can improve defense effectiveness, meaning lower ASR, but this also tends to diminish accuracy, as demonstrated in Figure 4. Adopting a 70% mask ratio manages to maintain accuracy without significant reduction. However, increasing the mask ratio further, for example, to 80%, results in a more noticeable decrease in clean accuracy of a 18.5% drop rate. Therefore, we have selected a 70% mask ratio as our default setting to achieve an effective defense while minimizing the impact on accuracy/utility.

**3. Clarify the metric Robust accuracy (Boa) in the cited paper [1] and the PACC. Please also show the original scores (no defense applied) in Table 1.**

The robust accuracy (Boa) used in [1] is the accuracy of a classifier achieved under a certain attack, which is defined in the section 4.3 in [1]. The PACC in our paper is same with robust accuracy (Boa) used in [1].

We include the original ASR scores, which were obtained without any defense, below. These scores will be incorporated into Table 1 in the upcoming version of the manuscript.

| | CACC | ASR | PACC |
|-------------|-------|-------|-------|
| TextFool | 92.69 | 91.87 | 8.13 |
| DeepWordBug | 92.69 | 93.04 | 6.96 |
| TrojLLM | 92.69 | 91.88 | 53.76 |

> [1] Zeng J, Xu J, Zheng X, et al. Certified robustness to text adversarial attacks by randomized [mask][J]. Computational Linguistics, 2023, 49(2): 395-427.

**4. Other improvements**

Thanks for pointing out the typos and providing valuable suggestions. We will fix them in the new manuscript.

## Reviewer VG4T
**1. Discuss the proposed methods' impact on inference efficiency**

The Superior Prompt Search is an offline process before online inference, thus the prompt search and generation phase does not impact the online inference. As mentioned in Section 4, the prompt search normally takes about 3.8 hours to train the policy model using only one single Nvidia GeForce RTX-3090 GPU. Once the policy model is trained, one could reuse it to generate multiple superior prompts in several seconds. The superior prompt we utilize in our paper is short and effective, comprising up to 5 tokens, resulting in an overhead (from appending the prompt compared to not using one) of no more than 10% for both the SST and AgNews datasets. Additionally, datasets with longer texts (Yelp) exhibit much lower overhead ratios, i.e., less than 5%. We highlight that superior prompt significantly enhances defense effectiveness. As the Table 2 shows, on the SST-2 dataset, it yields an improvement of over 14% in clean accuracy and a reduction of more than 21% in ASR compared to our baseline.

The generation of ensemble prompts runs parallel to the search for the superior prompt, occurring before the online inference phase. The certified efficiency of this method is closely linked to the number of inference executions, which is a product ($kn$) of the ensemble number ($k$) and the sampling number ($n$). To maintain efficiency, one could reduce the sampling number ($n$) when employing ensemble prompts ($k>1$) to keep a similar or the same product $kn$. For instance, sampling a single superior prompt 5000 times may yield a certified accuracy of 54.5%; however, an ensemble of 5 superior prompts (k=5) requires only 1000 samplings to reach a certified accuracy of 58.1%. For the defense inference against a specific attack, the number of $n$ can be much smaller, e.g., 50-100, for efficiency consideration. Also, We underscore the efficiency of prompt ensembling over model ensembling, owing to the prompt generation's speed and low memory footprint, as opposed to the more resource-intensive generation and memory demands of model ensembling.

We will incorporate the efficiecy results and discussion into the upcoming manuscript.

**2. Generality on other models like Llama and GPT-3.5, other NLP tasks**

We use the below table to demonstrate our CR-UTP also works on large models such as Llama2-7b and GPT-3.5 against UTP attack TrojLLM. CR-UTP outperforms our baseline defense in efficacy. For instance, on both the Llama2-7b and GPT-3.5 models, our CR-UTP method enhances CACC by approximately 10% compared to our baseline, while achieving a reduction in ASR of more than 35%.

| | | Llama2-7b | | | GPT-3.5 | |
|:------------:|:-----:|:---------:|:-----:|:-----:|:-------:|:-----:|
| | CACC | ASR | PACC | CACC | ASR | PACC |
| w/o defense | 90.40 | 88.17 | 53.82 | 92.01 | 96.88 | 51.94 |
| Our baseline | 73.89 | 83.14 | 55.03 | 75.34 | 86.72 | 56.19 |
| CR-UTP | 84.68 | 51.47 | 72.95 | 85.32 | 50.75 | 74.86 |

Exploring the generality of certified robustness to other non-classification NLP tasks is intriguing. However, current methods based on random smoothing are limited to classification tasks, as they need a definite output for integration over a smoothed area around the input when calculating the probability in Equation 2, Section 3.1. Addressing certified robustness against Universal Text Perturbations in classification remains a significant challenge. This paper focuses on developing methods to overcome these obstacles, with extending our approach to generative tasks being an interesting direction for future research.

**3. Compare with other advanced defense methods such as adversarial training.**

Empirical defense methods, like adversarial training, struggle against adaptive attacks due to their unpredictable and dynamic nature. In contrast, certified robustness provides a guaranteed defense against such attacks. The distinctions between these approaches are detailed in Section 2 starting from line 146.

We also compare the empirical defense effects of adversarial training and our CR-UTP in the below Table. Our CR-UTP significantly reduces the ASR by over 30% while maintaining similar accuracy, outperforming adversarial training. CR-UTP consistently defends against various adversarial attacks, such as TrojLLM and TextFool, unlike adversarial training, which shows inconsistent defense effectiveness. For instance, adversarial training effectively reduces ASR from 91.88% to 80.68% for attacks it was trained against (TrojLLM), but it provides minimal defense against different attacks (TextFool), only reducing ASR from 92.27% to 91.13%.

| | | TrojLLM | | | TextFool | |
|:-----------------------:|:-----:|:-------:|:-----:|:-----:|:--------:|:-----:|
| | CACC | ASR | PACC | CACC | ASR | PACC |
| w/o defense | 92.69 | 91.88 | 53.76 | 92.69 | 92.27 | 8.13 |
| adv. training on TrojLLM | 85.94 | 80.68 | 59.82 | 85.94 | 91.13 | 8.81 |
| CR-UTP | 85.7 | 50.55 | 73.04 | 85.28 | 37.39 | 62.61 |

**4. Clarify UTPs and ISIPs, Explore more UTPs and Show Results**

The term "Input-Specific Text Perturbations (ISTPs)" refers to adversarial perturbations adapted to each input sample, whereas "Universal Text Perturbations (UTPs)" denote perturbations that are universal across all input samples (one perturbation works for all samples). These definitions will be further clarified in the current Section 2.

In our manuscript, we exemplify UTP with TrojLLM, and ISTP with TextFool and DeepWordBug. To assess our method's adaptability to various UTPs, we also evaluated CR-UTP against UAT[1] in addition to TrojLLM in the below table. The findings reveal CR-UTP's superior defense capability compared to our baseline. CR-UTP significantly reduces the ASR from 96.85% to 50.63%, while our baseline achieves a reduction only to 79.92%. Furthermore, CR-UTP exhibits higher CACC and PACC than our baseline. Our CR-UTP shows the first effective and certified defense against UTPs.

| | CACC | ASR | PACC |
|:------------:|:-----:|:-----:|:-----:|
| w/o defense | 92.48 | 96.85 | 52.97 |
| Our baseline | 80.75 | 79.92 | 60.18 |
| CR-UTP | 85.53 | 50.63 | 75.92 |

> [1] Wallace E, Feng S, Kandpal N, et al. Universal Adversarial Triggers for Attacking and Analyzing NLP.

## Reviewer i5iH
**1. Study the proposed method on more models**

The below table shows that our CR-UTP also works on larger models such as Llama2-7b and GPT-3.5. The experiments are conducted on SST-2 dataset against UTP attack, TrojLLM. CR-UTP outperforms our baseline defense in efficacy. For instance, on both the LLama2-7b and GPT-3.5 models, our CR-UTP method enhances CACC by approximately 10% compared to our baseline, while achieving a reduction in ASR of more than 35%.

| | | LLama2-7b | | | GPT-3.5 | |
|:------------:|:-----:|:---------:|:-----:|:-----:|:-------:|:-----:|
| | CACC | ASR | PACC | CACC | ASR | PACC |
| w/o defense | 90.4 | 88.17 | 53.82 | 92.01 | 96.88 | 51.94 |
| Our baseline | 73.89 | 83.14 | 55.03 | 75.34 | 86.72 | 56.19 |
| CR-UTP | 84.68 | 51.47 | 72.95 | 85.32 | 50.75 | 74.86 |

**2. More details about training time and computational complexity**

The Superior Prompt Search is an offline process before online inference, thus the prompt search and generation phase do not impact the online inference. As mentioned in Section 4 (line 533), the prompt search normally takes about 3.8 hours to train the policy model using only one single Nvidia GeForce RTX-3090 GPU. Once the policy model is trained, one could reuse it to generate multiple superior prompts in several seconds. The generation of ensemble prompts runs parallel to the search for the superior prompt, occurring before the online inference phase. Also, We underscore the efficiency of prompt ensembling over model ensembling, owing to the prompt generation's speed and low memory footprint, as opposed to the more resource-intensive generation and memory demands of model ensembling. We will clarify the training details in the upcoming manuscript.

**3. The difference between Superior Prompt Search and RL-based approach in TrojLLM[1]**

Although both of CR-UTP and TrojLLM use the RL framwork proposed in RL-Prompt[2] to search prompt, their goals and designs are significantly different. Compared to CR-UTP's goals and designs, TrojLLM[1]'s goal and design are simpler and less challenging. TrojLLM aims to identify a harmful trigger that alters the model's predictions. Its objective is captured by Equation 4 in [1], employing a reward function that grants positive reinforcement for incorrect classifications and penalizes correct ones, as detailed in Equation 5 in [1]. However, for the Superior Prompt Search in CR-UTP, the target is to identify an optimized prompt $p_s$ that augments the model prediction on even token-masked inputs. How to model the objective and make it compatible with RL framework is non-trivial. Our strategy is to boost the model's accuracy $\mathcal{ACC}(f(p_s, \hat{x}_i), y_i)$ on inputs $\hat{x}_i$ that have undergone random word masking. We model it in Equation 3.

Another problem is how to design reward function to optimize the PLM's accuracy on masked sentences. We introduce the Masked Sentence Accuracy Reward (MSAR) mechanism in Equation 4, wherein a masked input that leads to correct model operation yields a positive reward, while incorrect outcomes result in a negative reward. However, this reward mechanism itself does not guarantee high accuracy on masked inputs. This is because a masked input with a high mask ratio may not retain sufficient information to ensure accurate model predictions, despite the guidance provided by the MSAR reward function. To address the challenge of information loss, we propose using the predictions from unmasked sentences as a supervisory signal. This approach helps align the predictions of masked sentences with those of their unmasked counterparts. Consequently, we introduce an additional reward function, known as the Predictive Distribution Alignment Reward (PDAR), to facilitate this process. It is designed to minimize the KL divergence between the predictive distributions of the vanilla prompt on unmasked sentences and the superior prompt on their masked equivalents. Our prompt search reward is the combination of MSAR and PDAR shown in the Line 377. The combination of $R_{MSAR}$ and $R_{PDAR}$ rewards yields an improvement of more than 2% in accuracy compared to using only one reward.

> [1] Xue J, Zheng M, Hua T, et al. Trojllm: A black-box trojan prompt attack on large language models[J]. Advances in Neural Information Processing Systems, 2024, 36.
> [2] Deng M, Wang J, Hsieh C P, et al. RLPrompt: Optimizing Discrete Text Prompts with Reinforcement Learning[C]//Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing. 2022: 3369-3391.

**4. Other Comments: Consider adding a table with the mathematical symbols used across the paper and the definitions.**

Thanks for the suggestion. We will add this table to increase the readibility.