Beyond Mere Token Analysis: A Hypergraph Metric Space Framework for Defending Against Socially Engineered LLM Attacks

Authors: Manohar Kaul, Aditya Saibewar, Sadbhavana Babar
Primary area: foundation or frontier models, including LLMs
Keywords: Jailbreak Attack, LLMs, LLM Security, AI Security

Abstract:
Recent jailbreak attempts on Large Language Models (LLMs) have shifted from algorithm-focused to human-like social engineering attacks, with persuasion-based techniques emerging as a particularly effective subset. These attacks evolve rapidly, demonstrate high creativity, and boast superior attack success rates. To combat such threats, we propose a promising approach to enhancing LLM safety by leveraging the underlying geometry of input prompt token embeddings using hypergraphs. This approach allows us to model the differences in information flow between benign and malicious LLM prompts.

In our approach, each LLM prompt is represented as a metric hypergraph, forming a compact metric space. We then construct a higher-order metric space over these compact metric hypergraphs using the Gromov-Hausdorff distance as a generalized metric. Within this space of metric hypergraph spaces, our safety filter learns to classify between harmful and benign prompts. Our study presents theoretical guarantees on the classifier's generalization error for novel and unseen LLM input prompts. Extensive empirical evaluations demonstrate that our method significantly outperforms both existing state-of-the-art generic defense mechanisms and naive baselines. Notably, our approach also achieves comparable performance to specialized defenses against algorithm-focused attacks.

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

Reviews and discussion:
<thread>
creation date:
1730297772130

thread_type:
official_review

<thread_object>
creator: reviewer_spo2

<content>
summary:
The paper studies defenses against prompt-based socially engineered attacks on LLMs.  Particularly, the paper introduces a robust prompt filter based on hypergraph metric geometry—each LLM prompt is represented as a metric hypergraph, forming a compact metric space, and the higher-order metric space over these compact metric hypergraphs can be leveraged to model the differences in information flow between benign and malicious LLM prompts.  The paper also derives upper bounds on the generalization error of the proposed prompt filter.  Finally the effectiveness of the proposed filter is demonstrated through experiments on two datasets.

strengths:
+ the paper is well-written and well-organized

+ the proposed robust prompt filter is novel, well-motivated,  and justified

+ theoretical analysis on the error bound of the robust prompt filter

weaknesses:
- more clarifications on the algorithms and experimental results are needed  

- more baselines are needed for comparison

questions:
Is Section 3.2 from previous work or proposed by the authors? I would like to know which part is novel and which is inspired by existing work. 

The paper tests that GNN and HGNN baselines do not perform well to distinguish malicious prompts. Can you provide more explanations and insights why (H)GNNs do not perform well, if the clique-expansion graph of a given hypergraph is well constructed. 
On the other hand, I am thinking about two other baselines: 

- 1. How about first performing clustering on the hyperpgraphs and then apply (H)GNN? 

- 2. The proposed kernel SVM is used to deal with varying size variable dimensional metric hypergraphs? What if we first map the metric hypergraphs into a latent space and then train a (SVM) classifier, or simply training a kernel SVM using the (malicious and benign) prompt embedding, which can be, e.g., an average of the tokens’ embeddings?  

- 3. There exists many (spatial-temporal) GNN works that can capture temporal, spatial, and higher-order information of the graph. Able to also compare with them?

It would be better to add some details of the baseline Mutation-based  and Detection-based defenses. This makes readers better understand the advantage of the proposed robust prompt filter.  

Any explanation why the proposed robust filter is also robust to algorithmic attack types? Can you also show example failure cases for Hypergraph? 

How to set w and s in the sliding-window for forward edge construction and r in the ball for forward edge construction in practice? Whats the impact of these factors? Is there any (positive/negative) correlation between the classification accuracy and the prompt length?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730344632788

thread_type:
official_review

<thread_object>
creator: reviewer_hy1p

<content>
summary:
The paper introduces a novel defense mechanism against social engineering attacks on large language models (LLMs). It models prompts as hypergraphs, capturing token interactions, and uses a Gromov-Hausdorff metric space to classify prompts as benign or malicious. Key contributions of this paper include hypergraph-based prompt modeling to detect complex manipulative patterns and theoretical guarantees for detecting new attacks. The proposed method outperforms existing defenses against socially engineered attacks. This approach provides a mathematically robust and effective method for improving LLM security.

