Learning Randomized Algorithms with Transformers
Authors: Johannes von Oswald
Seijin Kobayashi
Yassir Akram
Angelika Steger
Venue: ICLR 2025 Oral (2025)
Keywords: Randomized algorithms
Learning under adversarial losses
Adversarial robustness
In-context learning algorithms
Primary area: other topics in machine learning (i.e., none of the above)

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.

Published as a conference paper at ICLR 2025
LEARNING RANDOMIZED ALGORITHMS WITH TRANSFORMERS
Johannes von Oswald*1 Seijin Kobayashi Yassir Akram" Angelika Steger²
1 Paradigms of Intelligence Team, Google
Department of Computer Science, ETH Zürich
Equal contribution, order determined randomly
{ jvoowald, seijink ( @google. com, (yakram, asteger)@ethz.
ABSTRACT
Randomization is powerful tool that endows algorithms with remarkable prop- erties. For instance, randomized algorithms excel adversarial settings, often surpassing the worst-case performance of deterministic algorithms with large gins. Furthermore, their success probability can be amplified by simple strategies such as repetition and majority voting. In this paper, we enhance deep neural net- works, in particular transformer models, with randomization. We demonstrate for the first time that randomized algorithms can be instilled in transformers through learning, in purely data- and abjective-driver 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.
INTRODUCTION
Randomization is inherent to nature and an important ingredient in numerous scientific fields. In computer science, for example, randomness can powerful theoretical and practical tool to design algorithms (Papadimitriou, 1994). However, understanding how, if, and when randomization can be beneficial for algorithms is neither obvious nor intuitive, Nevertheless, randomness by now a well-established and widely used concept to design powerful and often strikingly simple algorithms (Motwani & Raghavam 1995 Rabin 1980). In particular, randomization is known to be crucial to obtain algorithms performing well in theoretcal adversarial settings, cf. pack-papr-sscisorrs simple example. Here, randomization is essential as otherwise players will get exploited from clever opponent. Within algorithmic design, furthermore, randomized algorithms are often surprisingly simple to implement. While base versions often have non-satisfactory high failure probability, simple repetition and majority voting strategies typically allow enhance overall success probability drastically at comparably low cost, see our illustrative example below and Appendix E for short background. In this paper we combine the power of randomization and deep learning, in particular transformer models Vaswani et al. (2017), and show that powerful randomized algorithms within transformers are discovered when optimized on adversarial objectives. These transformer algorithms significantly more robust against oblivious adversaries and dramatically outperform deterministic strategies through majority voting.
To set the stage, let's consider the example of associative recall to build up our intuition, illustrated in Figure Assume a simple computer system with memory size M d bits needs to save vectors, each of d bits. These vectors denoted as values e; [Ua..... vtal {0. 1)d which are associated with a unique one-hot binary key k; = [ka...., kav] with k, = Li=j. The aim of the computer system is to retrieve the correct value vector if queried with some key ky (ki,...;kay kN) after

---

Published as a conference paper at ICLR 2025
B
[s(ed)))
Fraction inputs
correct incornect for every lipue
Froction on of imputs
Success %
probubiility
linear transformer
ampliiicctioo on
with finite memory M < N
Notvarro succcrno roke every
(Ah, 91, sood)
(Kyx sood)
Success %
Success %
Sequence length
Deeemiieticc
Handomized
Hand-majorty (6)
Hand-ngjoiiy (30)
Figure 1: Solving associative recall tasks- the randomized way. A): A causal transformer model, with linear self-attention layers, is trained to remember N value vectors each associated with unique key. Given finite memory of size M < N, the model needs to decide which data to memorize in order to return the correct value when queried with some k, An algorithm that deterministically chooses what to remember will perform poorly as simple adversarial strategies will break retrieval. On the other hand, randomly deciding what to store protects the algorithm against such worst-case scenarios. To have a transformer learn such randomized strategy train it with an adversarial objective and furthermore, diverge from usual machine learning setups and provide randomness, denoted as a seed, as an additional input to the model. B): Histogram showing the fraction of possible inputs, all of length N = 20, with varying recall success rates. Left: We train two different models: 1) deterministic one where we fix the input seed and randomized one with varying input seed. While the deterministic model consistently fails on some fraction of the inputs, the randomized model stores in memory varying parts of the sequence leveraging the provided seed, thus succeeding with non-zero probability on all possible recall tasks. Right: At inference time, majority voting can be used on the randomized model evaluated on several seeds, thus amplifying the success rate. Enough seeds leads to optimal recall. C): Recall success rate for worst-case sequences of each model when trained on various input lengths. For larger sequence lengths, the deterministic model fails to recall on adversarial inputs and the worst case success rate thus drops to zero. On the other hand, randomized models have a non-zero success rate on all inputs. Strikingly, when amplifying the success probability with majority voting, the randomized model succeeds in recalling virtually all inputs.
observing the whole sequence of N value vectors. Crucially, if the memory of the system is not large enough i.. M < N, the system needs to decide which data to store in memory and which data to disregard, assuming no compression is feasible. This problem is variant of the well-known paging problem in computer science (Sleator & Tarjan 1985a) for which randomized solutions exist, see Appendix E.3 for short description. The problem also well-studied problem for transformers (Vaswani et al.] (2017) and transformer architecture variants with the goal to assess retrieval capabilities (Schlag et al. 202T Arora al. 2023 Jelassi al. 2024).
Let us first assume that the computer system or transformer implements deterministic strategy. For example, always saves the first AM elements in the sequence until memory capacity reached. Given this knowledge, there is simple adversarial strategy that breaks retrieval: query the system with keys k, where > M. Note that similar retrieval failure can be observed in large-scale language models where this test is known as finding a needle in haystack (Liu et al.) (2023b). Consider now that the transformer model is given an additional input, namely a random seed, and that based on the seed, it chooses uniformly at random which data to store. Then, every query will break retrieval (only) with probability 1 - N. Therefore, in stark contrast to a deterministic system, there exists no input sequence which the system will do specifically bad. In particular, make the system fail consistently. In other words: randomization improves worst-case behavior, see Figure B & C. Strikingly, randomization can enhance success rates of our trained transformers by repetition. Simply taking the majority vote among m predictions computed on different seeds boosts performance to perfect success rate far beyond the deterministic transformer counterpart despite the same network capacity and training objective.
M.
adversarial strategy can
2 THEORETICAL CONSIDERATIONS
We start by presenting some well-known theoretical results providing a more thorough description of when and why randomized algorithms can be beneficial compared to deterministic ones. This will lead us define a simple training objective, closely related robust optimization, that enforces the
2

---

