The Power of the Noisy Channel: Unsupervised End-to-End Task-Oriented Dialogue with LLMs
Brendan King Jeffrey Flanigan

Effective dynamics of qubit networks via phase-covariant quantum ensembles
    Sean Prudhoe, Unnati Akhouri, Tommy Chin, and Sarah Shandera
    
==========================================================================



Training task-oriented dialogue systems typically requires turn-level annotations for interacting with their APIs: e.g. a dialogue state and the system actions taken at each step. 
These annotations can be costly to produce, error-prone, and require both domain and annotation expertise. 
With advances in LLMs, we hypothesize unlabelled data and a schema definition are sufficient for building a working task-oriented dialogue system, completely unsupervised.
Using only (1) a well-defined API schema (2) a set of unlabelled dialogues between a user and agent, we develop a novel approach for inferring turn-level annotations as latent variables using a noisy channel model.
We iteratively improve these pseudo-labels with expectation-maximization (EM), and use the inferred labels to train an end-to-end dialogue agent.
Evaluating our approach on the MultiWOZ benchmark, our method more than doubles the dialogue success rate of a strong GPT-3.5 baseline.[Our code will be available at https://github.com/jlab-nlp/nc_latent_todhttps://github.com/jlab-nlp/nc_latent_tod]



In light of recent advances in LLMs, we hypothesize a fully functional dialogue agent can be built for a well-defined system from unlabelled conversation data alone. We assume (1) a well-defined API (schema) <cit.> for a dialogue system. From this, we derive a space of dialogue states (and dialogue acts). Finally, we assume (2) a potentially large set of unlabeled dialogues between a user and agent that could be modeled using the given schema. Overview in <ref>.





§ INTRODUCTION



Add: Tool use with APIs is very important, and inferring API calls from unlabeled dialogues would be very helpfulTask-oriented dialogue systems, which use APIs to complete tasks on behalf of users, have been a longstanding challenge within conversational AI.
Recent advances in large language models (LLMs) have further stimulated interest in task-oriented systems and LLMs which can use APIs as tools.
To facilitate API use, successful task-oriented dialogue systems usually employ a modular approach:

predicting a dialogue state which includes arguments to API calls, and dialogue acts for planning an appropriate response, before finally producing a natural language reply.
Training such systems typically requires expert annotation of these structured intermediates for every dialogue turn.
Even in settings where human-human dialogues are abundantly available, the high cost and expertise required to annotate the dialogues poses a significant hurdle to system development.



Recent work has shown that LLMs can accomplish a broad set of useful tasks without any structured labels for a task <cit.>. These include `zero-shot' approaches to task-oriented dialogue sub-tasks such as Dialogue State Tracking (DST) <cit.>, intent detection <cit.>, grounded response generation <cit.>, and even zero-shot end-to-end dialogue systems <cit.>. 
Still, existing approaches generally do not perform well enough for real-world use, and none are able to make effective use of in-domain unlabelled dialogues.



The motivation for such a system is the following. If a dialogue task is of high value but there is no existing dialogue system performing the task, then there are likely human agents performing the task while interfacing with users, and these conversations could be recorded. Additionally, a software developer likely has access to or can write a natural language API description for the API system that is supporting the task.   

We ask: can we use existing unlabelled dialogues (without any labels or API calls annotated) along with an API specification, to build a working dialogue agent, without needing an expert to annotate data?
This addresses a common real-world scenario. 
Many high value dialogue tasks are currently carried out by human agents, who interface a user with some software system. 
These conversations can be recorded and transcribed, and the API(s) supporting the agent typically have well-formed specifications.
However, annotating the API calls and system acts needed for aligning the two is time consuming and requires annotation expertise.
In lieu of this, `zero-shot' systems have been proposed, but these still require an expert to annotate a `formatting example' <cit.>, or a more detailed `policy skeleton' <cit.>.



    Old comments/notes, prior to Jeff edits:
    
    
    
    
    
    

We instead propose the following setting: we assume an API schema definition , and plenty of available human-human dialogues in natural language, but no annotations on these dialogues (<ref>). To the best of our knowledge, we are the first to consider this setting.
We demonstrate that one can develop a conversational agent for the API schema in this setting without any assistance from an expert annotator.  
Our contributions are as follows:

    
    
    
    
  * We construct an end-to-end task-oriented dialogue agent with an LLM solely from unlabelled dialogues and an API definition, without any turn-level labels or supervision from de-lexicalized utterances.
    
    
  * We accomplish this by inferring all the pseudo-labels necessary (API calls, system actions) to train a traditional end-to-end dialogue system from unlabelled dialogues, using prompts which are automatically generated from the API schema.
    
  * We propose a noisy-channel `code-to-text' re-ranking method, which is instrumental to our pseudo-label quality and final system.
    
    
  * We devise a novel Hard-EM <cit.>fix for camera-ready approach which uses predictions as in-context examples for the LLM, and additionally as data for iteratively fine-tuning a final model.
    
    
    
    
    




§ PRELIMINARIES


A task-oriented dialogue consists of turns of utterances between a user and an agent which interfaces the user with a programmable system or API to accomplish a task. Typically the system response utterance follows the user's utterance.
We denote u_t as the user's utterance at turn t, and r_t as the system's response. 
We assume the APIs supported by the system are defined in a schema , which gives names and descriptions for all arguments supported in each API, as well as the possible values any categorical arguments may take <cit.>. 
This is analogous to standardized formats for API documentation, many of which could be easily converted to a schema definition.

Task-oriented systems require some method for interacting with the APIs in . 
Modular approaches use a Dialogue State Tracking (DST) module, which predicts a belief state b_tshould we call this API call(s) instead?: a collection of arguments to API call(s) needed to satisfy the user's goal. 
A belief state is commonly represented with a set of slot-value pairs:

    b_t = {(s_1, v_1), (s_2, v_2), ... (s_n, v_n)}

For example, if a user says `I'm looking for a restaurant south of town', a DST system might produce the belief state {(restaurant-area, south)}, which can be used to query a restaurant API. We assume zero labeled belief states and infer them from unlabelled dialogues using the space of possible states supported by the schema definition .

We also make use of system dialogue acts to structure our agent's communicative intents with a policy module. 
Given a dialogue state and context for a turn t, the policy predicts set of dialogue acts to be communicated in the system response r_t. 
For instance, the policy might determine that we should ask the user to narrow their search to a price range: A_t = {Request(restaurant-area=?)}.
An appropriate system response might be: “Sure, are you looking for a particular price range?"
Like belief states, we assume zero supervised examples of A_t and infer them from unlabelled dialogues. 



§ METHOD OVERVIEW






We treat the turn-level labels needed for training an end-to-end dialogue system as a latent variables, and infer them from unlabelled dialogues.
We assume only the fully-lexicalized sequence of user and system utterances u_1, r_1, ... u_T, r_T, and the schema  defining the system's capabilities, which defines the space of valid dialogue state and act labels. 
Importantly, our prompts are automatically generated from the API schema.

In <ref>, we outline our noisy-channel prompting method for inferring the turn-level labels necessary for training our dialogue agent. We give an overview of the latent variables we infer in <ref>. We assume we cannot query the APIs or observe results while labeling dialogues offline, as the obtained API results may have changed.
In <ref>, we train a complete dialogue agent by fine-tuning on prompts derived from our inferred pseudo-labels.





§ INFERRING LATENTS VIA NOISY CHANNEL









In this section, we present our method for inferring latent annotations for the dialogue states b_1...b_TAPI calls? and dialogue acts A_1...A_T for each dialogue turn t given only the unlabelled user and system utterances (u_1, r_1, u_2, r_2, ... u_T, r_T).

To do this, we devise a noisy-channel prompting approach for DST and dialogue act tagging (DAT) using StarCoder <cit.>, a code-based LLM.
First, we use a text-to-code prompt to infer the API call(s) made by the system in each dialogue, and build the dialogue state from inferred API call arguments (<ref>).
We use a similar text-to-code prompt to infer the latent act(s) communicated in each agent response, so that we can reverse-engineer an agent's policy (<ref>).
For both tasks, we find much better performance when re-ranking latent predictions according to a noisy-channel model, in which we condition the observed utterance on a predicted latent in a code-to-text prompt (<ref>).
Finally, we leverage the in-context learning ability of LLMs by re-using our predictions as exemplars (<ref>).
Given these initial pseudo-labels, we iteratively improve their quality using Hard-EM <cit.> (<ref>).


moving this figure to the Appendix as two full-page figures





 §.§ Inferring API Calls and Dialogue State



We prompt the LLM with a text-to-code prompt for inferring the latent dialogue state as an API call.
<ref>  in <ref> gives an example of our prompt.
We generate a prompt enumerating the intents available in the schema  as APIs callable by our agent.
Following <cit.>, we predict the appropriate function call conditioned on the prior system response r_t-1, the current user utterance u_t, and the previous belief state prediction b̂_t-1. 
We then extract a dialogue state change Δb̂_t from the arguments to the call, and compute the next dialogue state as b̂_t = Δb̂_t + b̂_t-1.
While used offline here, this DST method is causal with respect to dialogue inputs and is the same as our method in online inference.



 §.§ Inferring System Acts
 

For inferring system acts, we use a similar text-to-code prompt for predicting the set of dialogue acts A_t communicated in a given system response r_t.
See <ref> in <ref> for an example of our prompt.
We define each act our system could take in the prompt instructions.
For input from each turn, we find best performance when conditioning only on the response to tag, r_t.
For our set of supported acts, we use a subset of the universal dialogue acts proposed in <cit.>, where some acts such as “Inform” or “Offer” may use slots defined in .
For example, an agent choosing to offer to book a user at a hotel named `acorn guest house' might be represented as Offer(hotel_name=`acorn guest house'). 
See <ref> for our complete dialogue act set. 
Importantly, we use the schema definition  and our act set to validate each act prediction, removing predicted keys which do not belong to , or acts which are not in the set. For example, the `text' key is not valid for a `ThankYou' act, so a prediction of “ThankYou(text=`thanks, have a good day')" would be normalized to only “ThankYou()”.
Using the inferred system acts, we use a rule-based method to delexicalize the system responses for training the response generator (<ref>, right).

