1. Bibliographic Information

1.1. Title

PEARL: Towards Permutation-Resilient LLMs

1.2. Authors

Liang Chen, Li Shen, Yang Deng, Xiaoyan Zhao, Bin Liang, Kam-Fai Wong

Affiliations:

• The Chinese University of Hong Kong: Liang Chen, Xiaoyan Zhao, Bin Liang, Kam-Fai Wong
• Shenzhen Campus of Sun Yat-sen University: Li Shen
• SMU: Yang Deng

1.3. Journal/Conference

This paper is published at arXiv, which is a preprint server for scientific papers. It is indicated as a preprint (v1) and its publication status beyond this is not specified. arXiv is a highly influential platform for rapid dissemination of research in various scientific fields, including artificial intelligence and natural language processing.

1.4. Publication Year

2025 (Based on the UTC timestamp 2025-02-20T15:07:02.000Z)

1.5. Abstract

The abstract outlines the critical vulnerability of Large Language Models (LLMs) in in-context learning (ICL): their predictions are highly sensitive to the ordering of demonstrations. This sensitivity can be exploited by a "natural attack" through simple permutation of demonstrations, achieving nearly an 80% success rate on models like LLaMA-3. Existing mitigation methods often rely on post-processing or architectural modifications, failing to enhance the LLM's inherent robustness to input permutations. To counter this, the paper proposes Permutation-resilient learning (PEARL), a novel framework based on distributionally robust optimization (DRO). PEARL optimizes model performance against the worst-case input permutation. It comprises a permutation-proposal network (P-Net) and the LLM. The P-Net identifies challenging permutations by treating it as an optimal transport problem, solved using an entropy-constrained Sinkhorn algorithm. Through minimax optimization, the P-Net and LLM iteratively train, progressively improving the LLM's robustness. Experiments on synthetic pre-training and real-world instruction tuning tasks demonstrate PEARL's effectiveness in mitigating permutation attacks and enhancing performance. Notably, PEARL shows significant performance gains (up to 40%) in many-shot and long-context scenarios, even when trained on fewer shots and shorter contexts, highlighting its efficiency and generalization capabilities.

1.6. Original Source Link

https://arxiv.org/abs/2502.14628

1.7. PDF Link

https://arxiv.org/pdf/2502.14628v1.pdf

2. Executive Summary

2.1. Background & Motivation

The core problem the paper aims to solve is the permutation sensitivity of in-context learning (ICL) in Large Language Models (LLMs). While ICL allows LLMs to perform complex tasks by learning from demonstrations, the effectiveness of this learning is highly unstable and dependent on the specific order in which these demonstrations are presented.

This problem is critically important in the current field due to several reasons:

• Instability in Predictions: The unpredictability stemming from demonstration ordering makes LLMs less reliable and harder to control for consistent performance.

• Challenges for Prompt Engineering: Practitioners struggle to engineer effective prompts because a slight change in demonstration order can drastically alter model behavior, hindering the development of robust LLM applications.

• Security Vulnerability: The paper highlights that this sensitivity can be exploited as a "natural attack." A malicious actor can degrade LLM performance by simply reordering demonstrations, without altering their content. Such attacks are difficult for model providers to detect, posing significant safety and reliability concerns. Existing mitigation methods are often post-processing techniques or architectural changes, which incur additional inference overhead or lack scalability, failing to address the fundamental lack of inherent robustness to input permutations within the LLM itself.

  The paper's entry point or innovative idea is to address this vulnerability from a fundamental learning perspective using Distributionally Robust Optimization (DRO). Instead of superficial fixes, PEARL (Permutation-resilient learning) focuses on making the LLM inherently robust by training it to perform well even under the worst-case permutations of demonstrations, thereby enhancing its resilience against such attacks and improving overall reliability.

2.2. Main Contributions / Findings

The paper makes several significant contributions:

• Demonstration of Permutation Vulnerability as an Attack: The authors empirically show that even advanced LLMs like LLaMA-3 are highly susceptible to simple permutation-based attacks, with success rates approaching 80%. This re-frames permutation sensitivity not just as a performance quirk but as a critical security vulnerability.

• Introduction of PEARL Framework: They propose Permutation-resilient learning (PEARL), a novel training framework based on Distributionally Robust Optimization (DRO). This framework is designed to explicitly optimize LLM performance against the most challenging input permutations.

• Novel Permutation-Proposal Network (P-Net): PEARL introduces a P-Net that acts as an adversary. This P-Net is designed to generate the "worst-case" permutations by formulating the problem as an optimal transport problem, which is efficiently solved using an entropy-constrained Sinkhorn algorithm.

• Minimax Optimization for Robustness: The P-Net and the LLM are trained together through minimax optimization, where P-Net maximizes the LLM's loss by finding difficult permutations, and the LLM minimizes its loss, thereby learning to be robust to these challenging orders. This adversarial training progressively enhances the LLM's inherent robustness.

• Empirical Validation and Performance Gains: Experiments on synthetic pre-training tasks (linear functions) and real-world instruction tuning tasks (Super-Natural Instructions) demonstrate PEARL's effectiveness.

  • It successfully mitigates permutation attacks and significantly improves both average and worst-case performance.
  • Notably, PEARL-trained models exhibit strong generalization capabilities, achieving performance gains of up to 40% when scaled to many-shot and long-context scenarios, even though they were trained on fewer shots and shorter contexts.
  • PEARL also improves shot efficiency, allowing models to achieve comparable average performance with two to four times fewer shots than ERM baselines.

• Generalizability Across LLMs: The method's effectiveness is shown across different LLM families, including Llama, Gemma, and Mistral models, indicating its broad applicability.

  These findings address the critical issue of permutation sensitivity by providing a robust, training-stage solution that enhances the intrinsic reliability and security of LLMs in ICL settings.

3. Prerequisite Knowledge & Related Work

3.1. Foundational Concepts

To fully understand the PEARL framework and its implications, a beginner should be familiar with the following core concepts:

• Large Language Models (LLMs): These are advanced artificial intelligence models, typically based on the Transformer architecture, trained on vast amounts of text data. They are capable of understanding, generating, and processing human language for a wide range of tasks, from translation to creative writing. Examples include GPT-3, LLaMA, and Mistral.

• In-Context Learning (ICL): A powerful capability of LLMs where the model learns a new task or adapts its behavior from a few examples provided directly within the input prompt, without requiring explicit weight updates or fine-tuning. For instance, to classify sentiment, one might provide a few examples like "Movie was great. -> Positive" followed by "Movie was bad. -> Negative" before asking the model to classify a new sentence. The examples are called demonstrations or shots.

• Permutation Sensitivity: This refers to the phenomenon where the performance or output of an LLM changes significantly when the order of the demonstrations within the ICL prompt is altered, even if the content of the demonstrations remains the same. This implies a lack of order invariance or permutation invariance, which is often desired for robust AI systems.

• Distributionally Robust Optimization (DRO): A framework in optimization that aims to find solutions that perform well under the worst-case probability distribution within a predefined set of plausible distributions, known as an ambiguity set. Unlike standard optimization (like Empirical Risk Minimization which optimizes for the observed training data), DRO provides stronger guarantees against distributional shifts and uncertainties. In the context of this paper, the uncertainty lies in the order of ICL demonstrations.

• Optimal Transport (OT): A mathematical theory that deals with efficiently moving a "pile of dirt" from one shape to another, minimizing the total cost of transportation. More formally, it provides a way to define a distance (like the Wasserstein distance) between probability distributions. In this paper, OT is used to model how to transform one distribution of permutations (e.g., random orderings) into a "worst-case" distribution of permutations that challenges the LLM.

• Sinkhorn Algorithm: An iterative algorithm used to approximate solutions to optimal transport problems, particularly for finding doubly stochastic matrices. A doubly stochastic matrix is a square matrix of non-negative real numbers where the sum of each row and each column is 1. In PEARL, it helps transform a relationship matrix into a probability distribution over permutations.

• Minimax Optimization: A type of optimization problem structured as a game between two players, often called a "min-max" game. One player (the "minimizer") tries to minimize an objective function, while the other player (the "maximizer") tries to maximize the same objective function. In PEARL, the P-Net (maximizer) tries to find the worst-case permutation to maximize the LLM's loss, while the LLM (minimizer) tries to improve its performance to minimize this worst-case loss. This adversarial process drives both components to improve.

