acceptodds
Under review as a conference paper at ICLR 2027

Characterizing and Improving Bijection Attacks through Prompt-Level Perturbation

Abstract

Among Large Language Model (LLM) jailbreaking methods, *bijection attacks*, that communicate using an invertible bijection language, have drawn interest due to their efficiency, black box applicability, and large attack space. These attacks are commonly characterized via a dispersion parameter, which specifies the number of characters in the alphabet that are encoded by the bijection. However, attacks with the same dispersion value can vary significantly across trials and prompts, making dispersion alone a coarse measure for characterizing attack success or identifying effective bijections in the large attack space. In this work, we characterize bijection attacks through *prompt-level perturbation*, a measure of the bijection's interaction with the prompt. We first show that the attack outcomes are structured along this measure, both within and across dispersion values. Next, we demonstrate that optimal prompt-level perturbation can vary across prompts, motivating adaptive strategies to localize successful attacks. Finally, we introduce Signed Langevin Search (SLS), a *gradient-free* stochastic search method inspired by Langevin dynamics for efficiently identifying successful bijection attacks in *both white and black-box settings*. SLS uses prompt-level perturbation to organize the search space and model feedback to guide exploration towards promising regions, demonstrating consistent improvements in query efficiency across multiple models and datasets. Together, these findings allow us to better understand vulnerabilities LLMs have to encoded prompts, providing a deeper understanding of LLM safety behavior.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
bijection attack, jailbreaking, LLM redteaming, safety, prompt transformations

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_v2fkOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper investigates the characterization and efficient discovery of bijection-based jailbreak attacks against large language models (LLMs). The authors argue that the conventional dispersion parameter is insufficient to characterize attack effectiveness because it does not account for how a particular character substitution interacts with the input prompt. To address this limitation, they introduce Prompt-Level Perturbation (PLP), which measures the proportion of prompt characters modified by a bijection.

The paper presents empirical evidence that attack outcomes exhibit structured patterns across different PLP levels and that favorable perturbation levels vary across prompts. Building on these observations, the authors propose Signed Langevin Search (SLS), a gradient-free stochastic search strategy that uses model feedback to navigate the perturbation space.

Experiments across multiple LLMs, including open-weight and proprietary models, and three jailbreak benchmarks demonstrate improvements in queries-to-first-attack compared with random bijection selection. The paper aims to provide both a more informative characterization of bijection attacks and a more query-efficient attack discovery method.

Critical strengths

S1. Prompt-Specific Characterization of Bijection Attacks. The introduction of Prompt-Level Perturbation provides a useful perspective for analyzing bijection attacks beyond the conventional dispersion parameter. By explicitly considering the interaction between a character mapping and its target prompt, the proposed measure captures variations that dispersion alone cannot distinguish. This characterization helps explain why bijections with identical dispersion values can produce different attack outcomes.

S2. Empirical Identification of Structured Attack Regimes. The paper provides interesting empirical observations suggesting that refusal, successful jailbreaks, and incoherent responses occupy different regions of the perturbation space. The analysis of prompt-dependent optimal perturbation levels further motivates adaptive attack strategies. These findings contribute to understanding the relationship between encoded input transformations and LLM safety behavior.

Critical weaknesses

W1. Limited Methodological Novelty of the Proposed PLP Measure. The proposed Prompt-Level Perturbation is essentially the fraction of input characters affected by the bijection, as defined in Equation (2). Although this measure is more informative than dispersion, it is closely related to a straightforward character-level modification ratio. The paper does not sufficiently establish why this relatively simple statistic constitutes a substantial methodological contribution. Furthermore, PLP ignores the semantic importance, positional distribution, and tokenization effects of substituted characters. Different bijections with identical PLP values may therefore induce substantially different model behaviors. More systematic comparisons with alternative perturbation measures are needed to establish the distinctive value of PLP.

W2. Insufficient Theoretical Justification for Signed Langevin Search. The proposed SLS algorithm is motivated by Langevin dynamics, but its actual update rule replaces the gradient of the log-success probability with a heuristic direction inferred from refusal and incoherence labels. The assumption that refusals consistently indicate the need for larger perturbations, while incoherent responses indicate the need for smaller perturbations, is not theoretically established. Moreover, the introduction of independently tuned noise, momentum, and annealing further separates the algorithm from conventional Langevin dynamics. Consequently, it remains unclear whether the observed improvements arise from the Langevin-inspired formulation or simply from directional heuristic search. This weakens the methodological justification for the central algorithmic contribution.

