Accelerating Greedy Coordinate Gradient and General Prompt Optimization via Probe Sampling

Authors: yiran  zhao
wenyue  zheng
tianle  cai
xuan long do
kenji  kawaguchi
anirudh  goyal
michael  qizhe shieh
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 05:48:23

Abstract: Safety of Large Language Models (LLMs) has become a central issue given their rapid progress and wide applications. Greedy Coordinate Gradient (GCG) is shown to be effective in constructing prompts containing adversarial suffixes to break the presumingly safe LLMs, but the optimization of GCG is time-consuming and limits its practicality. To reduce the time cost of GCG and enable more comprehensive studies of LLM safety, in this work, we study a new algorithm called $\texttt{Probe sampling}$ to accelerate the GCG algorithm. At the core of the algorithm is a mechanism that dynamically determines how similar a smaller draft model's predictions are to the target model's predictions for prompt candidates. When the target model is similar to the draft model, we rely heavily on the draft model to filter out a large number of potential prompt candidates to reduce the computation time. Probe sampling achieves up to $5.6$ times speedup using Llama2-7b-chat and leads to equal or improved attack success rate (ASR) on the AdvBench. Furthermore, probe sampling is also able to accelerate other prompt optimization techniques and adversarial attack methods, leading to acceleration of $1.8\times$ for AutoPrompt, $2.4\times$ for APE and $2.4\times$ for AutoDAN.

Main paper: 
 introduction: 
 Ensuring the safety of Large Language Models (LLMs) (Brown et al., 2020; Chowdhery et al., 2023; Touvron et al., 2023; Jiang et al., 2023 ) has become a central theme of research. Despite continuous efforts, LLMs are prone to generate objectionable contents in various scenarios including using an adversarial suffix (Zou et al., 2023) , further finetuning (Qi et al., 2024; Lermen and Rogers-Smith, 2024) , ciphering (Yuan et al., 2024b) and multilingual settings (Deng et al., 2024) . Among effective LLM adversarial attack works, Greedy Coordinate Gradient (GCG) (Zou et al., 2023) present a general and universal method as briefly illustrated in Figure 1 .Figure 1 : A brief illustration of the Greedy Coordinate Gradient (GCG) algorithm (Zou et al., 2023) .To optimize a prompt suffix to elicit the generation of a target reply, the Greedy Coordinate Gradient (GCG) algorithm iteratively attempts to replace existing tokens in the suffix and keeps the best-performing ones based on the adversarial loss. The GCG algorithm is empirically effective but searching the combinatorial space of the adversarial suffixes is time-consuming since each token replacement attempt requires a full forward computation using an LLM. This hinders us from using the algorithm to fully explore the safety properties of LLMs such as finding potentially harmful queries comprised of natural sentences. A possible solution for reducing forward computation is to resort to a smaller draft model when it is indicative of the results on the larger target model. This intuition has been applied in speculative sampling (Chen et al., 2023; Leviathan et al., 2023) for decoding, where the target model acts as a verifier that accepts or rejects the decoded tokens. However, speculative sampling cannot be used to optimize discrete tokens in GCG because the optimization of every token in adversarial suffix is independent of each other, which breaks the autoregressive assumption in decoding.Motivated by these observations, we propose a new algorithm called Probe sampling to accelerate the GCG algorithm. Instead of computing the loss on every suffix candidate, we filter out unpromising ones based on the loss computed with a smaller model called draft model, to reduce the time consumption of the optimization process. Importantly, we dynamically decide how many candidates we keep at each iteration by measuring the agreement score between the draft model and the target model, by looking at the loss rankings on a small set of prompts dubbed as the probe set. It is worth noting that the prompt candidates at each iteration in GCG are obtained by randomly changing one token of an original prompt. As a result, the agreement score is adaptive to the original prompt. We evaluate probe sampling on the AdvBench dataset with Llama2-7b-Chat and Vicuna-v1.3 as the target models and a significantly smaller model GPT-2 (Radford et al., 2019) as the draft model. Experiment results show that compared to the original GCG algorithm, probe sampling significantly reduces the running time of GCG while achieving better Attack Success Rate (ASR). Specifically, with Llama2-7b-Chat, probe sampling achieves 3.5 times speedup and an improved ASR of 81.0 compared to GCG with 69.0 ASR. When combined with simulated annealing, probe sampling achieves a speedup of 5.6 times with a better ASR of 74.0. Furthermore, when applied to prompt learning techniques and other LLM attacking methods, probe sampling demonstrates remarkable effectiveness. Specifically, in the case of prompt learning, probe sampling effectively accelerates AutoPrompt (Shin et al., 2020 ) by a factor of 1.8. Moreover, probe sampling delivers substantial speedup of APE (Zhou et al., 2022) on various datasets: 2.3× on GSM8K, 1.8× on MMLU and 3.0× on BBH. In the case of other attacking method such as AutoDAN (Liu et al., 2024) , probe sampling achieve a speedup of 2.3× and 2.5× on AutoDAN-GA and AutoDAN-HGA respectively.Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?Answer: [Yes] Justification: In the abstract and Section 1 (Introduction).Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
