Abstract
The rapid advancement of large language models (LLMs) calls for a rigorous theoretical framework to explain their empirical success. While significant progress has been made in understanding LLM behaviors, existing theoretical frameworks remain fragmented in explaining emergent phenomena through a unified mathematical lens. We establish the first formal connection between LLM architectures and Algorithmic Information Theory (AIT) by proving two fundamental results: (1) the training process computationally approximates Solomonoff prior through loss minimization interpreted as program length optimization, and (2) next-token prediction implements approximate Solomonoff induction. We leverage AIT to provide a unified theoretical explanation for in-context learning, few-shot learning, and scaling laws. Furthermore, our theoretical insights lead to a principled method for few-shot example selection that prioritizes samples where models exhibit lower predictive confidence. We demonstrate through experiments on diverse text classification benchmarks that this strategy yields significant performance improvements, particularly for smaller model architectures, when compared to selecting high-confidence examples. Our framework bridges the gap between theoretical foundations and practical LLM behaviors, providing both explanatory power and actionable insights for future model development.
Abstract (translated)
大型语言模型（LLM）的快速发展需要一个严格的理论框架来解释其实验成功的原因。尽管在理解LLM行为方面取得了显著进展，但现有的理论框架仍然缺乏统一的数学视角来解释新兴现象。我们首次建立了LLM架构与算法信息论（AIT）之间的正式联系，并证明了两个基本结果：(1) 通过损失最小化实现程序长度优化的过程计算上近似于Solomonoff先验；(2) 下一令牌预测实现了对Solomonoff归纳的近似实施。我们利用AIT提供了一个统一的理论解释，涵盖了上下文学习、少量样本学习以及规模法则。此外，我们的理论见解为少样本示例选择提供了基于原则的方法，优先考虑模型表现出较低预测置信度的情况下的样本。通过在多种文本分类基准上的实验表明，与选取高置信度示例相比，该策略能显著提高较小架构模型的性能。我们的框架弥合了理论基础和实际LLM行为之间的差距，为未来模型的发展提供了解释力和实用性的洞察。
URL
https://arxiv.org/abs/2505.15784
