Research map / Adversarial robustness and security / Certified and empirical robustness
Learning Randomized Algorithms with Transformers
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that transformers with random seed inputs can learn randomized algorithms when trained with a q-norm relaxed adversarial objective over multiple seeds, outperforming deterministic and ERM-trained counterparts on associative recall, graph coloring, and grid-world exploration.
Problem
Standard expected-risk training of transformers yields deterministic behavior, which is brittle against adversarial inputs; the paper asks whether randomized algorithms can be learned inside transformers via an adversarial objective.
Approach
Feed a random seed as an extra input token to the transformer and train with a q-norm relaxation of the min-max loss, averaging loss over m sampled seeds per input, so optimization learns to exploit the randomness; majority voting over seeds at inference further boosts success.
Key results
- On associative recall, majority voting over seeds for the q=100 randomized transformer recalls virtually all inputs, while the deterministic single-seed model's worst-case success drops to zero for larger sequences.
- On graph coloring, the randomized model with majority voting approaches near-100% success probability, while ERM-trained (q=1) models learn degenerate, seed-independent behavior.
- On grid worlds, the adversarially trained randomized agent (A^q_R) drastically outperforms A^E_R on adversarial inputs while staying competitive on average reward.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Train with the relaxed adversarial objective using multiple random seeds instead of a fixed seed | Transformer · Associative recall | 95th-percentile success rate | Helped |
| Use majority voting across random seeds (ablation) | A^q_R · Associative recall | success rate | Helped |
| Train with q=100 instead of ERM (q=1) (ablation) | Multi-seed transformer · Associative recall | 95th-percentile success rate | Helped |
| Provide multiple random seeds during ERM training instead of a single fixed seed (ablation) | Transformer · Associative recall | performance | No clear effect |
| Increase q above 1 during training (ablation) | Multi-seed transformer · Associative recall | worst-case success rate | Helped |
| Increase the number of seeds m beyond 1 (ablation) | A^q_R · Associative recall | performance | Helped |
| Train with the relaxed adversarial objective using multiple random seeds instead of a fixed seed | Transformer · 3-coloring cycles C_10 | worst-case success probability | Helped |
| Use majority voting across random seeds (ablation) | A^q_R · 3-coloring cycles C_10 | success probability | Helped |
| Increase q above 3 during training (ablation) | Multi-seed transformer · 3-coloring cycles C_10 | worst-case performance | Helped |
| Use output sampling instead of learned input-seed randomization (ablation) | A^q_{r_0} · 3-coloring cycles C_10 | success probability | Hurt |
| Train with the relaxed adversarial objective using random seeds | Transformer agent · Grid world | 95th-percentile accumulated reward | Helped |
| Increase the number of seeds m to at least 10 (ablation) | A^q_R · Grid world | average performance | Helped |
Surprising findings
- ERM-trained transformers given random seeds collapse to deterministic predictions and gain nothing from the extra randomness.
- Sampling outputs from a single-seed adversarially trained model does not recover the performance of the properly randomized multi-seed transformer on graph coloring.
Limitations
- Computational cost grows roughly linearly with the number of seeds m, limiting scalability.
- Evaluated only on small synthetic toy tasks; no large-scale language or vision experiments.
- Adversary for grid world is computed by brute-force enumeration of treasure positions, which does not scale to practical environments.
Experimental setup
Benchmarks: associative recall (N=20) 3-coloring of cycles C_10 5x5 grid world exploration
Metrics: average success rate 95th-percentile (adversarial) success rate accumulated reward predictive variance over seeds
Baselines: A^E_r0 (ERM single seed) A^E_R (ERM multi seed) A^q_r0 (adversarial single seed)
Builds on: Yao's minimax principle distributionally robust optimization PEPG randomized smoothing
Closest papers by meaning
- Algorithmic Capabilities of Random Transformers (NeurIPS 2024 · similarity 0.88)
- Random Entangled Tokens for Adversarially Robust Vision Transformer (CVPR 2024 · similarity 0.87)
- Adversarial Robustness via Deformable Convolution with Stochasticity (ICML 2025 · similarity 0.86)
- Random Sparse Lifts: Construction, Analysis and Convergence of finite sparse networks (ICLR 2024 · similarity 0.84)
- Towards Understanding Transformers in Learning Random Walks (NeurIPS 2025 · similarity 0.84)
- From Shortcut to Induction Head: How Data Diversity Shapes Algorithm Selection in Transformers (NeurIPS 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.