anthology-of-the-sota

LIT-535: Transformers Learn to Achieve Second-Order Convergence Rates for In-Context Linear Regression

2 min read

Properties5
StatusActive
Tagsin-context-learning, analysis-and-evaluation, training-optimization
Cited as “introduced by” bySOTA-324 — Separate rival accounts of an internal algorithm by convergence rate and conditioning, not by how well each fits the output
Cited as “paper” byNOTE-278 — Linear in Newton steps, exponential in gradient steps: a rate is what separates the rivals
Cited as “source” bySOTA-324 — Separate rival accounts of an internal algorithm by convergence rate and conditioning, not by how well each fits the output, THEORY-067 — A transformer can run a learning algorithm on a model held in its activations, and the architecture admits several, so a construction identifies none

Graph View

Fu, Chen, Jia and Sharan (2023) — ARXIV-2310.17086, NeurIPS 2024. Read as NOTE-278.

Key takeaways

  • The measurement is a rate, not a fit. Re-training only a read-out head on each layer’s hidden states, predictions improve monotonically with depth. Matching each layer to the best number of steps of a candidate algorithm gives a linear trend against Iterative Newton between layers 3 and 9 — about 3 iterations per layer — and an exponential one against gradient descent. Some single layers advance as far as hundreds of GD steps.
  • Ill-conditioning separates them. With κ(Σ) = 100 and a random eigenbasis per sequence, the transformer still matches Iterative Newton at 21 iterations, exactly as in the isotropic case; GD needs about 2,000 steps, which a 12-layer model cannot implement. No fixed or sparse preconditioner helps, because the eigenbasis is resampled.
  • Theorem 5.1: for any k there exist transformer weights predicting x_testᵀ ŵ_k^Newton with M_j = 2M_{j−1} − M_{j−1} S M_{j−1}, M_0 = αS, S = XᵀX; O(d) hidden dimension, k + 8 layers — one layer per Newton iteration, 3 to initialize and 5 to read out.
  • The claim is deliberately weaker than the evidence would allow. BFGS shows the same linear trend, so the paper claims some second-order method, not Iterative Newton specifically.
  • It is architectural, not generic. LSTMs trained identically behave like online gradient descent — later examples weighted more than earlier ones — and their predictions do not improve across layers at all.

Standing in the anthology

Active, and it is the strongest single piece of evidence in this cluster, because it separates the rivals where they actually differ. Fitting a transformer’s output to GD’s output and to Newton’s output both give high similarity; the rate at which layers advance does not, and neither does behaviour under ill-conditioning.

It attacks ARXIV-2212.07677’s identification from inside its own setup — same task, same GPT-2 backbone, same training objective — which is what makes it a different kind of objection from ARXIV-2310.08540’s.

Backlinks