Source-linked AI summary
Selective Critique for Cost-Aware LLM Agents in Long-Horizon Decision Making
Heewon Park, Somin Im, Minhae Kwon
TL;DR
Long-horizon LLM agents face a reliability challenge, while critique can add substantial token and latency costs and is not always helpful. SAG selectively gates critique using action ambiguity and distills successful trajectories into the actor; across benchmarks, it improves the performance–cost trade-off, including a 3.1× normalized token-efficiency gain on ALFWorld.
Problem
Long-horizon LLM agents must balance reliability against critique’s added token, latency, and monetary costs, while fixed schedules offer limited guidance on when critique is warranted.
Source: §1 · pp. 1–2Method
SAG gates critic queries step by step using action-level ambiguity as a proxy for critique value, then periodically fine-tunes the actor on successful trajectories.
Source: §1 · p. 2, §3.4 · p. 5Results
Takeaways & Limitations
Selective critique provides a practical and scalable pathway to improve LLM-agent reliability and efficiency in complex sequential environments.
Source: §7 · p. 9The study focuses on representative long-horizon interactive benchmarks; evaluation in additional real-world agent settings would further inform generality.
Source: A Broader Impacts and Limitations · p. 16
Abstract
from arXiv · showhide
Improving the reliability of large language model (LLM) agents in long-horizon decision-making remains a key challenge. When deployed as autonomous agents interacting with complex environments, early mistakes can propagate through trajectories and cause cascading failures. Recent approaches improve reliability by incorporating external critique or deliberation, but invoking these mechanisms at every step substantially increases token consumption and latency, limiting practical deployment. We propose SAG (Self-improving Agent with Gated critique), a cost-aware framework that formulates critique invocation as a step-wise decision problem during long-horizon interaction. SAG introduces a lightweight, training-free gating mechanism that estimates the utility of critique using action-level ambiguity signals--global entropy and local top-2 margin--computed over admissible actions. From a decision-theoretic perspective, this mechanism approximates the Value of Information (VoI) of critique, enabling the agent to selectively allocate expensive feedback only when its expected benefit justifies the cost. SAG further incorporates online bootstrapped self-improvement, allowing the actor to internalize critic-assisted behaviors and progressively reduce reliance on critique. Across three long-horizon interactive benchmarks and multiple backbone models, SAG substantially improves the performance-cost trade-off compared with both no-critique and always-on critique agents. On ALFWorld, SAG increases task success from 24.6% to 78.4% while maintaining a token budget comparable to ReAct, yielding a $3.1\times$ improvement in normalized token efficiency. Moreover, a 7B actor with a lightweight 3B critic achieves performance comparable to a 14B actor without critique, showing that selective critique can recover most of the reliability benefits of deliberation while dramatically reducing inference cost.
1 Introduction
Long-horizon LLM agents face costly critique decisions: always-on feedback can improve success while reducing efficiency. SAG uses action ambiguity to gate critique and distills successful trajectories into the actor, improving the performance–cost trade-off.
1 Introduction
- Long-horizon interaction remains challenging because early decision errors can propagate across steps and lead to irreversible failures.Large-scale environment rollouts can produce task-specific policies but require substantial training compute and infrastructure.Source: §1 · p. 1
- Critique adds inference, context, token, latency, and monetary costs, while imperfect critic advice may not improve the next action.Existing methods often use fixed or heuristic critique schedules, offering limited guidance on when its cost is warranted.Source: §1 · p. 2
- SAG frames critique as a step-wise, cost-aware decision and uses entropy and top-2 margin over admissible actions to gate critic queries.The gate uses action-level ambiguity as a lightweight proxy for critique value; successful trajectories are periodically distilled into the actor through online SFT.Source: §1 · p. 2, Figure 2 · p. 3
- 24.6% to 78.3% success on ALFWorld and 3.1× normalized token efficiency versus ReAct show SAG improves the success–cost trade-off.SAG maintains a token budget comparable to ReAct; Figure 1 contrasts its high success and efficiency with always-on critique.Source: §1 · p. 2, Figure 1 · p. 2
2 Related Work
Related work improves LLM agents either during execution through feedback and adaptation or before deployment through policy training. SAG targets deployment-time interaction, deciding when a non-oracle critic is worth its cost.
LLM agents in interactive environments
- Deployment-time methods use prompting, deliberation, feedback, or lightweight adaptation, while pre-deployment approaches use preference optimization, rollouts, or post-training RL.The latter often require substantial task-specific compute before deployment.Source: §2 · p. 3
Critique and cost-aware improvement
- Prior critic-guided and self-improvement methods can incur overhead through frequent critique, repeated sampling, fixed schedules, or multiple candidate evaluations.Adaptive-computation work allocates extra inference using confidence or uncertainty, but critique in long-horizon agents is still often triggered by fixed heuristics.Source: §2 · p. 3
- SAG distinguishes itself by treating critique as a cost-aware step-wise decision and querying a non-oracle critic using ambiguity signals motivated as proxies for VoI.This targets the deployment-time regime with an available actor and critic.Source: §2 · p. 3
3 Gated Critic-guided Self-improving Agent
SAG treats critic invocation as a step-wise, cost-sensitive decision, using actor ambiguity to gate critique and successful interaction trajectories to support online actor updates.
3.1 Problem Formulation
- The actor scores admissible actions from its reasoning state and induces a distribution over those candidates before deciding whether to query the critic.Critic invocation is binary and incurs additional cost; without a query, the actor executes its top-ranked action.Source: §3.1 · pp. 3–4
3.2 Ambiguity Signals from the Actor
- SAG measures global ambiguity with normalized entropy and local ambiguity with the log-probability margin between the top two actions.Entropy is set to zero when fewer than two actions are admissible; the margin is set to infinity when fewer than two are available.Source: §3.2 · p. 4
3.3 Gated Critic Invocation
- The gate combines normalized entropy with a binary indicator for a small margin, then compares the bounded score with a cost-calibrated threshold.A higher critic cost leads to more conservative critic use; the binary margin indicator targets high-risk near-boundary decisions rather than fine-grained calibration.Source: §3.3 · p. 4
- When queried, the non-oracle critic suggests an admissible action but may be wrong; unparseable suggestions fall back to the actor’s top action.In the main experiments, actor and critic share a backbone and differ in role prompts.Source: §3.3 · p. 4
3.4 Online Self-Improvement via Bootstrapped Supervision
- SAG collects context–action pairs from successful episodes and periodically updates only the actor with action-level SFT, while keeping the critic fixed.The executed action may be actor-selected or critic-suggested; updates are made after accumulated successful episodes.Source: §3.4 · p. 5
4 Theoretical Analysis
The analysis frames critique as a Value of Information decision and motivates actor-side ambiguity as a lightweight proxy for its expected benefit. It links higher decision-error risk with greater potential value from critique.
4.1 Critic as a VoI Decision
- The binary critic-invocation rule is Bayes-optimal when it queries exactly when expected step-level improvement exceeds critic cost.The paper notes that exact VoI is intractable in practice, motivating lightweight actor-derived proxies.Source: §4.1 · p. 5
4.2 Ambiguity as a Proxy for VoI
- Expected critique gain is approximated as correction reliability times average gain times the actor’s immediate error probability, so high-risk steps have greater VoI.The VoI threshold corresponds to an error-risk threshold scaled by critic cost, correction reliability, and average gain.Source: §4.2 · p. 5
- High entropy rules out a dominant action and raises an upper bound on greedy error risk, while a small top-two margin indicates greater local error risk under the stated top-two assumption.These broad and local ambiguity signals motivate normalized entropy and margin as computable proxies for decision risk.Source: §4.2 · p. 6
5 Experimental Setting
The evaluation covers three interactive benchmarks, multiple instruction-tuned backbones, and inference-time or lightweight-adaptation baselines. It reports success, episode length, token use, and normalized token efficiency.
Interactive decision-making benchmarks
- SAG is evaluated on ALFWorld, BabyAI-Text, and WebShop, covering grounded action under partial observability, compositional instruction following, and noisy open-domain search.The benchmarks together cover state tracking, multi-step reasoning, and cost-aware decision making.Source: §5 · p. 6
Backbone Models and Training
- The study uses Qwen2.5-7B-Instruct, Llama-3.1-8B-Instruct, and Mistral-7B-Instruct backbones, with actor–critic capacity pairings also analyzed.Online self-improvement collects successful context–action pairs and updates the actor after every 10 successful trajectories.Source: §5 · p. 6
Baselines and comparison methods; Evaluation protocol and metrics
- Comparisons include ReAct, deliberation methods, always-on critic methods, and a GPT-4.1 ReAct reference; Table 1 defines the reported success, horizon, token, and normalized-efficiency metrics.Evaluation uses standard test sets and pass@1 except Reflexion’s native pass@3 setting; Section 6 analyses and ablations use ALFWorld with Qwen2.5-7B-Instruct.Source: §5 · pp. 6–7, Table 1 · p. 7
6 Experimental Results
Across backbone–benchmark settings, SAG improves success over ReAct while keeping token use near ReAct on ALFWorld and WebShop and well below always-on critique on BabyAI-Text. Capacity, ablation, and learning-dynamics analyses further examine how selective critique and online self-improvement contribute to that trade-off.
6.1 Selective critique achieves strong success at near-ReAct cost
- Across backbone–benchmark settings, SAG improves success over ReAct by an average relative 91% while keeping token use near ReAct on ALFWorld and WebShop and far below always-on critique on BabyAI-Text.The performance–cost comparison uses bubble area for normalized token efficiency, with ReAct = 1.0.Source: §6.1 · p. 7, Figure 3 · p. 7
- SAG’s success advantage widens with episode difficulty, improving hard-episode success from 17.8% to 75.0%, compared with 43.4% to 85.1% on easy episodes.Difficulty is stratified by trajectory length of a GPT-4.1 ReAct agent; longer trajectories indicate higher difficulty.Source: Figure 4 · p. 7, §6.1 · p. 8
6.2 Why Gated Critique Works: Capacity Scaling and Ablations
- A 7B actor with a 3B critic reaches 76.9% success, close to the 77.2% of a 14B actor without critique; actor scaling provides the largest gains.Gated critique improves all actor sizes, with stronger gains for smaller actors that saturate as actor capacity rises.Source: §6.2 · p. 8, Figure 6 · p. 8
- On ALFWorld, removing either ambiguity signal lowers success from 78.3% to 77.6% without global entropy and 74.6% without local ambiguity, while removing the gate yields 62.0% success at 282k tokens.Disabling critic invocation lowers success to 33.0%.Source: §6.2 · pp. 8–9, Table 2 · p. 8
- With matched online updates, SAG reaches 78.3% success using 56k tokens, versus 30.2% for ReAct + online SFT and 74.2% for LAC + online SFT using 341k tokens.The comparison supports the authors’ claim that selective critique gains are not explained by online SFT alone.Source: §6.2 · p. 9, Table 3 · p. 9
6.3 Learning Dynamics of Self-Improving Agents
- Across early, middle, and late phases, SAG success rises from 71.0% to 83.0% as critic calls fall from 2.85 to 1.10; successful-episode ambiguity decreases while failure ambiguity remains higher.The reported success-rate sequence is 71.0% → 75.0% → 83.0%, and the critic-call sequence is 2.85 → 2.18 → 1.10.Source: §6.3 · p. 9
7 Conclusion
The paper concludes that SAG selectively invokes critique through a lightweight, training-free gate based on action-level ambiguity, achieving a favorable performance–cost trade-off across long-horizon benchmarks and backbone models.
7 Conclusion
- Across multiple long-horizon benchmarks and backbone models, SAG achieves a superior performance–cost trade-off to both no-critique and always-on critique agents.The conclusion presents selective critique as a practical and scalable pathway for improving reliability and efficiency in complex sequential environments.Source: §7 · p. 9
A Broader Impacts and Limitations
The paper presents SAG as a lightweight approach relevant to reliability and efficiency in interactive-agent settings, while identifying open questions about its uncertainty signals, evaluation scope, and critic architecture.
A Broader Impacts and Limitations
- SAG is described as lightweight, training-free, and compatible with existing agent frameworks, with potential to reduce unnecessary token use and latency while preserving reliability.The paper frames responsible deployment and application-level safeguards as important to beneficial outcomes.Source: A Broader Impacts and Limitations · p. 16
- The study uses representative long-horizon interactive benchmarks; evaluation in additional real-world agent settings remains an open direction.The authors also note that alternative uncertainty or value-estimation signals and adaptive or learned critics merit exploration.Source: A Broader Impacts and Limitations · p. 16
B Notation Table
- The notation table defines the gating score as combining global and local ambiguity, with a threshold controlling overall critic use and a margin threshold detecting near-boundary decisions.It also names normalized entropy as global ambiguity and the top-1/top-2 log-probability margin as local ambiguity.Source: B Notation Table · p. 16
C Proof of Lemma 4.1
The proof frames critic invocation as a one-step choice at the actor’s decision state, comparing expected improvement against computational cost.
C Proof of Lemma 4.1
- At decision state z_t = (x_t, r_t), the agent chooses whether to invoke the critic, with invocation incurring cost c > 0 and improvement Δ_t.Without invocation, the defined improvement and additional cost are both zero.Source: C Proof of Lemma 4.1 · p. 17
- The analysis treats critique allocation as maximizing conditional expected net utility given the current decision state.The Bayes-optimal decision compares the expected net utility of invocation with the zero utility of not invoking.Source: C Proof of Lemma 4.1 · p. 17
- Invoking the critic is optimal when its expected step-level improvement exceeds its computational cost.The stated rule is to invoke iff E[Δ_t | z_t] > c.Source: C Proof of Lemma 4.1 · p. 17
D Proof of Proposition 4.2
The proof interprets the actor’s action distribution over admissible actions as a belief about correctness, then relates greedy-action error to the distribution’s maximum probability and entropy.
D Proof of Proposition 4.2
- Under the belief interpretation, the greedy action’s error probability equals 1 − qmax, the probability mass assigned to all other admissible actions.Here qmax is the actor’s probability for its top-ranked action.Source: D Proof of Proposition 4.2 · p. 17
- The proof combines the greedy-error identity with an entropy bound and normalized entropy to establish the stated relation.The passages describe the entropy argument but do not include the final displayed relation.Source: D Proof of Proposition 4.2 · p. 17
E Proof of Proposition 4.3
This block presents a top-two-action error argument, benchmark and protocol details, implementation context, and descriptions of comparison methods.
E Proof of Proposition 4.3
- Conditioned on the correct action being among the top two, the proof expresses greedy-choice error as the conditional probability that the second-ranked action is correct.It defines the top-two log-probability margin as log(q1/q2), then uses it to rewrite the conditional error bound.Source: E Proof of Proposition 4.3 · p. 18
G.1 Benchmarks for Interactive Environments
- ALFWorld tests long sequences of grounded household actions on unseen layouts, where partial observability and early mistakes can compound.BabyAI-Text evaluates compositional generalization on held-out instructions; WebShop tests constrained shopping with noisy pages and distractors.Source: §G.1 · pp. 20–21
G.2 Online Self-Improvement Protocol
- Successful episodes contribute executed context–action pairs to D, and every K successes trigger actor-only SFT while the critic remains fixed.Episodes are evaluated once; updated actors are used only in later episodes, and the training target is the executed action rather than the reasoning trace.Source: Figure 9 · p. 21, §G.2 · p. 21
G.3 Hyperparameters
- Experiments used one NVIDIA RTX PRO 6000 Blackwell GPU with 96GB VRAM.The detailed simulation hyperparameters and training configurations are referenced in Table 7.Source: §G.3 · p. 21, Table 7 · p. 22
G.4 Detailed description of baselines
- The comparison set includes no-critique ReAct, deliberation and trajectory-reuse methods, and always-on critique systems alongside SAG’s gated critique.These baselines differ in whether they use fixed critique, multi-pass deliberation, confidence-based aggregation, or trajectory reuse.Source: §G.4 · pp. 21–22
G.5 Scope Relative to RL-based Agent Post-training
SAG targets deployment-time critique allocation rather than replacing RL post-training, and the supplied experiments report gains over no-critique agents with lower costs than always-on critique. The supplementary analyses examine critic capacity, matched online-SFT controls, episode ordering, and gate thresholds.
G.5 Scope Relative to RL-based Agent Post-training
- SAG is a deployment-time method for deciding when an available actor should query an imperfect critic, complementing rather than replacing RL-based post-training.A like-for-like cost comparison must account for rollout and training budgets as well as inference tokens, because SAG measures interaction-time cost.Source: §G.5 · pp. 22–23
H.1 Extended Model Scaling with Always-on Critique
- Across benchmarks and model sizes, SAG improves over no-critic agents and usually matches or exceeds always-on critique with fewer critic calls and lower token cost.The reported trend holds across model sizes, including the extended scaling analysis.Source: §H.1 · pp. 23–24, Table 9 · p. 24
H.2 Effect of Critic Capacity
- With a fixed 7B actor on ALFWorld, a stronger critic further improves success, while a 3B critic still provides a large gain over the no-critic baseline.The results suggest SAG does not require an oracle or a substantially stronger critic.Source: §H.2 · p. 24, Table 10 · p. 24
H.3 Matched Online-SFT Controls
- SAG achieves the best success on all three benchmarks with token budgets close to or below ReAct + online SFT and far below LAC + online SFT.The matched controls indicate that online self-improvement alone does not explain SAG’s gains; always-on LAC + online SFT uses 341k, 438k, and 84k tokens on ALFWorld, BabyAI-Text, and WebShop, respectively.Source: §H.3 · pp. 24–25, Table 11 · p. 25
H.4 Robustness to Trajectory Ordering
- Success rate and token usage remain stable across episode-order settings, with the qualitative conclusion unchanged.The analysis varies the order of ALFWorld episodes because successful-trajectory accumulation can affect when online updates occur.Source: §H.4 · p. 25, Table 12 · p. 25
H.5 Gate Threshold Sensitivity
- The entropy threshold τ primarily controls the cost–success trade-off, while the margin threshold δ has a milder effect on success across a broad range.Performance degrades mainly when τ is too high; nonzero δ values yield similar success.Source: §H.5 · p. 25, Table 13 · p. 25
H.6 Simulation results on BabyAI-Text
The supplementary material reports experiments and analyses of SAG on BabyAI-Text and WebShop, alongside disclosures on reproducibility, ethics, societal impacts, and research assets.
H.6 Simulation results on BabyAI-Text
- On BabyAI-Text, success rose from 68.0% to 72.3% as critic calls fell from 3.20 to 2.23 per episode during online learning.Successful episodes’ ambiguity decreased from 1.36 to 0.65, while failure ambiguity rose from 1.53 to 1.88; previously seen episode performance improved from 68.0% to 71.3%. For threshold sensitivity, increasing τ from 0.30 to 0.50 reduced success from 70.9% to 66.2% and token use from 83k to 71k; δ kept success within 69.5%–71.3% while increasing tokens from 68k to 82k.Source: Figure 11 · p. 26, §H.6 · p. 26, Figure 10 · p. 26
H.7 Simulation results on WebShop
- On WebShop, success rose from 34.7% to 40.5% as critic calls fell from 2.7 to 1.9 per episode during online learning.Successful-trajectory ambiguity decreased from 1.45 to 0.75, while failures remained more ambiguous; performance on seen episodes increased from 36.8% to 38.2%. Increasing τ reduced token use from 12k to 8k as success fell from 37.2% to 33.0%; across δ values, success remained 36.9%–37.2%.Source: §H.7 · pp. 26–27, Figure 13 · p. 27, Figure 12 · p. 27
H.8 Online SFT vs. One-shot SFT
- Online-SFT improves success with comparable or lower token usage than one-shot SFT by distilling critic-corrected behaviors earlier, enabling later rollouts to benefit.One-shot SFT first collects successful trajectories and then performs a single actor update, missing online-SFT’s compounding benefit.Source: §H.8 · p. 27
H.9 Failure Modes and Non-oracle Critic Behavior
- SAG’s selective critique remains useful despite non-oracle behavior, but critics can suggest suboptimal actions, gates can miss confidently wrong actions, and early errors may be unrecoverable.The paper suggests combining step-level gating with trajectory-level monitoring to address unrecoverable early mistakes.Source: §H.9 · p. 28
H.10 Sensitivity to Online Update Frequency
- SAG is robust across a moderate range of online update frequencies, with K = 10 selected as a balance among success, critic usage, and token cost.The comparison varies how many successful episodes are collected before each actor update.Source: §H.10 · p. 28, Table 15 · p. 28
H.11 Qualitative Analysis of Prompt-Induced Responses
- The full critic prompt elicits rationales reflecting broader task structure, whereas ablated prompts shift toward local cues or immediate re-examination.The actor and critic can attend to different aspects of the task despite sharing the same underlying models, due to prompt framing and objectives.Source: §H.11 · pp. 28–29, Table 16 · p. 28
H.12 Action-Only versus Reasoning-Consistent Supervision
- Action-only SFT achieves higher success and fewer critic calls than reasoning-consistent SFT in both ID and OOD evaluations.The comparison follows online adaptation on 134 ALFWorld episodes and evaluates on 140 episode-disjoint held-out examples.Source: §H.12 · p. 29, Table 17 · p. 29
H.13 Empirical Validation of the Gating Score
- Reference-action disagreement rose monotonically from 17.8% to 45.5% across gating-score quartiles, supporting the score as a practical ambiguity indicator, not a ground-truth error rate.The reference was BabyAI’s replanning bot, used only for this diagnostic; the disagreement result does not extend the conditional guarantee of the margin proposition.Source: §H.13 · p. 29, Table 18 · p. 29
NeurIPS Paper Checklist
- The paper reports that computational resources are detailed in Appendix G.3 and that the research conforms to the NeurIPS Code of Ethics.The checklist answers Yes to both questions.Source: NeurIPS Paper Checklist · p. 39
- The paper answers Yes that it discusses positive and negative societal impacts, with broader impacts reported in Appendix A.The checklist also marks safeguards for high-risk releases as not applicable.Source: NeurIPS Paper Checklist · pp. 39–40
- The experiments use open-source, widely utilized datasets and models, and the paper says new implementation assets include documentation and reproduction instructions.The checklist answers Yes on asset attribution and documentation.Source: NeurIPS Paper Checklist · pp. 40–41
- The paper marks crowdsourcing and human-subjects review as not applicable and says LLMs were used only for writing assistance, disclosed in Appendix J.The LLM-use item is marked not applicable to the core methodology.Source: NeurIPS Paper Checklist · pp. 41–42