- Rating
- 2
- Confidence
- 3
- Informativeness
- 1
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
The paper shows that having a few soft tokens allows a transformer to represent weighted majority and tabular q learning. It then implements these in very small transformers using backprop-through-time finding the learned recurrent transformers achieve good performance. Weighted majority performance is compared with existing large scale transformers showing that a specialized transformer with a recurrent state can perform well. Other experiments compare with a discrete one-token transformer showing better performance with the modified transformer.
Critical strengths
The proofs appear correct and the experimental results are believable.
Critical weaknesses
The implications of this paper appear primarily informational since the dependence on backprop through time makes the algorithm difficult to parallelize and no approach to a scalable algorithm is offered.
There's significant missing related work about existing similar implementation in Recurrent Memory Transformer (Bulatov, Kuratov, Burtsev, NeurIPS 2022) and related literature. People have also thought about recurrent state as an online learning algorithm. See for example the test time training work several of which are referenced here https://yueatsprograms.github.io/ttt/home.html . Note also that this is spelled out in the title of the Longhorn work which is cited but not discussed in relation to the thesis. There is prior work on getting transformers to explore by creating summaries in Krishnamurthy, Harris, Foster, Zhang & Slivkins, “Can Large Language Models Explore In-Context?” (NeurIPS 2024). Another very related one is: Lin, Bai, & Mei, Transformers as Decision Makers: Provable In-Context RL via Supervised Pretraining (ICLR 2024)
In the end, I'm left with relatively little to consider new here since similar methods have been tested and similar conclusions drawn previously. (1) Recurrent state is learnable, as per RMT and TTT papers. (2) Recurrent state can function as online learning per Longhorn. (3) Summaries help LLMs, as per the Krishnamurthy et al paper. And of course trained transformers also don't have a regret guarantee. The strongest point seems to be the constructions which are nice but seem unsurprising.
Questions for authors
How many seeds were used in conducting the Q-learning experiments and what was the variance across seeds?
3 comments
Response to Reviewer pQt5 (part 2)
Related work.
- Recurrent Memory Transformer. RMT shows that memory tokens carried across segments are an effective architecture. We give an explicit realization of WMA and Q-learning (state encoding, reads, updates, and proofs of correspondence), and we test which statistics training recovers. The write rule also matters: an RMT-style overwrite () is unstable across seeds on our task (regret 15.9 and 137.5 at ), while our additive write is stable (Fig. 12).
- TTT and Longhorn. These develop online-learning mechanisms as sequence layers. TTT runs learning updates on an inner model's fast weights; Longhorn derives an SSM transition from an online associative-recall objective. We show how standard attention and MLP computations, plus persistent context writes, implement the predictions and feedback updates of specific decision-making algorithms. The shared online-learning view motivates the connection, but the mechanisms, target algorithms, and guarantees differ. We now discuss Longhorn in this context.
- Lin, Bai & Mei. They construct transformers that run online RL algorithms and analyze supervised pretraining. In their setting, the whole interaction trajectory is the context (so length grows with ), and their constructions use ReLU attention. Ours carry out the online recurrence through softmax attention and persistent latent tokens whose number, dimension, and update depth don't depend on the horizon.
- Krishnamurthy et al. Their exploration setup feeds the model sufficient statistics computed outside it. Our note experiments ask the model to create and maintain its own summary, including a history-free setting where that summary is the only information passed between rounds. Using given statistics and testing whether a model builds and keeps them are different questions. Their setting is bandits; ours is full-information expert prediction.
In summary, each of the works above establishes one ingredient: recurrent memory is trainable, recurrent state can act as an online learner, and summaries help LLMs. Our contribution is to connect them with exact constructions and controlled experiments: a few continuous tokens suffice to run regret-minimization and RL algorithms with constant depth, and training without state supervision recovers that state when it is continuous. We believe this opens a principled direction for studying algorithm learning in transformers.
Seeds in Q-learning. We trained 3 seeds for the continuous and discrete versions; As we mention in Appendix 4.2.5, the teacher-forced agreement is 30%, and the -greedy returns are 35% for , 38% at , 44% at , and 47% at .
Of course, we would be happy to answer any further questions you may have for us, and if you find that we have addressed all your concerns, we hope you will consider raising your score.
Thank you,
Authors
Thanks for your response. I'm planning to stick with my review, because I still do not find the results surprising or impactful enough that I would recommend it to other folks.
Response to Reviewer pQt5 (part 1)
Dear Reviewer pQt5,
We thank you for your review. We address your concerns about novelty and scalability below, and we have expanded the related work in the revised PDF, which we will submit in the next few hours.
What we see as new. Our main result is a specific computational one: a fixed-depth transformer can run classical online decision-making algorithms by keeping their state in a constant number of continuous context tokens, with parameters independent of the horizon. Theorems 3.1 and 4.1 give explicit two-layer constructions:
We think this is less expected than it may look, for two reasons:
Backpropagation through time. Training cost and run-time cost are separate questions. Our constructed transformers need no training at all since their weights are given in closed form. At runtime, both the constructed and the trained models only run forward passes. Per-round work and state size don't depend on the horizon, giving O(T) total work without keeping the history. Nonetheless, we agree that training is sequential, like any recurrent memory (RMT included), and a parallel training method is a universal open problem.
Regret guarantees. We agree that trained models do not inherit MW's worst-case guarantee, and we mentioned this explicitly in the paper, stating that it tracks the average-case distribution. They are trained on in-distribution log-loss, so they are optimized for the training distribution, not for adversarial sequences. An adaptive adversary drives the trained model's regret to 47 within 500 rounds, versus MW's ln4 bound (Fig. 13). Our claims about trained models are therefore distributional: in distribution, they achieve low regret and closely track the reference learners (e.g., within 0.0015 of MW's predicted probabilities on data where MW is Bayes-optimal, Table 1). The worst-case guarantees belong to the constructions of Theorems 3.1 and 4.1, which implement WMA and Q-learning exactly.