Technical Summary: Sequential Correlations Change In-Context Learning

Problem Statement

Modern sequence models exhibit a striking capacity for in-context learning (ICL), performing new tasks based solely on examples provided in a prompt without parameter updates. While linear regression has served as a useful theoretical sandbox for understanding ICL, existing literature has largely relied on the simplifying assumption that examples within a prompt are independent and identically distributed (i.i.d.). This assumption, while analytically convenient, fails to reflect the sequential correlations inherent in real-world data (e.g., natural language, dynamical systems).

This work addresses the gap in understanding how sequential correlations affect in-context regression. Specifically, it investigates two distinct sources of correlation:

1. Bulk Context Correlations: Dependencies among the tokens within the prompt itself.
2. Query-Context Correlations: Dependencies between the test query token and the preceding context tokens.

The authors aim to determine how these correlations alter the effective sample size of ICL and whether they create architectural mismatches between different attention mechanisms (e.g., linear vs. softmax attention).

Methodology

The authors develop a solvable theoretical model based on reduced linear attention, extending the framework established in prior works (e.g., Lu et al., 2025; Zhang et al., 2023).

Data Setup

The model considers a context sequence $\{x_1, y_1, \dots, x_\ell, y_\ell\}$ and a test query $x_{test}$. The labels are generated via a linear model $y_a = x_a^\top w + \epsilon_a$.

• Sequential Structure: Tokens are modeled as mean-zero Gaussian variables with second moments defined by a correlation kernel $K$.
  • Context correlations: $E[x_a x_b^\top] = K_{ab} I_d / d$.
  • Query correlations: $E[x_{test} x_a^\top] = k_{test, a} I_d / d$.
• Correlation Length: The authors utilize an exponential kernel $K_{ab} = \exp(-|a-b|/\xi)$ to parameterize correlation strength via a correlation length $\xi$.
• Summary Statistics: The theory relies on three summary statistics derived from $K$ and $k_{test}$:
  • $k_2 = \text{tr}(K^2)/\ell$: A bulk measure of context correlation.
  • $k_0 = k_{test}^\top k_{test}$: Measures the overall strength of query-context coupling.
  • $k_1 = k_{test}^\top K k_{test}$: Measures how the query-correlation profile is amplified by the context structure.

Theoretical Framework

The analysis operates in a high-dimensional proportional limit where the dimension $d \to \infty$ and the context length $\ell \propto d$.

• Reduced Linear Attention: The predictor is approximated by $\hat{y}_{test} = \text{tr}(\Gamma H^\top)$, where $H$ is a data matrix constructed from the context and query, and $\Gamma$ is an optimal parameter matrix derived via ridge regression on a training batch of $n$ sequences.
• Random Matrix Theory: The authors derive asymptotic formulas for the expected ICL test loss ($E_{ICL}$) using random matrix techniques. They analyze the concentration of the optimal parameter matrix $\Gamma^*$ and its associated error.
• Regime of Validity: The primary theoretical results assume "weak correlations," where the summary statistics $k_0, k_1, k_2$ remain $\Theta(1)$ as $d, \ell \to \infty$. The paper notes that strong correlations (where $k_2 \propto \ell$) lead to a breakdown of standard high-dimensional concentration, a regime left for future work.

Experimental Validation

The theoretical predictions are validated against:

1. Reduced-parameter linear attention: Directly implementing the theoretical predictor.
2. Full-parameter linear attention: Trainable linear attention models.
3. Softmax attention: Standard transformer architectures with and without MLP blocks.

Key Contributions and Results

1. Effective Context Length Reduction

When the query is independent of the context ($k_{test} = 0$) but the context tokens are correlated ($k_2 > 1$), the authors derive an effective context length formula:
$$\ell_{eff} := \frac{1 + \rho}{k_2 + \rho} \ell$$
where $\rho$ is the label noise.

• Finding: Correlated prompts behave like shorter i.i.d. prompts. As the correlation strength increases (higher $k_2$), the effective number of independent samples decreases linearly.
• Implication: This reduction depends only on the scalar $k_2$ rather than the full spectrum of the covariance matrix, contrasting with classical correlated linear regression where test error depends more delicately on eigenvectors.

2. Gain from Query Correlations

When the query token is correlated with the context ($k_{test} \neq 0$), the model can exploit this additional statistical structure.

• Finding: The ICL error decreases substantially compared to the independent query case. This "query-correlation gain" ($\Delta_{query}$) is positive and increases with stronger query-context coupling ($k_0, k_1$).
• Mechanism: The model utilizes the correlation between the query and the context to improve inference, effectively treating the query as an informative prior.

3. Architectural Mismatch

The paper identifies a significant divergence in performance between attention architectures when query correlations are present.

• Linear vs. Softmax: While linear attention benefits from query correlations, softmax attention demonstrates a significantly larger reduction in error.
• Reasoning: The authors suggest that softmax attention is better matched to sequential inference because it can form query-dependent weights over the most informative tokens. In contrast, linear attention compresses correlations into second-order summaries, limiting its ability to fully exploit the specific structure of query-context dependencies.

4. Breakdown of High-Dimensional Analysis

The authors identify a regime where strong sequential correlations (specifically when the correlation length scales with the context length, $k_2 \propto \ell$) cause the standard high-dimensional concentration of the parameter matrix $\Gamma^*$ to fail. In this regime, the effective number of independent examples no longer scales proportionally with dimension, and the moments of the estimator do not concentrate.

Significance and Claims

The paper claims to be a first step toward a theory of ICL for structured, sequential data. Its primary significance lies in:

• Separating Effects: Distinguishing between bulk context correlations (which hurt performance by reducing effective sample size) and query-context correlations (which help performance by providing signal).
• Architectural Insight: Highlighting that the choice of attention mechanism matters significantly in the presence of sequential structure. The results suggest that softmax attention possesses a distinctive ability to exploit sequential information that is not captured by linear attention theory.
• Theoretical Limits: Defining the boundaries of current high-dimensional asymptotic analyses, specifically noting where strong correlations invalidate standard concentration assumptions.

The authors conclude that developing theory to explain the advantage of softmax attention in these settings, and extending these findings beyond linear regression to richer dynamical tasks, is necessary for understanding ICL in more realistic data regimes.