Skip to content

TokenCliff: Benchmarking Output Token Budget Sensitivity in Multi-Turn LLM Agents

Conference: EMNLP 2026
Paper: ACL Anthology
Area: LLM Agent
Keywords: Agent Evaluation, Token Budget, Budget Elasticity, Cliff Index, Multi-Turn Interaction

TL;DR

TokenCliff introduces a controlled benchmark of 660 deterministic tasks across four core capability domains and a multi-step split, sweeping episode-level output token budgets from 200 to 8,192 tokens across 10 LLMs (33,000 episodes) to reveal performance cliffs of up to 32 percentage points and demonstrate that peak task performance and model scale do not guarantee budget elasticity.

Background & Motivation

Large language model (LLM) agents solve complex real-world tasks through iterative multi-turn interactions—alternating between internal planning, executing tool calls, observing environmental feedback, and revising candidate solutions before submitting a final decision. While this agentic paradigm powers high-value applications across software engineering, automated data analytics, and interactive web search, deploying such agents in production environments is fundamentally constrained by computation and latency budgets. The total volume of generated output tokens directly governs inference response latency, GPU compute saturation, and cumulative API consumption costs.

Despite its practical primacy, evaluating agents under output-token constraints remains a major blind spot. Prior research on resource-aware agent evaluation has predominantly focused on post-hoc monetary cost audits, explicit caps on tool-call invocations, or single-turn response truncation under restrictive length bounds. However, these paradigms fail to capture how an agent's multi-turn deliberation strategy behaves when the global episode-level output-token budget is systematically throttled. Evaluating agents in real-world or non-deterministic testbeds frequently conflates environment stochasticity, API jitter, and noisy LLM-as-a-judge scoring with the true degradation dynamics induced by resource constraints.

In a multi-turn trajectory, the output-token budget does not merely limit the length of the final answer; it dictates how many tokens the agent can allocate to reasoning, exploratory tool queries, and recovery from intermediate errors. When budgets shrink, do agents degrade gracefully by trimming extraneous reasoning, or do they collapse catastrophically when token capacity drops below an operational threshold? Core idea: isolate the episode-level output-token budget as the primary controlled experimental variable across 660 deterministic, simulator-backed multi-turn tasks spanning four core capability domains and a compositional multi-step split, formulating budget elasticity and the Cliff Index to quantify graceful degradation and abrupt failure thresholds.

Method

Overall Architecture

TokenCliff formalizes each benchmark instance as a deterministic tuple comprising an instruction, a simulation environment with encapsulated state, an exposed tool interface, and an automated programmatic verifier. The evaluation protocol keeps the task instance, environment dynamics, initial prompts, interaction interface, and scoring functions completely identical while strictly varying the episode-level output-token budget \(b\) across five approximately logarithmic tiers: 200 (B1, extreme), 500 (B2, tight), 1,500 (B3, moderate), 4,000 (B4, comfortable), and 8,192 (B5, high).

The end-to-end evaluation pipeline operates in a closed loop as illustrated below, executing seed-controlled task generation, dynamic budget-tracked multi-turn interactions, and deterministic fallback verification:

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["Input: Task prompt, toolset, and episode budget B1-B5"] --> B["Deterministic Multi-Domain Task Corpus Generation<br/>4 core domains + Multi-Step compositional split"]
    B --> C["Budget-Enforced Multi-Turn Agent Loop<br/>THINK/USE/SUBMIT protocol with per-turn 500-token cap"]
    C --> D["Fallback-Protected Deterministic Verification<br/>Tail output extraction and programmatic ground-truth matching"]
    D --> E["Output: Response curve, Budget Elasticity ε, and Cliff Index"]

Key Designs

1. Deterministic Multi-Domain Task Corpus Generation: Environmental non-determinism and external dependencies inject noise -> Seed-controlled synthetic Python sandbox generation -> Complete isolation of budget sensitivity from environment variance
Existing agent benchmarks that rely on public web APIs, live search engines, or active shell environments suffer from transient latency, shifting web schemas, and scoring variance that obscure small budget-induced performance changes. TokenCliff resolves this by constructing fully self-contained, reproducible Python simulation environments. The benchmark procedurally generates 660 tasks across two stages using fixed random seeds. The base generator creates 500 tasks evenly divided across four foundational domains (125 tasks each): virtual filesystem traversal and text aggregation (File Operations), SQL-like table filtering, aggregation, and relational joins (Data Transformation), sequential and conditional API parameter chaining (Tool Use), and calendar conflict resolution and scheduling optimization (Planning). A secondary generator creates 160 complex Multi-Step tasks: large-table filtering across 30–59 rows (50 tasks), multi-file extraction across 8–15 files (50 tasks), and chained arithmetic pipelines spanning 4–6 sequential operations (60 tasks). All underlying ground truths are derived programmatically, completely eliminating human or LLM-judge annotation noise.

