Technical Summary: Do Agents Know What They Can't Do?

Problem Statement

Tool-using agents, which leverage Large Language Models (LLMs) to interact with external APIs and environments, often incur substantial computational costs due to long reasoning chains and iterative tool usage. In practical deployment scenarios, many tasks become infeasible because the specific capabilities required for successful completion are unavailable under current tool and environmental constraints.

Current agent benchmarks and evaluation paradigms largely assume tasks are solvable within the provided environment. They primarily reward persistent execution and final task success, often overlooking "brittle behaviors" where agents continue reasoning and invoking tools even after it becomes impossible to complete the task. This results in severe token waste and unnecessary interaction costs. Furthermore, constructing genuinely infeasible tasks for evaluation is challenging; existing methods rely heavily on labor-intensive human annotation or perturbation strategies that do not guarantee the removal of critical capabilities, potentially allowing agents to solve tasks via alternative strategies.

Methodology: FeasiGen

The authors propose FeasiGen, an automatic pipeline designed to construct infeasible agent tasks and evaluate an agent's ability to recognize them. The framework operates in three stages:

1. Data Collection: Tasks are collected from existing agent datasets (BFCL, StableToolBench, API-Bank, $\tau$-bench) that operate over a closed tool set, where each task is associated with a fixed, predefined pool of available tools.
2. Critical Tool Identification: The system executes multiple agent systems on the original solvable tasks. It collects successful tool-calling traces and identifies critical tools as the intersection of tools shared across all diverse successful execution strategies. The underlying hypothesis is that tools consistently required across different successful trajectories represent indispensable execution dependencies.
3. Infeasible Task Generation: The identified critical tools are masked (removed) from the candidate tool pool. This transforms the originally solvable task into an infeasible one under the constrained environment.

Evaluation Protocol:
The paper introduces feasibility-aware evaluation metrics beyond standard task success rates:

• False Continue Rate (FCR): Measures the proportion of infeasible tasks where the agent fails to detect the missing capability and continues execution instead of stopping.
• Token Cost to Early Stop ($TC_{early-stop}$) vs. Token Cost to Task Failure ($TC_{task-failure}$): Quantifies the efficiency trade-off, measuring tokens saved by early termination versus tokens wasted on failed execution.
• Feasibility-Aware Success Score (FASS): A unified metric combining correct feasibility detection and successful task completion on feasible tasks.

Human verification on a statistically grounded subset (95% confidence, 5% margin of error) confirmed that 94.7% of the constructed instances are genuinely infeasible.

Key Results

Experiments were conducted across nine modern models (including GPT-5.5, DeepSeek-V4, Qwen3.5, and Llama3.1 families) under both single-agent and multi-agent (planner–executor) architectures.

• Weak Infeasibility Detection: Current agent systems exhibit significantly weak ability to detect infeasible tasks. The False Continue Rate (FCR) ranges from 23.5% (best-performing GPT-5.5) to 73.9% (Qwen3.5-9B). This indicates that agents frequently waste resources attempting impossible tasks.
• Efficiency Impact: Failing to detect infeasibility is costly. The token cost of failed execution ($TC_{task-failure}$) is 2.3x to 5.0x higher than the cost of early stopping ($TC_{early-stop}$) across models.
• Multi-Agent Improvement: Multi-agent architectures significantly improve infeasibility detection. By introducing a planning stage that decomposes tasks and identifies required capabilities before execution, the average FCR drops from 54.6% (single-agent) to 17.5%. The best multi-agent pair (Qwen-122B $\to$ GPT-OSS) achieved an FCR of 2.6%.
• Reasoning Mode: Enabling reasoning modes generally improves detection and reduces token consumption for early stopping, though the effect varies by model size and family.
• Scaling Anomalies: Feasibility awareness does not scale uniformly with model size. While Qwen3.5 models show improved detection with larger parameters, Llama3.1 models degrade (FCR increases by 29.3% from 70B to 405B), suggesting that training choices and alignment objectives (e.g., rewarding engagement over refusal) influence this capability more than parameter count alone.
• Benchmark Contamination: The study observed "false positives" where agents generated correct answers for infeasible tasks without invoking tools. Manual analysis suggested 91% of these cases involved directly producing final answers, likely due to memorization of task outputs from pretraining corpora (benchmark contamination), rather than genuine reasoning about tool availability.

Significance and Contributions

The paper claims the following contributions:

1. FeasiGen Pipeline: The first automatic framework to construct infeasible agent tasks by identifying and masking critical execution dependencies, achieving over 94% accuracy in human verification.
2. Feasibility-Aware Evaluation: The introduction of metrics (FCR, token cost ratios) that explicitly measure an agent's ability to recognize constraints and terminate execution, addressing a gap in current evaluation paradigms that focus solely on task success.
3. Empirical Evidence of Limitations: Comprehensive evaluation reveals that current agents, even top-performing ones, struggle to recognize infeasible conditions, leading to significant resource waste.
4. Architectural Insights: The finding that multi-agent decomposition (specifically the planning stage) is a dominant factor in improving feasibility detection, offering a practical pathway to more efficient and robust agent systems.

The authors conclude that task success alone is insufficient for evaluating robust agent behavior in practical scenarios. They highlight that existing benchmarks may overestimate true agent capability due to memorization and a lack of constraint-aware reasoning, urging the community to incorporate feasibility detection into standard evaluation protocols.