2025-11-12T10:58:10.220342

AI Agents as Universal Task Solvers

Achille, Soatto
AI reasoning agents are already able to solve a variety of tasks by deploying tools, simulating outcomes of multiple hypotheses and reflecting on them. In doing so, they perform computation, although not in the classical sense -- there is no program being executed. Still, if they perform computation, can AI agents be universal? Can chain-of-thought reasoning solve any computable task? How does an AI Agent learn to reason? Is it a matter of model size? Or training dataset size? In this work, we reinterpret the role of learning in the context of AI Agents, viewing them as compute-capable stochastic dynamical systems, and highlight the role of time in a foundational principle for learning to reason. In doing so, we propose a shift from classical inductive learning to transductive learning -- where the objective is not to approximate the distribution of past data, but to capture their algorithmic structure to reduce the time needed to find solutions to new tasks. Transductive learning suggests that, counter to Shannon's theory, a key role of information in learning is about reduction of time rather than reconstruction error. In particular, we show that the optimal speed-up that a universal solver can achieve using past data is tightly related to their algorithmic information. Using this, we show a theoretical derivation for the observed power-law scaling of inference time versus training time. We then show that scaling model size can lead to behaviors that, while improving accuracy on benchmarks, fail any reasonable test of intelligence, let alone super-intelligence: In the limit of infinite space and time, large models can behave as savants, able to brute-force through any task without any insight. Instead, we argue that the key quantity to optimize when scaling reasoning models is time, whose critical role in learning has so far only been indirectly considered.
academic

AI Agents as Universal Task Solvers: It's All About Time

基本信息

  • 论文ID: 2510.12066
  • 标题: AI Agents as Universal Task Solvers: It's All About Time
  • 作者: Alessandro Achille, Stefano Soatto (AWS Agentic AI)
  • 分类: cs.AI, cs.LG
  • 发表时间: September 12, 2025 (arXiv preprint)
  • 论文链接: https://arxiv.org/abs/2510.12066

摘要

本文重新审视了AI智能体在学习推理中的角色，将其视为具有计算能力的随机动力学系统，并强调时间在推理学习基础原理中的关键作用。作者提出从经典的归纳学习转向转导学习，目标不是逼近历史数据的分布，而是捕获数据中的算法结构以减少解决新任务所需的时间。研究表明，通用求解器使用历史数据能实现的最优加速与其算法信息密切相关，并为观察到的推理时间与训练时间的幂律缩放提供了理论推导。

研究背景与动机

核心问题

  1. AI智能体的通用性：链式思维推理是否能解决任何可计算任务？
  2. 学习机制：AI智能体如何学会推理？是模型规模还是训练数据规模的问题？
  3. 缩放法则的本质：当前基于准确率的缩放法则是否真正反映了智能？

研究动机

传统机器学习专注于归纳学习（inductive learning），即拟合标记数据的函数并期望泛化到相似输入。但在智能体设置中，我们需要预训练模型能够处理新任务的特定实例并解决该实例。这种过程被称为转导（transduction）：在测试时，模型利用所有可用数据并主动推理来解决手头的任务。

现有方法局限性

  • 当前缩放法则使用预测误差作为智能的代理，忽略了时间成本
  • 随着模型变得更强大，学习变得不必要，因为模型可以依赖穷举计算而非从数据结构中获得的洞察
  • 无限资源的极限下，模型可以通过暴力破解任何任务而无需任何学习

核心贡献

  1. 理论框架：将AI智能体建模为随机动力学系统，扩展了通用求解器理论从图灵机到一般动力学系统
  2. 时间概念重新定义：引入"proper time"概念，解决随机系统中时间定义的非平凡问题
  3. 信息-速度等价性：证明了信息就是速度（Theorem 1.1: log speed-up = I(h : D)）
  4. 缩放法则理论：为推理模型中观察到的推理时间与训练时间幂律缩放提供理论推导
  5. 缩放法则反转：揭示了准确率-规模图的误导性，提出时间优化的重要性

方法详解

任务定义

研究聚焦于可验证任务（verifiable tasks）：每个问题实例x配对一个任务特定函数f(x,y)，可以交互式地验证或评分任何候选解y。

核心理论构建

1. 动力学系统作为计算

将LLM的链式思维推理建模为随机动力学系统：

  • 状态空间：S中的状态s
  • 轨迹：h = (s₁, ..., sₙ)，长度T(h) = n
  • 转移概率：ν(sₜ₊₁|sₜ)
  • 轨迹概率：ν(h) = ∏ν(sₜ₊₁|sₜ)

2. Proper Time定义

Definition 2.3: 对于随机动力学系统，从输入x到输出a的proper time定义为：

τᵥ(x ↓ a) = min[T(h)/ν(h|x)]

其中最小值取遍所有从enc(x)开始并以输出a终止的轨迹h。

Theorem 2.4: 存在确定性图灵机Mᵥ，使得：

T_Mᵥ(x ↓ a) ≤ 2τᵥ(x ↓ a)

3. 通用求解器存在性

Theorem 3.2: 给定任何编码程序的分布m，存在动力学系统Uₘ，对于任何求解器A：

