Stale Turns: Session-Level Dialogue Evaluation as Graph Segment Training

Dialogue systems are usually evaluated offline by replaying recorded conversations. The system under test writes its own reply at each turn, and the recorded human reply comes next. Once the system says something different from the original agent, every later human turn is answering a conversation that no longer exists. The damage is large. On MultiWOZ 2.1, corpus-based success scores correlate negatively (−0.460) with human success ratings (Dialogue Evaluation with Offline Reinforcement Learning). This note proposes treating those out-of-date human turns the way large-graph learning treats out-of-date cached embeddings. The idea is to recognize that they are stale, measure how stale each one is, and train the evaluator to rely on them in proportion to how current they still are.

The method comes from graph segment training (Learning Large Graph Property Prediction via Graph Segment Training). That work predicts a property of a whole giant graph by splitting the graph into segments. Only some segments are encoded at each step. The rest are read from a table of embeddings computed earlier with older weights. Two fixes correct for that staleness: randomly dropping cached embeddings during training, and refitting only the final prediction head once the cache has been refreshed. A replayed dialogue has the same shape. It is a session-level property (did the task succeed, would a human rate it well) computed from segments, where some segments are fresh (the system's own turns) and some are stale (recorded user turns conditioned on a past that has since changed). The difference from the graph case is that in dialogue the staleness can be measured turn by turn. That gives a principled schedule for dropping stale segments where graph segment training used a uniform drop rate.

Core Claim

A session-level evaluator does better when it is trained to predict the outcome of a fresh interaction from a stale replay, with each recorded segment dropped with a probability that rises with its measured context drift. Such an evaluator should agree with human session judgments more closely than corpus-based scoring and the offline reinforcement-learning critic. Its advantage should grow with how far the system under test departs from the recorded transcripts. The new element is the staleness-indexed treatment of recorded turns. Prior evaluators either ignore staleness, replace the replay entirely (critics, simulators), or score single turns where staleness never arises.

Positioning Against Prior Work

The dialogue literature supplies the motivation. Lubis et al. document the context-mismatch failure. They respond by learning an offline value critic over a latent action space, which reaches a 0.755 correlation with human success. Their critic scores the agent's trajectory but does not reason about which parts of the replayed evidence remain valid. We keep the replay and model its validity. ChatChecker removes staleness by generating fresh user turns with LLM-driven personas, including uncooperative ones. Its conversation-level rating reaches ρ = 0.683 on FED-Dial. We use simulation only to create training targets, not as the evaluation itself.

Turn-level coherence metrics are a second group. GRADE reasons over small ConceptNet subgraphs per context-response pair. QuantiDCE uses a ranking-trained text encoder that beats GRADE by about 5% in correlation without any graph. FlowEval compares dialogue-act sequences against retrieved human consensus. All three score a turn or a flow in isolation, so the question of which recorded evidence is out of date never comes up. QuantiDCE also constrains this proposal. Its result suggests explicit graph machinery is not needed for turn-level coherence, so we make no claim that graph structure helps there. The graph view matters here only because session evaluation is a whole-graph prediction built from segments.

Conversation Graph supplies a component. It merges dialogues into a state-transition graph over belief states and system actions and trains against all valid outgoing actions. That gives a way to tell whether an agent's deviating action is still an accepted continuation from the same state, which feeds our staleness measure.

On the graph side, graph segment training supplies the method: segment encoders, a historical embedding table, stale embedding dropout, and prediction-head finetuning. Cluster-GCN motivates restoring links between sampled clusters so that cuts do not sever dependencies. In our setting, this becomes keeping edges between segments that share dialogue-state slots. We do not claim a GPU memory problem in dialogue. Sessions are small, and the comparison of full-graph and mini-batch training in Full-Graph vs. Mini-Batch Training is a reminder that segmenting is a modelling choice with tradeoffs, not a free win. We borrow the staleness logic, not the scalability argument.

Research Program

A session is represented as a small graph. Each node is a segment of one system turn and the following user turn. Edges carry temporal order and slot dependencies, meaning a segment that references a slot set in an earlier one. A shared transformer encodes each segment. A light message-passing layer and a pooling head turn the segment embeddings into a session score.

For a replay in which the system under test produced turn $t$ and the recorded transcript continues, each later recorded user segment $k$ is assigned a staleness $s_k \in [0,1]$. This is the accumulated divergence between the system's actual turns and the original recorded system turns before $k$. It combines two measurements: whether the deviating action is an accepted outgoing edge at the same Conversation Graph state (zero cost if so), and the belief-state mismatch the deviation induces. During training, segment $k$'s embedding is dropped with probability

$$p_k = p_{\max}\,\sigma\big(\alpha (s_k - \tau)\big),$$

where $\sigma$ is the logistic function, $p_{\max}$ caps the drop rate, and $\alpha,\tau$ set how sharply dropping begins as drift grows. With $\alpha = 0$ this reduces to graph segment training's uniform stale dropout, which is the key ablation.

The training target is what makes this more than reweighting. For each human MultiWOZ dialogue, we create deviating replays by substituting system turns from a set of agents of varying quality. We then run the same agents fresh against an LLM user simulator from the same starting goal and record task success under live interaction. The evaluator sees only the stale replay and must predict the fresh outcome. Following graph segment training's last step and QuantiDCE's small-data fine-tuning, we freeze the segment encoder and refit only the session head on a small set of human-rated sessions. This keeps simulator biases from defining the final score. The human ratings come from the protocol of Lubis et al. If their annotations cannot be obtained, we collect a comparable set.

Baselines

The naive reference point is corpus-based success computed on the replay, which the file reports at −0.460 correlation with human success on MultiWOZ 2.1. Close to it is truncation scoring, which judges only the turns before the first deviation; it shows how much signal is lost by discarding stale evidence altogether.

The strongest existing method is the offline RL critic of Lubis et al.. It reports a correlation of 0.755 with human success judgments on MultiWOZ 2.1. It is the strongest competitor because it targets exactly the same failure on the same benchmark. We will retrain it on the same dialogues and agent pool, with the same human-rated finetuning set given to it as a calibration step and a matched hyperparameter search. Beating it means a higher correlation on held-out agents across three seeds, with non-overlapping bootstrap intervals.

A third baseline is simulator-only evaluation: score each agent by its success against the same LLM simulator used for our targets, in the style of ChatChecker. It has no staleness by construction. It is a threat whenever the simulator is faithful.

Two ablations isolate the key ingredient. The first is the same architecture and targets with no dropout. The second is uniform dropout with the average drop rate matched to the staleness schedule, which is the direct transfer from graph segment training. If uniform dropout matches the schedule, the staleness measure contributes nothing and the claim fails.

Why not just…?

Why not just evaluate everything with a user simulator and skip replays? This is the most serious alternative. Simulators remove context mismatch entirely. ChatChecker's own numbers show they behave differently by persona: uncooperative personas cause nearly twice the breakdowns per turn (0.23 vs 0.13). So the ranking of agents depends on which simulator you pick, and recorded human user behaviour is real evidence we would be throwing away. The simulator-only baseline settles this. If it matches our method's correlation with human ratings, then replays add nothing and we would report that.

Why not just use the offline RL critic? It already reaches 0.755. But it learns the value of the agent's actions without any notion that later recorded user turns lose validity at different rates. Our prediction is specific: the gap between the two methods should widen as agents deviate more from the transcripts. We test this by binning held-out agents by deviation rate. If the gap stays flat, the critic is sufficient.

Why not just feed the whole replay to a long-context evaluator and let it figure out staleness? Nothing in such a model tells it which recorded turns respond to a past that no longer exists. That is the same reason replayed corpus success fails. Our no-dropout ablation is exactly this model with identical targets and capacity. If it matches the full method, the staleness machinery is unnecessary.

Proposed Experiments

The main experiment is on MultiWOZ 2.1. We use a pool of policies including supervised, augmented, and reinforcement-trained agents such as the Conversation Graph agent (whose augmentation raised MultiWOZ 2.0 success from 73.4% to 79.8%). Agents are held out across splits so the evaluator never sees the system it scores. Metrics are Pearson and Spearman correlation with human session success, plus agreement on pairwise agent rankings.

The first decisive check is the deviation-binned analysis described above. The second is the matched-rate comparison of staleness-indexed and uniform dropout. The third tests robustness: we swap in a different simulator for generating training targets than the one used in the simulator-only baseline, to show the evaluator is not just copying one simulator.

As a secondary transfer test, we apply the same recipe to open-domain sessions on FED-Dial, comparing against ChatChecker's ρ = 0.683. Staleness there is measured with dialogue-act divergence of the kind FlowEval annotates, since belief states do not exist in chit-chat. We will also check STAR task flows, where FuDGE gives a flow-alignment distance as an alternative staleness signal. No reported session-level correlation was found on Lacuna for STAR, so that comparison is exploratory.

The proposal is falsified if, on MultiWOZ 2.1, the method fails to beat the retrained offline critic, or fails to beat uniform dropout at matched rate.