Adaptive Multilevel Twisted Sequential Monte Carlo for Rare Events Estimation in Language Models

Motivation

• At deployment scale, a failure probability of 10^-6 per query yields an expected one harmful output per day across 10^6 daily queries.Such failures are especially concerning in medical, legal, and disaster-management applications.Source: §1 · p. 1
• Direct sampling can require nearly 10^6 samples to estimate a probability on the order of 10^-5, with most samples contributing little information about the rare event.This motivates concentrating computation on low-probability but safety-critical regions of the output distribution.Source: §1 · p. 1

Method

• Unlike standard Twisted SMC, which may obtain almost no final-event positives, the multilevel procedure sustains positive samples across levels and reaches a final positive-sample rate close to 0.3.Figure 1 illustrates progressively increasing thresholds and proposal concentration on increasingly undesirable outputs.Source: Figure 1 · p. 2, §1 · p. 2
• Adaptive Multilevel Twisted SMC learns rare-event twists through nested intermediate events with increasingly stringent thresholds, progressively guiding generation toward the final target event.The first event is common enough for contrastive twist learning, and each learned twist increases access to the next rarer event.Source: §1 · p. 2

Contributions

• The paper establishes theoretical validity and improved positive-sample efficiency, then demonstrates rare-event estimation effectiveness across safety tasks and both small-scale models and modern large-scale LLMs.The discovered unsafe behaviors can also provide training or diagnostic examples for alignment methods.Source: §1 · p. 2

Rare-Event Estimation in Language Models

• Rare-event estimation targets p⋆ = P_p0(A⋆) and representative samples from σ⋆, but direct sampling is highly sample-inefficient and exact prefix marginals are intractable.The event is A⋆ = {x: R(x) ≥ γ⋆}, with potential ϕ⋆(x) = 1{R(x) ≥ γ⋆}; determining whether a partial sequence eventually reaches it requires marginalizing over continuations.Source: §2 · pp. 2–3

Twisted Sequential Monte Carlo

• Twisted SMC learns prefix twists that estimate eventual rare-event probabilities, focusing generation on promising regions and improving both representative sampling and rare-event probability estimation.The ideal twist is ψ⋆_t(x_1:t) = P_p0(R(X_1:T) ≥ γ⋆ | X_1:t = x_1:t).Source: §2 · p. 3

Contrastive Twist Learning

• Contrastive Twist Learning fits parameterized twists by minimizing KL divergence between twist-induced prefix distributions and target prefix marginals using positive and negative phases.Negative-phase prefixes are sampled relatively easily from the current twist-induced distribution, whereas positive-phase prefixes require rare-event samples.Source: §2 · p. 3
• Standard CTL can receive few or no informative positive samples, creating a bottleneck in which learning an accurate twist requires the rare-event samples that the twist is meant to produce.This feedback loop can yield poor estimates of future rare-event probabilities, inefficient sampling, and unreliable probability estimates.Source: §2 · p. 3

3.1 Multilevel Contrastive Twist Learning

• The method learns separate twists for nested intermediate events, beginning with a common event and progressively transferring informative positive samples toward the final rare event.Each learned twist guides sampling toward the next event, avoiding direct initial sampling from the final rare event.Source: §3.1 · p. 3

3.2 Gradient Estimation

• Importance-weighted samples from the previous-level twisted proposal preserve the correct positive-phase gradient, with estimation reliability governed by effective sample size.The proposal increases the probability of positive samples, while importance weighting corrects the distribution mismatch; training ESS remains consistently large and stable across levels.Source: §3.2 · p. 4

3.3 Adaptive Threshold Selection

• Adaptive thresholds choose each next event so approximately a fraction ρ of the current level’s target mass exceeds the threshold, balancing transition difficulty against the number of levels.Smaller ρ creates fewer, harder transitions, whereas larger ρ creates easier transitions requiring more levels; moderate values around 0.3 and 0.5 offer a favorable trade-off.Source: §3.3 · pp. 4–5

3.4 Adaptive Multilevel Twisted Learning

• The complete procedure iterates sampling, adaptive threshold selection, importance-weighted positive gradients, negative gradients, and twist updates until reaching γ⋆ or the maximum level count.The final learned twist and proposal support rare-event sampling and probability estimation.Source: §3.4 · p. 5
• Under ideal level-wise proposals, multilevel twist learning reduces training sample complexity from inverse dependence on rare-event probability p⋆ to polylogarithmic dependence on 1/p⋆, with improvement also shown for imperfect proposals.This contrasts with standard twist SMC and formalizes the central benefit of progressive learning.Source: §3.4 · p. 5

