acceptodds
Under review as a conference paper at ICLR 2027

Trace-MT: A Coverage-Guided Benchmark for Evaluating Complex Multi-Turn Dialogues

Abstract

Multi-turn conversations between real users and LLMs often exhibit complex and diverse behaviors such as interleaving, loops, and interruptions. Such behaviors make every response contingent on the conversational state accumulated over all prior interactions, yielding a combinatorial space of state dependencies that existing single-turn evaluations cannot capture. In this paper, we introduce Trace-MT—to the best of our knowledge, the first coverage-guided benchmark for evaluating complex user behaviors in multi-turn dialogues. Similar to a control-flow graph, we formalize a multi-turn dialogue as a dialogue-flow graph, where each node is a task (totally 6 types of tasks) and each edge denotes the transition taken in response to the source task. As such, we can leverage the concept of coverage, which has been widely used in control-flow testing, for evaluating complex multi-turn dialogues. To avoid exponential explosion as the number of turns increases, we define an N-gram on such dialogue-flow graphs as a sequence of N nodes. We set (equal to the number of task types) and, by enumerating all candidate traces and applying pruning algorithms, obtain a set of 472 specific traces. By selecting one topic to cover each trace, we build a benchmark of 472 coverage-guided tests, where the instructions for simulating user responses are dynamically generated from each trace. The benchmark results on nine open-weight models reveal interesting findings and demonstrate the usefulness of the proposed benchmark.

Primary area:
datasets and benchmarks
Keywords:
multi-turn dialogue, LLM evaluation, benchmark, coverage testing, dialogue behavior space, emergent degradation

Reviews

Among:
Shape:
1234this paper, Bottom 2%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.33 over 3 reviews, above 2% of the others.
Reviewer_4b8hOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

This work constructs Trace‑MT, a multi‑turn dialogue benchmark inspired by software control‑flow testing. It builds dialogue traces via N‑gram coverage‑guided pruning and adopts dynamic simulation with observer logs to achieve both reproducibility and state‑dependent evaluation. Empirical results reveal that strong performance under simple dialogue conditions does not transfer to scenarios with stacked interference.

Critical strengths
  1. This work adapts coverage criteria from software testing to formalize the behavioral space of multi‑turn dialogue, overcomes key drawbacks of static scripted benchmarks and non‑reproducible purely dynamic evaluations.
  2. This work leverages N-gram pruning to maintain the number of target behavior combinations at a manageable scale.
Critical weaknesses
  1. While extensive coverage efforts have been undertaken, the covered behavior combinations may not manifest in real‑world multi‑turn conversations. Specifically, the real‑world occurrence probability of higher‑difficulty combinations remains unclear, which may limit the practical impact of this benchmark for the broader research community.

  2. Difficulty tiers are defined based on interference density within dialogue traces rather than the intrinsic difficulty of seed questions.

Questions for authors
  1. Design choices including category merging during pruning and the selection of the 6‑gram window appear largely empirical. The validity of such pruning operations has not been sufficiently justified.

  2. The figures suffer from small fonts and poor readability. Moreover, all prompts provided in the appendix are written in Chinese, which raises concerns regarding the generalizability of the benchmark.

Reviewer_21o6OpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
1
Soundness
1
Read review
Paper summary

The paper describes a conversation simulator with a set taxonomy of utterance types set up to mimic real life multi-turn conversation. To support more realistic settings the authors derive a set of state transition (likely "hops" from one state to another). These are named traces, and the paper describes a software testing inspired approach to cut down of the number of transitions using a set-cover greedy algorithm. This leaves a manageable number of transitions to check. Then a LLM based (not sure from the prompts if it is a zero or few shot) classifer/generator is used to generate a trace from a given seed (which is paraphrased). The utterances are then scored against a reference free LLM-judge evaluator using a scale 0-100. Authors then explore different models and their performance across different types of traces.

Critical strengths

A controlled state transition is a interesting idea.

Critical weaknesses
  • the algorithm for set coverage does not seem to be deterministic and depends of the seed, and this means that the generated dataset and the results can change
  • the LLMaJ tool is not well defined: the same model is evaluating and setting the rubric, there is only one prompt used on a single model and no sensitivity to prompt changes were reported (this may lead to a situation that specific prompts or models favour some responses)
  • the user study falls short of statistical rigour: no sourcing information, it is not clear which 50 samples are used (and whether they are the full dialogues or single turns), the expert band and the LLMaJ band are different (and the scores between models are often a few pp points apart)
  • crucial parts of the paper are given in the appendix (the user study, the statistical testing)
  • the figures are too small to read even at the 400% magnification on a 24 inch screen
Questions for authors

How was the set of 6 node types derived? What are the effects of choosing any random run of the set coverage algorithm? Was there any prompt ablations run for LLMaJ? Why is there only a single datapoint used for a trace? What are the effects of using a different judge model? How many experts where used, how were they sourced? Why wasn't the expert and the LLMaJ scale set the same? Since the seeds are all in English and generation prompts in another language what are the generated conversations (while this reviewer acknowledges the importance of multilingual support for all models, the primary language of this venue is English and it is difficult to review the text in other languages)?

Reviewer_1PadOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper introduces Trace-MT, a coverage-guided benchmark for evaluating complex user behaviors in multi-turn dialogues. Specifically, the paper represents a dialogue as a dialog-flow graph, where each node denotes a task and each edge represents a response to the source task. The paper then uses an N-gram coverage criterion and coverage-guided pruning to select a compact set of traces that cover the behavior space. The paper evaluates nine open-weight models on the proposed benchmark.

Critical strengths
  1. The paper studies state dependencies in multi-turn dialogues, an important and interesting problem.
  2. The paper provides a comprehensive review of related work.
  3. The paper evaluates four turn types in the experimental section.
Critical weaknesses
  1. The writing lacks clarity in several places, making the paper difficult to follow. For example, the discussion of dynamic simulated evaluations does not clearly explain score variation across runs or the lack of measurable behavior coverage.
  2. Although coverage-guided benchmark construction is presented as the main contribution, the motivation for adopting this approach is not clearly explained.
  3. The constructed benchmark contains 472 paths and 6,537 dialogue turns, but the paper does not explain how the dialogue content is generated and validated. Besides, the human verification only covers 50 instances, which is a relatively small sample for validating an evaluation of more than 6,000 dialogue turns.
  4. The evaluation is limited to nine open-weight models and does not include closed-source models, such as Claude and Gemini.
  5. The figures in the paper are not clear, which affects the presentation.
Questions for authors
  1. What motivates the use of coverage guidance in benchmark construction?
  2. How does Trace-MT address the limitations of existing dynamic simulated evaluations?
  3. How are the 6,537 dialogue turns obtained?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.