DEPO: Dual-Efficiency Preference Optimization for LLM Agents

AI summary

Overview

Research area: Natural Language Processing — specifically reinforcement-learning-style preference optimization and efficiency for large language model (LLM) agents.

Technical level: Intermediate. The paper assumes familiarity with RLHF-style pipelines (PPO, DPO, KTO), KL-regularized policy optimization, and ReAct-style agent loops.

Scope: The paper defines a two-axis notion of "dual-efficiency" for LLM agents (tokens per step and steps per task) and proposes DEPO, an offline preference-optimization method that extends KTO with an efficiency bonus, validated on Webshop, BabyAI, GSM8K, MATH, and SimulEq.

What This Paper Is About

LLM agents that reason more often also talk more: long chains of thought mean more tokens generated per step, and inaccurate reasoning means more environment interactions (API calls, web actions) to finish a task. The paper argues that existing efficiency work only targets token count in a single response and ignores the cost of extra interaction steps, and that there is no systematic definition of agent efficiency. Its goal is to define agent efficiency along two dimensions — step-level (fewer tokens per step) and trajectory-level (fewer steps per task) — and to train agents that optimize both while keeping or improving task success.

Key Contributions

1. A formal definition of dual-efficiency for LLM agents, split into step-level efficiency (minimizing tokens generated per interaction step) and trajectory-level efficiency (minimizing the total number of interaction steps needed to complete a task), with the note that efficiency is optimized only among successful trajectories so that necessary long reasoning on difficult tasks is preserved.

2. DEPO (Dual-Efficiency Preference Optimization), an extension of vanilla KTO that adds an efficiency bonus — described as a parameter-independent offset — to the desirable log-ratio, jointly rewarding responses that use fewer tokens per step and trajectories that use fewer steps.

3. An offline data pipeline using Monte Carlo Tree Search (MCTS) with the UCT criterion to generate ReAct-style trajectories, a threshold-based desirable/undesirable labeling protocol, and a rephrasing model that polishes the Thought at each step while leaving the Action unchanged.

4. Comprehensive experiments across five benchmarks (Webshop, BabyAI, GSM8K, MATH, SimulEq) covering efficiency, performance, out-of-domain generalization, sample efficiency, and ablations over the bonus weights and over penalizing undesirable trajectories.

Main Findings

• Token reduction: DEPO achieves the lowest token usage on both Webshop and BabyAI. Reported reductions versus behavioral cloning (BC) reach 60.9% (T@All on BabyAI for Llama3.1-8B-BC+DEPO) and 60.3% (T@Succ. on BabyAI). Versus vanilla KTO, Llama3.1-8B-BC+DEPO reduces T@All and T@Succ. on Webshop and T@All on BabyAI by 18.4%, 11.8%, and 4.4% respectively; Qwen2.5-7B-BC+DEPO reduces T@All on Webshop and BabyAI by 18.1% and 25.5%.

• Step reduction: Qwen2.5-7B-BC+DEPO lowers S@All by 5.5% on Webshop and 26.9% on BabyAI relative to vanilla KTO; Llama3.1-8B-BC+DEPO lowers S@All and S@Succ. by 12.9% and 0.7% on Webshop and by 8.1% and 6.0% on BabyAI.

• Performance is not sacrificed: DEPO outperforms BC and vanilla KTO on success rate and reward. Llama3.1-8B-BC+DEPO improves Succ. and Reward on Webshop by 4.2% and 7.5% over vanilla KTO; Qwen2.5-7B-BC+DEPO improves them on BabyAI by 29.3% and 21.1%. The abstract reports up to a 29.3% improvement in performance, and the introduction describes the largest observed improvement as 29.3% relative to BC. Qwen2.5-7B-BC+DEPO achieves the highest Succ. and Reward on Webshop, while Llama3.1-8B-BC+DEPO attains the best results on BabyAI.

