acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

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.

Primary area:
interpretability and explainable AI
Keywords:
symbolic reasoning, large language models, formal languages, regular expressions, deterministic finite automata, mechanistic interpretability, activation patching, chain-of-thought, LLM evaluation, theory of computation

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_LUQfOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper investigates symbolic reasoning failures in LLMs through regular expression interpretation and DFA construction. The authors identify recurring failure modes, evaluate fine-tuning strategies, and conduct mechanistic analyses to understand why difficult cases remain unresolved. The results suggest that some failures persist despite training and inference-time interventions.

Critical strengths
  1. The paper studies an important question concerning the mechanisms underlying symbolic reasoning failures.
  2. The evaluation uses formally verifiable tasks, providing reliable correctness criteria.
  3. The study combines behavioral evaluations, fine-tuning experiments, and mechanistic analyses in a systematic framework.
Critical weaknesses

1.The mechanistic analysis relies heavily on correlations and averaged activation patching. These experiments do not convincingly establish that the observed failures originate from fundamental limitations in the model's internal representations, weakening the paper's central claim.

2.The curriculum experiments differ from joint training in more than training order, while dataset deduplication does not guarantee language-level uniqueness. These issues weaken the conclusions about generalization and the limits of training-based mitigation.

Questions for authors
  1. Can the authors provide stronger causal evidence, such as instance-matched activation patching, to support the mechanistic conclusions?
  2. Can the curriculum experiments be repeated with identical data composition and supervision formats?
  3. Have the authors checked for semantically equivalent regular expressions across training and evaluation sets?
10 comments
AuthorsOpenReview ↗

Response to Weakness 1 and Question 1

We thank the reviewer for the careful review and for recognising the importance of the question, the use of formally verifiable tasks with exact correctness criteria, and the systematic combination of behavioural evaluation, fine-tuning, and mechanistic analysis. The reviewer asked for three things: instance-matched activation patching, a curriculum experiment with identical data and supervision format, and a check for semantically equivalent regexes across training and test. We ran all three, reported below.

W1 + Q1.

We thank the reviewer for this request. We agree that averaged patching is a weak test: it replaces the representation of the specific regex with an average over different problems, so it cannot show whether an instance-correct state would repair a failure (lines 445–447). We have now run the stronger test the reviewer asks for. On each failing problem, we transplant the internal state of a matched twin that the model solves correctly. No transplant repairs a failure, at any of the 22 layer settings we tested.

Why this test is now possible. The submission noted that its alphabet-swapped variants could not support this test, because none of them was both solved correctly and token-aligned with its failing base (lines 452–454). For this rebuttal, we searched much more widely for twins: we renamed symbols both within the original alphabet and to new symbols, and checked every candidate, one problem at a time, for both a correct solution and exact token alignment.

How twins are built. A twin of a failing Tier 4 problem is the same problem with its symbols renamed. Only the regex symbols and the alphabet list change. The automaton has the same structure, and the rest of the prompt is identical. We keep a twin only if:

  1. its prompt aligns with the failing prompt token for token, differing only at the renamed symbols, so activations can be copied position by position; and
  2. the model solves the twin correctly while still failing the original, checked one problem at a time.

For example, the model fails (0|3)((02+1+++))*2 but solves its twin (2|0)((21+3+++))*1. The two 140-token prompts differ at only 6 positions. We found 14 verified pairs, covering 10 of the 42 failures. These 10 are the failures closest to success, since the model solves the same problem under a different symbol assignment. If any failure could be repaired by supplying a correct state, it should be one of these. For the remaining 32 failures, our search found no twin that the model solves and that is also token-aligned.

What we transplant. We run the failing prompt, but at the chosen layers we replace its activations with the correct twin's, then let the model generate. We test 22 layer settings for every pair: 15 single layers (every second layer from 0 to 26, and 27), six consecutive blocks of 4 to 5 layers (0–4, 5–9, 10–14, 15–19, 20–23, 24–27), and all 28 layers at once. We use two position choices:

  • Shared positions (main test): every prompt position where the failing prompt and its twin have the same token, which is every position except the renamed symbols (134 of 140 in the example). The model still reads its own regex, but what it has computed at all the other positions now comes from the twin it solves correctly.
  • Last position: only the final position of the prompt, just before the model starts writing its answer. If the model formed a plan for the whole construction before writing it, this is where that plan would be stored.

Results (CoT 7B, Tier 4). In every row, the model works on the problem it fails. Each row says whose internal state we put into that run.

