1 Introduction↩︎

Task-oriented dialogue (TOD) systems [@Balaraman-Survey-21; @BUDZIANOWSKI-multiWOZ2018; @mctear2020conversational; @qin2023end] play a crucial role in human-computer interaction, facilitating seamless communication between users and machines to perform specific tasks. In recent years, transformer-based neural models have become the core technology behind TODs. In particular, pre-trained large language models (LLMs) allow end-to-end approaches [@bang2023multitask; @lai2023external; @qin2023end] that greatly simplify the development of conversational systems, with respect to more complex component-based pipelines [@young2013pomdp]. However, despite their impressive generative capabilities, it is well known that LLMs exhibit significant limitations in producing outputs that adhere to the requirements of task-specific domains [@cho-etal-2022-know; @ji2022survey]. In a recent study [@labruna2024you] it has been shown that, when asked to generate a dialogue according to a given knowledge base (\(KB\)), as required by TODs, state-of-the-art open source LLMs produce up to 59% of per dialogue disalignments with respect to the underlying KB. Failing to align their outputs with a domain \(KB\), leads to inconsistencies that undermine LLMs reliability in real-world applications.

Figure 1 shows an example of a fragment of a Knowledge Base (three restaurants in a city) and a short TOD dialogue generated by a LLM. There are two hallucinations in this dialogue: first, at turn S1, the system mentions three restaurants serving Spanish food, which is not consistent with the knowledge base, where there are two such restaurants (this is a domain inconsistency). Second, at turn S2, the system introduces a Lebanese restaurant, which, although existing in the \(KB\), it is not coherent with the previous dialogue turns, as a Spanish restaurant would have been expected (this is a dialogic inconsistency). Intuitively, both domain and dialogic inconsistencies need the whole dialogue context in order to be detected: for instance, Lebanese appears inconsistent because the user is looking for a Spanish restaurant since the beginning of the conversation, while considering turn S2 alone would result in a well formed dialogue. In addition, notice that three changes would make the whole dialogue consistent: (i) changing three with two at turn S1; (ii) changing Lebanese with Spanish at turn S2; and (iii) changing Beirut with Taberna at turn S2. Detecting TOD inconsistencies and, if possible, suggesting how to solve them, is the goal of this paper. The novel intuition of the paper is to consider dialogue consistency as a kind of Constraint Satisfaction Problem (CSP [@BRAILSFORD1999557]), under the following working hypothesis: (i) first, dialogue consistency can be modeled with a limited number of domain independent constraints that need to be respected by appropriate linguistic realizations; (ii) such constraints can be well represented to define a CSP, whose allowed solutions can be identified by a CSP solver; (iii) a TOD is consistent if its linguistic realizations belong to the set of solutions allowed by a CSP solver for that dialogue. In the paper, we discuss how dialogue constraints are defined, how they can be extracted and modeled as a CSP, and how to set up an experimental setting where we can empirically prove that a CSP solver can detect inconsistencies in a dialogue and suggest possible changes that make the dialogue consistent.

The contributions of the paper are the following:

• We model TOD consistency as a Constraint Satisfaction Problem (CSP): to the best of our knowledge, this is a fully original approach.

• We set up a reusable experimental setting where TOD consistency can be automatically evaluated against a CSP solver.

• We show that the proposed CSP approach allows for effective detection of inconsistent TODs, achieving an accuracy of 75.9%.

2 Dialogue Consistency as a Constraint Satisfaction Problem↩︎

In this section, we explore the conceptualization of dialogue consistency in the CSP framework. We first describe the fundamental component of a conversational domain (Section 2.1), then we elucidate the various constraints that contribute to dialogue coherence (Section 2.2), encompassing linguistic, dialogic, and domain-based considerations. We finally expound upon the formalization of dialogue constraints as CSPs (Section 2.3), delineating the process of modeling dialogue coherence as a constraint satisfaction task.

2.1 TOD Conversational Domain↩︎

