On Memorization of Large Language Models in Logical Reasoning

Authors: chulin  xie
yangsibo  huang
chiyuan  zhang
da  yu
xinyun  chen
bill yuchen lin
bo  li
badih  ghazi
ravi  kumar
†  google
Venue: NeurIPS_cc_2024_Workshop_MATH-AI
Published: 2024-09-25 15:29:22

Abstract: Large language models (LLMs) show good performance on some complicated reasoning tasks, yet could also make the most basic reasoning mistakes. This contrasting behavior is puzzling when it comes to understanding the mechanisms behind LLMs' reasoning capabilities. One hypothesis is that the increasingly high and nearly saturated performance on common reasoning benchmarks could be due to the memorization of similar benchmark problems accidentally leaked into the training data.
In this paper, we systematically investigate this problem with a measurement of memorization in reasoning tasks inspired by human behaviors, and a dynamically generated logical reasoning benchmark based on Knights and Knaves puzzles. We found that LLMs could interpolate the training puzzles (achieving $\sim100$% accuracy) after fine-tuning, yet fail when those puzzles are slightly perturbed, suggesting that the models heavily rely on memorization to solve those training puzzles. 
On the other hand, we show that LLMs learn to reason while interpolating the training set. 
At higher level of memorization, the model not only solves more unseen test puzzles, but also solves them relatively robustly under perturbation. 
This phenomenon suggests that LLMs exhibit a complex interplay between memorization and genuine reasoning abilities, and reveals an interesting direction for future research. Our code and data are available at https://memkklogic.github.io/.