maybe also expand on this in the response generation section added under <ref>, Response Generation.



 §.§ Noisy Channel LLM Prompting



We find that a noisy channel prompting method <cit.> significantly the quality of our inferred dialogue states and acts.
Here we describe noisy channel prompting using a simple example, and then describe its application to dialogue state tracking and system act tagging.

A typical prompt for machine reading comprehension might be:

[fontsize=]
    <Optional in-context examples (c)>
    Passage: <Passage (z)>
    Question: <Question (x)>
    Answer:



Given this prompt of the in-context examples c, passage z, question x, an answer y completion is found with the language model by maximizing or sampling from Pr(y|x,z,c).  We call this the direct prompt.

The “noisy channel” prompt is:

[fontsize=]
    <Optional in-context examples (c)>
    Passage: <Passage (z)>
    Answer: <Answer (y)>
    Question: <Question (x)>



where the likelihood of the question now depends on the answer. 
To use the noisy channel LLM prompt, we first sample k samples from the direct prompt, and then pick the best output answer y according to the noisy channel prompt probability. 
One can choose to score the joint probability of the answer followed by the question, i.e. Pr(x|y,z,c)Pr(y|z,c), or only the conditional Pr(x|y,z,c), following <cit.>.[In the latter case, the prior Pr(y|z, c) is uniformly 1/k for the k samples from the direct prompt.]

