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

🕒 Published (v1): 2026-07-14 17:59 UTC · Source: Arxiv · link

Why this paper was selected

Complexity-aware execution; reduces wasted tokens/steps in agent workflows, directly applicable

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

TL;DR¶

LLM agents routinely over-provision context on simple tasks, re-reading files and dependencies far beyond what the task requires. This paper formalizes that inefficiency, proposes E3 (Estimate, Execute, Expand)—a three-stage framework that estimates task scope upfront and expands only on verification failure—and demonstrates 85% cost reduction and 91% token reduction with no loss in task success rate compared to the strongest baseline.

Problem¶

Current LLM agents default to a maximum-context-first strategy: they gather maximal context before acting, regardless of task difficulty. This produces gross cognitive and execution redundancy on simple tasks. No prior work provides a formal, capability-invariant measure of wasted effort, nor a principled mechanism for agents to judge how much context a task actually warrants before committing budget.

Method¶

Formalization. A task is $\tau = (q, E, V)$. The trajectory cost is: $$C(\pi) = \alpha T_{\text{lat}} + \beta N_{\text{tok}} + \gamma N_{\text{tool}} + \delta N_{\text{file}}$$ The minimum-sufficient trajectory is $\pi^\star = \arg\min_\pi C(\pi)$ s.t. $P(\text{success}|\pi,\tau) \geq 1-\epsilon$. The Agent Cognitive Redundancy Ratio (ACRR) is: $$\text{ACRR}(\tau) = \frac{C_{\text{act}}(\tau) - C_{\min}(\tau)}{C_{\min}(\tau)}$$ ACRR = 0 is optimal; ACRR = 4 means 5× the necessary cost was spent.

E3 Framework. Three stages: 1. Estimate — map query + one cheap environment probe to an initial operating point $x_0 = (\hat{d}, \hat{s}, \hat{r}, \hat{c})$: estimated difficulty, scope (files/sites to touch), risk, and confidence. Lexical cues (explicit file references, localized verbs) and optional occurrence counting determine scope level. The estimator is deliberately optimistic/cheap. 2. Execute — run the minimum viable path sized to $x_0$: at scope level 1, localize and edit a single site; level 2, reuse cached search hits and edit direct sites; level 3, additionally follow imports via dependency_trace to reach indirect sites. 3. Expand — if verification fails, increment scope level by one (bounded by $K$), reuse cached hits, and replan. Never restarts from scratch; never jumps to reading everything.

Benchmarks. MSE-Bench: 121 deterministic, offline edits (single-file, cross-file, repo-level) with per-task oracle trajectories enabling exact ACRR measurement. LLM-Case: live harness with gpt-4o editing a real open-source library, graded by running the project's actual pytest suite.

Key Contributions¶

Formal definition of minimum-sufficient execution and the ACRR metric, enabling exact, capability-invariant measurement of wasted agent effort.
The E3 framework: anticipatory execution-scope estimation paired with verified progressive expansion, distinct from routing (which selects from a fixed menu) and adaptive computation (which dials a scalar effort level).
MSE-Bench: 121-task deterministic benchmark with per-task oracles; released publicly.
Empirical demonstration that E3 matches strongest baseline success (100%) while cutting cost 85%, tokens 91%, and inspected files 92%, and still beats a strong adaptive retrieval baseline by 16% cost reduction.
Concept of engineering-grounded AI (EGAI): agents whose effort is anchored in the engineering reality of the task, not unconstrained search.

Results¶

MSE-Bench (121 tasks, capability-controlled simulator):
Max-Context-First: 100% success, mean cost $C = 122.9$, ACRR = 12.90
Adaptive Retrieval baseline: 100% success, $C = 22.1$, ACRR = 1.21
Fixed ReAct: 66.9% success, $C = 17.2$, ACRR = 1.29
E3 (ours): 100% success, $C = 18.6$, ACRR = 0.55 — leanest fully-successful policy
E3 reduces cost by 85% vs. Max-Context-First, tokens by 91%, inspected files by 92%
E3 beats Adaptive Retrieval by 16% cost at equal success
Results hold under held-out instruction wording (deliberate lexical perturbations) and across essentially all cost weight settings
LLM-Case (live gpt-4o, real pytest oracle): over-reading confirmed but milder; E3 is leanest and fastest at comparable task success; one shortfall attributed to provider rate-limiting, not incorrect edits.

Limitations¶

MSE-Bench is a controlled simulator with capability-invariant editing; results do not directly transfer to deployed agents where model capability, not context scope, may be the bottleneck.
The estimator relies on lexical cues; tasks with misleading or ambiguous wording lower confidence and can trigger unnecessary expansion.
Indirect dependencies (aliases, re-exports) are genuinely harder to estimate and may cause under-estimation, requiring the Expand stage as a safety net—this adds latency in such cases.
LLM-Case validation uses a single model (gpt-4o) on one library; generalization to other models and codebases is asserted but not fully measured.
The cost model weights $(\alpha, \beta, \gamma, \delta)$ are configurable and somewhat arbitrary; results are stress-tested across weightings but the default choice of $\delta = 1.5$ (highest weight to file reads) drives many conclusions.
Paper is a controlled probe, explicitly framed not as a measurement of any deployed production system.

Relevance to Agentic AI / LLM Agents¶

This paper directly addresses a pervasive but under-formalized failure mode in LLM agent design: the absence of task-complexity awareness before acting. By introducing ACRR and minimum-sufficient execution as formal concepts, it gives the agent community a principled diagnostic tool that is orthogonal to capability benchmarks—measuring trajectory shape rather than correctness. E3's Estimate-Execute-Expand loop is a broadly applicable design pattern that complements existing reasoning strategies (CoT, ReAct, reflection) without replacing them, instead adding a meta-level judgment layer that those strategies currently lack. The work connects to the broader effort-allocation literature (test-time compute scaling, adaptive routing) but occupies a distinct niche: structured scope prediction before acting, with verified recovery, rather than reactive effort adjustment. For anyone building tool-using LLM agents for software engineering, coding assistants, or scientific workflow automation, this provides both a quantitative framework for measuring redundancy and a concrete architecture for reducing it.