background: greedy coordinate gradient: 
 The overall optimization objective of GCG can be denoted by a simple log likelihood lossEQUATIONwhere x is a prompt that contains a harmful user query such as "Tell me how to build a bomb", y is the target sentence "Sure, here is how to build a bomb", and s is the adversarial suffix that is optimized to induce the generation of y. p is the probability of a sentence output by a LLM. This objective can be decomposed into the summation of the negative log likelihood of individual tokens in the target sentence like a typical language modeling objective. s is set to be a fixed length string in the GCG algorithm.The optimization of the adversarial suffix s is a non-trivial problem. Prior works (Guo et al., 2021; Wen et al., 2024) based on Gumbel-Softmax (Jang et al., 2016; Maddison et al., 2022) and soft prompt tuning (Lester et al., 2021) have achieved limited success, probably because the LLMs are well-aligned and the exceptionally large models magnifies the difference between a discrete choice and its continuous relaxations.Instead, GCG adopts a greedy search algorithm based on the gradient. In each iteration, it computes L(ŝ i ) for B suffix candidates ŝ1 , • • • , ŝB and keeps the one with the best loss. The B candidates are obtained by randomly changing one token from the current suffix s and replacing it with a randomly sampled token using the top K tokens. For example, suppose we change the token at position j, we first compute the gradient -∇ es j L(s) with respect to the one-hot vector e sj and obtain the top K tokens that have the largest gradient. The gradient information is by no means an accurate estimation of the resulting loss because of the gap between the continuous gradient information and the discrete one-hot vector denoting the choice of a token, so we need to check if the resulted new suffix ŝi leads to a lower loss L(ŝ i ).To obtain the B candidates, one just needs to perform one forward pass and one backward pass. But to compute the loss for the B candidates, one needs to perform B forward passes. In GCG, B is set to 512 for optimal performance, making the loss computation the most time-consuming part. As such, we focus on reducing the time cost of the loss computation of the B candidates in this work.Overview. As mentioned earlier, the most time consuming part in the GCG algorithm is the loss computation on B suffix candidates ŝ1 , • • • , ŝB . As shown in speculative sampling (Chen et al., 2023; Leviathan et al., 2023) , the speculated results using a smaller draft model can be helpful in reducing the computation with a large target model. The original speculative sampling is created to accelerate decoding so it isn't directly applicable here. But the intuition of relying a weaker draft model is obviously useful for negative log likelihood loss computation. Applying the intuition to the problem at hand, we can filter out the suffix candidates that the draft model finds to be unpromising, since the goal is to find the candidate that has the lowest loss with the target model.In addition, a unique structure in the GCG algorithm is that all the suffix candidates are based on changing one token of the original suffix s. As a result of this locality property, it is not unreasonable to assume that one can determine how much they agree on the B candidates based on their agreement on a subset of the B candidates. If the two models agree, we can choose to safely rely on the draft model and filter out more candidates.Based on these intuitions, we design the Probe sampling algorithm as follows: (i) probe agreement between the target model and the draft model to determine the size of the filtered set; (ii) rank candidates using the draft model and obtain the filtered set; (iii) pick the best candidate from the filtered set using the target model.Algorithm description. For the first step, specifically, we sample a probe set comprised of k candidates s1 , • • • , sk and compute their losses using the draft model and the target model and obtainL draft (s 1 ), • • • , L draft (s k ) and L target (s 1 ), • • • , L target (s k ).Then we measure the probe agreement score as the Spearman's rank correlation coefficient (Zar, 2005) between the two results as the agreement score. The probe agreement score α is computed asEQUATIONwhere d i is the distance between the ranks of suffix si in the two results. For example, d i = 4 if the suffix si is ranked as number 6 and number 2 for its losses computed from the draft model and the target model. The agreement score α falls into [0, 1] with 1 meaning a full agreement and 0 indicating a non-agreement. We use the rank agreement because it is more robust to the specific values of the resulting loss when measured on drastically different LLMs. s ′ = argmin{L target (s i ), L target (ŝ i )} Output: s ′After obtaining the agreement score, we keep (1 -α) * B/R candidates where (1 -α) * B means that the filtered set size is a scale-down of the previous batch size B and R is a hyperparameter that determines a further scale down. When α is close to 0, meaning little agreement between the two models, we will use a filtered set size of B/R. When α goes to 1, we almost filter out most of the candidates. With the filtered size determined, we can readily rank the candidates according to the draft model and filter the ones with higher losses. Finally, we evaluate the final loss on the filtered set using the target model and select the best candidate.Details. At first glance, probe sampling involves extra computation but it actually achieves effective acceleration. For computing the losses on the probe set using both the draft model and the target model, the size of the probe set can be set to be relatively small, so it would not add too much to the total time cost. The ranking procedure involves sorting on CPU, but luckily the probe set is small enough that this doesn't become a bottleneck. And the loss computation using the draft model on the whole candidate set is relatively cheap because of draft model's small size. These two operations can also be parallelized on GPU. On the plus side, we are able to avoid computing the loss using the big target model on many candidates that are filtered out. As we will show in the experiments, this approach achieves significant speedup measured by both running time and #FLOPs.An alternative to computing agreement on the spot is to measure the agreement score on a predetermined set of candidates and use a fixed agreement score for all the suffixes. This would save the time used to measure agreement for each candidate set. However, as we will show in the experiment, this approach does not work so well in terms of speedup. Our intuition is that one can squeeze the time cost more effectively if the agreement is measured accurately, and an adaptive agreement score is more accurate than an one-size-fits-all score. The plausibility of the adaptive score comes back to the locality property that we discussed earlier. Given a specific candidate set, one can accurately estimate the agreement because all the suffixes in this candidate set are similar to a large extent. However, given another candidate set altered from a different suffix, the agreement of the draft model and the target model can be widely different.In practice, we adopted two small changes in our implementation. First, we do not have a separate step to compute the loss of the probe set candidates using the draft model, since we need to compute the loss on all candidates for filtering purposes. We simply get the numbers from the losses on the whole candidate set. Second, to get the best candidate for the final result, we also look at the losses on the probe set, since the target model is evaluated on the probe set. Ideally, the candidates in the probe set should be in the filtered set if they achieve a low loss. However, it also does not hurt to look at the best candidate in the probe set in case it is not included in the filtered set. The overall algorithm is further illustrated in Algorithm 1, and the corresponding implementation is shown in Appendix A. We also test simulated annealing (Pincus, 1970 ) that provides complementary benefit to our algorithm.Although prompt sampling was designed to accelerate GCG, the general idea of reducing forward computation can be applied on other prompt optimization methods, where there is usually a process of sampling prompt candidates and evaluating their performances. To see whether probe sampling can effectively accelerate other methods, we also apply probe sampling to two prompt learning methods AutoPrompt (Shin et al., 2020) and APE (Zhou et al., 2022) . In addition, we apply probe sampling on AutoDAN (Liu et al., 2024) , a genetic algorithm that can find natural jailbreak prompts.Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [Yes] Justification: After Section 5 (Conclusion)Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
