acceptodds
Under review as a conference paper at ICLR 2027

The Cost of a Rule: Why a Backdoor Needs a Count and a Wrong Label Needs a Fraction

Abstract

A network can memorise training examples one by one, or learn a rule: a pattern shared by several examples, mapped to one label and applied to unseen inputs. How many examples a rule needs has two answers that seem to conflict. A backdoor, a trigger pattern added to training images relabelled to a target class, needs a roughly fixed count of these poisoned examples, whereas a class changes its prediction only when about half of it is relabelled, a fraction. We interpret both thresholds as a sum of two costs, counted in examples, and turn this into a cost model. A build cost separates the pattern from competing features, and counter-examples, images with the same pattern under their true label, add a weighted cost that separates it from competing labels. The model gives both regimes as limits: a count when nothing contradicts the pattern, and one half inside a class, whose correctly labelled images are all counter-examples. It also makes four predictions: counter-examples leave the build cost unchanged, the threshold is linear in them, different kinds add, and a backdoor forms at parity, against an equal number of counter-examples, only if each cancels less than one poisoned example. We test these predictions with a small synthetic patch as the pattern. All four hold, and both sides of parity occur, depending on how predictive another feature in the image is, while the pattern moves mainly the build cost. We therefore read the constants as properties of the network's representation, and expect the equation's form to transfer.

Primary area:
unsupervised, self-supervised, semi-supervised, and supervised representation learning
Keywords:
memorization vs. generalization, rule learning, sample complexity, label noise, data poisoning, shortcut learning, learning thresholds, data-centric deep learning

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_6KDpOpenReview ↗
Rating
4
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

A "backdoor poisoned" example in ML is one where an attacker pairs a hidden trigger (such as a small patch in an image or rare phrase in text) with a deliberately set incorrect label. The authors present a formula that relates the number of poisoned examples to the number of poison-counterexamples (ones with that pattern but correctly labeled) in order for an attack to succeed or fail.

Critical strengths
  1. Treating counter-examples as a priced additive term is a novel and interesting approach.
  2. The predictions from this equation are carefully tested, including a robustness analysis.
  3. The finding that the weight w for CIFAR-10 is 0.73, so a backdoor forms even when counterexamples exceed poisoned examples, is a noteable discovery - and bad news for defenses against data poisoning.
Critical weaknesses
  1. Not really a weakness, but as the paper notes, Souly et al. (2025) and Yang et al. (2022) developed the count and Natarajan et al. (2013) and Patrini et al. (2017) the one-half threshold, so the contribution is the linear interpolation between them and the counter-example term.
  2. An important and highly relevent prior work missed by the authors is Manoj and Blum (NeurIPS 2021), "Excess Capacity and Backdoor Poisoning", which attempts to provide a theoretical framework to explain poisoning.
  3. Study is limited to CFAR-10; could this be a phenomena of that particular model?
Questions for authors

The title promises a explanation ("Why") for the relationship between between poisoning and counterexamples. The paper, however, demonstrates the relationship but does not explain it. Can the authors speculate on why it holds?

Reviewer_4qctOpenReview ↗
Rating
1
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies how many poisoned examples are needed for a backdoor to generalize to unseen images. It models this threshold as a fixed build cost plus a weighted count of correctly labeled images carrying the trigger. Image classification experiments test this model and relate it to the threshold for class label flipping.

Critical strengths
  • The research problem is framed in an interesting way. It proposes a hypothesis that links the number of poisoned examples needed for a backdoor to the number of correctly labeled images carrying the same trigger. This offers a simple way to compare backdoor learning with class label flipping.