Sensitivity to Imperfect Rare-event Score R

• With an imperfect learned score, better proposals reduce proposal-dependent sampling error but cannot remove the bias caused by score misspecification when estimating the ground-truth probability p⋆.The error decomposition separates irreducible score-induced bias from proposal-dependent sampling error, and proposal samples can support asymptotically valid confidence intervals.Source: Sensitivity to Imperfect Rare-event… · pp. 5–6

4 Experiments

• Experiments span toxic-story generation and StrongREJECT jailbreak attacks across language models of varying scales, evaluating accuracy, rare-event hit rate, ESS, score misspecification, and hyperparameter sensitivity.The study compares standard Twisted SMC with SD-TSMC for toxic stories and LMTailRisk for jailbreak attacks, reporting results over five random seeds.Source: §4 · p. 6
• At γ⋆=7.0, standard Twisted SMC produces zero hit rate and zero ESS, whereas Adaptive Multilevel Twisted SMC maintains high hit rates and nonzero ESS for extremely rare toxic-story events.The method also yields more consistent probability estimates across random seeds than SMC and SD-TSMC.Source: Table 1 · p. 6
• Across reported StrongREJECT harmful categories, Adaptive Multilevel Twisted SMC consistently outperforms Twisted SMC and LMTailRisk, with relative error around 20% or lower.Its advantage is consistent across categories, while neither baseline consistently dominates the other.Source: Table 2 · p. 6
• With an imperfect proxy score, Adaptive Multilevel Twisted SMC remains relatively accurate across thresholds, while standard Twisted SMC returns zero estimates for the rarer settings.Its confidence intervals contain the ground-truth probability in most considered settings, unlike standard Twisted SMC beyond γ⋆=3.0.Source: Table 3 · p. 7, §4 · p. 7
• Increasing samples per level generally improves rare-event estimation, creating a trade-off between proposal quality and additional runtime and memory.The main experiments use 1,024 samples per level for γ⋆=7, with reference probability pMC = 3.81×10−6.Source: Table 4 · p. 7, §4 · p. 7

A Conclusion

• Adaptive Multilevel Twisted SMC addresses standard Twisted SMC’s positive-sample bottleneck by progressively learning twist functions over adaptively selected intermediate events.The resulting proposals support more accurate estimation, higher-quality rare-event sampling, and greater robustness to score misspecification for safety evaluation.Source: A Conclusion · p. 10

B Limitations

• The approach is limited by training a separate proposal model for each prompt and by not addressing alternative input-space formulations, motivating transfer across related prompts and extensions to prompt search.Semantically similar prompts may support proposal sharing or adaptation, while (Wu and Hilton 2025) studies searching for inputs that induce a fixed rare output.Source: B Limitations · p. 10

C.1 Rare-event Estimation in LLMs

• Related LLM rare-event methods search over inputs or use internal model quantities, whereas fixed-input output-space methods use unsafe proposals or twisted SMC; this work instead addresses scarce positives through progressively rarer events.Input-space importance sampling can be computationally intensive, while self-distilled Twisted SMC changes the base model; the proposed method keeps the base model fixed.Source: §C.1 · p. 10
• The multilevel construction differs from prior multilevel splitting, which allocates particles within one decoding run; here, intermediate events supply informative positives for learning a more accurate final twist.This distinction separates the paper’s twist-learning objective from search-allocation mechanisms in prior Twisted SMC work.Source: §C.1 · p. 11

C.2 Twisted Sequential Monte Carlo

• Twisted SMC and related particle-guidance methods have been applied to mathematical reasoning, hard-constraint generation, diffusion steering, and KL-constrained iterative twisting, demonstrating broader proposal-adaptation utility.These methods use expected-future potentials, weighted rejection sampling, resampling, or constrained path-space updates.Source: §C.2 · p. 11

D.1 Deviation of Level-wise CTL Gradient

• The proof of the level-wise CTL gradient deviation derives the gradient expression by differentiating the objective while treating σ_ℓ,t and p0 as independent of θ, then summing over timesteps.The supplied derivation proceeds through the log-normalizing-constant gradient identity.Source: §D.1 · pp. 11–12

D.2 Validity of the Importance-weighted CTL Positive Phase