experiment: 
 In this section, we evaluate the proposed method on its efficacy and the important factors through extensive studies.Settings. Following the original GCG paper, we conduct experiments on the first 100 instances of AdvBench (Zou et al., 2023) , which are divided into two parts, 500 harmful strings and 500 harmful human behaviors. We test open-source LLMs that have been specifically fine-tuned with respect to safety, including Llama2-chat-7b (Touvron et al., 2023) and Vicuna-7b (Zheng et al., 2023) . In the case of draft models, in our main experiments, we use a much smaller model GPT-2 (Radford et al., 2019) . Similarly, when applying probe sampling to AutoDAN, we use Llama2-7b-chat as the target model and GPT-2 as the draft model. For AutoPrompt, we follow their original setting, which uses RoBERTa-large (Liu et al., 2019) as the target model and tests on SST-2 (Socher et al., 2013) for sentiment analysis and SICK-E (Marelli et al., 2014) for natural language inference. We use the RoBERTa-base model as the draft model. In the case of APE, we conduct the experiments on three widely used benchmarks GSM8K (Cobbe et al., 2021) , BBH (Suzgun et al., 2023) , and MMLU (Hendrycks et al., 2020) . For these experiments, we use Vicuna-7b-v1.5 as the target model and GPT-2 as the draft model.Evaluation. Following (Zou et al., 2023) , we use Attack Success Rate (ASR) as the evaluation metric for GCG and AutoDAN, which is defined as the percentage of inputs that successfully lead LLMs to generate harmful outputs. An output is determined to be harmful if it does not match with rejection phrases, such as "I'm sorry", "I apologize" and "As an". This is not a perfect measurement but works relatively well in practice since LLMs are trained to reject harmful replies. It is also easy to measure and interpret. For prompt learning methods tested on other tasks, we employ Accuracy (Acc) as the metric. The processing time is determined as the average time used for each iteration across all input samples and all iterations. In all experiments, we use 1 NVIDIA A100 GPU with 80GB memory unless mentioned otherwise.Hyperparameters. To determine the hyperparameters for probe sampling, including probe set size k, filtered set size reduction hyperparameter R, we construct a validation set of size 100 from AdvBench by random sampling in the 400 instances different from the test set. We follow (Zou et al., 2023) for the hyperparameters used in the original algorithm such as the size of the candidate set B. We provide detailed analysis of hyperparameters in Section 3.4. When we combine probe sampling with simulated annealing, we follow the same procedure to select hyperparameters. We use the same number of optimization steps 500 as in GCG throughout the paper.Acceleration results. As shown in Table 1 , probe sampling achieves a speedup of 5.6 times and 6.3 times on Human Behaviors and Human Strings with Llama2 when combined with simulated annealing. Probe sampling achieves a speedup of 3.5 and 4.1 times alone. With Vicuna, we achieve an overall speedup of 3.2 and 3.6 respectively on the two datasets. We also measure the #FLOPs for different settings and found that the speedup results reflects in the reduction of #FLOPs. For example, with Llama2, the #FLOPs reduction is 202.3T/32.3T = 6.3 times and 198.4T/31.2T = 6.4 times on the two sets, which is close to the actual speedup results. This also shows that our algorithm results in little overhead with the introduced new procedures. It is worth noting that simulated annealing also achieves decent acceleration and is complementary to our acceleration results.GCG results. Interestingly, we achieve a better ASR score than the GCG algorithm although technically acceleration introduces noise to the algorithm. For instance, with Llama2, we improve the ASR from 57.0 to 64.0 on Human Strings and from 84.0 to 91.0 on Human Behaviors. We hypothesize that the improvement comes from the randomness added to the GCG algorithm based on greedy search over a single objective. Introducing randomness and noise has been seen as one of the advantages of SGD over full batch training. In contrast, simulated annealing only leads to comparable ASR when applied on GCG.Transferability Table 2 shows probe sampling's transferability across draft models based on Llama2-7b-Chat to various target models. We find that it maintains transferability when using draft models like GPT-2 and SheardLlaMa, which preserve the original ASR of plain GCG. However, draft models that significantly degrade initial performance, such as Flan-T5, impair transferability. Table 3 examines probe sampling transferability across filtered set sizes. Results align with prior findings: probe sampling minimally impacts transferability with appropriate parameters but decreases performance when Llama2-7b-chat's direct ASR is low such as R = 64.Results on AutoDAN, Autoprompt and APE. Table 5 demonstrates the effective acceleration of AutoPrompt through the implementation of probe sampling, resulting in a speedup of 1.79× on SST-2 and 1.83× on SICK-E. Importantly, this acceleration is achieved without compromising performance, as evidenced by the minimal changes in accuracy from 91.4 to 90.6 on SST-2 and from 69.3 to 68.9 on SICK-E. Furthermore, the application of probe sampling to APE, as presented in Table 6 , results in significant speed improvements, with a speedup of 2.3× on GSM8K, 1.8× on MMLU, and 3.0× on BBH. Similarly, these speed enhancements do not compromise the performance of APE.In addition, we implement probe sampling on another jailbreak method, AutoDAN. The detailed results can be found in Table 4 . Our findings indicate that probe sampling can achieve a speedup of 2.3× for AutoDAN-GA and 2.5× for AutoDAN-HGA, while minimally affecting its performance. These results demonstrate the effectiveness of our method in not only accelerating GCG but also its applicability to general prompt optimization methods and other LLM attack methods.Memory allocation. We evaluate whether probe sampling uses more memory because of the use of an extra model. In Figure 3 , we show the memory usage of GCG, probe sampling with and without annealing using either Llama2-7b-chat and Vicuna-7b-v1.3. Probe sampling uses a similar amount of memory to the original GCG algorithm although it involves extra procedures and an extra model, by saving the computation of target model on the whole candidate set. As such, the usage of probe sampling does not introduce extra memory and can be applied when the original GCG algorithm is applied. In terms of the memory usage of the target model and the draft model, most of the memory is spent on target model, probably because the draft model is much smaller.Time allocation. We look at the specific time spent on different operations. As shown in Figure 4 , probe set computation using the target model and full set computation using the draft model take a similar amount of time so we can parallelize the computation easily. Sampling candidates in the graph involves a forward and backward pass as mentioned earlier and can be completed relatively quickly. Similarly, it is also fast to compute the agreement using the ranked losses on CPU, so our algorithm introduces relatively little overhead.In this section, we conduct extensive studies to understand how the proposed method works. We conduct all of the following experiments on the validation set, so the numbers are not directly comparable to the numbers in the main results. For the validation set, the original GCG algorithm achieves an ASR of 66.0 with an average time of 9.16 seconds per iteration. In each of the study, we highlight the settings that we find to be the best.Filtered set size. The filtered set size is the most important factor in our method. If it is too small, then we will achieve a lot of speedup at the cost of relying too heavily on the draft model and resulting in a lower ASR. If it is too big, then we would not achieve much speedup. Hence we experiment with different filtered size reduction hyperparameter R. The filter set size is (1 -α) * B/R where α is the probe agreement score described in Section 2.2.As shown in Table 7 , the time does monotonically decrease if we use a smaller filtered set size. However, interestingly, there is a sweetspot for the ASR with R set to 8. We believe that this can resonates with the hypothesis of introducing randomness as the source of ASR boosts. Both too much or too little randomness hurt performance. As such, we use R = 8 for probe sampling. We further show several convergence processes with varying values of R in Appendix B.Adaptive vs fixed filtered set size. As mentioned in Section 2.2, an alternative to use an adaptive filtered set size is to use a fixed size. Here we investigate whether it matters to use an adaptive filtered set size that is determined by how much the draft model and the target model agree on each candidate set. To use a fixed size, we simply fix the probe agreement score α to be 0.9, 0.6, 0.3, and 0.0 and compare with the adaptive case. As shown in Table 8 , fixed probe agreement scores always lead to worse ASR. Furthermore, when adopting GPT-2 as the draft model, the average agreement score is 0.45 with a standard deviation of 0.11. This shows that the agreement score between the two models varies significantly for different candidate sets. We also provide the statistics of α for other draft models in Table 11 .Probe agreement measurement. We also experiment alternatives to measure the probe agreement score, including the Pearson correlation coefficient (Pearson, 1900 ), Kendall's Tau correlation coefficient (Kendall, 1938) , and Goodman and Kruskal's gamma (Goodman et al., 1979) where the Pearson correlation coefficient directly uses the loss values to compute the agreement and the others use the ranking information. As shown in Table 9 , all methods have similar time cost, and Spearman's rank correlation coefficient achieves the best ASR. The Pearson correlation coefficient performs worse than other ranking-based agreement measurement.Probe set size. The size of the probe set also determines whether the probe agreement score is measured accurately. As such, we experiment with different probe set size and report the performance in Table 10 . We find that using a small probe set such as B/64 or B/32 can result in inaccurate agreement score, which put a put a significant toll on the attack success rate. It also does not lead to too much time reduction since the draft model computation done in parallel takes more time and the reduced computation is not the bottleneck. Using a larger probe set size such as B/4 and B/2 will lead to more accurate agreement score but does not increase the ASR significantly. As such, using a probe set of size B/16 is good enough to accurately measure the agreement and achieves maximum time reduction.Here we also experiment with bigger draft models, some of which is of similar size to Llama2. We experiment with GPT-Neo (Gao et al., 2020) , Flan-T5-base (Chung et al., 2024), BART (Lewis et al., 2019) , Phi-1.5 (Li et al., 2023) , TinyLlama (Zhang et al., 2024) and Sheared-LLaMA (Xia et al., 2023) . Among them, Sheared-LLaMA might be the closest to Llama2 since it is a pruned version of Llama2. For TinyLlama, Phi and Sheared-LLaMA, we use 2 A100s with 80GB memory to fit the whole computation.As shown in Table 11 , Sheared-LlaMa achieves the best ASR although the time reduction is not as good as smaller models such as GPT-2 and there would be a higher time cost if we manage to fit all computation in one GPU. On contrast, Flan-T5, BART, TinyLlama and Mistral all achieve lower ASRs probably because of being very different than Llama2. However, the results are still better than the baseline ASR 66.0. GPT-2 and GPT-Neo achieve a good balance of performance and speedup.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Answer Justification: This paper adheres to the NeurIPS Code of Ethics.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
