# SKG-Eval: Stateful Evaluation of Multi-Turn Dialogue via Incremental Semantic Knowledge Graphs

arXiv: https://arxiv.org/abs/2605.16650 · HTML: https://mlsanity.com/paper/2605.16650/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 15 of its 21 references that are in the map.
- First posted on arXiv 15 May 2026.

## Builds on (most cited first, 15 of 15)

- [Judging LLM-as-a-Judge with MT-Bench and Chatbot Arena](https://mlsanity.com/paper/2306.05685/) (2023)
- [LLMs Get Lost In Multi-Turn Conversation](https://mlsanity.com/paper/2505.06120/) (2025)
- [MINT: Evaluating LLMs in Multi-turn Interaction with Tools and Language Feedback](https://mlsanity.com/paper/2309.10691/) (2023)
- [MultiChallenge: A Realistic Multi-Turn Conversation Evaluation Benchmark Challenging to Frontier LLMs](https://mlsanity.com/paper/2501.17399/) (2025)
- [LLM-Eval: Unified Multi-Dimensional Automatic Evaluation for Open-Domain Conversations with Large Language Models](https://mlsanity.com/paper/2305.13711/) (2023)
- [MT-Eval: A Multi-Turn Capabilities Evaluation Benchmark for Large Language Models](https://mlsanity.com/paper/2401.16745/) (2024)
- [Beyond Single-Turn: A Survey on Multi-Turn Interactions with Large Language Models](https://mlsanity.com/paper/2504.04717/) (2025)
- [Evaluating LLM-based Agents for Multi-Turn Conversations: A Survey](https://mlsanity.com/paper/2503.22458/) (2025)
- [KGGen: Extracting Knowledge Graphs from Plain Text with Language Models](https://mlsanity.com/paper/2502.09956/) (2025)
- [A Comprehensive Analysis of the Effectiveness of Large Language Models as Automatic Dialogue Evaluators](https://mlsanity.com/paper/2312.15407/) (2023)
- [BotChat: Evaluating LLMs' Capabilities of Having Multi-Turn Dialogues](https://mlsanity.com/paper/2310.13650/) (2023)
- [PsycoLLM: Enhancing LLM for Psychological Understanding and Evaluation](https://mlsanity.com/paper/2407.05721/) (2024)
- [An Automatic Evaluation Framework for Multi-turn Medical Consultations Capabilities of Large Language Models](https://mlsanity.com/paper/2309.02077/) (2023)
- [ECoh: Turn-level Coherence Evaluation for Multilingual Dialogues](https://mlsanity.com/paper/2407.11660/) (2024)
- [Consistency of Large Reasoning Models Under Multi-Turn Attacks](https://mlsanity.com/paper/2602.13093/) (2026)

## Abstract (arXiv)

Evaluating multi-turn dialogue systems remains challenging because response quality depends not only on the current prompt, but also on previously established entities, claims, and conversational commitments. Existing automatic evaluators, including LLM-as-a-judge frameworks and embedding-based metrics, largely rely on flat or turn-isolated representations, making them less effective at detecting long-range issues such as contradiction, topic drift, and entity inconsistency. To address this, we propose SKG-Eval, a quasi-deterministic and interpretable framework that models dialogue as an evolving Semantic Knowledge Graph (SKG) of entities, relations, and commitments across turns. The framework incrementally updates the graph through structured triple extraction and computes three complementary signals: (i) local relevance, measuring alignment with the current prompt and optional reference; (ii) historical consistency, evaluating how newly introduced information connects to prior conversational context using graph-based and embedding-driven signals; and (iii) logical coherence, assessed by a geometric contradiction engine that detects cross-turn conflicts without relying on NLI models or LLM judges. These signals are adaptively fused and aggregated into a length-invariant session score via recency-weighted trend analysis. Across multiple benchmarks, SKG-Eval achieves higher correlation with human judgments and substantially improves detection of long-range inconsistencies in extended conversations. In addition, the framework produces explicit contradiction certificates and deterministic scores for fixed inputs, enabling reproducible and auditable evaluation. Overall, our results suggest that structured externalized state tracking through semantic knowledge graphs provides a scalable alternative to implicit reasoning in LLM-based dialogue evaluators.