acceptodds
Under review as a conference paper at ICLR 2027

Does More Compute Make Every Adversarial Attack Transferable?

Abstract

Transferable attacks, or transferable jailbreaks, are a particularly strong version of adversarial examples that fool all learners in a class. In this work, we study when more compute enables transferable attacks. We show that, when there is a quadratic gap in computational resources between the parties, then every learnable *classification* task admits either a transferable attack or an adversarial defense. On the other hand, we prove that there exist *generative* learning tasks for which neither a transferable attack nor an adversarial defense exists at a similar resource gap. These constructions provide formal evidence that increasing inference-time compute can improve robustness, as empirically observed by Zaremba et al. (2025). Our constructions assume the existence of an array of cryptographic primitives: identity-based fully homomorphic encryption (IB-FHE), publicly verifiable zero-knowledge succinct non-interactive arguments of knowledge (zk-SNARKs), non-parallelizing languages (NPL), and incrementally verifiable computation (IVC).

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
adversarial robustness, AI safety, cryptography, transferable attacks, inference-time compute

Reviews

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

This paper studies when additional computation enables transferable adversarial attacks from a theoretical framework. The authors formally show that with a quadratic gap between attacker and defender in a classification learning task, then there exists either a transferable attack, TA (defined as an attack that causes all defenders within budget to output error), or an adversarial defense, AD, (defined as a defense that successfully answers under any attacker). The authors additionally study generative learning tasks where multiple answers can be deemed correct, wherein the authors provide formal evidence that there exist neither transferable attacks or adversarial defenses.

Critical strengths

Strengths:

  • The paper shows theoretical results for the generative learning task not reflecting the same dichotomy as the classification learning task under certain cryptographic assumptions. This is an exciting extension of the framework from Gluch et al. (2025) and is a valuable contribution to this area of research.
  • The paper is overall well written and presented.
Critical weaknesses

Weakness:

  • The framing/writing of the abstract and introduction seem to overstate the practical relevance to e.g. jailbreak attacks. The abstract explicitly states: “These constructions provide formal evidence that increasing inference-time compute can improve robustness, as empirically observed by Zaremba et al. (2025)”. I would say that the increased reasoning leading to lower attack success observed in Zaremba is a different setup that is not directly explained by your theoretical results, as “increased inference-time compute” is not the same as more LLM reasoning. All that being said I see why you cite it and that it could serve as motivation for this work. I mainly worry that the abstract and introduction makes the connection to empirical research within jailbreak attacks, prompt injection attacks, and other Adversarial ML research on language models appear stronger than it is.
  • The former point is my reasoning for giving presentation score of 2/3, as I find the current framing slightly misleading.

Minor comments (not actual weaknesses):

  • I found it slightly confusing that the appendix was supplied in supplementary materials instead of along with the main submission, as the appendix reference links then don’t work. Especially considering how fundamental results are presented in the appendix.
  • You could consider including the abbreviations you introduce (TA: Transferable attack, AD: Adversarial Defense in the abstract). It would enable readers to parse from abstract to the rest of the paper better.
Questions for authors
  • Can you clarify what the connection this work has with practical attacks on generative models, under attacks such as jailbreak attacks, prompt injection attacks, and clarify the connection your framework has with the setup from Zaremba et al. (2025).
  • Which parts of your theoretical results do you believe could generalize beyond the specific set of cryptographic assumptions and could be relevant for practical adversarial ml research?
3 comments
AuthorsOpenReview ↗

Inference-time compute and connections to LLM reasoning

Answer to Reviewer GmFa

We are very thankful for the positive feedback.

W1: Yes, you are right that the relationship of our theoretical results to practice could be explained more carefully. We agree that inference time is not equivalent to LLM reasoning; however, we believe our modeling is justified. We will include a more detailed comparison of what features our model captures and what it is missing. We believe that our model allows the inference-time algorithm to be more general than LLM reasoning phase. For example, an LLM reasoning generates its output using autoregression, while we don't impose such a restriction. We leave it for future work to consider a separation in this more restricted setting.