τ_Uₘ(x ↓ y) ≤ C'_A 2^(-log m(A)) τ_A(x ↓ y)

技术创新点

1. 信息-速度等价性

Theorem 4.2: 搜索算法在观察数据后的对数加速为：

log[τᵥ(h)/τᵥ(h|D)] = Iᵥ(h : D)

其中Iᵥ(h : D)是ν-算法互信息。

2. Hilberg猜想的推广

Definition 4.4: 广义Hilberg猜想（GHC）缩放：

I(Xₙ : Yₘ) ∝ n^β + m^β - (m+n)^β

3. 时间缩放法则

Theorem 4.5: 在足够大的数据集D（n个token）上训练获得的对数加速为：

log[τᵥ(h)/τᵥ(h|D)] = T(h)^β - βT(h)/n^(1-β)

实验设置

理论验证

论文主要是理论性工作，通过数学证明验证各个定理。实验验证主要体现在：

  1. Santa Fe过程构建：显式构建满足GHC缩放的数据生成过程
  2. 幂律缩放的理论推导：为经验观察到的推理时间与训练时间幂律关系提供理论基础

关键参数

  • β ∈ (0,1)：复杂度参数，控制"有用事实"分布的长尾性
  • 对于自然语言：β ≈ 0.5，意味着n ∝ L²的缩放关系

实验结果

主要理论结果

1. 最大加速界限

Theorem 4.3: 使用过程q生成的数据能获得的最大加速为：

log[τᵥ(h)/τᵥ(h|D)] ≤ K(q)

其中K(q)是q的Kolmogorov复杂度。

2. 学习与时间优化

Theorem 1.5:

  • 没有时间惩罚时，最优推理可以通过暴力破解实现而无需学习
  • 任何优化时间的系统必须从历史数据中学习至少I(h : D) = log speed-up比特

3. 内存-时间权衡

Corollary 4.7: 假设内存使用最优，作为已用内存函数的加速为：

log[τᵥ(h)/τᵥ(h|D)] = T(h)^β - T(h)/M^(1/β-1)

关键发现

  1. 复杂性悖论：与奥卡姆剃刀原理相反，复杂的数据生成过程实际上更有利于学习
  2. 缩放法则反转：随着模型规模增大，可能进入"学者模式"（savant regime），通过暴力计算获得高准确率但缺乏真正洞察
  3. 时间的核心地位：智能行为应该通过单位时间/计算的误差减少来衡量，而非仅仅是准确率

相关工作

主要研究领域

  1. Solomonoff归纳与通用搜索：基于Levin和Solomonoff的经典工作
  2. 转导学习：Vapnik等人的转导推理框架
  3. 上下文学习：现代LLM的上下文学习能力
  4. 算法信息理论：Kolmogorov复杂度和算法互信息

本文贡献

  • 将通用搜索理论从图灵机扩展到一般随机动力学系统
  • 提出时间在学习中的基础作用，挑战Shannon信息论的传统观点
  • 为LLM的推理能力提供理论基础

结论与讨论

主要结论

  1. 时间是智能的核心：真正的智能应该优化时间效率，而非仅仅追求准确率
  2. 学习的本质是加速：在转导设置中，学习的价值在于减少解决未见任务的时间
  3. 复杂性的价值：复杂的数据生成过程为学习提供更多机会
  4. 缩放策略重新思考：应该优化时间而非单纯的模型规模

局限性

  1. 理论性质：主要是理论工作，缺乏大规模实证验证
  2. 假设限制：依赖于GHC缩放假设，实际数据可能不完全符合
  3. 可计算性问题：某些理论结果涉及不可计算量（如Kolmogorov复杂度）

未来方向

  1. 实证验证：在实际LLM系统中验证理论预测
  2. 算法设计：基于理论洞察设计更好的训练和推理算法
  3. 评估指标：开发考虑时间成本的智能评估指标

深度评价

优点

  1. 理论深度：提供了AI智能体推理能力的深层理论基础
  2. 概念创新：重新定义了学习的目标（从准确率到时间效率）
  3. 数学严谨：证明完整，逻辑清晰
  4. 实际意义：为当前LLM缩放策略提供重要反思

不足

  1. 实证缺乏：理论结果需要更多实验验证
  2. 复杂性：数学内容较为抽象，实际应用门槛较高
  3. 假设强度：某些关键假设（如GHC）的普适性有待验证

影响力

  1. 理论贡献：为AI推理研究提供新的理论框架
  2. 实用价值：指导未来AI系统的设计和评估
  3. 范式转换：可能推动从准确率导向到效率导向的研究转变

适用场景

  • 大规模语言模型的训练策略设计
  • AI智能体的推理能力评估
  • 计算资源受限环境下的模型优化
  • 自动推理系统的理论分析

参考文献

论文引用了丰富的相关工作，包括：

  • Levin (1973): Universal sequential search problems
  • Solomonoff (1964): A formal theory of inductive inference
  • Hilberg (1990): 关于文本冗余信息的经典工作
  • 现代深度学习和LLM相关研究

这篇论文为AI智能体的推理能力提供了深刻的理论洞察，特别是强调了时间在学习中的核心作用。虽然主要是理论工作，但其观点可能对未来AI系统的设计产生重要影响。