Transformers as Multi-task Learners: Decoupling Features in Hidden Markov Models

Chenlu Ye; Chi Han; Tong Zhang; Yifan Hao

REVIEW 3 major objections 4 minor 1 cited by

Transformers as Multi-task Learners: Decoupling Features in Hidden Markov Models

T0 review · 3 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read A fixed Transformer construction provably approximates low-rank hidden Markov models, with vanishing error as memory, demonstrations, and internal gradient steps grow.

desk verdict The main theorem is unproven as stated—the proof quietly assumes the belief feature map is linear—but the explicit construction is promising and worth a serious referee once that assumption is stated and justified. read the letter →

arxiv 2506.01919 v1 pith:M4PGT7E3 submitted 2025-06-02 cs.LG cs.AI

Yifan Hao , Chenlu Ye , Chi Han , Tong Zhang This is my paper

classification cs.LGcs.AI

keywords transformersin-contextlearninghiddenMarkovmodelsexpressivenesslow-ranktransitionsattentionasgradientdescentfeaturedecouplingmulti-taskgeneralization

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper aims to prove that a Transformer can carry out in-context learning on hidden Markov models (HMMs) not by magic but by a concrete, layered computation: lower layers read off a window of recent tokens, upper layers run a regression on those features, and the final readout outputs next-token probabilities. Under low-rank transitions, an observability condition, and a well-spread sample covariance, an explicitly constructed Transformer with $O(\ln L + T)$ layers achieves expected $L^1$ prediction error at most $O(d e^{-\gamma^4 L}) + O(p L^{1/2} e^{-\alpha T/(2L)}) + O(pL \sqrt{\ln(nLp)}/(\sqrt{n}\,\alpha) + Ld/\alpha \cdot e^{-L\gamma^4})$, which vanishes as the memory length $L$, the number of internal gradient steps $T$, and the sample size $n$ grow. The paper's own reading is that this explains why transformers generalize across tasks from a few input-output examples: the architecture is literally running a fast learning algorithm on the in-context demonstrations. The result matters because it turns an empirical observation—that transformers go from local features to decoupled representations across layers—into a provable property of a specific construction.

What carries the argument

The machinery has four pieces. (1) The $(L-1)$-memory approximation $P_L(o_k \mid o_{k-L+1:k-1}) = \mu(o_k)^\top \phi(o_{k-L+1:k-1})$ from Lemma 1, which converts the infinite-history HMM into a finite-memory transition using a belief-state stability result from the POMDP literature. (2) The linearity assumption $\phi = V o_{k-L+1:k-1}$, which makes $P_L = W^* o$ and therefore turns next-token prediction into linear regression solvable by ordinary least squares. (3) The rotation matrices $A$ and $B$ applied to the two-dimensional position embedding, which shift attention by $\pm 1$ token so that after $O(\ln L)$ layers each row carries the full $(L-1)$-token history feature $Z_r$ plus one future feature $F_1$; this is what the paper calls decoupled features. (4) The $2p$-head attention block from Lemma 7, which implements one gradient descent step per layer on the squared loss, yielding the $O(T)$-layer optimization stage and the $e^{-\alpha T/(2L)}$ factor from strong convexity. Together these pieces let the Transformer compute the least-squares predictor $\hat W o_{\text{test}}$ whose error is split into the three vanishing terms of Theorem 1.

What would settle it

Take any low-rank HMM with $p=2$ observations and $d=2$ features that satisfies Assumptions 1–3 but whose belief feature for a two-token history contains a product term, e.g., $\phi(o_{i},o_{j}) = (\,o_i^\top e_1,\; \mathbf{1}(o_i \neq o_j)\,)$, and compute the least-squares error $\min_{W} \mathbb{E}\|P(\cdot\mid o_{k-1},o_k) - W [o_{k-1}; o_k]\|_1$: if this error does not vanish as $L,T,n$ grow, then Theorem 1's bound cannot hold for general low-rank HMMs because the linear-regression reduction has no true target.

Watch

Extended reading notes

Core claim

