arXiv:2608. 07224v1 Announce Type: new Abstract: Motivated by LLMs, which generate outputs by iteratively sampling from next-token distributions, we introduce a PAC-learning model for binary stochastic autoregressive learning.
By Ilan Doron-Arad, Idan Mehalel, Elchanan Mossel
arXiv:2606. 27721v1 Announce Type: new Abstract: Compositional generalization, the ability to solve complex problems by combining solutions to simpler sub-problems, is a fundamental capability of both natural and artificial intelligence, and a key mechanism underlying chain-of-thought reasoning.
By Nived Rajaraman, Audrey Huang, Miroslav Dudik, Robert Schapire, Dylan Foster, Akshay Krishnamurthy
arXiv:2609.38806v1 Announce Type: cross
Abstract: Next-token prediction has driven remarkable progress in large language models, yet a growing body of evidence suggests that they can struggle on prob...
By Woosang Jeon, Jaeyeon Kim, Sham Kakade, Yilun Du, Amrit Singh Bedi, Arun Kumar Chithanar, Chul Lee, Taehyeong Kim, Sitan Chen
The paper investigates how well practical machine‑learning algorithms approximate Solomonoff’s universal predictor when trained by minimizing log‑loss over diverse datasets. It establishes tight bounds on the worst‑case increase in prediction error caused by approximating the Bayesian mixture predictor, showing that while the excess error can be large in low‑prior environments, it remains bounded on average and under distribution shifts. The authors also extend their analysis to finite‑sample settings relevant to neural networks and Transformers.
By Qian Li, Shang-Hua Teng
The paper argues that Large Language Models (LLMs) do not function as Solomonoff induction estimators because their training objectives—cross‑entropy, negative log‑likelihood, and next‑token prediction—optimize fit to a supplied conditional distribution rather than a program‑weighted universal mixture. It further contends that additional computation alone does not transform these models into optimal predictors without external hyper‑parameter or architectural changes. The authors suggest that neurosymbolic machine learning, exemplified by models such as Fable and Astra, represents a shift toward symbolic model synthesis, moving beyond purely statistical LLMs.
By Hector Zenil, Abicumaran Uthamacumaran, Luan Ozelim
arXiv:2610.32104v1 Announce Type: cross
Abstract: Several formal theories have been developed to characterize the capabilities and limitations of the transformer architecture, each employing differen...
By Awni Altabaa, Tobias Schnabel, Kiran Tomlinson
arXiv:2601. 05280v3 Announce Type: replace-cross Abstract: On the one hand, the question of whether large language models (LLMs) are Solomonoff induction estimators has become an explicit question at the intersection of Algorithmic Information Theory (AIT) and Machine Learning (ML) of great interest.
By Hector Zenil
arXiv:2601.05280v4 Announce Type: replace-cross
Abstract: On the one hand, the question of whether Large Language Models (LLMs) are Solomonoff induction estimators has become an explicit question at...
By Hector Zenil, Abicumaran Uthamacumaran, Luan Ozelim
arXiv:2603. 06957v2 Announce Type: replace-cross Abstract: We study post-training linear autoregressive models with outcome and process rewards.
By Alireza Mousavi-Hosseini, Murat A. Erdogdu
The paper introduces Nexus, an optimizer that encourages gradient similarity during pretraining to bring task‑specific minima closer together. Experiments on models from 130M to 3B parameters show that Nexus achieves the same pretraining loss as standard optimizers while significantly improving downstream performance, including a 15% accuracy boost on GSM8k and a 0.012 reduction in out‑of‑distribution loss for the 3B model.
By Huanran Chen, Huaqing Zhang, Xiao Li, Yinpeng Dong, Ke Shen, Jun Zhu
The paper investigates how autoregressive language models can iterate a hidden state without emitting tokens, identifying three distinct risks associated with a latent process: token risk, teacher‑forced latent risk, and open‑loop risk. It shows that when the Bayes next‑token posterior depends on a full‑rank $k$‑dimensional statistic, a width‑$k$ latent with linear least‑squares transition and a refitted unembedding can match the Bayes token predictor, but this match is only up to an invertible gauge. The study also highlights sharp obstructions: a constant latent can drive teacher‑forced risk to zero while token cross‑entropy reverts to marginal entropy, and a perfect token predictor may still conceal a null‑space walk that causes open‑loop error to grow linearly with horizon, indicating that small latent or token losses alone do not guarantee accurate latent rollout without additional rank or injectivity conditions.
By Yuzhou Hong
The paper introduces F-ICL, a benchmark that measures in‑context algorithmic reasoning in language models by exhaustively enumerating 86 million valid programs of length ≤13 on a Turing‑complete machine and computing the exact posterior under a bounded Levin–Solomonoff prior. Unlike typical benchmarks, F‑ICL provides a distributional reference rather than just answers, allowing the evaluation of models’ inductive priors. Across 105 configurations of models ranging from 0.8 B to 675 B parameters, models achieve up to 92 % accuracy, yet many still deviate from the Bayes‑optimal reference, and the study derives theoretical bounds on cumulative loss for predictors with positive prior weight on the reference.
By Luan Ozelim, Hector Zenil