Query Your Way Out: Benchmarking Multi-Turn Knowledge Reasoning through Generalized Puzzle Solving

Xin Cheng; Junming Yang; Ning Xu

cs.CLOct 12, 2026

Query Your Way Out: Benchmarking Multi-Turn Knowledge Reasoning through Generalized Puzzle Solving

Authors: Xin Cheng, Junming Yang, Ning Xu

Organizations: School of Computer Science and Engineering, Southeast University, Nanjing, China.

Abstract

Puzzles offer a natural testbed for Large Language Models (LLMs) reasoning because they pose verifiable goals under partial information and require multi-step decisions to reach a solution. However, existing puzzle benchmarks typically focus on narrow environments with rigid mechanics and tightly constrained solution targets. To bridge this gap, we introduce the Active Probing Benchmark (APB), which generalizes puzzle-solving by casting concept identification as an interactive reasoning task that integrates specialized knowledge assessment into the puzzle setting. Specifically, APB evaluates whether models can acquire information via multi-turn active probing and inference to pinpoint 960 target concepts of specialized difficulty across eight diverse academic domains. Our evaluation reveals a counter-intuitive phenomenon: most open-source reasoning models significantly underperform their standard instruction counterparts. This finding suggests that in interactive settings, these models struggle to leverage procedural reasoning to reliably access and apply specialized domain knowledge. Beyond these empirical insights, APB provides a scalable pipeline for generating benchmarks that probe knowledge reasoning under interaction across diverse settings.

Figures & tables

Figure 1: Overview of the Active Probing Benchmark (APB) and representative performance results. (Left) Data construction : each puzzle specifies a target concept $P_{\text{target}}$ drawn from a generalized knowledge source (e.g., Wikipedia or domain documents) along with a reference document $I_{\text{ref}}$ . (Middle) Multi turn active probing : the model under test iteratively asks multiple-choice queries $Q_{t}$ , receives feedback $A_{t}$ from a knowledge oracle, and updates its hypotheses to reduce the candidate space until the target is identified or a turn budget is exhausted. (Right) Performance comparison : average success rates show that several open source “Thinking” models underperform their “No-Thinking” counterparts. Full results are reported in Table 2 .

Figure 2: Example episode from the Human Disease domain in APB, where the agent successfully identifies the target concept “Reticular dysgenesis”. Across turns, the agent acquires diagnostic evidence through queries and feedback, progressively narrowing the hypothesis set until the target is determined. The resulting interaction trace provides process-level evidence of how the model accesses and applies specialized knowledge.

Figure 3: The multi-stage, coarse-to-fine data filtering pipeline used to construct the Active Probing Benchmark from the English Wikipedia dump.

Group	$N$	Mean	Med.	Type
G1: Rejected (Stage 1)	1k	379.2	500 +	Common
G2: Rejected (Stage 4)	1k	86.7	19.0	Specialized
G3: Final (APB)	1k	59.3	16.0	Deep/Edge

Table 1: Topological Analysis of Concept Difficulty. In-link counts drop drastically, confirming the selection of “edge” knowledge.

Figure 4: Hierarchical distribution of puzzle targets across domains and sub-disciplines. Eight distinct color families represent the primary domains, while individual segments denote specific sub-topics. The area of each segment is proportional to the number of questions in that category. Exact distributions are provided in Appendix D .

Model	Bio	Dis	Chem	Phys	Math	CS	Econ	Phil	Avg.
GPT-5	34.2	37.5	33.3	34.2	34.2	25.0	39.2	30.0	33.4
Claude Opus 4	27.5	40.8	29.2	26.7	18.3	19.2	31.7	27.5	27.6
Claude Sonnet 4	29.2	35.0	23.3	23.3	17.5	18.3	42.5	21.7	26.4
o3	28.3	33.3	21.7	29.2	20.0	10.0	35.0	25.0	25.3
GPT-4o	26.7	24.2	20.0	17.5	11.7	10.8	25.0	20.8	19.6
Grok-4	14.2	30.8	16.7	13.3	10.0	13.3	20.8	21.7	17.6

Table 2: Success Rate (%) for various models across eight domains. The best performance in each domain is highlighted in bold . The bottom row, ’Domain Avg.’, summarizes the average performance for each domain.

Table 3: Detailed behavioral analysis metrics. PL : Probing Length, IG : Incorrect Guess rounds, IO : Incorrect Option rounds, IS : Incorrect Streak rounds, SR : Success Rounds, TR : Total Rounds. Blue bars visualize the normalized magnitude of each metric within its column to highlight behavioral patterns.