Critical weaknesses
  • The contribution beyond existing learning theory is unclear. The counter-examples can be viewed as hard negatives for a model that uses the trigger to predict the target class. Sagawa et al. (2020), which the paper cites, already study why models use spurious features and memorize conflicting examples. Manoj and Blum (2021) also relate backdoor attacks to model capacity and give conditions where the required poison count does not grow with the clean dataset. The paper should explain what its cost model adds beyond these results.

  • The work is built on heavy empirical hypotheses and heurstic formulations. However, the experiments employed to verify these hypotheses and heurstics are not in convincing scales. The results are based on SmallCNN trained with CIFAR10 and ResNet-18 trained with Imagenet32x32. In addition, this paper is hard for human readers to follow. Editorial-wise, the writing appears heavily AI touched and is difficult to follow. It uses unfamiliar wording for standard backdoor concepts, and the reasoning is often unclear.

Questions for authors
  1. Why is the threshold k∗k^* modeled as a linear function of mm? What justifies the assumption that each additional counter-example has the same average effect?

  2. What does the cost model explain beyond existing work on learning from hard negative examples and on backdoor sample complexity? Please clarify how the proposed costs relate to those explanations.

  3. Does the full model hold on larger datasets and stronger models when counter-examples are included? The ImageNet32 experiment only tests the case without them.

2 comments

Thank you.

The shared points (where Eq. 1 comes from, Manoj and Blum, new experiments, the rewrite) are in the general comment. Here are the ones specific to your review.

Q1, why linear. Linearity is an assumption of our model, so it is the first thing we tested. It held, in three ways. A curved term is zero over a fifteenfold range of counter-examples. Each threshold is predicted from the others. A threshold at 200 counter-examples was predicted from data up to 100: 186.6 predicted, 181.9 measured (Section 5). Within one setting (one dataset, one corpus size, one network) the weight is the average effect per counter-example, and we test that it does not change with the number of counter-examples. Between settings it does change, for example with corpus size.

Q2, relation to hard negatives and backdoor sample complexity. The two costs map onto the two literatures. The build cost is the backdoor sample complexity: the count of poisoned examples needed when nothing opposes them, which Manoj and Blum prove does not depend on the clean data (general comment). The weight is the effect of one hard negative: our counter-examples are hard negatives, images that carry the trigger under their true label. Sagawa et al. (ICML 2020) show that a network memorises such minority examples, and Qi et al. (ICLR 2023) use them to hide a backdoor; neither gives how many poisoned examples one of them cancels. What the model adds: that number (the weight), the fact that it is not always one, and that the two costs add into one threshold. Section 9 has been expanded.

Q3, larger scale. Does it hold a larger scale, yes. We added: ImageNet32 with 100 classes, 120,000 images, a ResNet-18, up to 200 counter-examples. The threshold is again a straight line, with weight 0.53 (Appendix K). One limit, stated in Appendix K: the paper reads the threshold where the target rate passes the true-label accuracy. If the threshold is read where the target rate reaches one half, the line bends on this dataset, because a quarter of the probes go to other classes. We read it the first way because it asks whether the rule beats the true label, which makes sense for any number of classes; with 100 classes the target rate can stay under one half while the rule already wins.

Terminology. The paper joins two literatures, and neither vocabulary covers both cases. "Trigger" assumes an added patch; in the label-noise case there is none. We used neutral words, and this made the paper harder for readers from the backdoor literature. Each word now has its standard term at first use, and Table 3 lists the equivalents.

We thank the reviewer for the feedback, which has substantially improved the paper. We have uploaded a revised manuscript (changes in blue). As the discussion period closes today, we would be grateful if the reviewer could let us know whether the revision addresses their concerns, and, if so, consider updating their assessment. We are happy to answer any remaining questions.

Reviewer_NGwJOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2(+1)
Presentation
2(+1)
Soundness
2
Read review
Paper summary

Summary:

This paper presents a unified equation / model describing both the effects of backdoor poisoning and label noise. These effects are normally studied separately, and so the novelty of this paper is in studying them together. The model is presented and then a range of experiments are used both to verify the model (I think) and to test whether four predictions resulting from the model actually hold in practice. These experiments are small-scale and on image data (so only one domain, and based on CIFAR-10 data). The experiments indicate that the model holds.