• Empirical Risk Minimization (ERM): The standard training paradigm in machine learning, where a model is trained to minimize its average loss on the observed training data. While effective for many tasks, ERM models can be brittle to inputs that differ significantly from the training distribution, as highlighted by permutation sensitivity.

• ROUGE-L (Recall-Oriented Understudy for Gisting Evaluation - Longest Common Subsequence): A common metric used to evaluate the quality of text summaries or generated text by comparing it to a reference text. ROUGE-L specifically measures the longest common subsequence (LCS) between the generated and reference texts, reflecting their structural similarity. A higher ROUGE-L score indicates greater similarity.

3.2. Previous Works

The paper contextualizes PEARL by discussing existing approaches to ICL and permutation sensitivity:

• Order Sensitivity in ICL:

  • Zhao et al. (2021), Lu et al. (2022), Reynolds & McDonell (2021) established the problem of LLMs' sensitivity to demonstration permutations.
  • This is seen as a fragility in LLMs despite their ICL capabilities.

• Existing Mitigation Methods (Training-Stage):

  • Improving General Performance: Most ICL research (Min et al., 2022; Wei et al., 2023) focuses on normal-case performance without specifically targeting permutation robustness.
  • Architectural Modifications:
    • Xiang et al. (2024) (InfoAC): Attempts to modify training objectives using contrastive learning to mitigate limitations of transformers' unidirectional attention, aiming for bidirectional token visibility. However, it showed limited success and was restricted to classification tasks.
    • Chen et al. (2023b): Explored permutation-equivariant architectures like DeepSet, which showed better permutation invariance. However, such MLP-based architectures are often too small and lack the scalability for complex language modeling tasks compared to Transformers.

• Existing Mitigation Methods (Inference-Stage): These methods modify the input or output during inference, introducing additional computational overhead per inference call, thus limiting practicality.

  • Demonstration Selection: (Chang & Jia, 2023; Peng et al., 2024) Aims to select the "best" demonstrations to improve normal-case performance but lacks worst-case guarantees under permutations.
  • Output Calibration: (Zhao et al., 2021; Li et al., 2023; Guo et al., 2024a) Effective for classification tasks but less applicable to generation tasks due to challenges in sequence calibration.
  • Order Optimization: (Lu et al., 2022) Tries to find the best ordering of demonstrations during inference, but this involves an exponential search space (n!), making it computationally prohibitive for many demonstrations.
  • Prediction Ensembling: (Zhang et al., 2024) Transforms n-shot ICL into n one-shot predictions and ensembles the results. While effective for classification, it can harm generation tasks.

• Distributionally Robust Optimization (DRO):

  • Previous applications of DRO (Ben-Tal et al., 2013; Lam & Zhou, 2015; Duchi et al., 2016; Miyato et al., 2018) have focused on distributional shifts like label shift (Hu et al., 2018), data source shift (Oren et al., 2019), and group shift (Sagawa et al., 2020). This paper is the first to apply DRO to ICL robustness by defining the ambiguity set over permutations.

• Optimal Transport (OT):

  • Fundamental mathematical discipline (Monge, 1781; Kantorovich, 1942) used for distribution matching (Montesuma et al., 2024; Xiao et al., 2024).
  • Mena et al. (2018) explored learning permutation structures through neural networks for tasks like sorting. This paper extends this by applying OT in the context of LLMs to generate challenging permutations.

3.3. Technological Evolution

The evolution of ICL has seen a progression from focusing on simply achieving few-shot performance to addressing its inherent instabilities. Initially, the success of Transformers and the ICL paradigm (Brown et al., 2020) demonstrated powerful learning from examples. However, early research quickly identified fragilities, such as sensitivity to the choice and order of demonstrations.

The first wave of solutions typically involved inference-stage heuristics (like demonstration selection or output calibration) or minor training tweaks. These methods, while sometimes effective, often added inference overhead or were limited to specific task types (e.g., classification). A parallel line of work explored architectural changes (e.g., DeepSet) to enforce permutation invariance, but these were often less powerful or scalable than the dominant Transformer architecture.

This paper's work (PEARL) represents a significant step in this evolution by integrating a robust optimization principle (DRO) directly into the LLM's training loop. Instead of fixing the output or modifying the architecture, PEARL aims to make the LLM learn to be inherently robust to permutations. It leverages advances in optimal transport for efficiently generating adversarial permutations, moving beyond simple random shuffling or exhaustive search. This places PEARL within the cutting edge of LLM robustness research, as it addresses a core vulnerability from a principled, training-stage perspective that preserves the Transformer architecture and its autoregressive objective, thereby maintaining scalability.

3.4. Differentiation Analysis

Compared to the main methods in related work, PEARL offers several core differences and innovations:

• Training-Stage, Inherent Robustness vs. Post-Processing:

  • Difference: Most existing mitigation methods are inference-stage (e.g., demonstration selection, order optimization, output calibration). They modify prompts or outputs during inference, adding computational overhead and not improving the model's fundamental understanding of permutation-invariant patterns.
  • Innovation: PEARL is a training-stage method. It fundamentally alters how the LLM learns, making it inherently robust to permutations. Once trained, a PEARL LLM can handle various demonstration orders without extra inference costs or external modifications, contrasting sharply with InfoAC which also targets training but with limited scope and success.

• Principled Robustness via DRO vs. Heuristics/Randomness:

  • Difference: Prior training methods ($ERM+DS$, $ERM+IM$) use random shuffling or simple mixing, which are essentially data augmentation techniques. They don't explicitly seek out the most challenging permutations.
  • Innovation: PEARL employs Distributionally Robust Optimization (DRO). This provides a principled framework to explicitly optimize against the worst-case input permutation within an ambiguity set. This is a significant theoretical advancement over empirical data augmentation strategies.

• Adversarial Permutation Generation via P-Net & Optimal Transport:

  • Difference: Exhaustive search for worst-case permutations is computationally infeasible (n!). Heuristic search methods are not guaranteed to find the true worst-case.
  • Innovation: PEARL introduces the P-Net, a specialized neural network that learns to generate adversarial permutations. This P-Net frames the permutation generation as an optimal transport problem, solved efficiently with an entropy-constrained Sinkhorn algorithm and Gumbel sampling for differentiability. This allows for efficient discovery of challenging permutations during training, a capability not present in other methods.

• General Applicability to Generation Tasks:

  • Difference: Many inference-stage methods (e.g., output calibration, prediction ensembling) are more effective for classification tasks and often underperform or are less applicable to generation tasks due to the complexity of sequence-level calibration or ensembling.
  • Innovation: PEARL is demonstrated to be effective for both NLG (Natural Language Generation) and NLU (Natural Language Understanding) tasks in instruction tuning, making it broadly applicable without task-specific constraints on output types.

• Preserving Transformer Architecture and Autoregressive Objective:

  • Difference: Some approaches explore permutation-equivariant architectures (e.g., DeepSet), which deviate from the standard Transformer and may lack its scale or versatility.

  • Innovation: PEARL enhances robustness without modifying the underlying Transformer architecture or its autoregressive objective. This means PEARL can be integrated into existing LLMs more seamlessly, preserving their core capabilities and scalability.

    In essence, PEARL introduces a powerful and theoretically grounded adversarial training framework that tackles permutation sensitivity at its root during the LLM's learning phase, providing robust and generalizable improvements across diverse models and tasks, which is a key differentiator from prior works.

4. Methodology

4.1. Principles

The core idea behind Permutation-resilient learning (PEARL) is to fundamentally enhance an LLM's robustness to the ordering of in-context learning (ICL) demonstrations. This is achieved by moving beyond Empirical Risk Minimization (ERM), which optimizes for average performance on observed data, to Distributionally Robust Optimization (DRO). The principle of DRO is to optimize model performance against the worst-case distribution within a defined set of plausible input distributions. In PEARL, this ambiguity set encompasses all possible permutations of ICL demonstrations.

To operationalize DRO efficiently, PEARL treats the problem as a minimax game between two players:

1. The Adversary (P-Net): A permutation-proposal network (P-Net) that aims to find the most challenging permutation of demonstrations for a given input, thereby maximizing the LLM's loss. It conceptualizes this as an optimal transport problem.

2. The Defender (LLM): The Large Language Model itself, which seeks to minimize its loss when faced with these challenging permutations generated by the P-Net.

   Through this iterative adversarial training process, the LLM is forced to learn features that are invariant or robust to different demonstration orderings, including those that are most detrimental to its performance. This ensures that the LLM can maintain high performance even under unexpected or "attack" permutations, thereby achieving permutation resilience.