Questions for authors

Q1. Distinctive Value of PLP. How does PLP compare with other simple perturbation measures, such as character-level edit distance, tokenization change rate, or frequency-weighted substitution ratios? Can the authors provide quantitative evidence that PLP offers additional predictive value beyond these alternatives?

Q2. Validity of the SLS Search Direction. What empirical evidence supports the assumption that refusal and incoherence reliably indicate opposite directions toward higher attack success probability? How frequently does this assumption fail across different prompts and models, and how sensitive is SLS to such violations?

Q3. Contribution of the Langevin-Inspired Components. Can the authors compare SLS against simpler PLP-guided search strategies, including deterministic directional search and adaptive interval search, under identical candidate sets and query budgets? Such comparisons would help establish whether stochastic noise, momentum, and annealing contribute meaningfully to the reported improvements.

Q4. Reliability of Response Classification. How robust are the experimental results to errors in the GPT-4o-mini judge and the keyword-based refusal classifier? Have the authors evaluated classification agreement against human annotations or independent safety classifiers, particularly for ambiguous responses?

Q5. Interpretation of Query Efficiency. Since prompts without successful candidates are excluded from QTFA evaluation, how would the conclusions change when all prompts are included and unsuccessful attempts are treated as censored observations? Can the authors additionally report attack success rates under fixed query budgets?

Q6. Statistical Reliability of Prompt-Specific Optimal PLP. In Section 3.3, the optimal PLP for each prompt is estimated using 100 attacks. How stable are these estimated optima across independent sampling runs? Could the observed variation between prompt-specific and global optima partly result from finite-sample estimation noise?

6 comments

Thank you for your review and your questions. We answer them below.

Q1 PLP as a Value

We arrived at PLP after examining a large array of other metrics and concluded that PLP, despite its simplicity, is the metric that best captures the three outcome regimes of success, incoherence, and refusals. While we had not included this analysis in the original draft, we will incorporate it into the revision to further strengthen our argument that PLP is a conceptually simple, easy-to-compute, black-box metric that requires no knowledge of the model's internal architecture, weights, or tokenizer.

We measure the average AUC of threshold classifiers on each measure for the 3 classification tasks (refusal vs success, success vs incoherence, refusal vs incoherence). Here we observe that no semantic, positional, or frequency-weighted metric we tested outperforms PLP. Only token-level edit distance did, by ~0.003 AUC, but token-level metrics cannot be used in black-box settings. Please see Appendix F of our revision for full details.

MetricHarmBench AUCAdvBench AUC
PLP0.7020.774
Token-based (needs tokenizer)
Token change rate0.6970.759
Token edit distance0.7050.776
Fraction of digit tokens0.6960.763
Semantic
Harmful keywords hit0.6460.710
Content words damaged0.6960.760
Core-syntax words hit0.6540.703
Frequency-weighted
Letters weighted by English frequency0.7000.770
Word damage weighted by rarity0.7000.778
Positional
Word-initial letters hit0.5580.601
Longest intact run0.6600.742

Q2 Regimes Across Prompts

Following your suggestion, we systematically analyzed the three-regime ordering with respect to PLP (ρ\rho). Our ordering metric is defined as follows. We use threshold classifiers to separate refusal and success (τRS\tau_{RS}), and success and incoherence (τSI\tau_{SI}). A prompt is ordered if τRS<τSI\tau_{RS} < \tau_{SI}. On Harmbench (20 trials per prompt), for Llama 3 8B, we find that 83% of prompts are ordered. We have included this experiment in Appendix B.4.

Q3 Langevin Inspired Components

Our ablation over the Langevin components is in Appendix D. In Appendix D.1 we isolate and justify the role of stochasticity in the update. When σ=0\sigma=0 (deterministic directional search), SLS reduces to a sign based-update which impacts mean QTFA (increases from 5.78 to 6.34). This demonstrates the importance of the Langevin component. Appendix D.3 and D.4 demonstrate that adding momentum and noise annealing reduces both mean and median QTFA on Qwen3 4B and yields similar QTFA with and without momentum on Llama 3 8B and Gemma E4B. Finally, in Appendix C.6 we demonstrate that SLS outperforms a more simplistic median-outward search. We have updated our text to make the reference to these appendices more explicit.

