SMTrap: Cost-Effective DoS Attacks Against Large Reasoning Models via SMT Conflict Guidance

Jian Yang, Zhenqi Feng, Zhaoyang Yu, Zhaoxin Fan, Kejian Wu, Xiaofeng Wang, Zheng Zhu, Jianjun Huang, Wei You, Bin LiangarXiv 2026 · arXiv

TL;DR

SMTrap introduces a highly cost-effective, model-feedback-free Denial-of-Service (DoS) attack paradigm against Large Reasoning Models (LRMs). By using cheap, CPU-side symbolic solver conflict counts as a proxy for combinatorial difficulty, it synthesizes benign-looking logic puzzles that force LRMs into extensive trial-and-backtracking loops. This "search amplification" exhausts the model's token budget and computational resources at near-zero cost to the attacker.

What Problem Does This Paper Address?

Modern Large Reasoning Models (LRMs)—such as DeepSeek-R1 or OpenAI's o1/o3 series—rely on generating long Chain-of-Thought (CoT) trajectories to solve complex problems. This introduces a severe computational asymmetry: a very short user query can trigger thousands of tokens of internal reasoning on the provider's side. Attackers can exploit this to launch LRM-Denial-of-Service (LRM-DoS) attacks to exhaust provider resources.

However, existing black-box DoS attacks are highly inefficient. They either require iteratively querying the target model to optimize prompt perturbations or training an expensive surrogate model via reinforcement learning. This heavy reliance on model feedback means attackers must spend significant GPU compute time just to craft an attack payload, severely weakening their adversarial leverage. SMTrap addresses this gap by generating highly disruptive queries completely offline, without any model queries or GPU training.

Methods

The core innovation of this paper is search amplification. The authors discovered a fascinating parallel between symbolic Satisfiability Modulo Theories (SMT) solvers and neural LRMs: when forced to solve Constraint Satisfaction Problems (CSPs) like Sudoku or Zebra puzzles, both systems rely on a similar trial-and-backtracking process. They propose assignments, check constraints, hit contradictions, and revise failed branches.

Figure 1: Comparison of LRM-DoS paradigms. Prior meth- ods rely on model-derived feedback to (a) optimize input per- turbations or (b) train attack generators, whereas (c) search amplification uses conflict feedback from a CPU-side SMT solver to guide generating inference-heavy CSP queries.

SMTrap leverages this insight through a lightweight, CPU-only framework:

  1. CSP Initialization: It starts with a valid, fully solved CSP instance and randomly hides clues to create an initial puzzle state.
  2. Clue State Branching and Pruning: It iteratively modifies the puzzle by adding and removing clues, exploring neighboring puzzle configurations while strictly maintaining unique solvability.
  3. Conflict-Guided Acceptance: Each candidate puzzle is encoded as an SMT formula and run through the Z3 solver on a CPU. SMTrap tracks the solver's internal conflict count and greedily selects the puzzles that cause the most solver conflicts.
  4. Shortcut Suppression: To prevent web-facing LRMs from simply executing Python code to solve the puzzle, SMTrap appends strict system prompts instructing the model to reason purely manually, step-by-step.

Datasets

The authors evaluated SMTrap by synthesizing hard instances of two classic CSP families:

  • Sudoku: Standard 9×9 grids.
  • Zebra Puzzles: Logic grid puzzles scaled to 9 houses and 9 attribute categories.
  • Graph Coloring: Used as a secondary task to demonstrate generalization.

These generated puzzles were tested against seven frontier LRMs (including Claude-Opus-4.7, GPT-5.5, Gemini-3.1-pro, and DeepSeek-v4-pro) via APIs and official web interfaces. SMTrap was compared against state-of-the-art DoS baselines (AutoDoS, CatAttack, and ReasoningBomb) as well as static human-designed stress tests (Sudoku-Bench and Pencil Puzzle Bench).

