acceptodds
Under review as a conference paper at ICLR 2027

Sequential Stability Bounds for Order-Dependent In-Context Learning

Abstract

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 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 , strictly decreasing in slot for and exactly flat for , which couples with a per-source sensitivity score to define *sequential stability coefficients* —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 separation, and a non-vacuity criterion in that is independent of embedding dimension; a spherical-concentration certificate resolves distinct sources at cost . A hierarchy of diagnostic experiments matches the theory: produces spread below across 120 permutations, matched trained and untrained networks are equivalent under normalized attention (TOST , )—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 is recovered from the empirical gap matrix: the position factor tracks closed-form at –, an intraclass ceiling – quantifies the per-example share, and a learned score saturates of that ceiling at —identifying the residual as the framework's predicted many-body component.

Primary area:
learning theory
Keywords:
in-context learning, demonstration ordering, stability bounds, causal attention, algorithmic stability, permutation sensitivity, transformers, variance ceiling

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_UaKgOpenReview ↗
Rating
2
Confidence
3
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

The paper addresses order-dependent in-context learning by proposing a causal-masking account of why demonstration ordering affects ICL accuracy by up to tens of percentage points. It derives a closed-form position-dependent amplification factor W(p,k,L) for causal linear attention, defines permutation-dependent sequential stability coefficients beta_sigma, and proves an order-dependent generalization bound (Theorem 4), a rearrangement-based low-sensitivity-first ordering result (Theorem 5), and a non-vacuity criterion (Theorem 6) plus a spherical-concentration coherence certificate (Lemma 7). The empirical hierarchy includes single-layer invariance (spread below 1e-8), trained-vs-untrained equivalence under normalized attention (TOST p=0.033), W-factor recovery in the gap matrix, a learned-score variance ceiling, and 8-39% accuracy spread on AG News/RTE across four 7-8B LLMs.

Critical strengths
  1. The paper provides a tractable, falsifiable mechanism for order-dependent ICL: causal masking yields position-dependent amplification, with single-layer invariance as a sharp empirical prediction. The authors test that prediction to numerical precision and use trained-vs-untrained equivalence to separate architectural from learned causes.
  2. The empirical hierarchy is unusually broad for a theory paper: synthetic causal linear attention, softmax models, four 7-8B instruction-tuned LLMs, a learned-score variance ceiling, and cost-adjusted baselines are all connected to the same framework. The supplementary code is detailed and the README is reproducible in intent.
Critical weaknesses
  1. The practical regime of the bound is very narrow. The non-vacuity criterion (Theorem 6) requires B3R2 < 0.059 at k=5, alpha=0.05, rmax=0.6, which is a small architecture/source-radius region. The default experimental setting and LLM regime likely do not satisfy the worst-case condition; the entropy-based tightening is a measured, post-hoc substitute and is not integrated into the main theorem. This limits the claim that the framework certifies orderings in the same regime where the 8-39% LLM spread is observed.
  2. The ordering-rule benefit is not clearly superior to simple random trials. Table 2 shows Random-20-tries (0.113 mean risk, 96th percentile, 87% gap capture, 20 evals) dominates or matches Greedy (0.122 mean risk, 60th percentile, 21% gap capture, 126 evals) on the shared query budget. The variance-ceiling analysis is valuable, but it also shows that the theoretically clean per-example sensitivity score saturates only a ceiling that remains far from full recoverability at dx <= 32 in some regimes. The main operational claim therefore needs a stronger cost-adjusted comparison or a better score.
Questions for authors
  1. Please specify the exact parameter regime under which each experimental configuration satisfies Theorem 6's non-vacuity condition. Does the 8-39% LLM spread occur inside or outside the certified regime?
  2. The entropy-based tightening is described as cutting the vacuity gap by a median of 3.4 orders of magnitude on 44/44 trained models. Please provide the formal status of this tightening: is it a theorem-compatible bound, a heuristic, or a post-hoc measurement? How does it affect the official Theorem 6 statement?
  3. In Table 2, how should the reader reconcile Greedy's 21% gap capture and 126 evaluations with the conclusion that the rearrangement rule is an efficient ordering strategy, given Random-20-tries captures 87% with 20 evaluations?
  4. What is the sensitivity of W(p,k,L) to the prefix-normalization and residual assumptions? Does the closed form remain the correct amplification factor under learned attention normalization or attention probabilities that are not near-uniform?
  5. How were the LLM permutations selected and are the 32 queries per permutation sufficient for stable accuracy-spread estimates? What is the confidence interval on the 8-39% spread values?
  6. Can the learned score be replaced by a theoretically justified estimator of eta_j or v_j? The current score is a trained predictor trained on the same gap matrix, which weakens the "certified" interpretation.
  7. Please clarify the exact role of Lemma 7's coherence certificate in the empirical claims. Is the claimed "distinct sources resolved at cost dx = Theta(log k)" actually exercised in any experiment?
  8. Does the framework make a falsifiable prediction about softmax multi-layer models beyond high entropy? The paper reports good fit but the amplification profile appears only weakly matched (rs=0.57).
4 comments
AuthorsOpenReview ↗

Author Response to Reviewer UaKg (Part 1/2): Regime Constants, Thm. 19, & Greedy Ceiling

We thank Reviewer UaKg for the thorough, quantitative review. Because your review raises two main weaknesses and eight technical questions, we respond in two self-contained parts (Part 1/2: W1–W2 & Q1–Q4; Part 2/2: Q5–Q8), with all updates reflected in the revised manuscript.

W1 & Q1 (Which experiments satisfy B3R2<0.059B^3R^2 < 0.059? How far outside are synthetic & LLM runs?). Zero unconstrained trained configurations satisfy the worst-case spectral condition B3R2<0.059B^3R^2 < 0.059 (k=5,α=0.05,CℓG=1,rmax⁡=0.6,L=2k{=}5, \alpha{=}0.05, C_\ell G{=}1, r_{\max}{=}0.6, L{=}2). Across the dx=32,L=3d_x{=}32, L{=}3 trained seeds (Table A5), exact per-seed values are:

VariantBB (mean$\pm$SD)RR (mean$\pm$SD)B3R2B^3R^2 mean [seed min, max]Thm. 6 (L=2L{=}2) ceiling
Normalized3.5±1.23.5 \pm 1.210.1±4.010.1 \pm 4.07.6×1037.6\times 10^3 [6.4×102, 3.1×1046.4\times 10^2,\, 3.1\times 10^4]0.0590.059
Unnormalized1.7±0.41.7 \pm 0.45.4±1.35.4 \pm 1.31.3×1021.3\times 10^2 [79, 17779,\, 177]0.0590.059

Pretrained 77–88B LLMs sit further outside this spectral ball and include RoPE, MLP, and LayerNorm. Revised §4.4 states upfront that Theorem 6 isolates the exact cubic–quadratic spectral barrier rather than certifying unconstrained checkpoints directly, whereas Tier-1 structural tests (L=1L{=}1 <10−8<10^{-8}, bidirectional 2.9×106×2.9\times 10^6\times collapse, normalized TOST p=0.033p{=}0.033, αp↔W(p)\alpha_p \leftrightarrow W(p) at rs=0.82r_s{=}0.82–0.980.98) require no small-norm assumption.

Q2 (Formal status of the entropy tightening, channel ablation, and Thm. 6).

  1. Formal status: Lemma 18, Theorem 19, Corollary 20 (App. H) form a proved data-dependent theorem—not an empirical heuristic. (App. H explicitly discards an earlier unproved product surrogate because it vanishes as ε→0\varepsilon \to 0 at L≥2L \ge 2.)
  2. Relation to Thm. 6: It leaves Theorem 6's spectral criterion unchanged, replacing spectral norms with checkpoint observables (νℓ,ε∗,Ψ,μℓ,Λℓ)(\nu_\ell, \varepsilon^*, \Psi, \mu_\ell, \Lambda_\ell) on a reference distribution.
  3. Tightening & ablation: Across 44/4444/44 multi-layer softmax models (dx∈{8,32,128},L∈{2,4}d_x \in \{8,32,128\}, L \in \{2,4\}), Thm. 19 beats the spectral bound by a median per-model factor of 2.6×1032.6\times 10^3 (3.43.4 OoM) and ranks spread at rs=+0.78r_s = +0.78 (p=6×10−10p{=}6\times 10^{-10}; +0.97+0.97 across 1414 configs; +0.84+0.84 within dx=32d_x{=}32). Gain requires the composite recursion: ε∗\varepsilon^* alone gives rs=+0.12r_s = +0.12 (p=0.45p{=}0.45, 7.9%7.9\% of Q(L)Q^{(L)}; 1.8%1.8\% at L=4L{=}4) and μ\mu alone gives −0.29-0.29. Scale remains >1>1 (median bound/spread 3.5×1033.5\times 10^3, best 322322; L=1L{=}1 controls give 10.910.9–11.711.7 vs. 66–8×10−98\times 10^{-9}).

