acceptodds
Under review as a conference paper at ICLR 2027

In-Context Regret: Sequence Models Are Online Learners

Abstract

The search for post-transformer architectures has converged on test-time-learning layers—linear attention, DeltaNet, gated variants, Titans, mesa/ridge layers—each from a hand-chosen objective and update rule. What is missing is a performance calculus: a way to say, before training at scale, how good a memory rule is and how it must fail. We supply one. Every causal sequence-mixing layer is an online learner over its own key–value stream, and its in-context regret organizes the design space: linear attention is Hebbian regularized follow-the-leader ( under bounded predictions), DeltaNet is online gradient descent (), gating is discounting, and the mesa layer is exactly the Vovk–Azoury–Warmuth forecaster (). Against the memorizing comparator that attention estimates, we prove a memory–regret tradeoff: any layer whose state passes an -bit bottleneck suffers per-query recall error at least , with the binary entropy—while its regret against the linear comparator can be zero. What an architecture pays in state is the size of the comparator class it can chase. The theory is generative: parameter-free and strongly-adaptive online learning yield two layers without learned step-size or time-scale gates, and regret probes measure trained networks label-free. On enwik8 from 14M to 340M parameters it pays off twice. The coin-betting layer’s gap to the tuned delta rule closes monotonically with scale and flips sign: at 340M it posts the best test bpc of any recurrent rule, at 2–3× the delta and gated baselines' throughput. And length extrapolation mirrors the hierarchy at every scale—bounded-regret rules evaluate below their training-length bpc at 16× context, while Hebbian’s interference diverges.

Primary area:
learning theory
Keywords:
online learning, sequence modeling, test-time learning, in-context learning, regret, associative memory, linear attention

Reviews

Among:
Shape:
1234this paper, Bottom 1%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.00 over 3 reviews, above 0% of the others.
Reviewer_fSxjOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper views sequence layers, including linear attention, DeltaNet, and Mesa, as online learners and compares them through regret. It establishes a lower bound showing that fixed memory capacity forces recall errors that attention can avoid. Building on this perspective, the authors propose two layers that adapt their step sizes and timescales without learned gates, and evaluate them on synthetic tasks and enwik8 language models with up to 340M parameters.

Critical strengths
  1. The paper is clearly written and easy to follow.

  2. It tackles a real gap, and framing sequence layers through regret and online learning is a clever idea.

  3. The length-extrapolation study is really nice. Re-evaluating the same checkpoints with RoPE interpolation separates positional effects from memory effects, and the bounded-state rules stay below their training-length bpc at 16× context across all four scales.

Critical weaknesses
  1. At 340M, Gated DeltaNet has the best validation bpc (1.2048 vs. 1.2102 for KT-Delta), but the abstract says KT-Delta has the best test bpc. Why lead with test? Please report test bpc for all rules at all scales and add DeltaNet seeds at 340M, since the claimed sign flip (−0.0098) rests on a single run. Also, validation bpc gets worse for every rule from 170M to 340M. Are these runs overfitting at 3×10^8 tokens?

  2. The synthetic regret rankings in Table 6 differ from the bpc rankings in Table 2. This limits what the synthetic results establish about predictive utility. Which regret statistic and comparator class, WlinW_{\mathrm{lin}} or FnpF_{\mathrm{np}}, should inform predictions about LM performance, and under what assumptions? Measuring the relationship between regret probes and bpc on the trained enwik8 models would strengthen this claim. Including Mesa in the enwik8 comparison would also be valuable given its central role in the theoretical framework.

  3. If I expand (3), I get St+1=ctSt−ηtgtS_{t+1} = c_t S_t - \eta_t g_t, where ct∈(0,2)c_t \in (0, 2) depends on the data. That looks like an implicit forget/amplify gate. Is that right? If so, an ablation with ct=1c_t = 1 would show whether the gain over DeltaNet comes from the wealth-based step or from this hidden decay.

  4. App. C.1 says KT-Delta's recurrence is inherently sequential, while linear attention and DeltaNet can be computed chunkwise in parallel, yet KT-Delta is reported faster than both. Softmax also runs out of memory past 8K tokens at eval. Which kernels did you use for the baselines, and does eval build the full attention matrix? A comparison against standard optimized kernels on the same hardware would make the throughput claim much more convincing.

I would frame the paper as a unifying view through regret, limit the claimed guarantees to the configurations actually trained, and strengthen the empirical evidence with more seeds, optimized baselines, Mesa at scale, and both validation and test results. The core idea is clever, but the paper in its current form is not strong enough for acceptance.

Questions for authors

Please check weaknesses section.

