On Memorization of Large Language Models in Logical Reasoning
Authors: name: Chulin Xie, name: Yangsibo Huang, name: Chiyuan Zhang, name: Da Yu, name: Xinyun Chen, name: Bill Yuchen Lin, name: Bo Li, name: Badih Ghazi, name: Ravi Kumar

Large language models (LLMs) achieve good performance on challenging
reasoning benchmarks, yet could also make 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 problems. In this paper, we systematically
investigate this hypothesis with a quantitative measurement of memorization in
reasoning tasks, using a dynamically generated logical reasoning benchmark
based on Knights and Knaves (K&K) puzzles. We found that LLMs could interpolate
the training puzzles (achieving near-perfect 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 while fine-tuning leads to heavy memorization, it also
consistently improves generalization performance. In-depth analyses with
perturbation tests, cross difficulty-level transferability, probing model
internals, and fine-tuning with wrong answers suggest that the LLMs learn to
reason on K&K puzzles despite training data memorization. This phenomenon
indicates that LLMs exhibit a complex interplay between memorization and
genuine reasoning abilities. Finally, our analysis with per-sample memorization
score sheds light on how LLMs switch between reasoning and memorization in
solving logical puzzles. Our code and data are available at
https://memkklogic.github.io.