Technical Summary: Evaluating Interactive Reasoning in Large Language Models

Problem Statement

Current evaluations of Large Language Model (LLM) reasoning are predominantly static, presenting models with fully specified problems and requiring a single-shot answer. This paradigm fails to assess reasoning as an active process of information acquisition and belief updating. Furthermore, static benchmarks often conflate two distinct failure modes: a knowledge deficit (lack of necessary facts) and a reasoning deficit (failure to utilize available information correctly). Existing multi-turn benchmarks often mix reasoning with world knowledge, dialogue skills, or instruction following, and frequently lack the scale or structural diversity to disentangle specific reasoning capabilities. There is a need for a framework that treats reasoning as sequential evidence acquisition under partial observability, isolates reasoning from factual recall, and probes higher-order capabilities like robustness and metacognition.

Methodology

The authors propose a hierarchical framework for interactive reasoning evaluation, instantiated as a benchmark of 474 executable games.

1. Interactive Reasoning Backbone

The core of the framework formulates reasoning as a state-search problem under partial observability.

• Setup: The LLM receives only the task rules and a hidden environment state. It must iteratively issue targeted queries to gather partial evidence, update its beliefs, and decide when to submit a final answer.
• Structure: Games are built from minimal structural primitives to avoid reliance on real-world knowledge. They span four canonical data structures (sets, sequences, trees, graphs) and three inference modes (deductive, inductive, abductive).
• Protocol: The interaction follows a structured action format (e.g., <submit>answer</submit>) to ensure reliable parsing. The environment responds to queries or evaluates submissions.
• Difficulty: Each game is evaluated under five fixed configuration search spaces, corresponding to five difficulty levels defined by the size of the latent search space (e.g., cardinality of sets, depth of trees).

2. Higher-Order Evaluation Layers

Beyond the basic interactive search, the framework introduces two layers to probe advanced capabilities:

• Contextual Robustness: Tests whether reasoning is preserved under:
  • Isomorphic Perturbation: Semantically enriched variants (e.g., changing graph nodes to patients) that preserve the underlying logic but alter surface form.
  • Intra-game Noise Injection: Adding irrelevant text to rules or responses.
  • Inter-game Boundary Control: Introducing a new game without resetting the interaction history to test context switching.
• Metacognitive Adaptation: Tests the model's ability to manage its internal reasoning state:
  • Counterfactual Revision: The environment corrects a previous observation mid-game, requiring the model to update its beliefs and revise its search strategy.
  • Necessity Judgment: The model is given full evidence, asked to solve the problem, and then asked to identify and remove redundant observations to form a minimal supporting set.

3. Benchmark Construction

The benchmark consists of 474 games (totaling 2,370 instances across difficulty levels). To ensure quality and scalability, the authors employed a hybrid human-LLM construction strategy:

• Rule Generation: Frontier models generated candidate rules under strict constraints regarding hidden states, query types, and solvability.
• Program Generation: A templated interface was used to generate executable environments, with LLMs implementing only game-specific logic.
• Filtering: Games were filtered based on preliminary model performance to remove those that were too easy (>90% success), too hard (<10% success), or ambiguous. Manual review further refined the set.

Key Results

The authors evaluated a broad set of frontier models (including Qwen3-max, Deepseek-3.2, Claude-4.5, GPT-5.4, and various Gemini versions) on the benchmark.

• Discriminative Power: The benchmark effectively differentiates models. Success rates ranged from ~43% to ~74%. Gemini-3.1-pro achieved the highest success rate (74.21%) and efficiency, while Claude-4.5 showed comparable accuracy but required nearly twice as many turns, indicating lower interaction efficiency.
• Reasoning Regimes:
  • Deductive reasoning was consistently the easiest for all models, likely due to training data emphasis.
  • Abductive reasoning and set-based tasks were the most challenging, with sets proving harder than trees or graphs due to the lack of explicit structural cues.
• Contextual Robustness:
  • Isomorphic Perturbation: Caused moderate but consistent performance drops (e.g., Gemini-3.1-pro dropped ~5-6%), indicating difficulty in preserving abstract reasoning under semantic shifts.
  • Noise Injection: Consistently reduced performance, suggesting models struggle to filter irrelevant content while tracking active evidence.
  • Boundary Control: Surprisingly, performance remained stable or slightly improved when new games were introduced without history reset, suggesting models can recognize task boundaries.
• Metacognitive Adaptation:
  • Counterfactual Revision: Caused significant performance drops (e.g., Gemini-3.1-pro dropped from 74.21% to 57.56%), revealing a qualitative weakness in updating internal reasoning states when evidence changes.
  • Necessity Judgment: Models frequently removed a large fraction of observations (62–83%) but failed to preserve the correct answer after pruning. Success rates plummeted after pruning (e.g., from 70.76% to 48.87% for Gemini-3.1-pro), indicating models are better at using evidence when present than at identifying indispensable evidence.
• Failure Modes: The dominant failure mode was FormatError (failure to follow the structured protocol), rather than timeouts, highlighting the challenge of maintaining protocol compliance over multiple turns.

Significance and Claims

The paper claims to provide a contamination-resistant and diagnostically rich framework for evaluating LLM reasoning. By treating reasoning as active evidence acquisition, the benchmark isolates reasoning deficits from knowledge deficits.

The authors assert that while current frontier models demonstrate non-trivial interactive reasoning abilities, they remain substantially weaker in:

1. Robustness: Maintaining performance under semantic perturbations and noise.
2. Belief Revision: Updating reasoning when earlier evidence is corrected.
3. Evidence Attribution: Distinguishing between sufficient and necessary information.

The work suggests that current models are better at solving problems under fixed evidence than at maintaining a revisable account of why an answer is correct. The authors position this benchmark as a tool for future work in reasoning diagnostics, training-time interventions, and interactive reinforcement learning, noting that the executable nature of the environment allows for explicit interaction protocols.

The paper modestly acknowledges limitations, including the inability of fixed configuration spaces to fully capture the continuous nature of real-world reasoning challenges and the potential oversimplification of interaction dynamics due to the structured XML-based action format.