• Webshop gains come mainly from fewer tokens per step: For Llama3.1-8B-BC+DEPO, T@All/S@All drops 6.4% and T@Succ./S@Succ. drops 11.2% relative to vanilla KTO; for Qwen2.5-7B-BC+DEPO the reductions are 13.3% and 2.8%, even though the step count rises slightly in some cases.

• Out-of-domain generalization: DEPO consistently improves accuracy on SimulEq and on the average across GSM8K, MATH, and SimulEq for both models. Llama3.1-8B-BC+DEPO shows a clear token reduction; Qwen2.5-7B-BC+DEPO shows a slight increase on average; on MATH both models generally generate fewer tokens.

• Sample efficiency: With only 25% of the training data (245 samples for BabyAI and 783 for Webshop), DEPO still improves over the BC baseline, with T@All improving efficiency by more than 10%. With the full dataset, T@All achieves nearly a 60% improvement.

• Both bonus terms are needed: Ablations show that jointly setting both α₁ and α₂ (3 and 3 for Llama3.1-8B-BC, 2 and 2 for Qwen2.5-7B-BC) gives the best overall performance/efficiency trade-off. Optimizing a single term can improve an individual efficiency metric but typically costs performance.

• Penalizing undesirable trajectories does not help: Applying an equally strong penalty to undesirable samples degrades performance on both Webshop and BabyAI and raises T@All and S@All markedly, with the sharpest increase for Llama3.1-8B-BC on BabyAI (T@All +46.5%, S@All +39.4%), which is why the bonus is applied only to desirable trajectories.

Methodology in Plain English

The authors model the agent–environment interaction as a partially observable Markov decision process and set two objectives: high task success and dual efficiency, with efficiency counted only over successful trajectories.

First, they generate training trajectories with Monte Carlo Tree Search (maximum search depth 50, using DeepSeek-V3 for the search). Each step is ReAct-style: a natural-language Thought followed by an Action. MCTS runs the standard four stages — selection via UCT, expansion, rollout, and backpropagation of the final reward.

Second, they label trajectories by reward threshold: a trajectory is desirable if its reward is at or above an upper threshold, undesirable if its reward falls in an intermediate band, and anything below the lower threshold is discarded. Concretely, in BabyAI rewards with 0.9 ≤ r(τ) are desirable and 0.7 ≤ r(τ) < 0.9 undesirable; in Webshop r(τ) = 1 is desirable and the undesirable range is the same as BabyAI. They then filter by step count (fewer than 7 steps go to the desirable set, 7 or more to the undesirable set) and use GPT-4.1 mini at temperature 0.7 to rephrase the Thoughts, keeping Actions unchanged and ensuring desirable trajectories have fewer tokens per step after rephrasing.

Third, they cold-start the agent with behavioral cloning (BC) on a subset of desirable trajectories, minimizing the negative log-likelihood of the trajectory. BC alone is described as brittle under distribution shift because it has no negative signal.

Fourth, they apply DEPO. The key change is in the implied reward used by KTO's sigmoid preference loss with KL regularization: DEPO adds a bonus b(τ) to the log-ratio between the current policy and the BC policy. The bonus is α₁ divided by the average tokens per step plus α₂ divided by the total number of steps for desirable trajectories, and zero for undesirable ones. Larger token counts or step counts therefore shrink the bonus, lowering the reward and discouraging inefficient trajectories. The loss formulation and the undesirable branch are left unchanged. DEPO needs only offline desirable/undesirable labels — no paired annotations, no reward-model training, and no on-policy sampling.

Training details: BC used 972 trajectories from BabyAI and 3,732 from Webshop, with LoRA at a learning rate of 1.0e-4 for 3 epochs. The DEPO stage used 512 desirable and 471 undesirable BabyAI trajectories and 1,567 of each category for Webshop, with β = 0.2, λ_D = λ_U = 1, learning rate 2.0e-5, and 3 epochs. All experiments ran on eight NVIDIA Tesla A800 GPUs with 80GB memory each. Tokens were counted with the cl100k_base encoding from tiktoken, and step count is defined as the number of responses the model generates over an entire trajectory. Prompts use a ReAct-style 0-shot format without ICL or heavy CoT prompting.

