acceptodds
Under review as a conference paper at ICLR 2027

Towards Robust Reasoning Trajectories: Certifying Chain-of-Thought Prefix Stability under Local Perturbations

Abstract

Chain-of-thought (CoT) reasoning enables large language models (LLMs) to solve complex tasks through intermediate reasoning steps, but extended CoT generation also makes inference increasingly sensitive to local perturbations. Small changes in input prompts can alter the reasoning trajectory, making both its stability and computational behavior difficult to characterize. Existing work has largely studied this phenomenon empirically, leaving a fundamental question unresolved: how long can a CoT prefix be certified to remain unchanged under bounded perturbations? We address this question by formalizing trajectory stability as exact prefix preservation under bounded local representation perturbations. We derive finite-perturbation propagation bounds for causal Transformers and combine them with clean next-token decision margins to obtain sufficient conditions for preserving every token in a target reasoning prefix. The resulting certificate explicitly links perturbation location, perturbation magnitude, and certifiable prefix length, providing a trajectory-level robustness guarantee for autoregressive reasoning. We evaluate the theory on four reasoning models and three benchmarks, and observe stability patterns that consistently follow the predicted effects of perturbation location, magnitude, and prefix length. Together, our theoretical and empirical results provide a principled framework for certifying the robustness of reasoning trajectories in autoregressive language models.

Primary area:
interpretability and explainable AI
Keywords:
Chain-of-Thought Reasoning, Certified Robustness, Reasoning Trajectory Stability, Prefix Stability, Large Language Models

Reviews

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

This paper studies a precise form of robustness for autoregressive chain-of-thought generation: how many initial reasoning tokens can be guaranteed to remain exactly unchanged when a bounded local perturbation is applied to one input representation. The paper derives position-dependent finite-perturbation propagation bounds for causal Transformers and combines these bounds with clean next-token margins to obtain sufficient conditions for exact prefix preservation. The resulting certificate can be viewed in terms of certified prefix length, certified perturbation radius, or certifiable input positions (Sec. 3.2–3.3). Empirically, the paper evaluates the predicted position- and magnitude-dependent stability patterns on four reasoning models and three benchmarks, including matched-magnitude controls (Sec. 4.1–4.3, Appendix B). It also gives an end-to-end numerical realization on a controlled two-layer Transformer, including verified constants, certified radii, tightness analysis, and direct generation checks (Sec. 4.4, Appendix C). I find the formulation and position-aware analysis useful, although the gap between the formal certificate and practical certification of contemporary reasoning models remains the main limitation.

Critical strengths
  • S1. The paper isolates a concrete and nontrivial robustness question at the trajectory level rather than reducing robustness to final-answer agreement. Defining robustness as exact preservation of the first K greedy-generated tokens under every perturbation in a local representation-space ball makes the object being certified precise and mathematically testable (Sec. 3.1, Eqs. 1–4). This is useful because autoregressive reasoning can diverge long before the final answer changes, so a prefix-level notion exposes a behavior that answer-level robustness can miss.
  • S2. The main technical contribution is genuinely position-aware: the propagation analysis retains the source position of the perturbation instead of collapsing it into a position-agnostic worst case. Theorem 3.1 and Corollary 3.2 produce a logit-drift coefficient A(i,t,L) whose dependence on the perturbation position leads directly to the prefix-length, perturbation-radius, and input-position certificates in Sec. 3.3 (Theorem 3.3, Propositions 3.1–3.2). Appendix C.3 further shows that retaining source-position information improves the realized certified radius over a position-agnostic certificate, which makes the theoretical refinement consequential rather than merely cosmetic.
  • S3. The large-model experiments are unusually well aligned with the structural predictions of the theory. Across four reasoning models and three benchmarks, the preserved-prefix length increases from early to late input locations under two independently drawn token substitutions, and the trend remains after matching absolute representation-space perturbation magnitudes across positions (Sec. 4.2, Fig. 2, Table 1; Appendix B.3–B.4). The matched-magnitude control is particularly important because it helps separate the claimed positional effect from the trivial possibility that later-token replacements simply induce smaller representation changes.
  • S4. The magnitude-prefix experiments provide a second, distinct empirical check of the certificate geometry rather than reusing the same positional observation. Prefix retention decreases as perturbation magnitude increases across the tested target horizons, and longer target prefixes are systematically harder to retain (Sec. 4.3, Fig. 3; Appendix B.5). This supports the qualitative dependence on both perturbation budget and target prefix length that appears in the certified-radius formulation.
Critical weaknesses
  • W1: The strongest formal certification result is not instantiated on the contemporary reasoning models used in the main empirical study. Sections 4.2–4.3 test whether observed trajectory stability follows the predicted position/magnitude geometry, whereas the actual end-to-end certificate in Sec. 4.4 and Appendix C is realized only on a two-layer synthetic arithmetic Transformer. Moreover, the certified radii in that realization are extremely small (e.g., the minimum radius at K = 32 is 3.397 × 10^-12 in Table 10). This does not invalidate the theory, but it leaves unclear whether the certificate is practically non-vacuous at perturbation scales relevant to the four large reasoning models.

  • W2: The usefulness of the guarantee depends strongly on assumptions and uniform constants that may be conservative for realistic Transformers. In particular, the propagation result relies on A1–A4, including a diffuse-attention bound of the form c_alpha/(j-1), together with uniform Lipschitz/norm constants over the relevant perturbation domain and generation horizon (Sec. 3.2, Appendix A.1). Appendix C.3 already shows that the closed-form relaxations reduce certified radii by roughly a factor of 2.5 relative to the direct recurrence in the controlled model. I therefore remain unsure how much of the favorable position dependence survives numerically after obtaining valid constants for deep production-scale models.