The paper's central claim is Theorem 1: for any HMM whose latent transition is low-rank (Assumption 1), which is $\gamma$-observable (Assumption 2), and whose sample history covariance has lower-bounded eigenvalues (Assumption 3), there exists a Transformer with $O(\ln L + T)$ layers such that the expected $\ell^1$ error between the true predictive distribution and the readout is bounded as stated in the theorem. The proof gives a fully explicit weight assignment, not an existence argument from counting parameters. First, using rotation matrices on the two-dimensional position embedding, $O(\ln L)$ attention layers shift each token's representation to recover the past $L-1$ observations $\{Z_r\}$ and the next observation $F_1$; this is the 'decoupled feature learning' stage that matches the paper's layerwise probes. Then $O(T)$ layers of $2p$-head attention each perform one gradient descent step on the least-squares objective $\min_W \sum_i \|o_{i,L} - W o_{i,1:L-1}\|^2$, and a final attention head outputs $\hat W o_{\text{test},k-L+1:k-1}$. The key algebraic move is the linear belief-feature assumption $\phi(o_{k-L+1:k-1}) = V o_{k-L+1:k-1}$, which turns the $(L-1)$-memory approximation $P_L = \mu(o_k)^\top \phi(\cdot)$ into the linear model $W^* o$, so that in-context learning of the HMM becomes an explicit linear regression. Theorem 2 extends the same construction to 'weak revealing' cases by grouping $m$ future observations into a single one-hot vector.

Load-bearing premise

The construction collapses unless the belief feature $\phi(o_{k-L+1:k-1})$ is a linear function of the one-hot recent history, $V o_{k-L+1:k-1}$; that assumption is introduced informally in Section 4.1, is not listed among Assumptions 1–3, and is not a consequence of the POMDP stability lemma used to justify the finite-memory approximation.

Editorial extensions

If this is right

A fixed, hand-constructed Transformer realizes in-context prediction for low-rank HMMs, so the observed few-shot behavior of transformers can in principle be explained by an explicit computation rather than by implicit Bayesian inference alone.
The error bound decreases with memory length $L$, internal gradient steps $T$, and demonstration count $n$, matching the empirical finding that accuracy improves with more examples and longer test sequences.
The layerwise split between neighboring-token feature extraction in lower layers and time-disentangled representations in upper layers is a structural consequence of the construction, giving a principled mechanism for the probing results in Figure 3.
In weak-revealing settings, where a single observation cannot identify the hidden state, grouping $m$ future observations recovers the same type of bound, so the architecture can handle latent spaces larger than the observation alphabet.
Increasing depth ($\ln L + T$ layers) rather than width is the lever that drives approximation error down in this construction.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Because the linearity of $\phi$ is assumed but never stated in Theorem 1, the theorem as written applies only to the linear-feature subclass; a reader who wants the general-HMM claim should treat it as conditional on that assumption—this is my inference, not the paper's framing.
A testable extension is to replace $V o$ with random or kernel features; the same gradient-descent attention module should learn $\hat W$ in the feature space, with an extra approximation error measuring how well the kernel spans the true belief features.
The $O(\ln L)$-layer history aggregation suggests depth can substitute for width in attention memory; a synthetic experiment comparing $\ln L$-layer versus $L$-layer towers on the same HMM could check whether the construction's depth dependence is necessary or merely sufficient.
The construction implies that probing a trained Transformer for 'decoupled features' may reflect the token-shifting position-embedding mechanism, so the empirical layerwise pattern could be diagnostic of whether the network adopted the paper's specific algorithm.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Read the Hao, Ye, Han, Zhang paper. The headline: Theorem 1 is not proven as stated. The proof assumes the belief feature map phi is a linear function of the one-hot history—introduced in Section 4.1 as 'for simplicity' and used in Eq. (5) of Appendix D—but that assumption is missing from Theorem 1 and does not follow from Assumptions 1-3. For a generic low-rank HMM the posterior belief is a nonlinear function of observations; a simple 2-state example with full-rank emission yields posterior values 0.956, 0.211, 0.711, 0.029 on the four length-2 histories, which no affine map can reproduce. So the target W* o_history does not exist and the linear-regression/attention construction cannot approximate the HMM. This is the load-bearing issue.

The paper still does real work. The explicit construction—local feature extraction via rotary position embeddings, then implicit linear regression with gradient-descent attention—is new for HMMs with low-rank transitions, and it gives a concrete mechanism for the local-to-global layerwise hierarchy observed empirically. The three-term error decomposition is standard, and the imported lemmas from Uehara, Bai, and Fan are used honestly. If the linear-realizability assumption were stated in Theorem 1 and either justified or relaxed, the theorem would be defensible.

There are other soft spots, in proportion. The empirical study uses 8192 sampled HMMs with 128 hidden states and a 16-token vocabulary; those random transitions are full-rank and the emission matrix cannot satisfy the stated observability condition, so the experiments are motivation rather than verification of the theory. The proof also has minor artifacts—an 'Assumption 4' reference in the proof of Lemma 1 that should be Assumption 2, and a forward reference to Lemma 4—that are easy to fix.