• The validity result requires proposal support wherever σ_ℓ+1 assigns positive probability, with strictly positive twists on the base-model support; finite second moments and bounded twist-score gradients control the estimator.Without the support condition, some target responses can never appear in proposal samples, while poor proposals can still cause severe weight concentration.Source: §D.2 · pp. 12–13
• Importance-corrected positive-phase gradients converge almost surely to the exact next-level CTL gradients as the number of proposal samples N increases, under Assumptions 1–3.The analysis conditions on the previously learned proposal q_ℓ and establishes consistency for Algorithm 1.Source: §D.2 · pp. 12–14
• A closer match between q_ℓ and the next-level target σ_ℓ+1 reduces importance-weight degeneracy and improves positive-phase gradient accuracy, making ESS a direct accuracy diagnostic.The population effective sample size is defined through the χ2 discrepancy between σ_ℓ+1 and q_ℓ.Source: §D.2 · p. 16

Interpretation of Adaptive Threshold Selection

• Using the same retained fraction ρ at every level keeps the statistical discrepancy between consecutive target distributions constant across levels.Smaller ρ yields fewer, more widely separated levels, while larger ρ yields easier transitions but requires more levels; adaptive quantiles approximately equalize transition difficulty and justify warm-starting successive twists.Source: §D.3 · pp. 17–18
• The empirical threshold converges almost surely to the population (1 −ρ)-quantile for each nonterminal transition under Assumptions 1–4.The result applies when the population quantile is uniquely identifiable, including discrete score distributions provided 1 −ρ does not lie at a jump endpoint.Source: §D.3 · pp. 19, 21
• Under the additional no-tie condition, the retained empirical fraction converges almost surely to ρ, so Proposition 7’s divergence identities hold asymptotically.This closes the gap between the ideal population construction and finite-sample threshold selection in Algorithm 1 as the sample size increases.Source: §D.3 · pp. 21–22

Positive-sample complexity

• Ideal multilevel sampling changes the positive-sample dependence from inverse in p⋆ to polylogarithmic in 1/p⋆.For fixed δ, the analysis explicitly states this improvement over standard Twisted SMC.Source: §D.4 · pp. 22–23
• With high probability, ideal multilevel sampling preserves a constant-order fraction of positive responses at every level, maintaining an informative training signal throughout progressive twist learning.The guarantee applies when consecutive levels satisfy Pp0(Aℓ+1 | Aℓ) = ρ.Source: §D.4 · pp. 24–25
• The multilevel improvement remains polylogarithmic in 1/p⋆ for imperfect learned proposals when their total-variation error is uniformly ε < ρ.Proposal error degrades the guarantee smoothly through the gap ρ − ε rather than eliminating the advantage abruptly.Source: §D.4 · pp. 25–26

D.5 Sensitivity to Imperfect Score Function

• p̂_R(γ⋆+η_sc)−ε_sc ≤ p⋆ ≤ p̂_R(γ⋆−η_sc)+ε_sc bounds the ground-truth probability using practical-score tails.The interval depends only on practical-score tail probabilities, and its width reflects mass near γ⋆ plus the probability that score error exceeds η_sc.Source: §D.5 · pp. 28–29
• The practical-score interval endpoints can be consistently estimated from the same weighted evaluation samples by re-thresholding at γ⋆+η_sc and γ⋆−η_sc.Finite-sample corrections yield an asymptotically valid clipped interval with coverage at least 1−α_L−α_U.Source: §D.5 · pp. 29, 30, 32
• The estimator’s mean-squared error separates irreducible reward-misspecification bias from proposal-dependent sampling error, so improving q cannot remove score bias but can reduce estimation error.The estimator is unbiased for the practical probability but generally biased for the ground-truth probability.Source: §D.5 · pp. 33–34

E.1 Approximate Negative Samping in Algorithm 1

• When direct sampling from the current twist-induced distribution is unavailable, the negative phase approximates its required constant with simple importance sampling (SIS).Algorithm 2 generates samples from the twist-induced proposal and computes normalized importance weights for the negative phase.Source: §E.1 · p. 34, §D.5 · p. 34

E.2 Evaluation Metrics

• Rare-event probabilities are evaluated under the base model with particle Twisted SMC, which propagates particles, applies incremental importance weights, and resamples prefixes.Direct importance sampling is used for LMTailRisk and the imperfect proxy-score experiment, while the learned twist still induces proposal q.Source: §E.2 · p. 34
• The evaluation uses an importance-sampling probability estimator that differs from the particle-SMC procedure used in the main experiments.The estimator produces weighted final particles and an estimated rare-event probability.Source: §E.2 · p. 35
• Rare-event hit rate measures direct generation frequency in the target event, while event ESS measures the effective number of importance-weighted samples contributing to the probability estimate.ESS is set to 0 when no rare-event samples are generated.Source: §E.2 · p. 35
• Relative error compares each method’s mean estimated rare-event probability with a brute-force Monte Carlo reference, which is more accurate but not exact for extremely rare events.The reference uses substantially more samples than the compared methods’ evaluation budget and is summarized across five random seeds.Source: §E.2 · pp. 35–36
• Resource evaluation reports wall-clock time, peak GPU memory, average GPU utilization, and average power draw from monitored runs, summarizing each metric across five seeds with mean and standard deviation.GPU statistics are sampled every five seconds using nvidia-smi.Source: §E.2 · p. 36