TODs typically need specific knowledge about the conversational domain (e.g., a database of restaurants, a playlist of songs, etc.). As in literature [@henderson-etal-2014-second], we assume a domain ontology providing a schema of the concepts (e.g., Restaurant, Hotel, Movie), a set of slots \(S\) (e.g., Food, Area, Price) for the concepts, and the set of values that each slot can assume (e.g., Expensive, Moderate, and Cheap for the Price slot). Then, a domain knowledge base (\(KB\)) comprises a collection of instances for the ontology concepts, each consisting of \([slot-value]\) pairs, adhering to the domain ontology schema.

2.2 Dialogue Consistency↩︎

A TOD can be considered as a sequence of conversational turns between a user and a system aimed at achieving a specific goal. Within this framework, ensuring the consistency of the dialogue is crucial for effective communication between the user and the system. We consider three types of constraints, which need to be respected for a dialogue to be consistent: linguistic, dialogic and domain constraints. Figure 3 provides a concrete example of how violations of these constraints can lead to inconsistencies, showing a case where the system response contradicts the underlying knowledge base despite a seemingly coherent dialogue flow.

2.2.0.1 Linguistic Constraints.

They are necessary to respect general rules of language, including morpho-syntactic rules (e.g., genre and number agreement) and syntax-based rules (e.g., the correct use of a preposition). For instance, consider the following masked utterance:

The choice of centre as a substitute for the masked token is valid, whereas expensive would not be suitable because the preposition in is rarely used to introduce a price in English.

2.2.0.2 Dialogic Constraints.

They maintain the semantic coherence across successive turns of the dialogue, ensuring that each utterance logically aligns with the preceding context, thereby facilitating a seamless flow of information. As an example, suppose the following masked dialogue turns:

Here both Italian and cheap would be eligible choices from a linguistic point of view, but only Italian would maintain the coherence with the previous turn in the dialogue.

2.2.0.3 Domain Constraints.

They ensure alignment between the dialogue content and the knowledge base of the system, thereby maintaining the dialogue’s alignment with relevant factual information. Consider, for instance, a \(KB\) with the following restaurants:

ID	Name	Area	Food	Price
R1	Mario	east	italian	expens.
R2	Napoli	centre	italian	cheap

And the following piece of masked dialogue:

Then, the only admissible choice for the masked token would be one, as selecting any other number would introduce an inconsistency with the information provided in the \(KB\).

2.3 TOD Consistency as CSP↩︎

A Constraint Satisfaction Problem (CSP) [@BRAILSFORD1999557; @kumar1992algorithms] defines a set of variables, each associated with a finite domain of values, and a set of constraints specifying the allowed combinations of values. A solution is an assignment of values to all variables that satisfies all constraints; if no such assignment exists, the CSP is unsolvable.

We model TOD consistency as a CSP, where variables correspond to dialogue elements to be instantiated (e.g., \(MASK\) tokens), and their domains are derived from the dialogue-specific \(KB\). Constraints capture linguistic, dialogic, and domain requirements (Section 2.2).

Formally, given a dialogue \(d_i\) with variables \(x_1, \ldots, x_n\), domains \(D_1, \ldots, D_n\), and a set of constraints \(\mathcal{C}\), the task is to determine whether there exists an assignment \(A = \{(x_1, a_1), \ldots, (x_n, a_n)\}\) with \(a_i \in D_i\) such that: \[\text{\textit{Satisfies}}(A, C_j) \quad \forall C_j \in \mathcal{C}\] where \(\text{\textit{Satisfies}}(A, C_j)\) indicates whether assignment \(A\) satisfies constraint \(C_j\).

3 Methodology↩︎

This section outlines the process of modeling a TOD as a CSP, and then to assess the dialogue consistency using a CSP solver. The assessment involves three key steps for a \([d, KB]\) pair, where \(d\) is a dialogue and \(KB\) is a Knowledge Base: (1) identification of the variables within the dialogue \(d\) (Section 3.1); (2) definition of dialogue constraints and construction of a CSP solver for the \([d, KB]\) pair (Section 3.2); and (3) application of the CSP solver to determine if the dialogue \(d\) represents a feasible solution with respect to the defined constraints (Section 3.3). These phases of the methodology are illustrated in Figure 2.

3.1 Identifying TOD Variables↩︎