Who should read it: people working on provable in-context learning and Transformer expressiveness. The construction is checkable and the gap is instructive. I'd send it to peer review, with the expectation of major revision: the authors need to state the phi-linearity assumption explicitly and discuss which HMMs satisfy it, or extend the construction to nonlinear feature maps. I wouldn't cite it in its current form.

Referee Report

3 major / 4 minor

Summary. The paper studies how Transformers perform in-context learning on Hidden Markov Models. Empirically, it reports that lower layers of a trained Transformer encode local features and upper layers produce positionally decoupled representations. The theoretical contribution is Theorem 1: under low-rank transitions (Assumption 1), gamma-observability (Assumption 2), and a lower bound on the sample covariance of one-hot histories (Assumption 3), there exists an O(log L + T)-layer Transformer whose readout approximates the HMM predictive distribution with error decomposed into model approximation, optimization, and generalization terms. Theorem 2 extends the construction to weakly revealing settings using m-step future observations. The proof proceeds by approximating the HMM by a finite-memory low-rank model, learning the resulting linear mapping by gradient-descent attention layers, and bounding the generalization error of the least-squares estimator.

Significance. If Theorem 1 were correct as stated, the paper would give an explicit, hand-constructed Transformer that provably performs in-context prediction for low-rank HMMs, with quantitative error rates in memory length, number of internal gradient steps, and sample size. The three-term error decomposition is a useful organizing principle, and the paper makes a genuine attempt to connect layerwise empirical observations to an explicit construction. The main theoretical claim, however, is currently not established as stated because the proof relies on a linear-realizability assumption on the belief feature map that is neither listed in Theorem 1 nor implied by Assumptions 1-3. Since that assumption is load-bearing for the regression formulation, the gradient-descent construction, and the generalization bound, the paper's central contribution needs substantive revision before the result can be accepted.

major comments (3)

[Sec. 4.1; App. D, Eq. (5)] Theorem 1 is not proven as stated: the proof requires that the belief feature map phi be linear in the one-hot history, phi(o_{k-L+1:k-1}) = V o_{k-L+1:k-1}, which is introduced in Sec. 4.1 as 'For simplicity, here we assume phi can be represented by a linear mapping' and used in App. D immediately before Eq. (5) to derive P_L(·|o_{k-L+1:k-1}) = W^* o_{k-L+1:k-1}. This assumption is absent from Theorem 1 and is not implied by Assumptions 1-2, because phi is constructed from the belief state b_L, which is a nonlinear Bayes update (a normalized product of emission and transition factors). For example, the 2-state HMM in the stress test satisfies Assumptions 1-2 but its L=3 belief map is not affine, so no W^* exists. Since Eq. (5) is the target of the linear regression in Eq. (6), the gradient-descent attention construction and the generalization bound both collapse without this assumption. The theorem must either include explicit linear-realizability of phi as an assumption or replace the regression-based construction with an analysis that handles nonlinear phi.
[App. E, Sec. E.1] Theorem 2 inherits the same linear-realizability gap. After defining P_L(o_{k:k+m}|...) := mu(o_{k:k+m})^T phi(o_{k-L+m:k-1}), the proof states 'Considering the linear assumption on phi' and immediately writes P_L = W' o_{k-L+m:k-1}. Assumption 4 only provides observability of the m-step emission operator; it does not make the belief-induced phi affine. The optimization and generalization error bounds for Theorem 2 therefore also require an additional assumption or a new argument.
[App. F, proof of Lemma 1] The proof of Lemma 1 as written does not establish the claimed L1 bound. The displayed calculation bounds a one-sided expected difference, E[P(o_k|o_{1:k-1})] <= E[P_L(o_k|...)] + epsilon, by inserting absolute values inside the inner product. Lemma 1, however, claims a bound on E||P(·|o_{1:k-1}) - P_L(·|o_{k-L+1:k-1})||_1, which requires controlling the absolute deviations summed over all output tokens. The argument in App. F only controls the signed difference without taking absolute values, so the model-approximation terms in Theorems 1 and 2 do not follow from the given proof.

minor comments (4)

