Sequential Stability Bounds for Order-Dependent In-Context Learning

In-context learning (ICL) accuracy swings by up to 39 percentage points under demonstration reordering, yet every existing theoretical framework treats the prompt as an unordered set and therefore certifies one number for all $k!$ orderings. We formalize causal attention masking as the source of this asymmetry: tracking a single-example replacement through the causal chain gives a closed-form position-dependent amplification factor $W(p,k,L)$, strictly decreasing in slot $p$ for $L\ge 2$ and exactly flat for $L=1$, which couples with a per-source sensitivity score ${\eta }_j$ to define *sequential stability coefficients* ${\beta }_{\sigma }$—the first bounded-differences constant for ICL that varies with the permutation. Three theorems follow: an order-dependent generalization bound, a rearrangement-based certification of low-sensitivity-first ordering with an $\Omega ({\Delta }^2/(k{C}^2))$ separation, and a non-vacuity criterion in $(B^3{R}^2,r_{\max },L)$ that is independent of embedding dimension; a spherical-concentration certificate resolves distinct sources at cost $d_x=\Theta (\ln k)$. A hierarchy of diagnostic experiments matches the theory: $L=1$ produces spread below $10^{-8}$ across 120 permutations, matched trained and untrained networks are equivalent under normalized attention (TOST $p=0.033$, $n=30$)—so ordering effects are architectural, not learned—and four 7–8B instruction-tuned LLMs show 8–39% accuracy spread on AG News and RTE. The multiplicative decomposition $W(p)\cdot {\eta }_{\sigma (p)}$ is recovered from the empirical gap matrix: the position factor tracks closed-form $W$ at $r_s=0.82$–$0.98$, an intraclass ceiling ${\mathcal{R}}_{\max }^2=0.35$–$0.98$ quantifies the per-example share, and a learned score saturates $\ge 92\%$ of that ceiling at $d_x\le 32$—identifying the residual $1-{\mathcal{R}}_{\max }^2$ as the framework's predicted many-body component.