Questions for authors
  • Q1: Have the authors attempted to compute even approximate or conservative certificate quantities (e.g., A(i,t,L), certified radii, or certified prefix lengths) for any of the four reasoning models in Sec. 4.1? If this is computationally infeasible or immediately vacuous, it would be helpful to quantify where the bottleneck occurs.

  • Q2: How restrictive is assumption A4 in the actual attention patterns of the four evaluated reasoning models? In particular, can the authors report empirical values or upper bounds for the effective diffuse-attention factor c_alpha over the positions/horizons used in Sec. 4, and indicate how sensitive the resulting certificate would be to this constant? This would help distinguish whether the current limitation is mostly numerical looseness or a more fundamental mismatch between the assumptions and realistic attention behavior.

Reviewer_Yi1YOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies the stability of chain-of-thought (CoT) reasoning trajectories under local input perturbations, formalizing stability as exact preservation of the first K tokens under greedy decoding. The authors derive a finite-perturbation propagation bound for causal Transformers that retains explicit dependence on the perturbation’s source position: the influence of a perturbation at position i on a subsequent position j is jointly controlled by an attention dilution factor of 1/(j−1) and a cross-layer accumulation factor of (1+log((j−1)/i))^(ℓ−1). Comparing the resulting upper bound on logit drift with the stepwise decision margins under clean decoding, then applying induction over generation steps, yields an exact-prefix certificate. This certificate admits three interpretations: certifiable prefix length, perturbation radius, and input position. Experiments across four reasoning models and three benchmarks show that later and smaller perturbations preserve longer prefixes, qualitatively consistent with the theoretical predictions. The authors also demonstrate end-to-end certification on a two-layer toy Transformer.

Critical strengths
  1. The problem is clearly formulated, and the propagation bound offers a substantive theoretical advance. The paper defines “reasoning trajectory stability” as exact prefix preservation and unifies it into a provable problem through the first divergence step τ and three dual perspectives: prefix length, radius, and position. The central result, Theorem 3.1, explicitly accounts for changes in softmax weights under finite perturbations while retaining the perturbation’s source position. This advances beyond the asymptotic or infinitesimal sensitivity analyses of Hahn, Barbero, and others.

  2. The empirical findings are robust, and the experiments and numerical implementation are rigorous. The observation that later perturbations preserve longer prefixes holds across four models, three benchmarks, and two independent replacement-sampling runs. All 24 curves are strictly monotonic, the correlation between the two sampling runs reaches 0.98, and the effect persists after matching perturbation magnitudes. The certificate implementation uses interval arithmetic, outward rounding, and rational-arithmetic cross-checks, and the reproducibility details are comprehensive.

Critical weaknesses
  1. The practical applicability of the certification remains unproven. Even on a specially constructed two-layer model, the certified radius is only approximately 10⁻¹²; the tighter direct recurrence in the appendix provides only a roughly 2.5-fold median improvement. The paper does not instantiate the certificate on any of the evaluated large models or compare certified radii with actual token-replacement distances.

  2. The large-model experiments support a qualitative pattern but do not sufficiently establish its connection to the proposed theoretical mechanism. A propagation upper bound that decreases as the source position moves later does not imply that actual sensitivity must follow the same ordering. The experiments do not rule out factors such as input content, replacement direction, or the timing of problem restatement, and they lack direct analyses of hidden-state propagation, logit drift, and decision margins.

Questions for authors
  1. Could the positional effect arise from “restating the problem” rather than propagation dilution?
1 comment

Dear Reviewer Yi1Y,

Thank you again for your careful review and constructive feedback. In our point-by-point responses and revised manuscript, we have provided additional certification results, direct propagation measurements, and controls for generation-stage and context-dependent effects.

As the discussion period approaches its conclusion, we would appreciate any feedback you may have on whether these additions adequately address your concerns. If further clarification would be helpful, we would be happy to provide it.

Thank you for your time and consideration.

Best regards,
The Authors

Reviewer_HL9FOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies exact prefix preservation in greedy CoT generation under bounded representation perturbations at one input position. Position-dependent propagation bounds and clean token margins yield sufficient conditions for prefix stability. Experiments on four reasoning models and three benchmarks examine empirical trends, while a two-layer arithmetic model provides numerical certificates.

Critical strengths

S1. The finite-perturbation bound retains the source position and accounts for input-dependent softmax changes. Combined with token margins and common-prefix induction, it guarantees exact greedy-prefix preservation for all admissible perturbations under explicit assumptions.

S2. The positional pattern recurs across models, benchmarks and two replacement draws. It persists when absolute perturbation magnitudes are matched on Qwen3-8B across all three benchmarks, addressing a plausible confound.

Critical weaknesses

W1. Demonstrated certification coverage is limited. Radii on the two-layer arithmetic model are around 10−1210^{-12}; even with the roughly 2.5-fold median improvement in Appendix C.3, their relation to token-substitution distances remains unclear. Large-model experiments show empirical trends without corresponding certificates, limiting the demonstrated relevance to the motivating reasoning models.

W2. The theoretical increment needs clearer comparison. Length, radius and position queries largely follow from one margin condition, leaving the propagation bound as the main technical contribution. Sections 2 and A.9 do not compare it closely enough with prior analyses, including Wang et al. (2026), Appendix D.3, which studies softmax perturbation radii for a different objective.

Questions for authors

Q1. How does Theorem 3.1 compare with the closest causal-path analyses and Wang et al. (2026), Appendix D.3, in assumptions and source-position/depth dependence? Please clarify A4's role and the technical gain in the propagation bound itself.

Q2. For the arithmetic model's full 32-token prefix, how do certified radii compare with layer-zero representation distances from actual token substitutions? Does the guarantee cover any single-token substitution at the evaluated positions?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.