[App. F] Appendix F refers to 'Assumption 4' when invoking the contraction from observation distributions to hidden-state distributions; in the context of Lemma 1 and Theorem 1 the relevant condition is Assumption 2.
[Sec. 5.1.2, App. D.2] The paper twice writes 'Cauchy-Schwartz'; the standard name is Cauchy-Schwarz.
[Footnote 6, Sec. 5.2] The readout index range '(L+1)(p+3)+1:(L+1)(p+3)+p^m' appears inconsistent with the earlier allocation D >= 2 p^m L; please check the offset and the width of the readout block.
[Fig. 5 caption] The caption of Figure 5 lists alphabet tokens and 'Length: 2 = 2^1' without explaining in the text what these tokens represent; add a sentence describing the doubling construction and the role of the A-matrix rotations.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the derivation is self-contained apart from an unstated linear-realizability assumption that is a correctness gap, not a circular reduction.

full rationale

The central claim is a constructive expressiveness result: under Assumptions 1-3, a transformer with O(ln L + T) layers is said to approximate an HMM predictive distribution. The proof chain is: (i) Lemma 1 approximates the full-memory posterior by an (L-1)-memory low-rank model P_L, citing Uehara et al. (2022) and Guo et al. (2023a) from non-overlapping groups; (ii) Appendix D reduces the construction to linear regression because of the explicit assumption that the belief feature phi is linear in the one-hot history (Sec. 4.1: "For simplicity, here we assume phi can be represented by a linear mapping"; Eq. (5): "P_L(...) = U^T V o_{k-L+1:k-1} := W^* o_{k-L+1:k-1}"); (iii) the transformer implements gradient descent for this regression following Bai et al. (2023), and generalization is bounded by standard concentration lemmas (Lemma 6 from Ye et al. 2023/Zhang 2023 and Lemma 8 from Fan et al. 2023, both standard and externally checkable). No fitted parameter is renamed as a prediction: W_hat is estimated from i.i.d. samples and all three error terms are derived rather than calibrated. The two self-citations are minor technical concentration inequalities and are not load-bearing. The genuine concern is the unstated linearity of phi, which is not implied by Assumptions 1-3 and does not hold for generic low-rank HMMs; this makes Theorem 1 overclaimed as stated, but it is an omitted assumption / correctness risk, not a circularity in which the conclusion is equivalent to the input by construction.

Assumptions & free parameters 5 free parameters · 7 assumptions · 0 invented entities

The theorem imports three external results: exponential stability of low-rank POMDP beliefs (Lemma 3, Uehara et al. 2022), attention-implements-gradient-descent (Lemma 7, Bai et al. 2023), and a matrix concentration inequality (Lemma 8, Fan et al. 2023). The paper's own additions are Assumptions 1-4, the unlisted linear-phi realizability condition, and hand-chosen constants beta_1, beta_2, L, T, m. No fabricated entities are introduced; Z_r and F_r are construction artifacts within the attention layers, not independent postulates. The main burden is the linear-phi assumption, which is ad hoc to this paper and is not justified by the cited POMDP literature.

free parameters (5)

beta_1 = sufficiently large, sent to infinity
Scales the rotary-position matrices A and B in the feature-extraction layers (Section 5.1.1, Appendix D.1); chosen by hand to make softmax concentrate on the intended neighbor token.
beta_2 = any value greater than 1000nk
Gating constant in the gradient-descent attention heads (Appendix D.1); chosen by hand to suppress attention to non-demonstration rows.
L (memory length) = Theta(gamma^{-4} log(d/epsilon))
Sliding-window length that trades model-approximation error against capacity (Lemma 1); chosen, not derived from a uniqueness principle.
T (number of gradient-descent layers) = chosen so O(p L^{1/2} e^{-alpha T/(2L)}) reaches target
Number of internal gradient steps in the construction; a hand-chosen accuracy-versus-depth knob in Theorem 1.
m (future window in Theorem 2) = any constant with m < L
Number of future observations composed in the weak-revealing extension (Section 4.3); chosen by hand to make the m-step operator injective.

assumptions (7)