2. Budget-Enforced Multi-Turn Agent Loop: Runaway reasoning in early turns exhausts budgets and prevents exploration -> Dynamic budget tracking, per-turn caps, and state reflection -> Rigorous measurement of multi-turn resource allocation strategies
Without explicit trajectory-level constraints, uncalibrated agents risk exhausting their entire token allowance on an overly verbose chain-of-thought in turn 1, artificially collapsing multi-turn planning into a single failed turn. TokenCliff enforces a controlled, dynamic execution harness. The agent is initialized with the global episode token limit \(b\) and restricted to emitting strictly one action marker per generation: THINK: for deliberation, USE: for tool invocations, or SUBMIT: for the final answer. Prior to each turn \(t\), the evaluator tracks cumulative completion tokens consumed in previous turns \(\sum_{\tau < t} c_\tau\), computes the remaining budget \(r_t = b - \sum_{\tau < t} c_\tau\), and injects an explicit budget status notice (Budget remaining: ~{remaining} tokens. Continue.) into the conversation context. Furthermore, each individual generation is clamped to \(\max\_tokens_t = \min(r_t, 500)\), maintaining a uniform 500-token per-turn ceiling that prevents early-turn monopolization while ensuring all models operate under identical single-step headroom.

3. Fallback-Protected Deterministic Verification: Premature budget exhaustion truncates explicit submission syntax -> Multi-tiered tail-generation extraction with exact programmatic verification -> Faithful recovery of underlying model capability near boundary thresholds
In ultra-low budget regimes (such as 200 tokens), an agent may deduce the correct answer on its final turn but hit the token cutoff before emitting the syntactic SUBMIT: prefix, or it may output a direct answer without proper tag framing. Treating all syntax slips as immediate failures artificially penalizes models for parser brittleness rather than substantive reasoning collapse. TokenCliff implements a robust, two-tier deterministic fallback rule: when an episode terminates due to token exhaustion or reaching the 20-turn limit without an explicit SUBMIT:, the evaluator extracts the model's final raw generation; additionally, if an output conforms to none of the THINK:, USE:, or SUBMIT: formats, it is treated as a candidate submission. The extracted candidate is then evaluated against the deterministic ground truth using exact match or canonical substring matching. This guarantees that model performance drops reflect genuine cognitive failure rather than superficial parser rejection.

Evaluation Metrics and Cliff Criterion

To formalize how agent capability degrades across resource tiers, TokenCliff establishes two complementary sensitivity metrics.

For an evaluated model \(m\) over \(K=5\) ordered logarithmic budget levels \(B = \{b_1, \dots, b_K\}\) (\(b_1 = 200\) to \(b_5 = 8,192\)), let \(s(m, b_k)\) denote mean task success at budget tier \(k\), and let \(s^* = \max_k s(m, b_k)\) denote peak performance. Budget Elasticity (\(\varepsilon\)) is defined as the normalized area under the success-budget curve (nAUC) computed via trapezoidal integration over log-scaled budgets:

\[\varepsilon(m) = \frac{1}{s^* \cdot (\log b_K - \log b_1)} \sum_{k=1}^{K-1} \frac{s(m, b_k) + s(m, b_{k+1})}{2} \cdot \Delta_k\]

where \(\Delta_k = \log b_{k+1} - \log b_k\). Integrating over log-budget intervals ensures that multiplicative budget doublings receive equal weight, preventing the high-token plateau from dominating the metric. By normalizing against peak accuracy \(s^*\), \(\varepsilon\) operates strictly as a shape-retention metric: a model retaining 80% of its peak accuracy across all budget tiers yields \(\varepsilon = 0.8\) irrespective of its absolute score. The benchmark also reports the unnormalized log-budget AUC, \(A_{\log}(m) = s^* \cdot \varepsilon(m)\), capturing absolute budget-averaged capability.