Q4 Response Classification

In this work, we use the exact classifier from the original bijection work (Huang et al. 2025), GPT4-mini using the popular Harmbench prompt. To further validate our analysis, we re-judge our Harmbench and Advbench results using the two open-source HarmBench classifiers (Llama-2-13B and Mistral-7B; Mazeika et al., 2024) which have been validated against humans. Here, using the same scheme as Q2 (averaged across all models), ordering remains consistent across the different judges. Further, average AUC values (across the 3 different classification tasks) indicate similar separability among these measures. The updated experiment is in Appendix G.1.

Success judge% Ordered [95% CI]Avg. AUC [95% CI]
HarmBench
GPT-4o-mini71.2 [69.2, 73.4]0.630 [0.623, 0.638]
HarmBench classifier (Llama-2-13B)74.5 [72.2, 77.0]0.650 [0.641, 0.659]
HarmBench classifier (Mistral-7B)74.5 [72.2, 76.9]0.649 [0.640, 0.658]
AdvBench
GPT-4o-mini74.1 [68.8, 78.9]0.672 [0.654, 0.691]
HarmBench classifier (Llama-2-13B)82.2 [76.4, 87.4]0.692 [0.666, 0.717]
HarmBench classifier (Mistral-7B)75.0 [69.0, 81.0]0.693 [0.671, 0.714]

We validate the keyword-based refusal-incoherence judge in Appendix G.2/G.3. Here we demonstrate strong recall against existing list-based judges (see our response to Reviewer uNUM, Q2). Further, using an LLM to judge into 3 groups instead of our rule based method makes no significant difference in ordering or separability (Appendix G.3).

Q5 Query Efficiency

Including prompts that have no successes in the candidate set would not change any of the conclusions of this work. Since both SLS and random search draw from the same fixed pool of N = 20 candidate bijections per prompt, at budget 20, the prompt is attacked successfully by SLS if and only if it is attacked successfully by random search. The ASR is identical for both methods (Table 6). For, these prompts where no such successful attack exists, any search method will search the entire candidate space and fail to find a successful attack. Therefore, any penalty will apply to every search method and have no effect on relative ordering. The exact values can be computed as a direct result from Tables 1, 3, 4, and 6. We include ASR@K results in Appendix C.8.

Q6 Statistical Reliability

We have replaced Figure 4 with a version using HarmBench (320 prompts, 5 independent runs of 20 attacks each), which gives a larger sample size. To verify that the spread observed in Fig. 4a is not sampling noise, we run ANOVA and Kruskal-Wallace tests. Both tests yielded p<0.01p < 0.01, supporting rejection of the null hypothesis of a single universal ρG∗\rho^*_G and confirming the variability across prompts. These tests also achieve p<0.01p < 0.01 for Advbench.

Thanks for the response. I would like to keep my score.

Reviewer_2xfAOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper introduces prompt-level perturbation (PLP) to characterize bijection attacks and proposes Signed Langevin Search (SLS), which uses response feedback to guide candidate selection. Experiments across ten models and three datasets report improved query efficiency over random search in many settings.

Critical strengths

The analysis provides a useful & novel perspective on why bijections with the same dispersion produce different outcomes, highlighting the interaction between the encoding and the specific prompt. The evaluation spans diverse models and datasets, with paired confidence intervals and hyperparameter ablations supporting the assessment of query-efficiency gains.

Critical weaknesses
  1. SLS combines two components: initialising near the median of candidates sorted by ρ\rho, and using refusal/incoherence feedback to guide subsequent steps. However in the experiment, the contribution is not cleanly isolate. Random search changes both initialization and candidate selection, while median-out replaces feedback-guided updates with a different traversal rule. These comparisons therefore leave unclear how much of the improvement comes specifically from directional feedback. Could author provide more clear contribution attribution between initialisation with ρ\rho vs. feedback guide.

  2. Section 3.3 estimates each prompt’s best ρ\rho from 100 attacks and repeats the experiment five times. These estimates may differ simply because different attacks were sampled. The spread in Figure 4a therefore does not by itself establish that different prompts have different true optima.