related work: 
 Alignment of LLMs. To build safe LLMs, alignments has also been a widely studied topic in the community (Stiennon et al., 2020; Ouyang et al., 2022) . Efforts have been put into improving helpfulness (Bai et al., 2022a; Cheng et al., 2023) , honesty (Kaddour et al., 2023; Liu et al., 2023; Xu et al., 2023) , and harmlessness (Hartvigsen et al., 2022) . Among these works, there has been a growing interest in using feedback from a LLM to perform alignment (Bai et al., 2022b; Gulcehre et al., 2023; Burns et al., 2024; Yuan et al., 2024a) . Despite all the efforts, there has not been a definitive answer for LLM safety alignments, which also motivates our research in LLM safety.Discrete Prompt Optimization. Attacking LLMs via adversarial prompt can be formulated as a discrete prompt optimization problem (Zou et al., 2023) . In this context, attacking algorithms strive to discover superior prompts that effectively steer aligned LLMs toward generating adversarial answers. Some approaches leverage LLMs themselves to iteratively refine prompts (Xu et al., 2022; Pryzant et al., 2023) . However, aligned LLMs may resist refining adversarial prompts, rendering these methods ineffective. Other strategies employ RL-based prompt optimization techniques such as those in (Mingkai and Jianyu, 2022; Lu et al., 2023) , necessitating additional MLP training with extensive adversarial data and specific reward design. Moreover, other models introduced in (Cho et al., 2023; Long et al., 2024) to help with prompt optimization must remain unaligned, particularly in jailbreak scenarios (Chao et al.) . However, their performance tends to be limited, especially when dealing with strongly fine-tuned models like Llama2-Chat.LLM Jailbreaks. LLM Jailbreaks have received considerable interests recently since due to the implications of applying LLMs widely in human society. Although there is a continuous effort to build safe and reliable LLMs, bypassing the safety mechanism of LLMs is not uncommon. For example, fine-tuning a safe LLM on a few data instances can easily breaks its safety guarantees (Qi et al., 2024; Lermen and Rogers-Smith, 2024) . Treating the jailbreak as a prompt optimization problem has also led to a certain level of success (Zou et al., 2023; Mökander et al., 2023; Liu et al., 2024; Chao et al.; Geisler et al., 2024) . In addition, conversing in a ciphered language (Yuan et al., 2024b) , planting a backdoor during RLHF (Rando and Tramèr, 2023) , using a less well-aligned language (Deng et al., 2024) and multi-modality (Shayegani et al., 2024) can also lead to successful jailbreaks. Researchers also construct large dataset of manual jailbreak prompts (Toyer et al., 2023) .Among these jailbreak methods, the prompt optimization method GCG (Zou et al., 2023) provides the more general and universal solution for us to study the jailbreaking problem. As such, in this work, we mainly focus on the acceleration of GCG, but the idea of delegating computation to a draft model can also be applied in other situations such as the multi-modality case and finetuning case. We leave the extension of this work for future work.Acceleration. In the field of acceleration, speculative sampling (Chen et al., 2023; Leviathan et al., 2023) is the most relevant to our method. They also use a draft model but its design cannot be directly applied to accelerate the GCG algorithm. REST (He et al., 2024) adopts the concept of speculative sampling but uses a retrieval approach based on a Trie to construct the candidate. The attention module has also been a focus of acceleration because of its quadratic nature (Dao et al., 2022; Cai et al., 2024) . There have also been continuous interests in more efficient versions of Transformers (So et al., 2019; Dai et al., 2021; Liu et al., 2021; Gu et al., 2020 Gu et al., , 2021)) . These architectural changes are complementary to our algorithm design and we leave it to future work. 