4.2. Core Methodology In-depth (Layer by Layer)

The PEARL framework addresses permutation sensitivity by integrating Distributionally Robust Optimization (DRO) into the LLM's fine-tuning process.

4.2.1. Instruction Tuning via DRO

The standard approach to training LLMs for few-shot learning via supervised fine-tuning (SFT) is Empirical Risk Minimization (ERM). The ERM objective is defined as: $$\hat { \theta } _ { \mathrm { E R M } } : = \arg \operatorname* { m i n } _ { \theta \in \Theta } \mathbb { E } _ { ( p , x , y ) \sim \hat { P } } [ \ell ( \theta ; p , x , y ) ]$$ Where:

• $\hat { \theta } _ { \mathrm { E R M } }$ denotes the optimal model parameters found by ERM.

• $\theta \in \Theta$ represents the parameters of the language model.

• $\ell$ is a non-negative loss function that measures the discrepancy between the model's prediction and the true output.

• ( p , x , y ) represents a training instance, where $p$ is an ICL prompt (a sequence of demonstrations), $x$ is the input, and $y$ is the true output.

• $\hat { P }$ denotes the empirical distribution derived from the training dataset.

• $\mathbb { E } _ { ( p , x , y ) \sim \hat { P } } [ \cdot ]$ denotes the expectation (average) over samples drawn from the empirical distribution.

  ERM models often fail to generalize to different permutations because the training set only covers a subset of possible permutations. PEARL addresses this using Distributionally Robust Optimization (DRO). The DRO objective is to find parameters that perform well under the worst-case distribution within a specified ambiguity set: $$\hat { \theta } _ { \mathrm { D R O } } : = \arg \operatorname* { m i n } _ { \theta \in \Theta } \Bigl \{ \operatorname* { s u p } _ { Q _ { \Pi } \in \mathcal { Q } } \mathbb { E } _ { ( p , x , y ) \sim Q _ { \Pi } } [ \ell ( \theta ; p , x , y ) ] \Bigr \}$$ Where:

• $\hat { \theta } _ { \mathrm { D R O } }$ denotes the optimal model parameters found by DRO.

• $\operatorname* { m i n } _ { \theta \in \Theta }$ signifies minimizing over the LLM parameters $\theta$.

• $\operatorname* { s u p } _ { Q _ { \Pi } \in \mathcal { Q } }$ signifies maximizing over all possible distributions $Q _ { \Pi }$ within the ambiguity set $\mathcal { Q }$. This finds the worst-case distribution for the current LLM parameters.

• $\mathbb { E } _ { ( p , x , y ) \sim Q _ { \Pi } } [ \cdot ]$ denotes the expectation (average) over samples drawn from a permutation-induced distribution $Q _ { \Pi }$.

  The ambiguity set $\mathcal { Q }$ is constructed as the convex hull of all distributions obtained by permuting the prompts in the empirical distribution $\hat { P }$: $$\mathcal { Q } : = \Bigg \{ \sum _ { \Pi \in \mathbb { P } } q _ { \Pi } Q _ { \Pi } \Big | q \in \Delta _ { | \mathbb { P } | - 1 } \Bigg \} , \quad \mathrm { w h e r e } \quad Q _ { \Pi } : = \Big \{ \big ( \Pi \cdot p , x , y \big ) \Big | ( p , x , y ) \sim \hat { P } \Big \} .$$ Where:

• $\mathcal { Q }$ is the ambiguity set, containing all possible distributions formed by permutations.

• $\sum _ { \Pi \in \mathbb { P } } q _ { \Pi } Q _ { \Pi }$ represents a convex combination of distributions.

• $\Pi$ is a permutation matrix that reorders the sequence of demonstrations in prompt $p$.

• $\mathbb { P }$ denotes the set of all possible permutation matrices for the demonstrations.

• $q$ is a vector of probabilities, $q \in \Delta _ { | \mathbb { P } | - 1 }$, where $\Delta _ { | \mathbb { P } | - 1 }$ is the probability simplex of dimension $| \mathbb { P } | - 1$. This means the elements of $q$ are non-negative and sum to 1, representing weights for different permutation distributions.

• $Q _ { \Pi }$ denotes a distribution where each instance ( p , x , y ) from the empirical distribution $\hat { P }$ has its prompt $p$ permuted by $\Pi$.

  To visualize the difference, Figure 2 (from the original paper) illustrates how ERM tends to assign high probabilities to frequently seen permutations and low probabilities to less frequent ones, leading to poor performance on unseen but valid permutations. In contrast, DRO aims to distribute probabilities more uniformly across all possible permutations, ensuring robustness.

  该图像是包含两部分的图表，比较了在ERM和DRO训练范式下模型学习的分布差异。蓝色柱状代表训练数据的经验分布 $\hat{P}$，紫色曲线表示模型学习的分布 $P_\theta$，展示了在出现频率较低但有效的排列组合上的不同表现。

Figure 2: Comparison of models trained under ERM and DRO paradigms. The blue bars represent the empirical distribution $\hat { P }$ of training data, showing different frequencies of six permutations in the training set. The purple curves denote the learned distribution $P _ { \theta }$ by (a) ERM and (b) DRO models, illustrating their different behaviors on less appeared but valid permutations.

4.2.2. Learning to Generate Permutations via P-Net

Directly solving the sup step in the DRO objective (Equation 6) through exhaustive search is computationally prohibitive due to the factorial growth of permutations (n!). PEARL addresses this by introducing a Permutation-proposal Network (P-Net) which learns to efficiently find challenging permutations.

The P-Net is designed to learn a distribution over permutations, denoted as $\Delta ( \Pi )$. From this distribution, PEARL samples challenging permutations to reorder the given demonstrations. The P-Net has two main components: a parameter component and a non-parameter component.

Parameter component: This part extracts features from the input and models relationships between demonstrations.

1. Feature Extractor: An encoder model (e.g., BERT-base) processes the ICL prompt, which consists of $n$ demonstration pairs $p = \{ ( x _ { i } , y _ { i } ) \} _ { i = 1 } ^ { n }$ and a predicting sample ( x , y ). It produces representations for each demonstration and the query. $$\left( [ \mathrm { C L S } ] , ( x _ { 1 } , y _ { 1 } ) , \dots , [ \mathrm { C L S } ] , ( x _ { n } , y _ { n } ) , [ \mathrm { C L S } ] , ( x , y ) \right) \xrightarrow { \mathrm { E n c o d e r } } \left( \mathbf { h } _ { 1 } , \mathbf { h } _ { 2 } , \dots , \mathbf { h } _ { n } , \mathbf { h } _ { n + 1 } \right)$$ Where:

   • $[ \mathrm { C L S } ]$ is a special token typically used to segment sequences and extract their representation in Transformer models like BERT.
   • ( x _ { i } , y _ { i } ) represents the $i$-th demonstration input-output pair.
   • ( x , y ) represents the query input and its true output (used for context, though $y$ might not be available during prediction).
   • $\mathbf { h } _ { i }$ is the representation vector corresponding to the $i$-th $[ \mathrm { C L S } ]$ token, capturing the semantic information of the $i$-th demonstration.
   • $\mathbf { h } _ { n + 1 }$ is the representation for the query sample.

2. Cross-Relationship Modeling Layer: After obtaining the representations for the $n$ demonstrations $H = ( \mathbf { h } _ { 1 } , \mathbf { h } _ { 2 } , \ldots , \mathbf { h } _ { n } ) \in \mathbb { R } ^ { n \times h }$ (where $h$ is the hidden dimension), a simple layer models pairwise relationships between them to form a relationship matrix $\mathbf { R } \in \mathbb { R } ^ { n \times n }$. $$\mathbf { R } = g \left( H W H ^ { \top } \right)$$ Where:

   • $H$ is the matrix where each row is a demonstration representation $\mathbf { h } _ { i }$.
   • $W \in \mathbb { R } ^ { h \times h }$ is a learnable weight matrix.
   • $H ^ { \top }$ is the transpose of $H$.
   • $g$ denotes a non-linear activation function.
   • The element R _ { i j } in $\mathbf { R }$ is interpreted as the potential increase in task difficulty for the LLM if demonstrations $i$ and $j$ are swapped. Higher values suggest a greater impact on prediction if swapped. This component essentially models an edge prediction process within a graph where demonstrations are nodes.

Non-parameter component: The relationship matrix $\mathbf { R }$ is then transformed into a doubly stochastic matrix, which represents a probability distribution over permutations. This is achieved using the Sinkhorn operator.