strengths:
1.	The paper proposes a method for defending against social engineering attacks using hypergraph structures and Gromov-Hausdorff metric spaces, which represents a novel defensive approach. 
2.	The method is not only applicable to social engineering attacks but also performs well against other types of attacks.

weaknesses:
1.	Regarding defense methods, the authors should also compare GradSafe, which has been shown in the related work leveraging gradient information to detect jailbreak prompts.
2.	The authors do a great job in demonstrating the effectiveness of the proposed defense. However, as mentioned in the related work, previous methods are memory-intensive and infeasible for practical use. I would expect the authors also conduct a cost analysis on different defenses as well.
3.	More jailbreak datasets should be considered.

questions:
See weaknesses.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730614155899

thread_type:
official_review

<thread_object>
creator: reviewer_rh5i

<content>
summary:
This paper proposes a novel defense against jailbreak attacks. The defense is based on hypergraphs and a Gromov-Hausdorff metric to build a classifier and distinguish harmful prompts.

strengths:
The perspective of this work is novel and interesting. A detailed and solid theoretical analysis is provided. Experiments on different kinds of attacks are conducted to illustrate the effectiveness of the proposed method.

weaknesses:
1. The motivation of the proposed method is very unclear. There is a gap between jailbroken prompts and the hypergraph-based method. The authors only provide a simple intuition of adopting hypergraph to distinguish jailbroken prompts, but there is no clear evidence why hypergraph is useful, including either empirical or theoretical analysis or existing literatures.

2. Sections 3 and 4 are used to introduce notations, how to construct hypergraphs, and how to build a classifier using metrics between hypergraphs. However, there is no explanation of how these constructions are related to defending against jailbreak attacks. The authors simply state their notations, construction, and theorem on generalization error bounds on the SVM built on the metric, but there is no practical implication of these contents such as how the hypergraph and distance constructed in this way can show the difference between benign prompts and jailbroken prompts, etc. This theoretical analysis should clearly state how the defending effectiveness is guaranteed. 

3. The details of conducting baselines is unclear. For example, how to apply white-box attacks like GCG and AutoDAN to API-only model GPT-4 is unclear. Besides, the number of tested models is not sufficient.

4. Time complexity analysis is missing.

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

</thread>
<thread>
creation date:
1730739375626

thread_type:
official_review

<thread_object>
creator: reviewer_vnma

<content>
summary:
LLMs are susceptible to socially engineered jailbreak attacks, which remains underexplored by traditional defense methods. This paper proposed a new defense method specifically designed against socially engineered jailbreaks, based on a hypergraph approach. This method captures both sequential and semantic relationships among tokens to understand underlying intent, constructs hypergraphs from each prompt, and trains an SVM classifier as a prompt filter to detect jailbreak prompts. They theoretically provided the upper bounds of the generalization error of the proposed filter. The experiments demonstrated the effectiveness of the proposed defense against socially engineered jailbreaks on Llama-3.1 and GPT-4.

strengths:
1.	This paper brings a novel perspective by introducing a hypergraph-based method for representing and analyzing LLM prompts. 
2.	Addressing socially engineered jailbreak attacks contributes to a crucial yet underexplored area in LLM security.
3.	The overall writing is well-structured, and the theoretical proofs provide strong justification for the method’s design.

weaknesses:
1. The paper omits several advanced LLM defenses (e.g., SmoothLLM mentioned in Related Works) from the baseline comparisons, which limits the strength of the results. Including these methods would provide a clearer understanding of the proposed approach’s relative effectiveness.
2. There is ambiguity regarding the application of GCG and AutoDAN (both white-box attacks) on GPT-4, which is a black-box model. It is unclear how the authors applied a white-box attack to a black-box model. Clarifying or adapting the experimental setup here would strengthen the credibility of the results.
3. The proposed method is complex, involving modified Gromov-Hausdorff distances and hypergraph structures, which likely increases time complexity. While the time complexity of each component is theoretically analyzed and inference efficiency is addressed in Appendix B, a discussion of the computational costs associated with training would be beneficial.