domain assumption Assumption 1: low-rank transition P(h'|h) = w*(h')^T psi*(h)
Standard in low-rank POMDP representation learning (Section 4.1); restricts the HMM class but is not derived in the paper.
domain assumption Assumption 2: gamma-observability, ||Td - Td'||_1 >= gamma ||d - d'||_1
Emission full-column-rank style condition, needed for Lemma 1's fixed-memory approximation (Section 4.1).
ad hoc to paper Linear realizability of phi: phi(o_{k-L+1:k-1}) = V o_{k-L+1:k-1}
Introduced in Section 4.1 'for simplicity' but not listed in Theorem 1; load-bearing for the linear-regression reduction (Eq. (5)-(6), Appendix D).
domain assumption Assumption 3: lambda_min(n^{-1} Z Z^T) >= alpha
Coverage and well-conditioning of history features; needed for the least-squares inverse and gradient-descent convergence (Section 4.2).
domain assumption Assumption 4: under-complete gamma-observability with m-step future observations
Weak-revealing variant used for Theorem 2 (Section 4.3).
standard math Lemma 3, Theorem 14 of Uehara et al. 2022: exponential stability of low-rank beliefs
Imported external theorem used in the proof of Lemma 1 (Appendix F).
standard math Lemma 7, Theorem 4 of Bai et al. 2023: attention layers implement gradient descent for well-conditioned linear regression
Imported external theorem; the optimization error bound in Appendix D.1 rests on it.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Transformers as Multi-task Learners: Decoupling Features in Hidden Markov Models." pith.science (2026). https://pith.science/paper/M4PGT7E3

@misc{pith2026250601919,
  author       = {Pith},
  title        = {Pith review of: Transformers as Multi-task Learners: Decoupling Features in Hidden Markov Models},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/M4PGT7E3}},
  note         = {Machine review of arXiv:2506.01919}
}

read the original abstract

Transformer based models have shown remarkable capabilities in sequence learning across a wide range of tasks, often performing well on specific task by leveraging input-output examples. Despite their empirical success, a comprehensive theoretical understanding of this phenomenon remains limited. In this work, we investigate the layerwise behavior of Transformers to uncover the mechanisms underlying their multi-task generalization ability. Taking explorations on a typical sequence model, i.e, Hidden Markov Models, which are fundamental to many language tasks, we observe that: first, lower layers of Transformers focus on extracting feature representations, primarily influenced by neighboring tokens; second, on the upper layers, features become decoupled, exhibiting a high degree of time disentanglement. Building on these empirical insights, we provide theoretical analysis for the expressiveness power of Transformers. Our explicit constructions align closely with empirical observations, providing theoretical support for the Transformer's effectiveness and efficiency on sequence learning across diverse tasks.

Figures

Figures reproduced from arXiv: 2506.01919 by the authors.

**Figure 1.** Accuracy of the Transformer under in-context learning setting. The y-axis denotes the number of demonstrative examples in-context, and the x-axis denotes the length of the test input otest. All demonstrative examples have a length of 8 in this setting. The expressiveness of Transformers on sequence modeling has been explored from several perspectives. Liu et al. (2022a) demonstrate that Transformers can emulate aut… view at source ↗

