Unsupervised Evaluation of Multi-Turn Objective-Driven Interactions

AI summary

Overview

Research area: Machine learning / large language model evaluation, with a focus on enterprise AI agents and multi-turn task-oriented dialogue.

Technical level: Advanced. The paper combines unsupervised clustering, LoRA fine-tuning of small open-weight language models, and a probabilistic treatment of token-sequence distributions. The prose is readable, but the methodology assumes familiarity with embeddings, k-means, log probabilities, and supervised fine-tuning.

Scope: The paper introduces three label-free metrics — goal labeling, interaction completeness, and response uncertainty — for evaluating multi-turn, objective-driven human–LLM interactions without human annotation or ground-truth "ideal" responses.

What This Paper Is About

Enterprise LLM systems (customer service agents, coding assistants, tool-using agents) produce long, complex multi-turn conversations that are hard to evaluate: data is unlabeled, human annotation does not scale, custom metrics only catch errors someone already anticipated, and LLM judges are unreliable and biased. The authors build the first set of unsupervised metrics for these objective-driven interactions, relying on statistical properties of unlabeled interaction data and fine-tuned small models that adapt to distributional shifts.

Key Contributions

1. LLM-guided clustering. A new algorithm that combines k-means with LLM language understanding to discover an unspecified number of labeled clusters from unlabeled interactions, producing stable and interpretable goal categories where an LLM-only labeling baseline is unstable.

2. Completion labeling without labels. A method that fine-tunes a small completion model (LoRA adapter on a LLaMA3.2-8B completion model) to approximate a distribution in which complete interactions end with a special end tag, so that a complete conversation yields end and an incomplete one yields the remaining turns — which also summarizes the tasks the system failed to finish.

3. Response trees for uncertainty. A graph-based approximation of the conditional response distribution P(r | p = p) that enumerates all branches reachable with probability ≥ α, giving an overview of divergent possible answers without repeated high-temperature sampling, and quantifying uncertainty via the number of leaf nodes and the max log probability.

4. Validation on open-domain and task-specific data, showing that an 8B fine-tuned model can match or exceed a 70B LLM judge on completion labeling, and that the response-tree statistics are not merely artifacts of conversation length.

Main Findings

• Clustering stability is dataset-dependent. For all datasets except Code-Feedback and Insurance, the LLM-guided clustering algorithm produces highly stable clusters across runs. The authors attribute the instability on those two datasets to them containing multiple topics (Insurance could be labeled by underwriting task or by type of business; Code-Feedback by question type or programming language). The baseline that prompts OpenAI's GPT-4.1 to label each sample is unstable and produces different clusters based on the order of the data; on WebShop it collapses to a single cluster, "Online Shopping and Purchase."

• Cluster sizes reflect topic breadth. LMSYS, Code-Feedback, and KB+OS+SQL exhibit many small data clusters, while Insurance and WebShop contain a smaller number of labels. Cluster visualizations are reported for the top 10 largest clusters.

• Completion labeling beats a 70B judge on several datasets. On SQL + OS + KB, the fine-tuned 8B model reaches accuracy 0.98, precision 0.99, recall 0.98, F1 0.99 versus the LLaMA 70B judge's 0.97, 0.96, 0.97, 0.96. On WebShop the fine-tuned 8B model reaches 0.92 accuracy, 0.89 precision, 1.0 recall, 0.94 F1 versus the 70B judge's 0.92, 1.0, 0.83, 0.91. On Insurance, fine-tuned 8B reaches 0.91, 0.94, 0.87, 0.91 versus the 70B judge's 0.95, 1.0, 0.91, 0.95.

• The method generalizes to unstructured chat. On the LMSYS subsample, an 8B completion model with a short prompt reaches 0.74 accuracy, 0.79 precision, 0.85 recall, 0.82 F1, compared with the LLaMA 70B judge's 0.43, 0.77, 0.25, 0.38.

• Code-Feedback is a failure case for completion labeling. No method performs well there; the fine-tuned 8B model drops to 0.47 accuracy, 0.71 precision, 0.12 recall, 0.21 F1, versus the 70B judge's 0.53, 0.53, 0.46, 0.49 and the non-fine-tuned 8B completion model's 0.59, 0.56, 0.84, 0.67. The authors explain that many samples contain a programming problem answered in the first turn with follow-up questions afterward, so there is no well-defined end.