1. Sinkhorn Operator: $$S ( R ) = \operatorname* { l i m } _ { l \infty } ( \mathcal { T } _ { c } ( \mathcal { T } _ { r } ( \exp ( R ) ) ) )$$ Where:

   • S ( R ) is the Sinkhorn operator applied to the matrix $R$.
   • $\operatorname* { l i m } _ { l \infty }$ indicates that the process iterates until convergence (as the number of iterations $l$ approaches infinity).
   • $\exp ( R )$ applies the exponential function element-wise to $R$.
   • $\mathcal { T } _ { r } ( R )$ and $\mathcal { T } _ { c } ( R )$ are the row and column normalization operators, respectively, defined as: $$\mathcal T _ { r } ( R ) = R \oslash \left( R \mathbf { 1 } _ { n } \mathbf { 1 } _ { n } ^ { \top } \right) , \quad \mathcal T _ { c } ( R ) = R \oslash \left( \mathbf { 1 } _ { n } \mathbf { 1 } _ { n } ^ { \top } R \right)$$ Where:
     • $\oslash$ indicates element-wise division.
     • $\mathbf { 1 } _ { n }$ is a column vector of ones of dimension $n$.
     • $R \mathbf { 1 } _ { n } \mathbf { 1 } _ { n } ^ { \top }$ creates a matrix where each row is the sum of the corresponding row in $R$.
     • $\mathbf { 1 } _ { n } \mathbf { 1 } _ { n } ^ { \top } R$ creates a matrix where each column is the sum of the corresponding column in $R$. The Sinkhorn operator iteratively normalizes rows and columns, ensuring that the resulting matrix has all its row and column sums equal to 1, thus becoming doubly stochastic.

2. Gumbel Trick for Differentiable Sampling: To enable differentiable sampling of permutations from the distribution represented by the doubly stochastic matrix (from the Sinkhorn operator), the Gumbel-softmax trick is applied. $$\Pi = \operatorname* { l i m } _ { \tau 0 } S ( ( R + G ) / \tau )$$ Where:

   • $\Pi$ is the resulting permutation matrix.
   • $\tau$ is a temperature parameter. As $\tau$ approaches zero, the output of the Sinkhorn operator approaches a discrete permutation matrix.
   • $G \in \mathbb { R } ^ { n \times n }$ is Gumbel noise, added to introduce randomness and make the sampling process differentiable. Each element G _ { i j } is generated as: $$G _ { i j } = - \log \left( - \log G _ { i j } ^ { \prime } \right) , \quad G _ { i j } ^ { \prime } \sim U ( 0 , 1 )$$ Where:

     • $G _ { i j } ^ { \prime }$ is a sample drawn from a uniform distribution $U ( 0 , 1 )$ between 0 and 1.

       By regarding permutation generation as an optimal transport problem and implementing it through P-Net's parameterized and non-parameterized components, the framework transforms the input permutation distribution into a target distribution, which P-Net learns to make the most challenging for the LLM.

The overall PEARL framework illustrating the interaction between the P-Net and the LLM is shown in Figure 3.

该图像是论文图3的示意图，展示了PEARL框架中P-Net和LLM的联合训练流程。P-Net基于输入示例序列生成置换矩阵，通过采样得到最挑战性的排列，并作用于输入后传入LLM计算损失，最后通过反向传播迭代优化。

Figure 3: An overview of the learning framework. The P-Net is a small model incorporating the Sinkhorn operator, trained jointly with the LLM under the adversarial optimization algorithm. Note that the permutation matrix operates on the input sequence's embeddings (simplified here as text sequences for clarity). After training, only the LLM is retained while the P-Net is discarded.

4.2.3. Adversarial Optimization

The LLM and the P-Net are jointly trained using an adversarial optimization framework. Let $\theta$ represent the parameters of the LLM and $\phi$ represent the parameters of the P-Net. For each sample ( p , x , y ) from the empirical distribution $\hat { P }$:

• The P-Net generates an adversarial permutation $\Pi$ that aims to maximize the LLM's loss.

• The LLM, in turn, tries to minimize its loss when subjected to this adversarial permutation.

  The LLM's loss function, under the influence of the P-Net, is defined as: $$L _ { \mathrm { l m } } ( \phi ; \theta ) = \mathbb { E } _ { ( p , x , y ) \sim \hat { P } , \Pi \sim \mathrm { P } \sim \mathrm { N e t } ( \phi ; p , x , y ) } [ \ell ( \theta ; ( \Pi \cdot p , x , y ) ) ]$$ Where:

• $L _ { \mathrm { l m } } ( \phi ; \theta )$ is the LLM's loss, which is a function of both its own parameters $\theta$ and the P-Net's parameters $\phi$ (because $\phi$ influences the generated permutation $\Pi$).

• $\mathbb { E } _ { ( p , x , y ) \sim \hat { P } , \Pi \sim \mathrm { P } \sim \mathrm { N e t } ( \phi ; p , x , y ) } [ \cdot ]$ denotes the expectation over training samples from $\hat { P }$ and over permutations $\Pi$ sampled from the distribution generated by P-Net parameterized by $\phi$.

• $\ell ( \theta ; ( \Pi \cdot p , x , y ) )$ is the loss of the LLM with parameters $\theta$ on a sample where the prompt $p$ has been permuted by $\Pi$.

  To prevent the P-Net from generating trivial permutations (e.g., always producing the same, easily handled permutation, or permutations that destroy semantic meaning), an entropy-based regularization term is introduced for the P-Net: $$L _ { \mathrm { e n t } } ( \phi ) = \mathbb { E } _ { ( p , x , y ) \sim \hat { P } , \Pi \sim \mathrm { P - N e t } ( \phi ; p , x , y ) } [ \mathcal { H } ( \Pi ) ]$$ Where:

• $L _ { \mathrm { e n t } } ( \phi )$ is the entropy regularization loss for the P-Net.

• $\mathcal { H } ( \cdot )$ denotes the element-wise entropy function. Maximizing entropy encourages P-Net to explore a wider range of permutations rather than collapsing to a single one.

  Combining these, the overall objective becomes a two-player min-max optimization problem: $$\operatorname* { m i n } _ { \theta } \operatorname* { m a x } _ { \phi } \left( L _ { \mathrm { l m } } ( \phi ; \theta ) - \beta L _ { \mathrm { e n t } } ( \phi ) \right)$$ Where:

• $\operatorname* { m i n } _ { \theta }$ means the LLM tries to minimize this objective by adjusting its parameters $\theta$.

• $\operatorname* { m a x } _ { \phi }$ means the P-Net tries to maximize this objective by adjusting its parameters $\phi$.

• $\beta$ is a hyperparameter that controls the strength of the entropy regularization. A higher $\beta$ encourages more diverse permutations from P-Net.

  This minimax optimization is solved using alternating optimization: Algorithm 1: Adversarial Optimization Algorithm for PEARL

Where:

• The for loop iterates $m$ times, updating the P-Net's parameters $\phi$ for a fixed LLM with parameters $\theta$. The P-Net's gradient is ascended ($\phi + \dots$) because it's the maximizer.
• After $m$ steps, the LLM's parameters $\theta$ are updated (descended, $\theta - \dots$) to minimize its loss against the P-Net's generated permutations.
• This alternating process continues until convergence, ideally leading to an LLM that is robust to the worst-case permutations discoverable by the P-Net.
• Crucially, after training, only the LLM is retained, and the P-Net is discarded, meaning no extra computational cost at inference time.

5. Experimental Setup

5.1. Datasets

The experiments are conducted in two main scenarios:

1. In-Context Learning with Linear Functions (Synthetic Pre-training):

   • Source: Follows methodologies from Garg et al. (2022) and Guo et al. (2024b).
   • Characteristics: The function class is defined as $\mathcal { F } = \{ f \mid f ( x ) = w ^ { \top } x , w \in \mathbb { R } ^ { d } \}$, where $d$ is the input dimension. This is a synthetic setting designed to isolate and study ICL behavior on simple, well-understood function classes.
   • Data Construction: Each data sample is constructed as follows:
     • Function sampling: A weight vector $w \sim \mathcal { N } ( 0 , I _ { d } )$ is sampled (meaning each component of $w$ is drawn from a standard normal distribution), defining a linear function $f ( x ) = w ^ { \top } x$.
     • Input sampling: Inputs $x _ { 1 } , x _ { 2 } , \ldots , x _ { k + 1 } \sim \mathcal { N } ( 0 , I _ { d } )$ are independently drawn.
     • Output generation: For each input, the corresponding output is computed as $y _ { i } = f ( x _ { i } ) = w ^ { \top } x _ { i }$ for $i = 1 , 2 , \ldots , k + 1$.
   • Prompt Structure: The input prompt $p ^ { i }$ consists of $i$ demonstrations and the $( i + 1 )$ -th example as the query: $p ^ { i } = ( x _ { 1 } , f ( x _ { 1 } ) , x _ { 2 } , f ( x _ { 2 } ) , . . . , x _ { i } , f ( x _ { i } ) , x _ { i + 1 } )$.
   • Why chosen: This synthetic task allows for controlled study of ICL mechanisms and robustness to permutations without the complexities of natural language, providing clear insights into the model's learning capabilities.