Why This Matters

Impact on research. The paper shifts the efficiency conversation for LLM agents from "one response is too long" to "the whole interaction is too expensive," and gives that shift a measurable definition. It also shows that an efficiency-aware reward can be added to an offline, unpaired preference method (KTO) without reward models or on-policy sampling, which lowers the cost of reproducing this kind of alignment work. Reporting token and step counts separately for all trajectories and for successful trajectories only (T@All, S@All, T@Succ., S@Succ.) gives the community a more honest evaluation protocol than token counts alone.

Real-world applications.

• Web and tool-use agents: shopping, booking, or form-filling agents that call search and API endpoints each step — fewer steps means fewer paid API calls and less latency.
• Customer-facing assistants: shorter per-turn outputs plus fewer turns produce faster responses, which the paper identifies as a major barrier to real-world adoption.
• Cost-constrained deployments: the authors emphasize that latency and cost scale with steps, not just tokens, so the trajectory-level savings map directly to serving budgets.
• Data-limited fine-tuning: with as little as 25% of the training data (245 BabyAI samples, 783 Webshop samples) still showing gains, teams with small labeled trajectory sets can still apply the method.

Industry relevance. The dual-efficiency framing matches how production agent systems are actually billed and monitored — per-token generation cost plus per-step environment/API cost. A method that needs only offline desirable/undesirable labels, trains in 3 epochs with LoRA, and does not degrade success rate is a practical candidate for post-training deployed agents.

Future Directions

• Deriving α₁ and α₂ rather than tuning them: the ablation shows the two weights trade off against each other, and the best values differ by base model (3/3 for Llama3.1-8B-BC, 2/2 for Qwen2.5-7B-BC). A principled way to set or schedule them is an open question.

• Extending beyond two efficiency axes: the paper defines exactly step-level and trajectory-level efficiency; whether wall-clock latency, monetary API cost, or tool-call diversity deserve their own terms is untested here.

• Closing the out-of-domain token gap: DEPO reduces tokens clearly for Llama3.1-8B-BC but shows a slight average increase for Qwen2.5-7B-BC on the math benchmarks, so the conditions under which efficiency transfers across domains remain unclear.

• Understanding why penalizing undesirable trajectories hurts: the added penalty raised T@All by 46.5% and S@All by 39.4% for Llama3.1-8B-BC on BabyAI rather than helping, and the paper does not explain the mechanism behind this degradation.

Target Audience

Researchers and engineers working on LLM agents, agentic RLHF/preference optimization, and inference-cost reduction. It is most useful to readers who already understand DPO/KTO-style objectives and want a concrete, offline recipe for trading off response length against environment interactions — and to practitioners evaluating whether an efficiency-focused post-training step is worth adding to a deployed agent pipeline.

Authors’ abstract

Recent advances in large language models (LLMs) have greatly improved their reasoning and decision-making abilities when deployed as agents. Richer reasoning, however, often comes at the cost of longer chain of thought (CoT), hampering interaction efficiency in real-world scenarios. Nevertheless, there still lacks systematic definition of LLM agent efficiency, hindering targeted improvements. To this end, we introduce dual-efficiency, comprising (i) step-level efficiency, which minimizes tokens per step, and (ii) trajectory-level efficiency, which minimizes the number of steps to complete a task. Building on this definition, we propose DEPO, a dual-efficiency preference optimization method that jointly rewards succinct responses and fewer action steps. Experiments on WebShop and BabyAI show that DEPO cuts token usage by up to 60.9% and steps by up to 26.9%, while achieving up to a 29.3% improvement in performance. DEPO also generalizes to three out-of-domain math benchmarks and retains its efficiency gains when trained on only 25% of the data. Our project page is at https://opencausalab.github.io/DEPO.