Recursive Semantic Divergence for LLM Agent Consistency

# Recursive Semantic Divergence for LLM Agent Consistency
Source: [https://arxiv.org/html/2610.33012](https://arxiv.org/html/2610.33012)
###### 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 thetoken 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 from132%132\\%to91%91\\%onτ2\\tau^\{2\}\-bench and from90%90\\%to44%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 labels111Source code is publicly available in the repository[https://github\.com/AgentConsistency/RSD\-agent\-consistency\.](https://github.com/AgentConsistency/RSD-agent-consistency)\.

## 1Introduction

With recent advances, Large language models \(LLMs\) agents can execute complex workflows and multi\-step tasks via tool calling functions\([Yao et al\., 2023](https://arxiv.org/html/2610.33012#bib.bib26);[Jang et al\., 2025](https://arxiv.org/html/2610.33012#bib.bib9);[Liu et al\., 2023](https://arxiv.org/html/2610.33012#bib.bib15)\)\. These agentic systems are increasingly deployed as autonomous agents that interact with users and tools over multiple turns\. For long\-horizon tasks such as code generation agents\([Shinn et al\., 2023](https://arxiv.org/html/2610.33012#bib.bib19);[Yang et al\., 2024](https://arxiv.org/html/2610.33012#bib.bib25)\), as well as agents built for critical applications such as healthcare systems\([Tu et al\., 2025](https://arxiv.org/html/2610.33012#bib.bib21);[Kim et al\., 2024](https://arxiv.org/html/2610.33012#bib.bib11)\), both correctness and reliability are important but manifest in different ways\. In long\- horizon tasks, like code generation, small errors in the beginning can accumulate over time, leading to compounding errors that deviate significantly from the expected solution trajectory\. In critical applications such as healthcare systems, reliability is further challenged by the need for consistent agent behavior in repeated executions\. However, in reality, we observe that given the same task to solve, the agent may still yield different decision paths across executions, such as calling entirely different tools, provide contradictory information to users, or follow divergent strategies that lead to different outcomes\.

While LLM decoding strategies such as setting the temperature to zero, or using greedy decoding reduce stochasticity at the token level, they do not necessarily ensure consistency at the agent\-level\. For a multi\-step or multi\-turn LLM agent, the behavior is determined by sequences of decisions conditioned on evolving trajectories, where small differences in the trajectories due to stochastic tool output responses or environmental feedback can lead to divergent agent trajectories even under deterministic decoding strategies\. Additionally, even when the underlying LLM is the same, the decoding strategy is deterministic, and the agent interaction history is fixed, there are additional sources of non\-determinism such as floating\-point precision and hardware\-level variability which can lead to inconsistent agent behavior\.

This highlights that the agent behaviour, which is trajectory\-dependent, may vary across executions under identical initial conditions\. Existing evaluation metrics\([Chang et al\., 2024](https://arxiv.org/html/2610.33012#bib.bib4);[Yao et al\., 2024](https://arxiv.org/html/2610.33012#bib.bib27);[Lu et al\., 2024](https://arxiv.org/html/2610.33012#bib.bib16)\)focus primarily on reporting task correctness using full or partial task completion metrics, often do not capture consistency in the agent performance\. Thep​a​s​spass^kkmetric\([Yao et al\., 2024](https://arxiv.org/html/2610.33012#bib.bib27);[Barres et al\., 2025](https://arxiv.org/html/2610.33012#bib.bib1)\), which measures the chance that allkki\.i\.d\. task trials are successful, is the closest existing metric to capturing agent consistency, but it remains binary and is used for reporting rather than enforcing consistency in the agent behavior\. Another line of work considers either token\-level distributions\([Malinin and Gales, 2020](https://arxiv.org/html/2610.33012#bib.bib17)\)or single\-response semantic similarity\([Kuhn et al\., 2023](https://arxiv.org/html/2610.33012#bib.bib13)\), but these approaches do not capture how inconsistencies propagate across future turns in a trajectory\. Notably, agent consistency is independent of correctness, as agents may exhibit stable behavior patterns that are either consistently successful or consistently failing across executions\.

Motivated by the need for a reliable and consistent agent behavior in long\-horizon tasks and critical applications, and the trajectory\-dependent variability of LLM agents that is not captured by existing evaluation metrics, we propose a trajectory\-level consistency metric to enforce agent consistency conditioned on identical interaction\-history states\. We introduce Recursive Semantic Divergence \(RSD\), an unsupervised trajectory\-level consistency metric adapted from bisimulation metrics\([Ferns et al\., 2004](https://arxiv.org/html/2610.33012#bib.bib7)\)in reinforcement learning, which define state similarity in terms of behavioral equivalence\. We extend this framework to interaction\-history states and replace reward differences with a semantic discrepancy based on Natural Language Inference \(NLI\)\([Bowman et al\., 2015](https://arxiv.org/html/2610.33012#bib.bib2)\), adapted to LLM agent’s actions\. We then define a recursive bisimulation\-style objective over this semantic distance, yielding a fixed\-point formulation of behavioral consistency, which is approximated using the Matching under Independent Coupling \(MICo\) method\([Castro et al\., 2021](https://arxiv.org/html/2610.33012#bib.bib3)\)\. We show that training with RSD metric as a reward signal improves agent consistency\.

![Refer to caption](https://arxiv.org/html/2610.33012v1/concept_diagram_final.png)Figure 1:Diagram illustrating Recursive Semantic Divergence \(RSD\) in LLM agents\. The first three panels display trajectory spreads for perfectly consistent, mostly consistent, and highly inconsistent agents over time\. The final panel maps an agent’s expanding and converging semantic action space alongside its corresponding RSD score, demonstrating how the metric tracks the variance of semantic divergence at each turn\.We summarize our contribution as follows:

1. 1\.We introduce Recursive Semantic Divergence \(RSD\), an unsupervised trajectory\-level consistency metric that adapts bisimulation from reinforcement learning to evaluate LLM agents\.
2. 2\.We empirically demonstrate that using the learned RSD metric as a reward signal for fine\-tuning significantly reduces behavioral variation and improves consistency across benchmarks and model scales\.
3. 3\.We provide a theoretical analysis showing that the RSD fixed\-point formulation converges and yields meaningful guarantees about agent behavior\. In particular, we derive bounds on the probability of total trajectory disagreement and prove the existence of a dominant action class when the agent exhibits low RSD\.

## 2Related Work

Agent evaluation\.Existing agent evaluation methods primarily focus on task correctness or completion rates\.[Wang et al\. \(2023\)](https://arxiv.org/html/2610.33012#bib.bib22);[Xie et al\. \(2024\)](https://arxiv.org/html/2610.33012#bib.bib24)evaluate coarse\-grained agent performance using success\-based metrics, while[Chang et al\. \(2024\)](https://arxiv.org/html/2610.33012#bib.bib4);[Chong et al\. \(2026\)](https://arxiv.org/html/2610.33012#bib.bib5)report fine\-grained metrics that capture intermediate progress and turn\-level efficiency\. Representing the tool call dependencies of an agent with a directed acyclic graph \(DAG\)\([Lu et al\., 2024](https://arxiv.org/html/2610.33012#bib.bib16)\), is also used to evaluate agent performance but it does not assess agent consistency across multiple executions\. Although some prior works partially account for agent stochasticity when reporting final performance metrics, they do not explicitly measure consistency in agent behavior or propose methods to enforce consistent execution of agent trajectories\. For instance,[Yao et al\. \(2024\)](https://arxiv.org/html/2610.33012#bib.bib27);[Barres et al\. \(2025\)](https://arxiv.org/html/2610.33012#bib.bib1), measure agent reliability with thep​a​s​spass^kkmetric which quantifies the chance that allkki\.i\.d\. task trials are successful out of thenntotal trials, but the metric remains limited for binary task outcomes only and not for evaluating the consistency of intermediate progress\. Similarly,[Chong et al\. \(2026\)](https://arxiv.org/html/2610.33012#bib.bib5), analyse the agent consistency across the different executions by visualising expected agent progress and variance in a plot, but does not provide method to improve agent consistency, which is the primary goal of our work\.

Uncertainty estimation\.Quantifying uncertainty in LLM outputs has been approached from multiple angles\.[Malinin and Gales \(2020\)](https://arxiv.org/html/2610.33012#bib.bib17)measure token\-level entropy, but such methods require access to model logits or weights and fail to account for the semantic content of the output\.[Kuhn et al\. \(2023\)](https://arxiv.org/html/2610.33012#bib.bib13)introduced semantic entropy, in which sampled responses are semantically clustered before entropy is computed\. While this addresses the limitations of token\-level measures, it operates at the level of single\-query responses and does not capture how disagreement at one turn propagates across a multi\-turn trajectory\.

For multi\-step agents specifically,[Kirchhof et al\. \(2025\)](https://arxiv.org/html/2610.33012#bib.bib12)argue that uncertainty quantification methods require fundamental reassessment due to underspecification and environmental effects introduced during agent interaction\.[Duan et al\. \(2025\)](https://arxiv.org/html/2610.33012#bib.bib6)propose an information\-theoretic framework that decomposes uncertainty propagation across agent steps into intrinsic and extrinsic components\. However, their approach is primarily diagnostic, requires the agent to complete the full trajectory before analysis, and does not produce a single scalar score that can be directly used as a reward signal\. In contrast, RSD is a lookahead, unsupervised metric that captures how semantic inconsistency propagates across future agent turns\.

## 3Preliminaries

### 3\.1Bisimulation Metrics

Bisimulation metrics\([Larsen and Skou, 1991](https://arxiv.org/html/2610.33012#bib.bib14);[Ferns et al\., 2004](https://arxiv.org/html/2610.33012#bib.bib7)\)were introduced in reinforcement learning to measure the behavioral distance between MDP states\. Two states are bisimilar if and only if they receive the same immediate reward and they transition to states that are themselves bisimilar\. This recursive definition yields a fixed\-point equation\. Following[Ferns et al\. \(2004\)](https://arxiv.org/html/2610.33012#bib.bib7), for an MDP with rewardRR, transition kernelPP, and discount factorγ\\gamma, the bisimulation distanced∗d^\{\*\}is the unique fixed point of the operator𝒯\\mathcal\{T\}acting on the space of all state\-pair distance functions𝒟\\mathcal\{D\}\. We define𝒯:𝒟→𝒟\\mathcal\{T\}:\\mathcal\{D\}\\to\\mathcal\{D\},d↦𝒯​dd\\mapsto\\mathcal\{T\}d, with pointwise form

\(𝒯d\)\(s\(i\),s\(j\)\)=\|R\(s\(i\)\)−R\(s\(j\)\)\|\+γ⋅W\(d\)\(P\(⋅∣s\(i\),π\),P\(⋅∣s\(j\),π\)\),\(\\mathcal\{T\}d\)\(s^\{\(i\)\},s^\{\(j\)\}\)=\|R\(s^\{\(i\)\}\)\-R\(s^\{\(j\)\}\)\|\+\\gamma\\cdot W\(d\)\\big\(P\(\\cdot\\mid s^\{\(i\)\},\\pi\),\\;P\(\\cdot\\mid s^\{\(j\)\},\\pi\)\\big\),\(1\)and the bisimulation distance is given by the fixed pointd∗=𝒯​d∗d^\{\*\}=\\mathcal\{T\}d^\{\*\}, whereW​\(d\)​\(⋅,⋅\)W\(d\)\(\\cdot,\\cdot\)denotes the Kantorovich distance between the two successor\-state distributionsP\(⋅∣s\(i\),π\)P\(\\cdot\\mid s^\{\(i\)\},\\pi\)andP\(⋅∣s\(j\),π\)P\(\\cdot\\mid s^\{\(j\)\},\\pi\), under the common policyπ\\pi, using the ground metricdd\. States that are close underd∗d^\{\*\}produce similar reward sequences and similar future trajectories, regardless of how different they appear in observation space\.

### 3\.2MICo: Sampling\-Based Bisimulation

Computing the exact fixed point of[Equation1](https://arxiv.org/html/2610.33012#S3.E1)requires evaluating theKantorovich distance over successor state distributions, which is intractable when these distributions are accessible only via samples\.The Matching under Independent Coupling \(MICo\) method\([Castro et al\., 2021](https://arxiv.org/html/2610.33012#bib.bib3)\)addresses this by replacing the intractable computation with sample\-based coupling: rather than computingW\(d\)\(P\(⋅\|s\(i\),π\),P\(⋅\|s\(j\),π\)\)W\(d\)\(P\(\\cdot\|s^\{\(i\)\},\\pi\),P\(\\cdot\|s^\{\(j\)\},\\pi\)\)over the full distribution, it pairs individual successor samples\(s′\(i\),s′\(j\)\)\(s^\{\\prime\(i\)\},s^\{\\prime\(j\)\}\)drawn independently from their respective transition distributions\. The key insight from[Castro et al\. \(2021\)](https://arxiv.org/html/2610.33012#bib.bib3)is that training on independently coupled samples still converges to a distance function that reflects behavioral similarity\.

MICo parameterizes the distance through a learned embeddingϕθ:ℝd→ℝm\\phi\_\{\\theta\}:\\mathbb\{R\}^\{d\}\\to\\mathbb\{R\}^\{m\}that maps state representations to a latent space\. The distance between two states combines a norm component \(capturing individual state “spread”\) and an angular component \(capturing relative orientation\):

U^θ​\(s\(i\),s\(j\)\)=α⁡\(‖ϕθ​\(zs\(i\)\)‖2\+‖ϕθ​\(zs\(j\)\)‖2\)\+β⋅d∠​\(ϕθ​\(zs\(i\)\),ϕθ​\(zs\(j\)\)\),\\hat\{U\}\_\{\\theta\}\(s^\{\(i\)\},s^\{\(j\)\}\)=\\alpha\\big\(\\\|\\phi\_\{\\theta\}\(z^\{s^\{\(i\)\}\}\)\\\|^\{2\}\+\\\|\\phi\_\{\\theta\}\(z^\{s^\{\(j\)\}\}\)\\\|^\{2\}\\big\)\+\\beta\\cdot d\_\{\\angle\}\\big\(\\phi\_\{\\theta\}\(z^\{s^\{\(i\)\}\}\),\\;\\phi\_\{\\theta\}\(z^\{s^\{\(j\)\}\}\)\\big\),\(2\)wherezs∈ℝdz^\{s\}\{\\color\[rgb\]\{0,0,0\}\\in\\mathbb\{R\}^\{d\}\}is a pretrained text embedding of statess,d∠d\_\{\\angle\}is the angular distance \(normalized arccos of cosine similarity\), andα,β\>0\\alpha,\\beta\>0are fixed coefficients\.

## 4Methodology

### 4\.1Problem Formulation

We follow existing methods\([Yao et al\., 2023](https://arxiv.org/html/2610.33012#bib.bib26);[Yao et al\., 2024](https://arxiv.org/html/2610.33012#bib.bib27);[Huang et al\., 2025](https://arxiv.org/html/2610.33012#bib.bib8)\)of formulating the LLM agent environment as a Partially Observable Markov Decision Process \(POMDP\)\([Kaelbling et al\., 1998](https://arxiv.org/html/2610.33012#bib.bib10)\):

ℳ=⟨𝒮,𝒜,𝒪,T,R⟩,\\mathcal\{M\}=\\langle\\mathcal\{S\},\\mathcal\{A\},\\mathcal\{O\},T,R\\rangle,\(3\)where𝒮\\mathcal\{S\}is the set of true environment states such as database contents and user preferences,𝒜\\mathcal\{A\}is the agent’s action space which includes the agent responses and tool calls, and𝒪\\mathcal\{O\}is the observation space which includes all feedback the agent receives from the environment such as user utterance and tool output\. The transition functionT:𝒮×𝒜→𝒮T:\\mathcal\{S\}\\times\\mathcal\{A\}\\to\\mathcal\{S\}governs how the environment changes after the agent takes an action\. The reward functionR:𝒮×𝒜→ℝR:\\mathcal\{S\}\\times\\mathcal\{A\}\\to\\mathbb\{R\}defines the reward the agent receives for executing a particular action in that state\. This reward may be difficult to obtain without ground truth or human feedback\.

In a standard setting, LLM agents never observe states∈𝒮s\\in\\mathcal\{S\}directly, due to partial observability, context limitations, and potential access restrictions\. Instead, the agent conditions on the interaction history, which includes the complete sequence of observations receivedo0,o1,…∈𝒪o\_\{0\},o\_\{1\},\.\.\.\\in\\mathcal\{O\}and actions takena0,a1,…∈𝒜a\_\{0\},a\_\{1\},\.\.\.\\in\\mathcal\{A\}:

ht=\(o0,a0,o1,a1,…,ot−1,at−1,ot\)\.h\_\{t\}=\(o\_\{0\},a\_\{0\},o\_\{1\},a\_\{1\},\\ldots,o\_\{t\-1\},a\_\{t\-1\},o\_\{t\}\)\.\(4\)
We reduce this POMDP to an MDP over belief states\. For LLM agents the model’s policy is already a function of the conversation history\. Therefore, the historyhth\_\{t\}serves as the belief state, and we define the induced MDPℳ′=⟨ℋ,𝒜,T′⟩\\mathcal\{M\}^\{\\prime\}=\\langle\\mathcal\{H\},\\mathcal\{A\},\{\\color\[rgb\]\{0,0,0\}T^\{\\prime\}\}\\ranglewhereℋ\\mathcal\{H\}is the set of all reachable histories and the transitionsT′T^\{\\prime\}are deterministic concatenation of the observations:ht\+1=ht⊕at⊕ot\+1h\_\{t\+1\}=h\_\{t\}\\oplus a\_\{t\}\\oplus o\_\{t\+1\}\. We denote a state in this induced MDP asst≡hts\_\{t\}\\equiv h\_\{t\}\.

The underlying LLM induces a stochastic policyπ⁡\(a∣s\)\\pi\(a\\mid s\)over this MDP, which results in a distribution over future trajectoriesτ∼Π\(⋅∣s\)\\tau\\sim\\Pi\(\\cdot\\mid s\)\. This means that two independent samples from this distribution may produce semantically different sequences\. We refer to this semantic spread of sampled trajectories from the same state as inconsistency\. Lower spread indicates that the policy is more deterministic\.

### 4\.2Recursive Semantic Divergence

The bisimulation framework \([Section3\.1](https://arxiv.org/html/2610.33012#S3.SS1)\) supplies a recursive, discounted measure of behavioral similarity that captures how present differences propagate into the future\. This notion maps directly onto agent consistency: if two independent runs from the same state yield similar behavioral futures, the agent is consistent; if they yield divergent futures, it is not\.

In the absence of human feedback or ground truth labels for LLM agents, we replace the immediate reward difference in a standard MDP,\|R⁡\(s\(i\)\)−R⁡\(s\(j\)\)\|\|R\{\(s^\{\(i\)\}\)\}\-R\(s^\{\(j\)\}\)\|from[Equation1](https://arxiv.org/html/2610.33012#S3.E1)with a Natural Language Inference \(NLI\)\-based distance function\. We adopt NLI\([Bowman et al\., 2015](https://arxiv.org/html/2610.33012#bib.bib2);[Williams et al\., 2018](https://arxiv.org/html/2610.33012#bib.bib23)\), which classifies sentence pairs as entailment, contradiction, or neutral and use it as an unsupervised measure of semantic agreement between agent actions, where bidirectional entailment is interpreted as equivalence, contradiction as disagreement, and neutrality as partial overlap\. We define the following NLI distance function:

###### Definition 1\(NLI Distance Function\)\.

For agent actionsa\(i\),a\(j\)∈𝒜\{\\color\[rgb\]\{0,0,0\}a^\{\(i\)\},a^\{\(j\)\}\}\\in\\mathcal\{A\}:

dNLI​\(a\(i\),a\(j\)\)=\{0if bidirectional entailment\.1if contradiction in either direction\.0\.5otherwise \(neutral\)\.d\_\{\\text\{NLI\}\}\(\{\\color\[rgb\]\{0,0,0\}a^\{\(i\)\},a^\{\(j\)\}\}\)=\\begin\{cases\}0&\\text\{if bidirectional entailment\}\.\\\\ 1&\\text\{if contradiction in either direction\}\.\\\\ 0\.5&\\text\{otherwise \(neutral\)\.\}\\end\{cases\}\(5\)

This function is symmetric, identity\-preserving \(dNLI​\(a,a\)=0d\_\{\\text\{NLI\}\}\(a,a\)=0\), and bounded in\[0,1\]\[0,1\]\.Considering time\-aligned samples at timestepttandsubstitutingdNLId\_\{\\text\{NLI\}\}for theimmediate reward difference termin[Equation1](https://arxiv.org/html/2610.33012#S3.E1), we obtain the following recursive distance:

U\(st\(i\),st\(j\)\)=𝔼at\(i\)∼π\(⋅\|st\(i\)\),at\(j\)∼π\(⋅\|st\(j\)\)\[dNLI\(at\(i\),at\(j\)\)\]\+γ⋅𝔼\[U\(st\+1\(i\),st\+1\(j\)\)\],U\(\{\\color\[rgb\]\{0,0,0\}s\_\{t\}^\{\(i\)\},s\_\{t\}^\{\(j\)\}\}\)=\\mathbb\{E\}\_\{\{\\color\[rgb\]\{0,0,0\}a\_\{t\}^\{\(i\)\}\}\\sim\\pi\(\\cdot\|s\_\{t\}^\{\(i\)\}\),\\;\{\\color\[rgb\]\{0,0,0\}a\_\{t\}^\{\(j\)\}\}\\sim\\pi\(\\cdot\|s\_\{t\}^\{\(j\)\}\)\}\\big\[d\_\{\\text\{NLI\}\}\(\{\\color\[rgb\]\{0,0,0\}a\_\{t\}^\{\(i\)\},a\_\{t\}^\{\(j\)\}\}\)\\big\]\+\\gamma\\cdot\\mathbb\{E\}\\big\[U\(\{\\color\[rgb\]\{0,0,0\}s\_\{t\+1\}^\{\(i\)\},s\_\{t\+1\}^\{\(j\)\}\}\)\\big\],\(6\)wherest\+1\(i\)∼P\(⋅\|st\(i\),at\(i\)\)s\_\{t\+1\}^\{\(i\)\}\\sim P\(\\cdot\|s\_\{t\}^\{\(i\)\},a\_\{t\}^\{\(i\)\}\)andst\+1\(j\)∼P\(⋅\|st\(j\),at\(j\)\)s\_\{t\+1\}^\{\(j\)\}\\sim P\(\\cdot\|s\_\{t\}^\{\(j\)\},a\_\{t\}^\{\(j\)\}\)are successor states\.

### 4\.3Learned Approximation

Computing the exact fixed point of[Equation6](https://arxiv.org/html/2610.33012#S4.E6)is intractable for two reasons\. First, we treat the LLM as a black box and do not have access to the internal transition probabilitiesP⁡\(st\+1∣st,at\)P\(s\_\{t\+1\}\\mid s\_\{t\},a\_\{t\}\)\. Second, even with access, the state space \(all possibleinteractionhistories\) is computationally large\.

To address this, we approximate the fixed point of[Equation6](https://arxiv.org/html/2610.33012#S4.E6)using the MICo method \([Section3\.2](https://arxiv.org/html/2610.33012#S3.SS2)\) with temporal\-difference \(TD\) learning using the rollouts from the LLM agent\. Given paired trajectory rolloutsτ\(i\)\\tau^\{\(i\)\}andτ\(j\)\\tau^\{\(j\)\}from the same task, we use time\-aligned state\-action pairs samples\(st\(i\),at\(i\)\)\(s\_\{t\}^\{\(i\)\},a\_\{t\}^\{\(i\)\}\)and\(st\(j\),at\(j\)\)\(s\_\{t\}^\{\(j\)\},a\_\{t\}^\{\(j\)\}\)at timesteptt\. Thenn\-step TD targetyty\_\{t\}is constructed by unrolling both trajectories for the nextnnsteps:

yt=∑k=0n−1γk​dNLI​\(at\+k\(i\),at\+k\(j\)\)\+γn​U^θ¯​\(st\+n\(i\),st\+n\(j\)\),y\_\{t\}=\\sum\_\{k=0\}^\{n\-1\}\\gamma^\{k\}d\_\{\\text\{NLI\}\}\(a\_\{t\+k\}^\{\(i\)\},a^\{\(j\)\}\_\{t\+k\}\)\+\\gamma^\{n\}\\hat\{U\}\_\{\\bar\{\\theta\}\}\(s\_\{t\+n\}^\{\(i\)\},s^\{\(j\)\}\_\{t\+n\}\),\(7\)whereθ¯\\bar\{\\theta\}is a copy of the network parameters that is soft\-updated at each step withθ\\thetaandγ\\gammais the discount factor\. The target corresponds to annn\-step unrolling of the Bellman equation, where discrepancies are accumulated and exponentially discounted with the time step\. The network is trained by minimizing the following Bellman residual:

ℒ⁡\(θ\)=𝔼⁡\[\(U^θ​\(st\(i\),st\(j\)\)−yt\)2\]\.\\mathcal\{L\}\(\\theta\)=\\mathbb\{E\}\\left\[\\left\(\\hat\{U\}\_\{\\theta\}\(s^\{\(i\)\}\_\{t\},s^\{\(j\)\}\_\{t\}\)\-y\_\{t\}\\right\)^\{2\}\\right\]\.\(8\)

### 4\.4Self\-Distance as a Measure of Consistency

The MICo distance function from[Equation2](https://arxiv.org/html/2610.33012#S3.E2)produces what[Castro et al\. \(2021\)](https://arxiv.org/html/2610.33012#bib.bib3)term adiffusedistance—the self\-distanceU⁡\(s,s\)U\(s,s\)can be non\-zero\. We use this property to measure how stochastic the process is from a given state\. If the transition dynamics from statesshave many possible successor states, thenU⁡\(s,s\)\>0U\(s,s\)\>0\. For deterministic states,U⁡\(s,s\)=0U\(s,s\)=0\. Intuitively, it captures how wide the tree of possibilities is when unrolling the process from that state\.

For the self\-distanceU^θ​\(s,s\)\\hat\{U\}\_\{\\theta\}\(s,s\), the angular term vanishes \(a vector has zero angle with itself\), leaving:

U^θ​\(s,s\)=2​α​‖ϕθ​\(zs\)‖2\.\\hat\{U\}\_\{\\theta\}\(s,s\)=2\\alpha\\\|\\phi\_\{\\theta\}\(\{\\color\[rgb\]\{0,0,0\}z^\{s\}\}\)\\\|^\{2\}\.\(9\)
In our formulation, stochasticity arises from the LLM policyπ\(⋅∣s\)\\pi\(\\cdot\\mid s\), which may sample different actions across runs\. Since we use NLI to measure the reward difference, the self\-distanceU⁡\(s,s\)U\(s,s\)captures the expected cumulativesemanticdivergence between two independent trajectories originating from the same conversational state\. It is zero when the agent always produces semantically equivalent actions \(regardless of surface variation in phrasing\), and positive when the agent would contradict itself across runs\.

###### Definition 2\(Recursive Semantic Divergence\)\.

The Recursive Semantic Divergence at statessis defined asthe infinite\-horizon discounted sum of stepwise discrepancies obtained by expanding[Equation6](https://arxiv.org/html/2610.33012#S4.E6):

U\(s,s\)=𝔼τ,τ′∼Π\(⋅\|s\)\[∑t=0∞γt⋅dNLI\(at,at′\)\],U\(s,s\)=\\mathbb\{E\}\_\{\\tau,\\tau^\{\\prime\}\\sim\\Pi\(\\cdot\|s\)\}\\left\[\\sum\_\{t=0\}^\{\\infty\}\\gamma^\{t\}\\cdot d\_\{\\text\{NLI\}\}\(a\_\{t\},a^\{\\prime\}\_\{t\}\)\\right\],\(10\)whereτ\\tauandτ′\\tau^\{\\prime\}are independent trajectory rollouts from the distribution of trajectoriesΠ\(⋅\|s\)\\Pi\(\\cdot\|s\), approximated in practice byU^θ​\(s,s\)=2​α​‖ϕθ​\(zs\)‖2\\hat\{U\}\_\{\\theta\}\(s,s\)=2\\alpha\\\|\\phi\_\{\\theta\}\(z\_\{s\}\)\\\|^\{2\}\.

RSD provides a notion of how consistent an LLM agent is\. Consider a statessfrom which the agent’s policyπ\(⋅\|s\)\\pi\(\\cdot\|s\)places all probability mass on a single semantic equivalence class of actions \(e\.g\., it always calls the same tool with the same arguments, possibly with different phrasings\)\. In this case,dNLI​\(a,a′\)=0d\_\{\\text\{NLI\}\}\(a,a^\{\\prime\}\)=0for any two independent samples, and by the Bellman structure, if all reachable successor states also exhibit this concentration, thenU⁡\(s,s\)=0U\(s,s\)=0\. The agent is perfectly consistent from statessonward\.

The complete RSD training algorithm is detailed in[Algorithm1](https://arxiv.org/html/2610.33012#alg1)in Appendix[A\.1](https://arxiv.org/html/2610.33012#A1.SS1)\. For inference, the computation of the consistency score requires only a single forward pass, with no additional rollouts, NLI evaluations, or sampling\. The Appendix[A\.1](https://arxiv.org/html/2610.33012#A1.SS1)also details the algorithm for RSD inference in[Algorithm2](https://arxiv.org/html/2610.33012#alg2)\.

## 5Theoretical Analysis

Our formulation replaces the reward signal with NLI classifications and operates on compressed state embeddings rather than full conversation histories\. We need to establish two things: first, that the recursive equation converges to a well\-defined quantity, and second, that this quantity provides meaningful guarantees about the agent’s actual behavior\.

The Bellman operator in[Equation6](https://arxiv.org/html/2610.33012#S4.E6)is aγ\\gamma\-contraction in supremum norm, so a unique fixed pointU∗U^\{\*\}exists withU∗∈\[0,1/\(1−γ\)\]U^\{\*\}\\in\[0,1/\(1\-\\gamma\)\]\. Refer to[SectionA\.2](https://arxiv.org/html/2610.33012#A1.SS2)

### 5\.1Disagreement Probability

In this section we interpret theU⁡\(s,s\)U\(s,s\)score and make conclusions about the probability that two independent runs of the agent disagree\. We first show a bound on the total trajectory level disagreement and a bound on the existence of a dominant behavioral mode\.

###### Theorem 1\(Trajectory Agreement\)\.

LetD⁡\(τ\(i\),τ\(j\)\)=∑t=0∞γt​dNLI​\(at\(i\),at\(j\)\)D\(\\tau^\{\(i\)\},\\tau^\{\(j\)\}\)=\\sum\_\{t=0\}^\{\\infty\}\\gamma^\{t\}d\_\{\\text\{NLI\}\}\(a\_\{t\}^\{\(i\)\},a\_\{t\}^\{\(j\)\}\)be the total discounted disagreement between two independent rollouts from statess\. For any thresholdδ\>0\\delta\>0:

Pr⁡\(D⁡\(τ\(i\),τ\(j\)\)≥δ\)≤U⁡\(s,s\)δ\.\\Pr\\big\(D\(\\tau^\{\(i\)\},\\tau^\{\(j\)\}\)\\geq\\delta\\big\)\\leq\\frac\{U\(s,s\)\}\{\\delta\}\.\(11\)

###### Theorem 2\(Dominant Action Class\)\.

IfU⁡\(s,s\)<1/4U\(s,s\)<1/4, there exists a semantic equivalence class\[C∗\]\[C^\{\*\}\]such that:

Pr⁡\(π⁡\(s\)∈\[C∗\]\)≥1−2​U​\(s,s\)\.\\Pr\(\\pi\(s\)\\in\[C^\{\*\}\]\)\\geq 1\-2U\(s,s\)\.\(12\)

Together, we can interpret the results as, ifU⁡\(s,s\)=0\.1U\(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\.

The proofs for[Theorem1](https://arxiv.org/html/2610.33012#Thmtheorem1a)and[Theorem2](https://arxiv.org/html/2610.33012#Thmtheorem2), and other theorems are detailed in Appendix[A\.2](https://arxiv.org/html/2610.33012#A1.SS2)\.

## 6Experimental Setup

We evaluate RSD onτ2\\tau^\{2\}\-bench\([Barres et al\., 2025](https://arxiv.org/html/2610.33012#bib.bib1)\), and ToolSandbox\([Lu et al\., 2024](https://arxiv.org/html/2610.33012#bib.bib16)\)to measure whether the learned metric captures trajectory\-level consistency and if it can serve as a reward signal for improving consistency during fine\-tuning\. For each benchmark, we run 8 independent trials across 8 test samples \(64 trajectories\) in total for Qwen\-2\.5 models \(3B and 7B parameters\)\([Team, 2024](https://arxiv.org/html/2610.33012#bib.bib20)\), where each trajectory consists of interleaved user messages, agent actions \(including tool calls\), and tool outputs\. We construct the training set by generating multiple rollouts using temperature set to 1\. We compare RSD against the Qwen baseline and three other methods, i\.e\., token\-level entropy\([Malinin and Gales, 2020](https://arxiv.org/html/2610.33012#bib.bib17)\), semantic entropy\([Kuhn et al\., 2023](https://arxiv.org/html/2610.33012#bib.bib13)\), and supervised fine\-tuning \(SFT\)\. For token entropy, semantic entropy, and RSD experiments, we fine\-tune the base models using Group Relative Policy Optimization \(GRPO\)\([Shao et al\., 2024](https://arxiv.org/html/2610.33012#bib.bib18)\), using each metric as a reward signal\. We minimize token and semantic entropy via negative entropy rewards, and minimize RSD self\-distance−U^θ​\(s,s\)\-\\hat\{U\}\_\{\\theta\}\(s,s\)\. For the evaluation metric, we adopt the evaluation framework from[Chong et al\. \(2026\)](https://arxiv.org/html/2610.33012#bib.bib5)to evaluate the agent behaviour\. We report two task performance metrics, area under the progress curve \(AUC\) which measures how quickly the agent makes progress, and the final progress rate\. To measure behavioral consistency, we compute the coefficient of variation \(CV =σ/μ\\sigma/\\mu\) of performance metrics across 8 independent trials per task, where a lower CV indicates more consistent behavior\. To ensure a fair comparison across models, we restrict evaluation to the intersection of samples where all models within a size group achieve non\-zero mean AUC\. For inference, we set the temperature to 0\. For more details, refer to Appendix[A\.3](https://arxiv.org/html/2610.33012#A1.SS3)\.

We use LLMs to polish the paper, write portions of the training and inference code, and verify the proofs presented in the paper\.

## 7Results and Discussion

### 7\.1Main Results

[Table1](https://arxiv.org/html/2610.33012#S7.T1)summarizes the overall performance and consistency changes across two benchmarks and two base models\. In most cases, we observe that RSD achieves a substantial reduction in CV\. Smaller models show the largest reduction in CV compared to larger models\. Onτ2\\tau^\{2\}\-bench with Qwen 2\.5 3B, RSD reduces AUC CV by 30\.9% and progress CV by 26\.1% compared to the base model\. On ToolSandbox 3B, we observe a 50\.5% reduction in AUC CV and a 49\.3% reduction in progress CV\. These results suggest that smaller models exhibit higher intrinsic stochasticity in their decision\-making processes\. In contrast, 7B models exhibit lower baseline variance \(e\.g\., 0\.38 CV for ToolSandbox 7B compared to 0\.90 for 3B\), indicating more stable internal representations\. For these larger models, the absolute gains from RSD are smaller because there is less variance to eliminate\.

We observe that token entropy and semantic entropy produce inconsistent results, with token entropy increasing CV in multiple cases\. Minimizing token entropy encourages the model to make confident predictions at each decoding step\. However, this token\-level confidence does not translate to trajectory\-level consistency\. This occurs because token entropy measures local uncertainty at the vocabulary level without considering semantic meaning\. Semantic entropy partially addresses this issue by clustering similar responses using NLI, but using this signal as a reward still produces inconsistent behavior onτ2\\tau^\{2\}\-bench \(−15\.9%\-15\.9\\%on 3B and\+0\.5%\+0\.5\\%on 7B\) and achieves only modest reductions on ToolSandbox \(−7\.0%\-7\.0\\%on 3B and−6\.0%\-6\.0\\%on 7B\)\. The fundamental limitation of both methods is that they operate myopically at the level of individual turns\. Agents can therefore be locally consistent while remaining globally inconsistent\. RSD directly addresses this issue through its trajectory\-level formulation \([Definition2](https://arxiv.org/html/2610.33012#Thmdefinition2)\) and empirically improves consistency across benchmarks\.

We compare RSD with SFT to investigate whether access to ground\-truth labels and expert demonstrations leads to more consistent behavior\. We observe that onτ2\\tau^\{2\}\-bench, SFT reduces CV \(−28\.0%\-28\.0\\%for 3B and−6\.5%\-6\.5\\%for 7B\), but on ToolSandbox it increases CV \(\+17\.9%\+17\.9\\%for 7B\)\.

Our training procedure estimates RSD from rollouts generated by a strong base agent that already makes non\-trivial progress on the target benchmarks\. As a result, the RSD network is trained only on trajectories sampled from a competent policy, and GRPO updates move the policy locally within this region of the behavior space\. In particular, degenerate policies that always output a fixed response and achieve near\-zero progress do not appear in the rollout distribution and are therefore not explicitly assigned low RSD\. This helps explain why optimizing RSD in our experiments does not collapse to trivial “always fail consistently” solutions, even though such policies would theoretically achieve low RSD\. Exploring from a randomly initialized or extremely weak policy could expose different failure modes, and avoiding trivial but consistent solutions in that regime would likely require combining RSD with correctness\-aligned rewards\.

Table 1:Performance and consistency, measured by the coefficient of variation \(CV\), across different fine\-tuning strategies\. The upwards and downwards arrows↑⁣↓\\uparrow\\downarrowshow relative change from the baseline\. The blue downwards arrow↓\\downarrowindicates reduction in variation, while the red upwards arrow↑\\uparrowindicates increased in variation\.
### 7\.2Hybrid Training Ablation

[Table2](https://arxiv.org/html/2610.33012#S7.T2)investigates whether combining RSD with task\-specific progress rewards can improve upon pure RSD\. We combine the reward from RSD \(weightλ\\lambda\) and progress delta at each step \(weight1−λ1\-\\lambda\) on ToolSandbox for Qwen\-2\.5\-7b model\. We observe a counterintuitive result where RSD \(λ=1\\lambda=1\) achieves both the lowest CV and the best performance\. As we decreaseλ\\lambdato incorporate progress rewards, both consistency and performance degrades monotonically\. We suspect this is happening because of progress delta being a very sparse reward\. Agent sometime makes the most amount of progress in the final turns which causes previous turns to receive near 0 rewards, causing the signal to be noisy\.

Table 2:Hybrid ablation on ToolSandbox Qwen\-2\.5\-7B\. The RSD weightλ\\lambdacontrols the balance between RSD consistency reward \(λ\\lambda\) and progress delta reward \(1−λ1\-\\lambda\)\.↑⁣↓\\uparrow\\downarrowshows relative change from pure RSD \(λ=1\.0\\lambda=1\.0\)\. The red upwards arrow↑\\uparrowindicates increased in variation\.
### 7\.3Evaluating finetuned models using RSD

To validate that finetuning with RSD as a reward signal reduces the actual inter\-run semantic inconsistency captured by our metric, we evaluate the RSD score directly on the outputs of each finetuned model\. For each test sample, the agent is run 8 times independently, and pairwise NLI \(gpt\-4\.1\) is used to classify whether outputs at each turn are functionally equivalent \(entailment\), contradictory, or neutral\.

[Table3](https://arxiv.org/html/2610.33012#S7.T3)reports the overall RSD scores across all methods\. On ToolSandbox, RSD finetuning reduces the inter\-run inconsistency by 52\.8% \(from 0\.672 to 0\.317\), the largest reduction among all methods\. Token entropy and semantic entropy also reduce inconsistency \(−40\.5%\-40\.5\\%and−34\.4%\-34\.4\\%respectively\), confirming that all uncertainty\-based rewards can improve behavioral consistency, though RSD is most effective because it directly optimizes the trajectory\-level consistency objective\. Notably, SFT shows negligible improvement \(−1\.1%\-1\.1\\%\) on ToolSandbox despite memorizing successful trajectories, suggesting that supervised learning alone does not enforce output consistency\.

Onτ2\\tau^\{2\}\-bench, the baseline RSD is substantially higher \(0\.8730\.873\), reflecting the compounding nature of multi\-turn airline service tasks where small early differences cascade into divergent trajectories\. All methods show limited improvement, with SFT achieving the largest reduction \(−8\.3%\-8\.3\\%\) by anchoring the model to fixed expert demonstrations\.

Table 3:Direct RSD evaluation \(lower = more consistent\) across 8 independent trials per sample, measured via gpt\-4\.1\.

## 8Conclusion and Limitation

We introduced Recursive Semantic Divergence \(RSD\), an unsupervised trajectory\-level consistency metric for LLM agents that captures how behavioral inconsistencies propagate across future interaction turns\. Unlike existing correctness\-based or token\-level approaches, RSD provides a recursive estimate of semantic divergence between independent executions from the same interaction\-history state, and can additionally be used as a training signal to reinforce consistent agent behavior\. Experiments across multiple benchmarks demonstrate that optimizing RSD reduces trajectory variability\.

Nevertheless, our approach has several limitations\. RSD may require retraining or adaptation when transferred to new domains or environments\. Moreover, consistency does not necessarily imply correctness, and therefore the metric cannot distinguish consistently failing behaviors from consistently successful ones\. Finally, the reliability of RSD depends heavily on the accuracy and calibration of the underlying NLI model used to estimate semantic disagreement\.

## References

- Barres et al\. \[2025\]Victor Barres, Honghua Dong, Soham Ray, Xujie Si, and Karthik Narasimhan\.τ2\\tau^\{2\}\-bench: Evaluating conversational agents in a dual\-control environment\.*arXiv preprint arXiv:2506\.07982*, 2025\.
- Bowman et al\. \[2015\]Samuel R\. Bowman, Gabor Angeli, Christopher Potts, and Christopher D\. Manning\.A large annotated corpus for learning natural language inference\.In*Proceedings of the Conference on Empirical Methods in Natural Language Processing*, 2015\.
- Castro et al\. \[2021\]Pablo Samuel Castro, Tyler Kastner, Prakash Panangaden, and Mark Rowland\.Mico: Improved representations via sampling\-based state similarity for markov decision processes\.In*Advances in Neural Information Processing Systems*, 2021\.
- Chang et al\. \[2024\]Ma Chang, Junlei Zhang, Zhihao Zhu, Cheng Yang, Yujiu Yang, Yaohui Jin, Zhenzhong Lan, Lingpeng Kong, and Junxian He\.Agentboard: An analytical evaluation board of multi\-turn llm agents\.*Advances in neural information processing systems*, 37:74325–74362, 2024\.
- Chong et al\. \[2026\]Penny Chong, Harshavardhan Abichandani, Jiyuan Shen, Atin Ghosh, Min Pyae Moe, Yifan Mai, and Daniel Dahlmeier\.Talk, evaluate, diagnose: User\-aware agent evaluation with automated error analysis\.In*The Fourteenth International Conference on Learning Representations*, 2026\.URL[https://openreview\.net/forum?id=fHsVNklKOc](https://openreview.net/forum?id=fHsVNklKOc)\.
- Duan et al\. \[2025\]Jinhao Duan, James Diffenderfer, Sandeep Madireddy, Tianlong Chen, Bhavya Kailkhura, and Kaidi Xu\.Uprop: Investigating the uncertainty propagation of llms in multi\-step agentic decision\-making, 2025\.URL[https://arxiv\.org/abs/2506\.17419](https://arxiv.org/abs/2506.17419)\.
- Ferns et al\. \[2004\]Norm Ferns, Prakash Panangaden, and Doina Precup\.Metrics for finite markov decision processes\.In*Uncertainty in Artificial Intelligence*, 2004\.
- Huang et al\. \[2025\]Kung\-Hsiang Huang, Akshara Prabhakar, Onkar Thorat, Divyansh Agarwal, Prafulla Kumar Choubey, Yixin Mao, Silvio Savarese, Caiming Xiong, and Chien\-Sheng Wu\.Crmarena\-pro: Holistic assessment of llm agents across diverse business scenarios and interactions\.*arXiv preprint arXiv:2505\.18878*, 2025\.
- Jang et al\. \[2025\]Kyochul Jang, Donghyeon Lee, Kyusik Kim, Dongseok Heo, Taewhoo Lee, Woojeong Kim, and Bongwon Suh\.Dice\-bench: Evaluating the tool\-use capabilities of large language models in multi\-round, multi\-party dialogues\.*arXiv preprint arXiv:2506\.22853*, 2025\.
- Kaelbling et al\. \[1998\]Leslie Pack Kaelbling, Michael L\. Littman, and Anthony R\. Cassandra\.Planning and acting in partially observable stochastic domains\.*Artificial Intelligence*, 101:99–134, 1998\.
- Kim et al\. \[2024\]Yubin Kim, Chanwoo Park, Hyewon Jeong, Yik Siu Chan, Xuhai Xu, Daniel McDuff, Hyeonhoon Lee, Marzyeh Ghassemi, Cynthia Breazeal, and Hae Won Park\.MDAgents: An adaptive collaboration of LLMs for medical decision\-making\.In*The Thirty\-eighth Annual Conference on Neural Information Processing Systems*, 2024\.URL[https://openreview\.net/forum?id=EKdk4vxKO4](https://openreview.net/forum?id=EKdk4vxKO4)\.
- Kirchhof et al\. \[2025\]Michael Kirchhof, Gjergji Kasneci, and Enkelejda Kasneci\.Position: Uncertainty quantification needs reassessment for large\-language model agents, 2025\.URL[https://arxiv\.org/abs/2505\.22655](https://arxiv.org/abs/2505.22655)\.
- Kuhn et al\. \[2023\]Lorenz Kuhn, Yarin Gal, and Sebastian Farquhar\.Semantic uncertainty: Linguistic invariances for uncertainty estimation in natural language generation\.In*International Conference on Learning Representations*, 2023\.
- Larsen and Skou \[1991\]Kim Guldstrand Larsen and Arne Skou\.Bisimulation through probabilistic testing\.*Inf\. Comput\.*, 94:1–28, 1991\.URL[https://api\.semanticscholar\.org/CorpusID:45053958](https://api.semanticscholar.org/CorpusID:45053958)\.
- Liu et al\. \[2023\]Xiao Liu, Hao Yu, Hanchen Zhang, Yifan Xu, Xuanyu Lei, Hanyu Lai, Yu Gu, Hangliang Ding, Kaiwen Men, Kejuan Yang, et al\.Agentbench: Evaluating llms as agents\.*arXiv preprint arXiv:2308\.03688*, 2023\.
- Lu et al\. \[2024\]Jiarui Lu, Thomas Holleis, Yizhe Zhang, Bernhard Aumayer, Feng Nan, Felix Bai, Shuang Ma, Shen Ma, Mengyu Li, Guoli Yin, et al\.Toolsandbox: A stateful, conversational, interactive evaluation benchmark for llm tool use capabilities\.*arXiv preprint arXiv:2408\.04682*, 2024\.
- Malinin and Gales \[2020\]Andrey Malinin and Mark Gales\.Uncertainty estimation in autoregressive structured prediction\.*arXiv preprint arXiv:2002\.07650*, 2020\.
- Shao et al\. \[2024\]Zhihong Shao, Peiyi Wang, Qihao Zhu, Runxin Xu, Junxiao Song, Mingchuan Zhang, Y\.K\. Li, Y\. Wu, and Daya Guo\.Deepseekmath: Pushing the limits of mathematical reasoning in open language models\.*arXiv preprint arXiv:2402\.03300*, 2024\.
- Shinn et al\. \[2023\]Noah Shinn, Federico Cassano, Ashwin Gopinath, Karthik R Narasimhan, and Shunyu Yao\.Reflexion: language agents with verbal reinforcement learning\.In*Thirty\-seventh Conference on Neural Information Processing Systems*, 2023\.URL[https://openreview\.net/forum?id=vAElhFcKW6](https://openreview.net/forum?id=vAElhFcKW6)\.
- Team \[2024\]Qwen Team\.Qwen2\.5: A party of foundation models, September 2024\.URL[https://qwenlm\.github\.io/blog/qwen2\.5/](https://qwenlm.github.io/blog/qwen2.5/)\.
- Tu et al\. \[2025\]Tao Tu, Mike Schaekermann, Anil Palepu, Khaled Saab, Jan Freyberg, Ryutaro Tanno, Amy Wang, Brenna Li, Mohamed Amin, Yong Cheng, et al\.Towards conversational diagnostic artificial intelligence\.*Nature*, 642\(8067\):442–450, 2025\.
- Wang et al\. \[2023\]Xingyao Wang, Zihan Wang, Jiateng Liu, Yangyi Chen, Lifan Yuan, Hao Peng, and Heng Ji\.Mint: Evaluating llms in multi\-turn interaction with tools and language feedback\.*arXiv preprint arXiv:2309\.10691*, 2023\.
- Williams et al\. \[2018\]Adina Williams, Nikita Nangia, and Samuel R\. Bowman\.A broad\-coverage challenge corpus for sentence understanding through inference\.In*Proceedings of NAACL\-HLT*, 2018\.
- Xie et al\. \[2024\]Tianbao Xie, Danyang Zhang, Jixuan Chen, Xiaochuan Li, Siheng Zhao, Ruisheng Cao, Toh J Hua, Zhoujun Cheng, Dongchan Shin, Fangyu Lei, et al\.Osworld: Benchmarking multimodal agents for open\-ended tasks in real computer environments\.*Advances in Neural Information Processing Systems*, 37:52040–52094, 2024\.
- Yang et al\. \[2024\]John Yang, Carlos E Jimenez, Alexander Wettig, Kilian Lieret, Shunyu Yao, Karthik R Narasimhan, and Ofir Press\.SWE\-agent: Agent\-computer interfaces enable automated software engineering\.In*The Thirty\-eighth Annual Conference on Neural Information Processing Systems*, 2024\.URL[https://openreview\.net/forum?id=mXpq6ut8J3](https://openreview.net/forum?id=mXpq6ut8J3)\.
- Yao et al\. \[2023\]Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik Narasimhan, and Yuan Cao\.React: Synergizing reasoning and acting in language models\.In*International Conference on Learning Representations*, 2023\.
- Yao et al\. \[2024\]Shunyu Yao, Noah Shinn, Pedram Razavi, and Karthik Narasimhan\.τ\\tau\-bench: A benchmark for tool\-agent\-user interaction in real\-world domains, 2024\.*URL https://arxiv\. org/abs/2406\.12045*, 2024\.

## Appendix Contents

## Appendix AAppendix

### A\.1Algorithm for RSD training and inference

The following pseudocode details the algorithm for RSD training\.

Algorithm 1RSD Training: Learning the Consistency Metric0:Target agent policy

π\\pi,

MMrollouts per task, NLI classifier,pretrainedtext encoderEnc

0:Hyperparameters:

γ\\gamma,

α\\alpha,

β\\beta,

nn\(TD steps\), learning rate

η\\eta
1:Data collection:For each task, collect

MMindependent rollouts

\{τ\(1\),…,τ\(M\)\}\\\{\\tau^\{\(1\)\},\\ldots,\\tau^\{\(M\)\}\\\}from

π\\pi
2:NLI labeling:For all trajectory pairs

\(i,j\)\(i,j\)within the task, compute

dNLI​\(at\(i\),at\(j\)\)d\_\{\\text\{NLI\}\}\(a\_\{t\}^\{\(i\)\},a\_\{t\}^\{\(j\)\}\)at each turn

tt
3:Initialize MICoNetwork parameters

θ\\theta, target network

θ¯←θ\\bar\{\\theta\}\\leftarrow\\theta
4:fortraining step

=1,…,N=1,\\ldots,Ndo

5:Sample a task and two trajectories

τ\(i\),τ\(j\)\\tau^\{\(i\)\},\\tau^\{\(j\)\}for the same task

6:Sample a turn

ttwithin the trajectory

7:Compute embeddings:zst\(i\)←Enc​\(st\(i\)\)z^\{s^\{\(i\)\}\_\{t\}\}\\leftarrow\\text\{Enc\}\(s\_\{t\}^\{\(i\)\}\),zst\(j\)←Enc​\(st\(j\)\)z^\{s^\{\(j\)\}\_\{t\}\}\\leftarrow\\text\{Enc\}\(s\_\{t\}^\{\(j\)\}\)

8:Compute

nn\-step TD target:

yt←∑k=0n−1γk​dNLI​\(at\+k\(i\),at\+k\(j\)\)\+γn​U^θ¯​\(st\+n\(i\),st\+n\(j\)\)\{\\color\[rgb\]\{0,0,0\}y\_\{t\}\}\\leftarrow\\sum\_\{k=0\}^\{n\-1\}\\gamma^\{k\}d\_\{\\text\{NLI\}\}\(a\_\{t\+k\}^\{\(i\)\},a\_\{t\+k\}^\{\(j\)\}\)\+\\gamma^\{n\}\\hat\{U\}\_\{\\bar\{\\theta\}\}\(s\_\{t\+n\}^\{\(i\)\},s\_\{t\+n\}^\{\(j\)\}\)
9:Update

θ\\thetato minimize

\(U^θ​\(st\(i\),st\(j\)\)−yt\)2\(\\hat\{U\}\_\{\\theta\}\(s\_\{t\}^\{\(i\)\},s\_\{t\}^\{\(j\)\}\)\-\{\\color\[rgb\]\{0,0,0\}y\_\{t\}\}\)^\{2\}
10:Soft update the target network

11:endfor

12:returnTrained MICoNetwork

ϕθ\\phi\_\{\\theta\}

The following pseudocode details the algorithm for RSD inference\.

Algorithm 2RSD Inference: Per\-State Consistency Scoring0:Trained MICoNetwork

ϕθ\\phi\_\{\\theta\},pretrainedtext encoderEnc, norm coefficient

α\\alpha
0:Interaction history state

ss
1:

zs←Enc​\(s\)z^\{s\}\\leftarrow\\text\{Enc\}\(s\)
2:

ϕs←ϕθ​\(zs\)\\phi\_\{s\}\\leftarrow\\phi\_\{\\theta\}\(z^\{s\}\)
3:

U^​\(s,s\)←2​α​‖ϕs‖2\\hat\{U\}\(s,s\)\\leftarrow 2\\alpha\\\|\\phi\_\{s\}\\\|^\{2\}
4:return

U^​\(s,s\)\\hat\{U\}\(s,s\)

### A\.2Theoretical Analysis

We establish that the RSD fixed\-point equation converges to a well\-defined quantity with the NLI changes, and the quantity provides meaningful guarantees about agent behavior\. Throughout, we letτ\(i\),τ\(j\)∼Π\(⋅\|s\)\\tau^\{\(i\)\},\\tau^\{\(j\)\}\\sim\\Pi\(\\cdot\|s\)denote two independent trajectory rollouts from statess, withat\(i\),at\(j\)a\_\{t\}^\{\(i\)\},a\_\{t\}^\{\(j\)\}the actions taken at stepttin each rollout\.

#### A\.2\.1Convergence

We first verify that the recursive equation \([Equation6](https://arxiv.org/html/2610.33012#S4.E6)\) has a unique solution\. Recall the RSD fixed\-point equation:

U\(st\(i\),st\(j\)\)=𝔼at\(i\)∼π\(⋅\|st\(i\)\),at\(j\)∼π\(⋅\|st\(j\)\)\[dNLI\(at\(i\),at\(j\)\)\]\+γ⋅𝔼\[U\(st\+1\(i\),st\+1\(j\)\)\]\.U\(s\_\{t\}^\{\(i\)\},s\_\{t\}^\{\(j\)\}\)=\\mathbb\{E\}\_\{a\_\{t\}^\{\(i\)\}\\sim\\pi\(\\cdot\|s\_\{t\}^\{\(i\)\}\),\\;a\_\{t\}^\{\(j\)\}\\sim\\pi\(\\cdot\|s\_\{t\}^\{\(j\)\}\)\}\\big\[d\_\{\\text\{NLI\}\}\(a\_\{t\}^\{\(i\)\},a\_\{t\}^\{\(j\)\}\)\\big\]\+\\gamma\\cdot\\mathbb\{E\}\\big\[U\(s\_\{t\+1\}^\{\(i\)\},s\_\{t\+1\}^\{\(j\)\}\)\\big\]\.Define the Bellman operator𝒯\\mathcal\{T\}acting on bounded functionsU:ℋ×ℋ→ℝ≥0U:\\mathcal\{H\}\\times\\mathcal\{H\}\\to\\mathbb\{R\}\_\{\\geq 0\}by:

\(𝒯U\)\(st\(i\),st\(j\)\)=𝔼at\(i\)∼π\(⋅\|st\(i\)\),at\(j\)∼π\(⋅\|st\(j\)\)\[dNLI\(at\(i\),at\(j\)\)\]\+γ⋅𝔼\[U\(st\+1\(i\),st\+1\(j\)\)\],\(\\mathcal\{T\}U\)\(s\_\{t\}^\{\(i\)\},s\_\{t\}^\{\(j\)\}\)=\\mathbb\{E\}\_\{a\_\{t\}^\{\(i\)\}\\sim\\pi\(\\cdot\|s\_\{t\}^\{\(i\)\}\),\\,a\_\{t\}^\{\(j\)\}\\sim\\pi\(\\cdot\|s\_\{t\}^\{\(j\)\}\)\}\\big\[d\_\{\\text\{NLI\}\}\(a\_\{t\}^\{\(i\)\},a\_\{t\}^\{\(j\)\}\)\\big\]\+\\gamma\\cdot\\mathbb\{E\}\\big\[U\(s\_\{t\+1\}^\{\(i\)\},s\_\{t\+1\}^\{\(j\)\}\)\\big\],wherest\+1\(i\)∼P\(⋅\|s\(i\),a\(i\)\)s\_\{t\+1\}^\{\(i\)\}\\sim P\(\\cdot\|s^\{\(i\)\},a^\{\(i\)\}\)andst\+1\(j\)∼P\(⋅\|s\(j\),a\(j\)\)s\_\{t\+1\}^\{\(j\)\}\\sim P\(\\cdot\|s^\{\(j\)\},a^\{\(j\)\}\)are the respective successor states\. SincedNLI∈\[0,1\]d\_\{\\text\{NLI\}\}\\in\[0,1\]is bounded andγ<1\\gamma<1, the operator𝒯\\mathcal\{T\}is aγ\\gamma\-contraction in supremum norm\.

#### A\.2\.2Disagreement Probability

Given thatU∗U^\{\*\}is well\-defined, we derive what the self\-distanceU⁡\(s,s\)U\(s,s\)implies about agent behaviour\. We make use of the[Definition2](https://arxiv.org/html/2610.33012#Thmdefinition2), where self distance equals to the expected total discounted disagreement between two independent rollouts\.

U\(s,s\)=𝔼τ\(i\),τ\(j\)∼Π\(⋅\|s\)\[∑t=0∞γtdNLI\(at\(i\),at\(j\)\)\]=𝔼\[D\(τ\(i\),τ\(j\)\)\],U\(s,s\)=\\mathbb\{E\}\_\{\\tau^\{\(i\)\},\\tau^\{\(j\)\}\\sim\\Pi\(\\cdot\|s\)\}\\left\[\\sum\_\{t=0\}^\{\\infty\}\\gamma^\{t\}\\,d\_\{\\text\{NLI\}\}\(a\_\{t\}^\{\(i\)\},a\_\{t\}^\{\(j\)\}\)\\right\]=\\mathbb\{E\}\[D\(\\tau^\{\(i\)\},\\tau^\{\(j\)\}\)\],\(13\)whereD⁡\(τ\(i\),τ\(j\)\)≔∑t=0∞γt​dNLI​\(at\(i\),at\(j\)\)≥0D\(\\tau^\{\(i\)\},\\tau^\{\(j\)\}\)\\coloneqq\\sum\_\{t=0\}^\{\\infty\}\\gamma^\{t\}\\,d\_\{\\text\{NLI\}\}\(a\_\{t\}^\{\(i\)\},a\_\{t\}^\{\(j\)\}\)\\geq 0is the total discounted disagreement\.

###### Theorem 1\(Trajectory Agreement\)\.

LetD⁡\(τ\(i\),τ\(j\)\)=∑t=0∞γt​dNLI​\(at\(i\),at\(j\)\)D\(\\tau^\{\(i\)\},\\tau^\{\(j\)\}\)=\\sum\_\{t=0\}^\{\\infty\}\\gamma^\{t\}d\_\{\\text\{NLI\}\}\(a\_\{t\}^\{\(i\)\},a\_\{t\}^\{\(j\)\}\)be the total discounted disagreement between two independent rollouts from statess\. For any thresholdδ\>0\\delta\>0:

Pr⁡\(D⁡\(τ\(i\),τ\(j\)\)≥δ\)≤U⁡\(s,s\)δ\.\\Pr\\big\(D\(\\tau^\{\(i\)\},\\tau^\{\(j\)\}\)\\geq\\delta\\big\)\\leq\\frac\{U\(s,s\)\}\{\\delta\}\.\(14\)

###### Proof\.

SinceD⁡\(τ\(i\),τ\(j\)\)≥0D\(\\tau^\{\(i\)\},\\tau^\{\(j\)\}\)\\geq 0and𝔼⁡\[D⁡\(τ\(i\),τ\(j\)\)\]=U⁡\(s,s\)\\mathbb\{E\}\[D\(\\tau^\{\(i\)\},\\tau^\{\(j\)\}\)\]=U\(s,s\)by[Equation13](https://arxiv.org/html/2610.33012#A1.E13), Markov’s inequality directly gives:

Pr⁡\(D⁡\(τ\(i\),τ\(j\)\)≥δ\)≤𝔼⁡\[D⁡\(τ\(i\),τ\(j\)\)\]δ=U⁡\(s,s\)δ\.\\Pr\\big\(D\(\\tau^\{\(i\)\},\\tau^\{\(j\)\}\)\\geq\\delta\\big\)\\leq\\frac\{\\mathbb\{E\}\[D\(\\tau^\{\(i\)\},\\tau^\{\(j\)\}\)\]\}\{\\delta\}=\\frac\{U\(s,s\)\}\{\\delta\}\.∎

A useful instantiation isδ=U⁡\(s,s\)\\delta=\\sqrt\{U\(s,s\)\}, which givesPr⁡\(D≥U⁡\(s,s\)\)≤U⁡\(s,s\)\\Pr\(D\\geq\\sqrt\{U\(s,s\)\}\)\\leq\\sqrt\{U\(s,s\)\}: both the disagreement threshold and the probability of exceeding it shrink asU⁡\(s,s\)→0U\(s,s\)\\to 0\.

###### Corollary 2\(Immediate Contradiction Bound\)\.

The probability that two independent actions from statesscontradict each other satisfies:

Pr⁡\(contradiction at step​0\)≤U⁡\(s,s\)\.\\Pr\\big\(\\text\{contradiction at step \}0\\big\)\\leq U\(s,s\)\.

###### Proof\.

We first bounding the expected immediate disagreement byU⁡\(s,s\)U\(s,s\), then bounding the contradiction probability by the expected immediate disagreement\.

DefineD0\(s\)≔𝔼a0\(i\),a0\(j\)∼π\(⋅\|s\)\[dNLI\(a0\(i\),a0\(j\)\)\]D\_\{0\}\(s\)\\coloneqq\\mathbb\{E\}\_\{a\_\{0\}^\{\(i\)\},a\_\{0\}^\{\(j\)\}\\sim\\pi\(\\cdot\|s\)\}\[d\_\{\\text\{NLI\}\}\(a\_\{0\}^\{\(i\)\},a\_\{0\}^\{\(j\)\}\)\]as the expected immediate disagreement\. ExpandingD⁡\(τ\(i\),τ\(j\)\)D\(\\tau^\{\(i\)\},\\tau^\{\(j\)\}\)into its first term and the remainder:

D⁡\(τ\(i\),τ\(j\)\)=dNLI​\(a0\(i\),a0\(j\)\)\+γ​∑t=1∞γt−1​dNLI​\(at\(i\),at\(j\)\)\.D\(\\tau^\{\(i\)\},\\tau^\{\(j\)\}\)=d\_\{\\text\{NLI\}\}\(a\_\{0\}^\{\(i\)\},a\_\{0\}^\{\(j\)\}\)\+\\gamma\\sum\_\{t=1\}^\{\\infty\}\\gamma^\{t\-1\}\\,d\_\{\\text\{NLI\}\}\(a\_\{t\}^\{\(i\)\},a\_\{t\}^\{\(j\)\}\)\.SincedNLI≥0d\_\{\\text\{NLI\}\}\\geq 0, every term in the remainder is non\-negative\. Taking expectations of both sides:

U⁡\(s,s\)=𝔼⁡\[D⁡\(τ\(i\),τ\(j\)\)\]=D0​\(s\)\+γ​𝔼​\[∑t=1∞γt−1​dNLI​\(at\(i\),at\(j\)\)\]⏟≥0\.U\(s,s\)=\\mathbb\{E\}\[D\(\\tau^\{\(i\)\},\\tau^\{\(j\)\}\)\]=D\_\{0\}\(s\)\+\\underbrace\{\\gamma\\mathbb\{E\}\\left\[\\sum\_\{t=1\}^\{\\infty\}\\gamma^\{t\-1\}\\,d\_\{\\text\{NLI\}\}\(a\_\{t\}^\{\(i\)\},a\_\{t\}^\{\(j\)\}\)\\right\]\}\_\{\\geq\\,0\}\.ThereforeD0​\(s\)≤U⁡\(s,s\)D\_\{0\}\(s\)\\leq U\(s,s\)\.

Then, letpentailp\_\{\\text\{entail\}\},pneutralp\_\{\\text\{neutral\}\}, andpcontrap\_\{\\text\{contra\}\}denote the probabilities that two independent samplesa0\(i\),a0\(j\)∼π\(⋅\|s\)a\_\{0\}^\{\(i\)\},a\_\{0\}^\{\(j\)\}\\sim\\pi\(\\cdot\|s\)yield bidirectional entailment, neutrality, or contradiction respectively, withpentail\+pneutral\+pcontra=1p\_\{\\text\{entail\}\}\+p\_\{\\text\{neutral\}\}\+p\_\{\\text\{contra\}\}=1\. By[Definition1](https://arxiv.org/html/2610.33012#Thmdefinition1),dNLId\_\{\\text\{NLI\}\}takes values00,0\.50\.5, and11for these three cases\.

D0​\(s\)=0⋅pentail\+0\.5⋅pneutral\+1⋅pcontra=0\.5​pneutral\+pcontra\.D\_\{0\}\(s\)=0\\cdot p\_\{\\text\{entail\}\}\+0\.5\\cdot p\_\{\\text\{neutral\}\}\+1\\cdot p\_\{\\text\{contra\}\}=0\.5\\,p\_\{\\text\{neutral\}\}\+p\_\{\\text\{contra\}\}\.Since0\.5​pneutral≥00\.5\\,p\_\{\\text\{neutral\}\}\\geq 0, we haveD0​\(s\)≥pcontraD\_\{0\}\(s\)\\geq p\_\{\\text\{contra\}\}\.

This results in:

Pr⁡\(contradiction at step​0\)=pcontra≤D0​\(s\)≤U⁡\(s,s\)\.\\Pr\(\\text\{contradiction at step \}0\)=p\_\{\\text\{contra\}\}\\leq D\_\{0\}\(s\)\\leq U\(s,s\)\.∎

###### Theorem 3\(Dominant Action Class\)\.

IfU⁡\(s,s\)<1/4U\(s,s\)<1/4, there exists a semantic equivalence classC∗C^\{\*\}such that:

Pr⁡\(π⁡\(s\)∈C∗\)≥1−2​U​\(s,s\)\.\\Pr\(\\pi\(s\)\\in C^\{\*\}\)\\geq 1\-2U\(s,s\)\.\(15\)HereC∗=Ck∗C^\{\*\}=C\_\{k^\{\*\}\}wherek∗=arg⁡maxk​Pr⁡\(π⁡\(s\)∈Ck\)k^\{\*\}=\\arg\\max\_\{k\}\\Pr\(\\pi\(s\)\\in C\_\{k\}\)is the most probable equivalence class under the policy\.

###### Proof\.

Partition the action space into semantic equivalence classes\{Ck\}k=1K\\\{C\_\{k\}\\\}\_\{k=1\}^\{K\}defined by bidirectional NLI entailment: two actionsa\(i\),a\(j\)a^\{\(i\)\},a^\{\(j\)\}belong to the same classCkC\_\{k\}if and only ifdNLI​\(a\(i\),a\(j\)\)=0d\_\{\\text\{NLI\}\}\(a^\{\(i\)\},a^\{\(j\)\}\)=0\(i\.e\., they mutually entail each other\)\. Letpk=Pr⁡\(π⁡\(s\)∈Ck\)p\_\{k\}=\\Pr\(\\pi\(s\)\\in C\_\{k\}\)with∑kpk=1\\sum\_\{k\}p\_\{k\}=1\.

We first lower bound on collision probability\. For two independent samplesa0\(i\),a0\(j\)∼π\(⋅\|s\)a\_\{0\}^\{\(i\)\},a\_\{0\}^\{\(j\)\}\\sim\\pi\(\\cdot\|s\), the probability they fall in the same class is:

Pr⁡\(a0\(i\)∼a0\(j\)\)=∑k=1Kpk2\.\\Pr\(a\_\{0\}^\{\(i\)\}\\sim a\_\{0\}^\{\(j\)\}\)=\\sum\_\{k=1\}^\{K\}p\_\{k\}^\{2\}\.When the samples fall in different classes, they are either neutral or contradictory\. By[Definition1](https://arxiv.org/html/2610.33012#Thmdefinition1),dNLI​\(a0\(i\),a0\(j\)\)≥0\.5d\_\{\\text\{NLI\}\}\(a\_\{0\}^\{\(i\)\},a\_\{0\}^\{\(j\)\}\)\\geq 0\.5in both cases\. Therefore, we can lower\-bound the expected immediate disagreement:

D0​\(s\)\\displaystyle D\_\{0\}\(s\)=𝔼⁡\[dNLI​\(a0\(i\),a0\(j\)\)\]\\displaystyle=\\mathbb\{E\}\[d\_\{\\text\{NLI\}\}\(a\_\{0\}^\{\(i\)\},a\_\{0\}^\{\(j\)\}\)\]\(16\)=𝔼⁡\[dNLI∣a0\(i\)∼a0\(j\)\]⏟=0​Pr⁡\(a0\(i\)∼a0\(j\)\)\\displaystyle=\\underbrace\{\\mathbb\{E\}\[d\_\{\\text\{NLI\}\}\\mid a\_\{0\}^\{\(i\)\}\\sim a\_\{0\}^\{\(j\)\}\]\}\_\{=\\,0\}\\Pr\(a\_\{0\}^\{\(i\)\}\\sim a\_\{0\}^\{\(j\)\}\)\+𝔼⁡\[dNLI∣a0\(i\)≁a0\(j\)\]​Pr⁡\(a0\(i\)≁a0\(j\)\)\\displaystyle\+\\mathbb\{E\}\[d\_\{\\text\{NLI\}\}\\mid a\_\{0\}^\{\(i\)\}\\not\\sim a\_\{0\}^\{\(j\)\}\]\\Pr\(a\_\{0\}^\{\(i\)\}\\not\\sim a\_\{0\}^\{\(j\)\}\)≥0\.5​Pr⁡\(a0\(i\)≁a0\(j\)\)\\displaystyle\\geq 0\.5\\,\\Pr\(a\_\{0\}^\{\(i\)\}\\not\\sim a\_\{0\}^\{\(j\)\}\)=0\.5​\(1−∑k=1Kpk2\)\.\\displaystyle=0\.5\\left\(1\-\\sum\_\{k=1\}^\{K\}p\_\{k\}^\{2\}\\right\)\.
By[Corollary2](https://arxiv.org/html/2610.33012#Thmtheorem2a),D0​\(s\)≤U⁡\(s,s\)D\_\{0\}\(s\)\\leq U\(s,s\)\. Substituting into the inequality from[Equation16](https://arxiv.org/html/2610.33012#A1.E16):

0\.5​\(1−∑k=1Kpk2\)≤U⁡\(s,s\)\.0\.5\\left\(1\-\\sum\_\{k=1\}^\{K\}p\_\{k\}^\{2\}\\right\)\\leq U\(s,s\)\.Rearranging:

∑k=1Kpk2≥1−2​U​\(s,s\)\.\\sum\_\{k=1\}^\{K\}p\_\{k\}^\{2\}\\geq 1\-2U\(s,s\)\.\(17\)
Now, we show the probability of the dominant class\. For any probability distribution\(p1,…,pK\)\(p\_\{1\},\\ldots,p\_\{K\}\)with∑kpk=1\\sum\_\{k\}p\_\{k\}=1, the following holds:

maxk⁡pk≥∑k=1Kpk2\.\\max\_\{k\}p\_\{k\}\\geq\\sum\_\{k=1\}^\{K\}p\_\{k\}^\{2\}\.
Combining with[Equation17](https://arxiv.org/html/2610.33012#A1.E17):

maxk⁡pk≥∑kpk2≥1−2​U​\(s,s\)\.\\max\_\{k\}p\_\{k\}\\geq\\sum\_\{k\}p\_\{k\}^\{2\}\\geq 1\-2U\(s,s\)\.
The classC∗=Ck∗C^\{\*\}=C\_\{k^\{\*\}\}achieving this maximum satisfiesPr⁡\(π⁡\(s\)∈C∗\)≥1−2​U​\(s,s\)\\Pr\(\\pi\(s\)\\in C^\{\*\}\)\\geq 1\-2U\(s,s\)\. The conditionU⁡\(s,s\)<1/4U\(s,s\)<1/4ensures this bound exceeds1/21/2, meaningC∗C^\{\*\}contains a strict majority of the policy’s probability mass\. ∎

#### A\.2\.3Approximation Error

The guarantees above hold for the true fixed pointU∗U^\{\*\}\. In practice, the learned approximationU^θ\\hat\{U\}\_\{\\theta\}differs fromU∗U^\{\*\}due to two sources of error: \(1\) the state embeddingϕ\\philoses information relative to the full interaction history, and \(2\) the NLI classifierd^NLI\\hat\{d\}\_\{\\text\{NLI\}\}is imperfect\. We quantify how these per\-step errors propagate through the recursive structure\.

Letϵϕ\\epsilon\_\{\\phi\}denote the worst\-case per\-step error from embedding compression:

ϵϕ=sups\(i\),s\(j\)\|𝔼\[dNLI\(a\(i\),a\(j\)\)∣s\(i\),s\(j\)\]−𝔼\[dNLI\(a\(i\),a\(j\)\)∣ϕ\(s\(i\)\),ϕ\(s\(j\)\)\]\|\\epsilon\_\{\\phi\}=\\sup\_\{s^\{\(i\)\},s^\{\(j\)\}\}\\left\|\\mathbb\{E\}\[d\_\{\\text\{NLI\}\}\(a^\{\(i\)\},a^\{\(j\)\}\)\\mid s^\{\(i\)\},s^\{\(j\)\}\]\-\\mathbb\{E\}\[d\_\{\\text\{NLI\}\}\(a^\{\(i\)\},a^\{\(j\)\}\)\\mid\\phi\(s^\{\(i\)\}\),\\phi\(s^\{\(j\)\}\)\]\\right\|and letϵNLI\\epsilon\_\{\\text\{NLI\}\}denote the worst\-case NLI classification error:

ϵNLI=supa\(i\),a\(j\)\|d^NLI​\(a\(i\),a\(j\)\)−dNLI∗​\(a\(i\),a\(j\)\)\|\\epsilon\_\{\\text\{NLI\}\}=\\sup\_\{a^\{\(i\)\},a^\{\(j\)\}\}\\left\|\\hat\{d\}\_\{\\text\{NLI\}\}\(a^\{\(i\)\},a^\{\(j\)\}\)\-d^\{\*\}\_\{\\text\{NLI\}\}\(a^\{\(i\)\},a^\{\(j\)\}\)\\right\|
###### Theorem 4\(Error Propagation\)\.

The approximation error satisfies:

\|U^θ​\(s,s\)−U∗​\(s,s\)\|≤ϵϕ\+ϵNLI1−γ\\left\|\\hat\{U\}\_\{\\theta\}\(s,s\)\-U^\{\*\}\(s,s\)\\right\|\\leq\\frac\{\\epsilon\_\{\\phi\}\+\\epsilon\_\{\\text\{NLI\}\}\}\{1\-\\gamma\}\(18\)

###### Proof\.

Let𝒯~\\tilde\{\\mathcal\{T\}\}denote the approximate Bellman operator that usesd^NLI\\hat\{d\}\_\{\\text\{NLI\}\}in place ofdNLI∗d^\{\*\}\_\{\\text\{NLI\}\}and conditions on embeddingsϕ⁡\(s\)\\phi\(s\)rather than full states\. Since each modification introduces at mostϵNLI\\epsilon\_\{\\text\{NLI\}\}andϵϕ\\epsilon\_\{\\phi\}error respectively in the per\-step cost, while the discounted recursive term is shared, we have for any functionUUand any state pair\(s\(i\),s\(j\)\)\(s^\{\(i\)\},s^\{\(j\)\}\):

\|\(𝒯​U\)​\(s\(i\),s\(j\)\)−\(𝒯~​U\)​\(s\(i\),s\(j\)\)\|≤ϵϕ\+ϵNLI\.\|\(\\mathcal\{T\}U\)\(s^\{\(i\)\},s^\{\(j\)\}\)\-\(\\tilde\{\\mathcal\{T\}\}U\)\(s^\{\(i\)\},s^\{\(j\)\}\)\|\\leq\\epsilon\_\{\\phi\}\+\\epsilon\_\{\\text\{NLI\}\}\.Both operators areγ\\gamma\-contractions \(since only the per\-step cost differs, not the discount structure\)\. LetU∗U^\{\*\}andU~∗\\tilde\{U\}^\{\*\}be their respective fixed points\. Evaluating atU∗U^\{\*\}:

𝒯~​U∗=𝒯~​U∗−𝒯​U∗\+U∗,\\tilde\{\\mathcal\{T\}\}U^\{\*\}=\\tilde\{\\mathcal\{T\}\}U^\{\*\}\-\\mathcal\{T\}U^\{\*\}\+U^\{\*\},so‖𝒯~​U∗−U∗‖∞≤ϵϕ\+ϵNLI\\\|\\tilde\{\\mathcal\{T\}\}U^\{\*\}\-U^\{\*\}\\\|\_\{\\infty\}\\leq\\epsilon\_\{\\phi\}\+\\epsilon\_\{\\text\{NLI\}\}\. Applying𝒯~\\tilde\{\\mathcal\{T\}\}repeatedly and using contractivity:

‖U~∗−U∗‖∞=limn→∞‖𝒯~n​U∗−U∗‖∞≤∑k=0∞γk​\(ϵϕ\+ϵNLI\)=ϵϕ\+ϵNLI1−γ\.\\\|\\tilde\{U\}^\{\*\}\-U^\{\*\}\\\|\_\{\\infty\}=\\lim\_\{n\\to\\infty\}\\\|\\tilde\{\\mathcal\{T\}\}^\{n\}U^\{\*\}\-U^\{\*\}\\\|\_\{\\infty\}\\leq\\sum\_\{k=0\}^\{\\infty\}\\gamma^\{k\}\(\\epsilon\_\{\\phi\}\+\\epsilon\_\{\\text\{NLI\}\}\)=\\frac\{\\epsilon\_\{\\phi\}\+\\epsilon\_\{\\text\{NLI\}\}\}\{1\-\\gamma\}\.SinceU^θ\\hat\{U\}\_\{\\theta\}is trained to approximateU~∗\\tilde\{U\}^\{\*\}, the bound follows\. ∎

Forγ=0\.8\\gamma=0\.8, the amplification factor is1/\(1−γ\)=51/\(1\-\\gamma\)=5, meaning per\-step errors of0\.020\.02each lead to at most0\.20\.2total error\. In practice, we calibrate decision thresholds empirically on held\-out rollouts rather than relying on worst\-case values ofϵϕ\\epsilon\_\{\\phi\}andϵNLI\\epsilon\_\{\\text\{NLI\}\}, since these depend on the specific encoder and NLI model used\.

### A\.3Experimental Setup

We evaluate RSD onτ2\\tau^\{2\}\-bench\[[Barres et al\., 2025](https://arxiv.org/html/2610.33012#bib.bib1)\], and ToolSandbox\[[Lu et al\., 2024](https://arxiv.org/html/2610.33012#bib.bib16)\]to measure whether the learned metric captures trajectory\-level consistency and if it can serve as a reward signal for improving consistency during fine\-tuning\.τ2\\tau^\{2\}\-bench contains scenarios related to airline customer service agent, while ToolSandbox comprises general\-purpose tasks spanning diverse domains, including calendar management and web search\. For each benchmark, we run 8 independent trials across 8 test samples \(64 trajectories\) in total for Qwen\-2\.5 models \(3B and 7B parameters\)\[[Team, 2024](https://arxiv.org/html/2610.33012#bib.bib20)\], where each trajectory consists of interleaved user messages, agent actions \(including tool calls\), and tool outputs\.

#### A\.3\.1RSD Training

We construct the training set by generating multiple rollouts using temperature set to 1\. Forτ2\\tau^\{2\}\-bench we collectM=30M=30independent rollouts from1313task instances, and for ToolSandbox we collectM=8M=8independent rollouts from2929task instances\. From the resulting trajectories, we extract state\-action transition as described in[Section4\.1](https://arxiv.org/html/2610.33012#S4.SS1)\. Each statests\_\{t\}consists of the full interaction history up to timesteptt, i\.e,\(o0,a0,o1,a1,…,ot−1,at−1,ot\)\(o\_\{0\},a\_\{0\},o\_\{1\},a\_\{1\},\\ldots,o\_\{t\-1\},a\_\{t\-1\},o\_\{t\}\), where observations include user messages and tool outputs, and actions include agent responses and tool calls\.

We adopt the MICo parameterization from[Equation2](https://arxiv.org/html/2610.33012#S3.E2), wherezsz^\{s\}is computed using a frozen Cohere embed\-v4\-0 and mapped through a 3\-layer MLP into a 256\-dimensional latent space\. The network is trained to satisfy[Equation6](https://arxiv.org/html/2610.33012#S4.E6)usingn=3n=3TD steps andγ=0\.8\\gamma=0\.8\. To compute pairwise NLI relations between actions, we use gpt\-4\.1 to label each pair as entailment, contraction or neutral, which are then mapped to scores as defined in[Definition1](https://arxiv.org/html/2610.33012#Thmdefinition1)\. The trained models are then used as reward signals to finetune different models\. Refer to[Algorithm1](https://arxiv.org/html/2610.33012#alg1)for more detail on the training algorithm\.

#### A\.3\.2Baselines

We compare RSD against three classes of methods:

Token\-level entropy\[[Malinin and Gales, 2020](https://arxiv.org/html/2610.33012#bib.bib17)\]: We compute the average token\-level entropy across all tokens in the agent’s response at each turn\. This provides a measure of uncertainty at the token generation level but does not capture semantic consistency across multiple turns\.

Semantic entropy\[[Kuhn et al\., 2023](https://arxiv.org/html/2610.33012#bib.bib13)\]: We cluster agent responses using bidirectional NLI entailment to identify semantic equivalence classes, then compute the entropy over these clusters\. Unlike token entropy, this captures semantic variation, but only at single\-response granularity without considering future trajectory divergence\.

Supervised fine\-tuning \(SFT\): We fine\-tune the base Qwen\-2\.5 models on expert trajectories from both benchmarks using next\-token prediction\. This provides a baseline that improves task success through supervised learning but does not explicitly optimize for consistency\.

For token entropy, semantic entropy, and RSD, we fine\-tune the base models using Group Relative Policy Optimization \(GRPO\)\[[Shao et al\., 2024](https://arxiv.org/html/2610.33012#bib.bib18)\], using each metric as a reward signal\. We minimize token and semantic entropy via negative entropy rewards, and minimize RSD self\-distance−U^θ​\(s,s\)\-\\hat\{U\}\_\{\\theta\}\(s,s\)\. All methods use the same base models \(Qwen\-2\.5\-3B and Qwen\-2\.5\-7B\), share GRPO hyperparameters, and are evaluated under identical trajectory collection settings with 8 trials per task for a fair comparison\.

#### A\.3\.3Evaluation Metrics

We adopt the evaluation framework from[Chong et al\. \[2026\]](https://arxiv.org/html/2610.33012#bib.bib5)to evaluate the agent behaviour, as it captures both intermediate progress and final outcomes\. We report two task performance metrics, area under the progress curve \(AUC\) which measures how quickly the agent makes progress, and the final progress rate\.

To measure behavioral consistency, we compute the coefficient of variation \(CV =σ/μ\\sigma/\\mu\) of performance metrics across 8 independent trials per task, where a lower CV indicates more consistent behavior\. To ensure a fair comparison across models, we restrict evaluation to the intersection of samples where all models within a size group achieve non\-zero mean AUC\. This avoids undefined CV whereμ=0\\mu=0, and also prevents models outputting trivial solutions from appearing more consistent\. This guarantees that every model is evaluated on identical samples where it demonstrates at least partial task engagement\. Additionally, we report pass@k and pass^kkmetrics\[[Yao et al\., 2024](https://arxiv.org/html/2610.33012#bib.bib27),[Barres et al\., 2025](https://arxiv.org/html/2610.33012#bib.bib1)\]\. For inference, we set the temperature to 0\.