To capture the steepest localized degradation point, the benchmark defines the Cliff Index (\(\text{Cliff}\)) and its corresponding Cliff Location:

\[\text{Cliff}(m) = \max_{1 \le k < K} \left| s(m, b_{k+1}) - s(m, b_k) \right|\]

This identifies the single largest adjacent-budget performance drop (or gain when expanding budget). The Cliff Location pinpointing which adjacent boundary exhibits this maximum reveals the critical compute threshold where an agent's multi-turn loop undergoes an operational phase transition.

Key Experimental Results

Main Results

The primary benchmark evaluation encompasses 10 leading proprietary and open-weight models evaluated across 660 tasks and 5 budget tiers, totaling 33,000 complete interaction episodes. The table below presents the full budget-response spectrum sorted in descending order of Budget Elasticity \(\varepsilon\):

Model B1 (200) B2 (500) B3 (1.5K) B4 (4K) B5 (8K) Elasticity \(\varepsilon\) \(A_{\log}\) Cliff Index Cliff Loc.
Gemini-3.1-Flash-Lite 0.567 0.829 0.936 0.932 0.932 0.919 0.860 0.262 B1→B2
Qwen2.5-72B 0.353 0.532 0.605 0.609 0.597 0.910 0.554 0.179 B1→B2
GPT-4o-mini 0.388 0.636 0.723 0.735 0.727 0.900 0.661 0.248 B1→B2
Claude-Haiku-4.5 0.477 0.724 0.838 0.833 0.850 0.897 0.763 0.247 B1→B2
Qwen2.5-7B 0.271 0.352 0.359 0.405 0.368 0.884 0.357 0.080 B1→B2
Qwen3.6-Flash 0.374 0.565 0.753 0.733 0.758 0.860 0.651 0.191 B1→B2
Qwen3.5-35B 0.374 0.564 0.695 0.752 0.758 0.843 0.639 0.189 B1→B2
Qwen3.6-Plus 0.426 0.680 0.915 0.961 0.958 0.839 0.806 0.255 B1→B2
Qwen3.5-397B 0.391 0.711 0.906 0.973 0.964 0.833 0.810 0.320 B1→B2
DeepSeek-V3 0.300 0.561 0.861 0.918 0.917 0.794 0.729 0.300 B2→B3

Diagnostic & Ablation Studies

To isolate whether the observed cliffs are unique to multi-turn deliberation rather than one-shot generation length constraints, the authors evaluated a matched single-shot diagnostic across the identical 500 base tasks (providing the entire environment state in the prompt and asking for a direct answer):

Model Single-Shot \(\varepsilon\) Single-Shot Cliff Agent Loop \(\varepsilon\) Agent Loop Cliff Paired \(\Delta\varepsilon\) 95% Bootstrap CI
GPT-4o-mini 0.991 0.018 0.887 0.236 [0.079, 0.133]
Qwen2.5-72B 0.977 0.012 0.917 0.136 [0.041, 0.114]
Qwen2.5-7B 0.989 0.006 0.884 0.084 [0.040, 0.147]

To further illuminate behavioral causes behind budget failure, the authors analyzed all 10,994 failed episodes across models and categorized their mutually exclusive terminal outcomes (Table 6):

Model Budget Limit Exceeded (%) 20-Turn Limit (%) Wrong Submitted Answer (%) Early Direct Submission (%) Other / Format (%)
Gemini-3.1-Flash-Lite 60.6 2.4 29.4 1.5 6.0
Qwen2.5-72B 26.1 4.1 59.4 10.3 0.1
GPT-4o-mini 40.4 0.9 49.5 9.1 0.1
Claude-Haiku-4.5 50.9 10.3 30.5 4.4 3.9
Qwen2.5-7B 13.8 3.0 69.0 14.0 0.3
Qwen3.6-Flash 54.5 20.3 21.7 3.0 0.6
Qwen3.5-35B 66.8 10.0 21.0 2.0 0.3
Qwen3.6-Plus 89.1 6.0 4.6 0.0 0.3
Qwen3.5-397B 88.8 2.9 7.9 0.0 0.4
DeepSeek-V3 82.0 3.0 13.7 0.3 0.9