Published as a conference paper at ICLR 2025
implementation of powerful randomized algorithms within deep neural networks like transformers" We then verify experimentally, in the following section, that this is indeed the case and show that transformer models do implement deep randomized algorithms in practice after training.
To this extent, we introduce some notation and definitions. We denote our model, in this paper a parametrized transformer, by Ao(2, r) with input X and some randomness (or seed) from set R. We will fix distributions over the input space X' and the seeds R of the transformer model. Specifically, we define two random variables X (over 2) and R (over R). For any parameter a + Aa R) is a randomized transformer model which we also call randomized transformer algorithm. We provide the transformer models in the following with a random seed encoding (RSE), similar to positional encodings common in transformer models. This encoding provides the randomness to the transformer and usually a vector of noise, such as random bits, which we concatenate to the input tokens. Note that optimization can therefore ignore R. by setting, for example, the appropriate weights in the first layer to zero resulting When there exists x E X such that the function + Ae(x, is not constant, we say that our transformer is properly random. For any fixed input x E X and r E R, the loss determined by L(x, Ao(2,,)) > 0. For notational simplicity, we will drop the dependence of the loss in the following whenever is clear from the context. The performance of the randomized transformer on the input x is its expected loss, i.e. (Ao R)]]. We now review well-known results from the randomized algorithms literature and analyze when randomization is advantageous compared to determinism and vice versa. This analysis will lead to an optimization procedure from which we expect that the random source in the transformer's ' input is leveraged to reach lower loss values.
deterministic transformer.
2.1 EXCESSIVE MODEL CAPACITY WILL NOT ENFORCE RANDOMNESS
A first necessary condition for randomness being beneficial is that the model capacity doesn't 't allow to achieve optimal performance without using randomness i.e. ignoring it in the input. More precisely, if there exists 0, r E R that perfectly fits the data, i.e. such that (I, all X, then randomness has no incentive to be leveraged. Whether the optimization algorithm will discover this 0 is however not guaranteed. We now continue by showing that commonly used expected risk minimization or empirical risk, in practice, should not lead to randomization.
arg min, L(x, y) for
2.2 RANDOMIZATION IS NOT BENEFICIAL IN EXPECTATION
To see that randomization is not beneficial in expectation, and therefore unlikely to be leveraged by optimization to reach lower loss, we discuss Yao's Minimax Principle (Yao) 1977). This is pivotal concept across various domains like game theory and randomized algorithms Neumann (928)). In the latter, it provides a framework understand how randomized algorithms fare in adversarial environments. It can be articulated as follows, for any random variables X and R over X' and R:
min ([L(AA(X,r)) L =[ R)) & max [[L(Ao(>,, RR))
rER
ZEX
More intuitively, given a fixed distribution over our dataset, Yao's 's Minimax Principle shows:
There always exists a deterministic algorithm performing, in expectation over the data, at least as well as the randomized algorithm A(,, The process of extracting a particular seed that performs as well as the randomized algorithm is called derandomization. There is however no general efficient recipe for this task.
1st inequality:
1st and 2nd inequality: Any randomized algorithm will inevitably perform worse on some input than the average performance of the best deterministic algorithm.
At first glance, this principle might seem to nullify any advantage of randomized algorithms over deterministic ones. However, the above principle applies the setting where we assume distribution over input data on which we want to perform well on expectation in particular, when the objective that of the empirical risk minimization (ERM) on fixed dataset. Therefore, we recognize that the most common optimization strategy in deep learning is not expected to show benefits from
We take the liberty throughout this paper to the (transformer) algorithm and model interchangeably.
3

---

Published as a conference paper at ICLR 2025
randomization. In fact, will show empirically that transformers that trained ERM do not have random predictions when varying т, i.c. ERM does not lead to properly randomized transformers.
2.3 RANDOMIZATION CAN BENEFICIAL IN ADVERSARIAL SETTINGS.
As discussed, randomness does not provide advantages when considering expected performance on an arbitrary distribution over data. This picture changes drastically when considering adversarial, in particular min-max settings. To understand these settings, we first define oblivious adversary:
Definition 1 (Oblivious adversary). An oblivious adversary possesses complete knowledge of the agent's 's algorithm but lacks control over the randomness.
In our context, such an adversary knows the algorithm A and R (the distribution of the seeds) but does not know the outcome of R advance. However, it can choose the distribution over the input and therefore restrict the input to the most "difficult" instances in X. For example, in rock-paper-scissony it would constantly play paper, if it determines that the opponent deterministically chooses rock. Unlike in other more game-theoretical settings, this adversary isn't a real opponent but rather thcoretical construct: the agent seeks in fact to ensure a favourable outcome irrespective of the input. This setting is closely linked to min-max strategies (1945): agent facing oblivious adversary aims to optimize the min-max loss, defined as:
Definition (Min-max loss). The min-max objective is the minimization of the following loss:
L (^) max (2
(2)
Proposition 1. [Randomization can be beneficial worst-case scenarios] Assume that X compact set of Rd for some d, and that L is continuous. Furthermore assume that there exist parameter 8* and a set of random seeds (ri)iSiSN RN such that for each i
max L(Ag- (x,
min max L(A, and Marg max L(Ag- (2' r:)) 0. 0,r ZEX
(3)
Then there exists randomized model with strictly smaller loss LA than any deterministic model.
We provide the proof in Appendix A.1 Note that the above subsumes the more straightforward argument that no randomization expected if the model can the data perfectly. Intuitively, the proposition shows that whenever there several possible optimal functions for L that can be implemented within our model class, such that there is no input x which adversarial to all them, then it is more beneficial to have distribution over such functions than to deterministically encode single one.
As argued by Rice et al. 2021). in the context of robust optimization it is often advantageous to relax the strict adversary of equation 2 by optimizing the q noror of the expected loss the model distribution for i.e.
min (²) min E| R)
Here, the conditional expectation (XL [X] is the averaged loss over R. The outer expecta- tion is over inputs. Note that with 1, L L and with
obtain L LA.
2.4 OUR TRAINING OBJECTIVE.
Based on the previous description, summarized in Proposition I of when randomization is beneficial, we propose the following practical training objective:
((A(()))))))))) 2/4
arg min (0) arg min #
Note that this biased approximation of equation 4 Although approximating the g-norm by such Monte Carlo sampling in practice is known to slowly converge to the expected value, see Rice et al. (202)) stick to it here and leave further investigations of refined sampling to future work.
4

---

Published as a conference paper at ICLR 2025
In our training objective, introduce, compared to the common stochastic approximation of the expected loss over the data, two new hyperparameters namely m, the number of random seeds we consider, and q. We will analyze the role of these in our experimental results section, focussing the sensitivity of q. as it shifts between ERM and adversarial training.
We stress that finding adversarial examples compute the loss in equation 2 is difficult, especially in settings where computing gradients poses challenges such as in language with discrete inputs or in reinforcement learning (RL). Therefore, the relaxation of q < 3o approximating the min-max adversary leads to a practical loss for which no explicit adversary is computed. Finally, note that the adversarial loss upper bounds the expected loss. i.e.. (A( 2 C (0). Nevertheless it not expected that optimizing L (0) will lead to better (6) compared to when optimizing L (P()) directly.
In the next section we show how can turn the above theoretical considerations into practice and present experimental results where optimization leads to randomized algorithms in transformers.
3 EXPERIMENTAL RESULTS
Before we present experimental results, we first describe an evaluation protocol to validate experi- mentally that
1. the algorithm implemented by transformer model after optimizing on L" for certain and m, induces randomization: The distribution of the random variable Ag(r, R) does not collapse i.e. is not degenerate. Therefore r - Ap(2; (z, r) is not constant.
2. the randomized transformer algorithm found is performing, compared to baselines described below, better on data that is adversarially chosen.
3. training on expected risk _ will not lead to randomization i.e. now r + Ae(x, r) is constant and does not possess the associated robustness against adversaries.
Finally, we investigate the robustness and scaling of proper randomization with respect the novel hyperparameters m and q. In order to provide the results a structured way, we present an evaluation protocol which follow when discussing our empirical findings in the following.
3.1 EVALUATION PROTOCOL AND BASELINES
In most of our experiments, we compare the following four transformer models:
1. A E ERM, which is by definition deterministic. The transformer is + Ap(x, ro) where ro is static seed selected at the beginning of training from R. The same ro is used for evaluation. The transformer is thus trained on C,F (0) E (A, ro)]..
rg trained on expected loss, single seed: This is the transformer baseline, trained on
2. A% trained on relaxed adversarial loss, single seed: This is the same transformer as above. but trained on the (relaxed) adversarial loss Cj, (0) [[L(As (o) 19 for some parameter q. In practice, we approximate the objective using equation all i. This transformer is closely related to robust optimization e.g. distributionally robust optimization (DRO), see related works section.
5 where r; = ro for
3. K trained on expected loss, multi seed: This transformer model given as input random seed r which is sampled from R, but trained on ERM. Concretely, the transformer is trained on (0) = E (L R.)].
4. A% trained on relaxed vdvesaaiaal loss, multi seed: This our transformer model of main interest trained on our proposed objective in equation 5 This is the model we expect to randomize itself and the focus of our investigation.
Given these models, we evaluate them in the following ways:
1. For A and AG the loss L(Aa(2, ro)) for an input x is computed by using the same seed To which was used for training. In all our experiments, Ag(x, ra) parametrizes discrete decision to take, such as the recalling of bits in the associative recall task (Section 3.2). the coloring of vertices in the graph coloring task (Section 3.3), or the action to take in
5

---

Published as a conference paper at ICLR 2025
the grid world task (Section 3.4) In all these cases, Ao(2,ro) produces a D D-dimensional vector where D is the number of possible discrete decisions. We may train the model by interpreting the prediction as parametrizing e.g. categorical distribution. To compute the success percentage however, we record whether the argmax of the prediction Ao(r, ro) is correct not. Furthermore, we also report the success percentage by sampling from the distribution parametrized by A(r, ro), in the case the loss L allows for such interpretation (e.g. L the cross entropy loss). We denote these by A E -sampled and to -sampled, resp.
2. For A& and A%g. the loss for an input æ is computed as the expected loss over random seeds, i.e. [AL((g R. For the success percentage given an input, we record the fraction of seeds r for which the argmax of the prediction Ag(x, r) is correct. Furthermore, we report the success rate of majority voting of the transformer predictions across seeds, which denote by A majoritt and A A% - resp. See Appendix F.1.1 for more details.
Finally, we report the performance of these models when averaging over the input distribution (Average) and measure the performance on udversarial inputs by reporting the 95th percentile performance values over the input distribution 1955h--eereetile We use the common transformer architecture and variations throughout our experiments; more details in Appendix A.2
3.2 RANDOMIZED TRANSFORMERS SOLVE ASSOCIATIVE RECALL
We start by revisiting the associative recall task which we introduced in the introduction, cf. Fig- ure 1 Here we train transformers with linear self-attention layers i.e. we replace the stan- dard softmax operation with the identity func- tion E' + E' + (QK* @ M)V W. This ar- chitecture change allows the transformer to be regarded as a fast-weighr programmer [Schmid]
0.12
1.0-
Variance
Averige 0p--paroinnl
Fraction of inputs
08-
32
0.08
816-
Predictive
11005
0.01
0.4
012
huber (1992): [Schlag et al. (202I) where an in- ternal fixed size memory matrix can be over-
0.00
10'
0.0
No
160
Success %
written with incoming information. Studying memory allocation issues with transformer vari-
Figure 2: Left: Variance of the predictive prob- ability conditioned on the input sequence, w.r.t. increasing q: Larger leads to randomized trans- former models with non-zero output variance over the seeds, with phase transition around q 16. Right: Histogram showing the fraction of inputs, all of length N 20, with varying recall success rates, when training A% with various q. For ERM training i.e. g = 1, we see the transformer produc- ing essentially binary predictions, i.e.the predic- tions, over seeds r, are either correct or incorrect. For >> 1, we see randomization emerging, with non-zero success rate on all input for = 32.
ants has seen considerate interest recently (Gu &
Dao 2023 De et al. 2024 Orvieto al. 2023T
Arora et al. 2023] von Oswald et al., 20236;
Zucchet et al. 2024). We give more details
the tokenization and how we provide random- ness in Appendix B The transformer is provided with the inputs that are the co-be-remembered key and value pairs i.c. E [eo...... eN]] with e; [D;, his seed]. where iy is a binary vector of d bits v; = [rao..... ., vtal with bi E {0, }} and en [-, k; seed]. We train the model on the sum of binary cross-entropy (CE) between ground truth bits and transformer predictions: ([A,(E,r) r), vx) = E, CE(0,, Big). We report the performance of the different models, including when varying q and m, in Figure 2 and 3
We start by analyzing ERM trained transformers for which we do not expect randomization to emerge, ie. A = A%, A A?, with q = 1, and their variants, Figure 3A. All models perform similarly, concluding that ERM models are not benefiting from additional randomness, even when random seeds are provided. Furthermore, even transformers that could potentially leverage randomness, i.e. AE, collapse in their predictions, see Figure 2 where we show the collapsed predictive variance induced when varying seeds for AE. This behaviour changes when increasing 9. Indeed, when choosing for example g = 100, we observe that randomization emerges demonstrated by increased predictive variance and gradual, instead of bi-modal, success rate, see Figure 2 Performance wise, the randomized A% (blue) improves significantly on worst-case inputs and especially Aajmajority (green), performs almost optimally on all inputs, see Figure 3B. We denote A as "deterministic" in Figure [ where we show for illustrative purposes the performance of the 95th percentile.

---

Published as a conference paper at ICLR 2025
A
B
100
130
0.0
80
Success
00
Success
Loss
Loss
635
Sequence length
Sequence length
1/2
Average
05 percentlle
AC. sampled
Majooiiy
Figure 3: Associative recall analyses. A): Performance of models trained ERM does not improve when provided with additional seeds, ef. overlapping lines of A7, and A B): Models trained with objective (q 100) do exhibit drastic improvements, especially with majority voting, compared to models trained with a single fixed seed their input. C): Influence when training with different and m, measured on the loss with 9 1. First, models show gradual improvement when increasing with randomness emerging over certain threshold. Second, when fixing 100, outer right plot, observe already for small
improvements over the deterministic counterpart.
We conclude that training linear self-attention transformers to solve associative recall tasks instills randomized strategy inside the transformer which outperforms deterministic counterparts.
3.3 RANDOMIZED TRANSFORMERS CAN SOLVE GRAPH COLORING PROBLEMS
theoretical and practical tool to design powerful and strikingly simple algorithms, One prominent use case of randomized algorithms solving graph coloring problems, with the aim color the vertices of graph G (V, E) in such way that vertices connected by edges are colored differently. Randomized algorithm are particularly useful in distributed settings which each vertex can only see and talk its neighbors. See Appendix E.4 for detailed description. We consider the problem of 3-coloring cycles, see Figure While the problem per is trivial, the goal in the distributed setting to minimize the time/number of communication rounds until the coloring is found.
Randomization has numerous applications in combinatories
A
B
Falhure
CN
locally masked transformer
t
CN
(V11,eod)
(uny)
[sed
[seed2]
[seed3]
Figure 4: Transformers solving graph coloring problems. A): We study distributed vertex coloring problems cycles C, where every vertex can only communicate with its immediate neighbors. B): locally masked transformer, which can only attend to the immediate neighboring vertices on the graph by appropriate attention mask, has decide the vertex color. C): If the transformer realizes fixed mapping of vertex id e to a color, an adversary can provide an input permutation for which the transformer fails generate a correct coloring. However, when trained with our objective, the transformer model, to protect itself against this adversary. implements a randomized strategy. The coloring computed by the transformer for a fixed graph, now depends on the random seed and will fail in some and be correct in others. With the probability of being correct hopefully being large.
We consider N 10 vertices, each with unique from to N. Each task consists of the 3-coloring problem i.e. cycle drawn uniformly from the set of possible cycles with N vertices. A transformer input are tokens, each consisting vertices. The random noise is concatenated to each of these tokens, see Figure The adjacency matrix of the cycle translated into an attention mask the transformer, such that each vertex can only attend to its neighbors the cycle. No other information about the particular configuration of the cycle is given. Every token stream then outputs the distribution over its color. Details in App.
distinct N-dimensional 1-hot vector, representing the N
The objective is partial coloring loss, which is an upper bound of the probability of the model outputting an invalid coloring of the graph. Specifically, given all edges E of a given cycle, the loss is defined as: ElWrEr Ece P(C(u)) c))((((v) c) which upper bounds the quantity

---

Published as a conference paper at ICLR 2025
P(U (w,))E C(u) C(e))
where C(u) is the random variable assigning color to u, sampled from
A
B
0083
Average
Fraction of inputs
95th percentile
Success
Loss
4g
4
(403
21
Ag sampled
A% majority
9
Success
Figure 5: Graph coloring performance analyses. A): Performance of models trained on L for varying value of q. As q increases, 4% learns to leverage randomness implement randomized algorithm, inducing large improvements of worst-case performance compared to the deterministic counterpart A Furthermore, majority voting boosts performance close optimal performance (green). Both the average and percentile curves are computed over all possible cycles of size N=10, B): Influence of varying during training evaluated on the loss with q = After training with q clear advantage of the randomized model is observed. C): Histogram over all possible inputs, of the transformers success probability when varying q when training A%. When increasing q we observe non-zero success rate due to randomization.
For our experiments we choose the transformer depth and the task difficulty defined by N such that there cannot be enough communication between vertices to coordinate and return a valid coloring. A deterministic strategy may work a large fraction of possible cycles, but may fail the remainder. To investigate the effect of the adversarial loss on the emergence of proper randomness, we again train A%, and A% for varying adversarial strength q. We present our results in Figure 5 We see that at = 1 the performances of the various transformers are almost identical. In particular, despite having random source its disposition, both A% and A learn a degenerate transformer that is, for each input, either correct or incorrect for all seeds, ef plot on the right, 1. As g increases proper randomness emerges and, in particular, the performance of 4%2 mijaootrtt improves significantly close to 100% success probability. This signals that the transformer learned randomized algorithm, where each seed underfits different parts of the input space such that, on expectation, the transformer returns correct output for each input with relatively high probability. Intriguingly, A%, -sampled, despite leveraging randomness at the output, does not recover the same performance as the properly randomized transformer, even though the objective optimizes the predictive distribution. To conclude, we are able to show that powerful randomization emerges within transformers from first principles due to optimization in the graph coloring setting well.
3.4 RANDOMIZED TRANSFORMER AGENTS EXPLORE GRID WORLDS
A
B
Regect 20.0
Rogret 22.0
Regret 20.5
[Ryusstaal
environment
rolled-out transformer
*
t (().)))
seed
[sedd]]
[sod22]
[sedd3]
Figure 6: Transformer agents exploring grid worlds in-context. A): The transformer agent is trained to explore a simple grid efficiently and search for randomly placed treasure. B): The transformer agent's output provides the next action (right, left, up, down) for which the environment returns the next state and a reward. The tuple is appended to the transformer model's context. C): Given different initial seeds, the agent chooses different explorations as adversarially trained to avoid deterministic strategy which could be casily attacked leading to high negative regret. We observe that after an initial exploration phase (Ep 1), the transformer cxploits a second episode (Ep 2) the previously obtained knowledge i.e. the treasure's position and approaches it optimally.
To showcase that objective discover randomized algorithms when lacking differentiability, we study rolled out transformers which we train to explore and exploit simple grid worlds with evolutionary strategies, see Appendix for details on the environment dynamics well as training
8

