Knights and Knaves (K&K) Dataset: A Precise Probe for LLM Reasoning vs Memorization

Forum topic · 小凯 · 2026-05-29

Summary

The Knights and Knaves (K&K) dataset, derived from Raymond Smullyan's 1978 logic puzzle, has become a precise research instrument for studying whether large language models truly reason or merely memorize. Hosted on Hugging Face, it programmatically generates puzzles with controllable parameters (number of people, statement depth and width, logical operators), and automatically produces chain-of-thought answers plus perturbed variants (renamed entities, shuffled statements, swapped truth conventions). The NeurIPS 2024 paper "On Memorization of Large Language Models in Logical Reasoning" introduces LiMem, a memorization score based on accuracy and perturbation consistency, showing that memorization and generalization co-evolve, and that role-flip perturbations expose deep common-sense biases. Separately, the Logic-RL project (MSRA) uses under 5,000 K&K samples with REINFORCE++ to train Qwen2.5-7B, achieving an average 0.89 accuracy—approaching o3-mini-high (0.94) and far exceeding GPT-4o (0.37)—with emergent behaviors like formal logic notation and cross-domain transfer to math. K&K is now a standard benchmark in NVIDIA NeMo Gym, DeepSeek R1 reproductions, and other reasoning projects, valued for its controllable difficulty, verifiable answers, and clean isolation from pretraining data.

*Translated and adapted from a zhichai.net forum post.*

LLM Reasoning or Memorization? The K&K Dataset as a Precise Probe

Project: dmackinnon1.github.io/knaves | Dataset: K-and-K/knights-and-knaves | Papers: NeurIPS 2024 / Logic-RL (MSRA)

In one sentence: a 1978 logic puzzle, "Knights and Knaves," has been turned into a surgical instrument for studying LLM reasoning. It can dynamically generate puzzles at any difficulty, automatically perturb them, measure the boundary between "memorization" and "reasoning," and even enable a 7B model trained with RL to reach o3-mini-level performance.

The Puzzle

Raymond Smullyan introduced the puzzle in 1978. The setup is minimal: an island has only two kinds of residents. Knights always tell the truth; knaves always lie. You hear several people speak and must determine who is who.

> Jack says: "If Samuel is a knight, then Lily is a knave." > Samuel says: "If Jack is a knight, then Lily is a knave." > Lily says: "Jack is a knight."

Three people, three statements, one unique logical solution.

dmackinnon1.github.io/knaves turned this into an interactive website where users can play, solve, and verify. But the real value is not the game—it's the programmatic generation engine behind it, repurposed as a benchmark tool for LLM reasoning research.

Engineering Precision of the Dataset

K-and-K/knights-and-knaves (Hugging Face) is not a static problem set. It is a dynamic problem generator.

Controllable parameters:

N (number of people): 2 to 8
D (statement depth): levels of logical nesting
W (statement width): complexity of each statement
Logical operators: and, or, not, imply, equivalence

Automatically generated: problem descriptions (natural language), detailed chain-of-thought reasoning steps, correct answers, incorrect answers (for robustness training), and flawed CoT (with one wrong step or shuffled steps).

Key capability — automatic perturbation:

| Perturbation type | Level | Method | |---|---|---| | Mathematical structure | Replace entire statement | Swap a statement for a newly sampled one | | Mathematical structure | Replace leaf node | Modify an atomic proposition within a statement | | Linguistic | Change names | Oliver/Jacob → Elowen/Osiris | | Linguistic | Change role names | knight/knaves → saint/sinner | | Linguistic | Reorder | Shuffle statement order | | Linguistic | Role flip | Knights lie, knaves tell truth (tests instruction following) |

Perturbed puzzles come with automatically recomputed answers and reasoning steps. Researchers can precisely control "how much changed" and see whether models can still solve it.

Paper 1: Memorization or Reasoning? A Quantitative Probe

"On Memorization of Large Language Models in Logical Reasoning" (NeurIPS 2024), by Chulin Xie, Yangsibo Huang, Chiyuan Zhang, et al. (Google, UIUC, Princeton, AI2).

Core question: are high scores on reasoning benchmarks due to genuine reasoning or memorized similar problems?

Measurement — LiMem (Local Inconsistency-based Memorization Score):

LiMem(f, D) = Acc(f; D) × (1 - CR(f; D))

Acc(f; D): accuracy on training set D
CR(f; D): consistency ratio — fraction of correctly solved training problems still solved correctly after local perturbation
High LiMem = accurate on training set + collapses under perturbation = memorization-dominated
Low LiMem = accurate + stable under perturbation = reasoning-dominated

Findings:

1. After fine-tuning, training-set accuracy approaches 100%, but failure rates spike under slight perturbation — consistent with the memorization hypothesis. 2. Yet as memorization grows, generalization improves too. Memorization and reasoning are not mutually exclusive but coexistent. 3. High-memorization models are more robust in perturbation tests. While "memorizing," LLMs seem to learn some transferable reasoning structure. 4. Role flips are catastrophic. Llama3-8B's LiMem under role flip is ~80%. Models treat "knight = good person = truth-teller" as prior knowledge and ignore instructions — common-sense bias overriding instruction following. 5. Internal probing: logistic regression on MLP outputs across transformer layers shows fine-tuned models develop detectable reasoning representations in middle layers. 6. Training on wrong answers also improves generalization, as long as detailed reasoning steps are provided — similar to how humans learn from incorrect worked examples.