State put into the failing runFailing problem now solvedTwin's answer given instead
State from the correct twin, shared positions0 / 3080 / 308
State from the correct twin, last position0 / 3080 / 308
State from a twin the model also fails (control), shared positions0 / 2860 / 286
State from a twin the model also fails (control), last position0 / 2860 / 286
The failing run's own state (control)0 / 14, output identical to the original–

The two columns check two different outcomes. The first counts how often the failing problem is now solved correctly. The second counts how often the model instead builds the twin's correct DFA, which would mean it simply copied the twin's answer. Both are zero everywhere.

As a check, we also copied each failing run's own state back into itself. Its answer stayed exactly the same, which confirms that the copying step does not change the model's behaviour on its own.

The main result is that a correct twin's state never fixes a failure, at any of the 22 layer settings, including all 28 layers at once. It does not even make the model copy the twin's answer. So the failure does not come from a faulty internal state that a correct one could replace, whether at a single layer, a block of layers, or all layers at once.

AuthorsOpenReview ↗

Response to Weakness 1 and Question 1 (Continued)

Our mechanistic conclusions do not rest on correlations. The paper's correlational analyses, the neuron scores and the linear probes, are used mainly to find where to look. Each conclusion is then tested by changing the model's internals and measuring the effect on its answers, at three levels: single neurons, directions in activation space, and the full internal state of each layer. Across all of them, including the new instance-matched test, no intervention repairs more than a small share of the failures:

  • Neurons (Table 2c): amplifying or damping the top-scoring neurons does no better than doing the same to random neurons. In a per-problem rerun, it changes the outcome of at most 3 of the 285 problems.
  • Directions (Table 2c): steering along learned directions (ActAdd, the probe direction, SADI) gains at most +1.0 point, and none of these changes is significant.
  • Iterative steering (Table 2c): the strongest intervention, VGNS, fixes 7 of the 42 failures (paired p = 0.016), and 35 resist all four rounds.
  • Full state, averaged (Section 5.2): replacing the state with the average correct state fixes none of the 42 failures at layers 0 to 25 or with all 28 layers at once. The few changes at the last two layers also appear when the average failing state is patched in instead, so they reflect disturbance rather than repair. Because an average also removes the information about which regex is being solved, the instance-matched test below is the stronger version of this experiment.
  • Full state, instance-matched (new): replacing it with a matched twin's correct state fixes none of them, at any of the 22 layer settings.

Across every level we examined, no intervention repairs more than 7 of the 42 failures. The Layer-10 state carries a moderate signal of the outcome (AUROC 0.85, precision 0.54), but the failure resists every local correction, including the correct state of a matched problem, which is what the paper means by a structural failure. As in the paper, we state this conclusion for the interventions tested. We will add the instance-matched experiment to Section 5.2 and Appendix F, and replace the sentence at lines 452–454 accordingly.

AuthorsOpenReview ↗

Response to Weakness 2a and Question 2

We thank the reviewer for this point. The reviewer is right that our original curriculum runs differed from joint training in more than order: they added theory Q&A examples, a balanced replay phase, a different trace format, and different epochs, batch size and early stopping (Table 5, lines 1300–1310). We have rerun all five orders with these differences removed. The reviewer's related question on duplicate languages is answered in W2b and Q3 below.