Setup in connection Zaremba et al. (2025). We think our modeling is close to the setup they consider. They consider how the amount of computational resources of the attacker and the model during inference influences robustness. This is exactly one of the questions we try to address. We want to stress that a priori it was not clear whether all the "thinking" (inference-time) couldn't have been "folded into" training in the setup of Zaremba et al. (2025). Empirically, such a solution is very hard to rule out. Our result proves that it is impossible in some cases.

Minor comments: 1) Yes, you are right. It would be better if we included the whole paper (main body plus the appendix) as the supplementary material. We will update it. 2) Yes, it is a good idea to introduce the abbreviations already in the abstract.

Q1 and Q2 Connection to practice and application: We think there are heuristics that can be derived from our results that can inform practical work. Some of them would require additional experimental work to test against real datasets, but we believe at least framing the questions is valuable.

Here are some practical lessons from our results:

  • for classification tasks the rule of thumb is that to defend one should square the amount of the defender's computational resources to guarantee robustness against attackers of a given size. Unless a TA exists, in which case there is no hope for any defense anyway.

  • for generative tasks the rule of thumb is to invest at least as much computational resources during inference time as the attacker spent. This is a heuristic that comes from our separation result that there are cases, where that much computation is needed to guarantee robustness (training TT, attack T\sqrt T, inference T\sqrt T). Future work should investigate with careful experimentation. Building on Zaremba et al. (2025), such experiments could lead to scaling laws for AI safety, where one could empirically test how robustness scales with the resources of training, the attacker resources, and the inference time. Our result form a basis of this investigation.

References

AuthorsOpenReview ↗

Revised version uploaded

Thank you again for your feedback and your suggestions. The abstract of the revised version now introduces transferable attacks (TAs) and adversarial defenses (ADs). Sections 1 and 4 now explain what inference-time computation means in our model, and note that it is more general than the autoregressive reasoning of language models studied by Zaremba et al. Section 4 also states the practical heuristics that our results suggest. The full paper is included in the supplementary material.

I appreciate the explanations and revisions you have made to the paper. This mostly addresses my concerns regarding the framing of practical relevance. I shall maintain my positive assessment of the paper.

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

The paper investigates the computational resources required for transferable adversarial (TA) attacks and adversarial defenses (AD). In particular the authors study the conditions under which a TA can win against computationally bounded defenders while remaining indistinguishable from natural inputs or an AD can withstand such attacks.The authors also investigate generative learning tasks and introduce active adversarial defenses (AAD), which can use additional resources to rethink how to defend against an attack, after observing the adversarial input. They use generative tasks in which an AAD succeeds against computationally bounded attackers, while ADs cannot achieve the same guarantees. They also raise interesting theoretical questions and provide a distinction between classification and generative learning tasks. I was not able to verify the cryptographic proofs in the appendix as it is not my area of expertise.

Critical strengths
  1. Interesting problem and well motivated theoretical questions.

  2. The authors raise important questions, make useful remarks and clearly address limitations.

Critical weaknesses
  1. Classification and generative tasks are claimed to behave differently as discussed in the paper, however the authors do not show a resource gap where the generative tasks fail the dichotomy and classification tasks satisfy it.

  2. The main theorem of Gluch et al. 2025 already implies a similar dichotomy at a quadratic computational cost, thus the improvement is mostly in parameters.

Questions for authors
  1. Is there a specific gap at which generative tasks fail the dichotomy while classification tasks satisfy it?

  2. Can you clarify which results are new in relation to previous work e.g., Gluch et al. 2025?

5 comments
AuthorsOpenReview ↗

Resource gaps and the novelty of the generative separation

Answer to Reviewer 7gLC

Thank you for your careful reading and for raising these questions about the resource-gap comparison. Our main technical contribution is the construction of a generative task for which an active adversarial defense (AAD) achieves robustness that no static adversarial defense (AD) can match under the stated resource bounds. Our classification dichotomy sharpens the guarantees that follow from Gluch et al. (2025) and motivated us to ask whether, in a generative task, a defender can gain robustness by performing additional computation after seeing the input. The value of the generative construction lies in proving that such a gain is possible, independently of how closely the resource gaps for classification and generation align.

We would like to address your critical points. We hope this will resolve your concerns.