---

Published as a conference paper at ICLR 2025
setup. We stress that do not consider reinforcement learning strategies e.g. based on policy gradients, as this requires sampling from a policy and therefore uses additional randomness. Here we aim to isolate the effect of randommess provided to the input of the transformer i.c. the first token.
As illustrated in Figure C after training the transformer on our objective, the model successfully implements randomized strategy: Over different random seeds, the transformer explores the grid differently in the first episode while exploiting in the second episode its knowledge about the treasure location. The performance during training when comparing to A shown in Figure 7 where see again A outperforming wrt. worst-case inputs and coming close to A average. In Appendix D we also provide the other baselines 4%, A, where the former did not properly train given our hyperparameter scan, and where we observe that A Afe. see Figure 10 To quantify randomization, we visualize the average time the transformer agent visits cell for the first time- showing its randomized exploration when considering A% instead of A see Figure
To conclude, even in this non-differentiable setting, optimization forces the transformer to use the provided randomness and instils efficient randomized exploration inside the transformer weights.
A
Perf. during Training of Grid
B
ning Ranc varying m Grid
C
A
4
-20
Acc. Aug. Roward
5
Acc. Reward
-30
-30-
-35
A0 mmmm-
40-m
-50
Ag m-]
0
3000
10000
13405 20100,
15909
0
5000
10000 15000
20000 25000
Training Steps
Training Steps
Figure 7: Grid world performance analyses. A): Accumulated reward over training transformers on our adversarial loss leading to models A and A%. The randomized model, while competitive on average, drastically outperforms on adversarial inputs. B): The adversarial loss requires several seeds for proper optimization. We scan m for the transformer A and observe that with m 2 10 we reach close to optimal average performance, while being robust to adversarial inputs. C): Average timestep at which the agent visits a given cell for the first time capped 25. Despite having access to random seed, A degenerates to a deterministic trajectory. On the other hand, A% learns a collection of trajectories such that on average, the timestep of the first visit is relatively uniform over cells.
4 DISCUSSION & RELATED WORK
Summary & Limitations. Randomness is an integral part of computer science. particular, there is long history in developing and analyzing randomized algorithms. In this paper, we build bridge between this intriguing class algorithms and deep learning and study under which circumstances optimization learns powerful randomized transformer algorithms. By optimizing well-motivated objective we show that randomness is chosen by optimization to endow transformer models with remarkable properties similar to those which classic randomized algorithms posses. Specifically, our learned randomized transformer algorithms significantly outperform their deterministic counterparts on adversarial inputs. Furthermore, simple majority voting among predictions computed on different seeds can boost performance far beyond deterministic transformers. Nevertheless, the provided evidence is only first conceptual step into how learn powerful randomized neural network algorithms, although we believe that the presented theory is general and applies to more practically relevant and large scale settings. Furthermore, is noteworthy that the computational intensity of our approach limits the applicability and scalability of the current form of our approach. Note that when comparing to ERM trained models, the hyperparameter m scales the memory as well as train and inference time (roughly) by factor of m. We leave scaling up our approach for future work.
Sampling from distributions, such as policies or probabilistic models, requires randomness. However, it remains unclear and key research direction to analyze the differences, advantages, and synergies of sampling from policies or (Bayesian) probabilistic models versus input-level sampling, as proposed here. In deep learning, methods like Markov-Chain-Mo Chain-Monte-Catte (MCMC) and variational inference (Kingma & Welling 2013; Rezende et al.] 2014), loosely including dropout (Srivastava et al.) 2014 Gal & Ghahramani 2015) and ensembling ilakshminarayyanan al. 2017), are related to