To apply this method to inferring dialogue states, we first sample a set of possible belief state changes using top-p sampling <cit.> from the direct DST prompt, and then pick the best dialogue state according to the noisy channel prompt (see <ref>).  
We use an analogous procedure for inferring system acts.
For DST, we find scoring with the joint Pr(x|y,z,c)Pr(y|z,c) to perform best, and scoring with the conditional Pr(x|y,z,c) best for act tagging.



    _Δ b_t P((, b̂_t-1, r_t-1, u_t))


Where  is a set of k in-context examples from a pool of our prior predictions, detailed below, and  combines arguments into our text-to-code prompt in the order they appear. 
We re-rank each candidate Δ b_t according to a code-to-text `channel' variant of the same prompt, where p(y|x) is proportional to p(x|y)p(y).



 §.§ Retrieval-Augmented In-context Learning


To leverage the in-context learning abilities of LLMs, we retrieve from a pool of examples from our predictions.
Because we assume no labeled examples, this pool starts with zero examples and is filled incrementally.


We retrieve up to k examples for in-context learning from this pool using an unsupervised dense retriever, with examples ranked by embedding cosine distance.[We use MPNet <cit.>, available on Huggingface as ] 
We use k=8 and k=6 for DST, DAT respectively. 
For retriever inputs, we use (b̂_t-1 r_t-1 u_t) and (u_t  r_t) for DST and DAT respectively, where  indicates concatenation.
Applied naively, this in-context learning approach can suffer a majority label bias <cit.>. We adjust for biases introduced in the initially small example pool by 1) not using any in-context examples until we have a minimum of n=32 examples in the pool and 2) using our API schema  to require at least 4 distinct labels in each set of in-context examples.[We consider two dialogue state change labels to be distinct if they update different slots, and two act labels to be distinct if they embody different acts or different slots]
Our algorithm for producing initial pseudo-labels is in <ref>.



 §.§ Refining the Labels with Hard-EM



While the labels we produce in <ref>-<ref> can be used directly for training an end-to-end dialogue system, we find their quality can be improved through expectation-maximization <cit.>.
For every dialogue turn in our dataset, our initial pseudo-labels provide the expected dialogue state and system dialogue acts according to our zero-shot system.
We then jointly fine-tune an LLM as a noisy-channel DST & DAT system to maximize the likelihood of these expected labels.
We use smaller version of our prompted LLM, StarCoder 3B <cit.>.

For each turn, we derive (prompt, completion) pairs for `direct' text-to-code and `channel' code-to-text DST and DAT modules, as defined in <ref>.
We then combine and shuffle these pairs into a single training set for joint fine-tuning.
For efficient training, we shorten our prompts by removing in-context examples as well as the function definitions used in the in-context learning setting. 
We find up-sampling the `channel' prompts so that there is a 2:1 ratio of `channel' to `direct' instances for training improves performance. 