At step 1 (see Figure 2), we consider a TOD \(d\) and a \(KB\) (i.e., a set of entities described by slot-value pairs) related to the conversational domain of the dialogue. We do not assume any particular dependency between \(d\) and \(KB\): \(d\) could be either fully covered by \(KB\) (i.e., all mentions of slot values in \(d\) are present in \(KB\)), only partially covered, or not covered at all. We consider CSP variables all text portions in \(d\) either referring to a slot value in \(KB\) or mentioning amounts of instances in \(KB\). The rationale is that both slot values and instance amounts are elements that better characterize a TOD and are responsible for its consistency. In our example in Figure 1, we will obtain the following variables with their assignments, corresponding to highlighted tokens:

\([x_1 = Spanish]\), \([x_2 = three]\), \([x_3 = Spanish]\), \([x_4 = cheap]\) ... \([x_{11} = Lebanese]\).

3.2 Defining TOD Constraints↩︎

We have established a set \(\mathcal{X}\) of variables \(x_1, x_2, ..., x_n\), where each variable \(x_i\) can assume a value either from the slot values or from amounts of instances in \(KB\). Moving to step 2 in Figure 2, we now define the set of constraints \(\mathcal{C}\) over the values that can be assigned to \(\mathcal{X}\) variables. We consider the three categories of constraints introduced in Section 2.2: linguistic, dialogic, and domain-based constraints, and for each category we define a set of domain independent patterns, which are then instantiated as actual constraints on a TOD.

3.2.0.1 Patterns for linguistic constraints.

We model linguistic constraints as the need for a variable derived from a slot value to match the semantic type of its slot type. For instance, given the utterance I am looking for a restaurant at \(x_1\), the value of the variable \(x_1\) must belong to the Area type. More precisely, \(C1\) is defined as follows: \[C1: x_1 \in V\] where \(V\) is the set of values belonging to the same slot type as the original value. Constraint \(C1\), is meant to avoid that a variable can assume values that are semantically non valid. For instance, avoiding that \(x_1\)=north can be assigned to a Food, as in I am looking for a restaurant at indian, which is ungrammatical in English.

3.2.0.2 Patterns for dialogic constraints.

We consider two dialogic constraints. \(C2\) ensures that variables referring to the same slot-name and slot-value in \(d\) are assigned to the same value. \(C3\) ensures that variables with the same semantic type (i.e., same slot-name) occurring in the same utterance are assigned to different values. Given the turn U: I want an \(x_1\) restaurant. S: There are 3 restaurant that serve \(x_2\), we define \(C2\) as follows: \[C_2: x_1 = x_2\]

where the aim is to keep internal coherence across the dialogue turns. Given the utterance We have \(x_1\), \(x_2\), or \(x_3\) restaurants., we define \(C3\) as: \[C_3: x_1 \neq x_2, \quad x_1 \neq x_3, \quad x_2 \neq x_3\]

which captures non redundancy at the utterance level.

3.2.0.3 Patterns for domain-based constraints.

We consider three domain-based constraints. All of them are meant to guarantee consistency between the number of instances mentioned in \(d\) and the actual number of instances present in \(KB\). We distinguish three cases: \(C4\) covers the cases when an utterance in \(d\) states that there are no instances in \(KB\); \(C5\) covers the cases where it is stated that there is at least one instance; and \(C6\) the cases where there are exactly \(n\) instances.

As for \(C4\), consider an utterance indicating no results for a search: There are no restaurants serving \(x_1\) food, assuming that there are no restaurants with [Food=\(x_1\)] in \(KB\). For this utterance, \(C4\) is defined as: \[C4: \neg \exists i \in KB \text{ with values } x_1\] implying that the variable \(x_1\) can not assume a value that is present in an instance of the \(KB\).

As for \(C5\), consider the utterance: We have many \(x_1\) restaurants at \(x_2\), where at least one restaurant with [Food=\(x_1\)] and [Area=\(x_2\)] is supposed to exist in \(KB\). For this utterance, \(C5\) is defined as: \[C5: \exists i \in KB \text{ with values } x_1, x_2\] imposing the existence of at least one instance with values \(x_1\) and \(x_2\). Finally, for \(C6\), consider the utterance There are \(x_1\) restaurants at \(x_2\). We define the constraint as: \[C6: |\{i \in KB \text{ with value }x_2\}| = x_1\] to check that the number of instances with value \(x_2\) is exactly equal to \(x_1\).

