Thank you for your thoughtful review and constructive feedback on our work. We appreciate your recognition of the strength of our experimental setup and are pleased that you found our paper well-written and easy to follow. Your acknowledgment that our method provides clear robustness against the ordering modifications of in-context examples is encouraging.

Your insights are valuable to us, and we have made extensive revisions to the manuscript based on your suggestions. For your convenience, we have highlighted these changes in blue.

We will address your comments and concerns in detail below and and have supplemented our work with new experimental results.

Response to Comment on the Threat Model

Thank you for your comment and for highlighting areas that required clarification. We apologize for any misunderstanding caused by our wording, and we appreciate the opportunity to clarify the threat model.

Clarification of the Attack Setting

Our study focuses on a two-party adversarial scenario involving a malicious end-user and the model provider. In this setting, the malicious user interacts directly with the LLM and manipulates the input—for example, by permuting the order of ICL examples—to compromise the model's performance. This threat model aligns with established adversarial settings in the literature [1,2,3,4] and provides a meaningful framework for evaluating the robustness of LLMs.

This differs from a three-party attack scenario, where a malicious actor intercepts a benign user's request. While such scenarios are also interesting, our work mainly focuses on the two-party setting where the adversary is the end-user directly interacting with the model.

Clarification about "imperceptible"

Thank you for bringing up this point. To clarify, the term "imperceptible" in our paper refers to being imperceptible to model providers, rather than end-users.

In the two-party adversarial setting, a malicious user intends to attack an LLM. In this context, the malicious user prefers the attack to be less noticeable to the model provider. Most methods in this scenario involve optimized adversarial prefixes or suffixes (often nonsensical strings) that are explicitly prepended or appended to the prompt [1,2,3] , or introduce noise perturbations into the samples [4]. Such alterations are easily detectable and filterable by model providers.

In contrast, our method involves only permuting the order of demonstrations, which is a normal operation during in-context learning and does not introduce any abnormal or suspicious content. This makes the attack less noticeable to model providers.

We have updated the manuscript to include this explanation, and we hope this clarification addresses your concern.

Response to Practical Use Scenarios

Thank you for your feedback. We discuss the practical use scenarios of our work as follows:

Our methodology is designed to enhance the robustness of LLMs in handling various possible input permutations, aiming to benefit both normal and adversarial scenarios:

• Normal Scenario: Typically, benign users provide demonstrations in arbitrary sequences. Our approach improves performance on the worst-case input permutations, thereby protecting the user experience in typical use cases.

• Adversarial Scenarios: Malicious end-users may deliberately reorder demonstrations to exploit model vulnerabilities and induce errors. Our enhancements mitigate the risks associated with such targeted attacks by ensuring the model remains robust to permutations intended to degrade its performance.

We hope these can address your concerns and demonstrates the applicability of our work.

References

[1] Universal and Transferable Adversarial Attacks on Aligned Language Models. 2023

[2] Tricking LLMs into Disobedience: Understanding, Analyzing, and Preventing Jailbreaks 2023

[3] Hijacking Large Language Models via Adversarial In-Context Learning. 2023

[4] Data Poisoning for In-context Learning. 2024

Response to Experiments

Thank you for your detailed feedback and for highlighting several areas where clarification is needed. We appreciate your suggestions and have addressed your concerns below.

Response to Sample Size and Independent Trials

Thank you for raising this important point. To ensure the robustness of our results, we have conducted three independent trials for each of the two datasets analyzed. In each trial, we randomly selected 100 examples from each task using different random seeds (42, 123, 456) to ensure unbiased selection and to capture variability in the data.

Table 1 below are the results, presented as the average performance across trials with 95% confidence intervals:

Table 1. Confidence Intervals of independent trials

continue...

The narrow confidence intervals indicate stable performance across different random samples, suggesting that our sample size is sufficient for the analyses conducted. We have included these details in the appendix of the revised manuscript for completeness. We hope this additional information addresses your concerns.

Response to Experiments on Diverse LLMs

Thank you for this valuable suggestion. In response, we have expanded our analysis to include four additional models: Mistral-7B, Gemma-7B, Llama2-7B, and Llama2-13B. While our findings could indeed extend to proprietary models, considerations of API changes over time and reproducibility have led us to focus on open-source models for this study.

The results are presented in Tables 2–5, which have been added to Appendix F of the manuscript. Key findings are as follows:

• Sensitivity to Permutations Across Different LLM Families: We observed that different LLM families exhibit varying sensitivities to permutations. Overall, the sensitivity ranking is Llama > Gemma > Mistral. Despite this variance, the phenomenon remains significant, with performance drops exceeding 10 percentage points in most cases.

• Effectiveness of Our Method: For cases involving three or more shots, our method consistently achieved improvements exceeding 10% in worst-case performance, validating the effectiveness of our approach across different models.

We appreciate your suggestion and believe that this expanded analysis provides a more comprehensive understanding of how the vulnerability impacts models outside of the Llama family.

Table 2. Experiments on Llama2-7B. Average and per-task performance are reported, with performance gains (%) shown in parentheses.

Table 3. Experiments on Llama2-13B

Table 4. Experiments on Mistral 7B v0.2

continue...

Response to Related Work

Thank you for these thoughtful suggestions regarding related work. We have strengthened the manuscript with following additions:

• We added relevant learning theory citations in Section 4 to provide more context for interested readers.

• We have incorporated discussion of OOD Generlization and GroupDRO work into the DRO paragraph in related work section.

These additions will provide readers with important context and enable them to explore the theoretical underpinnings in more depth. We appreciate the guidance on improving the manuscript's scholarly rigor.

Response to Miscellaneous

Thank you for these points.

