Greedy Coordinate Search: Why Token-Level Search Beats Naive Gradient Descent

The objective a jailbreak minimizes is a smooth function of the model's continuous embeddings but a rugged function of the discrete tokens an attacker actually controls. That mismatch is the whole difficulty of text attacks: the gradient points in a helpful direction, yet you cannot move a sentence a little bit along it. The influential answer, formalized by Zou and colleagues, is to stop trying to descend and instead search — but to search cleverly, letting the gradient nominate a short list of promising token swaps at each position and then paying for a real forward pass only on those. This article explains that idea at the level a defender needs: enough to see why it works, why it is efficient, and why the tokens it produces carry a detectable signature.

Why naive gradient descent fails on text

Gradient descent assumes you can take a small step in the input and re-evaluate. For an image that is literal — nudge the pixels along the negative gradient. For text it is incoherent. Tokens are discrete indices into a vocabulary, so there is no small step; the selection of a token from a distribution over the vocabulary is a non-differentiable argmax; and even if you follow the embedding gradient to a new point in continuous space, the nearest real token to that point often does not lower the loss, because the embedding manifold is sparse and the loss is non-linear between tokens.

These three obstacles — discreteness, the non-differentiable selection, and the nearest-token gap — are why an attacker cannot simply run an optimizer on a prompt. Each is a place the continuous intuition breaks. The gradient is still informative; it just cannot be followed directly. The design problem is to extract the gradient's information without pretending the space is continuous.

For a defender, understanding this failure mode is useful because it predicts what a successful attack must look like: a discrete search that repeatedly queries the model, and a result that lives at unusual points in token space rather than in fluent language. Both properties are handles for detection.

The gradient as a candidate proposer

The key idea is to demote the gradient from a step-direction to a proposer. Represent each controllable position as a one-hot selection over the vocabulary, and take the gradient of the loss with respect to that one-hot vector. Its components give a first-order, linear estimate of how much swapping in each alternative token at that position would change the loss — cheaply, for every candidate at once, without a forward pass. This linearized substitution estimate is the same trick that earlier token-flip attacks used, adapted to the language-model objective.

Crucially, this estimate is only a proposal. The linear approximation is unreliable across the large change of swapping one token for another, so the gradient's ranking is treated as a shortlist, not a decision. At each position the attacker keeps the top few candidates by estimated improvement, forming a small set of plausible swaps out of a vocabulary that may number tens of thousands. The expensive, accurate step is deferred to only these few.

Defensively, note that this proposer requires gradients, hence white-box access to the model or a transferable surrogate. A purely black-box attacker cannot compute it and must fall back on far more queries, which is why gradient access is the pivotal capability and why open-weight surrogates are the practical enabler.

Greedy coordinate search, step by step

With a shortlist per position, the search becomes a loop. Sample a batch of candidate substitutions from the shortlists, and for each candidate perform a true forward pass to measure the actual loss — not the linear estimate. Keep the single substitution that most reduces the real loss, apply it, and repeat from the new point. The gradient proposes; the forward pass disposes. Over many iterations the loss descends in a staircase of verified single-token swaps.

This is a coordinate-style search: at each iteration it changes one coordinate (one token position) greedily, guided by the gradient's proposal and confirmed by evaluation. It is neither pure gradient descent (which cannot be applied) nor blind combinatorial search (which is intractable) but a hybrid that uses the cheap gradient to make the expensive search tractable. The number of forward passes per iteration is the batch size, and the number of iterations is bounded by a budget.

The loop is the attacker's whole procedure, and it is also the defender's clearest behavioral signal: a sustained sequence of near-identical requests differing by one token region, each eliciting a slightly more compliant response, is exactly what an active search looks like from the server side.

Why guidance beats blind search

The efficiency case is stark. A blind search that tried random token substitutions would waste almost all of its forward passes on candidates that do not help, because the fraction of the vocabulary that lowers the loss at any position is tiny. The gradient proposer concentrates the expensive forward passes on the small shortlist most likely to help, so the same budget of forward passes buys far more real improvement. This is the entire reason the guided search succeeds where naive approaches — both continuous descent and random search — fail.

Two levers set the cost: the shortlist size per position, which trades proposal breadth against verification cost, and the batch size per iteration, which sets how many true forward passes are spent before committing a swap. The attacker tunes these to fit a query budget. The defender's counter-lever is to make forward passes scarce or observable — throttling, batching limits, and anomaly detection — so the guided search cannot amass the evaluations it needs.

Framed as economics, the guided search moved the attack from infeasible to feasible by cutting the number of costly evaluations by orders of magnitude. Defenses work by pushing it back toward infeasible along the same axis: raising the number and visibility of the queries required.

The detectable footprint