Contributions:

  • A unified model describing both the effects of backdoor poisoning and label noise.
  • Various conclusions / results derived from the proposed model.

Validation:

  • Experiments investigating three conditions: Backdoor, counter-example, and mislabelled examples. These appear to be fairly comprehensive, though the method isn't entirely clear to me.
Critical strengths
  1. This paper appears to examine two effects together (data poisoning and label noise) that are normally studied separately, thereby unifying the understanding of how these effects work. I feel that bringing this new understanding to the community may help advance the field in several areas and may change how future research is approached.
  2. Though the experiments focused only on datasets derived from CIFAR-10 (small, images only), the variety of experiments appears to be quite large and explores a number of factors, leading to some confidence in the proposed model.
Critical weaknesses
  1. I found the entire paper to be very difficult to follow, and therefore my understanding from reading it is limited. This clarity issue seems to stem from the writing of the paper rather than the use of complex theory beyond my familiarity. The sentence structure is unusual and there are many terms referred to before any explanation of what they are, or without any explanation. There is also unusual / confusing terminology throughout (e.g., the term "priced" is on line 214, but not found elsewhere. Why? What does this mean?). Without improving clarity, it is difficult to assess to what extent the paper is technically correct and experimentally rigorous. To be accepted, papers must convincingly demonstrate new, relevant, impactful knowledge, but the lack of clarity hinders this.
  2. It isn't entirely clear what question you are trying to answer. How much of the theory related to thresholds for data poisoning and noisy labels already exists?
Questions for authors

Clarification Requests:

  1. On line 178, you mention automated guards for excluding seeds that result in models that do not fit all images in the training set. Does this exclusion fundamentally limit the applicability of your findings? What demonstrates that your findings extend to cases where the model does not fit all training examples (which is by far more typical in practice)?
  2. Please give definitions of build cost (B), benefit (u_+), and weight (w) using equations. It is extremely unclear exactly what these are and where they come from.
  3. How did you arrive at Eq 1? Was this analytically or experimentally derived?

Updated ratings based on discussion with authors.

5 comments

Thank you.

Your review was right about clarity, and we changed the paper for each point.

