TL;DR
When LLM agents fail during complex, multi-turn tool use, trajectory-level rewards cannot pinpoint which specific turn caused the failure. Critical-State RL introduces a training-free diagnostic that uses nested sampling to isolate action-dependent reward variance from downstream noise, identifying the exact model call that will benefit from training. By optimizing only these diagnosed "critical states" via localized contextual-bandit training, the method significantly boosts agent performance while avoiding the degradation caused by training the wrong turns.
What Problem Does This Paper Address?
In multi-turn interactions—such as an LLM agent calling multiple tools to solve a user request—errors often hinge on a single bad decision. However, standard Reinforcement Learning (RL) struggles with credit assignment in these scenarios. If you only have a final trajectory-level reward (success or failure), how do you know which turn to blame or train?
Simply looking at reward variation across rollouts isn't enough. If an agent makes a decision at turn 2, the final outcome still depends on random variations or choices made in turns 3, 4, and 5 (continuation noise). As a result, a good action might end in failure, or a bad action might be bailed out later. Standard RL methods either update every turn indiscriminately (adding massive noise) or rely on rigid heuristics that target the wrong states, which can stall or even degrade model performance.
Methods
The authors propose a two-step framework: Diagnose where to train, then Optimize locally.
-
The Critical-State Diagnostic (Training-Free): Before updating any weights, the framework evaluates candidate turns based on three criteria: action-sufficiency (the local reward aligns with final task success), headroom (the current policy has room to improve), and trainability. To measure trainability, they use nested within-prefix sampling:
-
Fix the history (prefix) up to the candidate turn.
- Sample multiple alternative actions at this turn.
- For each action, resample multiple downstream continuations.
By applying the law of total variance, this nested sampling mathematically separates the variance caused by the current action from the downstream continuation noise. Turns with high action-dependent variance are selected as "critical states."
- Occurrence-Local RL: Once a critical turn is selected, the policy is optimized only at that specific call using contextual-bandit training. Gradients are applied strictly to the tokens generated during this turn, while the surrounding turns merely act as frozen context or reward providers.
Datasets
The method was evaluated across several models and multi-turn configurations:
- Berkeley Function Calling Leaderboard (BFCL) v4 (
multi_turnsuite): Testing specific failure modes includingmiss_func(withholding a required tool until later turns) andmiss_param(withholding a required argument). - Logged Interaction Traces: Real-world interaction logs from
Nemotron-Super-120Bevaluated for repeat-call avoidance. - Memory Management Tasks: Evaluated on
xLAMandGemmamodels using the BFCL v4 agentic/memory sub-tasks (Key-value store, Vector store, and Recursive summary).
Key Insights and Ideas
- Variance $\neq$ Trainability: High reward variance at a specific turn does not mean that turn is trainable. The variance could be entirely driven by downstream randomness.
- Critical States are Model- and Task-Dependent: There is no universal "correct turn" to train. For instance, on the missing-function task (
miss_func), the diagnostic determined thatGemmaneeded training on its recovery turn (after the tool becomes available), whereasNemotronbenefited from training on its decision turn (before tool availability). - Training the Wrong Turn Destroys Performance: Blindly applying local RL to non-critical turns can actively harm the model. For example, training Gemma on the decision turn for
miss_funccaused a 4.5 percentage point drop in accuracy because it forced the model to over-bias toward firing tools prematurely.
Key Results
The authors conducted a controlled four-cell study using Gemma-4-26B-A4B to validate their diagnostic choices against alternative turns:
- Missing-Function (
miss_func): Training the diagnostic-selected recovery turn improved BFCL accuracy from 14% to 28.3% (+14.3 pp), while training the alternative decision turn degraded performance. - Missing-Argument (
miss_param): Training the selected decision turn improved accuracy from 43.5% to 47.3% (+3.8 pp), while the alternative turn left performance flat. - Comparison to Baselines: Critical-State RL outperformed standard multi-turn RL using Monte-Carlo Return-to-Go (RTG), which only achieved 45% accuracy on
miss_param.
- Memory Management: On the xLAM memory sub-task, the agent's mean score jumped from 34.54% to 50.54%. On Gemma, it rose from 38.1% to 52.7%.
Limitations and Future Work
- Heuristic Candidate Phases: The framework still requires humans or task structures to define the initial "candidate phases" and local reward functions before the diagnostic can rank them.
- Simplified Recurrence ($K=1$): The experimental validation focused primarily on settings where the critical state occurs once per episode ($K=1$). Extending this to highly recurrent states within a single trajectory remains an open area for deeper empirical exploration.
- Threshold Calibration: The study evaluated categorical turn selection (choosing turn A over turn B) rather than establishing absolute, calibrated variance thresholds for when to trigger training across arbitrary tasks.
Summary updated