Technical Summary: Optimizer Memory Makes Shuffle Order a First-Order Source of Fine-Tuning Noise

1. Problem Statement

In fine-tuning large language models, the order in which data domains (or batches) are presented can significantly impact the final model parameters. Previous theoretical analyses, often assuming memoryless gradient steps, predicted that reordering an equal multiset of data should only affect the final state at a second-order level ($O(\eta^2)$) relative to the learning rate $\eta$. This is because the first-order term in a memoryless expansion is a flat sum over the multiset, which remains invariant under permutation.

However, practical optimizers like AdamW are not memoryless; they maintain state buffers (momentum, variance estimates, and bias-correction counters) that advance based on the discrete step index $k$, not the continuous-time training variable $\tau = \eta k$. The paper posits that this "fixed-clock" state advancement causes the same gradient to receive different weights depending on its position in the sequence. Consequently, the contrast between two different orderings of the same data (e.g., sequence $AB$ vs. $BA$) may become a first-order effect ($O(\eta)$) rather than second-order, potentially making shuffle order a dominant source of noise in fine-tuning comparisons.

2. Methodology

Theoretical Framework: Lifted-State Clock Theorem

The authors introduce a "lifted-state" framework where the optimizer state $z = (\theta, \xi)$ includes both parameters $\theta$ and internal buffers $\xi$. They analyze the local behavior of the optimizer over a finite window of $K$ steps with a fixed measurement state.

