Technical Summary: Do AI Agents Know When a Task Is Simple? Toward Complexity-Aware Reasoning and Execution

1. Problem Statement

Large Language Model (LLM) agents increasingly automate multi-step engineering workflows, yet they frequently exhibit a specific inefficiency: they fail to distinguish between simple and complex tasks. Instead of tailoring their effort to the task's actual requirements, many agents default to a "maximum-context-first" strategy. This involves re-reading files, re-analyzing dependencies, and gathering extensive context even for trivial edits (e.g., a single-line replacement). While this caution ensures correctness on complex tasks, it incurs massive cognitive and execution overhead on simple ones, turning seconds-long tasks into small code-base audits.

The paper argues that the missing capability is task-aware execution-scope estimation: the ability to judge a task's difficulty, identify the minimal information required, and determine the shortest reliable path before committing computational budget.

2. Methodology

2.1 Formal Definitions

The authors formalize the problem using a task definition $\tau = (q, E, V)$, where $q$ is the query, $E$ is the environment (e.g., a code repository), and $V$ is a verification check.

• Cost Model: The cost of a trajectory $\pi$ is defined as $C(\pi) = \alpha T_{lat} + \beta N_{tok} + \gamma N_{tool} + \delta N_{file}$, weighing latency, tokens, tool calls, and fully inspected files.
• Minimum-Sufficient Execution ($\pi^\star$): The cheapest trajectory that satisfies a reliability target ($P(success) \ge 1-\epsilon$). In a controlled environment, this serves as an "oracle" ($C_{min}$).
• Agent Cognitive Redundancy Ratio (ACRR): A normalized metric for wasted effort: $ACRR(\tau) = (C_{act} - C_{min}) / C_{min}$. An ACRR of 0 indicates an optimal agent; higher values indicate redundancy.

2.2 The E3 Framework

The paper proposes E3 (Estimate, Execute, Expand), a three-stage framework designed to mimic the engineering practice of forming a rapid estimate before acting:

1. Estimate: The agent estimates an initial operating point $x_0 = (\hat{d}, \hat{s}, \hat{r}, \hat{c})$, representing estimated difficulty, scope (files to touch), risk, and confidence. This is done via a lightweight, deliberately optimistic estimator using lexical cues and a single cheap probe.
2. Execute: The agent executes a minimum viable path sized to $x_0$. For example, if the estimate suggests a single-file edit, the agent locates, edits, and verifies only that file.
3. Expand: If verification fails or confidence is low, the agent progressively expands the scope (e.g., moving from single-file to cross-file to repository-level tracing) rather than restarting or gathering everything at once. This expansion is bounded and monotone, ensuring the agent degrades gracefully toward an exhaustive strategy only when necessary.

2.3 Evaluation Environment: MSE-Bench

To isolate execution redundancy from raw model capability, the authors introduce MSE-Bench, a deterministic, offline benchmark of 121 tasks.

• Design: Tasks are procedurally generated across three tiers: Level 1 (single-file), Level 2 (cross-file), and Level 3 (repository-level with deceptive wording hiding indirect dependencies).
• Oracle: Every task includes a pre-computed oracle trajectory ($\pi^\star$) defining the exact minimum cost, allowing for precise measurement of redundancy.
• Capability Control: The environment ensures that any policy capable of seeing the relevant content can make the edit; differences in success and cost arise solely from how much context the policy chooses to gather.

2.4 Real-Model Validation: LLM-Case

To address concerns about synthetic simulations, the authors release LLM-Case, a harness using a real $gpt-4o$ agent, real tools, and a real open-source library (toml). Success is graded by running the project's actual pytest suite against a measured oracle.

3. Key Contributions

1. Formalization: Defined minimum-sufficient execution and the Agent Cognitive Redundancy Ratio (ACRR) to quantify wasted effort relative to an oracle.
2. Framework: Proposed E3, a task-aware execution framework that constructs an initial operating point and uses verified progressive expansion instead of maximum-context-first exploration.
3. Benchmark: Built MSE-Bench, a capability-invariant benchmark with exact oracles to measure redundancy precisely.
4. Validation: Demonstrated that E3 matches the success of strong baselines while drastically reducing cost, and validated these findings on a real LLM agent with real code.

4. Results

4.1 MSE-Bench Findings

• Efficiency: E3 achieved 100% success on all 121 tasks, matching the strongest baselines.
• Cost Reduction: Compared to the "Max-Context-First" (MCF) baseline, E3 reduced:
  • Scalar cost by 85%.
  • Tokens by 91%.
  • Inspected files by 92%.
• Comparison with Adaptive Baselines: E3 also outperformed a strong Adaptive Retrieval (AR) baseline (which solves all tasks but over-gathers context on simple ones) by 16% in cost and 67% in inspected files.
• Redundancy Pattern: The study found that redundancy is highest on the simplest tasks. MCF exhibited an ACRR of 22.1 on Level 1 tasks (simple edits) versus 5.4 on Level 3, confirming that the "gather everything" instinct is most wasteful when the task is trivial.
• Robustness:
  • Instruction Wording: When tested on held-out, paraphrased instructions that broke the estimator's lexical cues, E3 maintained 100% success (with only an 8.7% cost increase) because the Expand stage recovered under-estimated tasks.
  • Cost Weighting: E3 remained the cheapest fully-successful policy in 99.8% of 4,000 random cost weightings.

4.2 LLM-Case Findings

On a real $gpt-4o$ agent editing a real library:

• Frugality: Even the "thorough" baseline (prompted to "read everything") was more frugal than the simulated MCF, inspecting only 1–4 files rather than the entire repository.
• Performance: E3 was the leanest and fastest policy overall. It used 18% fewer tokens and had 18% lower latency than the thorough agent.
• Reliability: On deceptive, high-complexity tasks, the heaviest-reading trajectories (thorough agent) were the most likely to fail due to rate limits or step-budget exhaustion, whereas E3 remained among the reliable runs.

5. Significance and Claims

The paper positions task-aware execution as a step toward Engineering-Grounded AI (EGAI): agents whose effort is anchored in the physical and procedural reality of the task rather than unconstrained search.

• Core Argument: True efficiency is not just solving hard problems but recognizing when a problem is easy. The authors argue that a "good initial operating point" (analogous to power-flow analysis) allows for fast, stable convergence, whereas exhaustive search is often irrational for simple tasks.
• Modest Claims: The authors explicitly state that their results are properties of policies under a cost model, not measurements of a specific deployed agent's raw intelligence. They emphasize that the simulator isolates "trajectory shape" from model capability.
• Conclusion: The redundancy studied is about the shape of the execution trajectory. The E3 framework demonstrates that an agent can be both highly reliable and highly efficient by estimating scope upfront and expanding only when evidence demands it. The paper concludes that this "knowing when a task is simple" is a critical, under-studied competence for autonomous agents.