Key Insights and Ideas

  • Symbolic-Neural Behavioral Alignment: Despite completely different underlying architectures, SMT solvers and LRMs scale similarly in response to combinatorial pressure. A high conflict count in Z3 reliably predicts extensive natural-language backtracking in an LRM.
  • Task-Side vs. Prompt-Side Optimization: Instead of trying to optimize surface-level prompt wording or adversarial triggers, it is far more effective to optimize the intrinsic mathematical difficulty of the task itself.
  • Asymmetric Leverage: SMTrap shifts the computational burden entirely. The attacker uses negligible CPU cycles (seconds) to generate a puzzle that forces the victim's massive GPU clusters to grind for minutes.

Key Results

  • State-of-the-Art Token Exhaustion: In API evaluations, SMTrap-Zebra achieved an average of 76,362 completion tokens across seven frontier models, outperforming the strongest baseline (AutoDoS) by 2.74×.
  • Extreme Web Delays: On official web interfaces, SMTrap forced models into massive over-reasoning loops. SMTrap-Sudoku caused GPT-5.5 to reason for 314.97 seconds (an 8.67× amplification over baselines), while SMTrap-Zebra forced GPT-5.4 to grind for over 21 minutes (1,308.33 seconds).
Figure 4: Validation of SMT conflict guidance for search amplification. (a,b) Normalized completion length across conflict levels for Sudoku and zebra puzzles. (c) Higher conflict levels are associated with more explicit search behaviors in Deepseek- v4-pro. (d) Explicit search behavior count is strongly correlated with completion length, where r denote Pearson correlations.
  • Negligible Synthesis Cost: SMTrap generated these high-impact payloads on a standard desktop CPU (Intel Core Ultra 9) in just 35 to 46 seconds on average.
  • High Stealthiness: SMTrap achieved an 83.33% stealthiness rate against a GPT-4o-based malicious prompt detector, as the queries look like entirely benign, standard logic puzzles.
  • Effective Mitigation: The authors demonstrated that routing recognized CSP queries to a local symbolic solver via tool-calling (and returning the direct output) successfully neutralized the attack, reducing LRM token consumption by 90.15% on average.

Limitations and Future Work

While highly effective, the authors note that SMTrap is currently focused on structured, CSP-style reasoning tasks that easily map to SMT formulas. It does not cover all possible forms of LRM resource-amplification vulnerabilities. Furthermore, Z3 conflict counts are highly dependent on the specific SMT encoding and solver heuristics used, meaning it isn't a universal metric of combinatorial hardness.

Future work includes exploring how this symbolic search pressure applies to broader, less structured reasoning domains, and investigating how changing solver heuristics impacts LRM behavior.

Summary updated

Abstract

Existing LRM-DoS methods rely heavily on model feedback to synthesize attack queries, requiring either repeated queries to the target model or training a dedicated attack model. These expensive operations severely weaken attack leverage. In this paper, we propose \emph{search amplification}, a novel, model-feedback-free LRM-DoS paradigm. It employs the conflict count derived from an Satisfiability Modulo Theories (SMT) solver as a low-cost external signal to guide the synthesis of inference-heavy Constraint Satisfaction Problem (CSP) instances. Our key observation is that LRMs depend on trial-and-backtracking search when solving CSPs, where higher SMT conflict counts on a given CSP instance positively correlate with more extensive LRM backtracking search and substantially longer output trajectories. Building on this finding, we propose \textsc{SMTrap}, a lightweight, CPU-only framework. Guided by SMT conflict counts, \textsc{SMTrap} generates inference-heavy CSP queries without model queries, attack-model training, or GPU computation. Evaluations across seven frontier models demonstrate the state-of-the-art LRM-DoS capability of \textsc{SMTrap}, producing DoS effects multiple times stronger than existing baselines. To mitigate the threat of \textsc{SMTrap}, we demonstrate a tool-based mitigation that significantly cuts token usage.
BibTeX
@misc{yang2026smtrap,
  author = {Jian Yang and Zhenqi Feng and Zhaoyang Yu and Zhaoxin Fan and Kejian Wu and Xiaofeng Wang and Zheng Zhu and Jianjun Huang and Wei You and Bin Liang},
  title = {{SMTrap: Cost-Effective DoS Attacks Against Large Reasoning Models via SMT Conflict Guidance}},
  year = {2026},
  eprint = {2608.18921},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2608.18921},
}
Figure