The shared points (the paper's question, where Eq. 1 comes from, new experiments) are in the general comment. Here are the ones specific to your review.

Q1, networks that do not fit their training set. The paper reports networks that fit, so that every network is read in the same state. With every guard switched off the equation still holds and the numbers barely move: the weight is 0.75, against 0.73 with the guards on (Appendix J). We also trained networks that stop before they fit. Again the equation holds, but both constants (k0k_0 and wˉ\bar{w}) change. These runs are outside the paper’s scope and are not in the revision. We plan to study this case in follow-up work.

Terms used before they were defined, and Q2. Eq. 2 now defines both constants by how we measure them: the build cost is the threshold with no counter-examples, and the weight is the slope of the threshold against the number of counter-examples. BB and u+u_+ are quantities of the model. Only their ratio is measured.

Q3, Eq. 1, analytic or experimental. Neither alone: a simple model that we state and then test (please refer to the general comment).

Method and wording. Section 3 now gives the procedure in one sentence. "Priced" is replaced by "predicted". "Trained until it fits" was inexact and is corrected: training runs for a fixed number of epochs.

Thank you for your response and revisions to the paper. Some of my concerns still remain.

Q1. This clarifies somewhat, but I am still a little unsure of what you meant by excluding models that do not fit all images in the training set. You clarified the terminology that training is conducted for a fixed number of epochs, rather than until the model fits. This helps, but, again, do you exclude all seeds that do not result in models that fit to all images in the training set? If so, I am still quite concerned about the applicability of your findings. You mentioned that the equation still holds with the guards off. If so, why include the guards? I'm still unsettled in this area of your paper.

Definitions of build cost (BB), benefit (u+u_+). Your revisions help, but I still would like a clear mathematical definition (give me an equation please!). You said

the build cost is the threshold with no counter-examples

and

BB and u+u_+ are quantities of the model. Only their ratio is measured.

That explanation is not clear. What is "the threshold"? Can you give an equation? Additionally, "quantities of the model" is not specific.

Thank you

Thank you for coming back to us. Both of your points are not just fair, but important. We start with the threshold and the equations.

The threshold. Let yy be the target label, and let fk,mf_{k,m} be the network trained with kk poisoned examples and mm counter-examples. We evaluate it on unseen images x1,…,xPx_1, \dots, x_P that carry the pattern, with true classes yi≠yy_i \ne y.

T(k,m)=1P∑i=1P1[fk,m(xi)=y]T(k,m) = \frac{1}{P}\sum_{i=1}^{P} \mathbf{1}\left[f_{k,m}(x_i) = y\right]

T = target rate, label = y

A(k,m)=1P∑i=1P1[fk,m(xi)=yi]A(k,m) = \frac{1}{P}\sum_{i=1}^{P} \mathbf{1}\left[f_{k,m}(x_i) = y_i\right]

A = true label Accuracy, label = yiy_i

d(k,m)=T(k,m)−A(k,m)d(k,m) = T(k,m) - A(k,m)

So d(k,m)d(k,m) is the share of held-out images predicted as the target label, minus the share predicted as their true class. The threshold is the number of poisoned examples at which the two are equal:

k∗(m):=k  such that  d(k,m)=0.k^*(m) := k \ \text{ such that } \ d(k,m) = 0 .

In practice we fit a sigmoid (a logistic curve in log⁡k\log k) to dd”. And for the weight: “wˉ\bar{w} := slope of a straight line fitted to k∗(m)k^{\ast}(m) against mm The two constants are then k0:=k∗(0)k_0 := k^{\ast}(0)

wˉ:=slope of k∗(m) against m\bar{w} := \text{slope of } k^{\ast}(m) \text{ against } m

Eq. 1 is the model’s prediction for the threshold, not its definition: the threshold is measured from the network, and the main text gave that only in words. Section 2 now states it as an equation.

BB and u+u_+. They are parameters of the model, not measurements. The model says the rule forms when (k−wˉm) u+≥B(k - \bar{w}m)\,u_+ \ge B. Multiplying BB and u+u_+ by the same number gives the same prediction, so no experiment of ours can fix them separately; only their ratio B/u+=k0B/u_+ = k_0 is observable. To be clear, we do not have an independent equation for either one. A new Appendix L gives the full mathematical formulation (Eqs. 6 to 13) and a discussion of BB and u+u_+.

Guards. Yes: a seed is excluded if its network does not reach 0.95 training accuracy at the counts the threshold is read from. The reason is the question we ask in the paper: when does a network that can memorise the poisoned examples switch to a rule? Above the threshold the rule explains the poisoned examples, so the network does not need to memorise them. Below the threshold it can fit them only by memorising them. If the network has not fitted its training set, we cannot be sure that memorisation has taken place, and d=0d = 0 could then mean something else. The guard is therefore part of how the threshold is measured, not a filter chosen for the result. We ran a guards-off check to verify that the guards do not create the result: the weight is 0.75 without guards against 0.73 with them (Appendix J). The paper’s claims are for networks that fit their training set, and Appendix L now states this scope.

For networks that do not, our runs show the same straight line with different constants. Understanding why the constants change would need a model of the build cost and the weight in terms of the network’s internal representation, which is our future work.

Thank you for your comments. They have made the paper much stronger than it was. We now see that the mathematical formulation was a missing step, and it makes the definitions in the text clearer.

Comments on the paper

1 comment

Dear reviewers,

The discussion phase is nearing its end. If you haven't already, could you please read the author's rebuttal and respond?

Thank you & kind regards,

Your AC

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.