• "General performance" refers to average performance or performance with a random permutation, both of which are now reported in Figure 1 as suggest.

• Modified Figure 1 with a more distinctive color palette to improve readability.

Response to Question 1

Thank you for your question. Exploring the best-case performance scenario is indeed intriguing. Although our methodology was initially designed to optimize for pessimistic (worst-case) scenarios, we have also included an evaluation of the best-case performance for both PEARL and ERM to provide a balanced perspective. The results are shown in the Table 6 below.

Table 6: Best performance comparison between ERM and PEARL.

Surprisingly, the results, show that across all datasets and in every shot condition, PEARL's best performance consistently exceeded that of ERM, although the overall average improvement was modest.

We appreciate your insightful suggestion, as it adds a significant dimension to our model evaluation. These findings have been included in the appendix for reference.

Thank you once again for your thoughtful engagement.

Response to Question 2

Thank you for this suggestion. We have:

• Added the random permutation baseline to Figure 1 and change the color.

• The average performance calculation method was previously explained in our response and in Equation (3).

Response to Question 3

Thank you for the query. This is indeed the actual upper bound, as previously clarified in our response and in added Equation (3).

---

We sincerely appreciate your detailed and insightful comments, which have undoubtedly strengthened our work. We hope that our responses and the updated manuscript effectively address your concerns and improve the clarity of our contribution. We look forward to any additional feedback you may have.

Response to Proposed Method

We appreciate your thorough review of the methodology. All content suggestions have been revised in Section 4 and are highlighted in blue for clarity.

Response to Question on NP-Hard and the Definition of Ambiguity Set $\mathcal{Q}$

Thank you for your questions about the NP-hardness and the definition of the ambiguity set.

Regarding NP-hardness: We apologize for this imprecision. While search space of the combinatorial optimization problem is indeed exponential O(n!), we cannot rigorously prove that it is NP-hard. We have corrected this claim in the manuscript.

Regarding the definition of $\mathcal{Q}$: The ambiguity set $\mathcal{Q}$ is constructed to capture all distributions obtained by permuting the prompts in the empirical distribution $\hat{P}$. Specifically, for each possible permutation $\Pi \in \mathbb{P}$, we define the permuted distribution $Q_{\Pi}$ by applying $\Pi$ to the prompt $p$ of each data point in $\hat{P}$ :

$$Q_{\Pi}:=\\\{(\Pi \cdot p, x, y) \mid(p, x, y) \sim \hat{P}\\\}, \quad \Pi \in \mathbb{P}$$

where $\Pi$ is a permutation matrix acting on the sequence of demonstrations in $p$, and $\mathbb{P}$ denotes the set of all possible permutation matrices. The ambiguity set $\mathcal{Q}$ is then defined as the convex hull of these permuted distributions:

$$\mathcal{Q}:=\\\{\sum_{\Pi \in \mathbb{P}} q_{\Pi} Q_{\Pi} \mid q \in \Delta_{|\mathbb{P}|-1}\\\}$$

where $q$ is a probability vector belonging to the $|\mathbb{P}|-1$-dimensional simplex $\Delta_{|\mathbb{P}|-1}$.

We have updated these detailed definitions in the manu and hope they can address your concerns.

Response to the [CLS] Token's Role and Function

Thank you for your question. The [CLS] token is a type of artificially defined special separator first introduced in BERT [8] (which can be replaced by other special separators like [bos], [eos]), and it serves two main purposes:

1. Acts as a separator between different demonstrations in the text sequence
2. Helps learn representations for each demonstration [9]

We hope this clarifies your question.

[8] BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding. NAACL 2019

[9] Less is More: Pretrain a Strong Siamese Encoder for Dense Text Retrieval Using a Weak Decoder. EMNLP 2021

Clarification about Adversarial Training

Thank you for your thoughtful question. We would like to clarify that our problem formulation aligns with adversarial training due to its inherent min-max structure, as demonstrated in Equation (6).

Additionally, the optimization objectives of the P-Net and the LLM are opposites (excluding the entropy constraint loss of the P-Net). Specifically, the P-Net maximizes the LLM's loss (Equation (17)) when the LLM parameters are fixed, whereas the LLM minimizes the LLM's loss (Equation (14)) when the P-Net parameters are fixed. This dynamic establishes a zero-sum game structure between the two components.

We have updated the manuscript with a more detailed explanation in Section 4.3. We hope this clarification addresses your concern, and we greatly appreciate your feedback.

Clarification about the OT Equations

Thank you for your questions and for highlighting areas that require further clarification. We address each point separately:

Dimensionality of X: In Equation (10), $X ∈ R^{n×n}$, where n is the number of demonstrations. (Note: X is now replaced by R.). We have expanded this explanation in the manuscript.

To clarify, the P-Net $: (\mathcal{P} \times \mathcal{X} \times \mathcal{Y}) \rightarrow \Delta(\Pi)$, which maps an input example to a distribution of challenging permutations. To this end, we employ sinkhorn algorithm, whose output converges to a the distribution of permutations (a doubly stochastic matrix), However, we need to sample a specific permutation from this distribution while ensuring the overall process differentiable for gradient-based optimization. To achieve this, we apply Gumbel sampling [10]. The "introduction of randomness" and "control of discreteness" refer to this sampling process.

We hope that these explanations and clarifications can address your concerns and improve the clarity of our work.

[10] Categorical Reparameterization with Gumbel-Softmax. ICLR 2017

Clarification about the Question "OT deals with distributions over perturbations or perturbations"

Thank you for your question. To clarify, the OT in our work aims to transform the input permutation distribution into a target distribution that is more challenging for current LLMs. To achieve this, we design P-Net, a mapping function defined as $P\text{-Net}: (\mathcal{P} \times \mathcal{X} \times \mathcal{Y}) \rightarrow \Delta(\Pi)$, which maps an input example to a distribution over challenging permutations. Thus, we are working with distributions over perturbations, not the perturbations themselves.

