Adversarial Optimization in Discrete Token Spaces

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 2426 papers474 conceptsfrozen 2026-10-04

In computer vision, finding an adversarial example is a matter of calculus. If you want to trick a model into seeing a cat as a toaster, you can use gradient descent to slightly nudge every pixel in the "toaster" direction. Because pixels exist in a continuous space, these tiny adjustments are mathematically straightforward.

Language models and text-to-image diffusion models present a much harder problem. Text is composed of discrete tokens—individual words or sub-words from a fixed dictionary. You cannot nudge the word "cat" 1% toward the word "toaster." You must either keep "cat" or replace it entirely with another discrete entry from the vocabulary. This creates a massive, non-differentiable combinatorial search space that Natalie Maus and Patrick Chao note is fundamentally difficult to navigate using standard optimization tools.

Researchers are currently developing new ways to bridge this gap, turning the "black art" of manual prompting into a systematic engineering discipline.

The Discrete Bottleneck

The core challenge in discrete optimization is the lack of useful gradients. In a continuous space, the gradient tells you exactly which direction to move to improve your objective. In a discrete space, small changes—like swapping one word for a synonym—can lead to unpredictable, non-linear shifts in model behavior.

As Yasaman Jafari and colleagues observe in their work on MORL-Prompt, this often leads to "objective collapse," where optimizing for one goal (like style) causes the model to fail at another (like accuracy). Because the search space is effectively infinite, simple greedy searches often get stuck in local optima, producing "gibberish" prompts that might satisfy a mathematical objective but lack human meaning.

Bridging the Gap with Continuous Proxies

To solve this, many researchers attempt to map the discrete problem back into a continuous one. One prominent approach is the use of differentiable relaxations.

Chuan Guo introduced GBDA (Gradient-based Distributional Attack), which uses the "Gumbel-softmax" trick. Instead of picking one word, the optimizer maintains a probability distribution over the entire vocabulary. This allows gradients to flow through the selection process, enabling the discovery of adversarial examples that are both effective and surprisingly natural.

Similarly, the ASETF framework developed by Hao Wang and others optimizes attacks in the continuous embedding space first. Once an optimal "direction" is found in the vector space, the system "translates" those embeddings back into fluent natural language. This bypasses the combinatorial explosion of trying every possible word combination directly.

Search Strategies for Black-Box Models

When researchers don't have access to a model's internal weights (a "black-box" scenario), they cannot use gradients at all. In these cases, the research shifts toward efficient search heuristics.

  • Bayesian Optimization: Deokjae Lee and the team behind Bayesian Red Teaming (BRT) use past evaluations to build a probabilistic model of the search space. This allows them to identify diverse failure modes with far fewer queries than random searching.
  • Coordinate Queries: Ema Borevkovic and Nicholas Carlini developed Greedy Coordinate Query (GCQ), which iteratively tests token substitutions at specific positions. This method has achieved nearly 100% success rates in forcing models like GPT-3.5 to emit targeted harmful strings.
  • Reinforcement Learning: Methods like QROA, proposed by Hussein Jawad, treat the discovery of adversarial suffixes as a reinforcement learning problem, rewarding the "attacker" for sequences that trigger safety violations.

Prompt Inversion and the Proxy Gap

This research isn't just about attacks; it's also about understanding what models have learned. Prompt Inversion is the task of taking an image and finding the exact string of dictionary words that would recreate it.

In PH2P, Shweta Mahajan and Leonid Sigal show that by focusing optimization on the "semantic-heavy" timesteps of the diffusion process, they can recover human-readable prompts more accurately than previous methods.

However, a recurring theme in this field is the "proxy gap." As Avi Schwarzschild points out, an optimizer might be very good at maximizing a mathematical similarity score (like CLIP) while producing a prompt that looks like nonsense to a human. This suggests that while we are getting better at navigating the discrete space, our mathematical objectives do not yet perfectly capture the nuances of human language.

Why It Matters

Understanding discrete optimization is central to AI safety. As Anas Awadalla and Nicholas Carlini argue, the current perceived robustness of text models may be an illusion caused by the difficulty of optimization, rather than true security. As these discrete search techniques become more efficient—reducing computational costs by orders of magnitude as shown by Tim Beyer—the "security through obscurity" provided by the discrete nature of language will likely vanish.

Papers in this version

Showing 60 of 426 papers.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 275 papers
  2. Version 1 · 2026-10-04 · 426 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_discrete_input_space_constraints_836e0e4e,
  title = {discrete input space constraints},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/discrete-input-space-constraints/rdr_836e0e4e7ce94126a9b06def0473fbc3},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_adversarial_optimization_in_discrete_tok_836e0e4e_v1,
  title = {Adversarial Optimization in Discrete Token Spaces},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/adversarial-optimization-in-discrete-token-spaces/rdr_836e0e4e7ce94126a9b06def0473fbc3/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}