Chain-of-thought (CoT) supervision has become a default assumption in fine-tuning large language models for reasoning tasks, with the intuition being that exposing models to intermediate reasoning steps leads to deeper learning than training on answers alone. We challenge this assumption. We introduce answer backtrackability, a measurable quantity capturing the degree to which a question can be reconstructed from its answer, and argue it is a key determinant of whether CoT supervision helps or hurts during fine-tuning. To test this, we construct two novel benchmarks derived from automata theory (NFA and DFA), where answers are transition tables from which the question is largely recoverable, and fine-tune three LLMs using LoRA on CoT and No-CoT versions of five datasets: GSM8K, MathInstruct, MATH, and our two formal-language benchmarks. On mathematical datasets, CoT consistently outperforms No-CoT. Within MathInstruct, Program-of-Thought (PoT) problems, where executable code answers are high-backtrackability, favour No-CoT, while CoT-format problems favour CoT. On our benchmarks, the pattern reverses: No-CoT outperforms CoT across all models and difficulty tiers. When the answer encodes sufficient structure to reconstruct the reasoning process, intermediate supervision adds noise rather than signal.

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.