Learning Randomized Algorithms with Transformers
Johannes von Oswald, Seijin Kobayashi, Yassir Akram, Angelika Steger
Abstract
Randomization is a powerful tool that endows algorithms with remarkable properties. For instance, randomized algorithms excel in adversarial settings, often surpassing the worst-case performance of deterministic algorithms with large margins. Furthermore, their success probability can be amplified by simple strategies such as repetition and majority voting. In this paper, we enhance deep neural networks, in particular transformer models, with randomization. We demonstrate for the first time that randomized algorithms can be instilled in transformers through learning, in a purely data-and objective-driven manner. First, we analyze known adversarial objectives for which randomized algorithms offer a distinct advantage over deterministic ones. We then show that common optimization techniques, such as gradient descent or evolutionary strategies, can effectively learn transformer parameters that make use of the randomness provided to the model. To illustrate the broad applicability of randomization in empowering neural networks, we study three conceptual tasks: associative recall, graph coloring, and agents that explore grid worlds. In addition to demonstrating increased robustness against oblivious adversaries through learned randomization, our experiments reveal remarkable performance improvements due to the inherently random nature of the neural networks' computation and predictions.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
1 top-tier paper has cited it since. Know what they found before your reviewers do.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
- MesaNet: Sequence Modeling by Locally Optimal Test-Time Training cites Language Models are Few-Shot Learners
- MesaNet: Sequence Modeling by Locally Optimal Test-Time Training cites Transformers Learn In-Context by Gradient Descent
- Resurrecting Recurrent Neural Networks for Long Sequences cites Language Models are Few-Shot Learners
- Transformers Learn In-Context by Gradient Descent cites Language Models are Few-Shot Learners
- Transformers Learn In-Context by Gradient Descent cites What Can Transformers Learn In-Context? A Case Study of Simple Function Classes
- What Can Transformers Learn In-Context? A Case Study of Simple Function Classes cites Language Models are Few-Shot Learners
Cited by top-tier papers1
Builds on16
- Language Models are Few-Shot LearnersTom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah et al.NeurIPS 2020 · 64,255 citations
- Chain-of-Thought Prompting Elicits Reasoning in Large Language ModelsJason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma et al.NeurIPS 2022 · 22,562 citations
- What Can Transformers Learn In-Context? A Case Study of Simple Function ClassesShivam Garg, Dimitris Tsipras, Percy Liang, Gregory ValiantNeurIPS 2022 · 883 citations
- Transformers Learn In-Context by Gradient DescentJohannes von Oswald, Eyvind Niklasson, Ettore Randazzo, João Sacramento et al.ICML 2023 · 729 citations
- Resurrecting Recurrent Neural Networks for Long SequencesAntonio Orvieto, Samuel L. Smith, Albert Gu, Anushan Fernando et al.ICML 2023 · 474 citations
Related papers
- Algorithmic Capabilities of Random TransformersZiqian Zhong, Jacob AndreasNeurIPS 2024 · 23 citations
- TeachAugment: Data Augmentation Optimization Using Teacher KnowledgeTeppei SuzukiCVPR 2022 · 57 citations
- Transformers learn to implement preconditioned gradient descent for in-context learningKwangjun Ahn, Xiang Cheng, Hadi Daneshmand, Suvrit SraNeurIPS 2023 · 324 citations
- Network Randomization: A Simple Technique for Generalization in Deep Reinforcement LearningKimin Lee, Kibok Lee, Jinwoo Shin, Honglak LeeICLR 2020 · 191 citations
- Gradient Smoothing: Coupling Layer-wise Updates for Improved OptimizationHaoming Meng, Anton Sugolov, Vardan PapyanICML 2026
