TL;DR
Can large language models (LLMs) genuinely learn to reason, or are they merely memorizing logic puzzles? By developing a dynamic Knights & Knaves benchmark and a local perturbation metric ($\text{LiMem}$), the authors show that LLMs heavily memorize training problems, yet this memorization coexists with—and even accompanies—the emergence of generalizable, genuine reasoning capabilities.
What Problem Does This Paper Address?
State-of-the-art LLMs can solve complex mathematical and logical benchmarks, yet they frequently stumble on trivial variations (such as comparing whether $13.11$ or $13.8$ is larger). This paradox fuels a central debate: are high benchmark scores just the result of memorization from massive pretraining corpora? Furthermore, if models memorize, does that prevent them from acquiring underlying reasoning principles?
This paper investigates whether memorization and logical reasoning are mutually exclusive by establishing a controlled, quantitative framework to measure both phenomena simultaneously.
Methods
The authors introduce three key methodological contributions:
-
Local Inconsistency-based Memorization Score ($\text{LiMem}$): Inspired by human study habits—where an unprepared student might solve an exact homework problem but fail if variables change—$\text{LiMem}$ quantifies memorization as: $$\text{LiMem}(f; \mathcal{D}) = \text{Acc}(f; \mathcal{D}) \times (1 - \text{CR}(f; \mathcal{D}))$$ Here, $\text{Acc}$ is task accuracy and $\text{CR}$ is the Consistency Ratio (the proportion of correctly solved problems that remain correct under local perturbations). High accuracy paired with low consistency yields a high memorization score.
-
Multi-Level Perturbations:
- Math-level perturbations: Modifying a single clause (leaf perturbation) or an entire premise (statement perturbation) while maintaining puzzle structure and a unique, different ground truth.
- Language-level perturbations: Swapping character names for rare ones, renaming roles (e.g., saint/sinner), reordering statements, or inverting role definitions.
- Mechanistic and Probing Analyses: Linear probes are trained on hidden representations across transformer layers to verify whether models internally separate true statements from false ones. Models are also fine-tuned on corrupted answers and incorrect Chain-of-Thought (CoT) steps to test whether reasoning emerges independently of verbatim target memorization.
Datasets
- Dynamic Knights and Knaves (K&K) Benchmark: A newly introduced functional benchmark based on classic Knights and Knaves puzzles (which map directly to the NP-complete Boolean Satisfiability / SAT problem).
- Puzzles range in difficulty from 2 to 8 characters with logical formulas parameterized by tree depth and width.
- Automatically generates natural language puzzle descriptions, step-by-step synthetic natural language proofs (CoTs), and verified single-solution ground truths.
- Unlike static benchmarks (such as TruthQuest), it programmatically guarantees unique solutions before and after perturbations.
Key Insights and Ideas
- Memorization Enables Rather than Inhibits Reasoning: As fine-tuning progresses, training set memorization scores ($\text{LiMem}$) rise sharply, yet test accuracy on unseen puzzles steadily improves rather than collapses. Memorization and generalization grow together.
- Reasoning Emerges Without Scratchpads: Even when fine-tuned strictly on question-answer pairs without reasoning steps (Direct FT), models generalize across problem complexities and transfer across difficulty levels (e.g., training on 8-person puzzles boosts accuracy on 3-to-6-person puzzles).
- Internal Emergence of Truth Values: Probing reveals that around layers 14–15 of Llama-3-8B, representations clearly separate valid from contradictory statements (reaching near 97% probing accuracy, compared to $<85\%$ for the un-finetuned base model).
- Learning from Imperfect Supervision: Models trained on datasets where up to 50% of the final answers are deliberately wrong (or 100% of CoT steps are shuffled) still show substantial generalization improvements, proving that models extract structural logical rules rather than simply memorizing input-output mappings.
Key Results
- Off-the-Shelf Limitations: 14 leading models (including Claude 3.5 Sonnet, GPT-4o, and Gemini 1.5 Pro) struggle on vanilla K&K puzzles. Best accuracy drops from $\le 70\%$ on 2-person puzzles to $\le 11\%$ on 8-person puzzles, exhibiting high memorization scores ($\text{LiMem} > 0.30$).
- Direct FT Scaling: Brute-force Direct FT on 10,000 8-person puzzles enables GPT-4o-mini to jump from near 0% to 52% accuracy on 8-person test puzzles and $\sim 90\%$ on 4- and 5-person test puzzles—without ever being exposed to reasoning chains.
- Predicting Memorization vs. Reasoning: Using a logistic regression classifier on text length, surface statistics, or middle-layer model embeddings can predict whether a given puzzle was solved via memorization or reasoning with an AUC of 0.70 to 0.79.
Limitations and Future Work
- Sub-100% Generalization: Even after extensive fine-tuning, models do not achieve perfect generalization, leaving open the question of whether models rely on brittle heuristic shortcuts for certain puzzle types.
- Model Internals for Proprietary Models: Deep internal probing was restricted to open weights (Llama-3-8B); proprietary API-based models (GPT-4o-mini) could only be analyzed via behavioral evaluations.
- Intervention Mechanisms: While classifiers can post-hoc detect whether an output was memorized or reasoned, future work is needed to design active training or decoding interventions that bias LLMs toward genuine reasoning pathways.
Summary updated