After fine-tuning, the model can be used to produce improved pseudo-labels by re-labeling each dialogue, using the same noisy-channel inference methods. Following this, we can repeat the fine-tuning process.
This train and re-label process can be repeated for any number of iterations, though we find a single re-labeling is sufficient.




§ END-TO-END SYSTEM




Following <cit.>, we utilize a multi-task fine-tuning method for training a single LLM as a complete dialogue system, consisting of a dialogue state tracker, policy, and response generator.



  
DST For the DST sub-task, we again use both `direct' and `channel' (prompt, completion) pairs. 
This allows us to use the same noisy-channel inference method presented in <ref>.




  
Policy For the Policy sub-task, we use a text-to-code prompt where we simply condition on the k=5 most recent utterances in the dialogue history: H_t = (u_t-2, r_t-2, u_t-1, r_t-1, u_t). 
The completion is the current turn's system acts A_t, which will be used to ground the next response r_t. 
We do not use a noisy-channel variant for Policy, and greedily decode an act prediction at inference time:


    Â_t = A_t ∈𝒱^*P((H_t)))







  
Response Generation For Response Generation, we condition on the turn's observed system and user utterances (r_t-1, u_t) and our policy's act prediction Â_t). The completion is the observed system response r_t. We also do not use a noisy-channel variant for response generation, and greedily decode the response:

    r̂_t = A_t ∈𝒱^*P((r_t-1, u_t, A_t)))