We hope this clarification addresses your concerns.

Clarification about the Question "where the sinkhorn operator factors in Equation (8)"

Thank you for your questions regarding the sinkhorn operator. We address these points below:

• Clarification on the Absence of the Sinkhorn Operator in Optimization Objective (14): The Sinkhorn operator is indeed utilized within our methodology; however, it is embedded in the sampling process denoted by $\Pi \sim P\text{-Net}(\phi; p,x,y)$ for the sake of brevity and clarity in presentation. The Sinkhorn operator, being parameter-free, does not appear explicitly in the optimization objective where the focus is on the trainable parameters of P-Net. We have added this clarification in the manuscript.

• Connection Between Formulations (8) and (3): The sampling step $\Pi \sim P\text{-Net}(\phi; p,x,y)$ in our P-Net training objective formulation (15), corresponds to addressing the inner maximization problem presented in formulation (3).

We have rewrite the formulas and descriptions in Section 3.4 to make it clearer, and hope they can address your concerns.

Clarification about "trivial solutions: outputting even matrices that average out the semantic content"

Thank you for your query. We clarify that P-Net outputs an approximate permutation matrix (Figure 3 and Sec. 4.2). Ideally, this should preserve the distinctiveness of each input element. However, P-Net may resort to shortcuts to producing trivial solutions, like the one described below, to artificially increase LLM's loss during adversarial training:

$\left[\begin{array}{ll}[0.5, 0.5], [0.5, 0.5]\end{array}\right] \cdot\left[x_1, x_2\right]=\left[0.5 \times x_1+0.5 \times x_2, 0.5 \times x_1+0.5 \times x_2\right]$

This results in semantic overlap by averaging the input features (demonstrations in our case), which leads to a loss of distinct information. While such extreme scenarios are unlikely, we are committed to ensuring that P-Net avoids these trivial solutions.

We hope this explanation can address your question. We appreciate your input and are open to further discussion.

Clarification about "the steps between Equation (9) and (10)"

Thank you for your question. We explain the steps between (9) and (10) in details. Note that (9) and (10) now correspond to (14) and (17) respectively in the updated manuscript.

We first optimize the P-Net, corresponding to the inner maximization step in Equation (6). For a given example $(p, x, y)$, we sample a permutation $\Pi \sim \operatorname{P-Net}(\phi ;(p, x, y))$ from P-Net. We then compute the LLM's loss on the permuted example $(\Pi \cdot p, x, y)$, denoted by $\ell(\theta ; \phi ;(\Pi \cdot p, x, y))$. The objective is to optimize the P-Net parameters $\phi$ to maximize this loss:

$$L(\phi; \theta)_lm = \mathbb{E}[\ell(\theta; \phi; (\Pi \cdot p, x, y))] \quad \text{s.t. } (p, x, y) \sim \hat{P}, \Pi \sim \text{P-Net}(\phi; (p, x, y)) \quad \quad (14)$$

Note that the Sinkhorn operator is implicitly included in $\Pi \sim \mathrm{P}-\mathrm{Net}(\phi ;(p, x, y))$. To prevent the P-Net from exploiting trivial solutions, such as outputting uniform matrices that dilute the semantic content of the demonstrations, we introduce an element-wise entropy constraint term that encourages $\Pi$ to be as distinct as possible:

$$L(\phi)_ent=\mathbb{E}[\Pi(1-\Pi)] \quad \text{s.t. } (p, x, y) \sim \hat{P}, \Pi \sim \mathrm{P}-\mathrm{Net}(\phi ;(p, x, y)) \quad \quad (15)$$

This leads to the following combined optimization for the P-Net:

$$\hat{\phi}^{\star}=\arg \max _{\phi \in \Phi}(L(\phi ; \theta)_lm-\beta L(\phi)_ent) \quad \quad (16)$$

where $\beta$ represents the penalty coefficient for the entropy constraint.

Note when optimizing Equation (16), $\theta$ remains constant.

We then optimize LLM, corresponding to the inner minimization step in Equation (6). For an example ( $p, x, y)$, we get a challenging permutation from the previously optmized $P$-Net $\left(\hat{\phi}^{\star}\right), \Pi \sim$ $P$-Net $\left(\hat{\phi}^{\star} ;(p, x, y)\right)$. We compute the LLM's loss on this permuted example $(\Pi \cdot p, x, y)$, denoted by $\ell\left(\theta ; \hat{\phi}^{\star} ;(\Pi \cdot p, x, y)\right)$. The objective is to optimize the LLM parameters $\theta$ to minimize this loss:

$$\hat{\theta}^{\star}=\arg \max _{\theta \in \Theta} L\left(\hat{\phi}^{\star} ; \theta\right)_lm, \quad \quad (17)$$

Note when optimizing LLM, we incorporate the previously optimized parameter $\hat{\phi}^{\star}$ from the P-Net and keep it constant. From Equation (16) to (17), we complete a loop of iteration. In the next iteration, we substitute $\hat{\theta}^{\star}$ into Equation (16) for a new round of optimization until convergence.

We hope these explanation can address your questions and look forward to any additional comments you may have.

Learned Distribution ($P_\theta$): This represents the distribution learned by the LM parameterized by $\theta$ over the training data. To differentiate this from the empirical distribution (represented by bars), it is represented by a curves.