W1, Q1: You are right to note that the resource gap parameter lies in a different regime for classification tasks than for generative tasks. We say it explicitly in the abstract: "On the other hand, we prove that there exist generative learning tasks for which neither a transferable attack nor an adversarial defense exists at a similar resource gap." Meaning that the two results hold for a similar resource gap. We agree that the phrasing in some other parts of the paper could be more careful to avoid confusion (e.g., line 150 in the PDF, where we say that the answer is different from that in Lemma 28).

Our classification and generation results concern nearby, but distinct, resource regimes. For every fixed ϵ>0\epsilon>0, the generative result holds at ρ=2−ϵ\rho=2-\epsilon, whereas the classification dichotomy holds at ρ=2\rho = 2, up to logarithmic factors. The two regimes thus approach the same threshold ρ=2\rho=2, but our results do not establish that they overlap. In answer to Q1, we currently do not know of a resource gap at which the classification dichotomy holds while a generative counterexample exists.

We tried to extend our proofs, but there seem to be conceptual barriers that we don't know how to overcome. We are happy to elaborate if you are interested. We leave it as a very interesting problem to analyze what happens in the regimes where our results don't cover.

W2, Q2: We agree that the trichotomy of Gluch et al. (2025) implies a TA–AD dichotomy for classification at a quadratic resource gap. The resulting dichotomy, however, couples the attack and defense guarantees in a way that can leave one branch with a vacuous distinguishing guarantee. Our direct proof gives stronger guarantees in both branches simultaneously (see Table 1).

We also give a separate construction of a classification task admitting a TA that assumes only public-key encryption, weakening the fully homomorphic encryption assumption used in Gluch et al. (2025).

The classification dichotomy motivated the question behind our main technical contribution: can a defender on a generative task gain robustness by performing additional computation after seeing the input? Under the stated assumptions and resource bounds, we construct a task on which an AAD achieves robustness that no AD with the same training budget can match. The generative setting, the notion of an active adversarial defense, and the separation between AAD and AD are all new relative to the classification framework of Gluch et al. (2025).

References

AuthorsOpenReview ↗

Revised version uploaded

Thank you again for your comments on the resource regimes and on the relation to prior work. The revised version states the two regimes explicitly and notes that they do not overlap, in the caption of Figure 2, in Remark 26 and in Open Question 1 in Section 4. Remarks 12 and 13 explain why our proof for classification does not carry over to generation, and why our separation for generation does not carry over to classification. The comparison with Gluch et al. is collected in Remark 8, Table 1 and Appendix F, which show that our dichotomy gives stronger guarantees in both alternatives. Section 2 describes our construction of a transferable attack from public-key encryption alone.

Thank you for your honest response and clarifications. The revised version presents the contributions of your work more clearly. However, as you acknowledge, your results do not establish a resource gap at which the dichotomy holds for classification but fails for generative tasks. In addition it seems that the improvement from Gluch et al. (2025) comes mainly from the generative AAD/AD separation. Thus, I am still not convinced whether the contributions of the paper are enough for a weak accept recommendation. I am keeping my weak reject recommendation for now, although it is borderline. A result at a common resource gap or framing the paper primarily around the generative tasks would probably strengthen the paper and could change my recommendation.

Reviewer_dfZoOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

This paper investigates the relationship between computational resources, transferable attacks (TAs), and adversarial defenses (ADs). For classification tasks, the authors establish a dichotomy showing that every learnable task admits either a TA or an AD under a roughly quadratic resource gap. For generative tasks, they construct a learning problem that admits neither a TA nor an AD under certain resource constraints, while an Active Adversarial Defense (AAD) can achieve robustness by performing additional computation after receiving an adversarial input. The results are established through game-theoretic arguments and cryptographic constructions.

Critical strengths
  1. Interesting theoretical contribution. The separation between AD and AAD for generative tasks is a compelling result. It formally demonstrates that additional computation performed after receiving an adversarial input can provide robustness that cannot be achieved by a static defense under the specified resource constraints.

  2. Nontrivial theoretical analysis. The paper develops a detailed cryptographic construction involving non-parallelizing languages, incrementally verifiable computation, and identity-based fully homomorphic encryption. The proof carefully addresses both the attackability of static defenses and the indistinguishability of adversarial inputs.

  3. Improved understanding of classification tasks. The classification dichotomy and the construction based on public-key encryption extend previous theoretical results, including improved quantitative guarantees and weaker assumptions for the transferable attack construction.

