Skip to content

DEPO: Dual-Efficiency Preference Optimization for LLM Agents

🕒 Published (v1): 2025-11-19 12:38 UTC · Source: Arxiv · Venue: AAAI 2026 · link

Ask a follow-up

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

💬 Ask ChatGPT✦ Ask Claude

TL;DR

DEPO introduces a formal two-dimensional efficiency definition for LLM agents—step-level (tokens per step) and trajectory-level (total steps)—and proposes an offline preference optimization method that encodes both dimensions as an additive bonus in a KTO-based loss. On WebShop and BabyAI, DEPO cuts token usage by up to 60.9% and step count by up to 26.9% while improving task success rates by up to 29.3%.

Problem

Prior work on LLM efficiency targets only token count per response, ignoring the compounding cost of multi-turn environment interactions where each API call adds latency and expense. Existing preference optimization methods (DPO, KTO, GRPO) optimize learning dynamics but have no explicit mechanism to reward agents for completing tasks in fewer steps or with more concise per-step reasoning. There is no standard definition of LLM agent efficiency to target.

Method

DEPO extends KTO (which applies prospect-theoretic sigmoid preference loss without requiring paired annotations) by augmenting the implied reward for desirable trajectories with an efficiency bonus:

\[b(\tau) = \frac{\alpha_1}{T_{\text{token}}(\tau)} + \frac{\alpha_2}{T_{\text{step}}(\tau)}\]

where \(T_{\text{token}}\) is mean tokens per step and \(T_{\text{step}}\) is total steps. The bonus is added only to the desirable branch's log-ratio; undesirable trajectories receive no modification. This creates a larger decision margin for efficient successful trajectories without altering the loss structure or requiring reward model training.

Training is two-stage: (1) SFT/behavioral cloning on MCTS-generated high-reward trajectories rephrased for conciseness via GPT-4.1 mini; (2) DEPO preference optimization contrasting desirable vs. mid-quality undesirable trajectories filtered by reward thresholds and step-count criteria.

Key Contributions

  • Formal dual-efficiency definition: step-level (tokens/step) and trajectory-level (steps/task), with efficiency only optimized over successful trajectories to preserve reasoning depth on hard tasks.
  • DEPO: parameter-independent efficiency bonus grafted onto vanilla KTO, requiring only offline desirable/undesirable labels—no paired annotations, reward model, or on-policy rollouts.
  • MCTS-based data generation pipeline (DeepSeek-V3 as search model) with reward-threshold labeling and an LLM rephrasing step to produce concise desirable demonstrations.
  • Empirical demonstration of generalization to out-of-domain math benchmarks and strong sample efficiency (25% data retains most gains).

Results

  • Token reduction vs. BC baseline: Llama-3.1-8B: −24.6% T@All, −38.4% T@All on BabyAI, up to −60.9% T@Succ. on BabyAI; Qwen2.5-7B: −28.4% T@All on WebShop, −56.7% T@Succ. on BabyAI.
  • Token reduction vs. vanilla KTO: Llama-3.1-8B: −18.4% T@All on WebShop, −4.4% on BabyAI; Qwen2.5-7B: −18.1% on WebShop, −25.5% on BabyAI.
  • Step reduction vs. vanilla KTO: Qwen2.5-7B: −26.9% S@All on BabyAI; Llama-3.1-8B: −12.9% S@All on WebShop.
  • Performance improvement vs. BC: Qwen2.5-7B: +29.3% success rate and +21.1% reward on BabyAI.
  • Out-of-domain generalization: Both models improve accuracy or maintain it on GSM8K, MATH, SimulEq while reducing tokens on most tasks.
  • Sample efficiency: With 25% training data, T@All efficiency already exceeds 10% improvement over BC; full data yields ~60% token reduction.
  • Baselines compared: BC, Token Budget (TB), vanilla KTO, DeepSeek-V3, R1-Distill-{Qwen-7B, Llama-8B}, Llama-3.1-8B-Instruct, Qwen2.5-{3B,7B,14B,72B}-Instruct.

Limitations

  • Efficiency bonus hyperparameters (α₁, α₂) require per-model tuning; optimal values differ between Llama and Qwen backbones.
  • Training data generated via MCTS using DeepSeek-V3, introducing dependency on a large proprietary model for data collection.
  • Evaluated on only two interactive agent benchmarks (WebShop, BabyAI) and three static math benchmarks; harder long-horizon or tool-use agent tasks are untested.
  • Efficiency is only enforced over successful trajectories; behavior on failing trajectories (which may also be verbose) is unaddressed.
  • Undesirable penalty ablation shows no benefit, but the reason (conflicting training signals or distribution mismatch) is not fully analyzed.

Relevance to Agentic AI / LLM Agents

DEPO directly addresses a practical deployment barrier for LLM agents: the multiplicative cost of multi-turn interactions where both per-step verbosity and total step count determine latency and API expense. The dual-efficiency framing is more principled than prior token-length penalties and is compatible with standard offline preference optimization pipelines, making it easy to incorporate into existing agent training stacks. The generalization to math benchmarks suggests the efficiency signal transfers beyond interactive environments, relevant to reasoning-heavy agentic chains. For researchers building or benchmarking agents, DEPO provides both a vocabulary (step-level vs. trajectory-level efficiency) and a concrete method for training agents that are fast without sacrificing reliability.