Questions for authors

Same as weakness above

1 comment

Thank you for your review and the suggestions. We address them below.

W1 Components

In Appendix D, we show an ablation over different components of SLS across Llama 3 8B, Qwen3 4B and Gemma E4B. To isolate the effect of the initialization we add an ablation over the starting position. We implement SLS using a random starting position (starting point is selected uniformly randomly across all candidates). On the Harmbench dataset, SLS with random initialization achieves the similar QTFA as median-initialization. This confirms that the efficiency improvements of the proposed SLS algorithm predominantly come from the directional Langevin search. This ablation has been added in Appendix D.5 of our revision.

Llama 3 8BQwen3 4BGemma E4B
Random Bijection5.4 ±\pm 0.194.50$\pm$ 0.184.27 ±\pm 0.19
SLS4.44 ±\pm 0.184.03 ±\pm 0.174.03 ±\pm 0.20
Random Start SLS U(0,1)\mathcal{U}(0,1)4.62 ±\pm 0.183.94 ±\pm 0.164.03 ±\pm 0.19

W2 Figure 4a Significance

We have replaced Figure 4 with a version using HarmBench (320 prompts, 5 independent runs of 20 attacks each), which gives a larger sample size. To verify that the spread observed in Fig. 4a is not sampling noise, we run ANOVA and Kruskal-Wallace tests. Both tests yielded p<0.01p < 0.01, supporting rejection of the null hypothesis of a single universal ρG∗\rho^*_G and confirming the variability across prompts. These tests also achieve p<0.01p < 0.01 for Advbench.

Reviewer_uNUMOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

In this paper, the authors investigate why bijection attacks with the same dispersion can produce different outcomes across bijections and prompts. They introduce prompt-level perturbation (PLP) to characterize these outcomes and Signed Langevin Search (SLS) to improve query efficiency. Specifically, SLS (1) orders candidate bijections by PLP and (2) uses model feedback and stochastic exploration to guide the search. Across ten models and three datasets, SLS generally reduces Queries-to-First-Attack (QTFA) relative to random bijection selection; on AdvBench, mean QTFA decreases from 8.42 to 6.81 for Llama 3 8B, evaluated on prompts with at least one successful attack among 20 candidates.

Critical strengths

PLP addresses a clear limitation of dispersion. It measures how much of the actual prompt is modified. Successful attacks concentrate within particular PLP regions even at fixed dispersion (Figure 2), making the characterization useful beyond counting substituted alphabet characters.

SLS delivers measurable query savings. On Llama 3 8B / HarmBench, ten independent runs show an average relative reduction in mean QTFA of 12.3% versus random search (Table 5). Paired bootstrap 95% confidence intervals support gains in 23 of 30 settings (Tables 11–13).

Critical weaknesses

The conceptual advance over prior bijection attacks is limited. Huang et al. (2025, §4, Figure 5) already report high refusal at low dispersion, stronger attacks at intermediate dispersion, and incoherence at high dispersion. The contribution is therefore a finer PLP characterization and SLS built from established search components.

The evidence for different optimal PLP values is not conclusive. Section 3.3 compares estimated success probabilities at each prompt's optimum and the global optimum without reporting independent evaluation. Selecting maxima from noisy estimates can exaggerate this difference, weakening the evidence for RQ2.

Questions for authors

Optimal PLP: Does Figure 4's loss under the global optimum persist when the optimal PLP values are selected using one sample and evaluated using independent samples?

Response categories: Section 2.2 labels every unsuccessful response without four refusal keywords as incoherent, potentially including coherent safe responses. Can a human audit validate this distinction, particularly at high PLP?

Query budgets: Table 6 reports ASR at 20 queries, while QTFA excludes prompts without a successful candidate. Can you report ASR at smaller query budgets over all prompts, particularly for Gemini 2.5 Flash on StrongREJECT, where the full-budget ASR is 18.2%?

1 comment

Thank you for your review and your questions. We address them below.

W1 Conceptual Advance

Our conceptual contribution is shifting from a bijection-only perspective to a prompt–bijection interaction perspective for understanding bijection-based attacks. Dispersion measures how much of the alphabet the bijection covers, which is a property fully determined by the attack itself. On the other hand, PLP (ρ\rho) measures how many characters are modified by the bijection attack for each prompt.