Reviewer_1jqoOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
1
Soundness
1
Read review
Paper summary
  • This paper studies sequence model's inner recurrences through the lens of online regret minimization
  • In particular, they derive regret bounds based for a few linear-regression-style recurrences under this rule (MesaNet, Linear Attention, (Gated) DeltaNet) (Table 1)
  • They derive minimum regret bounds for online learners with fixed sized matrix memory, and show that MesNet (i.e. essentially exact online least squares) minimizes this bound
  • They used this regret formalization to derive the KT-Delta layer, a layer which achieves sublinear regret, based on the perspective on coin-betting
  • Empirically, they should that their theoretical results on regret align with reality when the layers are measured in isolation
  • In byte-level models of size 38-340M, they claim that KT-Delta achieves competitive validation perplexity compared to DeltaNet, surpassing at 340M scales, while being slightly faster
Critical strengths
  • A valuable theoretical perspective on sequence models. The paper uses online regret to organize a broad range of existing sequence-model architectures within a common framework. The combination of regret guarantees and memory-capacity lower bounds provides a useful account of both the capabilities and limitations of different memory rules.

  • A theoretically motivated architectural proposal. KT-Delta follows naturally from applying parameter-free online learning to recurrent memory updates. I appreciate the connection between the theoretical framework and the proposed architecture, particularly the use of coin betting to adapt update magnitudes without learned step-size parameters.

  • Solid controlled experiments. The small-scale analyses in Figures 2–4 are reasonably thorough, examining behavior across stationary and nonstationary streams, checking regret bounds, and comparing recall error with the memory-capacity lower bound. These experiments provide useful validation of the theoretical results, although their implications for larger language models remain less established.

Critical weaknesses
  • Presentation and explanation need substantial improvement. The paper often reads as a sequence of claims and results without sufficient explanation connecting them. This made reading the paper very difficult. For example, Section 4.1 introduces the “vectorial Krichevsky–Trofimov bettor” and “wealth” without adequately explaining their meaning, how wealth relates to the optimization objective, or why the resulting update should improve memory behavior. Similarly, Section 5.5 largely repeats numerical results rather than analyzing them. Major work needs to be done in terms of presentation to meet the bar for ICLR acceptance.

  • The language-model evaluation is too limited to substantiate the broader performance claims. The largest experiments use enwik8, training on 1,024-byte sequences for 300M byte tokens, with quality assessed through validation/test bpc and length extrapolation. Broader datasets, longer-context training, larger training budgets, and downstream evaluations are needed to establish generality. Moreover, although the paper measures regret on synthetic streams and small trained recall models, it does not demonstrate that improved internal regret explains the language-model results. The absence of the mesa/ridge baseline from Table 2 further limits this comparison, although its stronger regret bound would not by itself guarantee better language-model performance.

  • The efficiency claims are insufficiently supported. The reported 340M-model throughput advantage over DeltaNet (15k versus 7k tokens/s) compares different execution strategies: KT-Delta uses a fused sequential kernel, while the DeltaNet baselines use chunkwise implementations. Although the appendix describes these implementations, the evaluation does not isolate their effect from that of the update rule. KT-Delta retains the core matrix–vector and rank-one operations of DeltaNet while adding clipping and wealth calculations, so an intrinsic computational advantage is not evident. A convincing comparison should include an equally optimized sequential DeltaNet baseline and profiling across sequence lengths (e.g., 512–32K), key/value head dimensions, and batch sizes.

  • The source of KT-Delta’s gains remains unclear. Relative to DeltaNet, KT-Delta changes residual clipping, history-dependent write magnitudes, global state rescaling, and the learning-rate parameterization. These changes are not separately ablated. In particular, a DeltaNet baseline with matched residual clipping would help determine whether robustifying writes explains the improvement. Additional ablations, together with regret measurements on the trained language models, are needed to establish whether wealth-based adaptation provides benefits beyond these other modifications.

Questions for authors

See weaknesses

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

The paper proposes viewing linear attention from an in-context regret perspective. They classify other linear attention variants through this view and propose new linear attention variants, which they test experimentally on small-scale language modeling.

Critical strengths

None

Critical weaknesses

The paper makes an entirely ai-generated impression and is not human-digestible. The main text contains dense and convoluted results, without providing intuitions or giving good exposition of what it is trying to convey. The entire paper (including abstract, figures, tables, theory, experimental results) seems like there was no human-in-the-loop to reasonably subselect and present results.

While AI-derived theory is usually correct, it is paired with unreasonable assumptions (e.g. the O(T^3) regret bound for linear attention is obtained by blowing up the norm of the stored association, which is a very unrealistic construction since the output is normed in practice) and does not lead to useful downstream improvements in practice. Here, main results in Table 2 are incomplete and existing results are poor. The tok/s numbers are clearly wrong/undertuned (there is no way a reasonably fast GDN implementation is half as slow as attention end-to-end). The baseline GDN uses a sigmoid gate for forgetting, which is non-standard and known to underperform.

Questions for authors

None

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.