Figure 5: DeepSeek R1 reasoning trace for the target ’Reticular dysgenesis’ (Round 5). Top: The internal reasoning content shows the model brainstorming specific disease candidates following an incorrect guess. Middle: The extracted hypotheses visualize the diverse set of conditions considered during this step. Bottom: The generated follow-up question focuses on differentiating clinical features.

Appendix figures & tables12 assets

Supplementary material from the paper’s appendix.

Appendix

	Synopsys		Cadence Innovus
Model	ICC	ICC2	Common	Legacy	Avg.
Claude Opus 4	27.5	14.2	16.7	22.5	20.2
GPT-5	25.8	15.0	14.2	20.0	18.8
grok-4	15.0	10.8	18.3	24.2	17.1
o3	20.0	15.0	12.5	12.5	15.0
Claude Sonnet 4	14.2	10.8	9.2	18.3	13.1

Appendix

Table 4: Success rates (%) on the IC Back-End Puzzle Benchmark. Tools are grouped by vendor: Synopsys (ICC, ICC2) and Cadence Innovus (Common, Legacy). “NT” denotes “No-Thinking”. Qwen3 models refer to the Qwen3-235B-A22B variants. Best results in each category are bolded .

Figure 6: Ranking consistency analysis (DeepSeek V3 vs. Claude Sonnet 4) across eight domains. Each point represents a model’s performance in a specific domain. The distinct clustering of model colors and the high Spearman’s rank correlation (

\rho

) within each domain confirm that relative model rankings remain robust despite the absolute score shift caused by the stricter judge.

Effect of Temperature (Open-Source Reasoning)
Model	Configuration	Success Rate	Tier
DeepSeek R1	Temp = 0.2 (Default)	6.7%	Bottom
DeepSeek R1	Temp = 1.0 (Recommended)	8.3%	Bottom
Qwen3 Thinking	Temp = 0.2 (Default)	11.7%	Low
Qwen3 Thinking	Temp = 0.6	10.8%	Low
Effect of Reasoning Effort (GPT-5)

Appendix

Table 5: Ablation results on sampling temperature and reasoning effort (

N=120

). The “Tier” column reflects the relative ranking within the full benchmark context.

Model	QA	QA	QA Total	KO Comp.
	Prompt	Comp.	Tok.	Tok.
(Best Performance)
GPT-5	9,821	24,301	34,122	430
(Most Verbosity)
GPT-OSS-120B	14,034	58,471	72,505	473
Qwen3 235B Think.	33,414	24,170	57,584	473

Appendix

Table 6: A summary of token usage for representative models. ”Comp.” stands for Completion, ”Tok.” for Tokens. KO output is low due to fixed formatting.

Sub-Discipline	Count (%)
Molecular and Genomic Biology	29 (24.2%)
Genes, Proteins, and Nucleic Acids	16 (13.3%)
Gene Expression and Regulation	7 (5.8%)
DNA Structure and Dynamics	5 (4.2%)
Genetics and Inheritance	1 (0.8%)
Ecology and Evolution	24 (20.0%)

Appendix

Table 7: Biology Domain Composition.

Sub-Discipline	Count (%)
Systemic & Structural Genetic Disorders	35 (29.2%)
Multi-system Genetic Syndromes	14 (11.7%)
Skeletal and Overgrowth Syndromes	13 (10.8%)
Syndromes with Major Dermatologic Features	4 (3.3%)
Genomic and Inheritance Disorders	4 (3.3%)
Neurogenetic Disorders	18 (15.0%)

Appendix

Table 8: Human Disease Domain Composition.

Sub-Discipline	Count (%)
Organic Chemistry	27 (22.5%)
Named Reactions and Rearrangements	11 (9.2%)
Synthesis, Reagents, and Specific Compounds	8 (6.7%)
Reaction Mechanisms and Concepts	5 (4.2%)
Stereochemistry and Molecular Structure	3 (2.5%)
Biochemistry and Chemical Biology	27 (22.5%)

Appendix

Table 9: Chemistry Domain Composition.

Sub-Discipline	Count (%)
Quantum Field Theory	22 (18.3%)
Foundational and Axiomatic QFT	9 (7.5%)
Gauge Theories and the Standard Model	6 (5.0%)
Non-Perturbative and Topological QFT	3 (2.5%)
Supersymmetry and Beyond	2 (1.7%)
QFT in Curved Spacetime	2 (1.7%)

