LLM看似能判图同构，实则只靠标签模式，不懂拓扑结构。
Detecting Differences Is Not Understanding Structure: Large Language Models Fail at Graph Isomorphism
- 用重标号节点测试，发现模型无法识别同构图
- 准确率看似接近100%，实为依赖标签模式而非结构理解
- 适合关注LLM推理局限性的研究人员
大型语言模型（LLMs）在多种推理任务中表现优异，但其在图结构推理方面的能力尚不明确。本文研究了LLMs是否真正理解图同构——图论中的基本问题。尽管LLMs在同构检测任务上达到接近完美的准确率，但我们发现这种表现是虚假的：当相同图以不同节点标签排列呈现时，LLMs无法识别其同构性。这表明LLMs依赖的是表面模式而非对抽象图结构的推理。由于置换不变性是有效结构推理的基本要求，这些结果说明，图推理基准上的成功不应被解释为对拓扑结构的真实理解。
原文摘要 · Abstract (English)
Large language models (LLMs) have shown impressive performance on diverse reasoning tasks, yet their capacity for structural reasoning in graphs remains unclear. We investigate whether LLMs can genuinely understand graph isomorphism -a fundamental problem in graph theory. While LLMs achieve near-perfect accuracy on isomorphism detection, we show this performance is illusory. When identical graphs are presented with permuted node labels, LLMs fail to identify their isomorphism. This finding suggests that LLMs exploit patterns rather than reasoning about abstract graph structure. Since permutation invariance is a fundamental requirement for valid structural reasoning, these results indicate that success on graph reasoning benchmarks should not be interpreted as evidence of genuine topological understanding.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。