conclusion: 
 In this paper, we propose an algorithm probe sampling that can effectively accelerate the GCG algorithm. We achieve an acceleration ranging from 2.1× to 6.3× in different scenarios on AdvBench. We illustrate the intuition and how the algorithm works through extensive experiments. Furthermore, this approach is also applied to general prompt optimization methods and other jailbreak techniques, including AutoPrompt, APE, and AutoDAN. We believe the idea of using the probe agreement score to perform adaptive computation can be applied to cases other than GCG. For example, it could potentially be used to perform conditional computation for attention. Another direction is to extend the framework to the multi-modality case which can be interesting given the vast amount of video data. It would also be interesting to run a small draft model on the scale of web data to detect the existence of natural adversarial prompts. 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed? 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: The paper poses no such risks Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [Yes] Justification: In Section 3 (Experiment)Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. 
 
 Appendix: Probe sampling has two main limitations. Firstly, it exhibits relatively slow performance when tested on large-sized test sets, which hampers its efficiency. Secondly, it is limited to supporting only open-source models, thereby excluding proprietary or closed-source models from benefiting from the proposed acceleration techniques. These limitations indicate the need for further improvements to enhance the speed and broaden the model support in order to make the jailbreak acceleration approach more robust and applicable across a wider range of language models.Probe sampling can be applied to accelerate GCG algorithm. Having a faster algorithm to explore adversarial cases of alignments enable us to study how to make LLMs safer. As far as we know, as of now, there is not a LLM that can use this algorithm to achieve malicious behavior in real-world that would not be possible without the algorithm. The goal of this research is to present a general algorithm which may inspire new research, and also contribute to the gradual progress of building safe and aligned AIs.The following code shows the core implementation of probe sampling using PyTorch. As seen in the code, the algorithm is relatively easy to use. In Figure 5 , we also show a few convergence processes with different values of R, where the pink line corresponds to R = 8. The pink line always achieves successful optimization while the other lines can lead to suboptimal results due to excessive randomness or insufficient randomness. In particular, the blue and yellow lines can suffer from excessive randomness and the other lines might have insufficient randomness. In other speedup works (He, 2023), using torch.compile() can lead to significant acceleration. It compiles LLMs into an kernel and alleviate the overhead of repeatedly launching the kernel. Table 12 shows that the time cost is similar with or without this optimization enabled. This is likely due to the fact that we use large batch sizes and long input sequences, whose computation cost dominates the overhead caused by the eager execution and launching the kernel repeatedly.NeurIPS Paper ChecklistJustification: There is no societal impact of the work performed.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 