To sum up, we have defined six general, domain independent (i.e., in principle they can be applied to any TOD), constraint patterns over the variable of a TOD.

3.3 Assessing Dialogue Consistency↩︎

After identifying all variables and constraints for a dialogue \(d\), a CSP solver computes all possible solutions for the variables in \(d\) based on the knowledge base (\(KB\)) (step 3 in Figure 2). If one of these solutions matches the variable assignments in \(d\), the dialogue is consistent with \(KB\) (step 4 in Figure 2). For example, in Figure 1, the assignment \([x_2 = \text{three}]\) violates \(C6\) (incorrect count of Spanish instances in \(KB\)), while \([x_{11} = \text{Lebanese}]\) violates \(C2\) (lack of coherence with prior turns). If the CSP solver finds at least one solution, the variable assignments in the dialogue must match one of those solutions to ensure all constraints are satisfied. Conversely, if no solution exists with respect to \(KB\), the variable assignments should either remain empty or include values not present in \(KB\) to maintain consistency. When at least one solution is found but none matches the variable assignments, the solver identifies the most similar solution and determines the minimal changes required to make the dialogue consistent. This process provides a detailed report highlighting specific inconsistencies and suggesting corrections.

4 Validating CSP Performance↩︎

We evaluate the ability of the CSP-based approach to detect inconsistencies in task-oriented dialogues (TODs) through a controlled experiment (Figure 2). We construct a balanced dataset of dialogue–knowledge base pairs \([d, KB]\), with equal proportions of consistent and not-consistent instances. Each pair is processed through the pipeline, and the CSP component outputs a binary decision, which is compared against ground truth.

4.1 Experimental Setup↩︎

We construct a balanced dataset of 108 dialogue–KB pairs from MultiWOZ 2.3. While the dataset is assumed to be consistent, manual inspection combined with CSP verification revealed that approximately 10% of dialogues exhibit inconsistencies due to annotation errors; these were removed. The remaining dialogues were split evenly into consistent and not-consistent subsets. Inconsistent dialogues were generated by randomly modifying slot values to violate KB constraints. For each dialogue, a tailored \(KB\) was constructed by selecting relevant entities from the global MultiWOZ knowledge base.

CSP variables are identified either from MultiWOZ annotations or via GPT-4o, and constraints are instantiated using the six patterns introduced in Section 3.2. We model the problem using MiniZinc [@nethercote2007minizinc], a declarative constraint programming language. We use the Chuffed solver [@chu2018chuffed], which is optimized for constraint satisfaction problems and supports efficient search and propagation strategies. The solver determines whether a valid assignment exists; absence of a solution implies inconsistency.

We compare four classification methods: a random baseline, two CSP-based approaches using MultiWOZ annotations (global and local), and a fully automated pipeline using GPT-4o for variable extraction. Performance is measured using accuracy over \([d, KB]\) pairs.

We consider four methods for classifying dialogue consistency:

• Random Baseline: assigns labels randomly (expected accuracy: 50%).

• MWoZ Global + CSP: variables are extracted from full-dialogue annotations and evaluated globally.

• MWoZ Local + CSP: variables are evaluated independently per turn; a single inconsistent turn marks the dialogue as inconsistent.

• GPT-4o Global + CSP: variables are extracted automatically using a two-step prompt chain, then evaluated globally.

The prompt chain used to annotate the dialogue turns consists of the following two prompts:

• Prompt-1: Analyze the given user utterance and extract any slot-value pairs. The possible slot types are: Area, Food, Price, Depart, Destination. Return the output as JSON with the dialog-act format.

• Prompt-2: Refine the given annotation for the user utterance. Ensure that only slots related to Area, Food, and Price are included. Correct any errors in the provided annotation, add missing slots, and remove any irrelevant slots. Return the output as JSON with the updated dialog-act format.

The GPT-4o response to Prompt-1 is used as input within Prompt-2, and the final output is a JSON file containing annotations about slot variables.

