Cost-Minimized Label-Flipping Poisoning Attack to LLM Alignment

AI summary

Overview

Research area: Adversarial machine learning and LLM alignment safety — specifically data poisoning during the RLHF/DPO (reinforcement learning from human feedback / direct preference optimization) stage.

Technical level: Advanced. The paper relies on convex optimization, Lagrangian duality, Moore-Penrose pseudo-inverses, and the Bradley-Terry preference model.

Scope: A theoretical and empirical study of the minimum number of preference-label flips an attacker needs to steer an LLM's policy toward a chosen target, plus a practical post-processing method (Poisoning Cost Minimization, PCM) that reduces the cost of existing label-flipping attacks.

What This Paper Is About

LLMs are aligned to human preferences using datasets where annotators label which of two candidate outputs is better. If an annotator is malicious, they can flip those labels. Prior work has shown empirically that this works, but nobody had quantified the cheapest attack that still achieves the attacker's goal. This paper asks: given an attacker who can only flip preference labels (never change the contexts or the two outputs compared), what is the minimum cost to force the victim's optimal policy to match an attacker-chosen target policy? The authors answer this with a convex optimization formulation, derive lower and upper bounds on that cost, and turn the analysis into a tool that shrinks the cost of attacks that already exist.

Key Contributions

1. First theoretical analysis of minimal-cost label-flipping poisoning in RLHF/DPO. The paper states it is the first to theoretically characterize how many preference labels must be flipped to steer the reward model toward an attacker-specified target.

2. A convex (and, for ℓ₁ cost, linear) programming formulation. The attack-cost minimization problem in Equation (9) is reduced under Assumption 1 to the convex problem in Equation (10), with linear equality constraints Φζ = Φ(θ_A − θ_O) and box constraints −θ_O ⩽ ζ ⩽ (1 − θ_O).

3. Matching lower and upper bounds on the minimum cost. Theorem 2 gives a lower bound involving the projected difference (Φ†Φ)(θ_A − θ_O); Theorem 3 gives an upper bound built from θ* = θ_O + (Φ†Φ)(θ_A − θ_O) and the scalars α* and ᾱ.

4. Poisoning Cost Minimization (PCM), a plug-in post-processing method. Given any target preference vector θ_A — hand-crafted or produced by an existing attack such as RLHFPoison — PCM solves the optimization to produce θ_A*, discretizes it to multiples of 1/m, and flips the corresponding labels. It is attack-agnostic and can be layered onto any label-flipping attack.

Main Findings

• Cost reduction is largest when data outnumber features. The analysis shows the reduction is most pronounced "when the reward model's feature dimension is small relative to the dataset size," because Φ†Φ is an orthogonal projection onto a subspace of rank at most n (the number of features), while the data live in dimension N.

• Bounds are tight in practice. The synthetic results fit between the Theorem 2 lower bound and the quantity ‖(Φ†Φ)(θ_A − θ_O)‖₁, and the discrepancy between them is "around the factor of 3 to 4."

• Larger datasets make cheap attacks easier. With the flip rate held roughly constant, there is a higher chance of reducing attack cost as N grows, since the rank of Φ†Φ (at most n) becomes smaller relative to N.

• Better feature extractors make attacks more expensive. Proposition 4 shows that if row(Φ₁) ⊆ row(Φ₂), the minimum cost under Φ₁ is no greater than under Φ₂ — i.e., a larger number n of features yields a model more robust to label flipping.

• Granularity matters for attack quality, not much for cost. The discretization granularity m (annotations per datum) does not heavily affect cost, but a greater m achieves a smaller performance loss rate. Even with m = 1, the paper reports a performance loss rate in the range given by a sentence that is cut off in the provided text.

• Adaptive embeddings weaken the guarantees. When the embedding itself is trained (Equation 15), the optimization becomes a relaxed problem (17). The attacker does not need to use the target embedding ω_A and may pick ω̄ with a smaller cost, but Theorem 6 shows only that the relaxed cost is lower-bounded by the simpler problem (19), with equality if a suitable ω̄ exists. Solving (19) may be too conservative from the defense perspective.

• A broader attack surface than naive cost accounting suggests. Under k flipped annotations, the reachable set Θ_k^A (Equation 13) can be much wider than the naive set Θ̃_k^A (Equation 14), which the authors frame as a way to assess the security risk of letting untrusted individuals annotate data.

• Synthetic setup specifics. Experiments used synthetic embeddings drawn from a standard normal distribution, θ_O = 1, two attack targets (random flips at probability 0.1, and RLHFPoison with quality filter parameter a = 0.25 and final poisoning ratio b = 0.1), feature counts n = 1000 and n = 3000, and 5 trials per configuration. The RLHFPoison variant here maximizes the first feature of the output rather than response length.

Methodology in Plain English

The paper sets up an attacker who plays the role of an annotator. The attacker sees triplets (context, response y, response z) but can only set the binary preference label w ∈ {−1, 1}. The goal is to make the victim's trained reward model — and therefore the policy derived from it — equal a target the attacker wants.