Despite its simplicity, PLP captures this interaction between the bijection and the prompt, enabling a more precise understanding of bijection-based attacks. We further compare PLP against a broad range of more complex metrics and demonstrate that PLP is surprisingly effective despite its conceptual and computational simplicity (see our response to Reviewer v2fk, Q1).

We demonstrate that the three regimes (success, incoherence, refusal) can be better stratified by PLP values than by dispersion values. We further show that attack success is largely independent of dispersion when conditioned on PLP. This suggests that the correlation between dispersion and attack success arises because dispersion changes PLP, uncovering a more fundamental mechanism of bijection-based attacks.

Q1/W2 Optimal PLP

Per your suggestion, we have replaced Figure 4 with a new experiment with a held-out design on HarmBench (320 prompts, 5 independent runs of 20 attacks each), which gives a larger sample size. Here, 4 of the runs are used to estimate optimal ρ∗\rho*, while the 5th is used for evaluation. The conclusions remain consistent with our original findings. In Figure 4a, we continue to observe variability across optimal ρ∗\rho*. In Figure 4b, we demonstrate that the success probability on held out samples is higher for prompt-specific ρ∗\rho* compared to the global ρG∗\rho_G*.

Q2 Response Categories

Any prompt that is not a successful attack and not a refusal is, by our definition, “incoherent”. This includes responses that may be safe but unrelated to the attack prompt. We further validate our refusal-incoherent list by comparing to existing refusal lists [1-5]. Here we find that our list appropriately captured refusals for all models except for Gemma 7B. For Gemma 7B, there were refusals that were not captured initially by our keyword list, as the refusals utilize the term “not able.” Adding this term to the list, we see 91.87% mean recall across all models.

ModelRecall (%)
Llama 3 8B99.03
Qwen 2.5 7B93.98
Qwen 3 4B81.10
Gemma 7B80.72
Gemma E4B92.12
Ministral 8B92.17
Llama 3.3 70B94.04
GPT OSS 120B98.82
Gemini 2.5 Flash98.34
Haiku 4.5 (d=16d = 16)88.41
Mean91.87

Furthermore, this improves SLS attack efficiency for Gemma 7B and does not change the performance of other models. We provide average QTFA for SLS for the original and revised list below. The full updated experiment is in Appendix G.2 of our revision.

ModelHarmBench Original Avg QTFAHarmBench Revised Avg QTFAAdvBench Original Avg QTFAAdvBench Revised Avg QTFAStrongREJECT Original Avg QTFAStrongREJECT Revised Avg QTFA
Llama 3 8B4.454.446.746.755.685.68
Qwen 2.5 7B3.853.854.804.782.832.83
Qwen 3 4B4.034.034.834.815.785.77
Gemma 7B5.705.616.666.595.104.59
Gemma E4B4.034.025.004.962.732.73
Ministral 8B2.272.281.951.941.691.69
Llama 3.3 70B3.903.866.066.025.275.22
GPT OSS 120B4.234.234.734.733.843.83
Gemini 2.5 Flash3.533.536.566.457.427.49
Haiku 4.5 (d=16)6.576.585.005.035.195.20

[1] Zou et al., Universal and Transferable Adversarial Attacks on Aligned Language Models

[2] Chao et al., Jailbreaking Black Box Large Language Models in Twenty Queries

[3] Li et al., Exploiting the Index Gradients for Optimization-Based Jailbreaking on Large Language Models

[4] Yu et al., Mind the Inconspicuous: Revealing the Hidden Weakness in Aligned LLMs' Refusal Boundaries

[5] Shen et al., PandaGuard: Systematic Evaluation of LLM Safety in the Era of Jailbreaking Attacks

Q3 Query Budgets

We would like to get a little more clarity about this question. Table 6 reports ASR values of the original bijection attack (Huang et al. 2025) on the models we use in this work. Both SLS and random search use the same pool of 20 candidate bijections per prompt, so they achieve the same ASR at the full budget. We include ASR@K results in Appendix C.8.

Comments on the paper

1 comment

Dear reviewers, as the deadline is approaching, please check the rebuttal and consider participating in the discussion.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.