Functional Homotopy: Smoothing Discrete Optimization via Continuous Parameters for LLM Jailbreak Attacks

Authors: Zi Wang, Divyam Anshumaan, Ashish Hooda, Yudong Chen, Somesh Jha
Primary area: alignment, fairness, safety, privacy, and societal considerations
Keywords: alignment, optimization

Abstract:
Optimization methods are widely employed in deep learning to address and mitigate undesired model responses. While gradient-based techniques have proven effective for image models, their application to language models is hindered by the discrete nature of the input space. This study introduces a novel optimization approach, termed the *functional homotopy* method, which leverages the functional duality between model training and input generation. By constructing a series of easy-to-hard optimization problems, we iteratively solve these using principles derived from established homotopy methods. We apply this approach to jailbreak attack synthesis for large language models (LLMs), achieving a 20%-30% improvement in success rate over existing methods in circumventing established safe open-source models such as Llama-2 and Llama-3.

Decision: accept (poster)
Reviewer scores: 8, 6, 8, 6

Reviews and discussion:
<thread>
creation date:
1730083127755

thread_type:
official_review

<thread_object>
creator: reviewer_m9rt

<content>
summary:
This paper presents a novel approach called the Functional Homotopy (FH) method for solving discrete optimization problems in the context of jailbreak attacks on large language models (LLMs). The method leverages a duality between continuous model parameters and input generation, using an easy-to-hard problem-solving approach. The authors claim a 20%-30% improvement in success rates over existing methods when applied to LLMs such as Llama-2 and Llama-3.

strengths:
* The paper introduces a novel functional homotopy method for jailbreak attacks on large language models (LLMs), building on the traditional homotopy framework used in optimization. Instead of directly solving the complex discrete optimization problem, the approach breaks it down into a series of progressively harder problems. Each solution from an easier problem is used as the starting point for the next, harder problem, which makes the optimization process smoother and more manageable.

* The experimental results show that this method delivers a 20%-30% improvement in success rates compared to baseline techniques when applied to state-of-the-art open-source models.

weaknesses:
* The proposed method appears overly simplistic, lacking both theoretical guarantees and in-depth analysis. The randomized search approach is basic and does not provide any assurance of optimality. Additionally, the complexity of performing a successful randomized search seems exponential with respect to the dimensionality of the problem. A formal theoretical analysis offering guarantees for the method would significantly strengthen the contribution.
* The baselines used for comparison also seem relatively weak. For instance, the gradient-based methods are naturally expected to perform poorly, given their myopic nature and disconnection from true gradient information. Furthermore, the datasets used for the experiments are small, making it difficult to draw definitive conclusions about the method’s effectiveness and efficiency. Stronger baselines would provide a more meaningful comparison.
* The algorithm's performance seems to be highly dependent on hyperparameter choices, such as the threshold, number of random search steps, and the search radius. A more comprehensive analysis on how to select these hyperparameters would provide valuable insight and improve the robustness of the proposed approach.

questions:
see weakness
</content>
</thread_object>

</thread>
<thread>
creation date:
1730452317393

thread_type:
official_review

<thread_object>
creator: reviewer_bvka

<content>
summary:
The paper trains the LLM to be less aligned and then attacks it with a greedy search for token replacements on the weaker versions of the model, gradually increasing the difficulty by reverting step by step to the aligned version.

strengths:
1. The idea is interesting and novel in its approach to manipulating the model's parameters.
2. The empirical performance in terms of ASR appears strong.
3. The effort to provide evidence that the token gradient in GCG is not beneficial is appreciated, even though this has already been hypothesized.

weaknesses:
1. The number of steps used for 'unalignment' must be decided beforehand. The procedure, if I understand correctly, is: conduct *N* steps to transition from parameter *p* to unaligned parameters *p'*. Then, iterate back and find an attack suffix for each *p_i* based on the previous one. This makes it difficult to determine if *p'* is sufficiently unaligned, and during the process of creating a new suffix, it is not possible to adjust to easier parameters when the attack does not seem effective.
2. The method introduces many additional hyperparameters (e.g., number of fine-tuning steps, number of GR steps per parameter set) and operational overhead, which are not discussed adequately (not even in RQ3). The authors should compare the attacks based on computational cost rather than steps, as fine-tuning is not factored into their 'step' metric.
3. The writing needs improvement. The text is often verbose, repeating the same points at different locations, and could be more concise. Additionally, there are inconsistencies in mathematical symbols, such as *p* being defined as the input (prompt) but is later used to refer to model parameters.