• In the ERM setting (left plot), the model tends to assign higher probabilities to the more frequently occurring permutations (0, 1, 4) and lower probabilities to the less frequent ones (2, 3, 5). This bias can lead to performance degradation when permutations unseen during training occur during inference.
• In the DRO setting (right plot), the model is trained to perform well across all possible permutations by considering the worst-case scenario over the ambiguity set $\mathcal{Q}$ (as shown in Equation (6) in the manuscript), thereby assigning a more balanced probability across all forms of the data (0-5) and mitigating the issue of unseen permutations during inference.

The left and right plots share the empirical distribution $\hat{P}$ (depicted as bars) and differ in the learned distribution $P_\theta$ (depicted as curves) influenced by different learning algorithm used ((a) ERM, (b) DRO). All instances of $P$ in the figures should be capitalized to maintain consistency.

We have revised Figure 2 and its caption, as well as the corresponding text in the manuscript, to incorporate these explanations and improve clarity.

Response to Hyperparameter Selection

Thank you for highlighting the need for a clearer explanation of our hyperparameter selection. We have added a detailed description of our hyperparameter tuning process in Appendix C.3 and D of the manuscript.

The analysis of the hyperparameters for P-Net, specifically those associated with Optimal Transport (OT)—temperature, iteration coefficient, and entropy-constrained coefficient—was conducted through a grid search. These hyperparameters were selected based on average validation performance. The results of this analysis were previously reported and can be found in Appendix D, "Analysis of Hyperparameters." P-Net’s other basic hyperparameters such as batch size follows common configurations and are listed in Appendix C.3.

For the basic hyperparameters of the LLM, such as learning rate and batch size, we adopted common configurations from SFT. Furthermore, the LoRA hyperparameters were set according to the recommended settings from LlamaFactory [5]. These parameters were consistently maintained across all experimental groups to ensure a fair comparison. These are also are listed in Appendix C.3.

Additionally, we plan to open-source our code and models to enable further research by the community.

[5] https://github.com/hiyouga/LLaMA-Factory

Response to Question on ROUGE-L

Thank you for raising this question about the evaluation metrics. We would like to explain the calculation of ROUGE-L and justify its usage in our work.

The ROUGE-L metric is calculated as follows:

$R_L = \frac{\text{LCS}(X,Y)}{|X|}$ $P_L = \frac{\text{LCS}(X,Y)}{|Y|}$ $F_L = \frac{(1 + \beta^2)R_L P_L}{R_L + \beta^2 P_L}$

where:

• $X$ is the reference text.
• $Y$ is the hypothesis text.
• $\text{LCS}(X,Y)$ is the length of the longest common subsequence between $X$ and $Y$
• $|X|$ and $|Y|$ are the lengths of $X$ and $Y$, respectively.
• $\beta$ is a parameter that determines the relative importance of precision and recall.

We chose ROUGE-L as our evaluation metric for two main reasons:

1. Standard Usage in Natural Instruction Benchmarks: It is the standard evaluation metric used in Natural Instruction benchmarks (v1 and v2) [6,7], from which we sourced our instruction tuning data. This metric provides a unified evaluation framework by treating all tasks as generation tasks.

2. Strong Correlation with Classification Accuracy: For classification tasks, ROUGE-L shows strong correlation with accuracy metrics. The Natural Instruction benchmark [4] reported a Pearson correlation coefficient of 0.97. Our independent validation on the COLA dataset (using 50 samples) showed a correlation coefficient of 0.98.

We hope these explanations can address your question.

[6] Cross-Task Generalization via Natural Language Crowdsourcing Instructions. ACL 2022

[7] SUPER-NATURALINSTRUCTIONS: Generalization via Declarative Instructions on 1600+ NLP Tasks. EMNLP 2022

Table 5. Experiments on Gemma-7B

Response to Questions on Threshold τ and Number of Examples n

Thank you for pointing this out. You are correct that the performance drop is influenced significantly by the number of in-context examples, n. As n increases, the number of possible permutations increases factorially (n!), which raises the likelihood of encountering permutations that degrade the model's performance.

The threshold τ is used in our study to determine whether an attack on a sample is considered successful. Specifically, we define an attack as successful if the performance drop exceeds τ. Therefore, τ itself does not influence the actual performance drop but serves as a criterion for measuring the impact of different permutations on the model's output.

We have expanded on this explanation in the revised manuscript to clarify the roles of τ and n in our analysis.

Response to Calculations of $\mu_i$ and $\omega_i$ in in Equation (1)

Thank you for your inquiry regarding the calculations in Equation (1). We apologize for any confusion caused by the original presentation. We have revised the formulas in the manuscript for better clarity.

Given a task $D={(p_i, x_i, y_i)}$, where $p_i$ represents an ICL prompt containing n demonstrations, we define a sample $\left(p_i, x_i, y_i\right)$ as successfully attacked if its relative performance degradation induced by a attacher exceeds a threshold $\delta \in[0 \%, 100 \%]$.

We denote the set of all possible permutations of the $p_i$ demonstrations as $\mathbb{P}=\\\{Pi_0, \ldots, \Pi_{n!-1}\\\}$, where $|\mathbb{P}|=n!$. Let $g$ be a performance metric function (e.g., ROUGE-L). The ASR for a dataset $D$ is defined as:

$$\operatorname{ASR}(D, \delta)=\frac{1}{|D|} \sum_{i=1}^{|D|} \mathbb{I}\left(\frac{\mu_i-\omega_i}{\mu_i} \geq \delta\right)$$

where $\mathbb{I}$ denotes the indicator function, $|D|$ is the size of the dataset, and $\delta$ is the threshold.

• Average Performance $\mu_i$: The expected performance over all permutations:

$$\mu_i=\mathbb{E}_{\Pi \sim \mathbb{P}}[g(\Pi \cdot p_i, x_i ; y_i)]$$

• Compromised Performance $\omega_i$: The performance under attack.

