Knights and Knaves: A Precision Probe for LLM Reasoning vs. Memorization

Forum topic · 小凯 · 2026-05-29

Summary

The Knights and Knaves puzzle, introduced by Raymond Smullyan in 1978, has been transformed into the K&K dataset, a programmatically generated benchmark for studying LLM reasoning. The dataset supports controllable difficulty (number of people, statement depth and width), automatic perturbation of both logical structure and surface wording, and auto-computed answers and chains of thought. A NeurIPS 2024 paper introduces LiMem, a memorization score showing that fine-tuned LLMs memorize and generalize simultaneously—reasoning ability appears to crystallize from memorization—while role-flip perturbations expose stubborn common-sense biases. Separately, the Logic-RL project (MSRA) trains Qwen2.5-7B with rule-based reinforcement learning (REINFORCE++) on fewer than 5,000 K&K samples, achieving 89% average accuracy and approaching o3-mini-high on puzzles of up to 7 people, with emergent use of formal logic notation, cross-domain transfer to math, and occasional Chinese-English code-switching during reasoning. This post surveys the dataset's engineering, both papers' findings, K&K's role in the reasoning ecosystem (NeMo Gym, DeepSeek R1 reproductions), and its limitations.

Overview

The classic 1978 logic puzzle "Knights and Knaves" (Raymond Smullyan) has become a precision instrument for studying LLM reasoning. On the island, knights always tell the truth and knaves always lie; given several statements, you must determine who is who.

Project page: dmackinnon1.github.io/knaves
Dataset: K-and-K/knights-and-knaves (Hugging Face)
Paper 1: "On Memorization of Large Language Models in Logical Reasoning" (NeurIPS 2024; Google, UIUC, Princeton, AI2)
Paper 2: "Logic-RL: Unleashing LLM Reasoning with Rule-Based Reinforcement Learning" (MSRA & Ubiquant, arXiv:2502.14768)

A Dynamic Puzzle Generator, Not a Static Benchmark

The K&K dataset is a programmatic generator with controllable parameters:

N (number of people): 2–8
D (statement depth): nesting level of logic
W (statement width): complexity per statement
Logical operators: and, or, not, imply, equivalence

It auto-generates problem descriptions, chain-of-thought reasoning steps, correct answers, wrong answers, and flawed CoTs.

Automatic perturbation is the key capability:

| Type | Level | Method | |------|-------|--------| | Mathematical structure | Replace whole statement | Swap in a newly sampled statement | | Mathematical structure | Replace leaf node | Change one atomic proposition | | Linguistic | Change names | Oliver/Jacob → Elowen/Osiris | | Linguistic | Change role words | knight/knaves → saint/sinner | | Linguistic | Reorder | Shuffle statement order | | Linguistic | Role flip | knights lie, knaves tell truth |

Perturbed puzzles come with recomputed answers and reasoning steps, letting researchers precisely control "how much changed."

Paper 1: Memorization vs. Reasoning, Quantified

The metric LiMem (Local Inconsistency-based Memorization Score):

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

Acc: accuracy on training set
CR: consistency ratio — fraction of correctly solved training puzzles still solved after local perturbation
High LiMem = accurate but collapses under perturbation = memorization-dominated
Low LiMem = accurate and stable = reasoning-dominated

Key findings:

1. Fine-tuned models hit ~100% on the training set but fail sharply under slight perturbation. 2. Memorization and generalization grow together — more memorization also improves unseen-test accuracy. They are symbiotic, not mutually exclusive. 3. High-memorization models are also more robust under perturbation; transferable reasoning structure seems to crystallize from memorization. 4. Role flips are catastrophic: Llama3-8B shows LiMem ≈ 80% under role flip. The model treats "knight = good person = truthful" as prior knowledge, overriding instructions — common-sense bias beats instruction following. 5. Probing with logistic regression on MLP activations reveals detectable reasoning representations in intermediate layers of fine-tuned models. 6. Training with wrong answers still improves generalization when detailed reasoning steps are provided — models learn from reasoning structure, like humans learning from incorrect solutions.

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

Setup: Qwen2.5-7B, REINFORCE++ (DeepSeek-R1-style reward), strict format rewards, <5,000 K&K samples (3–7 people).

| Model | 2p | 3p | 4p | 5p | 6p | 7p | 8p (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 |

Emergent phenomena:

1. Spontaneous formal logic: the model uses "If P then Q" implication rules not present in training data. 2. Language switching: it occasionally inserts Chinese as an internal scratchpad, then answers in English. 3. Transfer to math: training only on logic puzzles significantly improves math reasoning.

Why K&K Became a Standard Tool

| Project | Usage | |---------|-------| | Logic-RL (MSRA) | Main training data, <5K samples | | NVIDIA NeMo Gym | One of 100+ Reasoning Gym tasks | | Phantom Reasoning | GRPO training, synthetic generation | | DeepSeek R1 reproductions | Core training domain alongside MATH, Countdown | | mem-kk-logic | Memorization-vs-reasoning benchmark |

Reasons: difficulty is precisely controllable; answers are uniquely verifiable (essential for RL rewards); perturbations enable memorization/reasoning separation; and K&K is absent from pretraining corpora, unlike GSM8K.

Limitations

K&K covers only propositional logic — no quantifiers, modal logic, or higher-order reasoning.
Role flips expose non-erasable common-sense bias in LLMs.
Untrained Qwen2.5-7B-Instruct scores only 0.11 on 5-person puzzles; K&K remains hard without fine-tuning/RL.
o1 (2024-12-17) underperforms dramatically (0.38 on 5-person), showing K&K is a sensitive probe of reasoning-model differences.

Assessment

K&K's value lies in providing a controllable, verifiable, perturbable reasoning laboratory. It offers an operational definition: solve the perturbed puzzle and you're reasoning; solve only the original and you're memorizing. Logic-RL demonstrates a scaling direction based on precise task design plus RL rather than model size — the 7B model is more specialized, not more intelligent, pointing toward futures of small expert models collaborating via tool calls. And the fact that models learn from wrong answers (given correct reasoning steps) suggests LLMs abstract reasoning structure rather than copy conclusions — remarkably similar to human learning from solved mistakes.