To make this analyzable, the authors idealize the setting: the attacker is allowed to move a probability η(x, y, z) anywhere in [0, 1] rather than flipping discrete labels, and the victim minimizes the expected loss rather than the empirical loss. They assume the reward model is r(x, y) = rᵀφ(x, y), a linear head on a frozen LLM embedding, and consider both a fixed embedding and a trained embedding.

Under Assumption 1 (every difference φ(x, y) − φ(x, z) lies in the column space of Φ, the matrix of embedding differences), the attack problem collapses to a convex program whose only coupling to the data is through the linear constraint Φζ = Φ(θ_A − θ_O). For ℓ₁ cost, the problem becomes a linear program by writing ζ = ζ₊ − ζ₋ with both parts nonnegative. The authors then take the Lagrangian dual to obtain the lower bound, and construct an explicit feasible point to obtain the upper bound.

The practical version, PCM, applies the same program with the reward model's initial embedding treated as fixed, then rounds the optimal θ_A* to the grid of multiples of 1/m and flips labels accordingly. Effectiveness is measured by the ℓ₁ cost and by a "performance loss rate" (Equation 21) that compares the preference probabilities of reward models trained on θ_A versus θ_A*, normalized by the gap between θ_A and the original θ_O.

Why This Matters

Impact on research. The paper moves label-flipping attacks on RLHF/DPO from anecdotal empirical findings to a quantified, optimization-based characterization. It gives defenders a concrete notion of the worst-case region Θ_k^A that an untrusted annotator can reach for a given budget k, and shows that the intuitive budget — number of flipped labels — understates the reachable damage.

Real-world applications:

• Crowdsourced annotation platforms: operators can measure how many flips a given annotator would need to shift the reward model, and size their annotation redundancy (m) accordingly.
• Red-teaming and audits of alignment pipelines: PCM gives an automated way to check whether a proposed poisoning dataset is more expensive than necessary, i.e., whether the pipeline's cost assumptions are realistic.
• Reward-model architecture choices: Proposition 4 argues that increasing the number of features n raises attacker cost, informing decisions about embedding width versus dataset size.
• Data-quality monitoring: the gap between the lower bound and the naive cost of a suspected attack can indicate whether suspicious label patterns are genuinely costly or merely wasteful.

Industry relevance. Any organization that trains a reward model from human preference data — including those using RLHF or DPO — has an annotation supply chain that this threat model applies to directly. The paper's conclusion that cost scales with data-to-feature ratio implies that the common practice of collecting far more preference pairs than the reward head has parameters is exactly the regime where attacks are cheapest.

Future Directions

• Closing the theory–practice gap for adaptive embeddings. The analysis for trained embeddings relies on a relaxation and on the attacker not knowing or needing ω_A; whether a first-order or last-iterate guarantee can be established is left open.
• Bridging the discrete and continuous worlds. The theory assumes continuous annotation probabilities in [0, 1], while practice restricts them to multiples of 1/m. The paper reports that PCM stays effective without deteriorating attack performance, but a formal account of when discretization degrades or preserves the target reward is not given.
• Designing defenses from the bounds. The authors suggest the bounds can guide robust RLHF/DPO pipeline design and help detect low-cost poisoning, but no concrete defense is proposed or evaluated.
• Generalizing the cost measure. The formulation is written for a general norm ‖·‖ but the analysis and experiments focus on ℓ₁; other norms, and multi-objective or budget-constrained variants, remain unexplored.
• Full reporting of the empirical grid. The provided text ends mid-sentence in the results discussion (the claim about performance loss rate at m = 1), and the abstract promises evaluation "across synthetic and real LLM alignment datasets" while the detailed numerical analysis shown here is synthetic.

Target Audience

Researchers and practitioners working on LLM safety, adversarial robustness, and alignment — particularly those with a background in convex optimization or learning theory who want formal guarantees about preference-data poisoning. It is also useful for engineers responsible for RLHF/DPO data pipelines who need to reason quantitatively about how much a malicious annotator can achieve and how many redundant annotations reduce the risk. Readers without optimization background will find the theorems dense, but the PCM recipe and the qualitative finding (more features relative to data means more robustness) are accessible on their own.

Authors’ abstract

Large language models (LLMs) are increasingly deployed in real-world systems, making it critical to understand their vulnerabilities. While data poisoning attacks during RLHF/DPO alignment have been studied empirically, their theoretical foundations remain unclear. We investigate the minimum-cost poisoning attack required to steer an LLM's policy toward an attacker's target by flipping preference labels during RLHF/DPO, without altering the compared outputs. We formulate this as a convex optimization problem with linear constraints, deriving lower and upper bounds on the minimum attack cost. As a byproduct of this theoretical analysis, we show that any existing label-flipping attack can be post-processed via our proposed method to reduce the number of label flips required while preserving the intended poisoning effect. Empirical results demonstrate that this cost-minimization post-processing can significantly reduce poisoning costs over baselines, particularly when the reward model's feature dimension is small relative to the dataset size. These findings highlight fundamental vulnerabilities in RLHF/DPO pipelines and provide tools to evaluate their robustness against low-cost poisoning attacks.