Research map / Architectures and efficiency / RNNs and normalization
Learning Universal Predictors
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.
Meta-trains LSTMs and Transformers on data sampled from universal Turing machines (a BrainF*ck variant called BrainPhoque) and other algorithmic sources to approximate Solomonoff induction, with theory on consistent UTM-based training data.
Problem
How far meta-learning can go in amortizing the universal predictor (Solomonoff Induction), which is uncomputable, into neural networks trained on algorithmically generated data.
Approach
Generate meta-training sequences by running random programs on a universal Turing machine (BrainPhoque), prove consistency of the resulting training distributions (including normalized Solomonoff prior and generalized Solomonoff semimeasures under non-uniform program distributions), and train standard architectures with log-loss to approximate SI.
Key results
- Transformer-L and LSTM-L match the optimal CTW predictor on in-distribution VOMS sequences, with larger models performing better across architectures.
- Transformers fail to length-generalize to 1024 steps on VOMS while LSTMs perform best out-of-distribution.
- All models trained on UTM data beat the loose Solomonoff upper bound on UTM sequences; Transformers trained on UTM data transfer most to Chomsky tasks.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Increase model size from S to M to L (ablation) | Neural predictors trained on VOMS · VOMS, in-distribution | cumulative expected regret | Helped |
| Use Transformer-L instead of smaller neural predictors | Neural predictors trained on VOMS · VOMS, in-distribution | cumulative expected regret | Helped |
| Use LSTM rather than Transformer for length generalization | Neural predictors trained on VOMS · VOMS, length 1024 | cumulative expected regret | Helped |
| Increase model size (ablation) | Neural predictors trained on Chomsky hierarchy tasks · Chomsky hierarchy tasks, in-distribution | cumulative expected regret | Helped |
| Use Transformer-L instead of other evaluated architectures | Neural predictors trained on Chomsky hierarchy tasks · Chomsky hierarchy tasks, in-distribution | cumulative expected regret | Helped |
| Increase model size (ablation) | Neural predictors trained on UTM data · UTM, in-distribution | cumulative expected regret | Helped |
| Train on UTM data before evaluating on Chomsky tasks | Transformer models · Chomsky hierarchy tasks, transfer | accuracy | Helped |
| Train on UTM data before evaluating on VOMS | LSTM models · VOMS, transfer | cumulative expected regret | Helped |
| Use Transformers rather than LSTMs for length generalization | Neural predictors trained on Chomsky hierarchy tasks · Chomsky hierarchy tasks, length 1024 | cumulative expected regret | Hurt |
Surprising findings
- Transformers trained on UTM data transfer best to Chomsky tasks, while LSTMs transfer most to VOMS.
- Transformers fail to length-generalize while LSTMs do so, despite Transformers' strong in-distribution performance.
Limitations
- Results are empirical; universality of SI approximation cannot be guaranteed.
- The Solomonoff upper bound is loose and computed from shortened programs.
- UTM program distribution does not necessarily assign high probability to human-relevant tasks.
Experimental setup
Datasets: BrainPhoque UTM-generated sequences Variable-order Markov sources (VOMS) Chomsky hierarchy tasks (15 algorithmic tasks)
Benchmarks: Chomsky hierarchy tasks VOMS (CTW comparison) BrainPhoque UTM data
Metrics: cumulative expected regret accuracy length generalization
Baselines: Context Tree Weighting (CTW) Solomonoff upper bound RNN Stack-RNN Tape-RNN LSTM Transformer
Builds on: Chomsky hierarchy benchmark (Delétang et al.) Context Tree Weighting Ortega et al. meta-learning as Bayesian inference BrainF*ck Stack-RNN
Closest papers by meaning
- Meta-Learning and Universality: Deep Representations and Gradient Descent can Approximate any Learning Algorithm (ICLR 2018 · similarity 0.89)
- Understanding Generalization Requires Universal Induction (NeurIPS 2026 · similarity 0.84)
- Memory-Reduced Meta-Learning with Guaranteed Convergence (AAAI 2025 · similarity 0.84)
- MetaSymNet: A Tree-like Symbol Network with Adaptive Architecture and Activation Functions (AAAI 2025 · similarity 0.84)
- Improving Memory Efficiency for Training KANs via Meta Learning (ICML 2025 · similarity 0.82)
- Towards Understanding the Universality of Transformers for Next-Token Prediction (ICLR 2025 · similarity 0.82)
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.