Conclusion: LLMs on K&K show a complex interplay of memory and reasoning — not pure memorizers, not pure reasoners. Reasoning seems to "crystallize" out of accumulated memory.

Paper 2: 7B Model Trained via RL to o3-mini Level

"Logic-RL: Unleashing LLM Reasoning with Rule-Based Reinforcement Learning" (MSRA & Ubiquant, arXiv:2502.14768).

Setup: 3–7 person K&K puzzles, <5,000 synthetic samples, REINFORCE++ (DeepSeek-R1-style reward design), Qwen2.5-7B, strict format reward + practical system prompt to prevent shortcuts.

Results (accuracy by number of people):

| Model | 2 | 3 | 4 | 5 | 6 | 7 | 8 (OOD) | Avg | |---|---|---|---|---|---|---|---|---| | o3-mini-high | 0.99 | 0.98 | 0.97 | 0.95 | 0.94 | 0.89 | 0.83 | 0.94 | | o1-2024-12-17 | 0.83 | 0.51 | 0.38 | 0.38 | 0.35 | 0.30 | 0.20 | 0.42 | | DeepSeek-R1 | 0.91 | 0.73 | 0.77 | 0.78 | 0.75 | 0.88 | 0.83 | 0.81 | | GPT-4o | 0.68 | 0.57 | 0.49 | 0.32 | 0.23 | 0.21 | 0.11 | 0.37 | | Qwen2.5-7B + Logic-RL | 0.99 | 0.99 | 0.94 | 0.92 | 0.91 | 0.80 | 0.67 | 0.89 |

The 7B model matches or exceeds o3-mini-high up to 7 people. On 8-person (out-of-distribution) problems it still scores 0.67, far above GPT-4o's 0.11.

Emergent phenomena:

1. Spontaneous use of formal logic formulas: the model employs implication formulas ("P true Q false is the only falsifying case") absent from training data. 2. Language switching: the model occasionally inserts Chinese mid-reasoning, then switches back to English for the answer — possibly using Chinese as an internal scratchpad for format rewards. 3. Transfer to math: training only on logic puzzles significantly improves mathematical reasoning — logic structure learning transfers across domains.

K&K in the Reasoning Ecosystem

| Project | Usage | |---|---| | Logic-RL (MSRA) | Primary training data; <5K samples train a 7B model | | NVIDIA NeMo Gym | One of 100+ Reasoning Gym tasks with configurable difficulty | | Phantom Reasoning | GRPO training, synthetic data generation | | DeepSeek R1 reproductions | One of four major training domains alongside MATH and Countdown | | mem-kk-logic | Memorization-vs-reasoning benchmark with perturbation sets | | Trae1ounG | Chinese-language K&K dataset |

Why K&K is an ideal tool:

1. Controllable difficulty via N, D, W parameters — unlike ill-defined "difficulty" in math problems. 2. Verifiable answers — unique solutions enable automatic reward computation, essential for RL. 3. Perturbable — local edits with recomputed answers make separating memorization from reasoning possible. 4. Domain isolation — K&K doesn't appear in any LLM's pretraining data (unlike possibly-leaked GSM8K), keeping tests clean. 5. Rich structure — and/or/not/imply/equivalence cover full propositional logic.

Limitations

K&K is propositional logic only — no quantifiers, modal logic, or higher-order reasoning. Conclusions may not generalize.
Role flips expose bias — common-sense priors sometimes outweigh instructions.
Small models need fine-tuning/RL — untrained Qwen2.5-7B-Instruct scores only 0.11 on 5-person puzzles.
o1 underperforms on K&K — o1-2024-12-17 scores 0.38 on 5-person puzzles vs o3-mini's 0.95, suggesting K&K is a sensitive reasoning probe.

Author's Take

K&K's value lies not in fun puzzles but in providing a controllable, verifiable, perturbable reasoning laboratory. LiMem gives an operational definition: if you can solve perturbed problems, you're reasoning; if only the originals, you're memorizing.

Logic-RL demonstrates an important scaling direction: not bigger models, but more precise task design plus RL, letting small models match large ones in narrow reasoning domains. This hints at a future of many specialized small models collaborating via tools/MCP rather than one monolithic model.

Notably, training on wrong answers still improves reasoning — LLMs abstract from the *structure* of reasoning processes, not directly from correct answers, strikingly similar to human learning from error analyses.

Finally, role-flip tests reveal irreducible common-sense bias: when told "knights always lie," models sometimes refuse to comply. Making models flexibly switch between common sense and strict rules is the next challenge.

> References: > - dmackinnon1.github.io/knaves > - K-and-K/knights-and-knaves (Hugging Face) > - Xie et al., "On Memorization of Large Language Models in Logical Reasoning", NeurIPS 2024 > - Logic-RL, "Unleashing LLM Reasoning with Rule-Based Reinforcement Learning", arXiv:2502.14768