---

Published as a conference paper at ICLR 2025
our approach. This also applies to generative adversarial networks (GANs) (Goodfellow al. 2014). These methods use randomness to sample from prior or (approximate) posterior distributions. However, we emphasize that in these methods, randomness is intentional design choice and forced upon the algorithms computational graph rather than a learned characteristic. Therefore, when trained with our objective, weight distributions that randomize network predictions might be learned without a Bayesian formalism. This suggests a connection between Bayesian inference and our method leading to randomized neural networks based on, for example, "adversarial weight uncertainty".
Relationship to neuroscience. Randomness is also hypothesized to be useful for the brain. On the one hand. is well-known that the brain exposed noise but also produces activity that resembles chaos (London et al. [0100] Srajer et al.] [996] Faisal et al. 2008). On the other hand theories on functional properties due to criticality and learning algorithms that harness the randomness within the activity of recurrent neural networks exist (Lengler et al. 2013] Moss et al.) 2004, Shew & Plenz, 2012|Jaeger Haas 2004| Sussillo& Abbott 2009). Nevertheless, an objective that leads, in theory and in practice, to learning and leveraging randomness is not known to us. Here, we provide such an objective: the desire to perform well in worst-case scenarios. Furthermore, we provide evidence that optimization of the objective actually leads to randomized behaviour. The presented results provide an explanation of human and animal behavior and decision coriiiion-making processes which resemble taking actions leveraging randomization (Maoz et al.) 2019; Gliimcerr 2005 Noble & Noble 20088) Domenici et al.] 20088 Brrann 2021). hypothesizing that learning in the brain or evolution might optimize for some relaxation of worst-case behaviour as well.
Mlatn-le learning transformer algorithms. Through the advent of the transformer and large foundation models we are diverging from the classic perspective of neural networks learning abstract complex data representation LeCun et al. (2013). Indeed, large language models can be regarded as flexible tools and algorithms Weiss et al. (2021); Lindner et al. (2023); Giannou et al. (2023b) which can learn in-context Brown et al. [2020] Garg et al. (2022): b: Akyürek et al. (2023); von Oswald et al. (2023a); Giannou al. f (2023a); [ Liu et al. ( (2023a Li et al. (2023) and be re-configured by prompting Wei et al. ) Radford et al. (2019)] ester et al. (202T). We expand the class of algorithms that transformers can learn from data, to the family of randomized algorithms. We hope that through the neural algorithms perspective with exciting future research directions aiming towards distilling known, e.g. stochastic gradient descent, or discovering novel, unknown randomized algorithms hidden inside the trained weights of deep neural networks.
this work, we put more emphasis
Robustness. At the heart of our objective lies the desire to perform better in adversarial settings, a goal shared by established deep learning and RL methods. This goal is closely related to having more robust models. In this context, the incorporation of randomness has already proven to be beneficial in many domains. For instance, adversarial bandits have been extensively studied within the broader field of RL, particularly as a robust extension of the classical multi-armed bandits. Foundational work in adversarial bandits by Auer al. (2002) introduces the EXP3 algorithm which uses randomization to cope with oblivious adversaries. This line of research is already conceptually close to our grid world task, where smart exploration is learned to protect the agent against adversarial environments. Due to these connections, we speculate that our approach could allow for randomized algorithms being learned when trained with our objective the domain of adversarial bandits and RI..
In another line of work, in the domain of supervised learning, common adversarial training techniques are entirely deterministic. Some of them (Madry et al., 2018) employ gradient- attacks to augment training data with the most challenging perturbations, aiming to ensure consistent output within the neighborhood of any input. Other work investigated objectives aiming at prepare a model to perform well under distributional shifts (Arjovsky al. 2020). These objectives are very similar to our training objective (Duchi& & Namkoong [020]] Rahimian & Mehrotra 2022). except for the random component. Recent advancements have focused improving robustness through randomization, either of the model parameters or of the inputs, during both training and inference Rakin et al. (2018). These methods, when combined with adversarial training, are closely related to our proposed randomization technique. However, our approach determines the adversarial input based on the expected loss over random seeds, rather than relying on a single sampled seed i.e. m 1 crucial distinction to our objective which relied on m > as shown by our experiments.
Randomization is also used in randomized smoothing Cohen et al. (2019), a certified adversarial robustness method. This technique computes the majority vote over random perturbations of the input rather than over random seeds for a given input. We hypothesize that our procedure may offer
10

---

Published as a conference paper at ICLR 2025
better robustness guarantees by additionally randomizing decision boundaries. Overall, technique is readily applicable to methods aimed at defending against adversarial attacks and distribution shifts Sinha et al. 2020); Zou et al. (2023), positioning promising avenue for future research.
REFERENCES
Ekin Akyürek, Dale Schuurmans, Jacob Andreas, Tengyu Ma, and Denny Zhou. What learning algorithm is in-context learning? Investigations with linear models. In International Conference of Learning Representations, 2023.
Martin Arjovsky, Léon Bottou, Ishaan Gulrajani, and David Lopez-Paz. Invariant risk minimization. arXiv preprint arXiv: 02899, 2020.
Simran Arora, Sabri Eyuboglu, Aman Timalsina, Isys Johnson, Michael Poli, James Zou, Atri Rudra, and Christopher Ré. Zoology: Measuring and improving recall in efficient language models. arXiv preprint arXiv:2312.04927, 2023.
Peter Auer, Nicolò Cesa-Bianchi, Yoav Freund, and Robert E. Schapire. The nonstochastic multiarmed bandit problem. SIAM Journal on Computing, 32(1), 2002.
Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E. Hinton. Layer normalization. arXiv preprint 1607.06450, 2016.
Hans Albert Braun. Stochasticity versus determinacy in neurobiology: From ion channels to the question of the "free will". Frontiers in Systems Neuroscience, 15, 2021.
Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert- Voss. Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter. Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language models are few-shot learners. In Advances in Neural Information Processing Systems, volume 33, 2020.
Jeremy M Cohen, Elan Rosenfeld, and J. Zico Kolter. Certified adversarial robustness via randomized smoothing. arXiv preprint arXi 02918, 2019.
Soham De. Samuel L. Smith, Anushan Fernando, Aleksandar Botev, George Cristian- Albert Gu, Ruba Haroun, Leonard Berrada, Yutian Chen, Srivatsan Srinivasan, Guillaume Desjardins, Arnaud Doucet, David Budden, Yee Whye Teh, Razvan Pascanu, Nando De Freitas, and Caglar Gulcehre. Griffin: mixing gated linear recurrences with local attention for efficient language models. arXiv preprint arXiv:2402.1 19427, February 2024.
Paolo Domenici, David Booth, Jonathan Blagburn, and Jonathan Bacon. Cockroaches keep predators guessing by using preferred escape trajectories. Current biology: CB, 18:1792-44 6, 12 2008.
John Duchi and Hongseok Namkoong. Leamiing models with uniform performance via distributionally robust optimization. arXiv preprint arXiv: 180.00800000850, 2020.
AA Faisal. LPJ Selen, and DM Wolpert. Noise in the nervous system. Nature Review Neuroscience, 20392,303, 2008
Yarin Gal and Zoubin Ghahramani. Dropout as a bayesian approximation: Representing model uncertainty in deep learning. arXiv preprint 150..02 0200000021422.... 2015.
Shivam Garg, Dimitris Tsipras, Percy S. Liang, and Gregory Valiant. What can transformers learn in-context? A case study of simple function classes. In Advances in Neural Information Processing Systems, volume 35, 2022.
Angeliki Giannou, Shashank Rajput, Jy-yong Sohn, Kangwook Lee, Jason D. Lee, and Dimitris Papailiopoulos. Looped transformers as programmable computers. International Conference on Machine Learning, 2023a.
11

---