Decision: The paper investigates the problem of generating adversarial prompts using Greedy Coordinate Gradient (GCG) and introduces probe sampling with a small draft model to reduce the costs of prompt evaluation. Experiments demonstrate a substantial speedup on benchmarks. The primary concerns raised were the comparison with recent related work and the alignment between the draft and the base models. During the rebuttal, the authors provided additional experimental results that addressed most of these concerns.

Reviews: review: paper_summary: paper_summary: This paper presents a novel algorithm called "Probe sampling" to accelerate the Greedy Coordinate Gradient (GCG) method for optimizing adversarial prompts against large language models (LLMs). The key idea is to use a smaller "draft" model to filter out unpromising candidate prompts, reducing the number of expensive evaluations needed on the full target LLM. The method dynamically determines how many candidates to filter based on measuring agreement between the draft and target models on a small probe set. Experiments show Probe sampling achieves 3.5-6.3x speedups on benchmark datasets while maintaining or improving attack success rates. The technique is also shown to accelerate other prompt optimization and LLM attack methods.
strength_weakness: strength_weakness: - It would be good to comment on the other existing approaches to speed up GCG like Fast Adversarial Attacks on Language Models In One GPU Minute and Making a SOTA Adversarial Attack on LLMs 38x Faster. Since they were out in February/March, probably it’s still fine to treat them as concurrent work, but it would be good to discuss the differences to better contextualize your work.
questions: questions: No.
limitations: limitations: The authors provide a reasonable discussion of limitations. One additional limitation that would make sense to discuss is the high memory requirement for gradient-based red-teaming methods like GCG, which effectively limits the experiments to smaller models (i.e., only up to 7B parameters).
paper_summary: paper_summary: The authors propose using a significantly smaller draft model compared to the target LLM to filter candidate suffixes, thereby accelerating the training process of GCG-based algorithms.
The results demonstrate a faster training speed with enhanced ASR.
strength_weakness: strength_weakness: 1. As mentioned on line 82, "one needs to perform B forward passes." In my opinion, these B candidates can be sent to the LLM together within a batch. By fully utilizing the GPU's parallel technique, it actually does not need to take B times the amount of time. Can an LLM with a smaller batch size achieve faster speeds? If not, I think the author should illustrate why the proposed method can speed up.
2. Since the draft model is not optimized, how to guarantee that the draft model and the target model align well, i.e., $\alpha$ is significantly larger than $0$? In my opinion, GCG will generate meaningless words, and the function of the draft model seems to be to check the meaning of these suffixes and discard  the meaningless ones. I encourage the authors to explain the the meaning of alignment between the draft model and the target model.
3. While the GCG is a popular method and the $6x$ speed is impressive, there are another methods like advprompter [1] which has faster speed and higher ASR. I encourage authors to compare the proposed method with more efficient methods instead of GCG.