The dialog-act referred to in the two prompts is a JSON schema that guides GPT-4o in structured output mode and resembles the MultiWOZ JSON annotation schema.

4pt

4.2 Results↩︎

Table 1 reports the results. The upper-bound method based on MultiWOZ global annotations achieves 91.6% accuracy, confirming the effectiveness of the CSP formulation and the high coverage of the constraint patterns. Performance drops to 79% when constraints are applied locally, highlighting the importance of global context. The end-to-end pipeline using GPT-4o reaches 75.9%, with errors primarily due to imperfect variable extraction. The results show that (i) CSP-based modeling is effective for detecting dialogue inconsistencies, and (ii) the proposed constraint set provides strong coverage of relevant phenomena.

5 Analysing LLM Behavior↩︎

We investigate how large language models (LLMs) handle dialogue consistency under explicit constraints. Specifically, we study (i) their ability to generate consistent TODs, (ii) the role of different constraint types, and (iii) the localization of inconsistency sources.

5.1 Experimental Setup↩︎

We consider 950 MultiWOZ dialogues across multiple domains. Each dialogue is de-lexicalized by replacing slot values with placeholders. Models are then prompted to reconstruct the original dialogue by filling these placeholders using the provided Knowledge Base (\(KB\)), thereby generating a re-lexicalized dialogue.

All models operate in a zero-shot setting without any fine-tuning. Closed-source models are accessed via APIs, while open-source models are run using HuggingFace checkpoints.

The full prompt used in our experiments is reported below.

System Prompt:

You are given an instruction that outlines a task, a Knowledge Base containing domain-specific information, and a dialogue to process.

Your goal is to fill in the [MASK] placeholders in the dialogue using only the information provided in the Knowledge Base.

Task: Replace each [MASK] with the most appropriate value from the Knowledge Base. Preserve the original structure of the dialogue exactly. If a turn does not contain any placeholders, leave it unchanged. Each dialogue turn must start with either User or System. Maintain the original spacing and punctuation (e.g., write “Hi ,” instead of “Hi,”).

Input Format:

[Knowledge Base]

<key-value pairs>

[Dialogue]

User: ...
System: ...
User: ...
...

Output:

The same dialogue with all [MASK] tokens replaced accordingly.

The generated dialogue is then evaluated using the CSP solver to verify constraint satisfaction.

5.1.1 Models↩︎

We evaluate four language models: LLaMA-3.1 8B, GPT-3.5-Turbo, GPT-4o, and GPT-o1. LLaMA-3.1 8B is a large-scale model fine-tuned for handling complex dialogue contexts and maintaining coherence in text generation [@dubey2024llama]. GPT-3.5-Turbo is a model specifically designed for conversational tasks [@achiam2023gpt]. GPT-4o is an advanced language model recognized for its robust performance in various natural language processing tasks [@hurst2024gpt]. GPT-o1 is one of the latest update of the GPT series, designed to reason through complex tasks to solve harder problems¹. All models were prompted with both the de-lexicalized dialogue, \(d_{delex}\), and its associated \(KB\) as input, ensuring a comprehensive context for producing dialogues that adhered to implicit constraints. Inference was conducted in zero-shot mode without fine-tuning, leveraging the respective APIs for closed source models and the huggingface checkpoints for the open ones: GPT-3.5-Turbo (2023-05-15), GPT-4o and GPT-o1 (2024-05-13), and LLaMA-3.1 8B (2023-07-10).

5.1.2 Baselines↩︎

To comparison, we included four non-trivial dialogue re-lexicalization baselines:

• Random-ALL generates a re-lexicalized dialogue \(d_{relex}\) by randomly assigning variables in \(d_{delex}\) to any slot values present in the \(KB\), regardless of their slot type.

• Random-SLOT also assigns variables randomly but restricts the selection to values associated with the same slot type as the original.

• Most Frequent-ALL baseline assigns variables in \(d_{delex}\) to the most frequent slot values found across all slots in the \(KB\).

• Most Frequent-SLOT baseline selects the most frequent value from the same slot type as the original.

5.1.3 Evaluation Metrics↩︎