Published as a conference paper at ICLR 2025
Angeliki Giannou, Shashank Rajput, Jy- Yong Sohn, Kangwook Lee, Jason D. Lee, and Dimitris Papailiopoulos. Looped transformers as programmable computers. In Proceedings of the 40th International Conference Machine Learning, volume 202 of Proceedings of Machine Learning Research. PMLR, 2023b.
Paul Glimcher. Indeterminacy in brain and behavior. Annual review of psychology, 56:25-56, 02 2005. doi: 10.1 ptt.
Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Advances in Neural Information Processing Systems, volume 27, 2014.
Albert Gu and Tri Dao. Mamba: Linear-time sequence modeling with selective state spaces. arXiv preprint arXiv:2312.00752, 2023.
Herbert Jaeger and Harald Haas. Harnessing nonlinearity: Predicting chaotic systems and saving energy in wireless communication. Science, 304(5667):78
2004.
Samy Jelassi, David Brandfonbrener, Sham M. Kakade, and Eran Malach. Repeat after me: Trans- formers are better than state space models at copying. arXiv preprint arXiv:2402.01032, 2024.
Richard M. Karp. An introduction to randomized algorithms. Discrete Applied Mathematics, 34(1), 1991.
Diederik P. Kingma and Jimmy Ba. Adam: a method for stochastic optimization. In International Conference on Learning Representations, 2015.
Diederik P Kingma and Max Welling. Auto-encoding variational bayes. 1rXiv:13/2.611, 2013.
arXiv preprint
Balaji Lakshminarayanan, Alexander Pritzel, and Charles Blundell. Simple and scalable predictive uncertainty estimation using deep ensembles. Advances Neural Information Processing Systems, volume 30, 2017.
Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning. nature, 521(7553):436, 2015.
Johannes Lengler, Florian Jug, and Angelika Steger. Reliable neuronal systems: The importance of heterogeneity. PloS one, 8:e80694, 12 2013.
Brian Lester, Rami Al-Rfou, and Noah Constant. The power of scale for efffmeter-efffcient prompt tuning. arXiv preprint arXiv:2104. 0466819,.8...0 2021.
Yingcong Li, Muhammed Emrullah Iddiz, Dimitris Papailiopoulos, and Samet Oymak. Transformers as algorithms: Generalization and stability in in-context learning. In Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research. PMLR, 2023.
David Lindner, Janos Kramar, Sebastian Farquhar, Matthew Rahtz, Thomas McGrath, and Vladimir Mikulik. Tracr: Compiled transformers as laboratory for interpretability. In Thirty-eevntth Conference on Neural Information Processing Systems, 2023.
Bingbin Liu, Jordan T. Ash, Surbhi Goel, Akshay Krishnamurthy, and Cyril Zhang. Transformers learn shortcuts automata. arXiv preprint arXhv:2210.10749 2023a.
Nelson F. Liu, Kevin Lin, John Hewitt, Ashwin Paranjape, Michele Bevilacqua, Fabio Petroni, and Percy Liang. Lost in the middle: How language models use long contexts. arXiv preprint arXiv:2307.03172. 2023b. 2023b..
Michael London, Arnd Roth, Lisa Beeren, Michael Hausser, and Peter Latham. Sensitivity to perturbations implies high noise and suggests rate coding in cortex. Nature, 466:123-7, 07 2010.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In International Conference on Learning Representations, 2018.
12

---

Published as a conference paper at ICLR 2025
Uri Maoz, Gideon Yaffe, Christof Koch, and Liad Mudrik. Neural preeursors of decisions that matter an erp study of deliberate and arbitrary choice. eLife, 8, oct 2019. ISSN 2050-084X.
Gary L Miller. Riemann's s hypothesis and tests for primality. In Proceedings of the seventh annual 1975.
ACM symposium on Theory of computing, pp.
Frank Moss, Lawrence Ward, and Walter Sannita. Stochastic resonance and sensory information processing: tutorial and review of application. Clinical Neurophysiology, 115(2):267-28) 2004.
Rajeev Motwani and Prabhakar Raghavan. Randomized Algorithms. Cambridge University Press, New York, NY, USA, 1995.
J. Neumann. Zur theorie der gesellschaftsspiele. Mathematische Annalen, 100, 1928.
Ray Noble and Denis Noble. Harnessing stochasticity: How do organisms make choices? Chaos: An Interdisciplinary Journal of Nonlinear Science, 28:106::1 106309, 10 2018.
Antonio Orvieto, Samuel L. Smith, Albert Gu, Anushan Fernando, Caglar Gulcehre, Razvan Pascanu, and Soham De. Resurrecting recurrent neural networks for long sequences. In International Conference on Machine Learning, 2023.
Christos Papadimitriou. Computational complexity. Kidison-Wesleyy 1994.
Mary Phuong and Marcus Hutter. Formal algorithms for transformers. arXiv preprint wvXiv:2207.09238, 2022.
Michael O Rabin. Probabilistic algorithm for testing primality. Journal of Number Theory, 1980.
Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, llya Sutskever, et al. Language models are unsupervised multitask learners. OpenAl blog, 1(8):9, 2019.
Hamed Rahimian and Sanjay Mehrotra. Frameworks and results distributionally robust optimiza- tion. Open Journal of Mathematical Optimization, 3, 2022.
Adnan Siraj Rakin, Zhezhi He, and Deliang Fan. Parametric noise injection: Trainable random- ness to improve deep neural network robustness against adversarial attack. arXiv preprint 1rXiv:1811.09310. 2018
Danilo Jimenez Rezende, Shakir Mohamed, and Daan Wierstra. Stochastic backpropagation and approximate inference in deep generative models. In Eric P. Xing and Tony Jebara (eds.), Pro- ceedings of the 31st International Conference on Machine Learning, volume 32 of Proceedings of Machine Learning Research. PMLR, 2014.
Leslie Rice, Anna Bair, Huan Zhang, and J. Zico Kolter. Robustness between worst and average case. In Advances in Neural Information Processing Systems, volume 34, 2021.
Joel Rybicki and Jukka Suomela. Exact bounds for distributed graph colouring. In International Colloquium on Structural Information and Communication Complexity, pp. 46-60. Springer, 2015.
Tim Salimans, Jonathan Ho, Xi Chen, Szymon Sidor, and Ilya Sutskever, Evolution strategies scalable alternative to reinforcement learning. arXiv preprint wrXiv:1703.03866 2017.
Imanol Schlag, Kazuki Irie, and Jürgen Schmidhuber. Linear transformers are secretly fast weight programmers. In International Conference on Machine Learning, 2021.
Jürgen Schmidhuber. Learning to control fest- memories: an alternative to dynamic recurrent networks. Neural Computation, 4(1):131-139, 1992.
Frank Sehnke, Christian Osendorfer, Thomas Rückstieß, Alex Graves, Jan Peters, and Jürgen Schmid- huber. Parameter-explonee policy gradients. Neural Networks. 23(4):551-559, 2010. The 18th International Conference on Artificial Neural Networks, ICANN 2008.
Woodrow Shew and Dietmar Plenz. The functional benefits of criticality in the cortex. The Neurosci- entist review journal bringing neurobiology, neurology and psychiatry, 19, 05 2012.
13

---

Published as a conference paper at ICLR 2025
Aman Sinha, Hongseok Namkoong, Riccardo Volpi, and John Duchi. Certifying some distributional robustness with principled adversarial training. arXiv preprint arXiv:1710.10571, 2020.
Daniel D. Sleator and Robert E. Tarjan. Amortized efficiency of list update and paging rules. Commun. ACM, 28, 1985a.
Daniel D Sleator and Robert Tarjan. Amortized efficiency of list update and paging rules. Commu- nications of the ACM, 28, 1985b.
Vukica Srajer, Wilfried Schildkamp, Michael Wulff,, and Keith Moffat. Chaos in neuronal networks with balanced excitatory and inhibitory activity. Science, 274:1724 1726, 1996.
Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ily Sutskever, and Ruslan Salakhutdinov. Dropout: A simple way prevent neural networks from overfitting. Journal of Machine Learning Research, 2014.
David Sussillo and L. F. Abbott. Generating coherent patterns of activity from chaotic neural networks. Neuron, 63:544-557, 2009.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in Neural Information Processing Systems, volume 30, 2017.
Johannes von Oswald, Eyvind Niklasson, Ettore Randazzo, João Sacramento, Alexander Mordvintsev, Andrey Zhmoginov, and Max Vladymyrov. Transformers learn in-context by gradient descent. In International Conference on Machine Learning, 2023a.
Johannes von Oswald, Eyvind Niklasson, Maximilian Schlegel, Seijin Kobayashi, Nicolas Zucchet, Nino Scherrer, Nolan Miller, Mark Sandler, Blaise Agüera Arcas, Max Vladymyrov, Razvan Pascanu, and João Sacramento. Uncovering mesa-optimization algorithms in transformers. arXiv preprint arXiv:2309. 05858,, 2023b.
Abraham Wald. Statistical decision functions which minimize the maximum risk. Annals of Mathematics, 46(2):665-28) 1945.
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, brian ichter, Fei Xia, Ed Chi, Quoc
Le, and Denny Zhou. Chain-of-thoughe prompting clicits reasoning in large language models. In S. Koyejo, S. Mohamed, Agarwal, D. Belgrave, K. Cho, and A. Oh (eds.), Advances Neural Information Processing Systems, volume 35, 2022.
Gail Weiss, Yoav Goldberg, and Eran Yahav. Thinking like transformers. In Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research. PMLR, 2021.
Andrew Chi-Chin Yao. Probabilistic computations: Toward unified measure of complexity. In 18th Annual Symposium on Foundations of Computer Science (sfcs 1977), 1977.
Andy Zou, Zifan Wang. J. Zico Kolter, and Matt Fredrikson. Universal and transferable adversarial attacks on aligned language models. arXiv preprint urXiv:2307. 15043, 2023.
Nicolas Zucchet, Seijin Kobayashi, Yassir Akram, Johannes von Oswald, Maxime Larcher, Angelika Steger, and João Sacramento. Gated recurrent neural networks discover attention. arXiv preprint arXiv:2309.0173 2024.
14

---