Critical weaknesses

W1. Potential inconsistency in the resource accounting of Lemma 28.

Lemma 28 (Appendix D) claims the existence of an adversarial defense with circuit size O(S)O(S). However, the proof on page 30 explicitly derives the size of the constructed defense as

∣BAD∣≤SL+O(S)+SE+n+O(1)=O(S+SE)|B_{\mathrm{AD}}| \leq S_L + O(S) + S_E + n + O(1) = O(S + S_E),

where SES_E is the evaluation cost of the learned model.

Unless an additional assumption such as SE=O(S)S_E = O(S) is imposed, it is unclear how this establishes the claimed O(S)O(S) bound. In fact, Corollary 29 explicitly uses O(S+SE)O(S + S_E) for the defense complexity.

Since the quantitative relationship between attacker and defender resources is central to the paper, this apparent inconsistency should be clarified.

W2. Limited interpretation of the generative separation and dependence on strong assumptions.

The generative separation is theoretically interesting, but its implications for practical inference-time reasoning require more careful discussion.

Role of inference-time computation: The constructed AAD does not reuse the learned model during inference. Instead, it performs a separate certified computation based on the received input. This differs substantially from practical reasoning models that improve their predictions through additional computation using the same learned model. The paper should more clearly distinguish these settings.

Resource constraints: The separation depends on restricting the evaluation cost of the published static model while allowing additional input-dependent computation for the AAD. Although this is a valid theoretical setting, the extent to which the result depends on this particular resource asymmetry should be discussed more explicitly.

Cryptographic assumptions: The construction relies on strong assumptions, including an average-case non-parallelizing language, an IVC scheme with specific extension properties, and an IB-FHE scheme satisfying an additional admissibility property. It would be helpful to clarify which concrete constructions satisfy all the required properties and how restrictive these assumptions are.

W3. Important conditions of the theoretical guarantees are not sufficiently emphasized in the presentation.

The paper presents its main results through intuitive informal statements, which improve accessibility but may obscure important qualifications.

Classification dichotomy: The formal statement of Lemma 28 guarantees that at least one alternative holds with frequency at least 1/21/2 over input lengths. This is weaker than a guarantee that a fixed alternative holds for all sufficiently large input lengths. This distinction should be more explicit in the main text.

Inference complexity: The informal description emphasizes approximately square-root inference-time computation, whereas Theorem 46 formally depends on the NPL hardness gap parameter η∈(1/2,1)\eta \in (1/2,1), resulting in an inference complexity of poly⁡(n)T1/(2η)\operatorname{poly}(n)T^{1/(2\eta)}. The corresponding restriction on the published model's evaluation cost should also be highlighted.

Definition of AD: The paper uses a distinguishability criterion based on differences in flag rates between adversarial and natural inputs, which differs from the definition in Gluch et al. (2025). This difference is acknowledged, but its implications for the comparison of theoretical guarantees could be explained more clearly.

These issues do not necessarily invalidate the results, but addressing them would improve the precision and accessibility of the paper.

Questions for authors
  1. Resource accounting in Lemma 28: The proof derives a defense complexity of O(S+SE)O(S + S_E), whereas Lemma 28 states O(S)O(S). Is an assumption on SES_E implicit, or should the lemma's statement be revised?

  2. Cryptographic instantiation: Can the authors identify concrete cryptographic constructions satisfying the required IB-FHE admissibility property, depth-independent evaluation overhead, and IVC extension property?

  3. Interpretation of inference-time computation: Since the constructed AAD does not reuse the published model during inference, which aspects of the theoretical separation are expected to extend to practical reasoning-based AI models?

  4. Resource asymmetry: To what extent does the separation depend on the evaluation-cost restriction imposed on static defenses? How should the result be interpreted when static and active defenses are allowed comparable online computation?

  5. Presentation of theoretical guarantees: Can the authors more explicitly state the frequency condition in Lemma 28 and the dependence on the NPL hardness gap in Theorem 46?

