Bounds of Chain-of-Thought Robustness: Reasoning Steps, Embed Norms, and Beyond

Existing research indicates that the output of Chain-of-Thought (CoT) is significantly affected by input perturbations.
Although many methods aim to mitigate such impact by optimizing prompts, a theoretical explanation of how these perturbations influence CoT outputs remains an open area of research.
This gap limits our in-depth understanding of how input perturbations propagate during the reasoning process and hinders further improvements in prompt optimization methods.

Therefore, in this paper, we theoretically analyze the effect of input perturbations on the fluctuation of CoT outputs.
We first derive an upper bound for input perturbations under the condition that the output fluctuation is within an acceptable range, and we prove that:

• i) This upper bound is positively correlated with the number of reasoning steps in the CoT;
• ii) Even an infinitely long reasoning process cannot eliminate the impact of input perturbations.

We then apply these conclusions to the Linear Self-Attention (LSA) model, which can be viewed as a simplified version of Transformer.
For the LSA model, we prove that the upper bound for input perturbation is negatively correlated with the norms of the input embedding and hidden state vectors.

To validate this theoretical analysis, we conduct experiments on three mainstream datasets and four mainstream models.
The experimental results align with our theoretical analysis, empirically demonstrating the correctness of our findings.