Published as a conference paper at ICLR 2025
A APPENDIX
We provide here additional results and training details to reproduce the experiments one by one, as well as a proof of proposition
We give first a short overview of the compute budget used for this project. For the associative recall task well the graph coloring problem, estimate total compute budget using 4 Nvidia RTX 4090 for a month. For the grid world problem, we use a cluster of 16xA100 GPUs which we used to scan over the hyperparameters on and off over total of 2 weeks.
A.1 PROOF OF PROPOSITION
We first restate Proposition
Proposition 1 (Randomization can be beneficial in worst-case scenarios). Assume that X is compuct of Rd for some and that L continuous, Furthermore assume that there exist parameter 8 and a set of random seeds (ri)isigN E RN such that for each i
max L(As- ri)) = min max I(Ao(I,))), and Marg max L(A (x' r()) = 0. ZEX
(6)
0, #EX
Then there exists a randomized model which has a strictly smaller loss L than any deterministic model.
Proof. Assume there exist a parameter 6 and a set of random seeds (ri)isigN E RV such that for each equation 6 holds.
Let M = ming,r max L(Ag(r, r)). Any deterministic model, i.e. any choice of parameter 6, and fixed seed r E R. will yield an adversarial loss of at least M. On the other hand, consider following uniform distribution on the (rx):.
Let us now assume that
inf [[L(AA- R)]] #EX
inf DEX
Σ (x,) M
We can then fix a sequence (En) E 2 such that limn- [[L(Ag- (rn: R)) = M. Since X' compact set, without loss of generality we can assume (In) converge to some xn, By continuity of L, we have (Ag (x", [R)]] M. Thus, necessarily, for all i, L(Ag- (x" (x",ri)) = M, i.c. x" E N arg max,' L(Ag- (x', ,r))) which contradicts that assumption in equation
We therefore have, for each X,
CA inf ELL R)) < M xE
A.2 THE TRANSFORMER ARCHITECTURE AND THE RANDOM SEED ENCODING
We provide here short recap of the transformer neural network architecture Vaswani al. 2017 Phuong & Hutter 2022) that we use throughout our experiments. We define a transformer of depth K as being the transformation in blocks of the following two operations K times. First, we are considering input tokens E E R Lxdd for a sequence of length L, to which we add common positional encodings P E Lxdm. and either add or, as we do in this paper in most experiments, concatenate the random seed encoding (RSE). This is simply R E T.xd, or R E [0, 1,xx where each element of R sampled randomly from unit interval or a Normal distribution. Then, self-attention layer followed by a multi-layer- pereeepeoo transform the tokens by first computing queries, keys and values Q K.V V FWW,, FW,, EWW with which we then update as
E + + (softmax(QK3 (QK=) O M)VWP E E o
(7)
(8)
15

---

Published as a conference paper at ICLR 2025
and Wp E <d xdm well as W1 24dm W2 E R learnable parameter matrices. The softmax operation is applied row-wise. M is 0-1 mask that controls the attention span, non-linearity. We apply LayerNorm Ba et al. (2016) to the inputs of the self-attention layer as well as the MI.ss. We now present results where we trained the just training objective. We stress that these models
where w. WR. Wa
described transformer, well variants, are parametrized in way, although potentially only by taking positional encodings into account, which allows to condition computation the input position and therefore ignore the parts where provide randomness. We see that this is indeed the case when training on ERM and show this in the following.
B RANDOMIZED TRANSFORMERS SOLVE ASSOCIATIVE RECALL TASKS
A
1 0
100
100
Success %
Success %
60
40-
40
10-2
0-
0
10-3
LG 64256
16 64256
q
Figure 8: Fine-grained performance analyses of A% models trained with varying q on the associative recall task. When increasing above ERM (q=1), we observe non-zero success rate on all inputs due randomization. This success probability, see main text, can be increased by majority voting.
Table 1: Hyperparameters for the associative recall task.
Hyperparameter
Value
Dataset
Randomly generated binary value vectors with d = and corresponding one-hot encodings the keys
Tokenization RSE
One token is the concatenated vector [uv, ki,r;] where r; is (the same) random binary vector for all with d, 10.
Context size
Variable size from 8 20, see Figure
Optimizer
Adam (Kingma Ba 2015) with e le 9, 0.9, 0.95
Hyperparamters of our objective
m = 30 and = 100
Batchsize
512
Gradient clipping
Global norm of 1.
Positional encodings
We add standard positional encodings. transformer blocks with linear self-attention, head, key size token size no input- but output- embedddng Causal mask
Architecture details
Attention mask details
Weight init
Truncated normal initial with variance computed by common fan-in, bias parameter zero. We scale all weight matrices before skip connection with TVH with N the number of layers.
Learning rate scheduler Standard deviation Stat. robustness
Linear warm-up starting from to 0.003 for steps annealed to 0.0003 We average all results over 5 random seeds. We omit showing the deviation due to negligible differences across seeds.
16

---

Published as a conference paper at ICLR 2025
4
17
Fn
12
100
100
80-
Success %
Success %
10-
10-2
13-
1 3
5
q
q
Figure 9: Fine-gre tnee-graied performance analyses of A models trained with varying g on the 3-coloring problem. When increasing above ERM (q=1), we observe non-zero success rate all inputs due to randomization. This success probability, see main text, can be increased by majority voting.
C RANDOMIZED TRANSFORMERS SOLVE A GRAPH COLORING TASK
Table 2: Hyperparameters for the graph coloring task.
Hyperparameter
Value
Dataset
Random permutation of graph indices Single random floating point concatenated embedding Every token is the concatenated vector [v,, k. rs] where [0, 1] and d, 1.
Randomness
Tokenization
Context size
10 ie. we only consider cycles Ci0
Optimizer
Adam (Kingma & Ba 2015) with e 1e-3, 3 = 0.9, B2 = 0.95 with weight decay of 0.1 300000
Training steps
Hyperparamters of our objective
m 10 and 10 256
Batchsize
Gradient clipping
Global norm of
Positional encodings
We add standard positional encodings.
Architecture details
2 blocks of self atff-attention, head, key size 16, token size 16,
no input- but output-ent embedding
Attention mask details
Mask that only allows to observe direct neighboring tokens Truncated normal initial with variance computed by common fan-in, bias parameter zero. We scale all weight matrices before skip connection with 2V/ with
Weight init
number of layers.
Learning rate scheduler Standard deviation Stat. robustness
Linear warm-u up starting from 0 0.001 for 1000 steps annealed to 0.0001
average all results over random seeds. We omit show the deviation due to negligible differences across seeds.
D TRAINING TRANSFORMER AGENTS TO EXPLORE AND EXPLOIT GRID WORLDS.
We provide here additional results and details accompanying the main text.
Here, we first described the environment dynamics, loss functions and further details. For every task, we set the starting point of the agent in the lower left corner of 5 x 5 grid but sample random treasure location. The aim of the agent is now to explore the grid world efficiently. After 25 steps, the agent's position is reset and is given additional 25 steps to exploit the (potential) knowledge of the treasure location. After every step, the transformer agent is either given a reward of 1 the treasure is found and -0.1 otherwise, i.e. I(Ao) E,ro. rt. To have the ability explore differently,
17

---

Published as a conference paper at ICLR 2025
the first token of the model is vector sampled from normal distribution. Given this vector, the transformer first emits an output probability over the actions {left, up. right, down} from which extract the action by computing the argmax. Given the environment response providing the reward and next state, the concatenated embedding of the (i,j) coordinates as well as the reward is appended the sequence which is fed back the same transformer agent. If the transformer finds the treasure, the episode terminates. To compute an adversary in this setting, we do not fall back the q-norm relaxation. Rather compute the worst-case treasure position for the current transformer strategy by brute force iteration over all treasure positions. The adversarial position in the grid the one with the lowest accumulated reward. We stress the scalability issues, which we leave for future work, of this strategy to compute an adversary for most practical environments. To optimize the transformer weights, we use parameter-explorin policy gradients (PEPG) (Sehnke) et al., 201O) common gradient-free optimization method. PEPG estimates gradients based on evaluating populations of weight samples. Unlike methods like OpenAI-ES (Salimans et al., 2017), leverages a diagonal search covariance to infer directions of improvement.
Perf. during Training of Grid World
-20
Acc. Reward
-30
-40
Average
95th percentile
A
-50
Ag
0
5000
20000 25000 Training Steps
10000
15000
Figure 10: Performance of models A and A While A4, difficult to train, given the hyperpa- rameter sweep considered, A performs similarly as A see main text.
Table 3: Hyperparameters for the grid world task.
Hyperparameter
Value
Dataset
Randomly generated treasure location in 5 x grid
Randomness
Diverging from the other setups, here only provide single first random token ie. [[O] where every element sample from a Normal distribution.
Tokenization
One token is the concatenated vector [emb(i), (emb())) r] where emb
is a learnable embedding vector and (i,j) the current position of the token. {-0.1, } the reward at that time step. two episodes of steps each plus one initial random vector PGPE with population size of 300, center = 0.01, We sweeped over the following parameters and choose the best for the randomized transformer as well deterministic baseline
Context size Optimizer
0.01 and init std 0.03
center {0.03, 0.01, 0.003, 0.001). std Ir E {0.03, 0.01, 0.003, 0.001 and init std (0.03, 0.01, 0.003, 0.001).
Hyperparamters of our objective
m = 10 and g 20 We add standard positional encodings.
Positional encndings Architecture details
transformer blocks, 4 heads, key size 10, token size 80, we use an output-embert embeddinn
Attention mask details Weight init
Causal mask
Truncated normal initial with variance computed by common fan-in, bias parameter to zero. We scale all weight matrices before skip connection with 2/Z with N the number of layers.
18

---

Published as a conference paper at ICLR 2025
E SOME BACKGROUND ON RANDOMIZED ALGORITHMS
As we motivated in the introduction, we are aiming in this paper to learn randomized algorithms within neural networks, in particular transformers. Here we want to provide short background on randomized algorithms and their features.
A randomized algorithm is simply ... one that receives, in addition to its input data, stream of random bits that it can use for the purpose of making random choices. Even a fixed inpul, different runs of randomized algorithm may give different results; thus it is inevitable that a description of the properties of randomized algorithm will involve probabilistic statements. For example, even when the input fixed, the execution time of randomized algorithm is random variable" Karp (1911).
Given this class of algorithms, the main goal of this paper is to bring its advantages to deep learning. But it is neither obvious not intuitive what the advantages of randomization actually are. Nevertheless, in the last decades of intensive studies their benefits are established. To cite Karp (199I) (1989) again:
"By now is recognized that, in wide range of applications, randomization is an extremely important tool for the construction of algorithms. There are two principal rypes of advantages that randomized algorithms often have, First, often the execution time or space requirement of a randomized algorithm is smaller than that of the best deterministic algorithm that we know of for the same problem. But even more strikingly, if we look at the various randomized algorithmss that have been invented, we find that invariably they extremely simple understand and to implement; often, the introduction of randomization suffices to convert a simple and naive deterministic algorithm with bad worst-case behavior into randomized algorithm that performs well with high probability on every possible input."
Although much more manifold, one of the major advantages of randomized algorithms, which we also leverage to define a learning objective in the main text, is their robustness against adversarial inputs. To cite Karp (991)> a final time:
"A game-theorelic view is often useful in understanding the advantages of randomized algorithm. One can think of the computational complexity of a problem as the value of certain zero-sum two- person game in which one of the players is choosing the algorithm and the other player, often called the adversary, choosing the input data to foil the algorithm. The adversary's 's payoff is the running time of the algorithm on the input data chosen by the adversary. A randomized algorithm can be viewed as a probability distribution over deterministic algorithms, and thus as a mixed strategy for the player choosing the algorithm. Playing mixed strategy creates uncertainty to what the algorithm will actually do on a given input, and thus makes it difficult for the adversary to choose an input that will create difficulties for the algorithm."
Generally, one distinguishes between two classes of randomized algorithms, see below, whereas we focus on Monte-Carlo algorithms in this paper i.e. randomized algorithms with fixed runtime (such as a common beed-forward neural network) which we allow to produce incorrect predictions. We go on to furthermore discuss when and how one can boost the performance of these algorithms by repetition, a technique that we leverage heavily in the main text.
To showcase the advantages of randomized algorithms and give the reader a quick overview, furthermore introduce and describe in the following a few classic randomized algorithms, which also served as an inspiration for deciding on which problems we trained neural networks on.
E. TWo CLASSES OF RANDOMIZED ALGORITHMS: MONTECARLO VS. LASVEGAS ALGORITHMS
Definition Monte Carlo algorithm is randomized algorithm that runs for a deterministic runtime and whose output may be incorrect with some (usually small) probability.
Definition 4. A Las Vegas algorithm is a randomized algorithm that runs for a randomized runtime and always outputs correct solution.
These two notions are nevertheless tightly intertwined. Indeed, given a Las Vegas algorithm, one construct Monte Carlo algorithm by running the algorithm for prefixed amount of time (i.e.
19

---

Published as a conference paper at ICLR 2025
early terminating the algorithm if it exceeds this runtime) and returning whatever output if it didn't succeed. A simple Markov inequality allows to bound the probability of returning a wrong answer. In general however, a Monte Carlo algorithm cannot be converted into Las Vegas algorithm. There are however special cases where this can be done. When for example the correctness of a solution can be tested with deterministic algorithm, one can construct Las Vegas algorithm from Monte Carlo algorithm, by running it as many times as needed to find a correct answer. We describe this procedure detail in the following section which we leverage heavily in the main text, denoted as majority voting, to boost performance.
E.1.1 PROBABILITY AMPLIFICATION
Assume we have access to a randomized algorithm that can, for every single input I E X, output A(x) that is correct with a certain probability. Note that in our experiments of the main text, the output of the neural network (ar) returns a probability distribution e.g. the probability over certain classes or actions. We stress that compute the final result of the algorithm must therefore either sample obtain the final result of the algorithm or compute it by the argmax. Note that this additional sampling / argmax step is usually not necessary for common (randomized) algorithms. In the following, we will show a procedure that allows to define another algorithm that will significantly amplify the probability of success of A. Therefore, we wish to explain the presented results in the main text where we observe majority voting of the randomized transformer predictions indeed improves performance significantly while surpassing the deterministic transformer models dramatically.
More precisely, let y be the output space, and C₂ C y be the correct outputs for input E X.
Let E X. A(x) is a distribution over y (one can think of A as the random output for given input). We sample N E N samples of A(x) and return the statistical mode M, i.e., the most frequent output. We want to bound the probability to return a correct output y E C..
Proposition 2. Let 8 > 0.
max P[A(x) =] max P[A(x) = yl yEC²
EC
If A > 0 and N > XZ
In D.C.. then P(M E C₂] > 1 1-6.
The proof follows from Hoeffding inequality and union bound.
We now present well-known randomized algorithms which should give the reader better intuition how and why randomness is used to design powerful algorithms.
E.2 RABIN-MILLER MMILLER 1975 RABIN 1980
Setting: Given a number n E N, decide whether n is prime or not.
Approach: If is prime, any [1...., n satisfies a-1 1 mod p. We can write n 2nm where m odd. We necessarily have that "x² = =1 mod p or a "=² = mod p. By recurrence, we either have am = 1 or there exists a k < v such that a² = -1 mod One can show that, if is composite, at most 1 of the a in [I...., 1] will verify this property.
A naive solution would be to then try all possible bases. That would give an exact but very inefficient algorithm. Instead, we can sample independently and uniformly at random bases, and return "pseudoprime" if all tests are successful, and "composite" otherwise. If the algorithm gets a prime, it will always output "pseudoprime". If it gets a composite number, it will output "pseudoprime" with probability मe. Conversely, the number is always composite if the algorithm returns "composite". Using Bayes rule, one can easily bound the probability that the number is composite given that the algorithm returns "pseudoprime". The complexity of the algorithm is Ö log" n), much less than the Ónn) we would have needed with the deterministic approach.
Assuming the Grand Riemann hypothesis, is enough to test the first Olog² n) basis to get an exact deterministic algorithm running in Ölog" n). The hypothesis remains an open problem so far. The randomized version is still mainly used in practice because the deterministic algorithms that exist much more complex mathematically, more difficult to implement, and more expensive in terms of computational complexity.
20

---

Published as a conference paper at ICLR 2025
E.3 PAGING PROBLEM (SLEATOR & TARJAN 1985B))
Problem:
We are given fast memory (cache) that can fit l pages and an unlimited slow memory. user can only access data from the cache while there communication channel between the fast and the slow memory. a user wants to access data which not currently in cache, it requires a cost of I overwrite a cache entry by the required page from the slow memory. Writing data from the cache to the slow memory costs O. Therefore the goal of this problem is to find a strategy to fetch as little data from the slow memory. An oblivious adversary chooses sequence of queries. What the best online memory management strategy to minimize the cost?
One of the easiest strategies, the Random Marking Algorithm, goes as follows: initialize all pages in the cache as marked; whenever the queried page is not in the cache, evict one of the unmarked cache pages chosen uniformly random; in case all pages are marked, unmark all before. It can be shown that this achieves is (log competiiivee against oblivious adversary. This is also the best one can achieve theoretically. One can show that any deterministic algorithm can at best be k-competitive against oblivious adversary.
Approach:
E.4 CYCLE 3-COLORING
Problem: Given an oriented cycle defined by set of N vertices V = (wr) and edges E = {(v,, 0i+1 mod N) ) color the vertices using 3 colors such that neighbouring vertices receive different colors. Formally speaking, we desire mapping f: V + (1,2.3 such that f(v) + f(w) for all (v, w) E E. In the distributed graph coloring problem, which we consider here, we require that all vertices v compute f(u) locally, being able to only communicate with their immediate vicinity.
Approach: A simple randomized approach proceeds in two phases: In the first phase, each vertex selects itself with probability 1/2. If one of its neighbours also selected itself, it subsequently unselects itself again following some deterministic rule based on the vertex id. A typical example for such a rule, is that always the one with smaller id unselects itself. In the second phase, every vertex that is still selected colors itself with color O. Crucially, one easily shows that, regardless of the distribution of the vertex ids, this process ensures that with high probability the paths between vertices color have lengths at most nl Therefore, they can be colored properly, in third and final phase, by a simple propagation process using only (log nı) rounds. This defines a Las Vegas algorithm, that one turn to Monte Carlo algorithm (check section E.I). Using a different approach, one can actually achieve a much better complexity of O(log" (n) [Rybicki & Suomela (015)).
'log" (n) counts the number of times one has apply log composedly hecome smaller than
21


Reviews:
[{"review_id": "9sqOzv5gXQ", "reviewer": "Reviewer_y3S8", "summary": "Randomized algorithms can offer better worst-case performance than deterministic ones.  \nCan transformers learn randomized algorithms?   \nThe authors study conditions for randomized algorithms to yield possible advantages and they offer a training methodology to emerge them in transformer networks. Namely design choices to emerge randomized algorithms involve around: a. the model; it needs to have limited capacity and receive random signal at its input, b. the loss function; it needs to be a surrogate for worst-input risk instead of expected risk.\nThey demonstrate application in three conceptual tasks: associative recall, graph coloring, agent exploring a grid-world\nAnd they claim that randomized algorithms achieve increased robustness against adversaries.", "questions": "1. The transition to use the q-norm relaxed loss in L195-200 is not motivated sufficiently at that point in text. Can you elaborate on it a bit more?\n\n2. L207-208: Are the same random input seeds reused for all inputs? Why? What would happen if fresh seeds are sampled for every input $x_i$?  \n\n3. Batching strategy when finetuning for the emergence of a randomized algorithm is not clear at the text. I assume that $B \\times N$ samples are processed independently at once. $B$ is the number of input data, $N$ is the number of random seeds. Is this correct?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Very well-written paper, easy to follow, with extensive examples and related work material both in the main paper and in the appendix.\nWell-motivated and executed study for the possibility to learn randomized algorithms.\n\n1. Convincing results of superior worst-case performance in the considered tasks when compared to training alternatives, ablating some aspect of the loss, the multi-seed version trained on the relaxed adversarial loss is the best.\n2. Experiments cover well important hyperparameters for the training setting. namely the relaxation hyperparameter which interpolates between ERM and worst-case risk, $q$, and the number of seeds per input, $m$.\n3. Experiments cover variety of architectural constraints, such as linear attention (sec 3.2), structured local attention masks that are GNN-like (sec 3.3), and autoregressive settings (sec 3.4). As well as a variety of tasks and optimization techniques.\n\nThe paper finds the reader with a clear impression about the possibility of randomized algorithms for improving worst-case performance, as evidence by 95th percentile results in Figs 2,3,5 and 7. As well as inference-time strategies on improving them with majority voting.", "weaknesses": "1.a. I would personally have enjoyed seeing experiments with actual adversarial robustness training, using a threat model on human preference alignment data, applied at generative LLMs.  \n\n1.b. Lines 216-218 mention that adversarial robustness training is difficult, however recent literature has provided with framework for that [ 1]. While it does not decrease the contributions of this paper, comparing with the methodology mentioned in the paper would have been great!\n\n[1] Xhonneux et al., “Efficient Adversarial Training in LLMs with Continuous Attacks”, May 2024 to appear at NeurIPS 2024.\n\n2. Section 2.1 “Excessive Model Capacity Will not Enforce Randomness” the argument is not very convincing to me. In the face of a multi-seed worst-case objective like one described later, does the argument still hold? Proposition 1 also seems to go against the impossibility eluded by this section. Experiments on finetuning medium-sized (~1B) models on toy tasks could have provided some extra evidence for that.\n\n3. On grid-world experiments: While the first episode demonstrates randomness in ways to explore for the target, why doesn’t the randomness follow as well in the second “exploitation” episode? There are multiple equivalent in length ways to reach the target. I would expect that in Figure 6.C. those would vary across different seeds.\n\n4. Instead of using input randomness, it would have been very interesting to understand the ability or limitations on using output sample randomness which is fed back to the input in an autoreregressive case, as a drive to learn randomized algorithms. The authors avoid this explicitly in Section 3.4, however I do not understand the reason.\n\n\n## Typos\nL141: “for any distribution **over** $\\mathcal{X}$ and $\\mathcal{R}$.  \nL233: “hyperparameters $m$ and $\\mathbf{q}$.  \nL965, L895, L853: change $p$ for $q$.  \n\n\n## Missing citations\nOn linear attention (L291): Katharopoulos et al., “Transformers are RNNs: Fast Autoregressive Transformers with Linear Attention”, ICML 2020.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "2GpQ0Pz59F", "reviewer": "Reviewer_pYUp", "summary": "The paper explores the incorporation of randomized algorithms into transformer models through learning, in order to enhance robustness and performance in adversarial environments. By training transformers on expected and adversarial losso, single and multiple seeds, the study demonstrates that their proposed approach can outperform their deterministic counterparts, particularly when faced with adversarial challenges. The authors focus on three main tasks: associative recall, graph coloring and exploration in grid worlds, to evaluate the impact of randomized strategies on model performance. The results indicate that, by employing randomness, transformers achieve higher robustness and adaptability (implementing simple strategies repetition or majority voting) over predictions with different random seeds.", "questions": "What were the reasons that pushed the authors not to present analyses (even theoretical) regarding the computational cost preferring to insert more general information such as section E of the appendix?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1) Innovative integration of randomization: Altough randomization was a concept that has been used with Transformers during the years and at different levels (e.g. positional encodings, attention weights) the paper introduces an original concept of definining randomized algorithms within neural networks through learning: by simple epmloying repetitions and strategies such as majority voting this approach outperforms deterministic approach\n\n2) Comprehensive experimental design: The paper provides a solid experimental framework across varied tasks, such as associative recall, graph coloring, and grid world exploration. Each task is carefully selected to illustrate different advantages of randomization, such as memory management, combinatorial problem-solving, and exploration.\n\n3) Theoretical justifications and adversarially driven objective : The authors define a description of theoretical considerations about randomized algorithms that bring to the definition of an adversarially driven objective: it is an interesting addition that supports the study's claims on robustness. The use of a relaxed adversarial loss and exploration of different adversarial strengths adds depth and completeness to the analysis of transformer behavior in challenging environments.\n\n4) Empirical results on robustness: The empirical results are thorough and show randomized transformers advantages, eespecially in scenarios with worst-case inputs. The paper's analysis highlights how majority voting and the number of seeds influence performance, enhancing the robustness of the findings. Moreover tha authors discuss about their results and the major limitations of their approach.\n\n5) Appendix: Further information on the training modality and parameters is appreciated.", "weaknesses": "1) Scalability challenges: The most important corcern about the proposed methodology is the computationally cost, particularly with the reliance on multiple seeds and adversarial loss training. The authors acknowledge this in the \"Summary and Limitations\" paragraph, noting that scaling the approach to larger settings may require significant computational resources, which limits the practicality and broader applicability of the approach. I consider that such a problem should have been addressed in a more in-depth manner and not relegated to a second analysis, as it is a very important measure for judging the entire methodology.\n\n2) Limited practical applications discussed: While the theoretical foundation is strong, the paper could benefit from discussing more real-world applications where randomized transformers might be beneficial. \n\n3) Dependency on the choice of q and m hyperparameters: The model's performance and randomization effectiveness heavily depend on hyperparameters, particularly q and m. The authors could delve further into automated ways to tune these values or provide guidelines for choosing optimal parameters for various tasks. High-computation hardware needed to perfom analysis about the hyperparameters can be prohibitive.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "1ICUtjBrhk", "reviewer": "Reviewer_mQSR", "summary": "The paper explores how transformers can learn and implement randomized algorithms, which are advantageous in certain adversarial and game-theoretical contexts. Randomized algorithms typically perform well in adversarial environments and exhibit robustness against worst-case scenarios. The authors propose a novel objective function for training transformers that optimizes their performance in these settings by introducing randomization via an input \"seed.\"", "questions": "- What are the computational and memory challenges of scaling the proposed randomization method to larger, more complex datasets or real-world tasks? Are there specific optimizations that could make the approach more efficient?\n- The study introduces hyperparameters qq and mm in the training objective. How sensitive are the final model’s performance and robustness to variations in these hyperparameters?\n- Could the proposed randomization approach be adapted for more complex reinforcement learning environments, such as those with continuous action spaces or requiring long-term strategy?\n- How does this approach compare with other randomization techniques, such as dropout (at inference)?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- The authors provide a strong theoretical foundation for why randomization is advantageous in certain adversarial contexts, referencing game theory and established concepts like Yao’s Minimax Principle.\n- The study highlights that randomization can increase resilience against adversarial attacks.", "weaknesses": "- While the paper presents conceptual tasks to validate the approach, it does not provide empirical results on large-scale or real-world datasets. This limitation raises questions about how well the method would scale and perform in more complex, realistic environments.\n- The approach requires sampling multiple seeds during training (controlled by the hyperparameter mm), which can increase computational overhead significantly. The authors note that this limitation affects memory, training time, and inference time, making the method potentially impractical for large-scale applications.\n- The paper’s theoretical sections are rigorous but may be dense for readers without a background in adversarial training or randomized algorithms.\n- The study assumes relatively static environments for tasks like grid world exploration and graph coloring. However, it does not address how the transformer’s randomized strategies would perform in dynamic, non-stationary settings where environmental conditions change over time.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "tjQIYeFAus", "reviewer": "Reviewer_BfRQ", "summary": "This paper explores the integration of randomization into transformer models, traditionally used in deterministic settings, to enhance their performance, especially in adversarial contexts. The authors demonstrate that randomized algorithms can be instilled in transformers through learning, in a purely data- and objective-driven manner. Though an analysis of known adversarial objectives for which randomized algorithms offer a distinct advantage over deterministic ones, they 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.", "questions": "See first Weakness", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- The paper is very well written, clear, with a good motivation. They first introduce the setting by presenting an example with associative recall, which is a variant of the classical paging problem in computer science for which randomized solutions exist. This problem is also a well-studied problem for transformers with the goal of evaluating recall capabilities. The paper continues with a theoretical analysis in which the authors study when randomization can be beneficial and when it is not. From there, the authors propose a training objective. \nFinally, the authors experiment with 3 use cases: associative recall, graph coloring, and agents exploring lattice worlds.\n- The contribution is, to the best of my knowledge, novel and could lead to improvements in how transformers can solve certain tasks.", "weaknesses": "- The experiments are performed on three different small tasks, the proposed approach should increase the computational complexity, which is already high with transformers, can the authors comment on this in terms of training and inference? \n- I am a bit puzzled by the paragraph on adversarial robustness (small input perturbations) in the related work, first, the cited paper (Rakin et al. (2018)) shows an approach to increase robustness with randomization, but now such approaches have been mostly disproved (see Gnecco et al. 2023). Furthermore, the randomized smoothing approach uses randomization _only in the training phase_, the approach is inherently a training procedure for a smooth function. The inference _is_ deterministic. Overall, I find this discussion could be made clearer. \n\nGnecco et al. On the Role of Randomization in Adversarially Robust Classification. NeurIPS 2023.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Oral)