Main paper: 
 introduction: 
 Modern Large Language Models (LLMs) show impressive reasoning capabilities that allow them to solve a wide range of problems including commonsense reasoning and mathematical reasoning. In the meantime, LLMs also make mistakes on some of the most basic problems (e.g., comparing which number is bigger -13.11 or 13.8 [17] , and counting the number of sisters that Alice's brother have [21] ).Their contrast of both superhuman reasoning capabilities and dumb mistakes is puzzling when it comes to understanding how exactly LLMs perform reasoning tasks. This question is important both scientifically and practically: understanding how LLMs reason could shed light on our understanding of learning and generalization behaviors of LLMs; and is crucial for real-world applications where robust reasoning is required to mitigate safety and trustworthiness concerns [25, 15, 26] .One hypothesis is that LLMs could be relying on memorization when solving those reasoning tasks, especially when measured by popular benchmark datasets that could be accidentally leaked into the massive internet-crawled pre-training datasets. Previous work [5, 24] show that LLMs could indeed memorize the training data. However, most of those studies focus on analyzing memorization from the perspective of privacy [6] or copyright [13, 27] concerns. Other papers focus on designing dynamic benchmarks [32, 23, 22, 11] or alternative evaluation protocols [30, 31, 28, 23] that could mitigate the issue of benchmark saturation potentially due to memorization. In this paper, we take a direct approach to quantify memorization in reasoning tasks and analyze the interplay between memorization and reasoning. Specifically, we summarize our contributions below:• To quantify memorization in reasoning tasks, we define a memorization metric based on the notions of interpolation and the performance inconsistency under local perturbation that are inspired by human behaviors. • To facilitate the measurement, we propose a new logical reasoning benchmark based on the Knights and Knaves (K&K) [12] puzzles, that support the automatic generation of new puzzles with different difficulty levels and local perturbations of existing puzzles. • We show that K&K puzzles are challenging and only the most advanced LLMs could consistently solve them. The generally low accuracy observed across most off-the-shelf models indicates that K&K puzzles are likely uncommon in internet-based training data. However, our analysis suggests that certain models exhibit signs of memorization to solve the puzzles. • By fine-tuning on K&K samples, we confirm that modern LLMs are capable of memorizing a large collection of puzzles and their solutions when seen during training. Interestingly, when measuring accuracy on the unseen test puzzles, we found that the models' reasoning capabilities grow with the amount of memorization as the models interpolate [3, 20, 2, 1] the training set 1 . Additionally, these enhanced reasoning abilities transfer across different levels of puzzle difficulty.2 How to Measure Memorization in Reasoning Tasks 
memorization metrics for reasoning tasks: 
 Memorization of LLMs has been studied in various contexts such as privacy, copyright [6, 13, 27] , and solving knowledge intensive tasks [3, 10] . In this paper, we are specifically interested in measuring the level of memorization when solving reasoning tasks. This kind of behaviors can be observed on humans. For example, when preparing for an exam / interview, people may not be able to fully digest the underlying principles due to various reasons or constraints. But when (luckily) facing the same problem one has prepared for, they would still be able to solve it. The key characteristics of this type of memorization are: (A) high accuracy on observed problems; (B) low accuracy on unseen but similar problems, due to the lack of deep understanding.Based on this intuition, for a dataset D of reasoning puzzles, we measure the following two quantities:1. To measure (A), we use the accuracy Acc(f ; D) to measure the percentage of the puzzles in D that f can solve. We are especially interested in measuring on the set of observed puzzles, i.e. the training set, Acc(f ; Tr). We say f interpolates [3, 20, 2, 1] the training puzzles if Acc(f ; Tr) ≈ 100%.To measure (B), we measure a consistency ratio CR(f ; D) between the number of consistently solved puzzles after some local perturbations, and the number of solved puzzles (without perturbation). We are interested in local perturbations that makes minimal change to the puzzle and maintain the difficulty level (to be specified in § 2.2).We combine the two factors to define a Local Inconsistency based Memorization Score:LiMem(f ; D) = Acc(f ; D) • (1 -CR(f ; D)).When there is no ambiguity, we simply call it the memorization score. LiMem(f ; D) ∈ [0, 100]% and a larger score provide a stronger evidence of memorization. In our empirical study, we say f solves D via memorization if LiMem(f ; D) > 10%; otherwise we say f solves D via reasoning. Specifically, a high LiMem(f ; Tr) matches the characteristic behavior of human memorizing observed puzzles, and in this case we say f memorized the training puzzles. Furthermore, we also measure LiMem(f ; Tst) on test examples, to study if the generalization accuracy is due to reasoning or memorization.In order to effectively measure memorization score LiMem(f ; D), we need a principled way to (1) perform local perturbation that changes the problem while maintaining its difficulty level; (2) compute the new answer after perturbation, which should be different from the original answer. Towards this goal, we design and implement a functional dataset based on the Knights and Knaves puzzles [12] .Knights and Knaves (K&K) is a type of logic puzzle where some characters can only answer questions truthfully, and others only falsely. The goal is to infer each person's identity. For example: A very special island is inhabited only by knights and knaves. Knights always tell the truth, and knaves always lie. You meet 2 inhabitants: Samuel, and Isabella. Samuel told you that Isabella is a knight. Isabella said that Samuel is a knave and Isabella is a knight. So who is a knight and who is a knave?The ground-truth answer is that (1) Samuel is a knave and (2) Isabella is a knave.Based on the K&K puzzle, we design a dynamic benchmark that supports generating new problems and perturbing existing problems. Our library automatically solves the K&K puzzles and generates solutions for evaluation and training. Specifically, our benchmark consists of two components:The abstract problem sampler generates random K&K puzzles in an abstract format (see details in § B). Specifically, it takes as input the problem specification (N, D, W ) that determines the difficulty level. It then generates a problem with N persons, and for each person, a statement that consists of a random tree of maximum width W and depth D. The leaf nodes can be a claim that a specific person is lying (i.e., knaive) or telling the truth (i.e., knight) , whereas the branching node can be and, or, not, if, and if-and-only-if. The problem sampler also has two subcomponents: the Solver finds all possible solutions to a given puzzle, which is used to guarantee that we generate only problems with a unique solution; the Perturber which, given a problem, generates a locally perturbed version, by replacing a leaf node or an entire statement of a random person's statement with a different one. Perturber only keeps the perturbed problems that have a different solution than the original problem. Comparison between the original sample and the leaf/statement-perturbed samples is provided in Tab. 1.The natural language generator takes an abstract K&K problem and formats it in natural language.The formatting is template-based, but we support a variety of different (common and uncommon) person names, role names (e.g., knight & knaves, angels & devils), and different styles of making each person's claim.We create disjoint sets of n train training problems and n test testing problems for each N -person task.Here, n test = 100, n train = 1, 000 for N > 2, and n train = 200 for 2-person tasks due to limited combinations. Then, we generate perturbed versions for each problem.3 Quantifying LLM Memorization of Reasoning Tasks 3.1 Off-the-shelf Models  
fine-tuned models: 
 Here, we study the model's memorization capacity when directly fine-tuned on K&K problems. We take Llama3-8B and GPT4o-mini and run supervised fine-tuning (SFT) on a set of K&K training problems disjoint from the test set. Specifically, during SFT, the model observes the concatenation of the question and the answer for each problem, but the loss is only computed on the answer part.LLMs interpolate K&K training problems. We fine-tune 50 epochs for Llama3-8B and GPT4omini for 5 epochs (due to budget constraints) via the OpenAI Finetune API (see details in § C). From Fig. 2 (clean), we observe high Acc(f ; Tr), and GPT4o-mini fine-tuned on 3-person puzzles reach interpolation (Acc(f ; Tr) = 100%).Interpolating LLMs have large LiMem(f ; Tr). In Fig. 2 , we report the consistent accuracy Acc(f ; Tr) • CR under perturbation, defined as the ratio of samples correctly solved in both their original and perturbed forms. We observe significant gaps under math problem perturbations (e.g., statement and leaf) on training samples, suggesting that models have large LiMem(f ; Tr) and may rely on memorization to solve the training samples.4 Large Language Interpolators Learn to Reason # ppl for testing # ppl for testing # ppl for testing # ppl for testing The studies in § 3 show that both off-the-shelf and fine-tuned models exhibit some level of memorization in solving K&K reasoning tasks. However, does it mean that those models do not have reasoning capabilities at all? It turns out that the models seem to do both, and the reasoning capability actually improves as the memorization level increases. Next, we present evidence that support this hypothesis.The generalization performance increases with memorization level. As shown in Fig. 3 , the accuracy of fine-tuned models on the test set continues to increase as Acc(f ; Tr) increases, despite that Lp∆ on training samples also increases (i.e., stronger memorization).The LiMem(f ; Tst) on test samples are smaller than LiMem(f ; Tr) on train samples in Fig. 2 , particularly for more challenging cases (e.g., 5-person puzzles). This suggests that models are more likely to use reasoning when solving unseen test samples.The fine-tuned model generalizes across different difficulty levels. By fine-tuning on the M -person problem and testing on the N -person problem, we study LLMs' transferability. The N × M test accuracy improvement grid in Fig. 4 shows that 1) training on any M -person problem generally enhances accuracy on unseen N -person test problems for any N , indicating enhanced reasoning ability on both easier and harder problems; 2) extending the training epochs generally yields better results, particularly for Llama3-8B; 3) test accuracy improvement is larger when N ≤ 6, and improving performance on more challenging tasks remains possible but more difficult. 