• Insurance shows inconsistent fine-tuned performance, which the authors attribute to the small training dataset (50% of 380 samples) and the complexity of insurance underwriting, compared with WebShop (351 samples but a simpler format) and SQL+OS+KB (1043 samples).

• The end tag ablation confirms necessity. Fine-tuning on Insurance without the end tag degrades results to 0.70 accuracy, 0.66 precision, 0.79 recall, 0.72 F1.

• Uncertainty is highest on tool-heavy data. Despite fine-tuning, models exhibit high uncertainty (measured by number of response-tree leaf nodes and max logprob) on KB+OS+SQL and Insurance, with KB+OS+SQL being most challenging because it is highly dissimilar from the base chat distribution due to tool calls, SQL, terminal interactions, and tool output. Models show higher confidence on LMSYS and Code-Feedback, reflected by high max logprob.

• Response-tree statistics are not just length proxies. Correlations between max logprob and conversation length are -0.11 (LMSYS), -0.19 (Code-Feedback), -0.25 (Insurance), 0.16 (WebShop), 0.41 (KB+OS+SQL); between max logprob and leaf nodes, -0.49, -0.46, -0.10, -0.19, and -0.06 respectively.

• No ground-truth labels exist for the presence of errors, LLM uncertainty, or sample dissimilarity from the dataset's token distribution, so the response tree and its statistics are presented as quantifying the empirical distribution of P(r | p = p) rather than as accuracy scores.

Methodology in Plain English

The authors assume each interaction contains exactly one user goal, and that in a majority of interactions the user completes that goal — so failures are rare and hard to spot by inspection.

Goal labeling (LLM-guided clustering). First, an LLM summarizes each interaction's user goal as free-form text (optionally with a short application-context paragraph for specialized domains). These summaries are embedded with OpenAI's text-embedding-3-small into 1536-dimensional vectors. k-means produces an overestimate of k₁ clusters; the LLM labels each cluster by seeing ten summaries inside the cluster and ten outside it. The cluster descriptions are then embedded, and a cosine-similarity matrix D is built over the descriptions. Iteratively, the algorithm takes the most similar pair and asks the LLM whether to merge them (ten samples from each cluster plus ten from other clusters) — this is the only point where an LLM makes a clustering decision. The process ends when all clusters fail to merge, yielding cluster labels, text descriptions, and assignments.

Completion labeling. The authors define a modified distribution D′ in which the last response of each conversation carries a special end tag. If a conversation is complete, the most likely next token sequence is end; if incomplete, the expected output is additional turns representing remaining tasks. In practice they approximate D′ with a LoRA adapter trained on a tagged, unlabeled dataset where most interactions are complete (so incomplete ones are outliers), using LLaMA3.2-8B as the base completion model — LoRA with supervised fine-tuning, 3 epochs, AdamW 8-bit optimizer, learning rate 0.0002, weight decay 0.01, and a 50% train / 50% unseen test split per dataset. Four models are fine-tuned from a base LLaMA3-8B-Completion model, with input concat(p₁, r₁, …, pₙ) and desired output rₙ. Datasets that do not require fine-tuning are handled by prompting LLaMA3.1-8B-Instruct. The deliberate choice of small models shows that evaluation does not require large models, as earlier LLM-as-a-judge techniques did.

Uncertainty. A response tree enumerates all branches of the conditional response distribution reachable with probability ≥ α, rather than repeatedly sampling at high temperature. More leaves imply more divergent possible answers, which in turn suggests a higher chance the model picks a wrong one; human inspection of the tree also reveals the nature of possible errors.

Evaluation data. LMSYS-Chat-1M (1000 samples, unstructured human–LLM chats, no objective-driven or tool use), Code-Feedback (1000, code generation, objective-driven), Insurance (380, underwriting, tool use), WebShop (351, shopping, tool use), SQL (537), OS (195), KB (311) — the last three are Agent-FLAN subsets combined to represent an agent with multiple technical skills. Incomplete samples are manufactured by truncating an n-turn interaction at a random integer in 1, …, n−1. For LMSYS, 100 samples were annotated to serve as ground-truth labels; the GPT-4.1 clustering baseline was run on a 250-sample subset of each dataset.