[1] Paulus, A., Zharmagambetov, A., Guo, C., Amos, B., & Tian, Y. (2024). Advprompter: Fast adaptive adversarial prompting for llms. arXiv preprint arXiv:2404.16873.
questions: questions: 1. The method Amplegcg [2] achieve better performance than GCG, can the proposed method be applied to speed this traning process?

[1] Liao, Z., & Sun, H. (2024). Amplegcg: Learning a universal and transferable generative model of adversarial suffixes for jailbreaking both open and closed llms. arXiv preprint arXiv:2404.07921.
limitations: limitations: none.
paper_summary: paper_summary: The paper proposes a method to accelerate discrete prompt optimization algorithms. In addition to the target model, a smaller draft model is used to reduce the number of candidates to be evaluated by the target model based on an agreement score between the two models. When applied to Greedy Coordinate Gradient and trained with the open-source LLMs  Llama2-chat-7b and Vicuna-7b, the approach achieves a better runtime while maintaining the attack success rate (ASR) on AdvBench. The method is also applied to other prompt optimization algorithms such as AutoPrompt, ADE and AutoDAN.
strength_weakness: strength_weakness: - Transferability is a very important aspect of adversarial attacks but it is never mentioned in the paper. 
- The related work section lacks a proper presentation of discrete prompt optimization algorithms. Also, the authors did not mention other prior work that also use a pair of models for discrete prompt optimization. 