Implementation

• All methods use identical training and evaluation sampling budgets, while twist networks train only LoRA parameters on frozen base language models.Standard Twisted SMC follows Zhao et al. 2024, LMTailRisk uses its official defaults, and Self-Distilled TSMC uses two iterations as in Kim et al. 2025.Source: §E.3 · p. 36

Toxic Story Generation

• Toxic story generation uses TinyStories-33M with ToxiGuardrail scoring and evaluates thresholds from 3.0 to 7.0, spanning relatively common to extremely rare events.The prompt is “Once upon a time, there was a.” and the rare-event score is the negative non-toxic classifier logit.Source: §E.3 · p. 36

Jailbreak Attacks on StrongREJECT

• Jailbreak experiments estimate undesirable-response probabilities across six StrongREJECT harm categories using three safety-aligned instruction-following models and the official evaluator.The StrongREJECT score ranges from 0 for harmless responses to 1 for maximally harmful responses.Source: §E.3 · p. 36

Sensitivity to Imperfect Score Function

• Under imperfect scoring, methods train on bR(x)=R(x)+δ(x) with deterministic Uniform[-0.5,0.5] perturbations but evaluate proposals against the true reward R.The perturbation satisfies |bR(x)−R(x)|≤η_sc=0.5, and rare-event probabilities use 4,096 samples with 95% confidence intervals.Source: §E.3 · pp. 36–37

Ablation Study

• The ablation varies quantile ρ from 0.3 to 0.65 and samples per level from 256 to 2,048 at the hardest toxic-story threshold γ⋆=7.Each hyperparameter is varied while all other settings remain identical to the original toxic story generation experiment.Source: §E.3 · p. 37

E.4 Guidance for Selecting the Adaptive Threshold ρ

• Smaller ρ values create fewer but harder transitions, whereas larger values create more closely spaced levels while increasing the total number of transitions.Thus, ρ directly controls the conditional probability of reaching the next event from the current level.Source: §E.4 · p. 37
• For obtaining at least one positive response at every level, the sufficient sample budget is minimized at approximately ρ⋆=1/2.This criterion prioritizes preventing an empty positive phase.Source: §E.4 · pp. 37, 39
• For maintaining a constant number of positive responses at every level, the sufficient sample budget is minimized at approximately ρ⋆=1/e≈0.368.This criterion supports multiple positive responses needed for informative twist learning.Source: §E.4 · p. 40
• The constant-positive criterion is used with ρ=0.3 for inexpensive TinyStories-33M generation, supporting multiple positives and more stable twist-training signals.The choice is close to 1/e≈0.368 and is feasible because the underlying model is small.Source: §E.4 · pp. 40–41
• The one-positive criterion is used with ρ=0.5 for expensive Qwen2.5-7B-Instruct jailbreak experiments, prioritizing avoidance of empty positive phases under limited sampling.This value is optimal under the one-positive-per-level criterion.Source: §E.4 · pp. 39, 41
• These optimizers apply to sufficient bounds under ideal level-wise proposals, while imperfect proposals can reduce the effective transition probability from ρ to ρ−ε.The resulting optimum may depend on proposal quality, but the analysis supports moderate ρ rather than values near 0 or 1.Source: §E.4 · p. 41

F.1 Toxic Story generation

• At thresholds 5.0, 5.5, 6.0, and 7.0, our method achieves substantially lower relative error than SMC and SD-TSMC while maintaining much higher rare-event hit rates.At γ⋆=4.0, higher hit rate and ESS do not guarantee greater estimation accuracy; for γ⋆=7.0, SD-TSMC’s standard deviation is on the order of 10^-6 versus a mean estimate on the order of 10^-7.Source: §F.1 · p. 41, Table 9 · p. 42
• For toxic story generation, the multilevel procedure yields more stable proposal learning for extremely rare targets, while SMC and SD-TSMC estimates vary substantially across random seeds.The contrast is reflected in the baselines’ large standard deviations and the proposed method’s much smaller relative standard deviation at γ⋆=7.0.Source: §F.1 · p. 41
• Our method discovers high-toxicity continuations with rare-event scores around 10.3 that neither SMC nor SD-TSMC finds under the same evaluation budget.These samples indicate that multilevel proposals place meaningful probability mass deeper into the rare-event region rather than merely reaching target boundaries.Source: §F.1 · p. 41