Why This Matters

Impact on research. The paper reframes LLM evaluation as statistical inference over unlabeled interaction data rather than comparison against human references or subjective LLM judging. It contributes a reusable LLM-guided clustering algorithm for text, a "fine-tuned LLM as a model of a token distribution" framework, and the response tree as an approximate representation of P(r | p = p). It also sidesteps documented judge pathologies the paper catalogs — position bias, verbosity bias, familiarity bias (preference for lower-perplexity outputs), inconsistent outputs, and sensitivity to prompt wording — as well as the cost of human annotation, illustrated by HelpSteer's 200 annotators labeling 37,120 prompt-response pairs and HelpSteer3's over 7,000 annotators producing feedback on 40,500 multi-turn conversations.

Real-world applications:

• Customer service and enterprise agent monitoring: automatically discovering what users are trying to accomplish and which requests the system fails to finish, without building a custom metric for each anticipated failure mode.
• Coding and tool-using assistants: surfacing upstream distribution shift — the KB+OS+SQL setting, with tool calls, SQL, and terminal output, is where models were the least confident.
• Online intervention and escalation: uncertainty signals can trigger a request for human assistance before errors compound and tokens are wasted.
• Compute savings and orchestration: a small LLM could monitor a larger LLM's output, detect when an interaction is likely complete, and prompt the larger model to finish.
• Failure-mode discovery: because incomplete interactions generate the model's guess at the remaining turns, the method yields a natural-language summary of the kinds of tasks the system does not complete.

Industry relevance. The metrics are explicitly aimed at enterprise AI developers for whom objective-driven interaction data is not publicly available, and the ablation results show that small 8B models can match or exceed 70B judges — relevant when evaluation must run cheaply and continuously.

Future Directions

• Statistical properties of the fine-tuning approach. How does the distance between the base pretraining distribution and the fine-tuning distribution affect performance? How does fine-tuning dataset size affect completion-labeling performance? Can statistical guarantees be established?
• Extensions of the response tree. If the LLM's sampling strategy is known, one could establish a guarantee on the probability of producing a given output by inspecting the tree; one could even train the model against the whole tree rather than one sampled branch.
• Multiclass classification for clustering. The current approach does not perform multiclass classification; extending it would likely help on datasets such as Code-Feedback and Insurance that contain multiple overlapping topics.
• Making completion labeling robust to follow-up-only goals. The method currently relies on structure in the interaction and fails when the user's goal is completed in the first turn and later turns are follow-up questions.

The paper also notes open design constraints: the summarization prompt (which can be tuned to focus on desired attributes of the interaction) and the initial number of clusters k₁, which caps how many clusters can ever be discovered. The software implementation of the metrics is stated to appear in the final version of the paper, and the response-tree generation procedure is deferred to Appendix B.

Target Audience

Machine learning engineers and researchers building or evaluating enterprise conversational agents, particularly those who need scalable quality monitoring without labeled data or human annotation. It is also relevant to practitioners of LLM-as-a-judge who want a lower-cost, judge-free alternative, to researchers interested in unsupervised anomaly detection over text, and to teams working with tool-using or multi-agent systems where distributional shift from base chat data is a central concern. Readers should be comfortable with clustering, embeddings, LoRA fine-tuning, and probabilistic notions of LLM uncertainty.

Authors’ abstract

Large language models (LLMs) have seen increasing popularity in enterprise applications where AI agents and humans engage in objective-driven interactions. However, these systems are difficult to evaluate: data may be complex and unlabeled; human annotation is often impractical at scale; custom metrics can monitor for specific errors, but not previously-undetected ones; and LLM judges can produce unreliable results. We introduce the first set of unsupervised metrics for objective-driven interactions, leveraging statistical properties of unlabeled interaction data and using fine-tuned LLMs to adapt to distributional shifts. We develop metrics for labeling user goals, measuring goal completion, and quantifying LLM uncertainty without grounding evaluations in human-generated ideal responses. Our approach is validated on open-domain and task-specific interaction data.