• Regular Optimizers: Defined as those where the local state map $F^\eta_D(z) = z + \eta X_D(z) + O(\eta^2)$ has an impulse weight independent of position. For these, equal-multiset contrasts are $O(\eta^2)$.
• Fixed-Clock Optimizers: In optimizers like AdamW, the state update for buffers (e.g., $m_{t} = \beta_1 m_{t-1} + (1-\beta_1)g_t$) advances with the step index $t$. The authors derive a Lifted-State Clock Theorem, showing that for fixed-clock optimizers, the endpoint parameter difference between two permutations $w$ and $w'$ of the same multiset is:
  $$\langle u, \theta_K(w) - \theta_K(w') \rangle = \eta \Lambda_{w,w'}(u) + O(\eta^2)$$
  where $\Lambda_{w,w'}(u)$ is the difference in "frozen-parameter optimizer-state replays." If this replay coefficient is non-zero, the order contrast scales as $O(\eta)$.

Analytical Specialization: Frozen-Preconditioner AdamW

To derive closed-form results, the paper specializes to AdamW with a frozen preconditioner ($P_0$) at the measurement state, while keeping the first-moment buffer and bias-correction clocks active.

• Impulse Weights: The authors derive a position-dependent impulse weight kernel $W^{(s,\beta)}_{r,K}$ for a gradient at position $r$. Unlike regular optimizers, these weights are non-flat (e.g., decaying from 0.815 to 0.100 across a window of 16 steps for typical hyperparameters).
• Variance Floor: They derive an asymptotic lower bound for the variance of outcomes over random permutations. The leading term is:
  $$\text{Var}_w[\langle g_E, \theta_K(w) \rangle] \approx \eta^2 \frac{K}{K-1} \sigma^2_\phi V_K$$
  where $\sigma^2_\phi$ is the variance of the projected gradients and $V_K$ is a metric of the optimizer-memory contrast (variance of the impulse weights). For regular optimizers, $V_K=0$, yielding $O(\eta^4)$ variance; for fixed-clock optimizers, $V_K > 0$, yielding $O(\eta^2)$ variance.

Experimental Protocol

The authors validate these claims using local LoRA fine-tuning cells on models like Pythia-1B and Llama-3.2-1B.

• Exponent Split: They measure the scaling of the median parameter difference ($\|\theta_{AB} - \theta_{BA}\|$) against the learning rate $\eta$.
• Controls: They compare AdamW against:
  • SGD: Memoryless.
  • Matched-Clock Momentum: Where the decay $\beta$ and normalization are scaled with $\eta$ (e.g., $\beta = e^{-a\eta}$) to restore the regular $O(\eta^2)$ behavior.
  • Fixed-$\beta$ Momentum: To isolate the effect of buffering from coordinate adaptivity.
• Bitwise-Deterministic Replay: To isolate the mechanism, they fork a warmed optimizer state and replay it with different orderings using bitwise-deterministic steps, eliminating stochastic gradient noise.
• Diagnostics: They introduce metrics like $\rho$ (trust-region ratio for local validity), $\chi$ (conservativity gap between scalar frozen-P and full replay), and $\rho_{curl}$ (scalar sortability of pairwise order preferences).

3. Key Results

1. Exponent Shift from Second to First Order

Empirical measurements confirm the theoretical shift in scaling exponents:

• SGD and Matched-Clock Momentum: The order contrast scales near $\eta^2$ (exponents $\approx 2.0$).
• Fixed-Clock AdamW and Lion: The order contrast scales near $\eta^1$ (exponents $\approx 0.91 - 1.09$).
• Fixed-$\beta$ Momentum: A non-adaptive control with fixed-clock buffering also exhibits an exponent near $1.0$ (slope 0.998), confirming that buffering alone (without coordinate adaptivity) is sufficient to create the first-order order channel.

2. Variance Floor and Order Noise

• Variance Scaling: The order-orbit variance for fixed-clock AdamW scales with $\eta^{1.20}$ (raw) or $\eta^{1.83}$ (when heterogeneity input is controlled), significantly larger than the $\eta^{3.83}$–$\eta^{4.00}$ scaling observed for SGD and matched-clock controls.
• Deterministic Replay: Bitwise-deterministic replay yields variance slopes of 1.83 (AdamW), 2.00 (fixed-$\beta$ momentum), and 4.00 (SGD), isolating the mechanism from stochastic gradient noise.

3. Local Validity and Sortability

• Trust-Region ($\rho$): The first-order frozen-P approximation predicts live outcomes with high correlation (Pearson 0.80) when $\rho < 1$.
• Scalar Sortability ($\rho_{curl}$): In the perturbative regime, pairwise order preferences are largely sortable by a scalar potential (zero directed 3-cycles observed when $\rho_{curl} < 1$). When $\rho_{curl}$ approaches 1, non-conservative bracket terms can create directed cycles (intransitive preferences).

4. Shuffle-Seed Budget

The paper provides a formula to calculate the number of shuffle seeds required to resolve a performance gap $\Delta$ given the order-noise standard deviation $\sigma_{ord}$.

• Implication: When the gap between configurations is comparable to the order-noise floor ($|\Delta|/\sigma_{ord} < 1$), a single-shuffle comparison is underpowered and can easily flip the sign of the result. For example, in a held-out NLL calibration, sign-change rates reached 33–44% when the gap was small relative to the noise.

4. Significance and Claims

The paper claims to isolate and quantify a specific mechanism—fixed-clock optimizer memory—that elevates data ordering from a negligible second-order effect to a dominant first-order source of noise in fine-tuning.

• Mechanism Identification: It demonstrates that the "memoryless" assumption in previous theoretical work fails for standard optimizers because their internal clocks (step counters) do not scale with the learning rate. This creates position-dependent weights for gradients.
• Practical Impact: The resulting "order channel" is large enough that a single random seed can flip the outcome of a close A/B test in fine-tuning. This challenges the reliability of single-seed comparisons in hyperparameter tuning and model selection.
• Diagnostic Tools: The authors provide a "fit-free" way to size this noise using the derived variance floor and impulse weights, offering a criterion for determining the necessary shuffle-seed budget for reproducible comparisons.
• Scope Limitations: The authors explicitly state that their closed-form results are local to a finite measurement window and rely on a frozen-preconditioner approximation. They do not claim to solve global convergence issues or provide a universal ordering policy, but rather to explain the variance observed in local fine-tuning cells.

In summary, the paper argues that optimizer memory makes shuffle order a first-order source of fine-tuning noise, necessitating larger seed budgets and careful interpretation of fine-tuning comparisons when using fixed-clock optimizers like AdamW.