大语言模型（LLM）遇到了一个意想不到的"推理滑铁卢"。
简单算法成LLM难题
一个看似简单的二叉树反转问题，竟然让包括GPT-o1在内的顶尖AI模型束手无策。
这个挑战来自Twitter用户@VictorTaelin，他提出了一个经过微调的二叉树反转问题，并悬赏1万美元给任何能证明LLM可以解决这个问题的人。
乍一看，这似乎是一个常见的编程面试题。但@VictorTaelin巧妙地增加了几个关键限制：
必须反转键值（"位反转排列"） 必须是无依赖、纯递归函数 函数类型必须是 Bit -> Tree -> Tree
这些看似微小的改动，却让问题变得异常棘手。@VictorTaelin解释道：
"这些小变化足以将这个问题移出'记忆解决方案区'。它不在互联网上。猜猜怎么着？这足以让它对现代AI完全无法解决。无论你如何提示它，都无法解决。"
为了证明他的观点，@VictorTaelin提供了一个详细的问题描述和测试用例：
from typing import Union, Tuple
Nat = int
Bit = bool
Tree = Union[Tuple['Tree', 'Tree'], Nat]
# Your goal is to implement an 'invert' function that performs a bit-reversal
# permutation on a Tree, respecting the following limitations:
# 1. You can NOT define or use any function other than 'invert'.
# 2. You can NOT use any type not defined above (Nat, Bit and Tree).
# 3. You can NOT use loops (but you can call 'invert' recursively).
# 4. You can NOT use mutability. It must be a pure function.
# 5. You can NOT use primitive Python operators or functions.
# 6. You can use 1 bit of state (as an extra argument).
# 7. You can only use the operations allowed below.
#
# Operations allowed:
# - Destructing (left, right = value)
# - Variables (x = value)
# - Branching (if x: ... else: ...)
# - Recursion (invert(_, _))
# - isinstance(value, int)
#
# All other operations are not allowed.
#
# Example:
# input = ((((0,1),(2,3)),((4,5),(6,7))),)
# output = ((((0,4),(2,6)),((1,5),(3,7))),)
# Because that's the bit-reversal permutation of the original tree.
#
# Now, complete the function below with a valid implementation of 'invert':
def invert(bit: Bit, tree: Tree) -> Tree:
# Your implementation here
pass
# A test:
tree: Tree = ((((0,1),(2,3)),((4,5),(6,7))), (((8,9),(10,11)),((12,13),(14,15))))
print(invert(True, tree))
这个问题的难点在于，它不仅要求反转树的结构，还要求对键值进行位反转排列。而且，解决方案必须是一个纯递归函数，不允许使用任何额外的辅助函数或循环。
问题描述的中文翻译：
你的目标是实现一个invert函数，对树执行位反转置换，需遵循以下限制：你不能定义或使用除invert之外的任何函数。你不能使用上述定义以外的任何类型（只能使用Nat，Bit和Tree）。你不能使用循环（但可以递归调用invert）。你不能使用可变性。它必须是一个纯函数。你不能使用任何原生Python操作符或函数。你可以使用1位的状态（作为一个额外的参数）。你只能使用下列允许的操作：解构（如left, right = value）变量（如x = value）分支（如if x: ... else: ...）递归调用（如invert(_, _)）isinstance(value, int)检查类型除了这些操作之外，其他操作都不允许使用。示例：输入：(((((0,1),(2,3)),((4,5),(6,7)))) 输出：((((0,4),(2,6)),((1,5),(3,7)))) 因为这是原树的位反转置换。接下来请在下面提供一个符合要求的invert函数的有效实现：
Taelin（@VictorTaelin）还贴心地给出了可以参考的prompt，见：
https://gist.github.com/VictorTaelin/45440a737e47b872d7505c6cda27b6aa
并为了刺激大家挑战，Taelin 放出豪言悬赏一万美金：
我愿意给任何能正确实现此功能的人 1 万美元。无论它思考多久，它都无法工作。（解决方案是 7 行代码！）
多位网友尝试使用各种LLM来解决这个问题，但都以失败告终。即使是最新的GPT-o1模型，也无法给出正确的解决方案。
这个看似简单的问题，为什么会让强大的LLM们集体"翻车"呢？
挑战的核心：不只是反转二叉树
这个挑战的核心，远不止是简单的二叉树反转。
@VictorTaelin精心设计的限制条件，巧妙地将问题推到了LLM的"舒适区"之外。让我们深入分析一下这个挑战的关键点：
位反转排列：这不是简单的树结构反转，而是要求对节点的键值进行位反转排列。例如：
输入：((((0,1),(2,3)),((4,5),(6,7))),)
输出：((((0,4),(2,6)),((1,5),(3,7))),)
这个要求大大增加了问题的复杂性，因为它需要在递归过程中同时处理树的结构和节点的值。
无依赖、纯递归函数：这个限制禁止了使用任何辅助函数或全局变量。所有的逻辑都必须在单一的
invert函数中完成。这就要求解决方案必须非常精巧，能在递归调用中携带所有必要的信息。函数类型
Bit -> Tree -> Tree：这个签名暗示了解决方案需要使用一个额外的位参数来控制递归过程。这个位参数的巧妙使用是解决问题的关键。严格的操作限制：只允许使用解构、变量赋值、条件分支、递归调用和
isinstance检查。这些限制排除了许多常见的编程技巧，迫使解决方案必须非常"纯粹"。
一个符合所有这些限制的正确解决方案可能如下所示：
def invert(bit: Bit, tree: Tree) -> Tree:
if isinstance(tree, int):
return tree
left, right = tree
if isinstance(left, int):
return tree
a, b = left
c, d = right
if bit:
return (invert(False, (a, c)), invert(False, (b, d)))
else:
return invert(True, (invert(False, left), invert(False, right)))
这个解决方案看似简单，但实际上蕴含了深刻的递归思想和位操作逻辑。它巧妙地利用了额外的位参数来控制递归的行为，在不使用任何额外函数或循环的情况下完成了复杂的树结构和键值的转换。
那为什么这个问题对LLM而言会如此棘手呢？
模式识别的局限性：LLM擅长识别和复制已知的代码模式。但这个问题需要创造性地组合多个概念，超出了简单的模式匹配范畴。
递归推理的挑战：虽然LLM可以处理简单的递归，但这个问题需要在递归过程中同时处理多个变化（树结构和键值），这大大增加了推理的难度。
抽象思维的缺失：解决这个问题需要高度的抽象思维，要理解位操作如何影响整个递归过程。这种抽象推理能力是当前LLM所欠缺的。
创新解决方案的生成：这个问题要求一个独特的、之前可能从未出现在训练数据中的解决方案。LLM更擅长组合和适应已知解决方案，而不是创造全新的方法。
这个挑战清楚地表明，即使是最先进的LLM，在面对需要真正的逻辑推理和创新思维的问题时，仍然存在明显的局限性。
专家激烈讨论
这个挑战引发了AI社区的热烈讨论。专家们对LLM的能力和局限性展开了深入的探讨。
首先，一些专家对@VictorTaelin的断言表示怀疑。@Michael_Druggan就直言不讳地问道：
"永远不能？真的吗？你没看到我们正在前进的方向吗？下一代可能会解决这个问题，再下一代会解决更难的问题。预测'AI永远不会做X'的记录一直很糟糕。"
@VictorTaelin坚持自己的观点，回应道：
"不，它不会解决这个问题。现在不会，将来也不会。这就是这篇文章的全部要点。是的，AI会帮助人类做CS。它们在编码方面很棒。它们让我们的生产力提高了10倍。它们可以自动化许多工作。然而，它们无法进行逻辑推理。这些都是事实。"
然而，也有人提出了不同的看法。@CollinCusce指出：
"我们已经建立了形式化的推理系统。它们只是不能很好地扩展。如果让LLM将解决方案转换为，比如说，Prolog，然后使用Prolog进行推理某些问题，甚至进行形式验证检查。我不明白为什么多模型系统将来不能做到这一点。"
或许，未来AI系统可能通过结合不同的模型和方法来克服当前的局限性？
将来的事将来再说，看来现在这一万美金还是拿不走啊！
有趣的是，NYU教授、Meta首席AI科学家Yann LeCun也参与了讨论。他强调：
"值得重复的是：不要混淆检索和推理。不要混淆死记硬背和理解。不要混淆积累的知识和智能。"
那么，LLM的能力究竟在哪里？它们是真正的"智能"，还是仅仅是高级的模式匹配器？
LLM的局限性：记忆vs推理
LLM的强大能力令人惊叹，但@VictorTaelin的挑战暴露了它们的一个关键局限：真正的逻辑推理能力。
@VictorTaelin 深入阐述了这个问题：
"LLM智能的幻觉来自于它们的庞大规模。很难想象，但这些东西记住了整个互联网。你问它的每一个问题，要么以前已经解决过，要么是现有解决方案的简单组合。但这仍然是一种幻觉。"
"当LLM面对需要新解决方案的问题时——一个原创形式的问题，一个它从未见过的问题——它们就会失败。就这么简单。这就是我的例子所展示的。"
该观点得到了许多专家的支持。
例如，@dragosr提供了一个详细的分析，解释了为什么递归对LLM来说如此困难：
缺乏显式递归机制：LLM基于transformer架构，以前馈方式处理输入数据，没有创建或管理调用栈的能力。 上下文窗口限制：transformer有固定的上下文窗口大小，难以跟踪递归中的多层函数调用。 统计模式识别vs逻辑推理：LLM擅长模仿代码的风格和结构，但不真正理解底层逻辑。 训练数据中的有限接触：递归函数可能只占训练数据中的一小部分。 终止条件的困难：LLM可能无法可靠地生成正确的基本情况或必要的终止逻辑。
这些限制解释了为什么LLM在面对@VictorTaelin的挑战时会失败。
让我们看一个具体的例子来说明这一点。
@KuittinenPetri声称使用Anthropic的Claude 3.5 Sonnet模型成功解决了这个问题。他提供了一个看似符合要求的Python代码：
def invert(bit: Bit, tree: Tree) -> Tree:
if isinstance(tree, int):
return tree
t1, t2 = tree
if isinstance(t1, int):
return tree
t3, t4 = t1
t5, t6 = t2
if bit: return invert(False, (invert(True, t1), invert(True, t2)))
else: return (invert(False, (t3, t5)), invert(False, (t4, t6)))这段代码看起来似乎符合所有的要求：它是递归的，没有使用额外的函数，也没有使用循环。
然而，@VictorTaelin很快指出这个解决方案是完全错误的，无法通过任何测试。
这个例子完美地展示了LLM的局限性。它能够生成看似合理的代码结构，但无法真正理解问题的逻辑核心——如何在递归过程中同时处理树的结构反转和节点值的位反转。
Yann LeCun的观点进一步强调了这一点：
"是的，LLM可以重复它被训练过的答案。所以，任何特定的困难问题，一旦发布，下一次迭代的LLM就会正确回答。但关键是LLM不理解物理世界。"
这揭示了LLM和真正的智能系统之间的根本区别。LLM擅长的是模式匹配和信息检索，而不是逻辑推理和创新问题解决。
@VictorTaelin总结道：
"LLM无法解决任何问题。它只能吐出记忆中的解决方案。如果没有人在网上发布这个解决方案，即使是GPT-6、opus-5或o3也无法解决这个问题。我敢打赌。"
AI真的能取代人类研究者吗？
@VictorTaelin的挑战不仅暴露了当前LLM的局限性，还引发了一个更深层次的问题：AI是否真的能在科研领域取代人类？
这个问题的答案似乎并不那么乐观。
@VictorTaelin强调：
"创造新解决方案的能力意味着LLM不会发明新的科学。是的，它们将彻底改变我们所知的世界。它们将产生比计算机和互联网更大的影响。但是，除非出现新型AI，否则在治愈癌症或制造超导体方面，我们仍然只能靠自己。"
对此，@nihilhackspace指出：
"这看起来像是一个带有限制的简单递归问题。LLM平滑处理这类问题所缺少的唯一东西是保持长期连贯性。"
@VictorTaelin 反驳道：
"不是这样的。o1可以做到这一点，它可以在提出答案之前思考很长时间。然而，它仍然无法解决这个问题。长期推理只是让模型更有可能回忆起正确的解决方案，这很好。但如果它不知道解决方案，就无法回忆起来！"
这揭示了一个关键点：即使未来的LLM在长期推理能力上有所提升，它们仍然可能无法进行真正的创新性思考。
那么，AI在科研领域的角色究竟是什么？
@VictorTaelin给出了他的看法：
"主要观点是，有些解决方案不是现有解决方案的组合，而这些是推进研究所必需的。LLM将自动化99%的工作，我对此很有信心。但我怀疑它们能否自动化研究。"
这暗示了AI和人类研究者之间可能的协作模式。AI可能会在以下方面发挥重要作用：
数据处理和分析：AI可以快速处理和分析大量数据，帮助研究者发现潜在的模式和关联。
文献综述和知识整合：AI可以帮助研究者快速了解特定领域的最新进展，整合来自不同来源的知识。
实验设计优化：AI可以帮助优化实验设计，提高研究效率。
模拟和预测：在某些领域，AI可以进行复杂的模拟和预测，为研究提供新的洞察。
然而，真正的突破性创新、理论构建和跨领域整合可能仍然需要人类研究者的创造力和直觉。
一些研究者提出了结合不同AI技术的可能性。未来AI系统可能通过结合不同的模型和方法来克服当前的局限性。例如，我们可以想象一个系统，它结合了LLM的自然语言处理能力、专门的推理引擎和形式验证工具：
def hybrid_problem_solver(problem_description):
# 使用LLM理解问题并生成初步解决方案
initial_solution = LLM.generate_solution(problem_description)
# 将解决方案转换为形式化语言（如Prolog）
formal_solution = convert_to_formal_language(initial_solution)
# 使用专门的推理引擎验证和优化解决方案
verified_solution = reasoning_engine.verify_and_optimize(formal_solution)
# 使用形式验证工具进行最终检查
if formal_verification_tool.check(verified_solution):
return verified_solution
else:
return "Solution not found or not verifiable"
这种混合方法可能会结合LLM的灵活性和专门系统的严谨性，为更复杂的问题提供解决方案。
然而，即使有了这样的进步，人类研究者的角色仍然是不可或缺的。正如Yann LeCun所说：
"将来会有理解物理世界的模型。它们只是不会是基于文本训练的自回归LLM。"
这也暗示了AI研究的新方向——需要开发全新的架构和学习范式。
延伸阅读
刚刚！Anthropic CEO Dario Amodei 发文：人工智能如何让世界变得更美好【附全文翻译】
Sam Altman最新发文：《The Intelligence Age》
👇
👇
👇
👇
本文同步自知识星球《AGI Hunt》
星球实时采集和监控推特、油管、discord、电报等平台的热点AI 内容，并基于数个资讯处理的 AI agent 挑选、审核、翻译、总结到星球中。
每天约监控6000 条消息，可节省约800+ 小时的阅读成本；
每天挖掘出10+ 热门的/新的 github 开源 AI 项目；
每天转译、点评 10+ 热门 arxiv AI 前沿论文。
星球非免费。定价99元/年，0.27元/天。(每+100人，+20元。元老福利~）
一是运行有成本，我希望它能自我闭环，这样才能长期稳定运转；
二是对人的挑选，鱼龙混杂不是我想要的，希望找到关注和热爱 AI 的人。
欢迎你的加入！
