Why does an attacker minimising the size of a flipping perturbation pay far more compute per input than one filling a fixed radius?
answer
- one has a legal set, one does not
- two quantities pulling against each other
- every shrink has to be re-verified
- free offline, ruinous when metered
- the last bit of squeezing is the priciest
basics
~20 sFilling a fixed radius is bounded work: every candidate is allowed by construction and the search stops when its schedule ends. Minimising holds two things in tension - keep the flip, shrink the change - and must re-verify the flip at every smaller size.
solid answer
~50 sA fixed-radius attack has an easy job: the allowed set is fixed in advance, so anything it produces is admissible, and it just has to push the model as hard as it can inside that set before it runs out of work. A minimising attack has no fixed set. It must keep the label flipped while making the change smaller, and those pull against each other - shrink too far and the flip is lost, so the flip has to be re-checked every time the size comes down. In practice that means an outer trade-off between the two quantities being re-solved repeatedly, with a full inner search under each setting, and it is normal for this to cost one to two orders of magnitude more model evaluations per input. Who that bills depends on the vantage: an adversary running a weight file they extracted from an appliance pays only wall-clock time, while an adversary billed per call to a hosted endpoint often cannot afford the formulation at all.
go deeper
Recall that requiring the change to stay flipped while it is made smaller means checking the flip again and again, which is why it takes much more work than staying inside a preset limit.
Explain the mechanism: the allowed set disappears, two competing quantities have to be traded off, and each smaller candidate needs re-verification - typically one to two orders of magnitude more evaluations.
Tie the cost to the threat model: say which adversary can actually afford this and why an extracted or published weight file changes the answer from unaffordable to an afternoon.
Frame it as an exposure decision: shipping weights onto a device or into the open converts a metered attack cost into free offline compute, and that is a choice with consequences beyond this one attack.
## Where the extra work comes from Both formulations search over changes to a single input. The difference is what constrains the search. With a **fixed radius**, the constraint is a set defined before the search begins: a norm and a radius that say how far the input may move. Every candidate inside that set is admissible, so the search never has to ask whether its current answer is legal - only whether it is effective. The work is bounded: it runs its allotted effort and reports flipped or not flipped. Nothing about the result needs re-checking. With **minimisation**, there is no such set. Two quantities are in play and they pull in opposite directions. The change must be small, and the model must still read the input differently. Push the size down and the flip becomes fragile; keep the flip comfortable and the change stays larger than it needs to be. There is no single setting that resolves this, so the search has to explore the trade-off between the two - and every time it lowers the size it has to establish that the flip still holds, because a candidate that no longer flips is worthless regardless of how small it is. That is the structural reason for the cost: the fixed-radius attack does one search, and the minimising attack does a family of searches plus a verification at each level. ## What that costs, and who pays it The practical figure is that minimising an input's perturbation typically costs one to two orders of magnitude more forward and backward evaluations of the model than breaking the same input inside a preset radius. The exact factor depends on how tightly the result is squeezed - the last few percent of size reduction is the expensive part, because the search is working in a narrower and narrower region where the flip is barely holding. Who absorbs that bill is set entirely by the adversary's vantage, and this is the part interviewers actually probe: - **Weights in hand.** Someone who has a weight file - pulled off an appliance image, or simply published - runs the search on their own hardware. Nothing is metered. The only cost is wall-clock time per item, which for a batch of a few hundred items is an afternoon rather than a blocker. This is the setting where minimising results get produced. - **A metered endpoint.** Someone who has to send each candidate to a paid interface pays for every evaluation. Minimising multiplies the number of evaluations per input by a large factor, and the last stretch of squeezing is the most evaluation-hungry part of it. Under a query budget the rational adversary abandons the smallest-change goal and takes a coarser result. So the same formulation is cheap or unaffordable depending on nothing but access, which is why the cost question and the access question are really one question. ## Why an attacker accepts the bill The extra compute buys a specific property: the result is not merely a flip, it is a flip that is hard to notice. Where a machine decision is spot-checked - a routing model whose output a person also reviews - the constraint that actually binds is human perception, not a convenient constant chosen for an evaluation. A change that is comfortably inside a paper's radius may still be plainly visible or audible to that reviewer, at which point the item gets escalated and the attack has failed even though the model was fooled. Minimising is how an adversary converts free offline compute into an item that clears both the model and the person. Against that, a defender should notice that the same cost asymmetry limits where the attack shows up. A minimised perturbation is an artefact of an adversary who could search freely; if your model is only reachable through a metered interface and its weights have never left your infrastructure, an adversary is far more likely to be filling a budget than shrinking one. ## The reading that gets it wrong The weak answer is that minimising is slower because it 'runs more steps', as if the schedule were simply longer. That misses the mechanism. Running a fixed-radius search for longer produces a stronger attack inside the same set; it does not produce a smaller change, because nothing in that formulation rewards a smaller change - the search is happy to use the whole radius. The extra cost of minimising is not a longer version of the same loop; it is the price of turning one of the two quantities from a fixed constraint into something being optimised, which means the other one has to be checked over and over.
- Would simply running a fixed-radius attack for longer eventually give you the smallest change?No. That formulation has no incentive to be small - anything inside the allowed set is equally acceptable to it, so extra effort makes the attack stronger inside the set rather than tighter. Getting a minimum requires making the size the thing being reduced and the flip the thing being maintained, which is a different search with a different cost profile.
- If minimising is so expensive, why would a defensive team ever run it on their own model?Because the defender has the weights, so the search is free apart from machine time, and the output is the distribution that makes every other robustness number interpretable. Running it on a sample - a few hundred inputs rather than the whole set - is usually enough to see where the data sits and whether the radius used in the fixed-radius evaluation was chosen honestly.
saying these in an interview costs you the question
- Says it is just the same attack with more steps
- Claims a longer fixed-radius run yields the minimum
- Ignores that access decides who pays the cost
- Thinks offline search still costs the model owner queries
- Treats the extra compute as buying a stronger flip rather than a quieter one