questions:
1. I am curious about why the method works. I would understand if gradient optimization were involved and it was argued that the landscape is smoother, guiding the process to the next optimum. However, since the suffix is optimized with a greedy search, why is this more effective? If the main idea is just remaining at a broad minimum during random search, then the transferability from the base model to the weakest model should be higher, which does not appear to be the case.
2. In Figure 3, what does it mean for FH-GR to be a successful attack within 1 iteration? Does this mean only one parameter update, or does it start from the weakest model after *N* updates and do only one GR search?

### Review Summary:
The paper presents an interesting idea. However, in its current state, I am not in favor of accepting it. I believe more research into the method is necessary, further evidence should be gathered, and the writing should be improved. That said, I am open to revising my score if my concerns are addressed.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730507939906

thread_type:
official_review

<thread_object>
creator: reviewer_vykh

<content>
summary:
This paper introduces the Functional Homotopy (FH) Method, a novel optimization approach designed to tackle the discrete optimization challenges inherent in language models, with a specific application to synthesizing jailbreak attacks. The authors note that existing gradient-based techniques, effective in continuous spaces like image models, face difficulties when applied to the discrete token space of language models. The FH method addresses this by leveraging a functional duality between model training and input generation. The method involves transforming a difficult optimization problem into a series of easier ones, using a homotopy-based approach where model parameters and inputs are optimized in tandem. The paper demonstrates that this method achieves a significant improvement in attack success rates (20-30%) over existing techniques when tested on open-source models like Llama-2 and Llama-3.

strengths:
The paper introduces an original optimization method, blending continuous and discrete optimization techniques in a way that has not been widely explored for language models. This approach brings a fresh perspective to the field of adversarial attacks.  The authors provide a strong theoretical foundation for their method, clearly explaining the duality between model training and input generation. The homotopy-based approach is well-grounded in optimization literature, which adds depth to the contribution. The demonstrated success of the FH method in improving attack success rates against robust language models is significant. The practical implications for AI safety research are noteworthy, especially in understanding and defending against potential vulnerabilities in LLMs. The paper is clearly written, with a logical structure that effectively guides readers through the problem, methodology, and experimental results. The use of diagrams, such as the illustration of the homotopy path, aids in understanding the method’s workings.

weaknesses:
The paper does not thoroughly address the computational demands of the FH method. Randomly sample tokens
from the vocabulary to replace the token at that position can be time-consuming. Given the potential resource constraints in real-world applications, more details on runtime efficiency and how the method scales with model size would be beneficial.

questions:
The authors mention issues with overfitting to specific malicious queries, especially when targeting outputs that models are trained to reject. Are there additional strategies or techniques that could be implemented to reduce this risk without compromising attack success rates?

While the method shows improvements in success rates, could the authors provide more comprehensive comparisons of computational efficiency, such as runtime and resource usage, relative to baseline methods? This would help in understanding the practical trade-offs of deploying the FH method.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730719916596

thread_type:
official_review

<thread_object>
creator: reviewer_bdpk

<content>
summary:
The paper proposes the functional homotopy method, a novel optimization approach for LLM attacks. FH fintunes the LLM and solves a number of easy-to-hard problems, which are constructed via gradient descent. The results show a substantial improvement over different baselines.

strengths:
- The paper is well-written and easy to follow
- The methodology is novel and well-motivated
- The proposed attack allows easy substitution of future attacks
- FH shows promising results

weaknesses:
- L81-82: "can retain" should be "have to retain"
- The efficiency comparison is based on the iterations instead of the runtime, which seems to be a fairer comparison.
- Missing related work. Consider including [1, 2]


[1] Schwinn, Leo, David Dobre, Sophie Xhonneux, Gauthier Gidel, and Stephan Gunnemann. "Soft prompt threats: Attacking safety alignment and unlearning in open-source llms through the embedding space." arXiv preprint arXiv:2402.09063 (2024).  
[2] Liao, Zeyi, and Huan Sun. "Amplegcg: Learning a universal and transferable generative model of adversarial suffixes for jailbreaking both open and closed llms." arXiv preprint arXiv:2404.07921 (2024).

questions:
Questions:
- How much storage does it take to store all the LLMs?
- Is there ablation using another baseline for the discrete optimization for FH, e.g., AutoDAN or GCG?
</content>
</thread_object>