For Exhaustive Search Attacks, the attacked performance is calculated by testing all possible permutations of demonstrations in $Q_i$ and identifying one that yields the poorest performance:

$$\omega_i=\min _{\Pi \in \mathbb{P}} g\left(\Pi \cdot p_i, x_i ; y_i\right)$$

For Neural Search Attacks, the P-Net generates the most challenging permutation $\Pi_i$ for each sample $(p_i, x_i, y_i)$, and the attacked performance is calculated as:

$$\omega_i=g\left(\Pi_i \cdot p_i, x_i ; y_i\right), \quad s.t. \Pi_i \sim \mathrm{PNet}\left(p_i, x_i, y_i\right)$$

We have detailed these calculations in Section 3, Equations (1-4) of our manuscript. Thank you again for pointing the ambiguity.

We hope this clarification addresses your concerns regarding how $\mu_i$ and $\omega_i$ are computed.

Response to Question on Figure 2

We apologize for the confusion caused by Fig. 2 and its accompanying description.

Fig. 2 illustrates the different behaviors of ERM and DRO on less frequent but valid permutations. To this end, we distinguish between two types of distributions:

Empirical Distribution ($\hat{P}$): This represents the observed distribution of the data in the training corpus. For a 3-shot training example $(p,x,y)$, where prompt $p$ contains three demonstrations, there are six possible permutations, denoted as $\{(p^0, x, y), \ldots, (p^5, x, y)\}$. These permutations are indexed from 0 to 5. The bars in Fig. 2 shows the probability of each permutation occurring in the training corpus. Specifically, permutations 0, 1, and 4 appear in the training data with frequencies $\hat{P}(p^0, x, y) > \hat{P}(p^4, x, y) > \hat{P}(p^1, x, y)$, while permutations 2, 3, and 5 do not appear, hence $\hat{P}(p^2, x, y) = \hat{P}p^3, x, y) = \hat{P}(p^5, x, y) = 0$.

continue...

Dear Reviewer n5jf,

We hope this message finds you well.

This is a kind reminder that the discussion phase of the review process is ending soon.

We have carefully addressed your insightful comments and suggestions in our response, including detailed explanations, discussions, and new experimental results. Based on your feedback, we have made detailed revisions to the manuscript, particularly in Sections 3 and 4, to clarify the threat model and enhance the description of our proposed method.

Your feedback is crucial in helping us confirm whether we have appropriately addressed the issues and suggestions you raised. We would greatly appreciate any updates or further feedback from you. Your insights and expertise are invaluable to us, as we aim to address any outstanding concerns and improve our submission.

Thank you for your time and attention. We look forward to hearing from you soon.

Best regards,

Authors

Dear Reviewer n5jf,

As today is the deadline for our manuscript revisions, we kindly seek your feedback on our responses and the revised manuscript. We deeply appreciate the time and effort you invested in providing detailed and thoughtful comments on our work.

In return, we have worked diligently to address each of your concerns point-by-point, culminating in a comprehensive 7-page response along with careful revisions to the manuscript. We sincerely hope these efforts align with your expectations and address your concerns thoroughly.

We would be truly grateful if you could review our responses in your busy time and let us know if they sufficiently address your feedback. Your input is invaluable to us.

Best regards,

Authors

Dear Reviewer n5jf,

We noticed that we haven't yet received your feedback on our submitted response to your review. As the discussion phase is ending in the next three days, we would particularly appreciate your thoughts on our clarifications.

In our response, we have:

1. Thoroughly clarified your main concern about the practicality of our threat model setting: We have explained that our model follows the standard two-party setting (between an attacker and a defender) widely considered in the field of adversarial attacks for LLMs, which does not require network interception techniques as in a three-party setting. (Modified Section 3)

2. Provided detailed explanations for other technical questions you raised regarding adversarial training, DRO, Gumbel sampling and OT techniques. (Modified Sections 3 and 4)

3. Added new experimental results and made other necessary revisions as suggested. (Modified Section 3, Added Appendices E and G)

For your convenience, we have highlighted these changes in blue in the manuscript.

We believe we have addressed your primary concerns and would greatly value your feedback on these points if there are any outstanding questions.

Best regards,

Authors

Dear Reviewer n5jf,

This is a kind reminder that the discussion phase of the review process is ending soon.

Thank you for your time and initial review. We look forward to hearing from you.

Best regards,

Authors

Dear Reviewer n5jf,

We notice that we haven't received your feedback on our response yet. We look forward to hearing from you.

Best regards,

Authors

Response to Q3: Regarding the Architecture Improvements

Thank you for your insightful question. Your suggestion is indeed an interesting idea. However, implementing demonstrator-wise permutation invariance by masking examples so that no example can attend to another is challenging within the current Transformer architecture. Transformers rely on autoregressive attention modules present in every layer, making it difficult to completely isolate samples from one another. Additionally, preventing interactions between demonstrations may negatively impact the model's overall performance.

There is work exploring alternative architectures to address this issue. Preliminary research by (Chen et al. (2023)) shows that the DeepSet architecture exhibits better permutation invariance than Transformers. However, this MLP-based architecture is currently too limited to handle complex language modeling tasks. We have included this work in our related work section.

We hope this clarifies your concern.

Reference

[1] Chen et al., 2023, Positional Information Matters for Invariant In-Context Learning: A Case Study of Simple Function Classes

---

Thank you once again for your insightful comments, which has undoubtedly strengthened our work. We have updated our manuscript to reflect these changes, which are highlighted in orange for easy identification. We hope that our responses could effectively address your concerns, and we look forward to any further feedback you may have.