4 comments
AuthorsOpenReview ↗

Resource bounds and cryptographic assumptions

Answer to Reviewer dfZo

Thank you for your positive feedback as well as critical points that let us improve our writing. In the following we are addressing and clarifying the critical points in detail and answering your questions.

W1 (Potential inconsistency in the resource accounting of Lemma 28), Q1: You are right. We indeed implicitly assumed that the size SES_E of evaluation circuits for generated models is bounded by SS. Remember that attacker's size is smaller than SS and it is reasonable to assume that attackers can evaluate the model they receive. Hence, we assume that SE<SS_E < S. We will state this assumption explicitly to resolve confusion.

W2 (Role of inference-time computation), Q3: Yes, that is correct for the case of the running-time separation result. However, note that for the sample complexity separation, the inference-time computation uses private data computed and stored during the learning phase. This is much closer to the real-world situation that you describe, where the models improve their predictions using the learned model. In our case, the reasoning/inference-time uses information computed/learned during training (concretely, the signatures) that the defender keeps private (doesn't include them explicitly in ff).

W2 (Resource constraints), Q4: The separation in running time depends on restricting the evaluation cost of the published model, and some restriction of this kind is necessary. If the published model of an AD may cost as much per query as the inference of the AAD, the AD can publish that inference as its model, and the two notions coincide, as we remark after Definition 5.

We also claim that this relationship between the size of the published model and the inference time (or the attacker time) often holds in practice. Indeed, as you write in the "role of inference-time computation" question, the inference stage runs the published model many times, which implies that its running time (size) is bigger than that of the published model. The other restriction is for the published model to be smaller than the attacker, which is also natural as the attacker needs to run the model at least once.

Notice though that in sample complexity the separation does not depend on the bound on the evaluation cost and static and active defenses may use the same amount of online computation.

W2 (Cryptographic assumptions), Q2: To address the reliability of cryptographic assumptions, we will add a paragraph to appendix that names a construction for each primitive and the assumption it relies on. All assumptions are standard.

For the running-time separation, we assume (i) an IB-FHE, (ii) an IVC scheme, and (iii) an average-case non-parallelizing language with gap η∈(1/2,1)\eta\in(1/2,1). The sample-complexity separation uses the same encryption assumption, strongly unforgeable signatures, and publicly verifiable zk-SNARKs with knowledge soundness for auxiliary inputs.

(i) IB-FHE admits an instantiation under LWE, a problem studied since 2005 (Regev, 2005) and circular security of the Gentry–Sahai–Waters encryption scheme (Clear and McGoldrick, 2016; Asharov et al., 2019; Gentry et al., 2013; Chow et al., 2020). For (ii), Paneth and Pass (2022) give the required IVC extension property under LWE. For (iii), our assumption is motivated by the conjectured sequentiality of repeated squaring in RSA groups, which dates to 1996 (Rivest et al., 1996).

References

AuthorsOpenReview ↗

Separation guarantees and practical implications

W3 (Classification dichotomy rate), Q5: Indeed, in the classification setting we show that for every sufficiently large nn there is an attack or a defense. In terms of our definition of frequency, this means that there is an attack with frequency 1/21/2 or a defense with frequency 1/21/2. The frequency measures how often a scheme succeeds as nn grows. We will emphasize the difference between a guarantee for every sufficiently large nn, which implies frequency 11, and frequency 1/21/2.

Notice that the AAD construction works for all sufficiently large nn - this is the strongest possible sense.

W3 (Inference complexity), Q5: Yes, you are correct to point this out. In the revision, the Theorem 46 is stated in terms of the difficulty τ\tau, which is a free parameter, and the gap η∈(12,1)\eta\in(\frac12,1) of the NPL. The AAD trains with size τη/n\tau^\eta/n and answers with size τ⋅poly(n)\sqrt{\tau}\cdot\mathrm{poly}(n). For the "no AD" statement, the gap enters through the depth bounds τη/n\tau^\eta/n on the AD and τη−1/2/n\tau^{\eta-1/2}/n on its published model. We carefully derive these bounds and explain why they are necessary.

W3 (Definition of AD): Our goal was a natural definition of an AD in its own right, not a restatement of the definition of Gluch et al. (2025). Both definitions are meaningful, even though they capture slightly different guarantees. The AD of Gluch et al. (2025) implies our AD, with the proof and its parameters derived in the appendix, so their trichotomy also yields an attack-or-defense dichotomy under our definitions. The main reason the definitions are different is that the goals of the two papers are different. We aimed for an AD vs. TA dichotomy and they didn't.

Also notice that the dichotomy derived from Gluch et al. (2025) has weak parameters. Concretely, in the dichotomy implied by their theorem, the Indistinguishability and the Robustness sum to more than 11, so one of the two alternatives is always weak and in some regimes vacuous. Conversely, our construction has strong meaningful parameters.

We will include an elaborate comparison in the final version.

Questions

Q1. Resource accounting in Lemma 28. The assumption on the size of the evaluation circuit was implicit and justified in W1. We will state it explicitly to avoid confusion.

Q2. Cryptographic instantiation. All assumptions that we use are standard. We will add a paragraph to appendix that names a construction for each primitive and the assumption it relies on. See W2 for more details.

Q3. Interpretation of inference-time computation. We addressed this question in W2. In the sample-complexity result, AAD uses data learned during the training phase.

Our results suggest the following practical heuristics.

  • for classification tasks the rule of thumb is that to defend one should square the amount of the defender's computational resources to guarantee robustness against attackers of a given size. Unless a TA exists, in which case there is no hope for any defense anyway.

  • for generative tasks the rule of thumb is to invest at least as much computational resources during inference time as the attacker spent. This is a heuristic that comes from our separation result that there are cases, where that much computation is needed to guarantee robustness (training TT, attack T\sqrt T, inference T\sqrt T). Future work should investigate with careful experimentation. Building on Zaremba et al. (2025), such experiments could lead to scaling laws for AI safety, where one could empirically test how robustness scales with the resources of training, the attacker resources, and the inference time. Our result form a basis of this investigation.

Q4. Resource asymmetry. We addressed this question in W2. Reiterating, the evaluation-cost restriction is necessary for our time-complexity separation but is not needed for the sample-complexity result. Also, in the sample separation setting, static and active defenses may use the same amount of online computation.

Q5. Presentation of theoretical guarantees. We will carefully address the frequency condition and the dependence on the NPL hardness gap. See W3 for more details.

References

Thank you for the clear and detailed response. The clarifications on the resource accounting in Lemma 28, the necessity of the evaluation-cost restriction, the frequency condition, and the dependence on the NPL gap address my main concerns. I will keep my score of 3 (weak acceptance).

As several of the promised changes (e.g., the explicit assumption on S_E, the restated Theorem 46, the comparison with Gluch et al. (2025), and the paragraph on concrete instantiations of the cryptographic primitives) are not yet reflected in the manuscript, uploading a revised version would be very helpful for the final assessment.

AuthorsOpenReview ↗

Revised version uploaded

Thank you. In the revised version, the informal dichotomy (Lemma 7) now assumes that the models have evaluation circuits of size below SS, and the formal statement (Lemma 21) gives the size of the defense as O(S+SE)O(S+S_E). Remark 6 explains why a bound on the evaluation cost of the published model is needed for the running-time separation, while the sample-complexity separation (Theorem 24) holds for every SES_E. Theorems 9 and 23 now state the dependence on the gap η\eta of the non-parallelizing language together with this restriction. The meaning of frequency 1/21/2 is explained after Lemma 7 and in Section 3.1, and the role of inference-time computation in our two constructions is discussed in Section 4. Appendix H now includes a paragraph that names a known construction and the underlying assumption for each cryptographic primitive we use. Finally, the comparison with the trichotomy of Gluch et al. is given in Remark 8, Table 1 and Appendix F.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Revised version uploaded

We thank the reviewers again for their helpful feedback. We have uploaded a revised version of the paper, in which passages that address reviewers’ questions are marked in blue.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.