W2 & Q3 (Reconciling Greedy 21%21\%/126126 evals vs. Random-2020 87%87\%/2020 evals). Two facts reconcile Table 2 and motivate our revised framing in §4.6, §5.5, and §6:

  1. Cost crossover: At k=5,nr=8k{=}5, n_r{=}8, greedy makes [k(k+1)/2−1](1+nr)=126[k(k{+}1)/2 - 1](1{+}n_r) = 126 batch evaluations vs. 5!=1205! = 120. Its O(k2nr)O(k^2 n_r) cost crosses below k!k! only at k≥6k \ge 6 (180180 vs. 720720 at k=6k{=}6; 315315 vs. 40,320=128×40{,}320 = \mathbf{128\times} at k=8k{=}8; 486486 vs. 3.63×106≈7467×3.63\times 10^6 \approx \mathbf{7467\times} at k=10k{=}10).
  2. Single-example ceiling (Table A4, App. I): On 500500 instances (55 models ×100\times 100 fresh sets, dx=32,L=3,k=5,npop=128d_x{=}32, L{=}3, k{=}5, n_{\mathrm{pop}}{=}128), even sorting by the true oracle vjv_j from the 120×5120\times 5 gap matrix captures only 21.2%21.2\% of the ordering gap (learned_inv =21.9%= 21.9\%, greedy =9.0%= 9.0\% under npop=128n_{\mathrm{pop}}{=}128; Random-5 =62.7%= 62.7\%; Random-20 =87.5%= 87.5\%). Because 1−Rmax⁡21{-}R^2_{\max} and cross-slot interactions dominate, Random-m-tries is the right small-kk method.

Q4 (Sensitivity of WW to 1/t1/t normalization and residuals).

  • Removing residuals sets ρI→0\rho I \to 0 (M=γNM = \gamma N), collapsing Eq. (4) to the single maximum-hop term m=Lm{=}L (zero whenever k+1−p<Lk{+}1{-}p < L).
  • Removing 1/t1/t yields position-dependent diagonal 1+(t+2)B3R21 + (t{+}2)B^3R^2 (t≤k+1t \le k{+}1). Table A5 states the uniform upper bound ρˉ=1+(k+3)B3R2\bar\rho = 1 + (k{+}3)B^3R^2 (1+8B3R21{+}8B^3R^2 at k=5k{=}5), steepening W(1)/W(5)W(1)/W(5) from 1.941.94 to 2.122.12 and matching §5.3 where training amplifies sensitivity when unnormalized (p=0.0011,d=0.89p{=}0.0011, d{=}0.89) vs. normalized invariance (TOST p=0.033p{=}0.033).
AuthorsOpenReview ↗

Author Response to Reviewer UaKg (Part 2/2): LLM CIs, Prop. 21, Lem. 7, & Softmax Tests

(Continued — Part 2/2: Technical Questions Q5–Q8)

Q5 (LLM permutation sampling, 3232-query quantization, 95% CIs, and tail concentration).

  • Exhaustive permutations: Every model ×\times task cell in Table 1 evaluates all 5!=1205! = 120 permutations on each of 1010 demonstration sets ×32\times 32 test queries (38,40038{,}400 forward passes per cell; zero permutation subsampling).
  • Quantization & NLL: With 3232 queries, single-permutation accuracy moves in steps of 1/32=3.125%1/32 = 3.125\%, creating ceiling ties when accuracy >85%>85\%; this is why split-half retest uses continuous token NLL (4.54.5–23.223.2 SE above zero).
  • 95% CIs across sets (t0.975,9t_{0.975,9}, added to Table 1): Every cell's lower CI bound sits well above zero (minimum single-set spread across all 4040 pairs is 6.2%6.2\% on AG News and 9.4%9.4\% on RTE):
ModelAG News Spread (%) [95% CI]RTE Spread (%) [95% CI]
Qwen2.5-7B11.9 [9.6, 14.2]15.0 [12.5, 17.5]
Mistral-7B8.4 [6.6, 10.3]16.9 [14.3, 19.5]
Qwen3-8B12.2 [8.5, 15.9]13.1 [10.8, 15.4]
DeepSeek-R1-8B39.1 [34.8, 43.3]29.4 [25.8, 32.9]

(Table 1 also updates Pythia-410M SST-2 to exact per-set mean Acc 46.0–63.4% and spread 42.8 [39.3, 46.3].)

  • Tail concentration (added to App. F): Across all 120120 permutations, AG News spread is moderately catastrophic-tail skewed—the worst 10%10\% of permutations shift accuracy 1.6×1.6\times further from the median than the best 10%10\% (−5.5-5.5 vs. +3.5+3.5 pp)—whereas RTE tails are symmetric (−6.6-6.6 vs. +6.7+6.7 pp, ratio 0.98×0.98\times).

