TL;DR
Large Language Models (LLMs) struggle with complex, multi-turn reasoning tasks that mirror real-world problem-solving. This paper introduces TurnBench, a novel benchmark that simulates an interactive code-breaking game to rigorously evaluate LLMs' multi-step, multi-turn reasoning capabilities, revealing significant performance gaps compared to humans.
What Problem Does This Paper Address?
Despite impressive advancements, current benchmarks for evaluating LLMs often fall short when it comes to assessing their ability to perform complex, iterative reasoning. Many existing tasks focus on single-turn or single-step problems, failing to capture the dynamic nature of real-world scenarios where information is gathered sequentially, hypotheses are tested, and feedback is incorporated over multiple interactions. Furthermore, current evaluation methods often prioritize final answer correctness, lacking insight into the intermediate reasoning process, and are susceptible to data contamination from pretraining corpora. This makes it difficult to truly understand and improve LLMs' reasoning abilities.
Methods
The core of this paper is the introduction of TurnBench, a novel benchmark designed to evaluate multi-turn, multi-step reasoning. TurnBench is based on an interactive code-breaking game inspired by the "Turing Machine Board Game." In this game, LLMs act as players trying to deduce a hidden 3-digit code. The game involves:
- Interactive Rounds: LLMs propose candidate codes and query "verifiers" for feedback.
- Structured Feedback: Verifiers provide binary PASS/FAIL results based on hidden logical or arithmetic rules (Hidden Active Criteria - HACs).
- Iterative Deduction: LLMs must use this feedback across multiple rounds to infer the rules, adapt their hypotheses, and eventually deduce the correct code.
TurnBench offers two modes:
- Classic Mode: Verifier responses directly correspond to their active criteria.
- Nightmare Mode: Introduces a randomized mapping between verifiers and their responses, adding a layer of complexity where LLMs must first infer this mapping before deducing the rules.
A key methodological contribution is an automated evaluation pipeline that analyzes the LLM's Chain-of-Thought (CoT) reasoning. This pipeline uses an "Inference Extractor" to identify the LLM's inferred HACs and a "Judger" to compare these inferences against ground truth, classifying them as Correct, Incorrect, or Include (partial overlap). This allows for a process-level evaluation beyond just final answer accuracy.
Datasets
The paper introduces TurnBench as a new benchmark. It comprises 540 game instances across two modes (Classic and Nightmare), each with three difficulty levels. The dataset includes game settings, ground truth codes, and detailed interaction logs and reasoning steps for both models and human participants. This is designed to be resistant to data contamination due to its dynamic rule configurations.
Key Insights and Ideas
- The "Thinking" Matters: LLMs that are explicitly designed or prompted to "think" (e.g., using Chain-of-Thought) perform significantly better, highlighting the importance of explicit reasoning steps.
- Error Recovery is a Major Hurdle: Once LLMs make an initial mistake in multi-turn reasoning, they struggle to recover, often ceasing to reason effectively or perpetuating errors. This suggests a lack of robust self-correction mechanisms.
- Model Scale is Crucial: Smaller LLMs (7-8B parameters) perform very poorly on TurnBench, indicating they lack the capacity for complex multi-turn reasoning. Performance scales significantly with model size, with larger models (70B+) and MoE architectures showing much better results.
- Human Performance is the Gold Standard: Humans achieve near-perfect accuracy in both Classic and Nightmare modes, underscoring the substantial gap that still exists between current LLMs and human reasoning capabilities in complex, interactive tasks.
Key Results
- Classic Mode: The best-performing LLM (gpt-04-mini-high with CoT) achieved 84% accuracy, while human participants achieved 100%.
- Nightmare Mode: Performance dropped drastically for LLMs, with the best model (gemini-2.5-flash) reaching only 13% accuracy, and gpt-04-mini-high failing completely on the Hard difficulty. Humans maintained high performance (average 94.2%).
- Error Persistence: Models often get stuck in error states, with the probability of producing an incorrect conclusion increasing sharply with each subsequent round after an initial mistake, nearing 100% by the fifth round.
- Model Size Impact: LLMs in the 7B-8B parameter range achieved near-zero accuracy, while 70B models reached 36% accuracy on a subset of games.
Limitations and Future Work
The authors acknowledge several limitations:
- Generality of Evaluation Framework: The automated evaluation framework, while effective, is rule-based and may lack generality.
- Inference Extraction Limitations: Using Gemini 2.5 Flash for inference extraction, while showing high accuracy, still has some limitations.
- Potential for Bias: As with any LLM evaluation, there's a risk of models producing biased outputs, which needs careful consideration when interpreting results.
Future work could focus on improving the generality of the evaluation framework, further optimizing inference extraction, and exploring more advanced methods for LLMs to manage uncertainty and recover from errors in multi-turn reasoning. The paper also suggests that scaling up models and exploring MoE architectures are promising directions for improving performance on such complex tasks.
Summary updated