Technical Summary: MTR-Bench

Problem Statement

Recent advances in Large Language Models (LLMs), particularly reasoning-enhanced variants like o1 and R1, have demonstrated significant capabilities in complex, single-turn reasoning tasks across domains such as mathematics, logic, and code generation. However, current evaluation benchmarks predominantly focus on static, single-turn scenarios. This leaves a critical gap in assessing multi-turn, interactive reasoning, which is essential for real-world problem-solving involving long-term planning, iterative feedback acquisition, and gradual refinement. Existing attempts to evaluate multi-turn capabilities, such as MT-Bench and GameArena, suffer from significant limitations: they often prioritize dialogue coherence over reasoning, rely on human evaluation (making them non-scalable and costly), or lack sufficient scenario diversity and controllable difficulty. Consequently, there is a lack of comprehensive, automated frameworks to assess whether frontier LLMs can maintain effective reasoning in dynamic, multi-turn environments.

Methodology

To address these gaps, the authors propose MTR-Bench, a comprehensive benchmark and fully automated evaluation framework designed specifically for multi-turn reasoning. The methodology consists of three core components:

1. Task Taxonomy and Construction

The benchmark comprises 40 distinct tasks categorized into four types, each targeting specific reasoning abilities:

• Information Probing (IP): Tasks requiring the discovery of hidden, fixed information through iterative queries (e.g., "Find the Impostors"). This evaluates Inductive Reasoning.
• Dynamic Adaptation (DA): Tasks where the target state evolves based on deterministic transformation rules after each interaction (e.g., "Password Breaker" with XOR-based changes). This evaluates Abductive Reasoning.
• State Operation (SO): Tasks involving hidden mechanics or control systems that must be inferred through action and observation (e.g., "Maze Navigation" with swapped controls). This evaluates Deductive Reasoning.
• Strategic Gaming (SG): Adversarial two-player scenarios where outcomes depend on dynamic interaction and opponent modeling (e.g., "Knight Battle"). This evaluates Planning Reasoning.

Each of the 40 tasks is generated with three difficulty levels (Easy, Medium, Hard) using parametric generators, resulting in 3,600 evaluation instances. The tasks are derived from high-difficulty sources like Codeforces (algorithmic problems) and New York Times (logic puzzles), manually adapted into structured, interactive templates with strict input/output formats.

2. Automated Interactive Framework

MTR-Bench employs a fully automated pipeline to eliminate human intervention and ensure scalability:

• Generator: Transforms problem templates into specific instances with controlled complexity parameters (e.g., grid size, number of players) to ensure solvability and varying difficulty.
• Monitor: Acts as a deterministic, rule-based environment. It validates model query formats, processes the interaction state, provides rule-specific feedback, and enforces termination conditions (e.g., correct answer, maximum turn limit of 15).
• Evaluator: Assesses the complete conversation history using multiple metrics:
  • Accuracy (Acc): Proportion of successfully completed tasks.
  • Efficiency (Eff): Relative comparison of turn counts between models on solved tasks.
  • Invalid Rate (IR): Proportion of interactions containing format violations or illegal moves.
  • Pattern Analysis (PA): Quantifies reasoning patterns including Association, Verification, Planning, and Feedback utilization.

3. Evaluation Protocol

The framework evaluates 20 models, including both reasoning-enhanced LLMs (e.g., o3-mini, R1, QwQ-32B) and non-reasoning models (e.g., GPT-4o, Qwen-Max, Llama-3.1). The evaluation is conducted in a zero-shot setting with built-in one-shot demonstrations to guide interaction formats.

Key Results

Extensive experiments reveal several critical findings regarding the current state of LLMs in multi-turn reasoning:

• Performance Gap: Even state-of-the-art reasoning models struggle significantly as task difficulty increases. o3-mini demonstrates the superior overall performance, particularly in Information Probing and Strategic Gaming, but still faces challenges in Dynamic Adaptation and State Operation tasks.
• Reasoning vs. Non-Reasoning: Reasoning-enhanced models significantly outperform their non-reasoning counterparts. Notably, smaller reasoning models (e.g., QwQ-32B) often surpass the strongest non-reasoning models (e.g., Qwen-Max) in the same series.
• Distillation Limitations: Distilled versions of reasoning models (e.g., R1-Distill) show performance comparable to non-reasoning models on these Out-of-Distribution (OOD) interactive tasks, suggesting that Supervised Fine-Tuning (SFT) distillation alone is insufficient for generalizing reasoning capabilities without Reinforcement Learning (RL).
• Efficiency vs. Accuracy: A trade-off exists between performance and efficiency. While o3-mini achieves the highest accuracy, it often requires more interaction turns than models like R1 or QwQ-32B, indicating that superior performance stems from better long-term planning and feedback integration rather than raw efficiency.
• Failure Modes: Analysis identifies specific failure patterns, including State Tracking Collapse (failing to update internal beliefs in dynamic tasks), Hasty Generalization (premature hypothesis locking), and Logical Constraint Violations (syntax-compliant but logically illegal moves). Smaller models (<7B parameters) and distilled models exhibit higher Invalid Rates, indicating weaker instruction-following and reasoning stability.

Significance and Contributions

The paper positions MTR-Bench as a necessary evolution in LLM evaluation, moving beyond static benchmarks to dynamic, interactive assessment. Its primary contributions are:

1. A Specialized Benchmark: The introduction of a high-quality, scalable benchmark specifically designed to assess reasoning capabilities in multi-turn interactive scenarios, covering four distinct reasoning types with fine-grained difficulty control.
2. An Automated Framework: The proposal of a fully automated evaluation system (Generator-Monitor-Evaluator) capable of producing infinite, tunable-complexity problems. This framework addresses the issues of data contamination and evaluation saturation inherent in static datasets, allowing the benchmark to evolve alongside model capabilities.
3. Empirical Insights: The provision of critical empirical evidence revealing the limitations of current frontier models in interactive reasoning. The findings highlight that while models excel in direct inductive inference, they struggle with abductive and deductive reasoning in dynamic environments, and that reasoning ability does not linearly correlate with interaction efficiency.

The authors conclude that MTR-Bench serves as a diagnostic tool for identifying specific cognitive deficits in AI systems and suggests that the interactive environments created within the benchmark could serve as valuable training grounds for developing specialized reasoning capabilities through reward-based learning.