- 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
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.
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 T, attack T, inference 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