Beyond Memorization: Testing LLM Reasoning on Unseen Theory of Computation Tasks
This work addresses a fundamental gap in LLMs' reasoning capabilities for formal tasks, which is crucial for researchers and developers in AI and theoretical computer science, though it is incremental in highlighting limitations rather than proposing a new solution.
The paper tackled the problem of whether LLMs perform genuine symbolic reasoning or pattern matching on formal language tasks by testing them on unseen deterministic finite automata (DFA) construction problems, finding that accuracy dropped sharply by 30-64% on unseen tasks compared to seen ones, with errors persisting across various prompting strategies.
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.