F.2 Jailbreak Attack on StrongREJECT

• On StrongREJECT, our method uses resources comparable to standard Twisted SMC across all three models, with similar GPU usage and slightly lower wall-clock time.LMTailRisk uses less GPU computation and power but requires substantially longer training time.Source: §F.2 · p. 42
• Across six harmful categories and three language models, our method consistently outperforms standard Twisted SMC and LMTailRisk on the StrongREJECT jailbreak task.Neither baseline consistently dominates the other, indicating that the proposed method’s advantage is not specific to one harmful category or language model.Source: §F.2 · p. 42

Overall results

• Under score misspecification, our method remains substantially more accurate than standard Twisted SMC, with best-seed relative error below 10% for γ⋆= 5.0, 5.5, 6.0, and 7.0.For γ⋆≥5.0, standard Twisted SMC returns zero estimates across all seeds and 100% relative error, while our method produces nonzero estimates close to the Monte Carlo reference.Source: §F.3 · pp. 42–43

Coverage

• Our method achieves substantially more reliable confidence-interval coverage than standard Twisted SMC across seven thresholds, although coverage drops at γ⋆= 6.0.Coverage across five proposals is 5/5, 4/5, 4/5, 4/5, 4/5, 1/5, and 5/5, whereas standard Twisted SMC covers only the two least rare settings.Source: §F.3 · p. 43

Per-seed variability

• Across seeds, the multilevel method is more stable and usually maintains nonzero estimates, but severe proxy mismatch can still reduce proposal quality at particular rare-event thresholds.At γ⋆= 6.0, only one of five proposals covers pMC, while at γ⋆= 7.0 all five do; standard Twisted SMC often collapses to zero estimates as events become rarer.Source: §F.3 · p. 43

• Increasing samples per level from 256 to 2,048 raises rare-event hit rate from 4.14×10−2 to 0.81, increases ESS from 3.87 to 149.30, and reduces relative error from 93.1% to 12.8%.The larger budget supplies more positive samples for twist learning, producing a proposal that better concentrates on the target rare-event region.Source: §F.4 · p. 43
• Larger per-level sampling budgets improve estimation at higher cost, increasing runtime from 2.35 to 8.82 minutes and peak GPU memory from 2.57 to 6.98 GiB.GPU utilization rises moderately, while power consumption remains relatively stable.Source: §F.4 · p. 43
• As ρ increases from 0.30 to 0.65, rare-event hit rate falls from 0.55 to approximately 0.01 and ESS from 135.00 to 41.93, while relative error is lowest at 28.3% for ρ = 0.30 and highest at 70.3% for ρ = 0.52.Resource usage changes little across ρ: runtime ranges from 4.28 to 5.37 minutes and GPU memory from approximately 5.1 to 6.0 GiB, supporting moderate values around 0.3–0.5 as a favorable trade-off.Source: §F.4 · pp. 43–44

F.5 Training Metrics

• Training metrics report each level’s adaptive threshold γℓ, realized conditional quantile ˆρℓ, positive-sample rate, ESS, and a highest-scoring response with rare-event score R(x).These metrics are reported for Qwen-7B on the StrongREJECT sexual-content category.Source: §F.5 · p. 44
• The threshold γℓ increases from 0.0072 to 0.5, while representative response scores rise from 0.013 to 0.618 and exceed the target threshold at the final level.Responses begin containing harmful content at level 4, with a score of 0.466.Source: §F.5 · p. 44, Table 18 · p. 47
• The adaptive procedure constructs intermediate events that guide proposals toward harmful responses targeted by the rare-event estimator.This progression demonstrates the intended multilevel guidance mechanism.Source: §F.5 · pp. 44–45
• Positive-sample rates remain around 0.4 across levels and reach approximately 0.495 for the final target rare event, directly addressing the positive-sample bottleneck.The persistent supply of positive samples facilitates learning an improved proposal.Source: §F.5 · p. 45
• ESS remains stable at around 15 across levels, suggesting relatively stable estimation error for the positive-phase gradient.This behavior is reported as consistent with Proposition 1 and supportive of the method’s validity.Source: §F.5 · p. 45

F.6 Qualitative Examples

• The method discovered additional rare unsafe responses on the StrongREJECT jailbreak task that were not found by the other methods.Representative examples are reported for Qwen-7B and Llama-3B, with scores computed using the official StrongREJECT evaluator.Source: §F.6 · p. 45, Table 19 · p. 48, Table 24 · p. 53