Minor issues:
The use of the term "Probe sampling" is inconsistent across the paper. Sometimes it is not emphasized and in lower case. 
line 310: "In this paper, we propose an algorithm called Probe sampling that can ..."
questions: questions: - Does this method affect the transferability of adversarial attacks to other LMs (for example from Llama2-chat-7b to Vicuna-7b) compared to plain GCG? 
- What is the effect of the filtered set size and the draft model (size, similarity to target model) on transferability?
- GCG operates at the token level and the draft model has a different tokenizer. What is the effect of the draft model tokenizer on the resulting suffix? also on transferability? (are tokens common to both tokenizers chosen or is the method completely oblivious to tokenization differences)
limitations: limitations: The authors have included a section on limitations and potential negative social impact.

Comments: title: Follow-up comment
comment: Dear Reviewer Jngk,

I hope this message finds you well. The discussion period is ending soon, I am writing to emphasize the importance of your review for our submission. Your score is significantly lower than the other two reviewers, and we believe this discrepancy may indicate a misunderstanding or oversight.

We have addressed all the concerns in our detailed rebuttal and would appreciate your prompt attention to it. A thorough reassessment is crucial to ensure a fair evaluation.

Your expertise is highly valued, and we trust that a reconsidered review will reflect the true merit of our work.

Thank you for your immediate attention to this matter.

Best regards, Authors
Thanks for the further clarifications. They address my (minor) concerns. I increase my score from 6 to 7.
The authors clearly answered all the questions regarding transferability and the effect of the draft model's tokenizer. The experiments suggest that Probe sampling does not affect the transferability of the adversarial prompts compared to plain GCG. I recommend adding the transferability experiments as well as the discrete prompt optimization algorithms related work in the main paper. I have updated my score.