Measuring in-context algorithmic reasoning in language models against an exact Bayes-optimal standard
作者: Hector Zenil, Luan Ozelim
分类: cs.LG, cs.AI
发布日期: 2026-08-03
💡 一句话要点
提出F-ICL基准以评估语言模型的算法推理能力
🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)
关键词: 算法推理 语言模型 贝叶斯最优 上下文学习 程序生成 评估基准 推理能力 机器学习
📋 核心要点
- 现有的语言模型评估方法缺乏准确的归纳推理标准，难以判断模型是否具备真正的算法推理能力。
- 论文提出F-ICL基准，通过穷举程序并计算贝叶斯最优后验，为模型提供了一个确切的评估标准。
- 实验表明，尽管模型在多个配置下表现良好，但大多数模型的输出分布仍未达到贝叶斯最优水平。
📝 摘要（中文）
在大型语言模型是否具备真正的算法推理能力或仅仅是模式完成的问题上，现有基准缺乏准确的归纳推理标准。本文提出了F-ICL，一个提供确切标准的上下文学习基准。通过对所有1.5亿个长度不超过13的程序进行穷举，并在有界的通用先验下计算贝叶斯最优后验，评估模型的分布与最优分布的接近程度。实验结果显示，尽管模型在105种配置下的正确回答率高达92%，但大多数模型的分布仍远离最优解。F-ICL作为一个开放的可重复基准和工具包被发布。
🔬 方法详解
问题定义：本文旨在解决大型语言模型在算法推理能力评估中的标准缺失问题。现有方法无法准确判断模型的推理能力与模式完成能力的区别。
核心思路：论文通过引入F-ICL基准，提供一个确切的评估标准，利用穷举法生成程序并计算贝叶斯最优后验，以此评估模型的推理能力。
技术框架：整体流程包括程序的穷举生成、贝叶斯最优后验的计算、模型输出分布的评估，以及与最优解的比较。主要模块包括程序生成模块、后验计算模块和评估模块。
关键创新：F-ICL基准的提出是本研究的核心创新，它为语言模型的算法推理能力提供了一个明确的评估标准，区别于以往的模糊评估方法。
关键设计：在技术细节上，使用了Turing完备的机器F，并通过对称补充生成sF，以消除输出极性偏差。模型的评估基于与最优解的接近程度，采用了比特补充对比的方式来隔离模型的归纳偏差。
🖼️ 关键图片
📊 实验亮点
实验结果显示，在105种配置下，模型的正确回答率高达92%。然而，46个模型中有45个的输出分布远离贝叶斯最优解，且其行为受限于低阶前缀统计。这一发现揭示了模型在推理能力上的不足。
🎯 应用场景
该研究的潜在应用领域包括自然语言处理、智能问答系统和自动化推理等。通过提供一个准确的评估标准，F-ICL可以帮助研究人员更好地理解和改进语言模型的推理能力，从而推动相关技术的发展和应用。
📄 摘要（原文）
Whether large language models perform genuine algorithmic reasoning or mere pattern completion is hard to test, because most benchmarks lack a ground truth for correct inductive inference. We introduce F-ICL, an in-context-learning benchmark that supplies one exactly. Using the Turing-complete machine F, complement-symmetrised into sF to remove output-polarity bias, we exhaustively enumerate all 1.5 billion programs of length $L\le13$ and compute the Bayes-optimal posterior in closed form under a bounded universal (Levin--Solomonoff) prior; models are scored by how closely their served distributions approach it at matched evidence. Each task is paired with its bitwise complement, on which the optimum scores identically, so an original-twin gap isolates the model's inductive bias. Across 105 serving configurations spanning 37 open models (0.8B--675B) and frontier systems from four laboratories, models answer up to 92\% of queries correctly, yet 45 of 46 models yield distributions farther from the optimum than a keystroke reference, and their behaviour is bracketed by low-order prefix statistics fitted only on visible evidence. That reference is itself an algorithmic mixture, induced by a print-only machine with no loops, so the panel's implied measure sits closer to a loop-free mixture than to the loop-bearing optimum, independently of the reference machine. Updating is also non-monotone, which no prior explains: a Bayes-rational solved set can only grow in this realisable, noiseless setting, yet added examples produce $6{,}545$ solved-to-unsolved transitions against $13{,}702$ gains. The gap is not predicted by accuracy (Spearman $ρ=-0.19$, $p=0.21$), does not close with scale or across frontier generations in the serving modes that expose distributions, and is widened by instruction and reasoning post-training. F-ICL is released as an open, reproducible benchmark and toolkit.