测试大模型在未见自动机任务中的推理能力，发现其易犯语义错误。
Beyond Memorization: Testing LLM Reasoning on Unseen Theory of Computation Tasks
- 设计新基准，包含手造与生成的未见自动机问题
- 未见任务准确率下降30%-64%，主要因约束误解和星号语义错误
- 多种提示法均无法解决全局不一致，暴露深层推理缺陷
大型语言模型（LLMs）在形式语言任务上表现优异，但其能力是否源于真正的符号推理，还是对熟悉结构的模式匹配仍不明确。本文提出一个针对确定性有限自动机（DFA）从正则语言构造的基准，包含事实知识题、公开来源的已见构造题，以及两类未见问题：具有多重交互约束的手造实例，以及通过Arden定理系统生成的问题。模型在事实题上达完美准确率，在已见任务上准确率为84-90%。但在未见问题上准确率骤降30-64%，失败原因包括对语言约束的系统性误解、对克林星（Kleene-star）语义处理不当，以及未能保持全局一致性。评估了三阶段提示协议，虽能修正浅层错误，但无法可靠修复全局不一致或结构缺陷的自动机。在多种提示策略（直接、思维链、思维树）下，错误持续存在，揭示了模型生成语法上合理但语义上错误的DFA之间的根本差距。
原文摘要 · Abstract (English)
Large language models (LLMs) have demonstrated strong performance on formal language tasks, yet whether this reflects genuine symbolic reasoning or pattern matching on familiar constructions remains unclear. We introduce a benchmark for deterministic finite automata (DFA) construction from regular languages, comprising factual knowledge questions, seen construction problems from public sources, and two types of unseen problems: hand-crafted instances with multiple interacting constraints and systematically generated problems via Arden's theorem. Models achieve perfect accuracy on factual questions and 84-90% on seen tasks. However, accuracy drops sharply on unseen problems (by 30-64%), with failures stemming from systematic misinterpretation of language constraints, incorrect handling of Kleene-star semantics, and a failure to preserve global consistency. We evaluate a three-stage hint protocol that enables correction of shallow errors but does not reliably resolve globally inconsistent or structurally flawed automata. Our analysis across multiple prompting strategies (direct, Chain-of-Thought, Tree-of-Thought) reveals that errors persist regardless of prompting approach, exposing a fundamental gap between LLMs' ability to generate syntactically plausible DFAs and their capacity for semantically correct formal reasoning.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。