解密LLM算法推理能力：图遍历任务的动态混合评估框架

本研究聚焦LLM是否隐式近似BFS/DFS等经典图遍历算法的核心问题，开发了多维度可解释性评估框架（含scratchpad推理、表示相似性分析、注意力模式分析及混合符号-神经网络系统）。初步发现LLM在部分图结构上表现出与BFS类似的推理模式，但不完全；复杂图场景下性能显著下降；混合系统在一致性和准确性上更优。研究为理解LLM推理机制及神经符号AI方向提供实证依据。

问题本质

大语言模型在复杂问题中表现出"推理"行为，但核心疑问是：它们是真的结构化算法推理，还是仅基于训练数据的模式匹配？这一区分决定其在需严格逻辑保证任务中的可靠性。

核心研究问题

本项目针对图遍历领域，探究：

• LLM是否遵循BFS/DFS等结构化推理路径？
• 模型在不同图结构上的表现差异？
• 混合符号+神经网络系统能否提升推理一致性与准确性？

选择图遍历的原因

图遍历算法定义明确可验证，图结构变体丰富（树、网格等），且是众多实际推理任务的基础组件。

研究者设计了综合评估框架，包含四类技术：

1. Scratchpad-based推理评估

要求模型显式写出中间步骤，可追踪推理路径、对比标准算法轨迹、识别错误模式与回溯行为。

2. 表示相似性分析（RSA）

计算模型内部表征与算法执行状态的相似度：提取隐层激活，计算与算法状态向量的相关性矩阵，生成RSA热图可视化对应模式。

3. 注意力模式分析

分析Transformer注意力权重分布：模型是否关注相邻节点？注意力是否遵循拓扑结构？不同注意力头是否承担不同功能？

4. 混合符号-神经网络规划器

对比实验系统：符号组件执行BFS/A*算法，神经组件处理自然语言输入或提供启发式评估，协同工作测试性能与可解释性。

项目基于Python和PyTorch构建，主要依赖：

• Hugging Face Transformers：加载预训练模型
• PyTorch：推理与梯度计算
• NumPy/SciPy：数值计算与统计分析
• 自定义图环境：生成与操作多种图结构

核心代码模块：

• graphs.py：图环境定义与可视化
• evaluation_runner.py：实验主程序
• planner.py：混合规划器实现
• attention_analysis.py：注意力模式分析
• rsa_analysis.py：表示相似性计算
• scratchpad_runner.py：逐步推理评估

初步实验现象

• 部分BFS相似性：LLM在某些图结构上表现出与BFS类似的推理模式，但相似性不完全；
• 复杂图性能下降：图结构复杂度增加时，模型推理一致性与准确性显著下降；
• 混合系统优势：符号+神经混合系统在一致性和准确性上表现更优。

研究启示

• LLM可能学到近似算法的隐式策略，但学习不完整；
• 纯神经网络方法在需严格逻辑保证的任务中存在局限；
• 神经-符号混合架构是提升推理可靠性的可行路径。

应用价值

• 模型评估：为LLM推理能力提供标准化评估基准；
• 架构改进：指导设计更适合算法推理的模型架构；
• 混合系统开发：为神经符号AI系统设计提供实证依据。

未来方向

• 扩展到更大规模的语言模型；
• 改进推理评估指标；
• 将方法应用于实际规划任务。

本研究通过严谨实验设计与多维度分析，为LLM算法推理能力提供了有价值的实证数据。既不支持"LLM仅为模式匹配器"的悲观观点，也不认为其已掌握真正算法推理。揭示的图景是：LLM学到算法推理的某些方面，但学习不完整且复杂场景易失效。未来可通过优化训练方法、架构设计或混合系统，提升AI推理的可靠性与可解释性。