Recursive Semantic Divergence for LLM Agent Consistency

AI summary

Overview

Research area: Natural Language Processing / LLM agent evaluation and training (agent reliability, behavioral consistency, reinforcement learning for LLM fine-tuning).

Technical level: Intermediate. The core idea is intuitive, but the method borrows formally from reinforcement learning (bisimulation metrics, temporal-difference learning) and requires familiarity with NLI-based semantic comparison.

Scope: The paper introduces Recursive Semantic Divergence (RSD), an unsupervised trajectory-level metric that measures how much an LLM agent's behavior diverges across independent runs from the same interaction history, and shows it can also be used as a reward signal to make agents more consistent.

What This Paper Is About

LLM agents that call tools and act over multiple turns behave inconsistently: given the exact same starting state, independent runs may call different tools, contradict themselves, or pursue different strategies — and these differences compound over a trajectory. Existing evaluation metrics mostly measure task correctness (completion scores, pass^k), not consistency of behavior across executions, and existing uncertainty measures work at the token level or single-response level, missing how inconsistency propagates into future turns. The paper's goal is to define a trajectory-level consistency metric that can be measured at any turn and also used to train agents to be more consistent.

Key Contributions

1. A new metric — Recursive Semantic Divergence (RSD): an unsupervised, trajectory-level consistency metric that adapts bisimulation metrics from reinforcement learning to LLM agents, replacing reward differences with a Natural Language Inference (NLI) based semantic distance between agent actions, and defining a recursive fixed-point objective over future states.
2. A practical learned approximation: RSD is estimated with a neural network trained via the Matching under Independent Coupling (MICo) method and n-step temporal-difference learning on independent rollouts, so a consistency score can be produced at each turn with a single forward pass, without waiting for the full trajectory to complete.
3. Empirical demonstration as a training signal: using the learned RSD self-distance as a reward for GRPO fine-tuning reduces behavioral variation across two benchmarks and two model scales, while in most cases also improving task performance.
4. Theoretical analysis: the RSD fixed-point is shown to be a unique well-defined quantity (the Bellman operator is a γ-contraction, with the fixed point in [0, 1/(1−γ)]), plus bounds on the probability of total trajectory disagreement (Theorem 1) and on the existence of a dominant action class when RSD is low (Theorem 2).

Main Findings

• Large variance reductions on smaller models: On τ²-bench with Qwen 2.5 3B, RSD reduces AUC coefficient of variation (CV) by 30.9% and progress CV by 26.1% relative to the base model. On ToolSandbox 3B, it reduces AUC CV by 50.5% and progress CV by 49.3%. The abstract summarizes this as reducing variation in task progress from 132% to 91% on τ²-bench and from 90% to 44% on ToolSandbox.
• Smaller models are more stochastic: 7B models show lower baseline variance (e.g., 0.38 CV for ToolSandbox 7B versus 0.90 for 3B), so the absolute gains from RSD are smaller there — less variance to eliminate.
• Token and semantic entropy are unreliable consistency rewards: Token entropy increased CV in multiple cases, including +32.4% AUC CV and +40.5% progress CV on ToolSandbox 7B. Semantic entropy produced mixed results: −15.9% on τ²-bench 3B but +0.5% on 7B, and only modest ToolSandbox reductions (−7.0% on 3B, −6.0% on 7B). The authors attribute this to both methods operating myopically at individual turns, so an agent can be locally consistent but globally inconsistent.
• SFT is not a reliable consistency method: Supervised fine-tuning reduced CV on τ²-bench (−28.0% for 3B, −6.5% for 7B) but increased CV on ToolSandbox (+17.9% for 7B). Direct RSD evaluation showed SFT changed inconsistency by only −1.1% on ToolSandbox, despite memorizing successful trajectories.
• RSD is not uniformly better at 7B on τ²-bench: In Table 1, RSD on τ²-bench 7B increased AUC CV by 14.2% and progress CV by 15.1%; direct RSD evaluation showed +0.2% (0.873 to 0.875), while SFT achieved the largest reduction there (−8.3%, to 0.800). The authors note τ²-bench baseline RSD is substantially higher (0.873) because small early differences cascade in multi-turn airline service tasks.
• Direct metric validation: Measuring RSD directly on fine-tuned model outputs with gpt-4.1-based pairwise NLI over 8 independent runs per sample, RSD fine-tuning reduced inter-run inconsistency on ToolSandbox 7B by 52.8% (0.672 to 0.317) — the largest reduction among all methods. Token entropy achieved −40.5% and semantic entropy −34.4% there.
• Pure RSD beat hybrid rewards: In the ToolSandbox Qwen-2.5-7B ablation, RSD alone (λ=1.0) gave both the lowest CV (AUC CV 0.28) and the best AUC (0.555). Adding progress-delta reward degraded both consistency and performance monotonically (λ=0.8 → CV 0.36; λ=0.5 → CV 0.37; λ=0.2 → CV 0.42), which the authors suspect is because progress delta is a very sparse and noisy reward.
• Theoretical interpretation: The paper states that if U(s,s) = 0.1, the probability of contradiction is at most 10% and at least 80% of the policy's mass is concentrated on a single semantic action class (from Theorem 2, which applies when U(s,s) < 1/4).
• No collapse to "consistently failing" in these experiments: The authors explain that RSD was estimated from rollouts of a base agent that already makes non-trivial progress, and GRPO updates the policy locally within that region; degenerate always-fixed-response policies were not in the rollout distribution, so they were not explicitly assigned low RSD.

Methodology in Plain English