conclusion: 
 In this paper, we designed a K&K puzzle-based logical reasoning benchmark and local perturbationbased metrics to quantify LLMs' memorization in reasoning tasks. Our results reveal an intriguing interplay between memorization and reasoning: while models heavily rely on memorization to solve challenging K&K puzzles, models trained to have a higher level memorization also solve more unseen test puzzles, and solve them relatively robustly (in contrast to the memorized training puzzles). A Related WorkMemorization and benchmark contamination in LLMs Previous research has explored training data memorization in the context of privacy and copyright [6] , focusing on how LMs may unintentionally reproduce text by generating near-verbatim outputs from their training data [16, 4, 5] . Our study broadens the concept of memorization to the reasoning context, by evaluating whether LLMs can recall solutions to training questions but struggle to solve their variants during testing.Such memorization patterns appear in the off-the-shelf LLMs on popular math reasoning benchmarks, indicating potential benchmark contamination (i.e., included in the training data). For example, LLMs perform exceptionally well on benchmarks such as GSM8K, MATH, and MMLU, but their performance drops significantly when faced with benchmark variants. These include human-curated problems of similar difficulty [31] , functional variants systematically generated via programs [23] , rephrased versions [28] , translated versions [29] , or problems set beyond a specific date cutoff [22, 11] .Logical reasoning benchmarks To evaluate logical reasoning capabilities in LLMs, synthetic benchmarks have been developed. These benchmarks enable scalable generation of samples with varying configurations and difficulty levels [9] to study LLM reasoning in a controlled setup. For instance, DyVal [32] dynamically generates evaluation samples with controllable complexity based on directed acyclic graphs, which covers reasoning tasks including deductive, boolean, and abductive reasoning. The authors demonstrate that fine-tuning Llama2-13B-chat on these synthetic samples enhances its performance on other reasoning benchmarks. Chen et al. [7] focus on propositional logic problems involving definite clauses. They synthetically generate variations with different premise orders, such as forward, backward, and shuffled. Their study shows that aligning the premise order with the proof order improves LLMs' accuracy in solving these problems. Dziri et al. [8] explore the limitations of transformers in tasks requiring compositional reasoning, including multiplication, Einstein's Puzzle (a constraint satisfaction problem), and dynamic programming problems. They find that while GPT-3 fine-tuned on their training samples can solve in-distribution problems, it fails to generalize to out-of-distribution tasks with increased problem sizes. Extending from Einstein's Puzzle, ZebraLogic [18] is introduced to require reasoning through reduction, absurdum, and elimination to solve constraint satisfaction problems. The study shows that off-the-shelf models struggle with complex puzzles involving large problem sizes. BoardgameQA [14] presents a question-answering dataset characterized by contradictory facts and rules in the questions. To solve this task, the authors find that fine-tuning BERT-large and T5-XXL on their training dataset with proofs outperforms few-shot prompting using PaLM with chain-of-thought (CoT) prompting. Alice in Wonderland [21] is a type of reasoning task in the format of light quiz-style problems such as "Alice has N brothers and she also has M sisters. How many sisters does Alice's brother have?" Advanced models often fail to reason and count accurately in such simple scenarios.The closest benchmark to us is TruthQuest [19] , which builds on the classic K&K puzzles but only focuses on evaluation samples involving 3-6 people puzzles. In contrast, our proposed framework extends this line of research by generating a more comprehensive set of K&K puzzles with more difficulty levels and various perturbation types. We evaluate state-of-the-art models on more challenging K&K puzzles (e.g., 8-people) and analyze their memorization behaviors (via fine-tuning) and generalization capabilities under local perturbations. 
 
 Appendix: During our data construction, we use the maximum width W = 2 and depth D = 2, and the number of persons in the puzzle N = 2, 3,Tab. 1 presents the example knight (truth-teller) and knave (liar) scenario involving two people: Liam and Aria, with corresponding logical statements, and converted English statements, questions, and answers. It also shows three versions of the problems: an original example, a leaf-perturbed version, and a statement-perturbed version. Specifically, (1) leaf perturbation changes a "leaf" in the logical tree -a single truth value. In this case, it flipped Liam's status in Aria's statement from truth-teller to liar. (2) Statement perturbation changes the entire structure of a statement. Here, it changed Aria's statement from an equivalence to a contradictory conjunction. Both perturbations result in changing the answer. The leaf perturbation creates a subtle change in one statement that flips the logical outcome, while the statement perturbation changes the entire one statement. In our evaluation process, we use greedy decoding with temperature t = 0 for all models and a maximum token length of 2048.To assess the correctness, we implement keyword matching: a response is considered correct if each person's ground truth identity appears in the conclusion part of the model's output.Fine-tuning For Llama3-8B fine-tuning, we employed the following standard hyperparameters with a batch size of 4, gradient accumulation steps of 8, and 5e-5 learning rate. We finetune for a maximum of 100 epochs.For GPT4o-mini fine-tuning, we utilized the default hyperparameters provided by the OpenAI finetuning API. The model was fine-tuned for 5 epochs to achieve high accuracy within reasonable budget. NeurIPS 2024 Workshop on Mathematical Reasoning and AI.Interpolating is a term in learning theory to indicate fitting 100% accuracy on training set.persons, the best models still achieve < 70% accuracy. And the performance drops significantly as the complexity increases (the best accuracy is only 11% for 8-person problems).To quantify LLMs' memorization of the logical reasoning task, we employ the metrics proposed in the previous section. Since the training data for the off-the-shelf models is unknown, we will delay the measurement of the interpolation to fine-tuned models in§ 3.2 and focus on the memorization score under local perturbation LiMem(f ; Tst) here. As shown in Fig.1, the test accuracy is relatively low for most cases, suggesting K&K-related problems are probably rare in the Internet and in the training sets of these models. However, we also note that some specific models have large gaps under local perturbation as shown in Fig.5, such as GPT4o and Claude-3.5-Sonnet on 3-person problems under logical statement perturbation, indicating signs of memorization when solving these puzzles. 