Because the search optimizes the loss rather than readability, the token strings it selects are statistically unnatural — they sit at points a fluent language model finds highly improbable. This is not incidental; it is a direct consequence of minimizing a compliance objective with no fluency constraint. The result is a measurable footprint: high perplexity under a reference model, unusual token co-occurrences, and often non-linguistic character sequences.

This footprint is the most reliable defensive handle against optimized suffixes. A perplexity filter that rejects inputs the reference model finds improbable will catch a large fraction of these strings before they reach the target, and canonicalization can strip the unusual token regions they rely on. The caveat, important to state honestly, is that an attacker can add a fluency term to the objective and trade some attack strength for naturalness, which shrinks the footprint — so perplexity filtering is a strong, necessary layer, not a complete solution.

The defensive posture that follows is layered: filter on the footprint to stop the cheap, unnatural attacks, and rely on behavior-level monitoring and query throttling for the more expensive, fluency-constrained ones. Each layer targets a different point on the attacker's cost curve.

Threat model and the defenses it implies

The efficient form of the search needs gradients, so the primary threat is a white-box or surrogate-transfer attacker; a strictly black-box attacker faces a far higher query cost. In NIST taxonomy terms, the decisive dimension is the adversary's knowledge, and the practical reality is that open-weight models give everyone white-box gradients and that suffixes optimized on them frequently transfer to closed targets. Model secrecy therefore cannot be the control.

The defenses map cleanly onto the search's structure. The proposal step needs gradients — deny them where possible and assume transfer where not. The verification step needs many forward passes — make those scarce and observable through rate limits and anomaly detection. The output lives at unnatural token points — filter on perplexity and canonicalize. And the whole loop is a distinctive behavioral pattern — monitor for monotonic, single-region-varying query sequences. No single control stops the search; together they raise its cost at every stage.

This structure-to-defense mapping is the practical payoff of understanding the algorithm. Each stage the attacker relies on is a place to add cost, and the defender's job is to make the total cost exceed the attacker's budget.

Limits and honest framing

The search is powerful but not omnipotent, and the defenses are real but not walls. The greatest limitation for the attacker is the query and gradient cost, which the defenses attack directly; the greatest limitation for the defender is that a fluency-constrained variant can shrink the perplexity footprint, and that transfer lets an attacker pay the white-box cost once, offline, and reuse the result against a filtered black-box target. Neither side has a decisive move.

There are modeling caveats too. The affirmative-prefix objective the search minimizes is a proxy for harmful behavior, so a low loss does not guarantee a fully harmful completion, and defenses tuned to that proxy may miss other targets. And the behavioral signal — sustained single-region-varying queries — is clearest for online search against the deployed model; an attacker who searches entirely on a local surrogate emits no such signal and arrives with a finished suffix.

Held honestly, the algorithmic understanding still pays off. It tells the defender precisely which behaviors to watch, why perplexity filtering works and where it stops, and why model secrecy is not a defense. That precision — knowing the mechanism rather than chasing symptoms — is the contribution of taking the search seriously.

Practitioner Toolkit

Copy-paste, strictly defensive artifacts you can use today. Nothing here attacks a real system.

# DEFENSIVE / MOCK ONLY — detects search behavior, ships no attack
function detect_search(session):
    variants = near_duplicate_cluster(session.requests)   # single-region edits
    ppl_flags = [reference_perplexity(r) > PPL_T for r in session.requests]
    descending = is_monotonic(session.compliance_probs)   # loss going down
    if len(variants) > VARIANT_T and descending:
        return BLOCK(reason='active search pattern')
    if fraction(ppl_flags) > PPL_FRAC:
        return REVIEW(reason='high-perplexity inputs')
    return ALLOW

Glossary

Greedy coordinate search

A discrete optimization that changes one token position per step, guided by the gradient and confirmed by a forward pass.

Candidate proposer

Use of the embedding gradient to rank alternative tokens per position as a cheap shortlist, not a final choice.

Linearized substitution estimate

A first-order approximation of the loss change from swapping one token for another at a position.

Forward-pass verification

Computing the true loss of a candidate substitution rather than trusting the linear estimate.

Perplexity filter

A defense rejecting inputs a reference model finds improbable, catching optimized token strings.

Transfer

Reuse of a suffix optimized on an open surrogate against a different, often black-box, target.

Query budget

The number of model evaluations an attacker can afford, the resource the search consumes and defenses restrict.

References

1. Zou et al., Universal and Transferable Adversarial Attacks on Aligned Language Models (arXiv 2307.15043)
2. Goodfellow, Shlens & Szegedy, Explaining and Harnessing Adversarial Examples / FGSM (arXiv 1412.6572)
3. Szegedy et al., Intriguing properties of neural networks (arXiv 1312.6199)
4. NIST AI 100-2 e2023 — Adversarial Machine Learning: A Taxonomy and Terminology
5. OWASP Top 10 for LLM Applications: LLM01 Prompt Injection