We use Global Consistency Accuracy (GCA) and Variable Consistency Accuracy (VCA) as the metrics to evaluate the adherence of a dialogue to a specific set of constraints. Given a re-lexicalized dialogue \(d_{relex}\) where CSP variables are assigned to values, GCA measures the overall accuracy of the assignments for each variable. The average GCA is calculated as the proportion of dialogues that fully comply with all defined constraints: \[GCA = \frac{\sum_{i=1}^{N} \left( \prod_{j=1}^{M} \textit{Satisfies}(A_i, C_j) \right)}{N}\] where \(N\) is the total number of dialogues, and \(\textit{Satisfies}(A_i,C_j)\) is a binary indicator function that returns 1 if and only if all variable assignments in dialogue \(d_i\) comply with the constraint \(j\), 0 otherwise. On the other hand, VCA assesses the assignment accuracy on individual variables within the dialogue. We compare the dialogue assignment to the solutions of the CSP solver and find the most similar solution; then, we count how many variable assignments coincide with the assignments of the most similar solution. We formally define VCA as follows: \[VCA = \frac{\sum_{i=1}^{N} \lvert \textit{CorrectAssignments}(d_i) \rvert}{M}\]

where \(N\) is the total number of dialogues, \(M\) is the total number of variables in the dialogues, and \(\textit{CorrectAssignments}(d_i)\) are the variable assignments in dialogue \(d_i\) that coincide with the assignments of the most similar solution provided by the CSP solver. GCA and VCA provide insights into the ability of the dialogue generation system to maintain coherence and fidelity to the underlying domain knowledge while generating responses. Higher values of GCA and VCA indicate better performance in terms of dialogue quality and consistency, unlike traditional dialogue evaluation metrics (e.g., BLEU, ROUGE, or perplexity).

Additionally, the process used for computing VCA can be extended to identify specific errors within a dialogue. In cases where a dialogue is not among the solutions identified by the CSP, the most similar solution can be used to detect erroneous slot-value assignments. Specifically, errors are defined as slot-values that, if corrected, would result in a solution satisfying all constraints. This enables the generation of detailed reports pinpointing the errors in the dialogue, facilitating more targeted improvements.

5.2 Results↩︎

Table 2 shows that GPT-4o and GPT-o1 outperform other models, although absolute performance remains moderate, indicating that constraint satisfaction is still challenging for LLMs. Performance improves as the number of valid CSP solutions increases, suggesting that dialogues with higher flexibility are easier to generate correctly. The constraint analysis (Table 4) highlights the importance of domain-level constraints, particularly \(C6\), in ensuring consistency. These findings indicate that while modern LLMs can partially capture structured constraints, explicit modeling via CSP remains beneficial for enforcing consistency and diagnosing errors.

5.2.1 Ablation Study↩︎

Table 3 presents the results of an ablation study we conducted. The ablation study removes one constraint at a time to measure impact on GCA and VCA. Results indicate that \(C6\) (exact match with KB instances) is the most critical, followed by \(C1\) (hard constraints on slot values).

5.2.2 Additional Results: CSP Solution Distribution↩︎

Table 5 reports the distribution of dialogues based on the number of valid CSP solutions. Dialogues with a higher number of solutions tend to allow more flexibility in variable assignments, which correlates with improved LLM performance.

6 Related Work↩︎

TOD systems have been extensively investigated in NLP [@allen2001architecture]. Recent research has explored the use of neural network architectures for dialogue state tracking [@wu2020gcdst; @zhao2021effective; @labruna2023addressing] and policy learning [@su2016line; @liu2017iterative]. Several metrics have been proposed to assess the performance of TOD systems, including task completion rates, user satisfaction scores, and objective measures for system components, such as precision, recall, and F1-score [@chen2017survey; @santhanam2019towards; @deriu2021survey]. Recent studies have emphasized the importance of holistic evaluation frameworks that consider multiple aspects of dialogue quality [@zhang2021d; @labruna2024you]. Maintaining consistency and coherence in dialogues is essential for effective communication between users and dialogue systems. Previous research has investigated various approaches to ensure dialogue coherence, including coherence modeling  [@cervone2018coherence], and coherence-based response generation [@cervone2020dialogue], aiming to enhance the naturalness and fluency of generated dialogues. Finally, several studies have explored the application of CSPs to language. These include early attempts to ensure coherence in generated text [@kibble2004optimizing], model preposition lexicalization using constraints [@moriceau2004constraint], guide lexical choices through constraints [@mckeown1997floating], and treat context-sensitive utterance generation as a CSP [@popescu2009constraint]. Differently to these works, our approach focuses on detecting inconsistencies in already generated TOD dialogues using CSP.