Reviews: review: title: title: Review of the paper
main_review: main_review: Pros: 
This paper explores whether LLMs depend on memorization or genuine reasoning when tackling logical puzzles, using a newly introduced benchmark based on Knights and Knaves puzzles. The authors introduce the Local Inconsistency-based Memorization Score (LiMem), a metric that measures the extent of memorization by evaluating performance on both training puzzles and altered (unseen) versions. Interestingly, the findings reveal that while the models significantly rely on memorization to solve training puzzles, they also develop enhanced reasoning abilities, improving their capability to solve new puzzles and adapt to variations with greater resilience. The results suggest an intricate interplay between memorization and reasoning in LLMs, indicating a relationship that warrants further exploration to fully comprehend the models' reasoning mechanisms.

Cons:
Relying on a single type of dataset may limits the generalizibility of the findings. Incorporating a variety of logical reasoning benchmarks would provide a more comprehensive understanding across various contexts.
title: title: Study on "Large Language Interpolators Can Learn Logical Reasoning: A Study on Knights and Knaves Puzzles"
main_review: main_review: Evaluation Overall

Divided Evaluation into Quality, Clarity and Originality 

Quality: The paper presents a thoughtful examination of the interplay between memorization and reasoning in large language models (LLMs) using logical puzzles. The proposed LiMem metric and K&K benchmark offer a structured way to quantify this relationship. The experiments, particularly the fine-tuning on K&K puzzles and the introduction of perturbations, effectively showcase the balance between memorization and reasoning.