**Figure 2.** After randomly shuffling the positions of demonstrative inputs, we examine how the logits receive changes over layers (y-axis) and attention heads (x-axis). The measure is 1 − std(logits) mean(logits) . Decoupled features on upper layers. We randomly shuffle the positions of demonstrative inputs and measure how the logit changes. As shown in [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗

**Figure 3.** Investigation on Transformer recognitions. [PITH_FULL_IMAGE:figures/full_fig_p003_3.png] view at source ↗

Figures from the paper (4 more)

**Figure 4.** Figure 4: Illustration of Hidden Markov Model. where {Q, K, V } refer to the Query, Key and Value matrix respectively. The activation function σ(·) can be row-wise softmax function3 or element-wise ReLU function4 . Transformer. Based on the architecture of Attention head, with t…

**Figure 5.** Figure 5: Illustration of Feature learning process. [PITH_FULL_IMAGE:figures/full_fig_p007_5.png]

**Figure 6.** Figure 6: Illustration of gradient descent performance. [PITH_FULL_IMAGE:figures/full_fig_p008_6.png]

**Figure 7.** Figure 7: Attention of the Transformer on in-context learning inputs. The y-axis denotes layers [PITH_FULL_IMAGE:figures/full_fig_p014_7.png]

Discussion (0). Sign in to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Extracting Algorithms in Pre-trained LLMs: A Case on Hidden Markov Models
cs.AI 2026-06 conditional novelty 6.0 of 10

Pre-trained LLMs on HMM next-token prediction appear to use finite-window Soft n-gram-like learned predictors rather than Bayes-optimal inference, as shown by a new activation-probing and causal-patching pipeline.

Reference graph

Works this paper leans on

50 extracted references · 28 canonical work pages · cited by 1 Pith paper

[1]

L., Almeida, D., Altenschmidt, J., Altman, S., Anadkat, S., et al

Achiam, J., Adler, S., Agarwal, S., Ahmad, L., Akkaya, I., Aleman, F. L., Almeida, D., Altenschmidt, J., Altman, S., Anadkat, S., et al. (2023). Gpt-4 technical report. arXiv preprint arXiv:2303.08774

arXiv 2023
[2]

Agarwal, A., Kakade, S., Krishnamurthy, A., and Sun, W. (2020). Flambe: Structural complexity and representation learning of low rank mdps. Advances in neural information processing systems , 33:20095--20107

work page 2020
[3]

Aky \"u rek, E., Schuurmans, D., Andreas, J., Ma, T., and Zhou, D. (2022). What learning algorithm is in-context learning? investigations with linear models. arXiv preprint arXiv:2211.15661

arXiv 2022
[4]

Bai, Y., Chen, F., Wang, H., Xiong, C., and Mei, S. (2023). Transformers as statisticians: Provable in-context learning with in-context algorithm selection. Advances in neural information processing systems , 36:57125--57211

2023
[5]

Bai, Y., Chen, F., Wang, H., Xiong, C., and Mei, S. (2024). Transformers as statisticians: Provable in-context learning with in-context algorithm selection. Advances in neural information processing systems , 36

work page 2024
[6]

Baum, L. E. and Eagon, J. A. (1967). An inequality with applications to statistical estimation for probabilistic functions of markov processes and to a model for ecology

work page 1967
[7]

D., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., et al

Brown, T., Mann, B., Ryder, N., Subbiah, M., Kaplan, J. D., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., et al. (2020). Language models are few-shot learners. Advances in neural information processing systems , 33:1877--1901

2020
[8]

Chiu, J., Deng, Y., and Rush, A. (2021). Low-rank constraints for fast inference in structured models. Advances in Neural Information Processing Systems , 34:2887--2898

work page 2021

Show all 50 references

[9]

Dai, D., Sun, Y., Dong, L., Hao, Y., Ma, S., Sui, Z., and Wei, F. (2022). Why can gpt learn in-context? language models implicitly perform gradient descent as meta-optimizers. arXiv preprint arXiv:2212.10559

2022 arXiv
[10]

Dedieu, A., Gothoskar, N., Swingle, S., Lehrach, W., L \'a zaro-Gredilla, M., and George, D. (2019). Learning higher-order sequential structure with cloned hmms. arXiv preprint arXiv:1905.00507

2019 arXiv
[11]

Dong, Y. et al. (2023). A survey of in-context learning: Recent progress and future directions. arXiv preprint arXiv:2301.00234

2023 arXiv
[12]

Dubey, A., Jauhri, A., Pandey, A., Kadian, A., Al-Dahle, A., Letman, A., Mathur, A., Schelten, A., Yang, A., Fan, A., et al. (2024). The llama 3 herd of models. ArXiv preprint , abs/2407.21783

2024 arXiv
[13]

Fan, J., Wang, Z., Yang, Z., and Ye, C. (2023). Provably efficient high-dimensional bandit learning with batched feedbacks. arXiv preprint arXiv:2311.13180

2023 arXiv
[14]

Felzenszwalb, P., Huttenlocher, D., and Kleinberg, J. (2003). Fast algorithms for large-state-space hmms with applications to web usage analysis. Advances in neural information processing systems , 16

2003
[15]

S., and Valiant, G

Garg, S., Tsipras, D., Liang, P. S., and Valiant, G. (2022). What can transformers learn in-context? a case study of simple function classes. Advances in Neural Information Processing Systems , 35:30583--30598

2022
[16]

Guo, J., Li, Z., Wang, H., Wang, M., Yang, Z., and Zhang, X. (2023a). Provably efficient representation learning with tractable planning in low-rank pomdp. In International Conference on Machine Learning , pages 11967--11997. PMLR

2023
[17]

Guo, T., Hu, W., Mei, S., Wang, H., Xiong, C., Savarese, S., and Bai, Y. (2023b). How do transformers learn in-context beyond simple functions? a case study on learning with representations. arXiv preprint arXiv:2310.10616

2023 arXiv
[18]

L., Fard, M

Hamilton, W. L., Fard, M. M., and Pineau, J. (2013). Modelling sparse dynamical systems with compressed predictive state representations. In International Conference on Machine Learning , pages 178--186. PMLR

2013
[19]

M., and Zhang, T

Hsu, D., Kakade, S. M., and Zhang, T. (2012). A spectral algorithm for learning hidden markov models. Journal of Computer and System Sciences , 78(5):1460--1480

2012
[20]

Jiang, H. (2023). A latent space theory for emergent abilities in large language models. arXiv preprint arXiv:2304.09960

2023 arXiv
[21]

Kulesza, A., Jiang, N., and Singh, S. (2015). Spectral learning of predictive state representations with insufficient statistics. In Proceedings of the AAAI Conference on Artificial Intelligence , volume 29

2015
[22]

Lin, L., Bai, Y., and Mei, S. (2023). Transformers as decision makers: Provable in-context reinforcement learning via supervised pretraining. arXiv preprint arXiv:2310.08566

2023 arXiv
[23]

Liu, A., Feng, B., Xue, B., Wang, B., Wu, B., Lu, C., Zhao, C., Deng, C., Zhang, C., Ruan, C., et al. (2024). Deepseek-v3 technical report. arXiv preprint arXiv:2412.19437

2024 arXiv
[24]

T., Goel, S., Krishnamurthy, A., and Zhang, C

Liu, B., Ash, J. T., Goel, S., Krishnamurthy, A., and Zhang, C. (2022a). Transformers learn shortcuts to automata. arXiv preprint arXiv:2210.10749

2022 arXiv
[25]

Liu, Q., Chung, A., Szepesv \'a ri, C., and Jin, C. (2022b). When is partially observable reinforcement learning not scary? In Conference on Learning Theory , pages 5175--5220. PMLR

2022
[26]

B., and Ma, T

Mahankali, A., Hashimoto, T. B., and Ma, T. (2023). One step of gradient descent is provably the optimal in-context learner with one layer of linear self-attention. arXiv preprint arXiv:2307.03576

2023 arXiv
[27]

Min, S. et al. (2022). Rethinking the role of demonstrations: What makes in-context learning work? In EMNLP

2022
[28]

Nichani, E., Damian, A., and Lee, J. D. (2024). How transformers learn causal structure with gradient descent. arXiv preprint arXiv:2402.14735

2024 arXiv
[29]

Rabiner, L. R. (1989). A tutorial on hidden markov models and selected applications in speech recognition. Proceedings of the IEEE , 77(2):257--286

1989
[30]

E., Giryes, R., Suzuki, T., Blondel, M., and Peyr \'e , G

Sander, M. E., Giryes, R., Suzuki, T., Blondel, M., and Peyr \'e , G. (2024). How do transformers perform in-context autoregressive learning? arXiv preprint arXiv:2402.05787

2024 arXiv
[31]

Siddiqi, S., Boots, B., and Gordon, G. (2010). Reduced-rank hidden markov models. In Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics , pages 741--748. JMLR Workshop and Conference Proceedings

2010
[32]

Siddiqi, S. M. and Moore, A. W. (2005). Fast inference and learning in large-state-space hmms. In Proceedings of the 22nd international conference on Machine learning , pages 800--807

2005
[33]

M., Gordon, G

Song, L., Boots, B., Siddiqi, S. M., Gordon, G. J., and Smola, A. (2010). Hilbert space embeddings of hidden markov models

2010
[34]

Su, J., Ahmed, M., Lu, Y., Pan, S., Bo, W., and Liu, Y. (2024). Roformer: Enhanced transformer with rotary position embedding. Neurocomputing , 568:127063

2024
[35]

M., Hauth, A., et al

Team, G., Anil, R., Borgeaud, S., Wu, Y., Alayrac, J.-B., Yu, J., Soricut, R., Schalkwyk, J., Dai, A. M., Hauth, A., et al. (2023). Gemini: a family of highly capable multimodal models. arXiv preprint arXiv:2312.11805

2023 arXiv
[36]

Touvron, H., Lavril, T., Izacard, G., Martinet, X., Lachaux, M.-A., Lacroix, T., Rozière, B., Goyal, N., Hambro, E., Azhar, F., Rodriguez, A., Joulin, A., Grave, E., and Lample, G. (2023). Llama: Open and efficient foundation language models. arXiv Preprint

2023
[37]

D., Kallus, N., and Sun, W

Uehara, M., Sekhari, A., Lee, J. D., Kallus, N., and Sun, W. (2022). Provably efficient reinforcement learning in partially observable dynamical systems. Advances in Neural Information Processing Systems , 35:578--592

2022
[38]

Uehara, M., Zhang, X., and Sun, W. (2021). Representation learning for online and offline rl in low-rank mdps. arXiv preprint arXiv:2110.04652

2021 arXiv
[39]

and De Moor, B

Van Overschee, P. and De Moor, B. (1995). A unifying theorem for three subspace system identification algorithms. Automatica , 31(12):1853--1864

1995
[40]

Von Oswald, J., Niklasson, E., Randazzo, E., Sacramento, J., Mordvintsev, A., Zhmoginov, A., and Vladymyrov, M. (2023). Transformers learn in-context by gradient descent. In International Conference on Machine Learning , pages 35151--35174. PMLR

2023
[41]

Wang, L., Cai, Q., Yang, Z., and Wang, Z. (2022). Embed to control partially observed systems: Representation learning with provable sample efficiency. arXiv preprint arXiv:2205.13476

2022 arXiv
[42]

Wang, X., Zhu, W., and Wang, W. Y. (2023). Large language models are implicitly topic models: Explaining and finding good demonstrations for in-context learning. arXiv preprint arXiv:2301.11916 , page 3

2023 arXiv
[43]

Wei, J. et al. (2022). Emergent abilities of large language models. arXiv preprint arXiv:2206.07682

2022 arXiv
[44]

Wu, D., He, Y., Cao, Y., Fan, J., and Liu, H. (2025). Transformers and their roles as time series foundation models. arXiv preprint arXiv:2502.03383

2025 arXiv
[45]

M., Raghunathan, A., Liang, P., and Ma, T

Xie, S. M., Raghunathan, A., Liang, P., and Ma, T. (2021). An explanation of in-context learning as implicit bayesian inference. arXiv preprint arXiv:2111.02080

2021 arXiv
[46]

Ye, C., Xiong, W., Gu, Q., and Zhang, T. (2023). Corruption-robust algorithms with uncertainty weighting for nonlinear contextual bandits and markov decision processes. In International Conference on Machine Learning , pages 39834--39863. PMLR

2023
[47]

Ye, T., Xu, Z., Li, Y., and Allen-Zhu, Z. (2024). Physics of language models: Part 2.1, grade-school math and the hidden reasoning process. In The Thirteenth International Conference on Learning Representations

2024
[48]

Zhan, W., Uehara, M., Sun, W., and Lee, J. D. (2022). Pac reinforcement learning for predictive state representations. arXiv preprint arXiv:2207.05738

2022 arXiv
[49]

Zhang, T. (2023). Mathematical Analysis of Machine Learning Algorithms . Cambridge University Press

2023
[50]

Zhong, H., Xiong, W., Zheng, S., Wang, L., Wang, Z., Yang, Z., and Zhang, T. (2022). Gec: A unified framework for interactive decision making in mdp, pomdp, and beyond. arXiv preprint arXiv:2211.01962

2022 arXiv

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.

[1] [1]

L., Almeida, D., Altenschmidt, J., Altman, S., Anadkat, S., et al

Achiam, J., Adler, S., Agarwal, S., Ahmad, L., Akkaya, I., Aleman, F. L., Almeida, D., Altenschmidt, J., Altman, S., Anadkat, S., et al. (2023). Gpt-4 technical report. arXiv preprint arXiv:2303.08774

arXiv 2023

[2] [2]

Agarwal, A., Kakade, S., Krishnamurthy, A., and Sun, W. (2020). Flambe: Structural complexity and representation learning of low rank mdps. Advances in neural information processing systems , 33:20095--20107

work page 2020

[3] [3]

Aky \"u rek, E., Schuurmans, D., Andreas, J., Ma, T., and Zhou, D. (2022). What learning algorithm is in-context learning? investigations with linear models. arXiv preprint arXiv:2211.15661

arXiv 2022

[4] [4]

Bai, Y., Chen, F., Wang, H., Xiong, C., and Mei, S. (2023). Transformers as statisticians: Provable in-context learning with in-context algorithm selection. Advances in neural information processing systems , 36:57125--57211

2023

[5] [5]

Bai, Y., Chen, F., Wang, H., Xiong, C., and Mei, S. (2024). Transformers as statisticians: Provable in-context learning with in-context algorithm selection. Advances in neural information processing systems , 36

work page 2024

[6] [6]

Baum, L. E. and Eagon, J. A. (1967). An inequality with applications to statistical estimation for probabilistic functions of markov processes and to a model for ecology

work page 1967

[7] [7]

D., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., et al

Brown, T., Mann, B., Ryder, N., Subbiah, M., Kaplan, J. D., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., et al. (2020). Language models are few-shot learners. Advances in neural information processing systems , 33:1877--1901

2020

[8] [8]

Chiu, J., Deng, Y., and Rush, A. (2021). Low-rank constraints for fast inference in structured models. Advances in Neural Information Processing Systems , 34:2887--2898

work page 2021