2. Instruction Fine-Tuning of Large Language Models (Real-world Tasks):

   • Source: Data derived from Super-Natural Instructions (Wang et al., 2022), which is part of the FLAN v2 benchmark (Chung et al., 2024).

   • Characteristics: Diverse set of 17 tasks, including 9 Natural Language Generation (NLG) tasks and 8 Natural Language Understanding (NLU) tasks.

   • Data Split: 4 datasets are designated as held-out test sets, and the remaining 13 datasets are used for training.

     • Each training dataset contains 150 examples.
     • Each test dataset contains 100 examples.
     • This results in a total training set of 1,950 examples and a test set of 400 examples.

   • Why chosen: Super-Natural Instructions is a comprehensive and diverse benchmark for evaluating LLMs on instruction following and generalization across various NLP tasks, making it suitable for assessing PEARL's performance in real-world scenarios.

   • The following are the details of datasets used in instruction tuning from natural instructions from Table 5 of the original paper:

     Task ID	Task Name	Source	Category
     1297	QASC Question Answering	QASC	Question Answering
     442	COM_QA Paraphrase Question Generation	COM_QA	Question Rewriting
     908	DialogRE Identify Familial Relationships	DialogRE	Speaker Relation Classification
     288	Gigaword Summarization	Gigaword	Title Generation
     582	Natural Questions Answer Generation	Natural Questions	Question Answering
     151	TOMQA Find Location Easy Clean	TOM_QA	Question Answering
     1714	ConvAI3 Sentence Generation	ClariQ	Dialogue Generation
     379	AGNews Topic Classification	AG News	Text Categorization
     639	MultiWOZ User Utterance Generation	MultiWOZ 2.2	Dialogue Generation
     209	Stance Detection Classification	StarCon	Stance Detection
     1516	IMPPRES Natural Language Inference	IMPPRES	Textual Entailment
     589	Amazon Food Summary Text Generation	Amazon Reviews	Summarization
     1285	KPA Keypoint Matching	ArgKP	Text Matching

The following are the details of the dataset summary for instruction tuning from Table 2 of the original paper:

5.2. Evaluation Metrics

For every evaluation metric mentioned in the paper, here is a complete explanation:

• Normalized Squared Error (MSE)

  1. Conceptual Definition: Used for the synthetic task of in-context learning linear functions. Mean Squared Error (MSE) measures the average of the squares of the errors—that is, the average squared difference between the estimated values (model predictions) and the actual value. A lower MSE indicates that the model's predictions are closer to the true values. The normalized version scales this error relative to the problem's dimension, providing a standardized measure of prediction accuracy for linear regression.
  2. Mathematical Formula: The paper reports the normalized squared error as: $$\frac { ( L M ( p ) - w ^ { \top } x _ { \mathrm { q u e r y } } ) ^ { 2 } } { d }$$
  3. Symbol Explanation:
     • L M ( p ): The prediction made by the language model (LM) given the input prompt $p$.
     • $w ^ { \top } x _ { \mathrm { q u e r y } }$: The true output for the query input $x _ { \mathrm { q u e r y } }$, computed by the ground truth linear function $f ( x ) = w ^ { \top } x$.
     • $d$: The dimension of the input vectors (problem dimension).
     • $( \cdot ) ^ { 2 }$: The squared difference between the prediction and the true value.

• ROUGE-L (Recall-Oriented Understudy for Gisting Evaluation - Longest Common Subsequence)

  1. Conceptual Definition: ROUGE-L is a metric for evaluating text generation models, particularly for summarization or open-ended generation tasks. It quantifies the overlap between a generated text and a set of reference texts by focusing on the longest common subsequence (LCS). The LCS is the longest sequence of words that appears in both texts in the same relative order, but not necessarily contiguously. ROUGE-L is robust to minor syntactic variations and focuses on the main content and structure. It is often reported as an F-measure, combining ROUGE-L Recall and ROUGE-L Precision. A higher ROUGE-L score indicates a better quality of generated text compared to the reference.
  2. Mathematical Formula (Standard Formulation): Let $X$ be the reference text of length $m$ and $Y$ be the generated text of length $n$. The ROUGE-L Recall, ROUGE-L Precision, and ROUGE-L F-measure are calculated as: $$\text{ROUGE-L Recall} = \frac{\text{LCS}(X, Y)}{m}$$ $$\text{ROUGE-L Precision} = \frac{\text{LCS}(X, Y)}{n}$$ $$\text{ROUGE-L F-measure} = \frac{(1 + \beta^2) \times \text{ROUGE-L Recall} \times \text{ROUGE-L Precision}}{\beta^2 \times \text{ROUGE-L Recall} + \text{ROUGE-L Precision}}$$ Often, $\beta$ is set to 1, giving equal weight to Recall and Precision: $$\text{ROUGE-L F-measure (with } \beta=1) = \frac{2 \times \text{ROUGE-L Recall} \times \text{ROUGE-L Precision}}{\text{ROUGE-L Recall} + \text{ROUGE-L Precision}}$$
  3. Symbol Explanation:
     • $\text{LCS}(X, Y)$: The length of the Longest Common Subsequence between text $X$ and text $Y$.
     • $m$: The length (number of words) of the reference text $X$.
     • $n$: The length (number of words) of the generated text $Y$.
     • $\beta$: A non-negative coefficient that controls the relative importance of Recall and Precision. A $\beta > 1$ weights Recall more, while $\beta < 1$ weights Precision more.

• Attack Success Rate (ASR)

  1. Conceptual Definition: ASR measures the proportion of samples for which an adversarial attack (in this case, permutation-based attack) successfully degrades the model's performance beyond a specified threshold. A higher ASR indicates greater vulnerability of the model to the attack.
  2. Mathematical Formula: $$\mathrm { A S R } ( D , \delta ) = \frac { 1 } { | D | } \sum _ { i = 1 } ^ { | D | } \mathbb { I } \big ( ( \mu _ { i } - \omega _ { i } ) / \mu _ { i } \geq \delta \big )$$
  3. Symbol Explanation:
     • $\mathrm { A S R } ( D , \delta )$: The Attack Success Rate for a given task dataset $D$ and a performance degradation threshold $\delta$.
     • $| D |$: The total number of samples in the dataset $D$.
     • $\mathbb { I } ( \cdot )$: The indicator function, which returns 1 if its argument is true, and 0 otherwise.
     • $\mu _ { i }$: The average performance of the $i$-th sample across all possible permutations. It is defined as: $$\mu _ { i } = \mathbb { E } _ { \Pi \sim \mathbb { P } } [ g ( \Pi \cdot p _ { i } , x _ { i } ; y _ { i } ) ] = { \frac { 1 } { n ! } } \sum _ { j = 1 } ^ { n ! } g ( \Pi _ { j } \cdot p _ { i } , x _ { i } ; y _ { i } )$$ Where $g$ is the performance metric (e.g., ROUGE-L), $\mathbb { P }$ is the set of all possible permutations, and n! is the total number of permutations for $n$ demonstrations.
     • $\omega _ { i }$: The compromised performance of the $i$-th sample achieved by the permutation attack strategy. For Exhaustive Search Attack, $\omega _ { i } = \operatorname* { m i n } _ { \Pi \in \mathbb { P } } g ( \Pi \cdot p _ { i } , x _ { i } ; y _ { i } )$. For Neural Search Attack (using P-Net), \omega _ { i } = g ( \Pi _ { i } \cdot p _ { i } , x _ _ { i } ; y _ { i } ) , \qquad \mathrm { s . t . } ~ \Pi _ { i } \sim \mathrm { P - N e t } ( p _ { i } , x _ { i } , y _ { i } ).
     • $\delta$: The relative performance degradation threshold, expressed as a percentage (e.g., 50%). An attack is successful if the performance drops by at least this percentage relative to the average performance.