7 Conclusion↩︎

Generative LLMs may produce inconsistent TODs, due to misalignment between parametric memory and the TOD \(KB\). We have introduced a novel approach to detect TOD inconsistencies based on Constraint Satisfaction. Several experiments demonstrate the feasibility of the approach, enabling to effectively identify and quantify inconsistencies present in TODs with high accuracy (75.9% with GPT-4o and CSP solver). We also analysed the LLM inconsistencies when tasked to re-lexicalize TODs, finding that they primarily concern domain knowledge adherence, resulting in an overall accuracy of only 0.14 at the dialogue level. Our study highlights the potential of CSP-based methodologies in evaluating dialogue consistency and identifying areas for improvement in automated dialogue generation systems. Future research should further explore the application of CSP in task-oriented dialogues and investigate strategies to enhance the coherence of LLM-generated dialogues, particularly in applications with strong domain knowledge requirements.

Limitations↩︎

While the proposed Constraint Satisfaction Problem (CSP)-based approach offers a novel and effective method for detecting inconsistencies in task-oriented dialogues (TODs), it presents several limitations.

The system relies on the explicit mapping of dialogues into variable-constraint representations. Although our method is domain-independent in principle, the process of extracting variables and constraints from dialogues may require customization or adaptation for new domains or dialogue schemas.

Our method focuses on identifying inconsistencies and suggesting minimal changes for correction, but it does not automatically regenerate fluent or user-aligned responses after such modifications. This leaves the generation of corrected natural language utterances as future work.

Finally, although our experimental results are promising, they are based on controlled datasets and manually designed inconsistencies. Further work is needed to assess robustness in more complex or organically generated dialogues.

Ethical Considerations↩︎

Use of Scientific Artifacts. We used publicly available task-oriented dialogue datasets for experimentation. These datasets include MultiWOZ [@BUDZIANOWSKI-multiWOZ2018] and variations based on it. Additionally, we used off-the-shelf large language models (LLMs) to generate new dialogues with intentional inconsistencies for controlled evaluation. All code developed for the CSP-based inconsistency detection pipeline is our original contribution and will be made publicly available for research purposes under an open-source license.

Licensing and Intended Use. All external datasets and models used in this work were employed in accordance with their licenses. Our use was consistent with the intended purpose of the datasets (research), and we explicitly specify that the CSP-based system and associated data artifacts are intended solely for research and educational use. Any derivative dataset created using our framework also inherits this research-only restriction.

Privacy and Data Integrity. The dialogue data used in this study does not include personally identifiable information (PII), and no effort was made to collect or infer such data. We manually verified the synthetic and benchmark dialogues for inappropriate or offensive content, and none was found. Our system does not involve any human annotation beyond the authors, so no consent or risk disclaimers were required.

Documentation and Statistics. All artifacts, including the experimental codebase, constraint templates, and synthetic dialogue generation scripts, are provided with the submission. This includes coverage across domains, types of slot-value inconsistencies, and linguistic patterns. We report the number of dialogue examples used in each experiment, as well as their train/test splits, in the experimental section. We also provide accuracy scores as descriptive statistics for the evaluation.

Computational Resources. Model generation and evaluation were conducted using a single NVIDIA A40 GPU, with a total budget of approximately 40 GPU hours. We do not fine-tune any large models; our work only uses them in inference mode.

Use of Existing Software. Our system uses standard NLP libraries such as Hugging Face Transformers and MiniZinc ‘constraint’ solver library. All packages were used with default or explicitly documented parameters.

Human Participants. No human participants were recruited for this study, and no user studies or annotation tasks involving external contributors were conducted. Therefore, issues such as compensation or informed consent do not apply in our setting.

---

1. https://openai.com/o1/↩︎