Following prior works, we predict delexicalized responses, where values for slots in the system response are replaced with placeholders for the slot name. 
For example, instead of generating “The phone number for acorn guest house is 555-5309" directly, we would predict “The phone number for the [hotel_name] is [hotel_phone]”, where values could be filled in.
Importantly, we never presume access to gold delexicalized responses.
Instead, we use our predicted acts, e.g. “Inform(name=`acorn guest house', phone=`555-8309')”, to delexicalize the observed response for training.




  
End-to-end Training 
For each turn, we derive (prompt, completion) pairs for `direct' and `channel' DST, 
and direct Policy, and Response Generation prompts.
We then combine and shuffle these pairs into a single training set for joint fine-tuning.
For efficient training, we shorten our prompts by removing in-context examples as well as the function definitions used in the in-context learning setting. 
We find up-sampling the `channel' prompts so that there is a 2:1 ratio of `channel' to `direct' instances for training improves performance. 
Finally, we fine-tune StarCoder 3B using cross-entropy loss and AdamW with default hyperparameters. 






§ EXPERIMENTS


We conduct unsupervised end-to-end dialogue (E2E) and dialogue state tracking (DST) experiments on the MultiWOZ 2.2 dataset <cit.>, containing over ten thousand multi-domain task-oriented dialogues crowd-sourced in a wizard-of-oz setup. We use the fully lexicalized, unlabelled dialogues from the training set to build our system, and evaluate on the test set.
First, we demonstrate the value of our approach in an end-to-end dialogue evaluation, following prior works on task-oriented dialogue (<ref>). 
Second, we conduct a dialogue state tracking evaluation to more carefully evaluate the quality of our pseudo-annotations (<ref>).




 §.§ End-to-End (E2E) Experiments



In E2E experiments, we use our complete system to both predict API call arguments and generate a next system response in natural language. 
We evaluate our generated responses with Inform rate, Success rate, and BLEU, as well as a Combined score of 0.5(Inform + Success) + BLEU, following prior works. We provide details on these metrics in <ref>.

We compare our approach to the previous state-of-the-art unsupervised methods, a GPT-3.5 zero-shot baseline <cit.>, and SGP-TOD <cit.>. 
Where possible, we report results for both the original approach and modifications required to fit our fully unsupervised setting.
For reference, we also run our own method in the fully-supervised setting. 
We train a model using the procedure in <ref> using the annotations sourced from crowd-workers in the MultiWOZ 2.2 corpus <cit.>, rather than the pseudo-labels predicted in <ref>.
We also compare with existing supervised approaches as a reference point. 
We include DiactTOD <cit.>, which to our knowledge is the supervised state-of-the-art, and PPTOD <cit.>, which uses a multi-task fine-tuning approach similar to our own in <ref>, for T5 encoder-decoder models <cit.>.



 §.§ DST Experiments



We conduct multi-domain DST experiments on the MultiWOZ Dataset in order to evaluate the quality of our pseudo-annotations. We use our DST Module to predict and evaluate only latent dialogue states, which collect the arguments required for unseen API calls.

Following prior works, we evaluate DST performance with joint-goal accuracy (JGA), or whether a given dialogue state is completely accurate. More details are available in <ref>.

We compare to our ChatGPT 3.5 Turbo baseline <cit.>, as well as prior zero-shot DST methods.
These include IC-DST <cit.>, which re-frames DST as text-to-SQL, and RefPyDST which re-frames DST as text-to-python <cit.>. By default, both of these works use OpenAI Codex <cit.>, and we apply their prompting approaches to StarCoder 15B for clearer comparison. 





§ RESULTS




  
E2E Performance 
We present E2E results for our unsupervised dialogue agent in <ref>. 
We find that our method achieves state-of-the-art performance in our fully unsupervised setting, more than doubling the Success Rate and Combined score of the GPT 3.5 Turbo baseline of <cit.>.
When we remove the supervision of delexicalization for fairer comparison (- gold delex.), we find even greater improvement across all end-to-end metrics.
As discussed in <ref>, SGP-TOD uses both a supervised formatting example and a `Policy Skeleton', containing additional supervision for Policy and Response Generation.
With no implementation publicly available, we were unable to run a modified version of their experiments without this supervision for fair comparison. 
Despite a less-supervised setting, our method is able to perform comparably, even slightly out-performing SGP-TOD in Combined score.

Remarkably, our unsupervised EM approach also outperforms the supervised variant of our model due to improvements in Inform and Success rate, suggesting the Dialogue acts we infer are of high quality. 




  
DST Performance Our DST results are shown in <ref>. Where possible, we distinguish between `zero-shot' results which include a hand-engineered formatting example, and the same method applied without the formatting example.[Due to the deprecation of OpenAI Codex, we were unable to run experiments for IC-DST or RefPyDST without a formatting example on the original Codex model]
We find that our method significantly outperforms our GPT 3.5 Turbo baseline by 26% joint goal accuracy. 
Our approach performs nearly as well as the best method using OpenAI Codex with a supervised formatting example, using less than 10% of the parameters at any time (175B vs. 15B). 
When applying the IC-DST and RefPyDST prompting methods to StarCoder, our method significantly outperforms both, with and without a formatting example.


When comparing to state-of-the-art zero-shot text-to-code approaches in <cit.>, we find our performs comparably despite our final inference model far fewer parameters.
One could conceivably use our approach with OpenAI Codex or a similarly large model and achieve further gains, but we choose to use an open model so that we can interrogate the pre-training data for contamination.   











  
Ablations In <ref>, we conduct an ablation to evaluate both the impact of our noisy channel modeling and the value of iterative re-labeling in our EM approach.
We compare our proposed system to one in which each module is replaced by only greedily sampling from its `direct' variant, at both labeling and end-to-end inference time. We plot our Combined end-to-end performance across iterations of EM, with `0' indicating our zero-shot system.
We find that EM improves our end-to-end performance in both our noisy-channel approach and greedy ablation, and that our noisy-channel inference methods are important to dialogue success, with a 30 and 33 point improvement over our greedy baseline with 1 and 2 EM steps, respectively. 
Ablations across Inform, Success, BLEU, and joint goal accuracy are in <ref>.



    Removing this table in favor of a figure (graph)
    





§ CONTAMINATION ANALYSIS



Evaluation of unsupervised methods, such as ours, that use LLMs has the potential issue of task contamination, where supervised examples are seen in pretraining data <cit.>.  Inclusion of supervised examples of the task in LLM pretraining data would render the model no longer unsupervised and the evaluation potentially biased: tasks for which the training data has been seen may have a higher performance than truly unsupervised tasks.

To address this issue, we quantify the presence of contamination in LLM pre-training data, and then estimate the potential impact on our results.
Fortunately, the StarCoder family of models that we use has the complete pre-training corpus publicly available for analysis.[https://huggingface.co/datasets/bigcode/starcoderdatahttps://huggingface.co/datasets/bigcode/starcoderdata]


In an ideal world, benchmarks of community interest would be completely and verifiably excluded from LLM pre-training.
Today's NLP ecosystem poses two obstacles to this.
First, many of the most capable LLMs are released without an open pre-training corpus.
Second, public use of benchmark data complicates exclusion: it is not sufficient to simply exclude the primary source of the benchmark.
To our knowledge, there are no suitably complex human-human task-oriented dialogue benchmarks that are guaranteed to be excluded from the pre-training of the most capable LLMs.

In light of this, we aim to first 






We conduct an exhaustive search for supervised pairs of our dialogue subtasks in the StarCoder pretraining data using a semi-automated search with manual review.  Details of our search procedure are in <ref>.  We find no complete dialogues with supervised labels.  We do find 42 turns labeled with act tagging, and 42 turns labeled with DST in the pre-training corpus, categorized in <ref>.[The average dialogue length in MultiWOZ is 13.9 turns. Put together, the set of contaminated turns would be roughly the length of 6 dialogues]
We consider a (x, y) pair to be `Correct' if the state change/dialogue act y is actually correct for the utterance x, and to be `Authentic' if the (x,y) pair is found verbatim in the MultiWOZ corpus.[A `Correct' pair might arise from printing training data, and an incorrect pair from discussion of a failure case.]
Astonishingly, we find half of the found Act Tagging pairs are incorrect, and could possibly mislead a pre-trained model if the model learned from them.
We also find that less than half of the turns are authentic for either task, and find a number of them derive from Github issues discussing problems with dialogue simulators.



Additionally, we estimate the degree to which the contamination we discover could exaggerate expected performance of our method on an unseen schema, by using contaminated (x, y) pairs as in-context examples.[Ideally, one would pre-train an identical StarCoder model on a corpus without contamination, this is computationally impractical. Additionally, we are not aware of any available LLM that can be verified as not contaminated for this task.]

In <ref>, we compare our zero-shot prompt, which receives no examples of any kind, with a `contaminated' variant which uses k=3 in-context examples derived from contamination in the pre-training corpus.
The `contaminated' model retrieves the most relevant contaminated fragments from a pool using the dense retrieval approach described in <ref>. 
These are inserted as a triple-quoted string block, so that the prompt remains syntactically valid python.
By leaving contaminated examples in their original format, we test whether their inclusion elicits memorized knowledge rather than providing guidance on input/output formatting.

Surprisingly, we find including this supervision via contaminated fragments hurts performance, indicating that these examples do not provide meaningful supervision for our task.
Further, the substantial gains in our noisy-channel EM approach suggest our method is doing more than simply eliciting schema-specific knowledge memorized in pre-training.
 




§ RELATED WORK





  
Zero-shot Dialogue A few recent works have proposed zero-shot approaches to dialogue problems using LLMs. 
<cit.> and <cit.> propose DST methods which prompt code based LLMs in a text-to-SQL or text-to-program format, respectively. 
These methods rely on prompts tailored to the schema and the use of a supervised `formatting' example, which requires annotation expertise. 
<cit.> extends this approach to end-to-end task-oriented dialogue by adding a policy prompter for GPT 3.5. 
In addition to a formatting example, their policy prompt requires a hand-crafted `policy-skeleton' consisting of examples of the appropriate system act and reply in response to different user utterances or database results.
Our approach differs in that we require zero labeled examples of any kind. 
<cit.> propose a zero-shot end-to-end method for prompting instruction-tuned LLMs like GPT 3.5.
However, this method presumes delexicalized system responses r_1 ... r_t-1 in the conversation history as input, where entities are replaced with placeholders. 
Producing these inputs requires ground-truth annotations and gives a form of supervision about the entities and their attributes within a dialogue (see <ref> for a comparison for  GPT 3.5 Turbo with and without delex supervision).
In contrast, we only assume fully-lexicalized dialogues, which do not provide this supervision and require no human annotation.
We adapt the method of <cit.> to use lexicalized dialogues as inputs, and use this approach as our baseline.
<cit.> propose an end-to-end method which prompts GPT-4 for interactions with a knowledge base before producing a response, however it generalizes poorly to the multi-domain setting.



  
Semi-supervised TOD Some works propose semi-supervised approaches to end-to-end task-oriented dialogue. 
<cit.> propose an end-to-end sequence-to-sequence model where the dialogue state is a latent variable. 
<cit.> adapt this approach for use with pre-trained language models, fine-tuning GPT-2. 
While successful, these approaches require a non-trivial amount of supervised data.
Other semi-supervised works also evaluate their method in an unsupervised setting <cit.>. 
However, these works also assume delexicalized training dialogues, which requires ground-truth annotation and gives a form a supervision to the model.



  
Noisy channel and re-ranking methods 
A few previous works have utilized noisy channel methods for task-oriented dialogue or prompting methods. <cit.> pre-train a noisy channel for task-oriented dialogues as a sequence to sequence model, however their method requires significant labelled training data. <cit.> propose noisy channel prompting for few-shot classification tasks, which inspires our generalization to the generative setting.



§ CONCLUSION


We present a novel approach for constructing an end-to-end task-oriented dialogue system by leveraging pre-trained language models to infer labels from unlabeled dialogues.



§ LIMITATIONS


Data contamination in LLM pre-training poses a hurdle for accurate benchmarking across NLP, and particularly for unsupervised methods.
In an idealized setting, there would be a suitably strong task-oriented dialogue benchmark that could be verified as not belonging to the pre-training corpus of each new and more capable LLM.
This is not the case for our setting or for many others, and warrants careful attention from the NLP community.
For our setting, we were able to properly define problematic contamination and search for it in our LLM's pre-training corpus, thanks to the open release of the pre-training data.
We found limited contamination and demonstrated that the contamination we found was not helpful in eliciting task knowledge that might have been memorized in pre-training. 




All experiments in this paper were conducted on pre-existing public dialogue corpora, collected explicitly for training task-oriented dialogue agents with the knowledge of all participants <cit.>. 
Our use of the StarCoder model also falls within the terms of it's Responsible AI License.
It is important that subsequent applications of our method also adhere to any fair-use policies governing collected dialogues or transcripts.

Points to discuss: fair access and use of unlabelled dialogues






§ PROMPT EXAMPLES


<ref> provides abridged instances of our direct prompts for DST and for Act Tagging. <ref> shows our prompt for inferring API call(s) or changes to the dialogue state from an unlabelled dialogue, as detailed in <ref>. Our prompts use python keyword arguments to provide the input variables for a given sub-task, and to prompt the LLM for the next variable of interest. Using the arbitrary ordering of keyword arguments in Python function calls, our `channel' prompts simply re-order the arguments in order to score the likelihood of the user's utterance given the predicted state change.
<ref> provides a similar abridged instance of our direct prompt for tagging dialogue acts in an unlabelled dialogue. Here, we simply condition on the observed system response r_t.









§ METRIC DETAILS




  
End-to-End (E2E) Dialogue Metrics
We measure end-to-end dialogue performance using the Inform rate, Success rate, and BLEU, following prior works, using the automatic evaluation provided by <cit.>.[https://github.com/Tomiinek/MultiWOZ_Evaluationhttps://github.com/Tomiinek/MultiWOZ_Evaluation]

A dialogue is considered Informed if the most recently mentioned result for each domain meets the user's goal constraints, and is considered Successful if it is Informed and all values for requested slots are presented to the user. 
For example, if a user were to ask `Can you give me the phone number of a cheap hotel in the east part of town?', the dialogue would be Informed if we refer them to a hotel that is actually in the cheap price range and in the east, and Successful if we additionally provide the phone number, as requested. 
BLEU is computed against a single reference response, and the Combined score is 0.5(Inform + Success) + BLEU.



  
Dialogue State Tracking Metrics Following prior works, we evaluate DST performance with joint-goal accuracy (JGA): for a turn x_t, a dialogue state prediction ŷ_t is considered correct only if all slot names and values match the gold annotation state y_t. We again use the evaluation provided in <cit.>. Following their work, we accept fuzzy matches for non-categorical string values, such as the name of a restaurant or hotel, using the  library and a fuzz ratio of 0.95.[https://pypi.org/project/fuzzywuzzy/https://pypi.org/project/fuzzywuzzy/] 



§ DIALOGUE ACTS



Following <cit.>, we use a universal set of dialogue acts for managing our agents communicative intents. We omit some acts for simplicity and to reduce the context length required to enumerate them in a prompt. <ref> lists each act and a description. Since our dialogue set is not directly comparable to prior works, we do not directly evaluate act tagging or policy accuracy. Instead, acts serve only as an intermediate representation for planning responses in our end-to-end system.





§ OFFLINE LABELING ALGORITHM



Algorithm 1 gives our algorithm for pseudo-labeling of unlabelled dialogues.




Our algorithm for initial pseudo-labeling of unlabelled dialogues in _train




§ FURTHER RESULTS ACROSS EM STEPS



Here we expand on our ablations in <ref>, which evaluates our method with and without our proposed noisy-channel prompting across iterations of expectation-maximization (EM). In <ref>, we break down the performance gains we observed in our `Combined' metric into Inform rate, Success rate, and BLEU, where Combined = 0.5(Inform + Success) + BLEU. `0' iterations of EM indicates our zero-shot prompting system, without any in-context examples or EM. We find that EM substantially improves performance in all cases, and particularly for our noisy-channel prompting approach. We find the noisy channel prompting approach improves performance on all metrics, with the most substantial gains over the greedy baseline in Inform and Success rates. 
This suggests that within our algorithm, noisy-channel inference may be particularly important when inferring the system's dialogue acts in order to reverse-engineer an accurate policy.

In <ref>, we analyze dialogue state tracking performance across iterations of EM using Joint Goal Accuracy (JGA). We find our noisy-channel prompting approach improves the accuracy of our dialogue state tracking predictions across iterations of EM when compared to a greedy, direct prompting approach.









§ CONTAMINATION SEARCH & RESULT DETAILS





 §.§ Procedure
 

We detail our method for finding instances of task contamination within the StarCoder pre-training set.
We are particularly interested in supervised pairs (x, y) where y belongs to our schema of interest , for any of the dialogue sub-tasks used in our system. 
We devise a method for searching the complete pre-training corpus for contaminated (x, y) pairs, where x is an utterance we might observe from either the system or user, and y is the latent dialogue state change or dialogue act supporting . 
For each utterance x from either the system or user, we collect all documents from the pre-training corpus which contain the complete utterance. 
We use the elastic search index provided for the StarCoder pre-training data, which accounts for differences in capitalization, punctuation, and interrupting white-space.[https://github.com/bigcode-project/search/blob/main/index.pyhttps://github.com/bigcode-project/search/blob/main/index.py] 
Following this, we search matching documents for keywords from y (e.g. slot names and values) to determine which of these documents may plausibly contain a supervised label and warrant manual review. 
For dialogue states, these are the slot names and values, discarding extremely generic keywords like `name'.
For act tags, these are the act names, slots, and values.
We then consider a document to need manual review if 40% or more of the keywords are found in the 500 characters before or after a matching x in a document.
Finally, we hand-check the remaining documents and extract contaminated (x, y) pairs.




 §.§ Examples

<ref> contains examples of contamination discovered in our search process, and the type of document in which they were found. Notably, none of the examples found closely match our output formatting.



