ICL Permutation Exploit

Description: Autoregressive Large Language Models (LLMs) utilizing In-Context Learning (ICL) are vulnerable to demonstration permutation attacks due to inherent sensitivity to the ordering of input examples. This vulnerability arises from the limitations of unidirectional attention mechanisms and standard Empirical Risk Minimization (ERM) training, which fails to account for worst-case input permutations. An attacker can exploit this by permuting the order of valid, semantically correct few-shot demonstrations (contextual examples) to match a "worst-case" distribution. This adversarial reordering maximizes the model's loss function, leading to significant performance degradation, incorrect outputs, and instability, without requiring the injection of malicious or invalid content.

Examples: The vulnerability is reproduced by taking a standard few-shot prompt and reordering the examples to find the permutation that minimizes model accuracy.

• Exhaustive Search Attack: For a prompt with $n$ demonstrations, the attacker evaluates all $n!$ permutations to identify the specific order $\Pi$ that yields the lowest metric (e.g., ROUGE-L).
• Neural Search Attack: An attacker employs a trained Permutation-proposal Network (P-Net) to predict the most challenging permutation matrix $\Pi_i$ for a given sample $(p_i, x_i, y_i)$.
• See repository for attack implementation code (P-Net): https://github.com/ChanLiang/PEARL
• Specific degradation data on LLaMA-3-8B (3-shot setting): Average performance ~57.8 drops to Worst-case ~38.3 under permutation attack (See Table 3 in the referenced paper).

Impact:

• Reliability Degradation: Successful attacks achieve nearly 80% success rates on models like LLaMA-3, causing substantial drops in performance metrics (e.g., normalized squared error increase or ROUGE-L decrease).
• Stealth: The attack is difficult to detect via standard filters because the input demonstrations remain semantically valid and benign; only their sequence is altered.
• Scalability Risk: Increasing the number of demonstrations (shots) expands the permutation space ($n!$), potentially worsening worst-case performance despite improving average-case performance.

Affected Systems:

• Transformer-based autoregressive LLMs utilizing In-Context Learning (ICL).
• Verified vulnerable models include:
• Meta LLaMA-3 (8B)
• Meta LLaMA-2 (7B, 13B)
• Mistral AI Mistral-7B
• Google Gemma-7B
• OpenAI GPT-2 (in synthetic linear function tests)

Mitigation Steps:

• Implement Permutation-Resilient Learning (Pearl): Shift from standard Empirical Risk Minimization (ERM) to a Distributionally Robust Optimization (DRO) framework.
• Adversarial Training: Deploy a two-player game during fine-tuning consisting of:
• A Permutation-proposal Network (P-Net) that identifies and generates challenging permutations using an entropy-constrained Sinkhorn algorithm.
• The target LLM, which optimizes parameters to minimize loss against these worst-case permutations.
• Ambiguity Set Optimization: Explicitly optimize the model against the "ambiguity set" (the convex hull of all possible permutations of training prompts) rather than single static instances.