Technical Summary: Efficient Preference Poisoning Attack on Offline RLHF

1. Problem Formulation

This paper investigates label flip attacks against Offline Reinforcement Learning from Human Feedback (RLHF), specifically targeting the Direct Preference Optimization (DPO) pipeline under a log-linear policy class.

In offline RLHF, a policy is trained on a pre-collected dataset of pairwise preference labels $(s, a, a', o)$, where $o \in \{+1, -1\}$ indicates human preference. The attacker's goal is to manipulate a subset of these labels (flipping $o_i$ to $-o_i$) to force the learned policy $\pi_{\hat{\theta}}$ to align with a target policy $\pi^\dagger$ (parameterized by $\theta^\dagger$) while minimizing the number of flipped labels.

The core challenge addressed is that, unlike data injection attacks where attackers can append arbitrary poisoned data, label flip attacks are constrained to the existing dataset. Furthermore, the effect of flipping a single label on the final policy is non-trivial to predict. The authors frame this as a combinatorial optimization problem: finding a binary vector $x \in \{0, 1\}^n$ (indicating which labels to flip) that minimizes the $L_0$ norm (number of flips) subject to the constraint that the resulting policy is close to the target.

2. Key Theoretical Insight

The paper's foundational contribution is Theorem 3.1, which establishes a critical structural property of log-linear DPO:

• Parameter-Independent Gradient Shift: Flipping a single preference label $o_i$ to $-o_i$ induces a change in the DPO gradient, $\Delta g_i$, that is a constant vector independent of the current policy parameters $\theta$.
• Specifically, $\Delta g_i = o_i \beta \Delta \psi_i$, where $\Delta \psi_i$ is the feature difference between the preferred and dispreferred actions.

This property allows the authors to convert the complex policy-space attack problem into a structured binary sparse approximation problem in the gradient space. The attacker's objective becomes selecting a subset of gradient vectors (columns of a matrix $V$) such that their sum approximates the negative gradient of the clean loss at the target policy, $-g^\dagger$.

3. Methodology

To solve the resulting NP-hard binary sparse approximation problem, the authors propose two distinct attack algorithms:

A. Binary-Aware Lattice Attack (BAL-A)

Designed for the general minimum-flip objective (finding the sparsest solution without a strict budget $K$).

• Approach: The authors embed the binary selection problem into a lattice structure. They construct a basis where the top block measures the residual error ($\|Vz + g^\dagger\|^2$) and the bottom block penalizes non-binary coefficients ($M^2 \|z\|^2$).
• Algorithm:
  1. Construct a binary-aware lattice basis.
  2. Apply Lenstra-Lenstra-Lovász (LLL) basis reduction to obtain a well-conditioned basis.
  3. Use Babai's nearest-plane algorithm to find the closest lattice vector.
  4. Map the integer solution back to the original coordinates and truncate to binary.
• Theoretical Guarantees: The authors provide sufficient conditions on the penalty parameter $M$ to ensure that:
  1. The integer coefficients are restricted to $\{0, 1\}$ (binary).
  2. The solution recovers the true minimum-flip attack pattern under a "separation condition" regarding the residual errors of under-budget solutions.

B. Binary Matching Pursuit Attack (BMP-A)

Designed for the budgeted $K$-flip scenario, where the attacker is limited to flipping at most $K$ labels.

• Approach: This is a greedy algorithm adapted from Binary Matching Pursuit (BMP). It iteratively selects the sample whose flip-induced gradient shift has the highest normalized correlation with the current residual.
• Adaptation: Unlike standard sparse recovery, the gradient columns in this problem are not normalized. BMP-A handles this by using normalized correlations ($\frac{|\langle v_i, r \rangle|}{\|v_i\|_2}$) for selection while updating the residual with the original unnormalized vectors.
• Theoretical Guarantees:
  • Recovery: Under a mutual coherence condition on the dictionary $V$ (adjusted for non-uniform column norms), BMP-A is guaranteed to recover the support of the true attack vector within $K^\star$ iterations.
  • Impossibility (Robustness): The authors derive sufficient conditions (based on spectral norm and coherence) under which no $K$-flip attack can succeed. If the target gradient shift required exceeds the maximum possible shift achievable by $K$ flips (given the geometry of $V$), the attack is impossible.

4. Experimental Results

The authors validate their theory on both synthetic and real-world datasets:

• Synthetic Dictionaries:
  • BAL-A: Demonstrated that the True Positive Rate (TPR) of support recovery is high when the lattice penalty $M$ is below a theoretically predicted separation threshold. Above this threshold, performance degrades, confirming the theoretical trade-off.
  • BMP-A: Showed perfect support recovery within the coherence-based theoretical bounds. Beyond these bounds, the algorithm remained effective, suggesting the theoretical bounds are conservative.
• Stanford Human Preferences (SHP) Dataset:
  • Applied to log-linear DPO models trained on real preference data.
  • BAL-A: Successfully recovered attack patterns on small subsets, with performance aligning with the separation analysis.
  • BMP-A: Demonstrated that reducing the coherence of the gradient dictionary (via subset selection) significantly improves attack success rates and residual reduction.
  • Downstream Impact: Experiments showed that even with imperfect support recovery, the resulting policies trained on attacked datasets were close to the target policy, validating the gradient residual as a sufficient surrogate for policy-space success.

5. Significance and Claims

The paper claims to be the first theoretical analysis of label flip attacks on offline RLHF, specifically for the DPO pipeline. Its significance lies in:

1. Bridging the Gap: While data injection attacks have been theoretically analyzed, label flip attacks were previously understood primarily through empirical observation. This work provides a rigorous combinatorial and geometric framework for understanding them.
2. Geometric Insight: It highlights that the success of such attacks is governed by the geometry of the gradient dictionary (specifically coherence and column norms). This suggests that the robustness of an RLHF system is intrinsic to the structure of its preference data.
3. Robustness Certificates: The derived impossibility conditions provide a way to certify that a specific offline RLHF setup is robust against any $K$-flip attack, regardless of the specific algorithm used by the attacker.
4. Practical Algorithms: The proposed BAL-A and BMP-A methods offer efficient, theoretically grounded strategies for evaluating the vulnerability of RLHF systems to targeted poisoning.

The authors maintain a modest tone, noting that their analysis is specific to the log-linear policy class and that the derived bounds (e.g., for BMP-A) are sufficient but not necessarily necessary conditions. They emphasize that understanding these vulnerabilities is crucial for designing robust alignment algorithms for Large Language Models (LLMs).