Efficient Preference Poisoning Attack on Offline RLHF Chenye Yang, Weiyu Xu, Lifeng Lai Abstract Offline Reinforcement Learning from Human Feedback (RLHF) pipelines such as Direct Preference Optimization (DPO) train on a pre-collected preference dataset, which makes them vulnerable to preference poisoning attack. We study label flip attacks against log-linear DPO. We first illustrate that flipping one preference label induces a parameter-independent shift in the DPO gradient. Using this key property, we can then convert the targeted poisoning problem into a structured binary sparse approximation problem. To solve this problem, we develop two attack methods: Binary-Aware Lattice Attack (BAL-A) and Binary Matching Pursuit Attack (BMP-A). BAL-A embeds the binary flip selection problem into a binary-aware lattice and applies Lenstra-Lenstra-Lovász reduction and Babai’s nearest plane algorithm; we provide sufficient conditions that enforce binary coefficients and recover the minimum-flip objective. BMP-A adapts binary matching pursuit to our non-normalized gradient dictionary and yields coherence-based recovery guarantees and robustness (impossibility) certificates for K K -flip budgets. Experiments on synthetic dictionaries and the Stanford Human Preferences dataset validate the theory and highlight how dictionary geometry governs attack success. 1 Introduction Reinforcement learning from human feedback (RLHF) is a popular approach for aligning a learned policy with human preferences when an explicit reward function is hard to specify ( 19 ; 14 ) . In many practical pipelines, the policy is trained from a pre-collected dataset of pairwise preference labels ( 19 ; 8 ; 51 ) , which is referred to as offline RLHF ( 70 ) , to differentiate it from online RLHF where the policy is learned from real-time interactions with human feedbacks ( 64 ) . Recent work has demonstrated that RLHF faces substantial security issues related to the reliability of the human preference data, i.e., when there are adversarial attacks on preferences or random noises in human preferences ( 14 ) . The preference data can be manipulated by adversaries to mislead both offline and online RLHF to produce targeted outcomes ( 10 ; 66 ; 21 ; 46 ; 49 ; 75 ) . Two types of adversarial attack models are commonly studied in offline RLHF ( 10 ; 54 ; 66 ; 46 ) : (i) label flip attack, which flips some labels within the original dataset; and (ii) data injection attack, which appends poisoned trajectories and preferences to the original dataset. In particular, ( 54 ; 10 ; 66 ) provide valuable experimental results on the impact of label flip and data injection attacks, but focus less on the theoretical analysis. ( 46 ) provides a comprehensive theoretical analysis of the effectiveness of data injection attacks, showing that to mislead offline RLHF, the attacker needs to append numerous poisoned preference pairs, with size scaling linearly with the original dataset. However, while label flip attacks on offline RLHF is practically plausible, a comprehensive theoretical study of such a setup remains an open problem. We aim to address this critical gap in this paper. Understanding this vulnerability is crucial for developing robust algorithms and ensuring the reliability of RLHF systems in real-world applications, e.g., designing helpful and harmless LLMs robust to adversarial attacks on training set. Compared with the data injection attack, the problem of understanding label flipping attack is more challenging: First, flips are limited to the original dataset: the attacker can only change labels on existing comparisons and cannot freely create arbitrary many new preference pairs. Second, the effect of flipping a single label on the learned policy is hard to predict, which makes it difficult to effectively choose which labels to attack. To our best knowledge, this work is the first to provide a theoretical analysis of label flip attacks on offline RLHF, specifically on Direct Preference Optimization (DPO) pipeline ( 51 ) under the log-linear policy class. Our focus on log-linear policies follows prior RLHF theory ( 70 ; 18 ; 46 ) and isolates the core geometric phenomenon that drives flip attacks. The main technical observation is simple but powerful: in log-linear DPO, flipping one preference label changes the gradient of the DPO objective by a vector that does not depend on the current policy parameter. The attacker’s problem can therefore be expressed in gradient space as selecting a subset of existing preference pairs whose flip-induced gradient shifts add up to (or closely approximate) a target vector, which is decided by the attacker’s desired policy to force the learner to adopt. We further show that controlling the gradient residual is a sufficient surrogate for policy-space attack success. The reduction above implies that finding the optimal targeted flip attacks is a combinatorial problem and, in general, is computationally hard. To address this, we develop two algorithms with different focuses. First, for the general minimum-flip objective, we propose a Binary-Aware Lattice Attack (BAL-A). BAL-A uses a lattice embedding that simultaneously penalizes residual error and non-binary coefficients, and then applies Lenstra-Lenstra-Lovász (LLL) basis reduction and Babai’s nearest-plane algorithm to produce an integer solution that can be interpreted as a flip pattern. We further analyze how the embedding parameter controls the method and show that sufficiently large penalty enforces small integer coefficients and the proposed method finds the true minimum-flip solution under a separation condition. Second, when the attacker has a flip budget K and the true attack is sparse, we propose Binary Matching Pursuit Attack (BMP-A), a greedy method adapted from Binary Matching Pursuit ( 65 ) . BMP-A selects examples using normalized correlations to handle non-normalized gradient columns and admits coherence-based recovery guarantees. We also provide simple robustness certificates showing when no K -flip attack can succeed. We validate the theory on synthetic dictionaries and on dictionaries constructed from the Stanford Human Preferences (SHP) dataset ( 20 ) . The synthetic setting allows controlled tests of the lattice penalty and the coherence conditions. On SHP, we observe that BAL-A’s success depends sharply on the penalty region predicted by the separation analysis, and that BMP-A benefits substantially from reducing dictionary coherence, supporting our theoretical results. Additional Related Work : Adversarial attacks on bandit and standard RL problems have been extensively studied. In these setups, the attacker manipulates rewards, actions, and transitions to force the learner toward targeted behaviors. However, attacks on RLHF changes human feedback , such as preference labels, which are discrete, and indirectly shape the learned policy, making the effect of a single corruption harder to analyze. We summarize these additional related work in Appendix A . 2 Problem Formulation 2.1 Offline RLHF and DPO In offline RLHF, we observe a fixed dataset \mathcal{D} consisting of pairwise preferences over two candidate actions/responses a under the same state/prompt s . We write each comparison as (s,a,a^{\prime},o) , where o\in\{+1,-1\} encodes which action is preferred by the human labeler. o=+1 means a\succ a^{\prime} , while o=-1 means a^{\prime}\succ a . Given a reference policy \mu with parameter \theta_{\mu} , Direct Preference Optimization (DPO) trains a parametric policy \pi_{\theta} directly from these comparisons, without explicitly fitting a reward model ( 51 ) . We focus on the log-linear policies for DPO, as defined in Definition 2.1 . Log-linear policy class is commonly considered in RLHF literature ( 70 ; 18 ; 46 ) , and it features many good properties in the further analysis. Definition 2.1 (Log-linear Policy ( 46 ) ) . Let \psi be a d -dimensional feature mapping \psi:\mathcal{S}\times\mathcal{A}\to\mathbb{R}^{d} with \max_{s,a}\|\psi(s,a)\|\leq 1 . We consider the following class of log-linear policies \forall(s,a)\in\mathcal{S}\times\mathcal{A} where \theta\in\mathbb{R}^{d} : \Pi^{\text{log}}=\left\{\pi_{\theta}:\pi_{\theta}(a\mid s)=\frac{\exp\left(\psi(s,a)^{\top}\theta\right)}{\sum_{a^{\prime}}\exp\left(\psi(s,a^{\prime})^{\top}\theta\right)}\right\}. Then, the DPO objective can be written as a regularized logistic loss over comparisons ( 51 ) : \begin{split}L_{\mathrm{DPO}}(\theta;\mathcal{D})=&-\sum_{(s,a,a^{\prime},o)\in\mathcal{D}}\log\sigma\!\left(o\cdot\beta\left(\log\frac{\pi_{\theta}(a\,|\,s)}{\mu(a\,|\,s)}\right.\right.\\ &\left.\left.-\log\frac{\pi_{\theta}(a^{\prime}\,|\,s)}{\mu(a^{\prime}\,|\,s)}\right)\right)+\frac{\lambda}{2}\,\lVert\theta-\theta_{\mu}\rVert_{2}^{2},\end{split} where \sigma(\cdot) is the sigmoid function, \beta>0 is a temperature parameter, and \lambda>0 is the regularization parameter. For reader’s convinience, we summarize the main steps of the derivation of DPO from the RLHF pipeline provided in ( 51 ) in Appendix B . 2.2 Preference Attack We study label flip attacks on offline preference datasets. The attacker selects a subset of comparisons and flips their outcomes, equivalently changing o_{i} to -o_{i} on the chosen indices. The size of the dataset is fixed. Let x\in\{0,1\}^{n} indicate which comparisons are flipped, and write \tilde{\mathcal{D}}(x) as the attacked dataset. In this paper, a targeted label flip attacker’s optimization problem is formulated as: \min_{x\in\{0,1\}^{n}}\ \|x\|_{0}\quad\text{s.t.}\quad\bigl\|\pi_{\hat{\theta}(\tilde{\mathcal{D}}(x))}-\pi^{\dagger}\bigr\|_{1}\leq\varepsilon, Here \hat{\theta}(\tilde{\mathcal{D}}(x)) is the DPO policy parameter trained on the attacked dataset, and \pi_{\hat{\theta}(\tilde{\mathcal{D}}(x))} is the correpsonding policy. In this formulation, the goal of the attacker is to force \pi_{\hat{\theta}(\tilde{\mathcal{D}}(x))} to align with a target policy \pi^{\dagger} (with parameter \theta^{\dagger} ) decided by the attacker, while modifying as few labels as possible. We also consider a budgeted variant, in which the attacker can at most flip K entries in the training dataset: \min_{x\in\{0,1\}^{n}:\ \|x\|_{0}\leq K}\ \|x\|_{0}\quad\text{s.t.}\quad\bigl\|\pi_{\hat{\theta}(\tilde{\mathcal{D}}(x))}-\pi^{\dagger}\bigr\|_{1}\leq\varepsilon, 3 Label Flip Attack on DPO 3.1 Effect of Label Flip Attack The DPO optimization problem with log-linear policy can be written as \min_{\theta}L_{\mathrm{DPO}}(\theta;\mathcal{D}) . For sample i : (s_{i},a_{i},a_{i}^{\prime},o_{i}) , the per-sample loss is \displaystyle\ell_{i}(\theta)=-\log\sigma\!\bigg(o_{i}\,\beta\bigg[\log\frac{\pi_{\theta}(a_{i}|s_{i})}{\mu(a_{i}|s_{i})}-\log\frac{\pi_{\theta}(a_{i}^{\prime}|s_{i})}{\mu(a_{i}^{\prime}|s_{i})}\bigg]\bigg). (1) Using ( 1 ), the overall DPO loss can be written as: L_{\mathrm{DPO}}(\theta;\mathcal{D})=\sum_{j\in\mathcal{D}}\ell_{j}(\theta)+\frac{\lambda}{2}\lVert\theta-\theta_{\mu}\rVert^{2}. Theorem 3.1 (Flip-induced gradient shift for log-linear DPO) . Fix a comparison (s_{i},a_{i},a_{i}^{\prime},o_{i}) with o_{i}\in\{+1,-1\} , and define the feature difference \Delta\psi_{i}:=\psi(s_{i},a_{i})-\psi(s_{i},a_{i}^{\prime})\in\mathbb{R}^{d} . Let \ell_{i}(\theta) be the per-sample DPO loss in ( 1 ), and let g_{i}(\theta):=\nabla_{\theta}\ell_{i}(\theta) . If we flip the label o_{i} to \tilde{o}_{i}=-o_{i} , and we have \tilde{g}_{i}(\theta) replacing the o_{i} with \tilde{o}_{i} in g_{i}(\theta) , then for every \theta the per-sample gradient changes by a constant vector that is independent of \theta : \Delta g_{i}:=\tilde{g}_{i}(\theta)-g_{i}(\theta)\;=\;o_{i}\,\beta\,\Delta\psi_{i}. Theorem 3.1 is the key structural property behind our attack formulation: each flipped comparison contributes a fixed “atom” in gradient space for all values of policy parameter \theta . Appendix C formalizes two related extension identities: DPO with general differentiable policy classes beyond the log-linear class has an exact but generally parameter-dependent flip-induced gradient shift, and the reward-modeling phase of RLHF has a similar parameter-independent identity for linear rewards. These identities show the potential generality of our attack formulation to other DPO policy classes and RLHF pipelines. 3.2 Formulate Label Flip Attack Problem Using Theorem 3.1 , when the attacker flip a set \mathcal{F}\subset\mathcal{D} , the attacked gradient becomes: \displaystyle\nabla_{\theta}L_{\mathrm{DPO}}(\theta;\tilde{\mathcal{D}}) \displaystyle=\sum_{j\notin\mathcal{F}}g_{j}(\theta)+\sum_{i\in\mathcal{F}}\tilde{g}_{i}(\theta)+\lambda(\theta-\theta_{\mu}) \displaystyle=\nabla_{\theta}L_{\mathrm{DPO}}(\theta;\mathcal{D})+\Delta g_{\mathcal{F}}, where \Delta g_{\mathcal{F}}:=\sum_{i\in\mathcal{F}}\Delta g_{i} is a term depending on \mathcal{F} , but not on \theta . Strong convexity of L_{\mathrm{DPO}}(\theta;\tilde{\mathcal{D}}) (Lemma E.14 ( 46 ) ) ensures that the first order condition (FOC) is enough to guarantee optimality. Then FOC minimizer for the attacked problem, \tilde{\theta} , satisfies: \nabla_{\theta}L_{\mathrm{DPO}}(\tilde{\theta};\tilde{\mathcal{D}})=\nabla_{\theta}L_{\mathrm{DPO}}(\tilde{\theta};\mathcal{D})+\Delta g_{\mathcal{F}}=0. Now we need to study: if we want the learned policy \tilde{\theta} to be some (target) policy \theta^{\dagger} , what should the set \mathcal{F} be? From the FOC above, we have: g^{\dagger}:=\nabla_{\theta}L_{\mathrm{DPO}}(\theta^{\dagger};\mathcal{D})=-\Delta g_{\mathcal{F}}=-\sum_{i\in\mathcal{F}}o_{i}\beta\,\Delta\psi_{i}, where we define g^{\dagger} as the gradient of the clean DPO loss at the target \theta^{\dagger} . For simplicity, denote v_{i}=o_{i}\beta\Delta\psi_{i} , V=[v_{1},\dots,v_{n}]\in\mathbb{R}^{d\times n} . Then the label flip attack problem becomes: \min_{\mathcal{F}}\quad|\mathcal{F}|\quad\text{s.t.}\quad\sum_{i\in\mathcal{F}}v_{i}=-g^{\dagger}. It can be seen as a binary sparse approximation problem: \displaystyle\min_{x\in\{0,1\}^{n}}\quad\mathbf{1}^{\top}x\quad\text{s.t.}\quad Vx=-g^{\dagger}. We note that, in the label flip attack problem, the matrix V is fixed and determined by the original dataset \mathcal{D} , and the target gradient -g^{\dagger} is also fixed and determined by the target policy \theta^{\dagger} . The vector x is a binary vector indicating which samples to flip in the dataset \mathcal{D} . When we allow some approximation error \varepsilon in reaching the target policy \theta^{\dagger} , we say that: a flip attack is exactly successful if Vx+g^{\dagger}=0 , and approximately successful if \|Vx+g^{\dagger}\|_{2}\leq\varepsilon. Thus, the exact and approximate flip attack problems can be written as: \displaystyle\min_{x\in\{0,1\}^{n}}\quad\mathbf{1}^{\top}x\quad\text{s.t.}\quad Vx+g^{\dagger}=0, (2) and \displaystyle\min_{x\in\{0,1\}^{n}}\quad\mathbf{1}^{\top}x\quad\text{s.t.}\quad\|Vx+g^{\dagger}\|_{2}\leq\varepsilon. (3) 3.3 From Gradient Residual to Policy Closeness For log-linear policies, prior work justifies treating a parameter-space target as a surrogate for a policy-space success criterion. In particular, Lemma E.5 of ( 46 ) relate an \ell_{1} policy-closeness constraint with tolerance \epsilon to a parameter-closeness constraint with tolerance \epsilon^{\prime} : when \epsilon^{\prime}\leq\epsilon/(2\sqrt{d}) , parameter feasibility implies policy feasibility, and they also provide conditions for the reverse implication. Motivated by this equivalence, we analyze poisoning around a target parameter \theta^{\dagger} and connect attack success to how flips perturb the DPO optimality conditions. By construction, \nabla_{\theta}L_{\mathrm{DPO}}(\theta^{\dagger};\tilde{\mathcal{D}})=\nabla_{\theta}L_{\mathrm{DPO}}(\theta^{\dagger};{\mathcal{D}})+Vx=g^{\dagger}+Vx. (4) Hence, the approximate flip-attack constraint \|Vx+g^{\dagger}\|_{2}\leq\varepsilon (5) is exactly a bound on the gradient residual at \theta^{\dagger} for the poisoned objective, i.e., it enforces that \theta^{\dagger} is an \varepsilon -stationary point of L_{\mathrm{DPO}}(\;\cdot\;;\tilde{\mathcal{D}}) . The following lemma shows that, under strong convexity, such approximate stationarity guarantees that training on \tilde{\mathcal{D}} produces a parameter (and thus a policy) close to the target. Lemma 3.2 (Gradient residual to policy closeness) . Assume L_{\mathrm{DPO}}(\;\cdot\;;\tilde{\mathcal{D}}) is differentiable and m -strongly convex in \theta , e.g., for log-linear DPO with \ell_{2} regularization, see ( 46 ) . Let \hat{\theta}:=\arg\min_{\theta}L_{\mathrm{DPO}}(\theta;\tilde{\mathcal{D}}) and define the trained policy \pi_{\theta,\tilde{\mathcal{D}}}:=\pi_{\hat{\theta}} , with target policy \pi^{\dagger}:=\pi_{\theta^{\dagger}} . If \|Vx+g^{\dagger}\|_{2}\leq\varepsilon holds, equivalently \|\nabla_{\theta}L_{\mathrm{DPO}}(\theta^{\dagger};\tilde{\mathcal{D}})\|_{2}\leq\varepsilon , then \|\hat{\theta}-\theta^{\dagger}\|_{2}\leq\varepsilon/m. (6) Moreover, for log-linear policies this parameter bound implies the policy-space guarantee \|\pi_{\hat{\theta}}-\pi^{\dagger}\|_{1}\leq\epsilon whenever \varepsilon\leq m\,\epsilon/(2\sqrt{d}) . Lemma 3.2 justifies ( 5 ) as a sufficient condition for approximate attack success in policy space. This motivates our focus on the gradient perturbation at \theta^{\dagger} ; in the log-linear DPO case, the per-example flip induces a parameter-independent gradient shift, yielding a fixed dictionary of vectors (the columns of V ) and the binary selection formulation developed before. 3.4 Feasibility of Label Flip Attack The feasibility question asks whether there exists x\in\{0,1\}^{n} such that \|Vx+g^{\dagger}\|_{2}\leq R , where R=0 for ( 2 ) and R=\varepsilon for ( 3 ). This decision problem is NP-hard in general. Equivalently, feasibility means that -g^{\dagger} lies within distance R of the finite attainable set \mathcal{A}:=\{Vx:x\in\{0,1\}^{n}\} . A target \pi^{\dagger} closer to the clean optimum \pi^{\star} generally makes the attack easier because |g^{\dagger}| is typically smaller (exactly zero if \pi^{\dagger}=\pi^{\star} ), but closeness alone is not sufficient: feasibility depends not only on \pi^{\dagger} , but also on the geometry of the dictionary V , i.e., whether -g^{\dagger} can be well approximated by a sparse binary combination of V ’s columns. Therefore, we assume in the following that a feasible flip attack exists as in Assumption 3.3 , and focus on finding the attack set \mathcal{F} and quantifying the cost of such an attack in terms of the number of flipped labels |\mathcal{F}| . Assumption 3.3 (Existence of feasible flip attack) . There exists a true binary attack vector x^{\star}\in\{0,1\}^{n} such that \|Vx^{\star}+g^{\dagger}\|_{2}\leq R . In the exact problem we take R=0 , and in the approximate problem we take R=\varepsilon . 3.5 Lower-bound of Flips We now derive a simple lower bound on the number of flipped labels |\mathcal{F}| required for a successful flipping attack. Theorem 3.4 (Norm-based lower-bound of |\mathcal{F}| ) . If the attacker achieves the exact constraint in the exact problem ( 2 ), then the number of flips ( |\mathcal{F}| or \mathbf{1}^{\top}x ) must satisfy |\mathcal{F}|\geq\|g^{\dagger}\|_{2}/(2\beta) . If the attacker is allowed tolerance \varepsilon\geq 0 and achieves the constraint in the approximate problem ( 3 ), then the number of flips must satisfy |\mathcal{F}|\geq(\|g^{\dagger}\|_{2}-\varepsilon)/(2\beta) . Theorem 3.4 shows that, the number of flips must grow at least linearly with the norm of the target gradient \|g^{\dagger}\|_{2} . The bounds do not require any structural assumptions on the attack matrix V beyond the feature norm bound from Definition 2.1 . They provide a simple necessary condition on |\mathcal{F}| under the Assumption 3.3 of a feasible flip attack. The dependence on \beta comes from the per-flip shift o_{i}\beta\Delta\psi_{i} , of which the norm is proportional to \beta . Thus, smaller \beta makes each individual label flip weaker in gradient space, so more flips may be needed to cancel a fixed g^{\dagger} . 4 Binary-Aware Lattice Attack (BAL-A) In this section, we discuss why a standard lattice formulation for the closest vector problem (CVP) can not handle the flip attack problem, even they are similar. Motivated by the limitations, we introduce a binary-aware lattice embedding combined with Babai’s nearest-plane algorithm. We derive sufficient conditions under which the result is guaranteed to be binary and recover the minimum-flip. 4.1 Lattice Method and a Binary-aware Embedding The exact flip attack is the minimum-flip feasibility problem: \min_{x\in\{0,1\}^{n}}\ \mathbf{1}^{\top}x\quad\text{s.t.}\quad Vx+g^{\dagger}=0. (7) A common approximate relaxation approach replaces the hard constraint by residual minimization, which, however, results in a different objective: \min_{x\in\{0,1\}^{n}}\ \|Vx+g^{\dagger}\|_{2}. (8) A natural relaxation of ( 8 ) is to allow integer coefficients, \min_{z\in\mathbb{Z}^{n}}\|Vz+g^{\dagger}\|_{2}, (9) and view this as a CVP in the lattice ( 30 ) L:=\{Vz:z\in\mathbb{Z}^{n}\}\subset\mathbb{R}^{d} with target t:=-g^{\dagger} . Indeed, \mathrm{dist}(L,t):=\min_{z\in\mathbb{Z}^{n}}\|Vz-t\|_{2}=\min_{z\in\mathbb{Z}^{n}}\|Vz+g^{\dagger}\|_{2} . One can then apply lattice basis reduction (e.g., LLL ( 30 ) ) and Babai’s nearest-plane algorithm ( 7 ) to obtain an integer vector z\in\mathbb{Z}^{n} that approximately solves ( 9 ). The lattice relaxation ( 9 ) is a natural starting point, but it does not directly match the binary minimum-flip model ( 7 ) in two key ways: binary coefficients, and minimum-flip objective. We summarize the mismatches in Appendix D . These issues motivate a different design: rather than solving an unrestricted integer problem and truncating afterwards, we construct a binary-aware lattice embedding where non-binary coefficients are heavily penalized in the lattice norm, so that any sufficiently short lattice vector must already correspond to a (near) binary solution. We work directly with the real-valued attack matrix V and gradient g^{\dagger} . Assume that the flip-effect vectors are uniformly bounded \|v_{i}\|_{2}\leq B ( B=2\beta , shown in Appendix J.3 ), we build a lattice in \mathbb{R}^{d+n} using the (d+n)\times(n+1) real basis B_{\mathrm{bin}}:=\begin{pmatrix}V&-g^{\dagger}\\ MI_{n}&0\end{pmatrix},\qquad M>0, whose columns are b_{i}=(v_{i};Me_{i}) for i=1,\dots,n and b_{n+1}=(-g^{\dagger};0) . For any integer vector z\in\mathbb{Z}^{n} , consider the coefficient vector u(z):=(z;-1)\in\mathbb{Z}^{n+1} , and the corresponding lattice vector y(z):=B_{\mathrm{bin}}u(z)=\begin{pmatrix}Vz+g^{\dagger}\\ Mz\end{pmatrix}\in\mathbb{R}^{d+n}. Its squared norm decomposes as \|y(z)\|_{2}^{2}=\|Vz+g^{\dagger}\|_{2}^{2}+M^{2}\|z\|_{2}^{2}. (10) Intuitively, the top block of B_{\mathrm{bin}} measures how well z approximates the target -g^{\dagger} (attack effectiveness), while the bottom block penalizes the magnitude of the coefficients z_{i} . Thus, choosing M sufficiently large discourages non-physical solutions with |z_{i}|\geq 2 , addressing the first mismatch above. Moreover, for binary flip indicators x\in\{0,1\}^{n} we have \|x\|_{2}^{2}=\mathbf{1}^{\top}x , so restricting ( 10 ) to binary vectors yields \min_{x\in\{0,1\}^{n}}\ \|Vx+g^{\dagger}\|_{2}^{2}+M^{2}\,\mathbf{1}^{\top}x, (11) which couples residual minimization with the flip count and hence address the second mismatch. In particular, on the feasible set \{x\in\{0,1\}^{n}:Vx+g^{\dagger}=0\} the residual term vanishes and ( 11 ) reduces to minimizing \mathbf{1}^{\top}x ; therefore, whenever an exact attack is achievable, minimizing \|y(x)\|_{2} over feasible binary solutions is equivalent to ( 2 ). We summarize the practical Binary-Aware Lattice Attack (BAL-A), which combines lattice embedding with Babai’s nearest-plane algorithm, in Algorithm 1 . The inputs are the dataset matrix V\in\mathbb{R}^{d\times n} , the target gradient g^{\dagger}\in\mathbb{R}^{d} , and a penalty parameter M>0 . The method first embeds the binary flip selection problem into a lattice by augmenting each column v_{i} with a scaled identity component Me_{i} , so that nearest-lattice decoding corresponds to minimizing the binary-aware objective |Vz+g^{\dagger}|_{2}^{2}+M^{2}|z|_{2}^{2} over integer vectors z . It then applies LLL reduction to obtain a better-conditioned basis and uses Babai’s nearest-plane rounding to recover an integer coefficient vector, which is mapped back to the original coordinates and then truncated to produce a candidate flip pattern. For completeness, we provide the full step-by-step procedure (including the LLL and Babai) in Appendix E . Algorithm 1 Binary-Aware Lattice Attack (BAL-A) 0: V=[v_{1},\dots,v_{n}]\in\mathbb{R}^{d\times n} , g^{\dagger}\in\mathbb{R}^{d} , M>0 , \delta\in(1/4,1) 0: \hat{x}\in\{0,1\}^{n} 1: Set b_{i}:=(v_{i};Me_{i}) , B_{e}:=[b_{1},\dots,b_{n}] , and t:=(-g^{\dagger};0) . 2: Compute an LLL-reduced basis (\tilde{B},T)\leftarrow\mathrm{LLL}_{\delta}(B_{e}) with \tilde{B}=B_{e}T . 3: Run Babai nearest-plane decoding on (\tilde{B},t) and obtain coefficients z . 4: Map back to the original embedding coordinates: x_{\mathrm{int}}\leftarrow Tz . 5: \hat{x}_{i}:=\min\{1,\max\{0,x_{\mathrm{int},i}\}\} for each i . From a computational perspective, the dominant cost of BAL-A is the lattice preprocessing on the (d+n)\times n embedded basis, that is, LLL reduction plus the linear-algebra preprocessing used by Babai. Babai itself is inexpensive once the reduced basis is available, but the preprocessing cost grows quickly with n , which is why in our experiments BAL-A is used only for small-to-moderate attacked subsets. 4.2 Theoretical Guarantees for BAL-A 4.2.1 Large M enforces binary coefficients We formalize how the penalty parameter M controls the integer coefficients in the binary-aware embedding. Lemma 4.1 (Coefficient bound for the shortest binary-aware lattice vector) . Assume the flip-effect vectors are bounded as \|v_{i}\|_{2}\leq B for all i . Suppose there exists a binary flip attack x^{\star}\in\{0,1\}^{n} with support size K^{\star}:=\|x^{\star}\|_{0} and residual \|Vx^{\star}+g^{\dagger}\|_{2}\leq R . Let z^{\mathrm{opt}}\in\arg\min_{z\in\mathbb{Z}^{n}}\|y(z)\|_{2} be any minimizer of the binary-aware lattice norm over \mathbb{Z}^{n} . Then there exists M_{0}=M_{0}(B,R,K^{\star}) such that for all M\geq M_{0} , every coordinate satisfies |z^{\mathrm{opt}}_{i}|\leq 1 , i.e., z^{\mathrm{opt}}\in\{-1,0,1\}^{n} . One explicit sufficient choice is M_{0}=(B\sqrt{K^{\star}}+\sqrt{B^{2}K^{\star}+6BR+3B^{2}})/3. (12) Lemma 4.1 shows that if there exists a reasonably good binary attack x^{\star}\in\{0,1\}^{n} , then for a sufficiently large M the global minimizer of the embedded lattice norm over \mathbb{Z}^{n} cannot contain any coefficient with magnitude \geq 2 . We do not claim the explicit threshold in ( 12 ) is tight; its role is to exhibit a provable binary-enforcing method, and the experiments confirm that it can be conservative in practice. Theorem 4.2 (Binary optimality under nonnegativity) . Under the assumptions of Lemma 4.1 , assume additionally that we restrict to nonnegative coefficients, i.e., z\in\mathbb{Z}_{\geq 0}^{n} , which is natural when each v_{i} already encodes the flip direction. Let z^{\mathrm{opt}}\in\arg\min_{z\in\mathbb{Z}_{\geq 0}^{n}}\|y(z)\|_{2} . If M\geq M_{0}(B,R,K^{\star}) , then z^{\mathrm{opt}}\in\{0,1\}^{n} and \begin{split}\|y(z^{\mathrm{opt}})\|_{2}^{2}&=\|Vz^{\mathrm{opt}}+g^{\dagger}\|_{2}^{2}+M^{2}\|z^{\mathrm{opt}}\|_{2}^{2}\\ &\leq\|y(x^{\star})\|_{2}^{2}\leq R^{2}+M^{2}K^{\star}.\end{split} Theorem 4.2 converts the coefficient bound from Lemma 4.1 into an actual \{0,1\}^{n} guarantee under the natural constraint z\in\mathbb{Z}_{\geq 0}^{n} . Thus, the optimizer of the penalized embedding is a valid flip attack, which addresses the first mismatch. 4.2.2 Small M recovers minimum-flip objective We now analyze how M controls the recovery of the minimum-flip objective in our flip attack problem. Theorem 4.3 (Minimum-residual recovers minimum-flip) . Assume the exact flip attack is feasible, and let x^{\star}\in\arg\min_{x\in\{0,1\}^{n}}\ \mathbf{1}^{\top}x\text{ s.t. }Vx+g^{\dagger}=0 . Define K^{\star}\coloneqq\mathbf{1}^{\top}x^{\star} . For each k\in\{0,1,\dots,K^{\star}-1\} define the best k -flip residual \rho_{k}:=\min_{x\in\{0,1\}^{n}:\ \mathbf{1}^{\top}x=k}\ \|Vx+g^{\dagger}\|_{2} . Consider the binary-aware surrogate objective F_{M}(x):=\|Vx+g^{\dagger}\|_{2}^{2}+M^{2}\,\mathbf{1}^{\top}x,\quad x\in\{0,1\}^{n}. If M satisfies the separation condition \rho_{k}^{2}\;>\;M^{2}\,(K^{\star}-k)\quad\text{ for all }k=0,1,\dots,K^{\star}-1, (13) then every minimizer of \min_{x\in\{0,1\}^{n}}F_{M}(x) is an optimal exact attack pattern; in particular, any minimizer is feasible ( Vx+g^{\dagger}=0 ) and has \mathbf{1}^{\top}x=K^{\star} . Theorem 4.3 states that F_{M}(x) recovers the minimum-flip in exact attack case if all under-budget patterns ( k0, \displaystyle u_{i} \displaystyle:=\frac{v_{i}}{a_{i}}, \displaystyle D \displaystyle:=\mathrm{diag}(a_{1},\dots,a_{n}), \displaystyle U \displaystyle:=[u_{1},\dots,u_{n}]=VD^{-1}. Then for any binary attack x\in\{0,1\}^{n} , we have Vx=Uz with z:=Dx , so z is K -sparse and has the same support as x , but with nonzero amplitudes \{a_{i}:x_{i}=1\} rather than 1 . This normalization explains the BMP-A selection rule: at each step, i_{t}\in\arg\max_{i\in[n]\setminus\Gamma}\ \frac{|\langle v_{i},r\rangle|}{\|v_{i}\|_{2}}=\arg\max_{i\in[n]\setminus\Gamma}\ |\langle u_{i},r\rangle| , which is the standard correlation criterion under the unit-norm dictionary U . Likewise, mutual coherence is naturally defined using normalized directions, \mu(V):=\max_{i\neq j}\frac{|\langle v_{i},v_{j}\rangle|}{\|v_{i}\|_{2}\|v_{j}\|_{2}}=\max_{i\neq j}|\langle u_{i},u_{j}\rangle|. Note, however, that passing from (V,x) to (U,z) changes the nonzero magnitudes from 1 to a_{i} ; consequently, recovery guarantees stated for unit-norm dictionaries with equal-magnitude nonzeros require a mild adjustment that depends on the column-norm ratio. 5.3 Theoretical Guarantees for BMP-A 5.3.1 Recovery of x^{\star} within budget K Under standard binary sparse-recovery conditions, we specially adapt the following guarantees to our setting. Theorem 5.3 (Recovery under coherence) . Under the K^{\star} -flip Assumption 5.1 . Let \mu(V) be defined as above and b:=\min_{1\leq i\leq n}\|v_{i}\|_{2} , B:=\max_{1\leq i\leq n}\|v_{i}\|_{2} . If \mu(V)<\frac{b}{(2K^{\star}-1)B} (15) and \varepsilon<(b-(2K^{\star}-1)\mu(V)B)/2, (16) then BMP-A (Algorithm 2 ), selects an index in \mathrm{supp}(x^{\star}) at each iteration. Consequently, after K^{\star} iterations it exactly recovers \mathrm{supp}(x^{\star}) and returns a binary vector \hat{x} with \mathrm{supp}(\hat{x})=\mathrm{supp}(x^{\star}) . Moreover, once the correct support has been selected, r^{K^{\star}}=y-V\hat{x}=y-Vx^{\star}=e , so the stopping rule \|r\|_{2}\leq\varepsilon triggers no later than iteration K^{\star} . Theorem 5.3 is the direct analog of the coherence condition in ( 65 ) , but adapted to non-normalized columns through the norm range b\leq\|v_{i}\|_{2}\leq B . Let \rho:=B/b , the mutual coherence requirement scales as \mu(V)\lesssim\frac{1}{(2K^{\star}-1)\rho} : highly non-uniform column norms (large \rho ) make recovery more stringent. When b=B , e.g., after normalization, ( 15 )–( 16 ) reduce to the standard guarantee of ( 65 ) . 5.3.2 Impossibility conditions for K -flip attack We now give sufficient conditions under which no K -flip attack can succeed, independent of specific attack algorithms. Theorem 5.4 (Spectral norm and coherence impossibility) . Let B:=\max_{i}\|v_{i}\|_{2} , \mu(V) be defined as above, and \|V\|_{2} be the spectral norm of V . Fix a budget K\geq 1 and tolerance \varepsilon\geq 0 . If \|g^{\dagger}\|_{2}-\varepsilon>\sqrt{K}\|V\|_{2}, (17) or \bigl(\|g^{\dagger}\|_{2}-\varepsilon\bigr)^{2}>B^{2}\bigl(K+\mu(V)\,K(K-1)\bigr), (18) then there does not exist any x\in\{0,1\}^{n} with \|x\|_{0}\leq K such that \|Vx+g^{\dagger}\|_{2}\leq\varepsilon . In particular, ( 17 ) is a spectral-norm certificate, while ( 18 ) is a coherence-based refinement. Theorem 5.4 provides sufficient conditions under which a K -flip attacker cannot drive the gradient residual at \theta^{\dagger} below \varepsilon . It shows that the success of any label flip attack is limited by the geometry and scale of the flip-effect dictionary V . The spectral-norm condition ( 17 ) is universal: it only depends on the global operator norm \|V\|_{2} and scales as \sqrt{K} . The coherence condition ( 18 ) is more refined: it separates the per-example strength B from the directional similarity \mu(V) . When columns are weak (small B ) and point in diverse directions (small \mu(V) ), even the best choice of K flips cannot create a large enough shift to cancel g^{\dagger} . For example, when K=1 , the coherence condition reduces to the simple no-single-flip condition \|g^{\dagger}\|_{2}-\varepsilon>B . In the normalized case B=1 , it becomes (\|g^{\dagger}\|_{2}-\varepsilon)^{2}>K+\mu(V)K(K-1) , making explicit that larger budgets and more coherent dictionaries make attacks easier. These are certificates of robustness of DPO: failing them does not imply an attack exists, but satisfying them rules out all K -flip attacks, independent of specific attack algorithms. 6 Experiments and Results In this section, we evaluate the proposed methods on both synthetic and real preference datasets. 6.1 Setup We construct experiments with a ground-truth K^{\star} -flip attack pattern following Assumption 3.3 . In each trial, we sample a support S\subseteq\{1,\dots,n\} with |S|=K^{\star} , set x^{\star}=\mathbf{1}_{S} , and define the target vector as t:=Vx^{\star}=-g^{\dagger} . Thus the exact attack constraint is feasible by construction. Given an output \hat{x} by the attack algorithm BAL-A/BMP-A, we report the fraction of indices that are recovered against x^{\star} , i.e., true positive rate (TPR), and the residual \|V\hat{x}-t\|_{2} . For synthetic data, we construct synthetic V from normalized random Gaussian columns. To validate the BAL-A separation behavior, we use a dictionary with V\in\mathbb{R}^{64\times 20} and K^{\star}=5 and sweep the lattice penalty M over 25 log-spaced values; we apply LLL pre-reduction ( \delta=0.75 ) before Babai and run 200 Monte Carlo trials. To validate BMP-A in the sparse regime, we fix a single low-coherence dictionary V\in\mathbb{R}^{200\times 200} and sweep the true sparsity level K^{\star} ; for each K^{\star} we run 200 trials and run BMP-A for exactly K^{\star} iterations. For real data, we construct V from the Stanford Human Preferences (SHP) dataset ( 20 ) by training a log-linear DPO model and forming the per-example flip-induced gradient shifts. BAL-A is evaluated on a smaller subset ( n=50 , K^{\star}=7 ) because of lattice reduction cost, while BMP-A is evaluated on a larger subset ( n=401 , K^{\star}=10 ) with budget K\leq 15 , comparing random and low-coherence subsets. These choices reflect the intended regimes of the two methods rather than treating them as interchangeable solvers: BAL-A is used to study the minimum-flip attack and requires smaller attacked subsets, while BMP-A targets the budgeted K -sparse attack and can be evaluated on larger subsets. We also include a common feasible setting with n=50 and K^{\star}=7 for both methods to give a side-by-side comparison. The SHP experiments have two downstream policy diagnostics. Attack-vs-groundtruth diagnostic retrains DPO on \tilde{\mathcal{D}}(\hat{x}) and \tilde{\mathcal{D}}(x^{\star}) and compares \pi_{\hat{\theta}} with \pi_{\theta^{\dagger}} , checking if the recovered flips reproduce the target-policy effect of the constructed attack. Clean-vs-attacked diagnostic retrains DPO on \mathcal{D} and \tilde{\mathcal{D}}(\hat{x}) and compares \pi_{\mathrm{clean}} with \pi_{\hat{\theta}} , checking if the recovered flips actually mislead downstream policy away from clean policy. Full setup details are in Appendix H . 6.2 Results 6.2.1 Validate BAL-A theory on synthetic V Figure 1 : TPR of BAL-A on synthetic V as a function of M . Figure 1 shows the support TPR of BAL-A as the lattice penalty M varies on a Gaussian synthetic dictionary. BAL-A recovers the true support almost perfectly for small M , but the recall drops quickly once M becomes moderately large. The transition happens around the separation threshold M_{\text{all sep}}\approx 0.68 (vertical line) satisfying all of those in Theorem 4.3 : below this value all the separation conditions hold and recovery is stable, while above it BAL-A increasingly miss the true flips. The binary-coefficient sufficient bound M_{0}\approx 1.69 is overly conservative in this setting. 6.2.2 Validate BMP-A theory on synthetic V Figure 2 : TPR of BMP-A on synthetic V as a function of K^{\star} . Figure 2 evaluates BMP-A on a fixed low-coherence synthetic dictionary while increasing the true number of flips K^{\star} . The constructed matrix has empirical coherence \mu(V)\approx 0.197 and the corresponding guarantee in Theorem 5.3 only covers up to K_{\text{coh}}=3 (vertical line). Within this guaranteed region, BMP-A achieves perfect support recovery. Beyond K_{\text{coh}} , the sufficient condition no longer applies, yet BMP-A still maintains high TPR and degrades gradually as K^{\star} grows, indicating that the coherence bound is conservative in this synthetic setting and that BMP-A remains effective outside the sufficient guarantee. 6.2.3 Results on real dataset SHP On SHP, the attack-vs-groundtruth results in Appendix I show that BAL-A and BMP-A can recover the constructed attack pattern and induce policies close to that trained on \tilde{\mathcal{D}}(x^{\star}) . BAL-A has perfect support recovery in the predicted M -s satisfying separation conditions, while BMP-A benefits from the low-coherence subset. The corresponding policy distances are |\pi_{\theta^{\dagger}}-\pi_{\hat{\theta}}|\approx 0.012 in the SHP runs, indicating that training on \tilde{\mathcal{D}}(\hat{x}) closely tracks training on \tilde{\mathcal{D}}(x^{\star}) . Figure 3 gives the complementary clean-vs-attacked diagnostic on the common feasible SHP case. In this matched case, BAL-A and BMP-A recover the same constructed flip pattern exactly ( \mathrm{TP}=7,\mathrm{FP}=0,\mathrm{FN}=0 ), so their attacked subsets coincide. This also allows a direct runtime check: BAL-A takes 0.6865 seconds, while BMP-A takes 1.37\times 10^{-4} seconds. We include this comparison only as a matched diagnostic, and the two methods are designed for different attack problems. Figure 3 : Clean-vs-attacked diagnostic. The curves overlap because BAL-A and BMP-A recover the same flip pattern. The clean-vs-attacked distance \|\pi_{\mathrm{clean}}-\pi_{\hat{\theta}}\|_{1} stabilizes to around 0.224 , which is about 19 times the attack-vs-groundtruth distance of 0.012 . Thus the attack results do not merely recover the true flip pattern, they also mislead downstream DPO toward the target policy and away from the clean retraining baseline. 7 Conclusion We have studied label flip preference attacks on offline RLHF, specifically targeting the log-linear DPO pipeline. We have illustrated the effect of flipping one preference label on the gradient of the DPO objective, and converted the attack problem to a binary sparse approximation problem in the per-sample gradient space. To solve it, we have proposed BAL-A algorithm, and provided sufficient conditions for binary coefficients and objective recovering. In practice, with budget K , we have also considered the K -flip attack problem and propose BMP-A, and provided a coherence-based recovery guarantee. We have also provided two impossibility conditions under which no K -flip attack can succeed. We have provided extensive experiments on both synthetic and real data to validate the theory. Our goal is to understand the vulnerability of offline RLHF to adversarial preference poisoning, and to motivate robust algorithms that can defend against such attacks. As a first step, we limit our study to label flips in log-linear DPO with attacker access to white-box feature mapping \psi . These assumptions give an abstraction of general RLHF while leaving broader attack and defense settings for future work. Acknowledgements The work of Chenye Yang and Lifeng Lai was supported in part by the National Science Foundation under grants CCF-2232907 and ECCS-2448268. The work of Weiyu Xu was supported by the National Science Foundation under grant ECCS-2133205. Impact Statement This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here. Appendix A Introduction: Additional Related Work A.1 Adversarial Attacks on Bandits A line of work has studied adversarial attacks on bandit problems, including multi-armed bandits (MAB) ( 28 ; 34 ; 35 ; 42 ; 74 ) , linear contextual bandits ( 40 ; 23 ; 37 ) , and dueling bandits ( 22 ; 2 ; 57 ) . These works have demonstrated that bandit algorithms are vulnerable to adversarial manipulation. In the MAB setting, the learner takes an action by selecting one arm each round and observes its reward ( 56 ; 3 ; 4 ) . An adversary can manipulate the reward signals to mislead the learning algorithm into selecting a target arm more frequently ( 28 ; 34 ; 42 ) , or corrupt the action signals to influence the learning process ( 35 ) . Most of these existing work focused on the stationary random rewards setting, in which the distribution of reward of each arm does not change over time. Some ( 42 ) studied the adversarial setting, in which the reward given by the environment can be arbitrarily chosen ( 4 ; 80 ) . Other work ( 74 ) considered non-stationary stochastic bandits, in which the reward distribution of each arm can change over time but with some constraints on the total amount of changes ( 24 ; 11 ; 5 ; 12 ; 17 ) . In linear contextual bandits, the expected reward is modeled as a linear function of the context features ( 6 ; 1 ; 32 ) . Existing works on adversarial attacks against linear contextual bandits focus on the reward poisoning ( 40 ; 23 ) , where the attacker manipulates the reward signal; context poisoning ( 23 ) , where the adversary modifies the context observed without changing the reward associated with the context; and action poisoning ( 37 ) , where the adversary changes the action selected by the learner. In dueling bandits, the learner selects a pair of arms each round and observes relative feedback indicating which arm is preferred ( 76 ; 81 ; 60 ) . Prior work studies stochastic dueling bandits with adversarial corruption, where an attacker can corrupt pairwise outcomes ( 2 ) . Other works consider fully adversarial preference models, which can be viewed as an extreme form of corruption ( 22 ; 57 ) . A.2 Adversarial Attacks on Standard Reinforcement Learning Adversarial attacks on standard reinforcement learning (RL) have been widely studied under different poisoning models, where the attacker modifies the learning signals to mislead the learned policy. Common corruptions include reward poisoning (manipulating reward or cost signals) ( 27 ; 78 ; 52 ; 53 ; 9 ; 72 ; 31 ) , action poisoning (manipulating the agent’s action before it is applied) ( 36 ) , and more general environment poisoning such as manipulating transition dynamics ( 52 ; 71 ) . Poisoning has also been studied in batch setting ( 41 ) , and in dynamics-agnostic settings where attacker must learn to attack from interaction ( 62 ; 36 ; 53 ; 72 ; 31 ) . Beyond single-agent RL, adversarial attacks have been considered in more complex settings, including multi-agent RL where the attacker can corrupt rewards and/or actions ( 38 ; 69 ) , and federated RL where poisoning can exploit both the RL dynamics and the federated aggregation mechanism ( 39 ) . There is also work that characterizes limits of reward-only or action-only poisoning in episodic RL ( 55 ) , as well as work that studies optimal attack in attacker’s Markov decision process ( 45 ) . In addition, many attacks are studied specifically in deep RL, where policies are neural networks and the attacker perturbs high-dimensional observations to induce harmful actions at decision time ( 26 ; 29 ; 33 ; 44 ; 50 ; 25 ; 61 ; 48 ) . A.3 Adversarial Attacks on Reinforcement Learning from Human Feedback RLHF relies on human preference data as the training source, which is inherently different from bandit or standard RL settings that use numerical rewards. Recent works have shown that RLHF faces substantial security issues related to the reliability of preference data, i.e., when there are adversarial attacks on preferences or random noises in human preferences ( 14 ) . In offline RLHF ( 70 ) , where the learner trains on a pre-collected preference dataset ( 19 ; 47 ; 8 ; 79 ; 51 ) , preference data can be manipulated by adversaries to mislead training and induce targeted behaviors ( 54 ; 10 ; 66 ; 49 ; 46 ; 21 ) . Most existing studies demonstrate this vulnerability from data injection attacks and label flip attacks experimentally on large-scale models ( 54 ; 10 ; 66 ; 49 ; 21 ) , while ( 46 ) provides a comprehensive theoretical analysis of data injection attacks and shows that a large appended poisoned preference set may be needed to mislead offline RLHF. In online RLHF, where the agent learns from real-time interactions with human feedbacks ( 15 ; 58 ; 64 ; 77 ; 68 ) adversaries also attack the preference to manipulate the learning process ( 75 ) . Besides adversarial poisoning, the preference data is also inherently noisy due to annotation difficulty, limited expert availability, and systematic differences across annotators ( 14 ; 73 ) . Such noise can lead to hard-to-predict behaviors and potential biases in aligned model outputs. Accordingly, a line of work studies robustness of offline RLHF under noisy or partially corrupted preferences ( 73 ; 16 ; 18 ; 43 ; 67 ) . These works typically focus on random corruption models or random noise rather than a targeted adversarial attacker that strategically selects which comparisons to corrupt. Compared with attacks on standard RL and bandits, attacks on RLHF face an additional challenge: the feedback is discrete preference data, and its effect on the learned policy is less direct and harder to predict. Moreover, in label flip attack problem for offline RLHF, the attacker is restricted to manipulating a fixed preference dataset, rather than freely manipulating rewards or transitions or generating new comparison pairs. Our work focuses on this practically plausible label flip threat model and provides a theoretical analysis for DPO under the log-linear policy class. Appendix B Problem Formulation: Offline RLHF Pipeline and DPO Derivation ( 51 ) This appendix provides a short summary that connects the standard offline RLHF pipeline to the DPO objective used in the main paper. We note that these derivations were done in ( 51 ) with a slightly different notation. We include them here for readers’ convenience. The subsequent attack formulation and guarantees do not depend on the intermediate reward-modeling step. RLHF frameworks usually combine three interconnected processes: feedback collection, reward modeling, and policy optimization ( 19 ; 14 ) . Once given two answers a_{1} and a_{2} for the same prompt s , the human labeler is asked to compare the two answers and give their preference, denoted as a_{w}\succ a_{l}\mid s where a_{w} is the preferred answer and a_{l} is the dispreferred answer in the pair (a_{1},a_{2}) . Note that to match the notation in ( 51 ) , this appendix writes each comparison as (s,a_{w},a_{l}) , so the label is implicit. This is equivalent to the main-text notation (s,a,a^{\prime},o) with o\in\{+1,-1\} by setting (a_{w},a_{l})=\begin{cases}(a,a^{\prime}),&o=+1,\\ (a^{\prime},a),&o=-1.\end{cases} Equivalently, given (s,a_{w},a_{l}) one can take (s,a,a^{\prime},o)=(s,a_{w},a_{l},+1) . We assume that there is some latent reward model r^{*}(a,s) for the prompt s and the answer a , which can not be observed by anyone. Bradley-Terry model ( 13 ) describes the human preference distribution p^{*} for pairwise comparisons: p^{*}(a_{1}\succ a_{2}\mid s)=\frac{\exp(r^{*}(s,a_{1}))}{\exp(r^{*}(s,a_{1}))+\exp(r^{*}(s,a_{2}))}. In the offline RLHF setting, the agent has access to a static dataset of comparisons \mathcal{D}=\{s^{(i)},a_{w}^{(i)},a_{l}^{(i)}\}_{i=1}^{N} sampled from p^{*} . Using the dataset \mathcal{D} , the agent can learn a reward model r_{\phi}(s,a) parameterized by \phi via maximum likelihood estimation (MLE). The negative log-likelihood loss function is defined as: L_{\text{RLHF}}(r_{\phi},\mathcal{D})=-\mathbb{E}_{(s,a_{w},a_{l})\sim\mathcal{D}}\left[\log\sigma(r_{\phi}(s,a_{w})-r_{\phi}(s,a_{l}))\right], where \sigma(x)=\frac{1}{1+\exp(-x)} is the sigmoid function for the Bradley-Terry model. Then a RL algorithm is used to optimize a policy \pi_{\theta} parameterized by \theta with the learned reward model r_{\phi}(s,a) : \begin{split}\max_{\pi_{\theta}}&\mathbb{E}_{s\sim\mathcal{D},\,a\sim\pi_{\theta}(a\mid s)}\left[r_{\phi}(s,a)-\beta\,\mathbb{D}_{\mathrm{KL}}\left[\pi_{\theta}(a\mid s)\,\|\,\pi_{\mathrm{ref}}(a\mid s)\right]\right],\end{split} where \beta is a parameter controlling the trade-off between learning the human preferences and following the reference policy \pi_{\mathrm{ref}} . To avoid the computational cost of policy optimization by reinforcement learning in large-scale problems, DPO ( 51 ) is proposed to directly optimize the policy \pi_{\theta} with the preference data (s,a_{w},a_{l}) . Solving the policy optimization problem leads to the following optimal solution: \pi_{r}(a\mid s)=\frac{1}{Z(s)}\pi_{\text{ref}}(a\mid s)\exp\left(\frac{1}{\beta}r(s,a)\right), where Z(s)=\sum_{a}\pi_{\text{ref}}(a\mid s)\exp\left(\frac{1}{\beta}r(s,a)\right) is the partition function. Rearranging the above equation leads to: r(s,a)=\beta\log\frac{\pi_{r}(a\mid s)}{\pi_{\text{ref}}(a\mid s)}+\beta\log Z(s). Applying this reparameterization to the ground-truth reward function r^{*} and corresponding optimal policy \pi^{*} , and the Bradley-Terry model, we have: p^{*}(a_{1}\succ a_{2}\mid s)=\frac{1}{1+\exp\left(\beta\log\frac{\pi^{*}(a_{2}\mid s)}{\pi_{\text{ref}}(a_{2}\mid s)}-\beta\log\frac{\pi^{*}(a_{1}\mid s)}{\pi_{\text{ref}}(a_{1}\mid s)}\right)}. In this way, we model the human preference probability as a function of the optimal policy \pi^{*} rather than the reward function r^{*} . Therefore, the loss function in MLE for parameterized policy \pi_{\theta} can be rewritten as: \begin{split}L_{\text{DPO}}(\pi_{\theta};\pi_{\text{ref}})=&-\mathbb{E}_{(s,a_{w},a_{l})\sim\mathcal{D}}\left[\log\sigma\left(\beta\log\frac{\pi_{\theta}(a_{w}\mid s)}{\pi_{\text{ref}}(a_{w}\mid s)}-\beta\log\frac{\pi_{\theta}(a_{l}\mid s)}{\pi_{\text{ref}}(a_{l}\mid s)}\right)\right].\end{split} Solving this estimation problem leads to the desired policy \pi_{\theta} . Appendix C Label Flip Attack: Extension Identities for General DPO and RLHF This appendix records two natural extensions of Theorem 3.1 . C.1 Extension beyond log-linear DPO First, we consider DPO with differentiable policy classes beyond the log-linear class used in the main text, such as neural policies. In the log-linear case, the difference of the log-policy gradient reduces to a fixed feature difference, which makes each label flip a parameter-independent atom in the attack dictionary. Beyond this setting, the same algebra still gives an exact flip-induced gradient shift, but the atom is a policy-gradient difference and typically varies with \theta . The following proposition makes this distinction explicit: it defines a local dictionary at a target parameter \theta^{\dagger} , but does not by itself provide the fixed global dictionary used in the main attack reduction. Proposition C.1 (Flip-induced gradient shift for DPO with general differentiable policy classes) . Consider any differentiable policy class \{\pi_{\theta}\} and a fixed reference policy \mu that does not depend on \theta . For a comparison (s_{i},a_{i},a_{i}^{\prime},o_{i}) with o_{i}\in\{+1,-1\} , define q_{i}(\theta):=\log\frac{\pi_{\theta}(a_{i}\mid s_{i})}{\mu(a_{i}\mid s_{i})}-\log\frac{\pi_{\theta}(a_{i}^{\prime}\mid s_{i})}{\mu(a_{i}^{\prime}\mid s_{i})} and the per-sample DPO loss \ell_{i}(\theta;o_{i}):=-\log\sigma(o_{i}\beta q_{i}(\theta)) . If the label is flipped from o_{i} to -o_{i} , then \nabla_{\theta}\ell_{i}(\theta;-o_{i})-\nabla_{\theta}\ell_{i}(\theta;o_{i})=o_{i}\beta\left(\nabla_{\theta}\log\pi_{\theta}(a_{i}\mid s_{i})-\nabla_{\theta}\log\pi_{\theta}(a_{i}^{\prime}\mid s_{i})\right). Thus, the flip-induced gradient shift is exact but typically depends on \theta . At a fixed target \theta^{\dagger} , one may define local atoms v_{i}(\theta^{\dagger}):=o_{i}\beta\left(\nabla_{\theta}\log\pi_{\theta}(a_{i}\mid s_{i})-\nabla_{\theta}\log\pi_{\theta}(a_{i}^{\prime}\mid s_{i})\right)\bigg|_{\theta=\theta^{\dagger}}. If V_{\theta^{\dagger}}x=-g^{\dagger} , where V_{\theta^{\dagger}}:=[v_{1}(\theta^{\dagger}),\ldots,v_{n}(\theta^{\dagger})] and g^{\dagger}:=\nabla_{\theta}L_{\mathrm{DPO}}(\theta^{\dagger};\mathcal{D}) , then \theta^{\dagger} is a stationary point of the attacked DPO objective. Challenges for extending to DPO with general policy classes. The proposition shows that the flip-induced shift still has an exact first-order form, but extending the full log-linear theory to a general policy class faces three additional challenges. First, constructing V_{\theta^{\dagger}} requires per-example policy-gradient computations, such as per-sample backpropagation through a neural policy, rather than simply forming fixed feature differences. Second, because the atoms v_{i}(\theta) depend on the parameter value, the equation V_{\theta^{\dagger}}x=-g^{\dagger} is only a local first-order condition at \theta^{\dagger} . For nonconvex DPO objectives, it does not by itself imply that \theta^{\dagger} is a global optimizer of the attacked objective. Third, even a small gradient residual at \theta^{\dagger} does not automatically yield the parameter-space and policy-space guarantees in Lemma 3.2 without strong convexity. Proof of Proposition C.1 . Since the reference policy \mu is fixed, \nabla_{\theta}q_{i}(\theta)=\nabla_{\theta}\log\pi_{\theta}(a_{i}\mid s_{i})-\nabla_{\theta}\log\pi_{\theta}(a_{i}^{\prime}\mid s_{i}) . Differentiating \ell_{i}(\theta;o_{i})=-\log\sigma(o_{i}\beta q_{i}(\theta)) gives \nabla_{\theta}\ell_{i}(\theta;o_{i})=-o_{i}\beta\,\sigma(-o_{i}\beta q_{i}(\theta))\,\nabla_{\theta}q_{i}(\theta). After flipping the label, \nabla_{\theta}\ell_{i}(\theta;-o_{i})=o_{i}\beta\,\sigma(o_{i}\beta q_{i}(\theta))\,\nabla_{\theta}q_{i}(\theta). Subtracting the two gradients and using \sigma(t)+\sigma(-t)=1 yields \nabla_{\theta}\ell_{i}(\theta;-o_{i})-\nabla_{\theta}\ell_{i}(\theta;o_{i})=o_{i}\beta\,\nabla_{\theta}q_{i}(\theta), which proves the identity. The local stationarity claim follows by summing the identities over flipped indices: at \theta^{\dagger} , the attacked gradient is \nabla_{\theta}L_{\mathrm{DPO}}(\theta^{\dagger};\mathcal{D})+V_{\theta^{\dagger}}x=g^{\dagger}+V_{\theta^{\dagger}}x , which is zero if V_{\theta^{\dagger}}x=-g^{\dagger} . ∎ C.2 Extension to RLHF reward modeling Next, we consider the standard two-stage RLHF pipeline with a separately learned reward model. Unlike DPO, where the preference loss directly updates the policy parameter, the first stage fits a reward parameter \phi from the same type of pairwise comparison data. The following proposition shows that label flips induce an analogous gradient shift in the reward-modeling objective. This identity should be interpreted in reward-parameter space; its implication for the final policy depends on the subsequent policy-optimization stage. Proposition C.2 (Flip-induced gradient shift in the RLHF reward-modeling phase) . Consider the Bradley–Terry reward-modeling loss for a comparison (s_{i},a_{i},a_{i}^{\prime},o_{i}) , \ell_{i}^{\mathrm{RM}}(\phi;o_{i}):=-\log\sigma\left(o_{i}\left(r_{\phi}(s_{i},a_{i})-r_{\phi}(s_{i},a_{i}^{\prime})\right)\right), where r_{\phi} is a differentiable reward model. If the label is flipped from o_{i} to -o_{i} , then \nabla_{\phi}\ell_{i}^{\mathrm{RM}}(\phi;-o_{i})-\nabla_{\phi}\ell_{i}^{\mathrm{RM}}(\phi;o_{i})=o_{i}\left(\nabla_{\phi}r_{\phi}(s_{i},a_{i})-\nabla_{\phi}r_{\phi}(s_{i},a_{i}^{\prime})\right). In particular, if the reward is linear, r_{\phi}(s,a)=\phi^{\top}\psi(s,a) , then the shift is the parameter-independent vector o_{i}\left(\psi(s_{i},a_{i})-\psi(s_{i},a_{i}^{\prime})\right). Equivalently, in winner-loser notation (s_{i},a_{w}^{i},a_{l}^{i}) with o_{i}=+1 , the shift is \psi(s_{i},a_{w}^{i})-\psi(s_{i},a_{l}^{i}) . Challenges for extending to RLHF. The main difficulty is the two-stage nature of RLHF. The proposition gives a gradient identity only for the reward-modeling objective. A poisoned reward estimate must then pass through a separate policy-optimization stage, and the map from reward error to the final policy may depend on the RL optimizer, KL regularization, policy class, and possible nonconvexity. Therefore, the parameter-independent shift in reward-modeling phase does not by itself yield similar guarantees for final-policy manipulation as in log-linear DPO. Proof of Proposition C.2 . Let h_{i}(\phi):=r_{\phi}(s_{i},a_{i})-r_{\phi}(s_{i},a_{i}^{\prime}) . Differentiating the reward-modeling loss gives \nabla_{\phi}\ell_{i}^{\mathrm{RM}}(\phi;o_{i})=-o_{i}\,\sigma(-o_{i}h_{i}(\phi))\,\nabla_{\phi}h_{i}(\phi). After flipping the label, \nabla_{\phi}\ell_{i}^{\mathrm{RM}}(\phi;-o_{i})=o_{i}\,\sigma(o_{i}h_{i}(\phi))\,\nabla_{\phi}h_{i}(\phi). Subtracting and using \sigma(t)+\sigma(-t)=1 gives \nabla_{\phi}\ell_{i}^{\mathrm{RM}}(\phi;-o_{i})-\nabla_{\phi}\ell_{i}^{\mathrm{RM}}(\phi;o_{i})=o_{i}\,\nabla_{\phi}h_{i}(\phi), which is the stated general reward-modeling identity. If r_{\phi}(s,a)=\phi^{\top}\psi(s,a) , then \nabla_{\phi}h_{i}(\phi)=\psi(s_{i},a_{i})-\psi(s_{i},a_{i}^{\prime}) , independent of \phi . ∎ Appendix D BAL-A: Key Mismatches of the Standard Lattice Relaxation This standard lattice approach has two key mismatches (binary coefficients, and minimum-flip objective) with our flip model, which can be further categorized into three detailed mismatches: 1. Objective mismatch (minimum residual vs. minimum flips). The CVP-style formulation focuses on minimizing the residual \min_{x\in\{0,1\}^{n}}\ \|Vx+g^{\dagger}\|_{2} , whereas our flip attack is a minimum-cardinality problem: \min_{x\in\{0,1\}^{n}}\ \mathbf{1}^{\top}x . Even when an exact attack is feasible (so the residual is zero), residual minimization alone does not distinguish among multiple feasible solutions and therefore does not, in general, recover the minimum-flip pattern. 2. Unbounded integer coefficients. In ( 9 ), the coefficients z_{i} can be arbitrary integers, corresponding to “using” the same flip-effect v_{i} multiple times. In our setting, each data point can be flipped at most once, so the admissible coefficients must lie in \{0,1\} . Large integer coefficients are not meaningful as physical flip patterns. 3. No guaranteed truncation. A common workaround is to truncate an integer solution to the binary hypercube, e.g., x_{i}=\mathbf{1}\{z_{i}\geq 1\} . This nonlinear projection can destroy the relationship between \|Vz+g^{\dagger}\|_{2} and \|Vx+g^{\dagger}\|_{2} , and there is no guarantee that a near-optimal integer solution leads to a near-optimal binary solution. Appendix E BAL-A: Full Binary-Aware Lattice Attack Algorithm The Binary-Aware Lattice Attack (BAL-A) algorithm is summarized in Algorithm 1 . Here we provide more details on each step of BAL-A: 1. Construct the binary-aware lattice basis and target. (a) Form the extended basis B_{e}=[b_{1},\dots,b_{n}]\in\mathbb{R}^{(d+n)\times n},\quad b_{i}:=\begin{pmatrix}v_{i}\\ Me_{i}\end{pmatrix}, where i=1,\dots,n and e_{i} is the i -th standard basis vector in \mathbb{R}^{n} . (b) Define the target vector t:=\begin{pmatrix}-g^{\dagger}\\ 0\end{pmatrix}\in\mathbb{R}^{d+n}. Minimizing \|B_{e}x-t\|_{2} over x\in\mathbb{Z}^{n} is equivalent to minimizing \|Vx+g^{\dagger}\|_{2}^{2}+M^{2}\|x\|_{2}^{2} in the binary-aware objective. 2. Apply LLL basis reduction ( 30 ) to basis B_{e} . (a) Fix a parameter \delta\in(1/4,1) , e.g. \delta=3/4 . (b) Initialize the basis vectors b_{1},\dots,b_{n} as the columns of B_{e} and compute their Gram–Schmidt orthogonalization: b_{i}^{\ast},\ \mu_{i,j},\quad 1\leq j0 . There exist an instance (V,g^{\dagger}) for which the exact flip attack is feasible with optimal flip count K^{\star}=1 , i.e., \exists\,x^{\star}\in\{0,1\}^{n} with \|x^{\star}\|_{0}=1 and Vx^{\star}=-g^{\dagger} . But the minimizer of the surrogate problem \min_{x\in\{0,1\}^{n}}F_{M}(x) is infeasible and hence not the optimal attack pattern. Consequently, there is no universal choice of M that guarantees F_{M} recovers a feasible minimum-flip attack pattern for all instances. Proposition F.2 ( M can enforce under-selection for any sparsity level) . Fix any integer K_{0}\geq 2 and any residual scale r>0 . There exists an instance (V,g^{\dagger}) with optimal flip count K^{\star}=K_{0} , i.e., \exists\,x^{\star}\in\{0,1\}^{n} with \|x^{\star}\|_{0}=K_{0} and Vx^{\star}=-g^{\dagger} , such that for any M satisfying M^{2}>r^{2} every minimizer \hat{x} of \min_{x\in\{0,1\}^{n}}F_{M}(x) satisfies \|\hat{x}\|_{0}\leq K_{0}-1 . In particular, minimizing F_{M} does not recover the minimum-flip solution x^{\star} . Proposition F.1 shows that for any fixed M there exist instances where the F_{M} minimizer is infeasible even though a feasible exact solution exists. This rules out a universal M that guarantees attack success via minimizing F_{M} . Proposition F.2 is conceptually different: it exhibits instances with any prescribed optimum sparsity K^{\star}=K_{0} for which the F_{M} strictly prefers an attack pattern with fewer flips. Together, these results clarify that F_{M} mixes two goals: (i) promoting binary structure via regularization, (ii) recovering the minimum-flip attack pattern via residual minimization. These goals can conflict, so sufficient conditions tied to each need not admit a common choice of M on a given instance. Appendix G BAL-A: Worst-Case Performance of BAL-A We cite the following corollary and definition on the worst-case performance of Babai’s algorithm on LLL-reduced bases ( 7 ; 59 ) : Corollary G.1 . For any \delta\in(1/4,1] , Babai’s algorithm with a \delta -LLL basis solves \gamma -CVP for \gamma\leq\sqrt{n}\,(\delta-1/4)^{-n/2} . In particular, there is an efficient algorithm that solves \gamma -CVP for \gamma=2^{O(n)} . Definition G.2 ( \gamma -CVP) . For any approximation factor \gamma=\gamma(n)\geq 1 , the \gamma -Closest Vector Problem ( \gamma -CVP) is defined as follows. The input is a basis for a lattice \mathcal{L}\subseteq\mathbb{R}^{n} and a target vector t\in\mathbb{R}^{n} . The goal is to output a lattice vector x\in\mathcal{L} with \|x-t\|\leq\gamma\cdot\text{dist}(t,\mathcal{L}) . Appendix H Experiments and Results: Setup Details This section collects implementation details omitted from the main text. H.1 Synthetic Dictionaries We use synthetic V to test the theory in a controlled way. For BMP-A, the coherence guarantee is stated for a fixed dictionary; therefore we fix a single low-coherence matrix V\in\mathbb{R}^{200\times 200} and sweep the sparsity level K^{\star} . We build V by repeatedly resampling random Gaussian columns (normalized to unit norm) to reduce the maximum pairwise normalized correlation. The final constructed V has empirical mutual coherence \mu(V)\approx 0.1971 and the maximum K^{\star} satisfying the condition ( 15 ) is K_{\text{coh}}=3 . We then run 200 Monte Carlo trials per K with K\in\{1,\dots,60\} . In each trial we sample a random support S of size K^{\star} as the ground-truth flips x^{\star} , set -g^{\dagger}=\sum_{i\in S}v_{i} , and run BMP-A for exactly K^{\star} iterations to isolate whether the greedy rule selects the correct support as K^{\star} increases. For BAL-A, we study the dependence on the lattice penalty M and compare to separation thresholds. Computing the separation threshold requires combinatorial search, so we keep n small. We use a random Gaussian dictionary with unit-norm columns, with V\in\mathbb{R}^{64\times 20} , K^{\star}=5 , and 200 Monte Carlo trials. The sufficient binary coefficient bound from ( 12 ) gives M_{0}\approx 1.68817 with B=1 and R=0 . The M_{\text{all sep}} that satisfies all separation conditions in ( 13 ) is computed exactly as M_{\text{all sep}}\approx 0.68287 . For each trial we sweep M over 25 log-spaced values in [0.05,\,3.0] ; we apply LLL reduction \delta=0.75 before Babai to improve numerical stability. With n=20 , we can enumerate all k -flip candidates for k2B(R+M\sqrt{K^{\star}})+B^{2}. Equivalently, 3M^{2}-2B\sqrt{K^{\star}}\,M-(2BR+B^{2})>0, which holds whenever M exceeds the positive root of this quadratic, giving ( 12 ). Thus, for all such M , no coordinate of x^{\mathrm{opt}} can satisfy |x^{\mathrm{opt}}_{j}|\geq 2 . Therefore x^{\mathrm{opt}}\in\{-1,0,1\}^{n} . ∎ J.5 Proof of Theorem 4.2 Proof. By Lemma 4.1 , every minimizer over \mathbb{Z}^{n} satisfies |x_{i}|\leq 1 for all i when M\geq M_{0} . Under the additional restriction x_{i}\geq 0 , this implies x_{i}\in\{0,1\} for all i , hence x^{\mathrm{opt}}\in\{0,1\}^{n} . The objective bound follows from feasibility of x^{\star} and optimality of x^{\mathrm{opt}} : \|y(x^{\mathrm{opt}})\|_{2}^{2}\leq\|y(x^{\star})\|_{2}^{2}\leq R^{2}+M^{2}K^{\star} . ∎ J.6 Proof of Theorem 4.3 Proof. Since x^{\star} is feasible, F_{M}(x^{\star})=M^{2}K^{\star} . Consider any x\in\{0,1\}^{n} . If \mathbf{1}^{\top}x\geq K^{\star} , then F_{M}(x)\geq M^{2}\,\mathbf{1}^{\top}x\geq M^{2}K^{\star}=F_{M}(x^{\star}) . If \mathbf{1}^{\top}x=kM^{2}(K^{\star}-k)+M^{2}k=M^{2}K^{\star}=F_{M}(x^{\star}) . Hence no k -flip vector with k0 . Choose any dimension d\geq 1 and any n\geq 1 . Let g^{\dagger}\in\mathbb{R}^{d} be any nonzero vector with \|g^{\dagger}\|_{2}\;=\;\frac{M}{2}\;<\;M. Construct V\in\mathbb{R}^{d\times n} whose first column is v_{1}:=-g^{\dagger}, and whose remaining columns are arbitrary. Then the exact flip attack is feasible with the binary vector x^{\star}=e_{1}\in\{0,1\}^{n} : Vx^{\star}\;=\;v_{1}\;=\;-g^{\dagger}, so the optimal flip count is K^{\star}=\|x^{\star}\|_{0}=1 . Now consider the surrogate objective F_{M}(x)=\|Vx+g^{\dagger}\|_{2}^{2}+M^{2}\,\mathbf{1}^{\top}x over x\in\{0,1\}^{n} . For the zero vector, F_{M}(0)\;=\;\|g^{\dagger}\|_{2}^{2}\;=\;\frac{M^{2}}{4}. For any x\neq 0 with x\in\{0,1\}^{n} , we have \mathbf{1}^{\top}x\geq 1 , hence F_{M}(x)\;=\;\|Vx+g^{\dagger}\|_{2}^{2}+M^{2}\,\mathbf{1}^{\top}x\;\geq\;0+M^{2}\;>\;\frac{M^{2}}{4}\;=\;F_{M}(0). Therefore, the unique minimizer of \min_{x\in\{0,1\}^{n}}F_{M}(x) is \hat{x}=0 . Finally, since g^{\dagger}\neq 0 , \hat{x}=0 is infeasible for the exact attack constraint Vx+g^{\dagger}=0 (it yields residual \|g^{\dagger}\|_{2}>0 ), whereas a feasible exact solution exists with one flip. This shows that for the fixed M we constructed an instance where minimizing F_{M} fails to recover a feasible minimum-flip exact attack. Since M>0 was arbitrary, no universal choice of M can guarantee minimum-flip recovery for all instances. ∎ J.8 Proof of Proposition F.2 Proof. Fix K_{0}\geq 2 and r>0 . Choose any d\geq K_{0} and any n\geq K_{0} . Construct a dictionary whose first K_{0} columns are orthogonal vectors with equal norm r : v_{1},\dots,v_{K_{0}}\in\mathbb{R}^{d},\qquad\langle v_{i},v_{j}\rangle=0\ (i\neq j),\qquad\|v_{i}\|_{2}=r. (The remaining columns, if any, are arbitrary.) Define x^{\star}=\sum_{i=1}^{K_{0}}e_{i}\in\{0,1\}^{n},\qquad K^{\star}=\|x^{\star}\|_{0}=K_{0}, and set the noiseless target -g^{\dagger}\;=\;Vx^{\star}\;=\;\sum_{i=1}^{K_{0}}v_{i}. Then x^{\star} is feasible and achieves zero residual, hence using \|x^{\star}\|_{2}^{2}=\|x^{\star}\|_{0}=K_{0} , F_{M}(x^{\star})=0+M^{2}K_{0}. Now consider the (K_{0}-1) -flip candidate x^{\prime}=\sum_{i=1}^{K_{0}-1}e_{i} . Its residual is Vx^{\prime}-(-g^{\dagger})=\sum_{i=1}^{K_{0}-1}v_{i}-\sum_{i=1}^{K_{0}}v_{i}=-v_{K_{0}}, so \|Vx^{\prime}-(-g^{\dagger})\|_{2}^{2}=\|v_{K_{0}}\|_{2}^{2}=r^{2} , and \|x^{\prime}\|_{2}^{2}=K_{0}-1 . Therefore, F_{M}(x^{\prime})=r^{2}+M^{2}(K_{0}-1). Comparing F_{M}(x^{\prime}) and F_{M}(x^{\star}) , F_{M}(x^{\prime})r^{2}. Hence for any M satisfying M^{2}>r^{2} , the K_{0} -flip solution x^{\star} cannot minimize F_{M} , and every minimizer \hat{x} must satisfy \|\hat{x}\|_{0}\leq K_{0}-1 . ∎ J.9 Proof of Theorem 5.3 Proof. We follow the proof of Theorem 1 in Appendix B of ( 65 ) and only record the substitutions needed to match our non-normalized BMP-A. Notation substitutions. Replace the unit-norm dictionary columns A_{i} in ( 65 ) by the normalized directions u_{i}:=v_{i}/\|v_{i}\|_{2} , and denote U:=[u_{1},\dots,u_{n}] . Replace the measurement model y=Ax^{\star}+v by our target y together with the residual noise e:=y-Vx^{\star} (so \|e\|_{2}\leq\varepsilon by Assumption 5.1 ). Replace their sparsity level K by K^{\star} , their tolerance \delta by \varepsilon , and their coherence \mu(A)=\max_{i\neq j}|A_{i}^{\top}A_{j}| by \mu(V):=\max_{i\neq j}|\langle u_{i},u_{j}\rangle| . Finally, introduce the column-norm range b:=\min_{i}\|v_{i}\|_{2} and B:=\max_{i}\|v_{i}\|_{2} . Changes to Appendix B inequalities. The greedy selection rule of BMP-A is i_{k}\in\arg\max_{i\notin\Gamma_{k-1}}\frac{|\langle v_{i},r^{k-1}\rangle|}{\|v_{i}\|_{2}}=\arg\max_{i\notin\Gamma_{k-1}}|\langle u_{i},r^{k-1}\rangle|, so (B1) in Appendix B of ( 65 ) becomes \|U_{\Omega\setminus\Gamma_{k-1}}^{\top}r^{k-1}\|_{\infty}>\|U_{\Omega^{c}}^{\top}r^{k-1}\|_{\infty}. The residual decomposition (B2) is replaced by the exact identity implied by our update r\leftarrow r-v_{i} : r^{k-1}=y-\sum_{i\in\Gamma_{k-1}}v_{i}=\sum_{i\in\Omega\setminus\Gamma_{k-1}}v_{i}+e=\sum_{i\in\Omega\setminus\Gamma_{k-1}}\|v_{i}\|_{2}\,u_{i}+e. With these substitutions, the derivation of (B3) is unchanged, except that every occurrence of A^{\top}(\cdot) is replaced by U^{\top}(\cdot) and A_{\Omega\setminus\Gamma}x_{\Omega\setminus\Gamma} is replaced by V_{\Omega\setminus\Gamma}\mathbf{1} , since x^{\star} is binary on the remaining support. The two key bounds (B4) and (B5) in Appendix B of ( 65 ) now read \|U_{\Omega\setminus\Gamma}^{\top}V_{\Omega\setminus\Gamma}\mathbf{1}\|_{\infty}\geq b-(|\Omega\setminus\Gamma|-1)\mu(V)B\quad\text{and}\quad\|U_{\Omega^{c}}^{\top}V_{\Omega\setminus\Gamma}\mathbf{1}\|_{\infty}\leq|\Omega\setminus\Gamma|\mu(V)B, since \langle u_{i},v_{i}\rangle=\|v_{i}\|_{2}\geq b and |\langle u_{i},v_{j}\rangle|=\|v_{j}\|_{2}|\langle u_{i},u_{j}\rangle|\leq B\mu(V) for i\neq j . The noise bound (B6) is unchanged because \|u_{i}\|_{2}=1 : \|U_{\Omega\setminus\Gamma}^{\top}e\|_{\infty}+\|U_{\Omega^{c}}^{\top}e\|_{\infty}\leq 2\|e\|_{2}\leq 2\varepsilon. Combining these bounds yields the same correlation gap as in Appendix B of ( 65 ) provided that b-(2K^{\star}-1)\mu(V)B>2\varepsilon>0, which is exactly ( 15 )–( 16 ). Therefore, BMP-A selects an index in \Omega=\mathrm{supp}(x^{\star}) at each iteration, and after K^{\star} iterations it recovers \mathrm{supp}(x^{\star}) . Finally, once \mathrm{supp}(\hat{x})=\mathrm{supp}(x^{\star}) , we have r^{K^{\star}}=y-V\hat{x}=y-Vx^{\star}=e , so \|r^{K^{\star}}\|_{2}\leq\varepsilon and the stopping rule triggers no later than iteration K^{\star} . ∎ J.10 Proof of Theorem 5.4 Proof. We prove impossibility by upper bounding the largest gradient shift \|Vx\|_{2} achievable with at most K flips, and comparing it to the amount of shift needed to reach tolerance \varepsilon . Suppose there exists a binary vector x\in\{0,1\}^{n} with \|x\|_{0}\leq K such that \|Vx+g^{\dagger}\|_{2}\leq\varepsilon . Let r:=Vx+g^{\dagger} . By the reverse triangle inequality, \|Vx\|_{2}\;\geq\;\|g^{\dagger}\|_{2}-\|r\|_{2}\;\geq\;\|g^{\dagger}\|_{2}-\varepsilon. (28) Thus any successful K -flip attack must produce a shift of size at least \|g^{\dagger}\|_{2}-\varepsilon . Spectral norm impossibility ( 17 ). Since x is binary with at most K ones, we have \|x\|_{2}=\sqrt{\|x\|_{0}}\leq\sqrt{K} . Therefore, \|Vx\|_{2}\leq\|V\|_{2}\,\|x\|_{2}\leq\|V\|_{2}\sqrt{K}. Combining with ( 28 ) yields \|g^{\dagger}\|_{2}-\varepsilon\leq\|V\|_{2}\sqrt{K}, which contradicts ( 17 ). Coherence impossibility ( 18 ). Let S:=\mathrm{supp}(x) so that |S|=\|x\|_{0}\leq K and Vx=\sum_{i\in S}v_{i} . Write v_{i}=a_{i}u_{i} with a_{i}=\|v_{i}\|_{2} and \|u_{i}\|_{2}=1 . Expanding the squared norm and using |\langle u_{i},u_{j}\rangle|\leq\mu(V) gives \begin{split}\|Vx\|_{2}^{2}&=\Big\langle\sum_{i\in S}a_{i}u_{i},\ \sum_{j\in S}a_{j}u_{j}\Big\rangle=\sum_{i\in S}a_{i}^{2}+\sum_{\begin{subarray}{c}i,j\in S\\ i\neq j\end{subarray}}a_{i}a_{j}\langle u_{i},u_{j}\rangle\\ &\leq\sum_{i\in S}a_{i}^{2}+\mu(V)\sum_{\begin{subarray}{c}i,j\in S\\ i\neq j\end{subarray}}a_{i}a_{j}\leq|S|B^{2}+\mu(V)\,|S|(|S|-1)B^{2}\leq B^{2}\Bigl(K+\mu(V)\,K(K-1)\Bigr).\end{split} (29) Together with ( 28 ), this implies \bigl(\|g^{\dagger}\|_{2}-\varepsilon\bigr)^{2}\leq B^{2}\Bigl(K+\mu(V)\,K(K-1)\Bigr), which contradicts ( 18 ). This completes the proof. ∎