5.3. Baselines

The paper compares PEARL against several baseline learning algorithms:

• For Linear Functions (Synthetic Pre-training):

  • $ERM + CL$ (Empirical Risk Minimization with Curriculum Learning): This is the standard ERM approach where the model is trained to minimize average loss. Curriculum Learning (Bengio et al., 2009; Wu et al., 2020) is added, meaning the training process gradually increases the number of demonstrations (shots) presented to the model. This allows for progressive learning of more complex patterns and helps stabilize training. It serves as a strong baseline for ICL on linear functions.

• For Instruction Fine-Tuning of LLMs (Real-world Tasks):

  • ERM (Empirical Risk Minimization): (Min et al., 2022) This is the standard fine-tuning approach that minimizes the average loss over the training dataset. It is adopted by mainstream instruction tuning models like FLAN (Chung et al., 2024), Natural Instructions (Mishra et al., 2022; Wang et al., 2022), and MetaICL (Min et al., 2022). It represents the default behavior of LLMs when fine-tuned without specific robustness considerations.

  • ERM + DS (Empirical Risk Minimization with Demonstration Shuffling): (Zhang et al., 2018) This method enhances ERM by randomly shuffling the order of in-context demonstrations within each sample at each training step. This introduces a basic form of data augmentation to expose the model to different permutations, aiming for some level of robustness. It can be seen as an epoch-level data augmentation strategy.

  • ERM + IM (Empirical Risk Minimization with Instance Mixup): (Zhang et al., 2018) This approach incorporates the Instance Mixup technique during each training step. For each data point, multiple augmented versions are generated by randomly selecting different in-context demonstrations. The losses for these augmented versions are computed, averaged, and then a single backward pass is performed using the averaged loss. This provides a finer-grained data augmentation than simple shuffling. By comparing with PEARL, it contrasts min-mean optimization ($ERM+IM$) with min-max optimization (PEARL).

  • InfoAC: (Xiang et al., 2024) A training-stage method that uses contrastive learning to allow earlier tokens in an autoregressive LM to access information from later tokens. This is specifically designed to mitigate the order sensitivity inherent in causal language models by breaking the strict autoregressive constraint.

    These baselines are chosen to represent both standard ERM training and existing attempts at addressing permutation sensitivity through data augmentation or architectural modifications, providing a comprehensive evaluation context for PEARL.

5.4. Implementation Details

5.4.1. Architecture and Training for Linear Functions

• LLM ($L _ { \theta }$): Implemented using a GPT-2 base model (Radford et al., 2019) with 12 layers, 8 attention heads, and a hidden dimension of 256. It takes a sequence of vectors in its embedding space and predicts the next vector.
• P-Net: Initialized as a BERT-base sized transformer encoder.
• Training: Both LLM and P-Net are trained from scratch.
  • LLM pre-trained on a generated dataset of 40k linear functions.
  • Optimizer: AdamW (Loshchilov & Hutter, 2019).
  • Batch size: 128.
  • Training steps: 500k.
  • Checkpoint selection: Based on validation set performance.
• Testing: New functions are sampled to evaluate the model's ability to infer new weights $w$ from in-context demonstrations.

5.4.2. Architecture and Training for Instruction Fine-Tuning

• LLMs Evaluated: Llama3-8B, Llama2-7B, Llama2-13B, Mistral-7B, and Gemma-7B.
• P-Net: FLAN-large encoder.
• Fine-tuning method: Both LLM and P-Net are fine-tuned using LoRA (Low-Rank Adaptation) (Hu et al., 2022).
  • Number of finetuned parameters of P-Net is 1/20 that of the LLM.
• Training Details:
  • GPU: Single NVIDIA A40.
  • Epochs: 2.
  • Batch size: 16.
  • Total training steps: 246.
  • Optimizer: AdamW.
  • Learning rates:
    • P-Net: $1 \times 1 0 ^ { - 4 }$
    • LLM: $3 \times 1 0 ^ { - 4 }$
  • Sinkhorn algorithm parameters:

    • Iterations: 80.

    • Temperature parameter: 0.1.

    • Entropy constraint coefficient ($\beta$): 1.0.

      The following are the hyperparameter settings used in the main experiment from Table 6 of the original paper:

      Category	Hyperparameter	Value
      LLMs	Learning rate	3e-5
      	Batch size	16
      	Max sequence length	512
      	Weight decay coefficient	0.1
      	Epoch	2
      LoRA	Rank	8
      	Alpha	32
      	Dropout	0.1
      	P-Net target modules	q, Vv
      	LLMs target modules	q_proj, k_proj, v_proj, o_proj, gate_proj,
      P-Net	Temperature	up_proj, down_proj 0.1
      	Iteration coefficient	80
      	Entropy constraint	1.0
      	Noise	0.3
      	Learning rate	1e-4
      	Batch size	16
      	Max sequence length	512

6. Results & Analysis

6.1. Core Results Analysis

6.1.1. Performance on In-Context Learning with Linear Functions

The experiments on linear functions highlight PEARL's ability to improve both average and worst-case performance while defending against permutation attacks.

The following are the normalized MSE across permutations from Table 1 of the original paper:

• Average vs. Worst-Case Performance: Table 1 shows that for the baseline $ERM+CL$, there's a significant gap between average and worst-case performance. For example, at 5 shots, the average Normalized MSE is 1.28, but the worst-case plummets to 5.03. This large degradation indicates severe vulnerability to permutations. As the number of shots increases, this relative performance drop for $ERM+CL$ worsens (from 74.6% at 3 shots to 84.1% at 4 shots), effectively negating the benefits of providing more contextual information.

• PEARL's Improvement: PEARL consistently improves both average and worst-case performance. For instance, at 5 shots, PEARL achieves an average MSE of 0.87 (32.0% better than $ERM+CL$) and a worst-case MSE of 1.33 (73.6% better than $ERM+CL$). This demonstrates PEARL's effectiveness in making the model more robust to challenging permutations.

• Worst-Case Generalization: While PEARL's average performance gains tend to stabilize with more shots, its worst-case performance gains continue to increase (from 65.5% at 3 shots to 73.6% at 5 shots). This highlights PEARL's strength in enhancing the model's fundamental robustness and generalization under adverse conditions.

  The defense capability against permutation attacks is shown in Figure 4.

  该图像是图表，展示了不同训练方法下在不同阈值比例下的攻击成功率对比。图中曲线比较了ERM+CL和PEARL在3、4、5个样本条件下的表现，显示PEARL在多种阈值下均有较低的攻击成功率，体现其对排列攻击的鲁棒性。

Figure 4: Comparison of attack success rates.

• Attack Success Rates (ASR): Figure 4 illustrates PEARL's superior defense against permutation attacks. The ASR for PEARL is consistently lower than $ERM+CL$ across all attack success thresholds ($\delta$) and shot numbers.
• Robustness at High Thresholds: PEARL's advantage becomes more pronounced at higher thresholds (e.g., $\delta > 50\%$). At these thresholds, PEARL's defense success rate (inverse of ASR) is approximately double that of the baseline. This implies PEARL is particularly effective at preventing large performance degradations caused by malicious permutations.
• Scalability: PEARL's performance improves with an increasing number of shots, suggesting better scalability in maintaining robustness in more complex ICL scenarios.

6.1.2. Performance on Instruction Fine-Tuning of Large Language Models

PEARL's effectiveness extends to real-world instruction fine-tuning tasks, demonstrating improvements across various LLMs and scaling scenarios.

The following are the average and worst-case performance of Llama3-8B on four held-out tasks from Table 3 of the original paper:

• Consistent Improvement: Table 3 demonstrates that PEARL consistently improves both average and worst-case performance of Llama3-8B across four held-out tasks. For 2-shot, PEARL yields a 9.8% average gain and 14.2% worst-case gain over ERM.

• Worst-Case Gain with More Shots: As the number of shots increases, the relative worst-case performance gain over ERM progressively increases, from 14.2% at two shots to 29.4% at four shots. This reinforces PEARL's ability to build robustness against increasingly complex permutation spaces.

• Superior Average Performance: Despite optimizing for worst-case performance, PEARL also achieves superior average performance, with gains ranging from 5.7% to 9.8%. This suggests that making the model robust to difficult examples also improves its general performance.