questions:
Please refer to weaknesses.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732207479780

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Response to all reviewers

comment:
Dear Reviewers,
We would like to thank all of you for your valuable time and suggestions that have helped further strengthen our paper's results. Along with our detailed rebuttal, we have also updated our draft based on your feedback. All the changes to the draft are highlighted in blue color. 
Below is a detailed list of the changes made to the draft following the order of sections in the paper, along with a prefix that identifies the reviewer(s) who suggested the changes:

# Main Paper

**[By reviewer rh5i]** 
In Introduction (Lines 45-51), we added an explanation about well established linguistic patterns in persuasive prompts to strengthen our motivation. Lines 60-69, from the original Introduction then discuss how these patterns are captured by our hypergraph construction. 

**[By reviewer sPo2]** 
In Related Work (Lines 116-120 and 135-137) we describe mutation and detection based defenses, in comparison to our work. 

**[For reviewer rh5i]** 
In Our Method (Lines 141-144) we give a brief summary of our method before describing the mathematical details of our approach.

**[For all the reviewers]** 
In Empirical Results, the experimental setup, we give details about two more additional datasets that we run our experiments on - namely WildGuardTest and JailBreak-28K. In Models, we add two more LLM models, i.e., Mistral-7B and Vicuna-13B. We then provide our comparative ASR results over several existing attack and defense combinations for all 4 models on the JPP dataset for both persuasion attacks in Table 1 and algorithmic attacks in Table 2.

**[By reviewer sPo2]** 
In Tables 1 and 2, we compare against two naive baselines suggested by the reviewer (described in Lines 423-430), namely comparing to higher-order GNNs and just using an average token embedding per prompt and passing it through a kernel SVM to classify. 

**[By reviewer vNMa]** 
Tables 1 and 2, include comparisons to SmoothLLM.

**[By reviewer hy1p]** 
Tables 1 and 2, include comparisons to GradSafe. Lines 467-476 summarize all our findings in Tables 1 and 2.

**[By reviewers vNMa, rh5i]** 
We add a footnote on Line 467 outlining how white-box attacks like AutoDAN and GCG are run on GPT4.

**[By reviewer vNMa]** 
Lines 477-487, we show our training runtime breakdowns.  
Lines 489-495, we update our classification related description to also describe the results for additional datasets.

**[By reviewer sPo2]** 
Lines 515-520 give a brief description on the robustness of our method as compared to the baselines.

**[By reviewer sPo2]** 
Lines 522-530 show the limitations in terms of failure cases for our approach.

# Appendix

**[All reviewers]** 
Section B.3 has the ASR results like Tables 1 and 2, but for the other two datasets, i.e., WildGuardTest (Tables 5 and 6) and JailBreak-28K (Tables 4 and 7).

**[By reviewer sPo2]** 
Sections B.5 and B.6 discuss our method's robustness in comparison to other (H)GNN methods and the failure cases of our approach.

**[By reviewer Hy1p]** 
Section B.7 gives a detailed computational cost analysis of our method vs. the others, both theoretically and empirically. Tables 8 and 9 compare the CPU and GPU memory utilization, inference time, and ASRs for all the defenses on the JPP dataset on Llama 3.1 and Mistral-7B, respectively. It also outlines future improvements that can further speed up our method. 

We invite all reviewers to engage with our rebuttal and modifications to the draft.
</content>
</thread_object>

</thread>
<thread>
creation date:
1733157395789

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Thank you message

comment:
Dear Reviewers,

Thank you for taking the time to thoroughly review our paper and provide very valuable feedback. Your detailed comments and suggestions really helped us improve the quality of our work. We greatly appreciate your expertise and dedication to the peer review process.

Best regards,

Authors #10409
</content>
</thread_object>

</thread>


Metareview:
metareview:
Different from the previous work, this paper proposes a novel defense method against jailbreak attacks for LLMs, which is based on hypergraphs and a Gromov-Hausdorff metric. All the reviewers find this paper is really novel and interesting, and may motivate further studies. This paper is above the bar of top conferences. Congratulations to the good work!