[ICLR 2025] ZebraArena: Probing the Reasoning–Action Gap in Tool-Augmented LLMs

TL;DR

While Large Language Models (LLMs) are increasingly used as "agents" that call APIs and tools, we lack a clean way to measure their efficiency. ZebraArena solves this by turning the classic Einstein logic puzzle into a diagnostic testbed. By withholding clues and forcing models to "buy" info through tool calls, it proves that even GPT-5 is a "clumsy" agent—it gets the right answer but uses nearly 3x more tool calls than mathematically necessary.

The Problem: The Noise in Agentic Evaluation

Current benchmarks for agents (like WebArena or ToolBench) are "noisy." If a model fails to book a flight, is it because it can't reason, or because the website UI changed?

The authors identify four major flaws in existing benchmarks:

1. Complexity Confounds: Real-world environments (web/API) hide reasoning flaws behind interface complexity.
2. Memorization: Models might "remember" solutions from training data.
3. Shallow Reasoning: Some tasks only require a single retrieval step.
4. Inefficiency Blindness: Most benchmarks only reward the final answer, ignoring how much "resource" (tokens/queries) was wasted.

Methodology: The Logic Grid as an Oracle

ZebraArena uses the Zebra Puzzle (e.g., "The Englishman lives in the red house..."). In its standard form, these are Constraint Satisfaction Problems (CSPs) with a unique solution.

1. The Missing-Clue Setting

The environment removes a subset of clues ($C_{full}o{C}_0$), making the puzzle unsolvable with the provided information. The model must then interact with an environment to retrieve the missing constraints.

2. The ToolBox

Agents have two main tools:

• Fact Queries: "Does Eric like Dragonfruit?" (Decisive, low-level).
• Relation Queries: "Is the Red house to the left of the Green house?" (Strategic, high-level).

3. Metric: The "Efficiency Frontier"

The paper introduces the Inefficiency Ratio (IR): $IR=\frac{T}{K^{\ast }}$ Where $T$ is the total tool calls and $K^{\ast }$ is the theoretical minimum queries needed to reach a unique solution. An optimal agent has an $IR=1$.

Figure 1: The ZebraArena workflow showing the Background, Given Clues, ToolBox interaction, and final Solution grid.

Key Results: Accuracy $

eq$ Intelligence The experiments across GPT-5, Gemini 2.5 Pro, and Llama 3.3 reveal a massive gap between "frontier" and "open-source" models.

• The Efficiency Gap: GPT-5 is highly accurate (~99%) but significantly inefficient. It issues redundant queries or fails to plan the most informative questions, resulting in an IR of 1.7 to 3.7.
• Budget Anxiety: When told they have a "Tight" budget ($K^{\ast }$), models become "anxious"—their accuracy drops because they spend their few queries on non-decisive information.
• Token Explosion: Gemini-2.5-Flash requires over 20k tokens per puzzle compared to GPT-5's 1.2k, largely due to "vocalizing" redundant internal reasoning and excessive tool calling.

Figure 2: Scaling behavior showing accuracy dropping (middle) and tool calls rising (left) as the search space grows.

Critical Insight: Cost Sensitivity

One of the most fascinating experiments involved Pricing Signals. Can models adapt like economists?

• When Fact queries were made 20x cheaper than Relation queries, models shifted their strategy to use more Facts.
• However, they couldn't always find the "Pareto optimal" cost. Sometimes, they ignored a necessary (but expensive) Relation query and failed the puzzle entirely, showing that "cost-aware planning" is still a brittle skill in LLMs.

Conclusion & Future Impact

ZebraArena proves that being "smart" isn't enough for an agent; being efficient is the next frontier. The environment is now open-source, providing a "gym" for researchers to train agents that don't just solve problems, but solve them with the minimum necessary action.

Takeaway: We are moving from the era of "Can LLMs solve this?" to "How much does it cost for the LLM to solve this?"