Large Language Models as Computable Approximations to Solomonoff Induction

📄 arXiv: 2505.15784v1 📥 PDF

作者: Jun Wan, Lingrui Mei

分类: cs.LG, cs.AI, cs.CL

发布日期: 2025-05-21

备注: Both authors contributed equally

💡 一句话要点

将大语言模型视为Solomonoff归纳的可计算近似，并提出一种新的少样本选择方法。

🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)

关键词: 大语言模型 Solomonoff归纳 算法信息论 少样本学习 上下文学习

📋 核心要点

  1. 现有理论框架难以用统一的数学视角解释大语言模型中的涌现现象，例如上下文学习和少样本学习。
  2. 论文核心思想是将大语言模型视为Solomonoff归纳的可计算近似，通过算法信息论建立理论联系。
  3. 实验表明，选择模型预测置信度低的样本进行少样本学习，能显著提升模型在文本分类任务上的性能。

📝 摘要（中文）

大语言模型（LLMs）的快速发展需要一个严谨的理论框架来解释其经验上的成功。虽然在理解LLM行为方面已经取得了显著进展，但现有的理论框架在通过统一的数学视角解释涌现现象方面仍然是分散的。我们通过证明两个基本结果，建立了LLM架构与算法信息论（AIT）之间的第一个正式联系：（1）训练过程通过损失最小化（解释为程序长度优化）在计算上近似Solomonoff先验，以及（2）下一个token预测实现了近似Solomonoff归纳。我们利用AIT为上下文学习、少样本学习和缩放定律提供了一个统一的理论解释。此外，我们的理论见解导致了一种基于原则的少样本示例选择方法，该方法优先选择模型表现出较低预测置信度的样本。通过在各种文本分类基准上的实验，我们证明，与选择高置信度示例相比，这种策略产生了显著的性能改进，特别是对于较小的模型架构。我们的框架弥合了理论基础和实际LLM行为之间的差距，为未来的模型开发提供了解释能力和可操作的见解。

🔬 方法详解

问题定义：现有理论框架难以解释大语言模型涌现的上下文学习、少样本学习和缩放定律等现象，缺乏统一的数学视角。现有方法在少样本学习中，通常选择模型预测置信度高的样本，但这种方法可能并非最优。

核心思路：论文的核心思路是将大语言模型与算法信息论（AIT）联系起来，证明LLM的训练过程可以近似为Solomonoff先验的计算近似，而next-token预测则近似于Solomonoff归纳。基于此，提出一种新的少样本示例选择方法，优先选择模型预测置信度低的样本。

技术框架：该研究主要分为两个部分：理论分析和实验验证。理论分析部分，论文建立了LLM架构与AIT之间的联系，证明了LLM训练过程和预测过程分别近似于Solomonoff先验和Solomonoff归纳。实验验证部分，论文在多个文本分类基准上测试了提出的少样本示例选择方法，并与选择高置信度样本的方法进行了比较。

关键创新：论文最重要的创新点在于建立了LLM与AIT之间的正式联系，为理解LLM的涌现现象提供了一个统一的理论框架。此外，提出的基于预测置信度的少样本示例选择方法，与传统方法选择高置信度样本的思路相反，是一种反直觉但有效的策略。

关键设计：论文的关键设计在于将损失最小化解释为程序长度优化，从而将LLM的训练过程与Solomonoff先验联系起来。在实验中，论文使用了多种文本分类数据集，并比较了不同模型架构下，选择高置信度样本和低置信度样本的性能差异。具体的损失函数和网络结构等细节取决于所使用的具体LLM模型。

🖼️ 关键图片

fig_0

📊 实验亮点

实验结果表明，在多种文本分类基准上，选择模型预测置信度低的样本进行少样本学习，能够显著提升模型性能，尤其是在较小的模型架构上。与选择高置信度样本相比，该方法在某些数据集上取得了超过5%的性能提升。这一结果验证了论文提出的理论框架的有效性，并为少样本学习提供了一种新的思路。

🎯 应用场景

该研究成果可应用于提升大语言模型的少样本学习能力，尤其是在资源受限的场景下。通过选择更具信息量的样本，可以减少对大量标注数据的依赖，降低训练成本。此外，该理论框架有助于更好地理解和解释LLM的行为，为未来的模型设计和优化提供指导。

📄 摘要（原文）

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.