Thank you for your thoughtful and positive feedback on our work. We are delighted that you find our solution to be both intuitive and well-performing. Your acknowledgment of the elegance of our approach to handling the combinatorial explosion—using the Sinkhorn operator and Gumbel sampling—is particularly encouraging. We are also pleased that you found our paper to be clearly written and well-presented. We will address your comments and supplement our work with new experimental results.

Response to W1: Experiments on Many-shot Setting

Thank you for your suggestion. In response, we expanded our evaluations to 8, 16，32, and 64 shots. We were unable to test with 128 shots as most sequences exceeded the maximum sequence length of 8k for Llama3. The results for average and worst-case performance gains are reported in Table 1 below.

Table 1: Scaling to many-shot ICL.

As shown in Table 1, our method, PEARL, achieves notable worst-case performance gains ranging from 24% to 40% when generalizing to larger shot numbers (up to 64 shots) and longer sequences (up to 8k). This indicates that PEARL helps LLMs learn robust features that generalize well to many-shot ICL settings. Detailed results and visualizations have been updated in Section 6.2 and Appendix G of our manuscript, and these updates are distinctly marked in orange for easy identification.

Regarding "whether the proposed method is better than simply adding extra demonstrators," this can be seen from Figure 1 and Table 2 in the manu. As the number of shots increases, the worst performance generally shows a monotonic decline because more shots lead to more permutation variants, which are likely to further reduce worst-case performance. In contrast, our method is able to improve the worst-case performance.

We hope these additional results substantiate the generalizability of our method and adequately address your concerns.

Response to W2: Comparison With Best Ordering Performance

Thank you for your question. Exploring the best-case performance scenario is indeed intriguing. Although our methodology was initially designed to optimize for pessimistic (worst-case) scenarios, we have also included an evaluation of the best-case performance for both PEARL and ERM to provide a balanced perspective. The results are shown in the Table 2 below.

Table 2: Best performance comparison between ERM and PEARL.

As shown in Table 6, across all datasets and for every shot condition, PEARL's best-case performance consistently exceeds that of ERM. These results indicate that PEARL not only significantly improves the worst-case performance but also achieves stable improvements in the best-case performance.

We have included these findings in Appendix G of our paper to provide a more comprehensive evaluation of our model.

Thank you once again for your thoughtful engagement and valuable suggestion.

Response to Q1: Formatting Corrections

Thank you for your careful review and for pointing out the inaccuracies. We have updated the manuscript accordingly. Your meticulous feedback has undeniably enhanced the clarity of our presentation.

Response to Q2: Clarification on P-Net's Adaptability to Various Shot Sizes

Thank you for your question. To clarify, our P-Net does not require a separate model for each number of demonstrators. It is designed to handle varying numbers of shots effectively within a single model.

This capability stems from its underlying transformer architecture, which is adept at processing sequences of variable lengths. In the context of P-Net, the number of shots provided corresponds to the sequence length that the transformer processes. As shown in Equations (9) and (10) of our paper, increasing the number of shots does not change the number of parameters in the model. This flexibility enhance its scalability and practical implementation.

We appreciate your thoughtful question and hope this clarifies the adaptability of P-Net.

Thank you for your insightful and positive feedback on our work. We are delighted that you find our proposed method, PEARL, to be both elegant and practical for practitioners as part of their fine-tuning pipeline. Your recognition of the noticeable gains in both average and worst-case performance is highly encouraging. We appreciate your acknowledgment that our approach does not incur any additional inference-time overhead. Additionally, we are pleased that you find the clarity and presentation of our paper to be strong. We will address your comments sequentially and supplement our work with new experimental results and discussions.

Response to W1: Experiments on Diverse LLMs

Thank you for your suggestion. In response, we expanded our experiments to include four additional models: Llama 2 7B and 13B (from the previous generation), Mistral 7B v0.2, and Gemma 7B. The results are presented in Tables 1-4 and have been added to Appendix F of the manuscript. Key Discoveries are as follows:

• Sensitivity to Permutations Across Different LLM Families: We observed that different LLM families exhibit varying sensitivities to permutations. Overall, the sensitivity ranking is Llama > Gemma > Mistral. Despite this variance, the phenomenon remains significant, with performance drops exceeding 10 percentage points in most cases.

• Effectiveness of Our Method: For cases involving three or more shots, our method consistently achieved improvements exceeding 10% in worst-case performance. This validates the effectiveness of our approach.

We appreciate your suggestion and hope that the expanded results can addresses your concerns.

Table 1. Experiments on Llama2-7B. Average and per-task performance are reported, with performance gains (%) shown in parentheses.

Table 2. Experiments on Llama2-13B

Table 3. Experiments on Mistral 7B v0.2

continued...

Response to W3: Formatting Corrections

Thank you for your careful review and for pointing out the inaccuracies. We have updated Equation (1) and the formatting in the Algorithm section of our manuscript accordingly. Your meticulous feedback has undeniably enhanced the clarity of our presentation.

Response to Q1: Clarification About Matrix W

Thank you for your question. We apologize for any confusion caused by our unclear description initially. To clarify, the matrix $W$ mentioned is not a projection matrix, but rather a normal parameter matrix. Its function is to map the representations $H$ of the demonstrations into a new space for further interaction. We regret any confusion caused and have updated our manuscript accordingly.

Response to Q2: Explanation Regards the Performance of ERM+DS/IM

Thank you for your question. The decrease in average-case performance for the ERM+DS and ERM+IM baselines can be attributed to the trade-off between robustness and accuracy inherent in these methods.

Instance Mixupintroduces new samples by linearly interpolating between existing examples. While this approach can enhance robustness by providing more varied training data and mitigating overfitting, it also introduces noise that can obscure meaningful patterns in the original data. This added noise may hinder the model's ability to learn crucial relationships, leading to decreased average-case performance. Demonstration Shuffling can be considered a gentler version of Instance Mixup, which is why its decline is smaller.