Curriculum with order as the only difference. Each run uses exactly the joint-training data (the same 22,500 construction examples, with no theory Q&A and no replay), the same JSON-trace supervision, and the same LoRA configuration, optimizer, epochs, batch size and seed as joint training. The learning rate follows a single cosine schedule over the full run, as in joint training. The examples are grouped by tier and presented in the stated order. As a check on the training code, the same script with all tiers shuffled together reproduces joint training: 96.5% overall and 82.9% on Tier 4, the same as in Table 2a. All runs are evaluated on the same 200-example test sample as Table 2b (39, 47, 73 and 41 examples in Tiers 1–4, where Tier 1 includes the sample's one handcrafted example).

Order (7B, CoT)Tier 1Tier 2Tier 3Tier 4OverallOriginal Table 2b
Natural (1→2→3→4)56.466.056.246.356.543.5
Reverse (4→3→2→1)48.740.424.719.532.026.0
Hard-first (4→1→2→3)53.844.738.431.741.539.0
Mid-out (3→2→1→4)61.553.234.248.847.043.5
Random permutation (1→4→2→3)59.051.139.756.149.537.0
Joint (all tiers shuffled)10010010082.996.596.5 (Table 2a)

The collapse is caused by ordering, not by the extra components. With order as the only difference, the best curriculum reaches 56.5% overall against 96.5% for joint training. The best Tier 4 result under any order is 56.1%, 26.8 points below joint training's 82.9%. The extra components of the original runs did make results worse, lowering overall accuracy by a further 2.5 to 13 points depending on the order. But those components only enlarged the collapse. They did not cause it. So changing the order of training does not close the Tier 4 gap, which addresses the reviewer's concern about the limits of training-based mitigation.

What carries over from Table 2b, and what changes. Easy-to-hard (natural) order is still best overall, and the orders that begin with the hardest tier are still worst (reverse 32.0%, hard-first 41.5%). The middle of the ranking changes: the random permutation rises from fourth to second, and it gives the best Tier 4 accuracy (56.1%). With only 41 Tier 4 test examples (95% intervals of about ±15 points), the smaller Tier 4 differences among orders, such as random (56.1%) against natural (46.3%), are within sampling error. The gap to joint training is not.

Interpretation. Under every order, tiers trained early fall far below their near-perfect joint-training accuracy, which is consistent with forgetting. Tiers trained last also stay low, for example Tier 4 at 46.3% under natural order and Tier 1 at 48.7% under reverse order. Because the learning rate has largely decayed by the final phase of the single cosine schedule, this second effect may reflect reduced plasticity, a low final learning rate, or both. We will report these controlled runs in Table 2b and Appendix C.

Reviewer_KroLOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
1
Read review
Paper summary

The manuscript investigates whether Large Language Models (LLMs) genuinely internalize the algebraic structure of symbolic tasks or merely approximate them through pattern matching and distributional interpolation. Using the task of converting regular expressions to deterministic finite automata (regex-to-DFA) as an exactly checkable testbed, the authors evaluate frontier models and fine-tuned open-weight models (Qwen 2.5 family) across multiple difficulty tiers. Through behavioral interventions (Chain-of-Thought, curriculum learning) and mechanistic interpretability techniques (activation patching, inference-time steering), the authors demonstrate that models consistently fail on the most complex, multi-step subset construction tasks (Tier 4). Because these failures persist regardless of scale or intervention, the authors conclude that LLMs fail to internalize the underlying algorithmic logic and instead rely on approximation, framing this as a fundamental structural limitation of the Transformer architecture.

Critical strengths

Good Presentation and Readability: The manuscript is very well-written. It features a clear narrative arc, high readability, and excellent structural organization, making complex concepts accessible to the reader.

Comprehensive, Multidimensional Experimental Design: The authors tackle their central research question with commendable thoroughness. By evaluating the problem across multiple dimensions—spanning zero-shot prompting, supervised fine-tuning with curriculum learning, and mechanistic interpretability—they provide a highly rigorous, multi-angled investigation.

High Relevance and Timeliness: The research addresses a critical and highly debated topic within the AI community: the true capacity for formal, multi-step symbolic reasoning in LLMs. Disentangling genuine algebraic execution from heuristic approximation is of paramount importance to the field.

Contribution of a Novel, Graded Benchmark: The creation of a new, procedurally verified benchmark of 22,500 regex-to-DFA examples is a significant contribution. Grading the dataset into four distinct difficulty tiers (from simple mappings to nested subset constructions) provides a valuable tool for future research into structural reasoning limits.

Granular Error Taxonomies: The paper does an excellent job of moving beyond binary pass/fail metrics. By developing formal taxonomies for both semantic misunderstandings (11 modes) and construction failures (6 modes), the authors provide a highly useful vocabulary and framework for categorizing specific LLM reasoning breakdowns.

Rigorous Human Evaluation: Unlike many contemporary papers that rely lazily on "LLM-as-a-judge" automation, the authors utilized double-blinded human annotators to build their initial failure taxonomies. This manual, cross-consistency protocol adds substantial empirical credibility to their diagnostic baselines.

Critical weaknesses

Argument by Exclusion and the Unproven Alternative Hypothesis: The central question of the manuscript establishes a dichotomy: either LLMs internalize the algebraic structure of a task, or they approximate it via distributional interpolation. To answer this, the methodology systematically tests for the presence of algebraic execution (through zero-shot diagnostics, fine-tuning ceilings, and mechanistic interpretability). Upon finding that models fail to robustly execute complex subset construction, the authors accept the alternative hypothesis—distributional interpolation—by default. However, ruling out perfect algorithmic execution does not affirmatively prove distributional interpolation. The authors provide no positive empirical evidence, data-tracing analysis, or mathematical proof demonstrating that the models are actually interpolating across a learned data distribution. By treating "distributional interpolation" as a residual catch-all for any non-algorithmic output, the paper's ultimate mechanistic conclusion remains an unproven assumption rather than an empirically validated finding.

Lack of a Formal Definition for "Pattern Matching": The term "pattern matching" is central to the manuscript's thesis and forms a primary pillar of both its title and research question, yet neither the text itself nor the cited literature provides an explicit, formal definition for it. Throughout the paper, it is used as a broad, informal descriptor to contrast against genuine symbolic reasoning. Given how heavily the manuscript's core arguments rely on this distinction, the authors must explicitly define and operationalize what constitutes "pattern matching" within their evaluation framework.

The False Dichotomy of "Weights vs. Inference-Time Reasoning": In Section 5.1 and Appendix E, the authors conclude that because No-CoT matches or outperforms CoT, "the limitation lies in the weights, not in inference-time reasoning." This creates a false dichotomy and constitutes a confusing, vague claim based purely on intuitive explanations. "Inference-time reasoning" (such as Chain-of-Thought) is not a separate computational module; it is executed entirely by the model's weights generating tokens autoregressively. By failing to provide formal justification for this distinction, the authors undermine their own point: if a model fails at inference-time reasoning, it is precisely because its weights lack the capacity to generate the correct sequence of tokens. Treating the weights and inference-time reasoning as two distinct sources of failure is conceptually flawed.

Conflating Semantic Understanding with Constrained Generation: In Section 3, the authors use the Cross-Consistency Protocol to diagnose a lack of "understanding." Specifically, Task 2 requires the model to generate 10 accepted strings that cover all structural branches of the regex, and the authors use failures here (e.g., "Simple-Path Bias") to argue semantic misunderstanding. This is a severe construct validity error. It conflates recognition (understanding the rules) with constrained generation (planning and search). Autoregressive models generate tokens sequentially and lack intrinsic lookahead/search algorithms; therefore, a model could possess a perfect internal representation of the regex rules but still fail to generate a perfectly distributed set of 10 strings, due to the statistical biases of sequential sampling. Penalizing the model's "understanding" based on a task that fundamentally requires search misdiagnoses an autoregressive generation bottleneck as a semantic failure.

Missing Conditional Analysis Between Understanding and Synthesis: In Section 4, the authors state their goal is to test if a model can produce a correct DFA and how its semantic weaknesses manifest during synthesis. They attempt to link the specific semantic weaknesses identified in the previous section to these construction failures. However, the current methodology leaves these two types of error entangled because the evaluation tasks are run via independent prompts without cross-referencing the results. To truly prove that semantic errors propagate into synthesis, the analysis must be conditioned on the Stage 1 outcomes. The authors should isolate cases where the model successfully understood the regex versus cases where it failed, and trace how those specific prior outcomes connect to subsequent construction failures. Without this conditional breakdown, it is impossible to disentangle whether a DFA construction failed due to an underlying semantic misunderstanding or an independent execution error.

Mismatch Between Diagnosis and Fine-Tuning Methodology: In Section 3.1, the authors explicitly diagnose the root causes of "Indexing and Positional Drift" by stating: "These errors stem partly from unstable positional representations during multistep reasoning and partly from tokenization effects, since models operate over subword tokens rather than raw characters, leading to index drift and loss of exact string boundaries." However, the mitigation experiments in Section 5 completely ignore this dual diagnosis. The authors fine-tune standard Qwen 2.5 models using Low-Rank Adaptation (LoRA), while leaving both the subword tokenizer and the model's positional representation mechanisms unchanged. Because regular languages and DFAs are inherently character-by-character state machines, forcing a model to learn these transitions over unpredictably chunked subword tokens introduces a severe representational bottleneck. By failing to evaluate a character-level baseline, it remains unclear how much of the Tier 4 performance ceiling is a fundamental limit of transformer reasoning circuits, and how much is simply an artifact of the model losing exact string boundaries due to its own tokenizer.

Sweeping Architectural Claims Based on Low-Rank Constraints: In Section 5, the authors conclude that the inability to master Tier 4 subset construction represents a fundamental, structural limitation of the Transformer architecture. However, this sweeping conclusion is drawn entirely from experiments utilizing Low-Rank Adaptation (LoRA) for fine-tuning. LoRA restricts parameter updates to a low-rank subspace, inherently limiting the model's capacity to learn novel, high-degree representational circuits. Formal algorithmic tasks like subset construction require precise, multi-step state tracking that may require full-rank weight updates to properly wire the necessary neural circuitry. By failing to perform full-parameter fine-tuning, the authors introduce a strong confounder: the observed performance ceiling may not be a fundamental limit of Transformers, but merely an artifact of the low-rank constraints imposed by their chosen fine-tuning methodology.

Inadequate Rigor in Activation Difference Scoring: In Section 5.2, the authors use Activation Difference Scoring to search for localized neurons responsible for multi-step reasoning processes like subset construction. This approach lacks formal rigor. The method relies on the naive assumption that complex algorithmic execution is modularly localized in distinct neurons. However, Transformers parameterize information via distributed representations and superposition, meaning logic is encoded in continuous, high-dimensional vector spaces rather than discrete neuronal firing rates. Furthermore, an observed difference in activation is merely correlational; the method cannot disentangle whether a neuron is genuinely computing state transitions or simply reacting to confounding surface-level heuristics, such as token frequency or sequence length. Therefore, using activation differences to diagnose a model's structural reasoning capacity is fundamentally inadequate.

Questions for authors

All the comments below are suggestions for improvement:

Provide Formal Definitions: The authors must provide explicit, formal definitions for the core concepts of "pattern matching" and "distributional interpolation". Because the entire paper contrasts these concepts against algebraic internalization, they need to be rigorously defined rather than used as vague, informal descriptors.

Address the Tokenization Bottleneck: In Section 3.1, subword tokenization is explicitly diagnosed as a root cause for positional drift and the loss of string boundaries. However, the mitigation experiments in Section 5 ignore this variable entirely. The authors must either conduct a baseline experiment that mitigates this (e.g., using a character-level tokenizer) or explicitly justify why the tokenization bottleneck is fundamentally irrelevant to the Tier 4 failures.

Supply Positive Evidence for Interpolation: The conclusion that models approximate tasks via distributional interpolation is currently reached purely through an argument by exclusion. The authors should provide positive empirical evidence—such as tracing training data distributions or mapping statistical heuristics—to affirmatively prove that interpolation is occurring, rather than just proving that algebraic execution failed.

Conduct a Conditional Error Analysis: To rigorously support the claim that semantic interpretation errors propagate into DFA construction errors, the authors should provide a conditional breakdown. By cross-referencing Stage 1 and Stage 2 outcomes, they need to isolate instances where the model explicitly failed to understand a regex and trace how that specific semantic failure caused the subsequent construction breakdown.

17 comments
AuthorsOpenReview ↗

Response to Weakness 1 and Question 3

We sincerely thank the reviewer for the detailed review and for recognizing the paper's presentation, its multidimensional experimental design, the new graded benchmark of 22,500 regex-to-DFA examples, the two error taxonomies, and the double-blind human annotation. We address each point below, and add new experiments wherever the reviewer asked for evidence.

W1 + Q3. Positive evidence for interpolation

We thank the reviewer for this point. It is correct that showing the models do not follow the procedure does not, by itself, show that they rely on their training data. We therefore ran new experiments that test this directly on the fine-tuned CoT models (Qwen 1.5B, 7B and 14B: the same fine-tuned checkpoints reported in Table 2a, with no retraining). Because the training data of the frontier models is not public, distance to the training data can be measured only for models we trained ourselves. The experiments show that the models' accuracy depends strongly on how close a problem is to their training data.

A new, controlled probe set. We first tried this on the original test set, but there the problems far from the training data were also the longer ones (correlation 0.62). A far problem could fail because it is unfamiliar or simply because it is long, and the data could not tell the two apart: once we accounted for length, no distance effect could be detected (p = 0.45). We therefore built a new probe set of 1,200 problems in which distance and length are no longer tied, with all selection rules fixed before any model was run. It has 6 groups of 200: 200 problems taken from the training data, a rewritten copy and a relabelled copy of each, and 600 new problems at three distances from the training data. Each group has 50 problems per tier, and all groups are matched in size (median DFA of 5 states, median regex length of 13 characters). For the 200 problems taken from the training data, the prompt is word for word the same as during training (same system prompt, same question).

1. Accuracy falls as problems move away from the training data. We generated a large pool of new problems whose languages do not appear in training. For each one, we compared its regex with all 22,500 training regexes, found the closest one, and recorded what share of its characters differ from it. From this pool we picked three groups of 200, each matched in tier and size: near (the closest fifth, about 14% of characters differ), mid (the middle band, about 25%) and far (the furthest fifth, about 38%).

ModelNearMidFarNear → far
Qwen-1.5B92.076.561.5−30.5
Qwen-7B92.577.563.5−29.0
Qwen-14B92.579.062.5−30.0

Problems of the same size and difficulty lose about 30 points of accuracy as they move away from the training data. A model that had learned the procedure would solve near and far problems equally well.

AuthorsOpenReview ↗

Response to Weakness 1 and Question 3 (Continued)

2. Same problem, new labels: accuracy collapses. We took 200 training problems and made two altered copies of each:

  • Rewritten: the same language, with the regex written differently (e.g., ddbb(c|b) → ddbb(b|c)). The correct DFA is the one seen in training.
  • Relabelled: the letters swapped (e.g., ddbb(c|b) → bbcc(d|c)). The correct DFA has exactly the same structure, but with labels the model never saw for this problem.
ModelOriginalRewrittenRelabelled
Qwen-1.5B89.087.058.5
Qwen-7B90.589.059.0
Qwen-14B90.588.559.5

Rewriting barely matters, but relabelling costs about 30 points, even though the construction steps are exactly the same. The models can solve a problem when its answer looks like one they have seen, and often fail when only the labels change. Two simpler explanations could produce the same drop, and we ruled out both. First, unfamiliar letters: if some letters were rare in training, a relabelled problem could contain letters the model had rarely seen. This is not the case. Within every alphabet, all letters occur equally often in training (each within about one point of an even split), and relabelling only swaps letters within the same alphabet, so a relabelled problem uses letters the model has seen just as often. Second, tokenization: swapping letters can change how the regex is split into tokens, so the drop could come from a different token split. We checked this: 172 of the 200 relabelled regexes are split into exactly the same token pattern as their originals, and on these the drop is just as large, from 89.5% to 57.0% averaged over the three models.

3. The models do not copy stored answers. When the models are wrong, their DFA is almost never exactly the answer to a training problem (0 to 1 of 67–78 wrong DFAs), which is at or below the rate expected by chance (1.2–1.4%, the share of wrong DFAs that would match a training answer if the errors were random small mistakes). So the models are not retrieving stored answers. Their answers get worse as a problem moves away from what they have seen, which is what interpolation predicts.

Together, these provide the positive evidence the reviewer asked for: the models' success depends on how close a problem is to their training data, which is what we define as distributional interpolation (Definition 3 in W2 + Q1 below). We will add this probe set and its results to the paper as a new appendix, and state the interpolation claim with this evidence.

AuthorsOpenReview ↗

Response to Weakness 2 and Question 1

We thank the reviewer for this point and agree. We will add the following definitions to Section 1. A problem is a regex r over an alphabet Σ, with language L(r), and M(r) is the DFA that model M builds for it. Both terms are defined against symbolic reasoning, so we define that first.

Definition 1 (symbolic reasoning). M reasons symbolically on a set of problems if its answers depend on r only through L(r). That is: (a) M(r) is correct, L(M(r)) = L(r), and M's other outputs for r (its description of the language, its example strings and its accept/reject decisions) agree with L(r) and with each other, and (b) M's success is unchanged by any transformation τ that changes the form of r but not its language up to renaming, such as a bijective renaming of the symbols π: Σ → Σ, or a rewriting r′ with L(r′) = L(r). In words: the model follows the meaning of the regex, so its answers are correct, agree with each other, and do not change when the regex is only written or labelled differently.

Definition 2 (pattern matching). M pattern-matches when its answers depend on the surface form of r beyond L(r). Formally, condition (b) fails: for some transformation τ of the kind in (b), M's success rate on a set of problems changes significantly when τ is applied to each of them. On a single problem, the sign is that M solves exactly one of r and τ(r). A second sign is that condition (a) fails internally: M's own description of L(r) and its own accept/reject decisions contradict each other. In words: the model reacts to how the problem looks rather than to what it means, so renaming the symbols can flip its answer, or it states one rule and then acts against it.

Definition 3 (distributional interpolation). Let d(r) be the edit distance from r to the closest training regex, divided by the length of r. M interpolates when, among problems of the same difficulty (same tier and DFA size), its probability of success falls as d(r) grows. Under Definition 1, this probability would not depend on d(r). In words: the model does well on problems that look like ones it was trained on, and worse on unfamiliar ones of the same difficulty. Because d(r) requires the training data, this definition applies to the models we fine-tuned.

The two are related but distinct. Pattern matching concerns which features of the current problem drive the answer, and interpolation concerns how close the problem is to the training data.

How each is measured:

DefinitionTestResult
Pattern matching, (b) failsRename the symbols of the 42 failing Tier 4 problems (Section 5.2), and of 200 solved training problems (W1)11 of 42 failures become successes, and accuracy on the training problems falls from about 90% to 59%
Pattern matching, (a) failsCompare each model's description of the language with its own string decisions (Section 3)Descriptive–Operational Dissonance in every model
InterpolationAccuracy at three distances from training, at matched size (W1)About 92% near, falling to about 62% far
Reviewer_DkGwOpenReview ↗
Rating
3
Confidence
3
Informativeness
3(+1)
Presentation
3
Soundness
3
Read review
Paper summary

The paper investigates whether LLMs genuinely perform symbolic reasoning or rely on pattern matching, using regular languages as an exactly decidable testbed. It introduces a Cross-Consistency Protocol that probes regex interpretation, example generation, and edge-case recognition within a single prompt, surfacing eleven systematic failure modes across six models. It then evaluates DFA construction under two strategies, identifying six structural error classes. Finally, it trains on a purpose-built regex-to-DFA benchmark across four difficulty tiers, showing that fine-tuning closes the gap on Tiers 1-3 but not Tier 4, and presents mechanistic analyses — activation difference scoring, linear probing, activation patching, and inference-time steering — indicating that the residual failure is distributed across the network and only partially remediable. The overall evaluation is reasonable that can verify the effectiveness of method.

Critical strengths

(1) The testbed is well chosen: regex-to-DFA is exactly decidable, so every judgement is verifiable rather than plausibility-based. The Cross-Consistency Protocol is a real methodological contribution — putting description, generation, and recognition in a single context makes contradictions attributable to the model itself, and the Appendix F control shows the joint setting is conservative.

(2) The fine-tuning and mechanistic sections are refreshingly honest. No-CoT matches or beats CoT, curriculum underperforms joint training, and the counterintuitive findings are reported without spin. The mechanistic search is thorough: 56,000 neuron-layer pairs tested with contrast sets, whole-trajectory patching recovering zero failures, and the admission that the probe direction is not a steering direction. These are meaningful negative results.

Critical weaknesses

(1) The diagnostic benchmark is manually curated to "specifically target" the reported failure modes, so the taxonomy in Sections 3-4 risks circularity. I would like to see failure-mode frequencies on uncurated or generator-based regexes before calling them systematic.

(2) Grok-4.1's exclusion from the construction study is significant. Six completions out of 360 attempts is itself a striking cross-architecture difference — it failed differently and more severely — but the paper treats it as a side note.

(3) The Tier 4 intervention experiments rest on 285 examples. A +2.4 pp gain is roughly 7 cases, and the random control already gains +0.3. Without confidence intervals or per-example stability, the neuron-level and representation-level deltas are close to the noise floor.

(4) There is also an unresolved tension between the layer-10 probe result (AUROC 0.85 separates success from failure) and the steering failures. If the outcome is so linearly readable early, why is it not locally actionable? The paper explains the probe direction but not this deeper puzzle.

Questions for authors
  1. Table 1 renders with empty cells in my viewer. Do the per-model failure counts exist in the submission?

  2. What are the failure-mode frequencies on uncurated regexes? This would break the circularity concern.

  3. Why did Grok-4.1 complete only 6 of 360 constructions — token limits, refusals, or malformed output? Would a larger budget change the rate?

  4. Can you report per-example stability or confidence intervals for the Table 2c deltas?

If the rebuttal addresses the Table 1 rendering, provides uncurated failure counts, and gives some variance estimate for the steering results, I would support acceptance without reservation.

5 comments

Dear Reviewer,

Thank you again for your thoughtful review. We have addressed each of your weaknesses and questions to the best of our knowledge in the responses posted above. We would be happy to answer any further questions, and if you feel your concerns have been resolved, we would sincerely appreciate that being reflected in your assessment.

Best regards,

The Authors

Dear Reviewer,

We understand this is a busy period, and we are grateful for the time you have given our paper. As the discussion phase closes on November 18 (AoE), we wanted to check whether our responses have addressed your concerns. We would be glad to clarify any remaining point before the deadline, and if your concerns have been resolved, we would appreciate it being reflected in your assessment.

Best regards,

The Authors

Dear Reviewer,

As the discussion phase closes today (November 18, AoE), we wanted to send a final note. We would be glad to address any remaining concerns in the remaining hours.

Thank you again for your time.

Best regards,

The Authors

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of revisions in the uploaded PDF

Summary of revisions

We thank all reviewers for their feedback. We have uploaded a revised PDF. The title, abstract, claims and three-stage structure are unchanged, and the main text stays within the 10-page limit. Most additions are in the appendix; the main text gains only short sentences that point to them. Every change is coloured by reviewer:

  • Blue: Reviewer DkGw
  • Red: Reviewer LUQf
  • Green: Reviewer KroL (first round)
  • Purple: Reviewer KroL (follow-up)

Deleted wording is not shown. xAI has discontinued Grok-4.1 and now serves all Grok-4.1 requests with Grok-4.3, so every new Grok run uses Grok-4.3. This is stated wherever those runs appear.

Reviewer DkGw (blue)

  • W1/Q2, curated benchmark: Appendix C.1 now describes the benchmark correctly: 120 of the 180 problems were generated from random NFAs, and no problem was selected on model performance. New Appendix G.4 reports all eleven failure modes and P1–P6 on 180 newly generated regexes; Section 3 and Section 4 each point to it.
  • W2/Q3, Grok in construction: Appendix D.4 now states the 4,000-token budget and breaks down Grok-4.1's 354 runs without a DFA. New Appendix D.5 reruns Grok at 16k and 32k tokens and adds P1–P6 labels and the Task 1 comparison. Section 4 gains one sentence. Figure 4 is unchanged, because all its models run at 4,000 tokens.
  • W3/Q4, steering variance: Appendix F.2.5 adds paired McNemar tests and a per-problem table of problems fixed and broken; Appendix G.3 is updated to match. Section 5.2 gains one sentence pointing to them.
  • W4, probe vs. steering: Section 5.2 gains a short explanation; the full argument is in Appendix F.2.4.
  • Q1, Table 1: no change needed.

Reviewer LUQf (red)

  • W1/Q1, instance-matched patching: Section 5.2 gains one sentence replacing the earlier statement that no matched twins existed. Appendix F.2.4 adds the full experiment and a results table, and the Limitations section is updated.
  • W2a/Q2, curriculum: Table 2b now reports curriculum runs in which order is the only difference from joint training, and Section 5.1 is updated to match. Appendix C.3 describes these runs. Appendix C.4 presents the phase-wise curriculum run, with its setup, results and data.
  • W2b/Q3, equivalent regexes: Appendix C.2 now describes both deduplication steps, string-level and language-level, and the train–test check. Section 5 gains one clause.

Reviewer KroL (green, first round)

  • W1/Q3, evidence for interpolation: new Appendix G.6 (probe set; distance and relabelling results). Section 5.1 gains one sentence.
  • W2/Q1, definitions: new Appendix A.9 gives formal definitions and how each is tested. The Introduction gains one sentence.
  • W3, weights vs. inference-time reasoning: the sentence in Section 5.1 is reworded, and the matching wording in the Introduction is removed.
  • W4, Task 2 and planning: new Appendix F.7 reports the recognition-only and branches-given experiments. Section 3 gains one sentence.
  • W5/Q4, conditional analysis: new Appendix G.5 crosses Stage 1 and Stage 2 outcomes problem by problem. Section 4 gains one sentence.
  • W6/Q2, tokenization: new Appendix G.7 reports the three tokenization tests. Section 3.1 now states the scope of the tokenization remark.
  • W7, LoRA and architectural claims: new Appendix G.8 reports full fine-tuning. Section 5.1 gains one sentence; the last sentence of the Introduction now states what "structural" means; Limitations is updated.
  • W8, activation difference scoring: Appendix F.2.4 adds length and token controls and the ablation of the top neurons. Section 5.2 gains short clauses.

Reviewer KroL (purple, follow-up)

  • Appendix A.9 adds a paragraph on how the definitions identify each mechanism and a sentence on how relabelling relates to Definitions 2 and 3; its table is extended.
  • Appendix G.6 adds the prediction argument for the relabelled and rewritten copies.

The Reproducibility Statement and Appendix J.3 now give the collection dates of the new runs (7–10 November 2026) and note the Grok-4.3 change.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.