Key Findings

  • Large performance cliffs are concentrated at the lowest budget boundary: Across 9 out of 10 evaluated models, the steepest drop occurs between B2 (500 tokens) and B1 (200 tokens). The single sharpest cliff is observed in Qwen3.5-397B, which plummets by 32.0 percentage points (71.1% down to 39.1%). This demonstrates that 200 output tokens represents an irreducible minimum envelope required for an agent to perform one round of planning, tool invocation, environment observation parsing, and final synthesis.
  • Peak task performance does not imply budget elasticity: While Qwen3.5-397B achieves the highest overall peak accuracy (97.3% at B4), it ranks near the bottom in elasticity (\(\varepsilon = 0.833\), 9th out of 10). Conversely, Gemini-3.1-Flash-Lite (\(\varepsilon = 0.919\)) and Qwen2.5-72B (\(\varepsilon = 0.910\)) retain their relative performance far more robustly despite lower ceiling scores. Across the 10 models, peak accuracy and elasticity correlate weakly and negatively (\(\text{Spearman } \rho = -0.462, p = 0.179\)), proving that capability ceiling is orthogonal to resource adaptability.
  • Budget cliffs are an emergent property of multi-turn interaction loops: When tested on identical tasks in a single-shot setup, budget response curves remain virtually flat (\(\varepsilon \ge 0.977\), Cliff \(\le 0.018\)). In contrast, the multi-turn agent loop amplifies sensitivity by orders of magnitude (Cliff indices between 0.084 and 0.236), proving that cliffs originate from multi-turn deliberation dynamics and error-recovery failure rather than output string truncation.
  • Divergent terminal failure mechanisms across model families: Frontier dense and MoE models (Qwen3.5-397B, Qwen3.6-Plus, DeepSeek-V3) fail almost exclusively by exhausting the budget during intermediate reasoning before producing a submission (82%–89% of failures). In contrast, smaller models (Qwen2.5-7B, GPT-4o-mini) predominantly fail by prematurely submitting hallucinated or incorrect final answers within budget (50%–69% of failures).

Highlights & Insights

  • Operationalization of Agent Compute Phase Transitions: The paper provides the first formal framework treating episode output-token allowances as a direct independent variable, exposing the empirical phase transition where multi-turn agents collapse.
  • Zero-Variance Fully Deterministic Evaluation Suite: By engineering seed-controlled Python simulation environments with exact programmatic ground truths, the authors benchmarked 33,000 multi-turn episodes with total reproducibility for under $85 in API costs.
  • Decoupling Peak Capability from Curve Geometry: Introducing Budget Elasticity \(\varepsilon\) alongside \(A_{\log}\) provides practitioners with an actionable framework: models should be selected not merely by peak benchmark scores, but by matching their elasticity profile to production budget constraints.

Limitations & Future Work

  • Synthetic Simulation vs. Real-World Agent Tasks: The 660 tasks rely on controlled synthetic sandboxes (virtual filesystems, structured tables, and synthetic APIs). While this eliminates environmental noise, it remains to be proven whether identical cliff boundaries occur in noisy production environments like SWE-bench or live web browsing.
  • Omission of Input Context Growth and Reasoning Token Accounting: TokenCliff strictly meters observable completion tokens. In production deployments, multi-turn history accumulation dramatically scales input token costs and memory bandwidth, which were not modeled in the benchmark's scalar budget constraint.
  • vs BCAS / BATS: Previous studies introduced explicit resource constraints restricted to tool-call counts or single domain boundaries (e.g., search queries or RAG retrieval rounds). TokenCliff establishes a domain-general, multi-turn output-token budget benchmark evaluated across multiple capabilities.
  • vs AgencyBench / SWE-Effi: AgencyBench and SWE-Effi measure resource consumption as a passive dependent variable in long-horizon tasks. TokenCliff treats the budget as an active causal variable, systematically tracing the mathematical degradation curve across budget tiers.

Rating

  • Novelty: ⭐⭐⭐⭐⭐ [Pioneering benchmark isolating multi-turn output token budgets as a controlled causal variable]
  • Experimental Thoroughness: ⭐⭐⭐⭐⭐ [33,000 episodes across 10 models, 660 tasks, single-shot diagnostics, and failure taxonomy]
  • Writing Quality: ⭐⭐⭐⭐⭐ [Clear mathematical formalisms, cohesive prose narratives, and crisp empirical findings]
  • Value: ⭐⭐⭐⭐⭐ [Crucial benchmark for production agent deployment, budget-aware routing, and test-time compute optimization]