</thread>
<thread>
creation date:
1732488231512

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
General Response

comment:
We express our gratitude to all reviewers for their thorough evaluation and insightful inquiries, which have led to further analysis and significant improvements in our paper. We particularly appreciate the unanimous recognition of our method's **originality**, **novelty**, and **empirical superiority**. Our study provides compelling evidence that intermediate model checkpoints can facilitate attacks on the base model, a finding with broad implications for the deep learning community, given that model fine-tuning LLM is a standard practice known to potentially compromise model alignment [1]. 

We address several common concerns raised during the review process in our other comments **("Algorithmic Intuition" and "Hyperparameters")**. 

All addressed concerns have been incorporated into the revised manuscript, with new text highlighted in blue.

---
## References
[1] Xiangyu Qi, Yi Zeng, Tinghao Xie, Pin-Yu Chen, Ruoxi Jia, Prateek Mittal, and Peter Henderson. "Fine-tuning Aligned Language Models Compromises Safety, Even When Users Do Not Intend To!." . In The Twelfth International Conference on Learning Representations.2024.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732488320418

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Algorithmic Intuition

comment:
We emphasize two key aspects that differentiate our approach from a purely random search: (1) the discrete topology defined by Hamming distance, and (2) the utilization of greedy search heuristics in optimization algorithms, including GCG and GR.
1. The discrete topology is characterized by a Hamming distance of 1 between neighboring inputs that differ by a single token. Given our focus on 20-token suffixes, the maximum distance between any two suffixes is 20. Theoretically, this implies that an existing attack suffix could be identified within 20 iterations under ideal conditions.
2. Our optimization algorithms employ local search with greedy heuristics. Each iteration samples a fixed number of neighboring inputs at distance 1 from a seed input, selecting the neighbor with the minimal objective value as the seed for subsequent iterations. However, this greedy approach may lead to entrapment in local optima, as proximal neighbors to a successful suffix do not necessarily yield lower loss values.

While both GCG and GR adhere to this framework, GCG incorporates gradient information for neighbor sampling, offering only marginal improvements over random sampling.

To address the limitations of greedy search heuristics, we propose a **homotopy-based approach**. This method constructs a series of progressively complex optimization problems through continuous model fine-tuning. The underlying principle posits that solutions to adjacent problems within this continuum are likely proximal, facilitating more effective search guidance towards the global optimum compared to local greedy heuristics. Our FH method generates a series of effective intermediate solutions converging to the original problem's solutions.  We provide a new level-set based conceptual illustration **(Figure 6 in Appendix E)** to show the evolution of the solution underpinning our homotopy method.

We present additional empirical analyses to substantiate this argument. Recall that both GCG and GR utilize identical loss objectives (F_0), while FH-GR employs a sequence of loss objectives (F_n, ..., F_0), culminating in the same final loss expression as GCG. We designate (F_n, ..., F_0) as the homotopy loss, with inputs guided by F_i. 

The evolution of the loss objective is graphically represented over 1000 iterations of input search. For FH-GR, we present two plots: (1) the progression of homotopy loss **(Figure 7 in Appendix F)**, and (2) the evolution of F_0 induced by the inputs during FH-GR optimization **(Figure 8 in Appendix F)**.

---
## Empirical Results
The empirical evidence aligns with our homotopy method assumptions: (1) The progression of homotopy loss demonstrates that introducing easier problems enables the maintenance of lower homotopy loss during optimization. (2) Comparing F_0 evolution for GCG and FH-GR inputs reveals that GCG inputs, driven by greedy search heuristics, rapidly decrease loss initially but soon stagnate, likely due to local optima entrapment. Conversely, FH-GR inputs, guided by homotopy objectives, exhibit a slow but steady decrease in loss, ultimately achieving a **significantly lower loss**.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732489557891

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Hyperparameters

comment:
### Computational Overhead
Our proposed method demonstrates comparatively modest storage and computational overheads. We use LoRA [1], which is a parameter-efficient method for finetuning. **Each LoRA checkpoint requires 49 MB**, with a maximum of 768 checkpoints occupying approximately 38 GB. In practice, we utilized significantly fewer checkpoints, further reducing storage requirements. For context, full model storage needs are substantially larger: Llama-2 (13 GB), Mistral (14 GB), Vicuna (26 GB), and Llama-3 (60 GB)

We also provide the average runtimes (in minutes) of different methods (including the check for success performed by the judge) for a single test case while ensuring maximal GPU utilization. 