• Comparison with Baselines: Other baselines like $ERM+DS$, $ERM+IM$, and InfoAC generally show limited or even negative impact on average performance, and often only marginal gains (or even losses) in worst-case performance compared to ERM, highlighting PEARL's distinct advantage. The rapid convergence and effectiveness for advanced LLMs like Llama3 suggests that DRO (focusing on challenging permutations) is more effective than random data augmentation.

  The generalization performance of our method across different types of LLMs and many-shot settings is shown in Figure 5.

  该图像是图表，展示了论文中方法在不同大语言模型（LLM）及多示例任务中的泛化性能。左图为3-shot情况下在Mistral-7B、Gemma-7B、Llama2-7B及Llama3-8B不同模型的性能提升，右图显示基于5-shot训练时，在多示例数量（8、16、32、64）和长序列（8k标记）条件下的扩展表现，柱状图区分了平均性能提升和最差性能提升。

Figure 5: Generalization performance of our method across different types of LLMs and many-shot settings. Left: Performance gains on 3-shot across different LLMs (Mistral-7B, Gemma-7B, Llama 2-7B, and Llama3-8B). Right: Scaling behavior across many-shot settings (8, 16, 32, and 64 shots) and longer sequences $\mathrm { 8 k }$ tokens) when trained with 5 shots and a sequence length of 512 tokens.

• Generalization Across LLMs (Left Panel of Figure 5): PEARL consistently improves worst-case performance by more than 10% for three-shot settings across various LLMs (Mistral-7B, Gemma-7B, Llama 2-7B, and Llama3-8B). This confirms the method's broad applicability. Llama models are noted as most sensitive to permutations, followed by Gemma and Mistral, yet PEARL provides consistent improvements across all.

• Scalability to Many-Shot and Long Contexts (Right Panel of Figure 5): Despite being trained on limited configurations (5 shots, 512 tokens max sequence length), PEARL demonstrates strong generalization to many-shot ICL (up to 64 shots) and longer sequences (up to 8,000 tokens). It achieves substantial worst-case performance gains ranging from 24% to 40% in these scaled scenarios. This indicates that PEARL helps LLMs learn more robust features that are not overfit to the training context length or number of shots.

  The shot efficiency from Table 4 of the original paper:

  # Shots	2	4	8	16	32	64
  ERM	57.3	59.7	61.8	66.9	67.4	68.1
  PEARL	62.9	63.1	66.5	70.5	70.0	70.4

• Shot Efficiency (Table 4): PEARL-trained models achieve comparable average performance while requiring significantly fewer shots. For example, PEARL with 2 shots (62.9) already outperforms ERM with 8 shots (61.8). PEARL at 4 shots (63.1) is better than ERM at 8 shots, and PEARL at 8 shots (66.5) is close to ERM at 16 shots (66.9). This highlights the efficiency of PEARL, as it can achieve desired performance levels with much less in-context information.

6.2. Ablation Studies / Parameter Analysis

6.2.1. Hyperparameters in Instruction Finetuning

The following are the impact of number of iterations and temperature on the average/worst-case performance from Figure 6 of the original paper:

• Effect of Sinkhorn Algorithm Parameters (Table from Figure 6): The analysis of the Sinkhorn algorithm's parameters (number of iterations and temperature) reveals a surprising robustness. With the entropy regularization coefficient fixed at 1, varying the number of iterations (80, 200) and temperature (0.03, 0.1, 0.3) resulted in minimal performance variation. This suggests that the Sinkhorn algorithm within PEARL is not highly sensitive to these specific parameters, implying a wider range of stable configurations for practical deployment.

  The impact of entropy coefficient is shown in Figure 7.

  该图像是图表，展示了梯度范数与熵系数β之间的关系。图中曲线分别表示P-Net和LLM的梯度范数随β变化的趋势，反映了熵系数对模型训练过程的影响。

Figure 7: Impact of entropy coefficient.

• Influence of Entropy Regularization (Figure 7): The entropy regularization coefficient ($\beta$) plays a crucial role in P-Net's learning.
  • At a low coefficient (0.3), P-Net's gradient norm remains small, indicating it learns minimally and might generate simple semantic overlaps rather than truly challenging permutations. The LLM's gradient also struggles to decrease.
  • The P-Net's gradient norm peaks at 1.0, suggesting optimal learning conditions where it effectively finds challenging permutations.
  • As coefficients increase further (3.0 and 10.0), P-Net's gradient norm decreases again, indicating that excessive regularization might restrict its ability to explore diverse permutations.
  • The range of 1.0-3.0 appears to strike an ideal balance, encouraging P-Net to extract meaningful adversarial information. The LLM's gradient norm consistently decreases with increasing coefficients, showing a clear response to entropy regularization.

6.3. Extended Instruction Finetuning Across Diverse LLMs

The following are the instruction fine-tuning results for Mistral-7B evaluated on four held-out tasks from Table 7 of the original paper:

• Mistral-7B (Table 7): PEARL provides consistent improvements for Mistral-7B, with worst-case performance gains reaching 14.5% at 5 shots.

  The following are the instruction fine-tuning results for Gemma-7B evaluated on four held-out tasks from Table 8 of the original paper:

  		Average		CSQA		CurDial		CoLA		TMW
  # Shot	Method	Avg.	Worst.	Avg.	Worst.	Avg.	Worst.	Avg.	Worst.	Avg.	Worst.
  2	ERM PEARL	66.2 66.3 (+0.0)	59.5 60.7 (+2.0)	71.0 74.0	70.0 68.0	59.1 47.3	46.1 39.2	77.0 82.0	70.0 78.0	57.8 61.7	52.0 57.6
  3	ERM PEARL	64.7 68.4 (+5.8)	52.5 59.3 (+13.0)	70.7 74.7	64.0 68.0	67.1 59.2	45.2 42.5	70.3 78.7	60.0 76.0	50.5 61.0	40.7 50.6
  4	ERM PEARL	65.0 67.2 (+3.4)	46.5 52.5(+13.0)	65.0 71.4	54.0 60.0	71.4 60.7	41.1 38.9	72.5 75.9	58.0 66.0	51.1 60.8	32.9 45.2
  5	ERM PEARL	64.3 66.3 (+3.1)	46.3 51.0 (+10.2)	65.9 70.3	54.0 60.0	73.4 63.4	48.3 43.6	65.6 71.3	50.0 60.0	52.3 60.2	32.9 40.4

• Gemma-7B (Table 8): For Gemma-7B, PEARL yields robust worst-case improvements, achieving 13.0% gains at both 3 and 4 shots, and 10.2% at 5 shots.

  The following are the instruction fine-tuning results for Llama2-7B evaluated on four held-out tasks from Table 9 of the original paper:

  		Average		CSQA		CurDial		CoLA		TMW
  # Shot	Method	Avg.	Worst.	Avg.	Worst.	Avg.	Worst.	Avg.	Worst.	Avg.	Worst.
  2	ERM PEARL	56.6 57.4 (+1.5)	46.3 46.5 (+0.4)	56.0 58.0	50.0 48.0	61.3 55.2	50.2 44.7	58.2 62.0	42.0 48.0	50.7 54.4	43.1 45.4
  3	ERM PEARL	58.2 59.6 (+2.3)	34.0 40.4 (+19.1)	52.7 56.3	34.0 40.0	64.0 66.2	36.4 46.2	66.0 67.0	36.0 42.0	50.1 48.7	29.4 33.5
  4	ERM PEARL	58.9 60.5 (+2.7)	19.9 31.6 (+59.1)	60.0 61.2	26.0 40.0	68.1 69.4	24.4 40.1	60.2 62.4	14.0 24.0	47.3 48.9	15.1 22.4
  5	ERM PEARL	61.9 62.9 (+1.6)	25.8 32.1 (+24.7)	59.0 62.4	32.0 38.0	74.2 73.3	43.9 43.4	65.7 64.8	10.0 24.0	48.6 51.0	17.1 23.0

• Llama2-7B (Table 9): This model shows particularly high sensitivity, with ERM worst-case performance dropping as low as 19.9 at 4 shots. PEARL provides dramatic improvements, boosting worst-case performance by 59.1% at 4 shots and 24.7% at 5 shots.

  The following are the instruction fine-tuning results for Llama2-13B evaluated on four held-out tasks from Table 10 of the original paper:

  		Average		CSQA		CurDial		CoLA		TMW
  # Shot	Method	Avg.	Worst.	Avg.	Worst.	Avg.	Worst.	Avg.	Worst.	Avg.	Worst.
  2.0	ERM PEARL	66.3 67.9 (+2.4)	56.6 60.7 (+7.3)	56.0 64.0	46.0 58.0	72.6 73.8	56.2 64.2	83.0 81.0	76.0 76.0	53.4 52.6	48.0 44.4
  3.0	ERM PEARL	65.7 68.5 (+4.2)	46.2 50.3 (+8.7)	55.7 62.7	38.0 44.0	76.4 81.0	51.3 58.4	77.7 76.7	56.0 56.0	53.1 53.5	39.6 42.6
  4.0	ERM PEARL	65.8 66.4 (+0.9)	33.2 40.2 (+21.1)	58.2 63.3	28.0 42.0	79.6 80.4	41.6 45.5	73.7 69.4	38.0 42.0	51.8 53.1	25.0 29.1