In essence, both methods aim to improve robustness but may inadvertently compromise accuracy due to the introduction of noise (in the case of Mixup) or loss of beneficial ordering (in the case of Demonstration Shuffling). Our experimental results indicate that these simple learning strategies struggle to achieve an good balance between robustness and accuracy.

We hope this explanation clarifies the observed performance of the ERM+DS and ERM+IM baselines. Please feel free to reach out with any further questions.

---

Thank you once again for your insightful comments, which has undoubtedly strengthened our work. We have updated our manuscript to reflect these changes, which are highlighted in orange for easy identification. We hope that our responses could effectively address your concerns, and we look forward to any further feedback you may have.

Table 4. Experiments on Gemma-7B

Response to W2: Experiments on Many-shot Setting

Thank you for your suggestion. In response, we expanded our evaluations to 8, 16，32, and 64 shots. We were unable to test with 128 shots as most sequences exceeded the maximum sequence length of 8k for Llama3. The results for average and worst-case performance gains are reported in Table 5 below.

Table 5: Scaling to many-shot ICL.

As shown in Table 5, our method, PEARL, achieves notable worst-case performance gains ranging from 24% to 40% when generalizing to larger shot numbers (up to 64 shots) and longer sequences (up to 8k). This indicates that PEARL helps LLMs learn robust features that generalize well to many-shot ICL settings.

Detailed results and visualizations have been updated in Section 6.2 and Appendix G of our manuscript, and these updates are distinctly marked in orange for easy identification.

We hope these additional results substantiate the generalizability of our method and adequately address your concerns.

Response to W3: Explanation About Optimal Transport

Thank you for your question. We provide an alternative interpretation of our modeling approach from a graph-theoretic view. The OT modeling implemented by the P-Net can be understood in two parts:

1. Parametric part: This acts as a feature extractor that takes $n$ demonstrations, producing their sentence representations $H \in \mathbb{R}^{n \times h}$, where $h$ is the dimensionality of the representations. Pairwise relationships among the demonstrations are modeled using a layer of cross-demonstration interaction:

   $\mathbf{R}=g\left(H W H^{\top}\right)$, where $W$ is a $d \times d$ weight matrix, and $g$ is a nonlinear activation function. The output matrix $\mathbf{R} \in \mathbb{R}^{n \times n}$ can be interpreted as an adjacency matrix. In this graph-theoretic view, the nodes represent demonstrations, and the relationship between nodes $i$ and $j$ is denoted by the edge $R_{ij}$. Here, we define $R_{ij}$ as the potential increase in difficulty for the LLM if demonstrations $i$ and $j$ are swapped; a higher value of $R_{ij}$ indicates that swapping these two demonstrations may significantly increase the task's difficulty. However, the current gap is that $R$ is not yet a probability distribution.

2. Non-parametric part: We employ the Sinkhorn algorithm to transform $\mathbf{R}$ into a probability distribution. This is achieved by normalizing each row and column iteratively until the matrix $\mathbf{R}$ approximately converges to a doubly stochastic matrix or the sinkhorn distribution. This corresponds to Equations (11-12) in our paper. Following this, we would like to sample a permutation matrix from this distribution, and the permutation matrix indicates which elements among the $n$ demonstrations should be swapped—entry '1' indicates a swap, and '0' indicates no swap. The sampling method used is Gumbel sampling, as described in Equation (13).

Together, parts (1) and (2) comprise the entirety of P-Net. This allows the process of permutation mapping (from the input permutation to the target permutation) to be fully differentiable.

To further ensure that the outputing permutation matrix presents a challenge to the LLM, we conduct adversarial training between P-Net and the LLM (Section 4.3).

We have updated this explanation in Section 4.2 OT of our manuscript, hoping it will aid in better understanding the processes involved.

Thank you for your insightful and positive feedback. We appreciate your recognition of our method as a unique approach that combines distributionally robust optimization (DRO) using optimal transport (OT) with min-max learning to enhance the robustness of ICL against permutations. We are also pleased that you noted our attacker model's favorable computational complexity and the effectiveness of our robust learning method in outperforming baseline approaches. We will now address your comments sequentially and supplement our work with new experimental results and discussions.

Response to W1: Related Work Discussion

Thank you for pointing out the omission in our related work section. We have improved this section to better situate our work within the existing literature.

Current research on order sensitivity in in-context learning can be divided into three categories: structural improvements, training-stage methods, and inference-stage methods.

Most training-stage methods focus on improving general performance in ICL [1,2] while neglecting robustness to permutations of demonstrations. Recent studies suggest that this phenomenon stems from the autoregressive nature of Transformer language models [3,4]. InfoAC [4] introduces contrastive learning during fine-tuning to break the autoregressive constraint and enable bidirectional token visibility; however, their approach achieves limited success and is restricted to classification tasks. Preliminary work by [3] seeks for structural improvements and they shows the DeepSet architecture exhibits better permutation invariance than the Transformer; however, this MLP-based new architecture is too small to solve complex language modeling tasks.

Inference-stage methods can be categorized into four types:

• Demonstration selection [5,6], which primarily enhances normal-case performance without guaranteeing worst-case performance under permutations;
• Output calibration [7-9], which proves effective for classification tasks but is less applicable to generation tasks due to sequence calibration challenges;
• Order optimization [10], which aims to find the best ordering during inference but suffers from exponential computational complexity;
• Prediction ensembling [11], a recent work proposes transforming an $n$-shot ICL into $n$ one-shot predictions and ensembling the results; while effective for classification, this approach leads to decreased performance on generation tasks.