| Model |  FH-GR |  GCG |  AutoDAN | 
|---|---|---|---|
|  Llama-2 (1000 iters)| 49.45  |  50.01 |  120.08 | 
|  Llama-3 (1000 iters)| 46.08  |  46.08 |  81.34 | 
|  Mistral (500 iters)| 23.35  |  23.82 |  67.53 | 
|  Vicuna (500 iters)| 24.09  |   24.47 |  63.16 | 


Recall that we only fine-tuned each model once for all test inputs, which takes **approximately 20 minutes**, while attacking a single input for 1000 iterations requires **at least 45 minutes**. When amortized across 200 inputs, the running-time overhead is about **6 seconds per instance**. Consequently, both the storage and computational overheads of our method are relatively insignificant compared to the resource demands of complete language models and the overall attack process. We have included detailed overhead information in **Appendix A** of the updated manuscript.

---
### Robustness of Hyperparameter Tuning
 The selection of 500 epochs for model fine-tuning was based on empirical observations that this duration sufficiently misaligns the model parameters to facilitate jailbreaking **without additional optimization**. However, our method's effectiveness persists with fewer epochs, essentially initiating the homotopy from a more aligned model state. 

We conducted additional experiments with stronger checkpoints (i.e., models fine-tuned for fewer epochs), and the result demonstrates that the optimization still converges to a lower loss than the base GCG algorithm. **Figure 9 in Appendix F** illustrates that optimizations starting from stronger checkpoints exhibit more rapid loss reduction compared to GCG, underscoring the robustness of our approach to variations in the fine-tuning duration.

---
### Search Steps and Radius
1. We use 1000 search steps, as per the baseline methods GCG [2] and AutoDAN [3] in order to make a faithful comparison with them.
2. We consider a search radius of 20 tokens for the adversarial suffix, as per GCG [2], in order to make a faithful comparison with it and AutoDAN, which also uses the same baseline in it's comparisons.

---
### References
[1] Edward J Hu, Yelong Shen, Phillip Wallis, Zeyuan Allen-Zhu, Yuanzhi Li, Shean Wang, Lu Wang, & Weizhu Chen (2022). LoRA: Low-Rank Adaptation of Large Language Models. In International Conference on Learning Representations.

[2] Zou et al. “Universal and Transferable Adversarial Attacks on Aligned Language Models” arXiv preprint arXiv:2307.15043 (2023)

[3] Xiaogeng Liu, Nan Xu, Muhao Chen, and Chaowei Xiao. “AutoDAN: Generating stealthy jailbreak prompts on aligned large language models. In The Twelfth International Conference on Learning Representations”, 2024a. URL https://openreview.net/forum?id=7Jwpw4qKkb.
</content>
</thread_object>

</thread>
<thread>
creation date:
1733155758624

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
NP-Hardness of Jailbreak Attacks

comment:
We additionally established that the computational complexity of the jailbreak attack optimization problem is **NP-hard**. This problem involves minimizing the prefix-matching loss (i.e. cross-entropy loss with the target string *"Sure here is..."*), for a given prompt in any LLM.

This is proven through a demonstration that a **single hidden layer** neural network with binary inputs can emulate the computation of a boolean formula. Due to revision constraints, the detailed proof is available [anonymously at this link](https://anonymous.4open.science/r/np-hard-52F1/NP_hardness.pdf), and will be incorporated into the camera-ready version. 

This study establishes the computational complexity of the LLM jailbreak optimization problem, a new contribution to the field as previous jailbreak literature has not addressed this aspect to the authors' knowledge. The demonstrated complexity implies that efficient jailbreak optimization algorithms likely require exploitation of problem-specific structures. Our FH method, leveraging model fine-tuning, can be interpreted as utilizing the "alignment" property of models. A rigorous analysis of FH would necessitate an extensive exploration of neural network structures, LLM architectures, and typical language data characteristics, potentially advancing the frontiers of deep learning and LLM theory.
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper proposes a new method called the Functional Homotopy (FH) method to solve discrete optimization problems that appear in jailbreak attacks on LLMs. The proposed method achieves 20%-30% improvement in success rates.  

The proposed method is based on an interesting idea that is quite new in the literature. The method is nicely designed by solving a series of progressively harder problems one after another. Moreover, the performance improvement is significant.   
The writing is clear and well organized. It is easy for readers to follow the context. The readers will benefit from reading this paper.  

Hence, I recommend acceptance for this paper.