The researchers model an LLM agent as a decision process where the agent never sees the true environment state and instead conditions on the full interaction history — the sequence of observations, actions, and tool outputs so far. Two independent runs from the same history can produce semantically different actions.

Their core borrowing is the idea of bisimulation from reinforcement learning: two states are "behaviorally equivalent" if they yield the same immediate reward and lead to states that are themselves equivalent. This gives a recursive, discounted equation. Since there are no ground-truth labels or human rewards for agent trajectories, they swap the reward difference for an NLI-based distance between the two agents' actions: 0 if the two actions entail each other in both directions, 1 if they contradict, and 0.5 if they are neutral. This yields a recursive definition of divergence that accumulates discounted semantic disagreement over future turns.

Because the exact recursive quantity is intractable, they approximate it with a neural network following the MICo approach: states (interaction histories) are embedded with a pretrained text encoder, then mapped into a latent space where the distance combines a norm term and an angular term. The network is trained with n-step temporal-difference targets built from paired rollouts of the same task, minimizing the squared Bellman residual.

A key trick is the self-distance: comparing a state to itself removes the angular term and leaves twice the norm of the embedding, which is nonzero when the agent's policy is stochastic from that state. This self-distance is exactly the RSD score, and it estimates expected cumulative semantic disagreement between two independent rollouts. At inference it costs one forward pass — no extra rollouts or NLI calls needed.

Experiments use τ²-bench and ToolSandbox with Qwen-2.5 3B and 7B. They run 8 independent trials over 8 test samples (64 trajectories), generate training rollouts at temperature 1, and evaluate at temperature 0. They compare against the base model, token entropy, semantic entropy, and SFT, all applied via GRPO with each metric used as a reward (entropy methods minimized via negative entropy rewards; RSD minimized as −U(s,s)). Consistency is measured using the coefficient of variation (σ/μ) across trials, alongside AUC (area under the progress curve), final progress rate, pass@1, and pass^3.

Why This Matters

Impact on research: The paper reframes agent reliability as a trajectory-level property rather than a per-token or per-response one, and provides a formally grounded, label-free metric that can also serve as a training objective. It connects bisimulation metrics from RL with NLI-based semantic distance, and its theoretical bounds give the score an interpretable meaning (probability of disagreement, concentration of policy mass on a dominant action class).

Real-world applications:

• Enterprise workflow agents: business process automation where the same request must produce the same tool calls and outcomes across runs, as in the authors' SAP context.
• Healthcare and other critical systems: the paper explicitly motivates consistent behavior in repeated executions for critical applications such as healthcare systems.
• Customer-facing assistants: avoiding agents that give contradictory information to users across sessions.
• Long-horizon code generation agents: where small early errors compound into large deviations from the expected solution path.

Industry relevance: The metric needs no ground-truth labels, and inference is a single forward pass — attractive for deployment monitoring and for fine-tuning without curated expert demonstrations. The reported result that RSD training "matches supervised fine-tuning performance with substantially lower variance, without requiring ground-truth labels" is directly relevant to teams that lack labeled agent traces. The authors also note smaller models show the biggest consistency gains, which matters for cost-sensitive deployments.

Future Directions

• Domain transfer: RSD may require retraining or adaptation when moved to new domains or environments — how to make the learned metric transferable is open.
• Separating consistency from correctness: the metric cannot distinguish consistently failing behavior from consistently successful behavior; the authors suggest combining RSD with correctness-aligned rewards, and note that starting from a randomly initialized or very weak policy could expose failure modes such as collapsing to trivially consistent failure.
• Reducing dependence on the NLI model: RSD's reliability depends heavily on the accuracy and calibration of the underlying NLI model used to estimate semantic disagreement.
• Better auxiliary rewards: the hybrid ablation showed sparse progress-delta rewards hurt both consistency and performance (on ToolSandbox Qwen-2.5-7B), leaving open the question of how to design dense correctness signals that combine well with RSD.

Target Audience

Researchers and practitioners working on LLM agents, agent evaluation, and reinforcement-learning-based fine-tuning of language models. It is also relevant to engineers responsible for deploying agents in production, who need reliability monitoring beyond task-success rates, and to readers interested in applying bisimulation-style metrics to language-model behavior. Some background in RL notation (discount factors, Bellman operators) and NLI will help with the technical sections.

Authors’ abstract

Large Language Model (LLM) agents with tool use exhibit inconsistent behavior across independent runs from identical states, calling different tools, producing contradictory outputs, or pursuing divergent strategies. This variability compounds over time and undermines deployment reliability. Existing evaluation metrics primarily measure task correctness via completion-based scores and do not capture consistency in agent behavior across executions. Separately, agent behavior is analyzed either at the token level using probability distributions or at the single-response level using semantic clustering, but neither captures how inconsistency propagates across future turns of a trajectory. We introduce Recursive Semantic Divergence (RSD), an unsupervised trajectory-level consistency metric adapted from bisimulation metrics in reinforcement learning. RSD measures the expected cumulative semantic disagreement between two independent rollouts of the same agent from the same state, using natural language inference to detect logical inconsistency. It is defined recursively over future states and approximated by a neural network trained on independent rollouts. The learned metric estimates future divergence from the current state, providing a consistency score at each turn without requiring the full trajectory to complete. When used as a reward signal for fine-tuning, RSD reduces the variation in task progress from 132% to 91% on tau2-bench and from 90% to 44% on toolsandbox, while improving performance across benchmarks and model scales. Training with RSD as an additional reward signal matches supervised fine-tuning performance with substantially lower variance, without requiring ground-truth labels.