研究变换器对组合任务的算法外推能力，揭示其内在偏好与计算复杂性限制。
Algorithmic Task Capture, Computational Complexity, and Inductive Bias of Infinite Transformers
- 定义算法捕获：在任意任务规模下可控误差外推，区分逻辑内化与统计插值。
- 实证发现：在2.5个数量级的规模变化中，存在可捕捉与不可捕捉任务的分界。
- 理论证明：无限宽度变换器在高效多项式启发式类中偏向低复杂度算法。
我们形式化定义了组合任务的算法捕获能力，即变换器在任意任务规模下以可控误差和对数样本适应实现外推，提供明确的缩放判据，用于区分逻辑内化与统计插值。在跨越高达2.5个数量级的缩放范围内，我们观察到算法捕获与非捕获的证据。通过分析无限宽变换器在懒惰与丰富两种情形下的行为，我们推导出这些网络能捕获的组合任务在推理时间上的计算复杂度上界。尽管变换器具有通用表达能力，但其归纳偏置倾向于避免高效多项式启发式类中的高复杂度算法，这与在简单组合任务（如归纳头、排序、字符串匹配）中成功捕获的现象一致。
原文摘要 · Abstract (English)
We formally define algorithmic capture of combinatorial tasks as the ability of a transformer to extrapolate to arbitrary task sizes with controllable error and logarithmic sample adaptation, providing a sharp scaling criterion for distinguishing logic internalization from statistical interpolation. Empirically, across scaling ranges spanning up to 2.5 orders of magnitude, we observe evidence of capture and non-capture. By analyzing infinite-width transformers in both the lazy and rich regimes, we derive upper bounds on the inference-time computational complexity of the combinatorial tasks these networks can capture. We show that, despite their universal expressivity, transformers possess an inductive bias that disfavors higher-complexity algorithmic procedures within the efficient polynomial-time heuristic scheme class, consistent with successful capture on simpler combinatorial tasks such as induction heads, sort, and string matching.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。