Clarity: The paper is well-written, with a clear and structured organization. However, further elaboration on the interpretation of LiMem scores would help readers less familiar with memorization in LLMs to better understand the implications.

Originality: The study is original, proposing a novel benchmark and a memorization metric for reasoning tasks. It builds upon existing work on memorization in LLMs, providing valuable insights into the role of memorization in generalization during reasoning.

Significance: The balance between memorization and reasoning is crucial for advancing LLMs. The K&K benchmark and the findings on memorization's role in reasoning contribute meaningfully to our understanding and improvement of LLM performance in practical applications.

-----

Pros
- Novel LiMem Metric: The new metric effectively measures memorization in reasoning, enhancing our understanding of LLM capabilities.
- K&K Benchmark: The logical reasoning benchmark with varying difficulty provides a robust and scalable evaluation framework.
- Insightful Interplay Analysis: The study demonstrates how memorization can enhance reasoning, offering an interesting perspective on LLM learning behavior.
- Thorough Model Evaluation: The tests on both pre-trained and fine-tuned models provide a comprehensive performance analysis.

-----

Cons
- LiMem Score Interpretation: The implications of LiMem scores could be further clarified to aid reader understanding.
- Generalization Beyond K&K: Broader reasoning benchmarks would enhance the study's generalizability beyond the K&K tasks.
- Model Complexity and Scaling: Deeper exploration of the effect of model size on memorization and reasoning would improve the overall analysis.
title: title: A good paper on LLM logical reasoning
main_review: main_review: This study examines the logical reasoning abilities of Large Language Models (LLMs) using Knights and Knaves puzzles as a case study. It introduces a bespoke benchmark for these puzzles and develops a method to quantify the impact of memorization in reasoning tasks. Findings reveal that LLMs, while achieving almost flawless results on training puzzles, struggle with minor modifications, indicating a significant reliance on memorization. However, the research also shows that higher levels of memorization enable LLMs to not only tackle more unfamiliar test puzzles effectively but also maintain their performance under modifications, suggesting a nuanced interplay between memorization and true reasoning skills.


Strength:

1. The paper innovates by developing a new benchmark based on Knights and Knaves puzzles, offering a novel way to assess LLMs' logical reasoning capabilities, especially under perturbed conditions.
2. The analysis delves deep into examining both the memorization capacity of LLMs and the relationship between memorization and reasoning. This dual focus provides new insights into the operational mechanisms of these models.


Weakness:
1. While challenging, the Knights and Knaves puzzles represent a very specific type of logic problem. This specialization might not sufficiently capture the full spectrum of logical reasoning abilities of LLMs.
2. The study focuses primarily on a specific type of puzzle and perturbation, which may not fully explore the models' capabilities across a broader range of logical problems
title: title: A Promising Approach to Understanding LLM Reasoning Through Knights and Knaves Puzzles
main_review: main_review: The paper explores how large language models (LLMs) balance memorization and reasoning in complex tasks. Using Knights and Knaves puzzles, the study shows that LLMs heavily rely on memorization to solve training puzzles but struggle when small changes are introduced. However, LLMs with higher memorization levels also perform better on unseen puzzles and are more robust under perturbation, suggesting an intricate relationship between memorization and genuine reasoning. This finding offers insight into LLM behavior and presents a path for future research.

# Pros:
## 1. Novel Benchmark: The paper introduces a Knights and Knaves (K&K) puzzle-based benchmark that dynamically generates logical reasoning problems, providing a fresh and controlled way to evaluate LLMs' reasoning abilities.

## 2. Memorization-Reasoning Interplay: It highlights an intriguing relationship between memorization and reasoning, showing that models with higher memorization levels can generalize better to unseen tasks and are more robust against perturbations.

## 3. Fine-Tuning Improvements: The study demonstrates that fine-tuning LLMs on these logical puzzles enhances both their reasoning and memorization capabilities, offering valuable insights into how training data impacts performance.

# Cons:
## 1. Lack of Comparative Analysis: The paper primarily focuses on its own benchmark without providing a strong comparison to other existing reasoning benchmarks. This makes it harder to evaluate how well the proposed method performs relative to other state-of-the-art techniques.

## 2. Limited Real-World Applicability: While the Knights and Knaves puzzles are a useful benchmark, they may not fully capture the complexity and diversity of real-world reasoning challenges, making it harder to generalize the findings to broader applications.