In summary, inference-stage methods aim to circumvent order sensitivity by pre-/post-processing without fundamentally enhancing the robustness of LLMs to different orders. Moreover, most methods are designed for classification tasks and show reduced effectiveness on generation tasks.

To the best of our knowledge, our work is the first to address this problem from an adversarial perspective. We propose a novel distributionally robust optimization (DRO)-based learning algorithm to enhance the inherent robustness of LLMs against order perturbations, and we solve it using the Sinkhorn operator. Our approach complements existing inference-stage methods and generalizes across diverse task categories.

We have updated the related work section in our manuscript accordingly. We hope this addresses your concern, and we appreciate your suggestion, which has helped us improve the rigor of our work.

Reference:

[1] Min et al., 2022, MetaICL: Learning to Learn In Context

[2] Wei et al., 2023, Symbol tuning improves in-context learning in language models

[3] Chen et al., 2023, Positional Information Matters for Invariant In-Context Learning: A Case Study of Simple Function Classes

[4] Xiang et al., 2024, Addressing Order Sensitivity of In-Context Demonstration Examples in Causal Language Models

[5] Chang et al., 2023, Data Curation Alone Can Stabilize In-context Learning

[6] Peng et al., 2024, Revisiting Demonstration Selection Strategies in In-Context Learning

[7] Zhao et al., 2021, Calibrate Before Use: Improving Few-shot Performance of Language Models

[8] Li et al., 2023, Distinguishability Calibration to In-Context Learning

[9] Guo et al., 2024, What Makes a Good Order of Examples in In-Context Learning

[10] Lu et al., 2022, Fantastically Ordered Prompts and Where to Find Them: Overcoming Few-Shot Prompt Order Sensitivity

[11] Zhang et al., 2024, Batch-ICL: Effective, Efficient, and Order-Agnostic In-Context Learning

Response to W2: Baseline Comparisons

Thank you for highlighting these important baselines. We have added comparisons with these methods in our updated manuscript. Since CurStable ([5] Chang et al., 2023) and Batch-ICL ([11] Zhang et al., 2024) are inference-based methods and are complementary to our approach, we have not only compared our method with them but also considered combining our method with theirs. The new results are presented in Table 1 (also updated in Table 2 in the manuscript).

Our comparisons show that PEARL achieves superior performance compared to both training-stage and inference-stage methods. Among inference-stage methods, Batch-ICL boosts both average and worst-case performance on classification tasks (CSQA, CoLA); however, it exhibits limited or negative effects on generation tasks (CurDial, TMW), limiting its applicability. In contrast, CurStable, through demonstration selection, performs well on both task types. Moreover, combining PEARL with inference-stage methods further improves performance.

We hope that these additional baseline comparisons effectively address your concern.

Table 1: Average and worst-case performance with added baselines. Performance gain (%) are in parentheses.

Response to W3: Clarification of The Contribution

Thank you for your insightful comment. We apologize for any confusion caused by our phrasing. In Section 3, our goal is not to introduce the vulnerability of LLMs to input permutations as a new discovery but to revisit and empirically assess this issue in the context of current SOTA open-source models. We focus on validating the two questions to motivate our research:

1. Has order sensitivity been resolved in latest SOTA open-source LLMs like Llama 3? If not, what is its severity?
2. Can this vulnerability be exploited as a new means of attack to perturb LLMs, and how effective could such attacks be?

By investigating these questions, we aim to highlight the ongoing significance of order sensitivity in modern LLMs, underscoring the necessity for robust solutions. This examination sets the stage for our main contribution: proposing a novel method to enhance the robustness of LLMs against input permutation perturbations.

We have also revised the phrasing in the manu and we hope it can address your concerns.

Response to Q1: Missing Citations

Thank you for noting these missing citations. We have added it to the manuscript.

Response to Q2: Novel of Attack Methods and Comparative Analysis

Thank you for your thoughtful comment. We acknowledge that this concern may also relate to Weakness 3. In our revisiting section, we seek to explore adversarial attacks on ICL based on permutations, thereby introducing this new attack scenario. To the best of our knowledge, there are currently no existing attack methods specifically designed for the proposed permutation-based attack scenario.

Existing adversarial attacks on prompts and ICL mainly fall into two categories:

1. Prefix/Suffix Optimization: Methods that optimize a prefix or suffix to explicitly prepend or append to the prompt [12,13,14].

2. Noise Perturbation in Samples: Methods that introduce noise perturbations into the ICL demonstration samples [15].

However, these methods cannot be directly applied to permutation-based attack scenarios because learning to generate permutations that can maximize adversarial impact is a non-trivial problem. Besides exhaustive search, we propose a neural-based attack that utilizes a neural network equipped with optimal transport (OT) to learn adversarial permutations.

Our assessment of the severity of attacks in this new scenario is to highlight the need for robust solutions. This motivates our main contribution: introducing a DRO-based learning algorithm to enhance the inherent robustness of LLM’s ICL abilities.

We hope that this explanation can address your concerns, and we look forward to any further feedback you may have.

Reference

[12] Universal and Transferable Adversarial Attacks on Aligned Language Models. 2023

[13] Tricking LLMs into Disobedience: Understanding, Analyzing, and Preventing Jailbreaks 2023

[14] Hijacking Large Language Models via Adversarial In-Context Learning. 2023

[15] Data Poisoning for In-context Learning. 2024

Response to Q3: Discussion and Comparison with Recent Baselines

Thank you for raising this point. We have incorporated them into the responses to Weaknesses 1 and 2, as well as into the updated manu. We hope this can address your questions.

---

Thank you once again for your insight comments, which has undoubtedly strengthened our work. We have updated our manuscript to reflect these changes, which are highlighted in orange for easy identification. We hope that our responses could effectively address your concerns, and we look forward to any further feedback you may have.