Beyond Pattern Matching: Tracing Symbolic Reasoning Failures in LLMs to Their Mechanistic Origin

Large language models (LLMs) have shown strong performance across reasoning benchmarks, yet whether this reflects genuine symbolic reasoning or sophisticated pattern matching remains actively debated. We investigate this question using regular languages, the simplest class of formal languages, where operator semantics are unambiguous and correctness is exactly checkable. Our work proceeds in three stages. First, by applying a cross-consistency protocol to frontier models (GPT-5.2, Grok-4.1, Gemini-2.5) and open-weight Qwen 2.5 models (1.5B, 7B, 14B), we show that models cannot reliably interpret regular expressions: they describe constraints they then violate in generation and recognition, revealing eleven systematic failure modes that recur across all architectures regardless of scale. Second, when asked to construct deterministic finite automata, these semantic failures propagate into six classes of structural construction errors that persist regardless of construction strategy. Third, we examine if training can fix these failures. Fine-tuning on a purpose-built regex-to-DFA benchmark (22,500 training, 1,000 test examples) recovers near-perfect accuracy on simpler tiers, but a persistent gap remains at the highest complexity tier that no supervision format, curriculum ordering, or model scale closes. Because the gap survives every behavioral intervention, we look inside the model. Mechanistic analysis points to a consistent picture: the outcome is largely predictable from early-layer representations, no individual neuron or localized group implements subset construction, correcting the internal representation at any layer repairs no case beyond a matched control, and inference-time steering recovers at most 2.4 percentage points of the residual gap. Thus, symbolic reasoning failures in LLMs are structural and only partially remediable.