Appendix

Table 10: Physics Domain Composition.

Sub-Discipline	Count (%)
Geometry & Topology	37 (30.8%)
Algebraic Topology & Homotopy Theory	12 (10.0%)
General & Geometric Topology	12 (10.0%)
Differential & Geometric Analysis	11 (9.2%)
K-Theory	2 (1.7%)
Number Theory	19 (15.8%)

Appendix

Table 11: Mathematics Domain Composition.

Sub-Discipline	Count (%)
Theoretical Computer Science	43 (35.8%)
Mathematical Foundations	25 (20.8%)
Logic in Computer Science	12 (10.0%)
Computability and Complexity Theory	6 (5.0%)
Artificial Intelligence and Machine Learning	17 (14.2%)
Bayesian and Probabilistic Methods	5 (4.2%)

Appendix

Table 12: Computer Science Domain Composition.

Sub-Discipline	Count (%)
Pluralist Econ	34 (28.3%)
Behavioral and Experimental Economics	8 (6.7%)
Public Economics and Social Choice Theory	8 (6.7%)
Marxian Economics	7 (5.8%)
Other Theories and Applied Fields	6 (5.0%)
Economic History and History of Thought	5 (4.2%)

Appendix

Table 13: Economics Domain Composition.

Sub-Discipline	Count (%)
Philosophy of Religion and Interdisciplinary	31 (25.8%)
History of Philosophy and Specific Texts	10 (8.3%)
Philosophy of Religion and Theology	9 (7.5%)
Other Interdisciplinary Concepts	8 (6.7%)
Philosophy of Language	4 (3.3%)
Logic and Philosophy of Mathematics	20 (16.7%)

Appendix

Table 14: Philosophy Domain Composition.

Multi-Turn Language Model Reasoning

See all 11 papers

Pencil Puzzle Bench: A Benchmark for Multi-Step Verifiable Reasoning
Mar 2, 2026Justin WaughLLM Evaluation LLM Reasoning
Approximate Labs
General365: Benchmarking General Reasoning in Large Language Models Across Diverse and Challenging Tasks
Apr 13, 2026Junlin Liu, Shengnan An, Shuang Zhou +10LLM Reasoning Language Model Generalization
University of Chinese Academy of Sciences · Meituan
Self-Awareness before Action: Mitigating Logical Inertia via Proactive Cognitive Awareness
Apr 22, 2026Fulong Fan, Peilin Liu, Fengzhe Liu +2Abductive Reasoning Structured Reasoning
School of Software, Jilin University · School of Computer Science, Jilin University

Mar 2, 2026J/K move · Enter open · S save

Pencil Puzzle Bench: A Benchmark for Multi-Step Verifiable Reasoning

Justin Waugh

Approximate Labs

LLM Evaluation LLM Reasoning AI Agent Benchmarks Constraint Satisfaction

Open paper AskPDF arXiv

We introduce Pencil Puzzle Bench, a framework for evaluating large language model reasoning through pencil puzzles, a family of constraint-satisfaction problems closely related to NP-complete problems, with deterministic, step-level verification. From a database of 62,231 puzzles across 94 varieties with verified unique solutions, we select a benchmark of 300 puzzles spanning 20 varieties and evaluate 51 models from 11 providers in two modes: direct ask (single-shot) and agentic (multi-turn with iterative verification). A key differentiator of our benchmark is that every intermediate board state can be checked against variety-specific constraints, localizing errors to the exact rule violated, providing the infrastructure for dense, per-move reward signals for process supervision and reinforcement learning. Our evaluation reveals two distinct axes of capability: (1) reasoning effort scaling, where GPT-5.2 improves 81x from no reasoning to maximum effort; and (2) agentic iteration, where Claude Opus 4.6 rises from 0.3% to 30.0% through iterative checking, while GPT-5.2@xhigh improves from 20.2% to 56.0%. Agentic attempts span a median of 29 turns over 17 minutes, with the longest exceeding 1,221 turns and 14.3 hours - a demanding test of long-context utilization, not just reasoning.

Abstract

Multi-Turn Language Model Reasoning

Explore similar work

Pencil Puzzle Bench: A Benchmark for Multi-Step Verifiable Reasoning

General365: Benchmarking General Reasoning in Large Language Models Across Diverse and Challenging Tasks

Self-Awareness before Action: Mitigating Logical Inertia via Proactive Cognitive Awareness