• Llama2-13B (Table 10): Similar to Llama2-7B, PEARL significantly improves worst-case performance, with a 21.1% gain at 4 shots.

  The following are the performance evaluation across 8-, 16-, 32-, and 64-shot settings comparing PEARL and ERM learning algorithm for Llama3-8B on four held-out tasks, with gains (%) relative to the ERM from Table 11 of the original paper:

  		Average		CSQA		CurDial		CoLA		TMW
  # Shot	Method	Avg.	Worst.	Avg.	Worst.	Avg.	Worst.	Avg.	Worst.	Avg.	Worst.
  8	ERM PEARL	61.8 66.5 (+7.6)	21.3 29.7 (+39.2)	61.4 67.7	36.0 44.0	68.3 77.1	22.7 28.7	62.7 65.0	16.0 32.0	54.8 56.2	10.6 14.0
  16	ERM PEARL	66.9 70.5 (+5.3)	21.3	67.3	36.0	76.5	31.4	67.2	8.0	56.5 56.9	9.7 9.8
  32	ERM	67.4	26.3 (+23.7) 19.3	70.9 67.5	46.0 32.0	83.9 77.8	37.5 30.7	70.1 68.2	12.0 6.0	56.1	8.6
  64	PEARL ERM PEARL	70.0 (+3.8) 68.1	26.4 (+36.4) 20.6	70.0 68.1	44.0 38.0	82.6 76.9	40.3 27.7	70.6 72.2	12.0 8.7	56.6 55.0	9.1 8.0 8.1

• Scaling to Many-Shot (Table 11): Even when trained with only 5 shots, PEARL exhibits strong generalization to many-shot scenarios (8, 16, 32, 64 shots). It consistently achieves substantial worst-case performance gains (e.g., 39.2% at 8 shots, 36.4% at 64 shots) over ERM, underscoring its ability to enable LLMs to learn robust features that generalize effectively to larger contexts.

  The following are the best performance comparison between ERM and PEARL from Table 12 of the original paper:

  #Shot	Method	Average	Gain	CSQA	CurDial	CoLA	TMW
  2	ERM	64.1	-	68.8	64.4	64.1	59.2
  	PEARL	68.8	7.2%	73.4	69.2	70.3	62.1
  3	ERM	72.8	-	70.3	85.0	65.6	70.3
  	PEARL	77.0	5.7%	73.4	87.9	79.7	66.9
  4	ERM	82.9	-	81.3	92.4	78.1	79.7
  	PEARL	84.3	1.7%	82.8	93.6	81.2	79.5
  5	ERM	86.8	-	84.4	95.3	81.3	86.2
  	PEARL	89.3	2.9%	87.5	96.5	85.9	87.3

• Best-Case Performance (Table 12): Surprisingly, PEARL not only improves worst-case scenarios but also slightly enhances best-case performance across all datasets and shot conditions, compared to ERM. This suggests that the robustness learned through DRO generalizes to improve performance even under optimal permutation conditions, indicating a more comprehensively capable model.

6.4. Vulnerability Reassessment of LLaMA-3

As shown in the right of Figure 1, the permutation-based attacks are effective and approachable, even on advanced LLMs like LLaMA-3.

该图像是图表，展示了Llama-3在CurDial和TMW数据集上的性能与攻击成功率。左侧图表显示不同示例数量下的随机、平均和最差表现；右侧图表展示在不同阈值下穷举和神经搜索攻击方法的成功率。

Figure 1: Performance and attack success rates of Llama-3 on CurDial and TMW datasets. Left panels: Random, average and worst-case performance as a function of shot number. Right panels: Attack success rates for exhaustive and neural search attack methods at different thresholds.

• Attack Effectiveness: Exhaustive search attack successfully attacks over 50% and 80% of samples with $\delta = 50\%$ on CurDial and TMW datasets respectively, showing the upper bound of vulnerability.
• Neural Attack Efficacy: The neural attack (using P-Net for adversarial generation) achieved a success rate close to this upper bound across different shots. This validates the P-Net's ability to approximate the worst-case permutations efficiently, demonstrating that the vulnerability is a real concern and not just a theoretical one.

7. Conclusion & Reflections

7.1. Conclusion Summary

This paper effectively identifies and addresses a critical vulnerability in Large Language Models (LLMs): their sensitivity to the ordering of in-context learning (ICL) demonstrations. The authors demonstrate that this permutation sensitivity can be exploited as a "natural attack," significantly degrading LLM performance. To counter this, they introduce PEARL (Permutation-resilient learning), a novel training framework built upon Distributionally Robust Optimization (DRO). PEARL utilizes a permutation-proposal network (P-Net) that leverages optimal transport and an entropy-constrained Sinkhorn algorithm to generate the most challenging permutations. Through minimax optimization, the LLM and P-Net iteratively train, leading to an LLM that is inherently robust to various demonstration orderings. Empirical evaluations on both synthetic tasks and real-world instruction-tuning tasks confirm PEARL's efficacy in mitigating permutation-based attacks and significantly enhancing both average and worst-case performance. Crucially, PEARL demonstrates strong generalization capabilities to many-shot and long-context scenarios, even when trained on fewer resources, and improves shot efficiency.

7.2. Limitations & Future Work

The authors highlight that while PEARL primarily focuses on improving in-context learning in LLMs, its underlying framework is generalizable. They suggest that PEARL provides a general framework for handling set-structured inputs with order-independent elements. This implies potential future research directions:

• Beyond Text: Applying PEARL to other modalities where input elements form a set but their order might implicitly influence model behavior, such as processing multiple documents, images in a gallery, or video frames.

• Broader Robustness: The DRO paradigm could be extended to address other forms of input variability or adversarial attacks beyond just permutations.

• Theoretical Guarantees: Further theoretical work could explore the bounds and guarantees provided by PEARL's DRO formulation in more diverse and complex settings.

• Efficiency of P-Net: While P-Net is shown to be efficient, exploring alternative or more lightweight P-Net architectures could reduce training overhead even further, especially for extremely large LLMs.

  The paper implicitly acknowledges that the P-Net needs to be sufficiently powerful to identify truly challenging permutations, which might be a limitation if the P-Net itself is too simple or gets stuck in local optima.

7.3. Personal Insights & Critique

The PEARL framework presents a highly innovative and principled approach to a well-known vulnerability in LLMs. The integration of Distributionally Robust Optimization (DRO) with Optimal Transport (OT) to create an adversarial permutation-proposal network (P-Net) is a sophisticated and elegant solution. It shifts the paradigm from simply trying to cope with permutation sensitivity to actively learning robustness against it.

One of the most compelling aspects is PEARL's ability to improve worst-case performance without sacrificing average performance; in fact, it often enhances it. This suggests that training on the "hardest" examples forces the LLM to learn more robust and generalizable features, which then benefits all input scenarios. The shot efficiency finding is also significant, implying that PEARL can potentially reduce the amount of in-context information needed for a given performance level, which has practical implications for prompt length and computational cost during inference.

A potential area for further exploration or a subtle unverified assumption might lie in the "naturalness" of the P-Net generated permutations. While P-Net is designed to find challenging permutations, it's not explicitly stated if these permutations always remain semantically coherent or representative of "natural" orderings that users might encounter. The entropy regularization helps prevent trivial solutions, but the quality of adversarial examples generated by P-Net is key to the overall framework's effectiveness.

The method's applicability beyond ICL to any set-structured input is a powerful insight. Imagine a model that processes a collection of medical images; PEARL could make it robust to the order in which those images are presented. This opens up exciting avenues for future research in multi-modal AI and data augmentation strategies across various domains.

In conclusion, PEARL offers a robust, principled, and highly effective solution to a critical problem in LLM reliability. Its theoretical foundation and strong empirical results make it a significant contribution to the field of robust AI and trustworthy language models.