Q6 (Learned score target, dx=128d_x{=}128 gap, compatibility with Prop. 21, and non-certification).

  1. Target & CV protocol: In Table A3 (App. I), the regressor predicts direct realized slot sensitivity across 600600 identities ×8\times 8 contexts using nested GroupKFold over held-out example identities (distinct from Table A6's 1717 heuristic candidates, which were correlated against gap-matrix vjv_j at dx=128d_x{=}128).
  2. Why dx=128d_x{=}128 drops to 0.430.43–0.530.53 of ceiling: Feature-free split-half identity lookup (Table A3) still reaches 6666–90%90\% of Rmax⁡2\sqrt{R^2_{\max}} at dx=128d_x{=}128. Thus the predictable signal is present in ZjZ_j; RF/kk-NN fall short because 600600 groups in dx+1=129d_x{+}1{=}129 dimensions hit finite-sample regression limits (and 3/53/5 models at dx=128d_x{=}128 have training loss >0.9>0.9).
  3. Compatibility with Prop. 21 & non-certification: Prop. 21 proves realized sensitivity is not a function of ZjZ_j alone—both because of context interactions (1−Rmax⁡21{-}R^2_{\max}) and dependence on trained weights θ\theta (cross-init vjv_j Spearman =0.02= 0.02). Fitting a checkpoint-specific regressor recovers at most the Rmax⁡2R^2_{\max} marginal share without violating Prop. 21, and does not inherit βσ\beta_\sigma's certificate (§4.6, Table A4).

Q7 (Where Lemma 7 is exercised empirically). First, thank you for catching a broken section link in §5.5 (fixed from \Cref{app:proof-nonvacuity} to \Cref{app:additional}, App. J). Two experiments in App. J directly test Lemma 7's dx=Θ(ln⁡k)d_x = \Theta(\ln k) coherence scaling:

  1. Onset dimension vs. kk: Taking the dimension where proxy–slot correlation crosses +0.2+0.2 across k∈{3,5,6}k \in \{3,5,6\} gives dx=100,90,78d_x = 100, 90, 78, a ratio dx(k=3)/dx(k=6)=1.28d_x(k{=}3)/d_x(k{=}6) = \mathbf{1.28}—consistent with ln⁡k\ln k (0.880.88) and opposite in direction to pure k2k^2 (0.250.25) or k2ln⁡kk^2\ln k (0.150.15).
  2. Causal coherence intervention: Prescribing pairwise coherence cc at fixed dxd_x amplifies spread by 1.9×1.9\times at c=0.6c{=}0.6–0.80.8 (p<10−10p < 10^{-10}) before pushing it below baseline at c=0.95c{=}0.95 (0.67×0.67\times), isolating a non-monotone coherence window.

Q8 (Falsifiable softmax predictions beyond observing high entropy). Four quantitative tests go beyond observing H/Hmax⁡=0.95H/H_{\max} = 0.95:

  1. Exact L=1L{=}1 invariance at any entropy: All 8/88/8 single-layer softmax models yield spread ≤1.4×10−9\le 1.4\times 10^{-9} (Fig. A4a), confirming single-layer symmetry is architectural rather than a high-entropy or linear-attention artifact.
  2. Depth & learner stratification: Slot-profile agreement with linear W(p)W(p) rises from mean rs=0.41r_s = 0.41 (L=2L{=}2) to 0.790.79 (L=4L{=}4) as Cor. 2's amplification steepens, increases with entropy (rs=0.63,p<0.001r_s = 0.63, p{<}0.001), and collapses to −0.07-0.07 on non-learners (loss ≥0.9\ge 0.9).
  3. Cross-model magnitude: Attention entropy predicts ordering spread at rs=0.85r_s = 0.85 (p=5×10−12p{=}5\times 10^{-12}; partial rs=0.69r_s = 0.69 controlling depth LL).
  4. Data-dependent bound ranking: Theorem 19 ranks spread across all 4444 multi-layer softmax models at rs=+0.78r_s = +0.78 (p=6×10−10p{=}6\times 10^{-10}).
AuthorsOpenReview ↗

Author Response to Reviewer UaKg: Regime, Entropy Bound, LLM CIs, & Ceiling

We thank Reviewer UaKg for the thorough, quantitative review. We address every item (W1–W2, Q1–Q8) below and in the revised manuscript.

W1 & Q1 (B3R2<0.059B^3R^2 < 0.059 vs. trained models & LLMs). Zero unconstrained trained runs satisfy B3R2<0.059B^3R^2 < 0.059 (k=5,L=2,rmax⁡=0.6k{=}5, L{=}2, r_{\max}{=}0.6). Across dx=32,L=3d_x{=}32, L{=}3 seeds (Table A5), normalized models have B3R2∈[6.4×102,3.1×104]B^3R^2 \in [6.4\times 10^2, 3.1\times 10^4] (mean 7.6×1037.6\times 10^3) and unnormalized have [79,177][79, 177] (mean 1.3×1021.3\times 10^2); 77–88B LLMs sit further outside and add RoPE/MLP/LayerNorm. §4.4 states upfront that Thm. 6 isolates this cubic–quadratic norm barrier rather than certifying unconstrained checkpoints, whereas Tier-1 tests (L=1L{=}1 <10−8<10^{-8}, bidirectional 2.9×106×2.9\times 10^6\times collapse, TOST p=0.033p{=}0.033, αp↔W(p)\alpha_p \leftrightarrow W(p) at rs=0.82r_s{=}0.82–0.980.98) need no small-norm assumption.

Q2 (Formal status of entropy bound). Lemma 18, Theorem 19, Corollary 20 (App. H) form a proved data-dependent bound (an earlier unproved product surrogate is discarded in App. H as it vanishes as ε→0\varepsilon\to 0 at L≥2L\ge 2). Leaving Thm. 6 unchanged, Thm. 19 replaces spectral norms with (νℓ,ε∗,Ψ,μℓ,Λℓ)(\nu_\ell, \varepsilon^*, \Psi, \mu_\ell, \Lambda_\ell), tightening vacuity on 44/4444/44 softmax models by median 2.6×1032.6\times 10^3 (3.43.4 OoM) and ranking spread at rs=+0.78r_s = +0.78 (p=6×10−10p{=}6\times 10^{-10}; +0.97+0.97 config-level), whereas ε∗\varepsilon^* alone gives rs=+0.12r_s = +0.12 (p=0.45p{=}0.45, 7.9%7.9\% of Q(L)Q^{(L)}). Absolute scale remains >1>1 (median 3.5×103×3.5\times 10^3\times, best 322322).

W2 & Q3 (Greedy vs. Random-mm at k=5k{=}5). Two facts reconcile Table 2: (1) Cost crossover: Greedy uses [k(k+1)/2−1](1+nr)=126[k(k{+}1)/2 - 1](1{+}n_r){=}126 evals at k=5,nr=8k{=}5, n_r{=}8 vs. 5!=1205!{=}120, crossing below k!k! only at k≥6k \ge 6 (180180 vs. 720720 at k=6k{=}6; 128×128\times cheaper at k=8k{=}8; ∼7467×{\sim}7467\times at k=10k{=}10). (2) Oracle-vjv_j ceiling (Table A4, App. I): Across 500500 instances (55 models ×100\times 100 sets, npop=128n_{\mathrm{pop}}{=}128), even sorting by true oracle vjv_j captures only 21.2%21.2\% of the gap (learned_inv 21.9%21.9\%, greedy 9.0%9.0\%; Random-5 62.7%62.7\%, Random-20 87.5%87.5\%). §5.5 and §6 therefore recommend Random-m-tries at small kk.

Q4 (1/t1/t normalization & residuals). Dropping residuals sets ρI→0\rho I \to 0 (M=γNM{=}\gamma N), leaving only m=Lm{=}L in Eq. (4). Dropping 1/t1/t gives diagonal 1+(t+2)B3R21+(t{+}2)B^3R^2, bounded uniformly by ρˉ=1+(k+3)B3R2\bar\rho = 1+(k{+}3)B^3R^2 (Table A5), steepening W(1)/W(5)W(1)/W(5) (1.94→2.121.94 \to 2.12) and matching §5.3 where training amplifies sensitivity only when unnormalized (p=0.0011p{=}0.0011 vs. normalized TOST p=0.033p{=}0.033).

Q5 (LLM protocol, 95% CIs, tails). All cells evaluate all 120120 permutations ×10\times 10 sets ×32\times 32 queries (38,40038{,}400 inferences/cell). Continuous NLL avoids 1/321/32 accuracy ties. Added t9t_9 95%95\% CIs in Table 1 are all ≥6.6%\ge 6.6\%: AG News Qwen2.5 11.9 [9.6, 14.2], Mistral 8.4 [6.6, 10.3], Qwen3 12.2 [8.5, 15.9], DeepSeek 39.1 [34.8, 43.3]; RTE 15.0 [12.5, 17.5], 16.9 [14.3, 19.5], 13.1 [10.8, 15.4], 29.4 [25.8, 32.9] (Pythia Acc fixed to 46.0–63.4%, spread 42.8 [39.3, 46.3]). Worst-10%10\% shift is 1.6×1.6\times best-10%10\% on AG News (−5.5-5.5 vs. +3.5+3.5 pp) and symmetric on RTE (−6.6-6.6 vs. +6.7+6.7 pp; App. F).

Q6 (Learned score, dx=128d_x{=}128, Prop. 21). Table A3 predicts direct slot sensitivity (600×8600\times 8, nested GroupKFold over held-out identities). At dx=128d_x{=}128, feature-free split-half identity lookup hits 6666–90%90\% of Rmax⁡2\sqrt{R^2_{\max}}, showing RF/kk-NN's 4343–53%53\% is finite-sample regression in 129129 dims (plus 3/53/5 models loss >0.9>0.9). Prop. 21 holds because vjv_j depends on context (1−Rmax⁡21{-}R^2_{\max}) and weights θ\theta (cross-init rs=0.02r_s{=}0.02); learned scores carry no βσ\beta_\sigma certificate (§4.6).

Q7 (Lemma 7 tests). Fixed §5.5 ref to App. J. Two App. J tests exercise Lemma 7: (i) +0.2+0.2-agreement onset gives dx(k=3)/dx(k=6)=100/78=1.28d_x(k{=}3)/d_x(k{=}6){=}100/78{=}\mathbf{1.28} (ln⁡k\ln k predicts 0.880.88; k2k^2 predicts 0.250.25); (ii) prescribing cc at fixed dxd_x boosts spread 1.9×1.9\times at c=0.6c{=}0.6–0.80.8 (p<10−10p{<}10^{-10}) and drops to 0.67×0.67\times at c=0.95c{=}0.95.

Q8 (Softmax tests beyond high entropy). (1) L=1L{=}1 spread ≤1.4×10−9\le 1.4\times 10^{-9} on 8/88/8 models at any entropy; (2) profile match rises from rs=0.41r_s{=}0.41 (L=2L{=}2) to 0.790.79 (L=4L{=}4) and drops to −0.07-0.07 on non-learners; (3) entropy predicts spread (rs=0.85r_s{=}0.85; partial 0.69∣L0.69 \mid L); (4) Thm. 19 ranks 4444-model spread at rs=+0.78r_s{=}+0.78.

AuthorsOpenReview ↗

A Clearer Follow-Up on Xiang et al. (2024), Our Rewritten Paper, and Your Questions

Dear Reviewer UaKg,

Thank you again for engaging promptly with our reply and stating your concern about Xiang et al. (ACL 2024) directly. Looking back at our posts last week, we realize they were overly compressed and heavy on notation (with math lines scrambled by OpenReview's Markdown parser on Nov 13). Since our Nov 14 note, we rewrote the entire paper using ICLR's 10-page discussion allowance (9.5 pages main text, now live at the top PDF link) so the prose and scope read much more naturally. We hope you can forgive our dense earlier posts, and we wanted to walk through Xiang et al. and your main questions clearly here.

1. Why Xiang et al. (ACL 2024) does not pre-empt our core contribution We give Xiang et al. full credit in the Abstract, §1, and §2 for showing across pretrained LLMs (Flan-T5/UL2 vs. Llama2/Vicuna) that causal masking drives high flip rates, and for proposing LoRA fine-tuning (InfoAC). Rather than claiming the observation that causal LMs are order-sensitive, our work starts where that observation ends and shows why Xiang et al.'s intuitive explanation is incomplete:

  • A causal mask alone gives zero sensitivity at 1 layer: Xiang et al. attribute CausalLM sensitivity to example 1 seeing itself while example k sees all k examples. Yet in a 1-layer causal transformer without positional encodings, that exact asymmetric causal mask is active, and order sensitivity is identically zero (below 10^-8 across linear and softmax models), because the query sums direct contributions from each raw input and addition does not care about order. Sensitivity turns on at 2 or more layers, where layer-2 tokens read layer-1 states shaped by different prefixes, launching multi-hop chains bounded in closed form by W(p, k, L). As you noted in Strength 1, this 1-layer vs. multi-layer boundary is a falsifiable prediction absent from Xiang et al.'s 24–40 layer LLM study.
  • Deconfounding the mask from positional encodings and pretraining: Comparing Flan-T5 with Llama2 varies the mask, positional encodings (T5 bias vs. RoPE), architecture, and pretraining at once (hence bidirectional Flan-T5 in Xiang et al. still flips on 7%–19% of inputs). In position-free controls, flipping only the causal mask drops spread three million fold to float noise, and normalized causal models already carry their full sensitivity at random initialization before training.
  • First order-dependent ICL theory and frozen-model ceiling: Xiang et al. prove no theorems and update weights via LoRA. We study frozen-weight ICL, prove the first generalization bound explicit in prompt order (beta_sigma, Theorems 4–6) plus a proved softmax bound (Theorem 19), and prove why frozen single-example selection hits a ~21% ceiling without multi-order sampling or weight updates.

2. Worst-case norm limits vs. our proved softmax bound (W1, Q1, Q2, Q7, Q8) Zero unconstrained runs or 7–8B LLMs satisfy Theorem 6's condition B^3 R^2 < 0.059 (our L = 3 seeds sit in [79, 3.1 x 10^4], Table A5); Theorem 6 isolates why worst-case spectral bounds blow up cubically with norms. To bridge to trained checkpoints, Theorem 19 (Appendix H) is a proved mathematical bound (not a heuristic) swapping spectral norms for observables like attention entropy. While its scale stays above 1, it cuts vacuity by 3.4 orders of magnitude across all 44 trained softmax models and ranks their spreads at 0.78 Spearman correlation (entropy alone gives 0.12). Softmax models also pass four falsifiable checks beyond high entropy (Q8): exact 1-layer invariance at any entropy, stronger profile match at L = 4 (0.79) than L = 2 (0.41) vanishing on non-learners (-0.07), and spread tracking entropy at fixed depth; Appendix J (fixed §5.5 link, thank you!) tests Lemma 7's ln k scaling directly (Q7).

3. Greedy vs. Random-20 at k = 5, oracle scores, & LLM CIs (W2, Q3–Q6) At k = 5, Greedy takes 126 passes vs. 5! = 120 exhaustive, saving compute once k >= 6 (128x cheaper at k = 8). Across 500 fresh prompts (Table A4), even sorting by an oracle knowing every example's true average sensitivity reaches at most 21.2% of the gap, matching our cross-validated predictor (21.9%, zero leakage) vs. 87.5% for Random-20. Single-example sorting hits that ~21% wall because sensitivity depends on preceding neighbors (Proposition 21; at d_x = 128, 129-dim regression hits sample limits while split-half lookup reaches 66–90% of the ceiling), making 5–20 random shuffles the right small-k choice. Finally, Table 1 tests all 120 permutations exhaustively with 95% CIs cleanly above zero on every LLM (8.4% [6.6, 10.3] to 39.1% [34.8, 43.3]; Q5), and dropping 1/t steepens the curve just as unnormalized training amplifies sensitivity (Q4).

Thank you again for your thorough critique; it sharpened both our positioning and our practical takeaways.

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

An interesting paper that addresses an important topic, the variability of predictions based on context ordering. A relatively simple proof idea would help and could simplify the presentation: ordering (no positional encoding) should not affect representations for a 1 layer attention transformer, as we are just take commutative operations over token representations swapping two tokens x1 and x2 in a layer prior to xp simply two sums with QxpKx1⊤Vx1Qx_pKx1^\top Vx1 and QxpKx2⊤Vx2Qx_pKx2^\top Vx2 swapped in the global sum σi=1pαipVxi\sigma_{i = 1}^p \alpha_ipVx_i. On the other hand once we move to two layers we are using the representation that depends on a particular context. As the contexts are ordered, this will make a difference to the output.

Critical strengths

An interesting paper that addresses an important topic, the variability of predictions based on context ordering.
The results are complete and seem sound to me though they are very compressed and would benefit from a more relaxed and explanatory style (the authors say they used gen AI tools for the math and that might explain the style; they could lighten it a bit).

Critical weaknesses

It would be nice if the authors introduced the problem with an intuitive explanation of why ordering makes a difference in transformers with multi-layer attention before going into the technical details.
The authors should consult 'Re-examining learning linear functions in context' (German Conference on Artificial Intelligence, Springer Nature) which shows such ordering effects on small transformers (p6). They also look at heterogeneous sources; they shift the distribution of the input contexts and show degradations in accuracy over several types of shift. In addition arXiv preprint arXiv:2502.03503 argues that attention level distortions due to softmax saturation affect predictions and can also be responsible for ordering effects. There is a problem of reordering even with attention only transformers. Perhaps the authors should investigate how softmax impinges their results. The appendix contains a short section on softmax but it doesn't seem to address this issue. The authors restrict in their perturbation in proposition 15 to a very small one at spot p in the context. But this doesn't reflect the general question where the perturbation can involve elements from very different distributions. This question is addressed by arXiv:2508.14685. That paper shows that softmax can shift to a discontinuous hardmax function under OOD perturbations of an element in the context. This can radically alter the model's performance, as the model only pays attention to one contextual element in this case.

The main weakness for me is the lack of a take home message, What is the take home message about permutation sensitivity? Should we take lower or upper bounds a mean as the model's prediction on a given context? Problems are perhaps not simply a list either in terms of discourse structure What is the data independent ordering rule? on p.3 That would be useful but I didn't find it.

Questions for authors

see above

Some minor comments

When you introduce W(p, k,L) specify what k and L are. Presumably L is the total number of layers, and k is a permutation, I guess.

you look at a single attention head. What happens with multi head attention?

you put bounds on the representational norm and on the weights in the component matrices. Please say how this avoids softmax saturation problems of the sort mentioned above

In l 189 what is \tilde{h}

W is an amplification factor through most of the paper, but the W is used also for weights or matrices in (3) and e.g. (5). The reader can figure out these things but it's simple enough to just explain the notation when you introduce it.

Bound (6) is informative only below 1: an architectural condition (non-triviality) and a geometric one (resolvability). This sentence is weird somehow or just incoherent; the items after the : don't explain or specify the sentence before.

8 comments
AuthorsOpenReview ↗

Author Response to Reviewer RVnh: L=1 Intuition, Naim et al., & Multi-Head Proof

We thank Reviewer RVnh for the clear mechanistic intuition, the pointers to Naim et al.'s papers, and the six minor comments—all incorporated into the revised manuscript.

W1 (1-layer vs. multi-layer intuition in §1). Thank you for this crisp formulation—we adopted it directly in §1 (p. 2). At L=1L{=}1 without positional encodings, the query updates by summing over context tokens, so swapping two demonstrations reorders summands in a commutative sum and leaves the output invariant (W(p,k,1)=γ/(k+1)W(p,k,1)=\gamma/(k{+}1)). At L≥2L \ge 2, each token's layer-11 state already depends on its own causal prefix; earlier slots perturb more intermediate states and launch strictly more causal chains to the query.

W2 (Engagement with Naim et al. 2025, 2026a, 2026b & softmax saturation). We read all three papers closely and added citations and regime bounds in §1, §2, §4.5, and App. G (alongside Xiang et al., ACL 2024 on CausalLM vs. PrefixLM masks):

  • Naim, Fouilhé & Asher (KI 2025, LNCS 15956): On 11D linear functions, sorting xix_i into natural R\mathbb{R}-order on 12L8AH cuts deep-OOD error up to 31.2%31.2\% at σ=10\sigma{=}10 (30.23→20.830.23 \to 20.8 bimodal; 73.93→58.5673.93 \to 58.56 Gaussian) while slightly raising error at σ=3\sigma{=}3–55 (1.34→1.631.34 \to 1.63)—consistent with interaction-dependent ordering. Their Fig. 3 also finds largely uniform in-distribution attention, matching our H/Hmax⁡=0.95H/H_{\max} = 0.95 (εH=0.094\varepsilon_H = 0.094).
  • Naim, Bolte & Asher (NeurIPS 2026) & Naim, Bhar, Bolte & Asher (ACL 2026, SSA): The NeurIPS work proves final-LayerNorm readout boundedness and OOD concentration (ECS→1.8\mathrm{ECS} \to 1.8 at σ=9\sigma{=}9, Lemma 5) without permuting prompts; the ACL SSA work shows that above logit gap δ≈4\delta \approx 4, softmax increasingly resembles hardmax (one OOD outlier shifts MSE from 6.4×10−56.4\times 10^{-5} to 2.202.20).
  • Synthesis: Both lines probe opposite ends of one concentration axis. At k=5k{=}5, δ≈4\delta \approx 4 gives entropy deficit εH≈1.37\varepsilon_H \approx 1.37 nats—over 10×10\times our in-distribution deficit (εH=0.094\varepsilon_H = 0.094 on the 2424 learners; worst-layer ε∗≈0.14\varepsilon^* \approx 0.14 across the 4444-model sweep). Cor. 16 / Thm. 19 govern the in-distribution high-entropy regime, whereas Naim et al. establish the OOD hardmax/saturation boundary where O(εH)O(\sqrt{\varepsilon_H}) ceases to certify monotonicity (our synthetic models also omit final LayerNorm).

W3 (Practical take-home & fixing "data-independent" phrasing). Revised §3(c), §5.5, and §6 distill four points:

  1. Mechanism: Causal masking breaks summation symmetry only at L≥2L \ge 2; early slots carry larger amplification W(p)W(p).
  2. Why static rules cap out: Realized sensitivity follows αpvj\alpha_p v_j with context-dependent vjv_j (Prop. 21, Lem. 22). In Table A4 (500500 instances), even oracle-vjv_j sorting captures only 21.2%21.2\% of the gap vs. 87.5%87.5\% for Random-20. Across our four 77–88B LLMs, NLL permutation rankings do not transfer across models (rs∈[−0.11,+0.29]r_s \in [-0.11, +0.29] AG News; [−0.31,+0.30][-0.31, +0.30] RTE; App. F).
  3. Practice: At k≤5k \le 5, evaluate 55–2020 random orderings on a tiny validation slice (63–87% capture); pool-based greedy probing beats k!k! cost only at k≥6k \ge 6.
  4. Terminology: Rewrote p. 3's "data-independent ordering rule" to "an ordering rule with architecture-determined position weights instantiated by per-source sensitivity scores", clarifying that βσ\beta_\sigma and Thm. 19 are certificates (rs=+0.78r_s{=}+0.78 across models), not instance predictors.

Minor Comments (all 6 incorporated):

  1. Define k,Lk, L in Abstract: Added at first use.
  2. Multi-head extension (Remarks 1 & 5, §4.1 & App. A): For HH-head causal linear attention ht(l+1)=ht(l)+1t∑s≤tWO∑h=1H⟨WQ(h)ht,WK(h)hs⟩WV(h)hsh_t^{(l+1)} = h_t^{(l)} + \tfrac{1}{t}\sum_{s\le t} W_O \sum_{h=1}^H \langle W_Q^{(h)}h_t, W_K^{(h)}h_s\rangle W_V^{(h)}h_s sharing factor 1/t1/t, the head sum factors out of the position sum. Prop. 1, Cor. 2, and Thm. 6's 0.0590.059 ceiling hold verbatim under B3R2↦ΛMH:=R2∑h=1H∥WQ(h)∥∥WK(h)∥∥WO(h)WV(h)∥B^3R^2 \mapsto \Lambda_{\mathrm{MH}} := R^2\sum_{h=1}^H \|W_Q^{(h)}\|\|W_K^{(h)}\|\|W_O^{(h)}W_V^{(h)}\| (γ↦2ΛMH,ρ↦1+3ΛMH\gamma \mapsto 2\Lambda_{\mathrm{MH}}, \rho \mapsto 1{+}3\Lambda_{\mathrm{MH}}; conservative bound HBh3BOR2H B_h^3 B_O R^2). Identical heads show tightness, and 27,00027{,}000 checks verify the closed form to 5×10−135\times 10^{-13} (per-head softmax denominators break shared-1/t1/t factoring).
  3. (B,R)(B,R) & saturation: ∥W∥≤B,∥h∥≤R\|W\| \le B, \|h\| \le R and τ\tau cap logits by ∣q⊤k/τ∣≤B2R/τ|q^\top k/\tau| \le B^2R/\tau; Lemmas 9–11 & Thm. 4 bound arbitrary-support replacements via ηj\eta_j (Remark 4). 4–6. Notation & prose: Defined h~k+1(L)\tilde{h}_{k+1}^{(L)} (§3); distinguished W(p,k,L)W(p,k,L) from WQ,WK,WVW_Q,W_K,W_V; rewrote §4.4's opening sentence.
Reviewer_RVnhOpenReview ↗

reply to rebuttal

Thank you for the rebuttal. You have done a thorough job of tabulating my concerns. I would like to look at the revised submission. But it does not seem to be included in the rebuttal. Thanks

AuthorsOpenReview ↗

Revised PDF Uploaded

Thank you for letting us know! We forgot to submit the top-level Submission Revision form on OpenReview when posting our rebuttal comments. We have now uploaded the revised PDF (36 pages, 9.0 pages main text), which is accessible via the main PDF link at the top of the page. Thank you again for your time and review.

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

This paper develops a position-dependent bounded-differences analysis for causal linear-attention in-context learning. It derives a closed-form upper bound W(p,k,L)W(p,k,L) for how a replacement at demonstration slot pp can propagate to the query, combines it with source-diameter scores ηjη_j into a permutation-dependent stability coefficient βσβ_σ, and uses this coefficient to derive an order-dependent generalization bound and a low-sensitivity-first ordering rule. The paper also presents synthetic experiments, controls comparing causal and bidirectional masking and trained versus untrained models, as well as prompt-order sensitivity measurements for four 7–8B instruction-tuned LLMs on AG News and RTE. It further discusses a softmax-attention extension and a heuristic greedy ordering estimator.

Critical strengths
  1. The paper isolates a sharp architectural prediction. Figure 2 directly visualizes the key claim from Corollary 2: the normalized bound is flat for L=1L=1, while it decreases with slot position for L≥2L≥2. This is a useful diagnostic because it distinguishes a statement about causal composition across layers from a vague claim that “earlier examples matter more.” The experiments also make a serious attempt to test this boundary case, rather than merely reporting aggregate prompt-order effects.

  2. The empirical program includes several worthwhile controls. Figure 3 provides a targeted trained-versus-untrained comparison for the synthetic normalized-attention setting. The authors also test multiple depths, attention normalizations, masking conditions, and source geometries rather than relying on a single synthetic configuration. This is substantially stronger than treating prompt order sensitivity as an anecdotal LLM phenomenon.

  3. The LLM measurements establish that order sensitivity is practically observable. Table 1 reports substantial maximum-minus-minimum accuracy spreads across all 120 permutations at k=5k=5, ranging from 8.4% to 39.1% on AG News and from 13.1% to 29.4% on RTE. The use of NLL split-half retest correlations is a reasonable response to the fact that accuracy rankings become quantized or saturated for high-accuracy models.

Critical weaknesses
  1. The central certificate is presently a worst-case, often vacuous bound whose ordering does not establish useful prediction of realized ICL performance. The paper’s formal result concerns βσβ_σ, a certificate based on worst-case source diameters and norm bounds, not realized loss or accuracy under a prompt ordering. This distinction is important because the claimed practical implication is an ordering rule. Section 4.4 itself gives a very restrictive example: at k=5,L=2k=5, L=2, rmax⁡=0.6r_{max}⁡=0.6, and CℓG=1C_ℓG=1, Equation (8) requires B3R2<0.059B^3 R^2<0.059. Such a condition is not shown to hold for trained transformers or LLMs.

  2. The proposed ordering method is not operational in the setting where it would matter most. The theoretical ηjη_j is the diameter of the support of a source distribution DjD_j​, but ordinary ICL prompts provide one fixed demonstration per source, not access to repeated samples from that source. Algorithm 1 replaces this inaccessible object with resampled forward-pass differences, but the main text does not specify what resampling oracle is available for arbitrary prompts or for the LLM tasks. It is unclear how one would construct the “resamples” in a realistic prompt-selection setting without labels, additional examples from the same source, or a task-specific generative model.

  3. The paper inconsistently characterizes W as exact versus an upper bound. The introduction states that causal linear attention “yields a closed-form amplification factor” and that path counting is exact, whereas Section 4.1 explicitly defines W as an upper bound, W(p,k,L)≥w(p,k,L)W(p,k,L)≥w(p,k,L), on the true amplification. This distinction is fundamental. The matrix power computes the path count exactly for the norm-relaxation recursion, but the recursion itself comes from triangle inequalities and spectral/representation-norm bounds. Thus W is not generally the exact realized perturbation amplification of Equation (3). Figure 2 therefore supports a position profile for the certificate, not an exact profile for a trained model’s influence.

Questions for authors
  1. Can the authors precisely define the prediction and risk objects in Equation (2)? In particular, when evaluating fθ(Pσ(S);xj)f_θ(P_σ(S);x_j), is xjx_j substituted for the appended query token in Pσ(S)P_σ(S), and is the corresponding demonstration zjz_j still included in the context? A formal definition that makes the ghost-sample argument unambiguous would materially increase confidence in Theorem 4.

  2. Can the authors state Theorem 5 and Corollary 2 with an explicit non-degeneracy assumption such as γ>0γ>0? What is the appropriate theorem statement when cross-token coupling is zero?

  3. Can the authors provide held-out evidence that βσβ_σ, the ηη-based ordering, or Algorithm 1 ranks realized generalization gaps or test losses? The essential experiment would use source sets, permutations, and models not used to estimate the score, and compare against random-m-tries, entropy-based selection, and exhaustive search when feasible.

4 comments
AuthorsOpenReview ↗

Author Response to Reviewer NeRf: Proof Scope, Notation, & Oracle-vj Ceiling

We thank Reviewer NeRf for the rigorous checks on our proofs, notation, and algorithmic scope—every point improved the revised manuscript.

W1 (Vacuous absolute bounds vs. predictive validity). We separate two roles of the framework:

  • Mechanistic falsifiability (zero free parameters): L=1L{=}1 flatness (<10−8<10^{-8} linear; ≤1.4×10−9\le 1.4\times 10^{-9} on 8/88/8 softmax models), 6.56.5-OoM collapse upon removing the causal mask (2.9×106×2.9\times 10^6\times, Fig. A2), normalized trained/untrained equivalence (TOST p=0.033p{=}0.033), and empirical αp\alpha_p tracking W(p)W(p) at rs=0.82r_s = 0.82–0.980.98 hold independently of βσ\beta_\sigma's global scale.
  • Tightening & why static ranking fails: Unconstrained weights (B3R2∈[79,3.1×104]B^3R^2 \in [79, 3.1\times 10^4], Table A5) exceed Thm. 6's spectral ceiling (0.0590.059). Replacing spectral norms with measured attention rows gives a proved data-dependent bound (Thm. 19, App. H) cutting vacuity by median 2.6×103×2.6\times 10^3\times (3.43.4 OoM on 44/4444/44 softmax models) and ranking cross-model spread at rs=+0.78r_s = +0.78 (p=6×10−10p{=}6\times 10^{-10}), while remaining >1>1 (322322–3.5×103×3.5\times 10^3\times). Within a model, static ηj\eta_j gives rˉs=−0.00\bar r_s = -0.00 (Table A10) for the reason proved in Prop. 21 & Cor. 23: realized sensitivity vjv_j is context-dependent (§4.4, §5.5).

W2 (Algorithm 1 & resampling oracle). Agreed. Algorithm 1 requires a per-source candidate pool (or augmentation oracle)—as in retrieval from a labeled bank—and cannot run on a bare single kk-shot prompt without extra pool draws. At k=5k{=}5 (nr=8n_r{=}8), greedy costs 126126 evals vs. 5!=1205!{=}120, crossing below k!k! only at k≥6k \ge 6 (180180 vs. 720720 at k=6k{=}6; 128×128\times cheaper at k=8k{=}8). Both constraints are stated upfront in §4.6, App. E (alg:greedy), and §6: for a fixed small-kk prompt without a pool, Random-m-tries (m=5m{=}5–2020) is the right practical choice.

W3 ("Exact path counting" vs. upper bound WW). W(p,k,L)=[ML]k+1,pW(p,k,L) = [M^L]_{k+1,p} counts paths of the norm-relaxation matrix M=ρI+γNM = \rho I + \gamma N in closed form, upper-bounding true amplification: W(p,k,L)≥w(p,k,L):=sup⁡∥hk+1(L)−h~k+1(L)∥/DW(p,k,L) \ge w(p,k,L) := \sup \|h_{k+1}^{(L)} - \tilde{h}_{k+1}^{(L)}\|/D. We fixed p. 3 (which briefly wrote :=:= for WW before §4.1 defined ww) and revised Abstract, §1, and §3 to state upper-bound status throughout.

Q1 (Notation fθ(Pσ(S);xj)f_\theta(P_\sigma(S); x_j) & exchangeability). In §3 Eq. (2), fθ(Pσ(S);x′)f_\theta(P_\sigma(S); x') evaluates fθf_\theta on (zσ(1),…,zσ(k),x′)(z_{\sigma(1)}, \ldots, z_{\sigma(k)}, x'): x′x' occupies query slot (k+1)(k{+}1) while all kk demos—including zjz_j at slot pj=σ−1(j)p_j = \sigma^{-1}(j)—remain in context. In R^\hat R, zjz_j is in context and query xjx_j; in Rˉ\bar R, zjz_j stays in context while i.i.d. zj′∼Djz_j' \sim \mathcal{D}_j supplies (xj′,yj′)(x_j', y_j'). Retaining zjz_j makes Lemma 10 (lem:bias) exact: swapping (zj,zj′)∼Dj2(z_j, z_j') \sim \mathcal{D}_j^2 turns ℓ(fθ(Pσ(S);xj),yj)\ell(f_\theta(P_\sigma(S); x_j), y_j) into ℓ(fθ(Pσ(S(j));xj′),yj′)\ell(f_\theta(P_\sigma(S^{(j)}); x_j'), y_j'), differing from Rˉ\bar R's jj-th summand by one slot-pjp_j replacement bounded by δpj(σ)\delta_{p_j}(\sigma) (§3).

Q2 (γ>0\gamma > 0 in Thm. 5 / Cor. 2 & γ=0\gamma{=}0 limit). Since γ=2B3R2\gamma = 2B^3R^2, γ=0  ⟺  B=0 or R=0\gamma = 0 \iff B{=}0 \text{ or } R{=}0. Then M=ρI=IM = \rho I = I (every m≥1m \ge 1 term in Eq. (4) has γm=0\gamma^m = 0), so W(p,k,L)=0W(p,k,L) = 0 for all pp (fixed App. C's slip ρL→0\rho^L \to 0). Thus δp(σ)=0\delta_p(\sigma) = 0 and βσ≡0\beta_\sigma \equiv 0, reducing Thm. 4 Eq. (6) to ∣Rˉ−R^∣≤ln⁡(2/α)/(2k)|\bar R - \hat R| \le \sqrt{\ln(2/\alpha)/(2k)} (kk-sample Hoeffding), while cL,k=1−(W(k)/W(1))2c_{L,k} = 1 - (W(k)/W(1))^2 is 0/00/0 undefined. At L=1L{=}1, W(p,k,1)=γ/(k+1)W(p,k,1) = \gamma/(k{+}1) holds for all γ≥0\gamma \ge 0. Added γ>0\gamma > 0 to Cor. 2 (L≥2L{\ge}2) and Thm. 5, plus Remark 3.

Q3 (Held-out comparison vs. random-mm, greedy, and entropy heuristics).

  1. Unfitted proxy & entropy baselines: Across 7272 runs (Table A10), worst-case βσ\beta_\sigma gives rˉs=−0.00\bar r_s = -0.00. In Table 2 (55 seeds ×20\times 20 sets, npop=384n_{\mathrm{pop}}{=}384), Lu et al. analogs (GlobalE-analog Rˉ=0.147\bar R{=}0.147, −173%-173\% capture; LocalE-analog Rˉ=0.150\bar R{=}0.150, −195%-195\%) fall below single random (0.1250.125), and per-permutation softmax entropy does not rank orderings (ρˉ=−0.087\bar\rho = -0.087).
  2. Held-out learned score vs. oracle vjv_j (Table A4, App. I): Across 500500 instances (55 models ×100\times 100 fresh sets, dx=32,L=3,k=5,npop=128d_x{=}32, L{=}3, k{=}5, n_{\mathrm{pop}}{=}128, nested GroupKFold over held-out identities on the shared 55-model cohort), held-out learned_inv (ρcv=0.9986\rho_{\mathrm{cv}}{=}0.9986) gets 21.9%21.9\% capture—matching oracle-vjv_j (21.2%21.2\%, no fitted model) and beating greedy (9.0%9.0\% under npop=128n_{\mathrm{pop}}{=}128; p=2×10−5p{=}2\times 10^{-5}), while Random-5 (62.7%62.7\%) and Random-20 (87.5%87.5\%) lead (learned_seeded_5 =65.6%= 65.6\%). Even exact single-example scores hit a ∼21%{\sim}21\% many-body ceiling.
AuthorsOpenReview ↗

A Clearer Follow-Up on Your Questions (and Fixing Our Mangled Math Lines)

Dear Reviewer NeRf,

Looking back at our Nov 13 reply to you, we noticed two problems: we wrote in overly compressed shorthand, and OpenReview's Markdown parser collided with two formulas (in W3 and Q1) and swallowed whole sentences without spaces. Since then, we also rewrote the full paper from top to bottom using ICLR's 10-page discussion allowance (9.5 pages main text, now live at the top PDF link) so the prose and scope are much easier to read. We hope you can forgive that dense first reply, and we wanted to walk through your questions cleanly here.

1. What our theory predicts when worst-case bounds exceed 1 (W1) Unconstrained trained transformers and 7–8B LLMs sit outside Theorem 6's small-weight condition (B^3 R^2 < 0.059), which we now disclose upfront in Section 4.4 and Table A5. Rather than asking beta_sigma to predict exact loss on one unconstrained prompt, the revised paper separates two concrete roles:

  • Zero-parameter architectural predictions: Predicting where perturbations grow across positions does not depend on global weight norms. With zero fitted parameters, our recursion predicts that 1-layer causal models have zero ordering spread (confirmed below 10^-8 across linear and softmax models), that removing the causal mask at L >= 2 collapses spread by six orders of magnitude to float noise, that normalized causal models are just as sensitive at random initialization as after training, and that earlier slots carry greater leverage matching W(p, k, L) (rank correlation 0.82 to 0.98).
  • Data-dependent tightening across models: In Theorem 19 (proved in Appendix H), we swap worst-case matrix norms for measured attention entropy on data. Across all 44 trained multi-layer softmax models, its absolute scale stays above 1 (so it does not certify single prompts), yet it cuts vacuity by over 3,000 times and ranks which trained models have larger vs. smaller ordering spreads at a 0.78 Spearman correlation.

2. When Algorithm 1 is usable vs. what to run on a standard prompt (W2) We completely agree with your critique. On an ordinary prompt where a user has k fixed examples and no extra draws from each source, there is no resampling oracle and Algorithm 1 cannot run. Algorithm 1 applies when each slot draws from a candidate pool (such as retrieval from a labeled bank), and its quadratic probing cost (126 passes at k = 5) beats exhaustive k! search once k >= 6 (180 vs. 720 at k = 6, and 128 times cheaper at k = 8). Both limits are stated upfront in Sections 4.6 and 6: for a fixed short prompt (k <= 5), evaluating 5–20 random orderings on a tiny validation slice is the right practical choice.

3. Held-out comparison against random tries, entropy rules, and an oracle (Q3) We ran the held-out test you asked for on unseen examples and fresh prompts (Tables 2 and A4). Unfitted worst-case beta_sigma and entropy baselines (GlobalE / LocalE analogs) do not beat a single random ordering. More tellingly, across 500 fresh prompts in Table A4, a cross-validated predictor trained on held-out examples captures 21.9% of the accuracy gap, matching an oracle that knows every example's exact true average sensitivity on that prompt set (21.2%) and beating Greedy (9.0%), while 5 random shuffles reach 62.7% and 20 random shuffles reach 87.5%. Even an oracle single-example score tops out near 21% because an example's impact in a multi-layer causal model depends on the prefix ahead of it (Proposition 21), explaining why multi-order random sampling wins at small k.

4. Clean restatement of the math fixes that got scrambled earlier (W3, Q1, Q2)

  • Upper bound W (W3): W(p, k, L) counts paths exactly inside the norm-bounded recursion matrix M = rho I + gamma N, making it an upper bound on true perturbation growth, not exact influence itself. We revised the Abstract, §1, and §3 to state this consistently everywhere.
  • Ghost sample (Q1): In Equation (2), f_theta(P_sigma(S); x') keeps all k demos (including z_j at its assigned slot) in context while placing x' in query slot k + 1. Empirical risk uses query x_j; expected risk keeps z_j in context and draws a fresh query (x_j', y_j') from D_j. Because z_j and z_j' are exchangeable draws from D_j, swapping them changes just that single demo slot, making the bounded-differences step in Theorem 4 exact.
  • Zero coupling (Q2): We added gamma > 0 to Theorem 5 and Corollary 2, plus Remark 3 on gamma = 0 (B = 0 or R = 0), where W = 0, beta_sigma = 0, and Theorem 4 reduces to standard k-sample Hoeffding (while Corollary 2's ratio would be 0/0).

Thank you again for catching every one of these points; they made the revised paper much sharper and clearer.

Thanks for the authors' response. Some of my concerns have been addressed. However, the manuscript's overall writing and presentation still need further improvement, and the core contributions need to be more concise. Therefore, I will maintain my original rating.

AuthorsOpenReview ↗

Thank You: Concise Contributions and Clearer Prose Now Uploaded

Dear Reviewer NeRf,

Thank you for checking our responses and sharing this candid note. You were right that our earlier draft still packed too many nested clauses, symbols, and repeated numbers into individual paragraphs, and that the contribution bullets in Section 1 were too long.

We have just uploaded a focused revision (main.pdf, 9.5 pages main text, 35 pages total) addressing both points:

  1. Concise core contributions (§1, p. 2): We cut the contribution list in half down to three short bullets (~95 words total) that fit cleanly at the bottom of Page 2 and avoid repeating the introductory paragraphs:

    • Order-dependent stability theory (§4, Appendices A–H): We derive the closed-form bound W(p, k, L), prove exact order invariance at L = 1 and strict decay for L >= 2, and establish order-explicit generalization, rearrangement, non-vacuity, and softmax entropy bounds.
    • Architectural isolation from toy models to 7–8B LLMs (§5.2–5.3, §5.5): Controlled ablations isolate multi-layer causal masking as the sole architectural trigger (already present at random initialization under normalized attention) and quantify 8%–39% accuracy swings across four 7–8B LLMs.
    • Prefix-coupling ceiling on static sorting (§5.4–5.5, Appendix I): We prove a variance ceiling R^2_max on single-example predictors and show across 500 prompt sets that prefix coupling caps even oracle single-example sorting at 21.2% of the gap versus 87.5% for 20 random shuffles.
  2. Clearer, unpacked prose in both main text and appendices:

    • Abstract, §1–§4, and §6: We split multi-clause sentences, introduced the physical intuition before symbols, removed repeated statistics between the Conclusion and the Take-Home Message, and tightened Page 10 so the Conclusion and all three end-of-paper statements fit cleanly together.
    • §5 and Appendices A–J: We defined |r_s| directly where §5.3 introduces the random-initialization test, changed Adam's learning-rate notation to lr so it does not collide with eta_j, fixed the prefix matrix N in Proposition 17 to match Appendix A, and rewrote dense blocks in Appendices F, H, I, and J in straightforward step-by-step prose.

Even with your rating unchanged, your push for tighter contributions and clearer writing made the manuscript noticeably better. Thank you again for your time and constructive feedback.

Comments on the paper

3 comments
AuthorsOpenReview ↗

Author Response to All Reviewers: Three-Tier Framework & Summary of Revisions

We thank all three reviewers (NeRf, RVnh, UaKg) for their constructive critiques and concrete suggestions. A shared question across the reviews is: how should our theoretical guarantees be read given that worst-case spectral bounds exceed 11 on unconstrained networks and Random-mm-tries outperforms greedy ordering at k=5k{=}5?

To make the contribution boundaries unambiguous, we organize our results—and have aligned the revised manuscript—around a three-tier hierarchy:

  1. Tier 1 — Architectural Mechanism (independent of bound tightness). Causal masking creates position-dependent perturbation amplification only at depth L≥2L \ge 2. At L=1L{=}1 without positional encodings, permuting demonstrations reorders summands in a commutative query sum, giving exact invariance (spread <10−8< 10^{-8} linear; ≤1.4×10−9\le 1.4\times 10^{-9} across 8/88/8 softmax models). Removing the causal mask at L≥2L \ge 2 collapses spread by a median factor of 2.9×1062.9\times 10^6 (6.56.5 OoM; Fig. A2). Under normalized attention, trained and random-init networks are equivalent in ordering sensitivity (TOST p=0.033p{=}0.033, n=30n{=}30), and empirical slot profiles αp\alpha_p track closed-form W(p,k,L)W(p,k,L) at rs=0.82r_s = 0.82–0.980.98.
  2. Tier 2 — Worst-Case Certificate vs. Proved Data-Dependent Tightening. βσ\beta_\sigma (Thms. 4–5) is the first ICL generalization bound explicit in σ\sigma. Theorem 6 isolates the cubic–quadratic spectral barrier (B3R2<0.059B^3R^2 < 0.059 at k=5,L=2,rmax⁡=0.6k{=}5, L{=}2, r_{\max}{=}0.6); as disclosed in Table A5, unconstrained synthetic models (B3R2∈[79,3.1×104]B^3R^2 \in [79, 3.1\times 10^4]) and LLMs lie outside this worst-case regime. Replacing spectral norms with measured attention rows gives a proved data-dependent bound (Theorem 19, App. H) that cuts vacuity by a median per-model factor of 2.6×1032.6\times 10^3 (3.43.4 OoM on 44/4444/44 multi-layer softmax models) and ranks cross-model spread at rs=+0.78r_s = +0.78 (p=6×10−10p{=}6\times 10^{-10}), while remaining >1>1 in absolute scale (322322–3.5×103×3.5\times 10^3\times).
  3. Tier 3 — Realized Many-Body Barrier & Practical Prescription. Realized slot gaps factorize as αpvj\alpha_p v_j (rank-11 capturing 7070–90%90\% of reproducible variance), where αp≈W(p)\alpha_p \approx W(p) is architectural while vjv_j is context-dependent (Prop. 21, Lem. 22, Cor. 23). A 500500-instance oracle test added in Table A4 (App. I) closes the loop: a held-out random-forest score (ρcv=0.9986\rho_{\mathrm{cv}}{=}0.9986) matches sorting by the true oracle vjv_j (21.9%21.9\% vs. 21.2%21.2\% gap capture, beating greedy's 9.0%9.0\% at p=2×10−5p{=}2\times 10^{-5}), yet even oracle vjv_j captures only 21.2%21.2\% vs. 87.5%87.5\% for Random-2020. Moreover, across our four 77–88B LLMs, permutation rankings are reproducible within each model (NLL retest up to 0.710.71) but do not transfer across models (pairwise rs∈[−0.31,+0.30]r_s \in [-0.31, +0.30]; App. F). Thus at small kk, light multi-order sampling (Random-5 to Random-20) is the principled default, whereas pool-based greedy probing crosses below k!k! cost only at k≥6k \ge 6 (128×128\times cheaper at k=8k{=}8).

Summary of Manuscript Revisions (Main Text Remains 9.09.0 Pages)

  • Intuition, Notation & Precision (§1, §3, §4.1, §4.3, App. C): Added 11-layer commutative-sum vs. L≥2L{\ge}2 prefix-representation intuition (RVnh); defined k,Lk,L in Abstract and h~k+1(L)\tilde{h}_{k+1}^{(L)} in §3, distinguished W(p,k,L)≥w(p,k,L)W(p,k,L) \ge w(p,k,L) from WQ,WK,WVW_Q,W_K,W_V, and clarified ghost-sample retention of zjz_j in fθ(Pσ(S);x′)f_\theta(P_\sigma(S); x') (NeRf, RVnh); added γ>0\gamma > 0 to Cor. 2 & Thm. 5 plus Remark 3 on the γ=0\gamma{=}0 limit (NeRf).
  • Multi-Head Extension (Remarks 1 & 5, §4.1 & App. A): Proved verbatim carryover of Prop. 1, Cor. 2, and Thm. 6 under shared 1/t1/t normalization via B3R2↦ΛMH:=R2∑h=1H∥WQ(h)∥∥WK(h)∥∥WO(h)WV(h)∥B^3R^2 \mapsto \Lambda_{\mathrm{MH}} := R^2\sum_{h=1}^H \|W_Q^{(h)}\|\|W_K^{(h)}\|\|W_O^{(h)}W_V^{(h)}\| (RVnh).
  • Related Work & Softmax Scope (§2, §4.5, App. G): Cited and engaged with Naim et al. (2025, 2026a, 2026b) and Xiang et al. (2024), contrasting our in-distribution near-uniform regime (H/Hmax⁡=0.95H/H_{\max}{=}0.95) with OOD concentration toward hardmax and readout saturation (RVnh).
  • Tables & Algorithmic Scope (§4.4, §4.6, §5–§6, Tables 1–2, A4–A5): Added 95%95\% CIs across all Table 1 LLM spreads (all lower bounds ≥6.6%\ge 6.6\%) and Pythia per-set Acc range 46.046.0–63.4%63.4\% (UaKg); added GlobalE/LocalE analogs to Table 2 (NeRf); added the 500500-instance oracle-vjv_j table (Table A4) and per-seed B3R2B^3R^2 ranges + ρˉ=1+(k+3)B3R2\bar\rho{=}1{+}(k{+}3)B^3R^2 (Table A5; UaKg, NeRf); scoped Algorithm 1's candidate-pool input (§4.6, App. E) and sharpened §6 (NeRf, RVnh, UaKg).
AuthorsOpenReview ↗

A Clearer Walkthrough of Our Rewritten Paper and Core Takeaways

Dear Reviewers (NeRf, RVnh, UaKg) and Area Chair,

Looking back at the replies we posted last week, we owe you an apology for how dense and mechanical they were. In trying to squeeze every equation, p-value, and table reference into OpenReview's character limit, we wrote in telegraphic shorthand that obscured our main story (and even let OpenReview's Markdown parser scramble a couple of math lines in our replies to NeRf and UaKg). When Reviewer RVnh noted that both our draft and our answers still read too compressed and robotic, it really hit home for us.

Over the weekend, we used ICLR's 10-page discussion allowance (9.5 pages main text, 36 pages total, now live at the top PDF link) to rewrite the entire manuscript from Abstract to Appendices so the ideas have room to breathe. We hope you can look past our overly dense first round of replies, and we wanted to summarize what changed in the paper and how it resolves the central questions across your reviews.

What Changed in the Rewritten Manuscript

  • End-to-end prose overhaul (§1–§6, Appendices A–J): We rewrote the paper in relaxed, readable prose, unpacked §1 to explain the mechanism before equations, engaged directly with Xiang et al. (ACL 2024) and Naim et al. (2025, 2026a, 2026b) in §2, and added a Take-Home Message in §6 on why multi-layer causal ICL does not behave like classical regression.
  • Tighter definitions and multi-head proof (§3, §4.1, §4.3, App. A & C): We clarified our risk and ghost-sample notation, stated consistently that W(p, k, L) is an upper bound rather than exact influence, added gamma > 0, and proved verbatim carryover to multi-head causal attention.
  • Empirical checks and clear scope (§4.4, §4.6, §5, Tables 1–2, A4–A5): We added 95% confidence intervals across all four 7–8B LLMs (Table 1), exact weight and state norms (Table A5), entropy baselines (Table 2), upfront candidate-pool and k >= 6 requirements for Algorithm 1, and a 500-prompt oracle test (Table A4).

How This Resolves the Three Shared Questions

  1. Didn't we already know causal masks cause order sensitivity? Prior empirical work (such as Xiang et al., ACL 2024) showed that causal LLMs flip predictions much more often than prefix-bidirectional models, attributing this to earlier examples seeing fewer tokens than later ones. Our paper starts from a sharper threshold: a causal mask by itself does not create order sensitivity. In a 1-layer causal transformer without positional encodings, example 1 still sees fewer tokens than example k, yet shuffling the prompt changes the output by zero (below 10^-8 floating-point noise in both linear and softmax models), because the query adds up direct contributions from each raw input, and addition does not care about order. Order sensitivity turns on at 2 or more layers, where layer-2 tokens read layer-1 states shaped by different prefixes, setting off multi-hop chains from earlier slots. Consequently, multi-layer causal transformers are not silently running textbook OLS, ridge regression, or batch gradient descent in context: even on clean in-distribution data, they act as path-dependent sequential operators.

  2. If the worst-case bound exceeds 1 on unconstrained networks, what does the theory give us? Unconstrained trained networks sit outside Theorem 6's small-weight ball (B^3 R^2 < 0.059, Table A5), yet the theory does two concrete jobs on real checkpoints. First, the shape of W(p, k, L) across positions is independent of weight scale: with zero free parameters, it predicts exact 1-layer invariance and matches empirical slot profiles on multi-layer models (rank correlation 0.82 to 0.98). Second, Theorem 19 (Appendix H) proves a rigorous data-dependent bound (not a heuristic) using measured attention entropy; while its scale stays above 1, it cuts vacuity by over 3,000 times across all 44 trained softmax models and ranks their accuracy swings (correlation 0.78).

  3. Why does trying 5–20 random orderings beat single-example sorting at k = 5? In Table 2, 20 random shuffles capture 87% of the accuracy gap in 20 evaluations, vs. 21% in 126 evaluations for Greedy. Our 500-prompt oracle test (Table A4) shows why: even if an oracle gives us every example's exact true average sensitivity for free, sorting examples one by one reaches at most 21.2% of the gap. While which slot amplifies perturbations is architectural, which example causes trouble depends on the neighbors ahead of it. For short prompts (k <= 5), testing 5–20 random orderings (or averaging predictions across a few shuffles when unlabeled) beats any single-example sorting rule, while pool-based greedy probing saves compute once k >= 6.

Thank you again for your patience with our earlier replies and for helping us make this paper much clearer.

AuthorsOpenReview ↗

Updated PDF Uploaded: Concise Contributions and Plain, Direct Prose Throughout

Dear Reviewers (NeRf, RVnh, UaKg) and Area Chair,

Following Reviewer NeRf's latest feedback that the paper's overall writing still needed improvement and that the core contributions should be more concise, we have uploaded an updated revision (main.pdf, 9.5 pages main text, 35 pages total, live at the top PDF link).

Specifically, we made three targeted improvements across the manuscript without altering any theorem numbers, table/figure labels, or experimental results:

  1. Concise three-point Contributions (§1, p. 2): We trimmed the contribution list by half down to three short bullets (~95 words total) so it sits cleanly at the bottom of Page 2 without repeating the paragraphs above it:

    • Order-dependent stability theory (§4, Appendices A–H): Closed-form path amplification W(p, k, L) (exact flatness at L = 1, strict slot decay for L >= 2), order-explicit generalization and rearrangement bounds, dimension-free non-vacuity conditions, and a data-dependent softmax entropy bound.
    • Architectural isolation from toy models to 7–8B LLMs (§5.2–5.3, §5.5): Controlled ablations confirming that multi-layer causal masking is the sole trigger of order sensitivity in position-free models (already present at random initialization under normalized attention) alongside 8%–39% accuracy swings across four 7–8B LLMs.
    • Prefix-coupling ceiling on static sorting (§5.4–5.5, Appendix I): An exact variance ceiling R^2_max on single-example predictors and held-out evidence across 500 prompt sets showing that prefix interactions cap even oracle single-example sorting at 21.2% of the gap versus 87.5% for 20 random shuffles.
  2. Direct, unpacked prose across Abstract, §1–§6, and Appendices A–J: We broke up long multi-clause sentences, explained each mechanism intuitively before introducing equations, removed repeated numbers between the Conclusion and the Take-Home Message (§6), and rewrote dense appendix passages (Appendices F, H, I, and J) into clear step-by-step explanations. All three end-of-paper statements now fit cleanly on Page 10.

  3. Targeted notation and definition fixes: In §5.3 and Appendix F, we explicitly defined |r_s| (the mean absolute Spearman correlation between empirical slot sensitivity beta_hat_sigma and generalization gap across all 120 permutations). We also separated Adam's learning-rate notation (lr) from the source-diameter symbol eta_j in §5.1, and aligned the causal prefix matrix N in Proposition 17 (Appendix G) with Appendix A.

We hope this cleaner version makes both the main storyline and the technical details easy to follow on a single pass.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.