Improving Dialogue State Tracking through Combinatorial Search for In-Context Examples
Haesung Pyun, Yoonah Park, Yohan Jo · 2025
Read Improving Dialogue State Tracking through Combinatorial Search for In-Context Examples by Haesung Pyun, Yoonah Park, Yohan Jo (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-00622.txt.
Introduction
Haesung Pyun, Yoonah Park, and Yohan Jo wrote this language technology paper, published in two thousand twenty-five, on tracking what a user wants across a conversation. Dialogue state tracking keeps the running list of goals, like dates and places, and few-shot models learn it from example dialogues picked by a retriever.
Most retrievers score examples one by one, missing how examples help or clash as a set. Their method, CombiSearch, scores whole combinations by their joint effect on tracking accuracy. It also weighs the query's own wording more fully. On the MultiWOZ benchmark, retrievers trained this way beat the prior best while using twenty times less training data. The gains carried to a second data set as well. With perfect retrieval assumed, the ceiling for the whole task rose by twelve points.
Catalog record
| CREATOR | Haesung Pyun, Yoonah Park, Yohan Jo |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 70 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-00622
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Improving Dialogue State Tracking through Combinatorial Search for In-Context Examples Haesung Pyun, Yoonah Park, Yohan Jo Abstract In dialogue state tracking (DST), in-context learning comprises a retriever that selects labeled dialogues as in-context examples and a DST model that uses these examples to infer the dialogue state of the query dialogue. Existing methods for constructing training data for retrievers suffer from three key limitations: (1) the synergistic effect of examples is not considered, (2) the linguistic characteristics of the query are not sufficiently factored in, and (3) scoring is not directly optimized for DST performance. Consequently, the retriever can fail to retrieve examples that would substantially improve DST performance. To address these issues, we present CombiSearch—a method that scores effective in-context examples based on their combinatorial impact on DST performance. Our evaluation on MultiWOZ shows that retrievers trained with CombiSearch surpass state-of-the-art models, achieving a 20× gain in data efficiency and generalizing well to the SGD dataset. Moreover, CombiSearch attains a 12% absolute improvement in the upper bound DST performance over traditional approaches when no retrieval errors are assumed. This significantly increases the headroom for practical DST performance while demonstrating that existing methods rely on suboptimal data for retriever training. 1 1 1 Our code: https://github.com/holi-lab/combisearch 1 Introduction Figure 1: (A) Conventional data preparation method. (B) Our data preparation method that integrates diverse pool construction and combinatorial re-ranking based on DST performance. Dialogue state tracking (DST), a core task for task-oriented dialogue systems and tool agents, tracks user intentions and relevant constraints throughout the dialogue. For example, if a user says “I want to book a guest house” and later adds “I want to book it for four people”, the dialogue state is updated with the slot-value pairs ‘[<hotel-type: guest house>, <hotel-book people: 4>]’. Recent work shows that large language models can perform DST through in-context learning (ICL) ( Brown et al. 2020 ; Zhao et al. 2023 ) . By supplying query–response exemplars in the prompt, models learn task-specific patterns from in-context examples, thereby eliminating the need for costly fine-tuning or extensive annotation ( Brown et al. 2020 ; Zhang et al. 2022 ; Chowdhery et al. 2023 ; Hoffmann et al. 2022 ; Touvron et al. 2023 ) . However, since performance depends on the relevance of these exemplars ( Liu et al. 2022 ) , recent studies propose retrievers that dynamically select examples tailored to each test query, boosting the accuracy and robustness of ICL performance across tasks ( Levy et al. 2023 ; Lu et al. 2023 ; Ye et al. 2023 ) . To select effective examples, it is crucial to train an ICL example retriever on high-quality data. The most widely adopted approach for preparing retriever training data follows two steps Hu et al. 2022 : (1) pool construction selects dialogues similar to the target query, and (2) re-ranking prioritizes dialogues whose dialogue states substantially overlap with the query’s dialogue state (Figure 1 -A). However, what constitutes effective in-context examples for DST and how to systematically select them remain understudied and particularly challenging, as DST requires a comprehensive understanding of various conversational aspects ( Chen et al. 2023 ) . For instance, coreference resolution is both crucial and error-prone, requiring the system to correctly identify anaphors (e.g., “it”) and their corresponding antecedents (e.g., “guest house”), which may span multiple dialogue turns. Our analysis identifies prominent errors and challenges in prior approaches (Appendix A.1 ). We focus on three key limitations in the prior data preparation process and address them in this paper. First, the re-ranking step scores each example individually, which can result in selecting redundant in-context examples that offer little new information. Second, relying solely on dialogue state similarity may neglect important contextual information within the dialogue itself and retrieve examples whose conversational characteristics differ significantly from the query dialogue. Such examples are suboptimal for handling complex linguistic phenomena, such as coreference resolution, present in the query dialogue. Furthermore, re-ranking examples based on dialogue state similarity does not directly optimize for DST performance, resulting in only “indirect supervision”. To address these limitations, we introduce CombiSearch, a new method for preparing training data for in-context example retrievers in DST. By combining diverse pool construction with combinatorial re-ranking (Figure 1 -B), CombiSearch has three key characteristics. First, the pool construction step collects diverse dialogues that share similar linguistic characteristics with the query—such as conversational flow, style, and structure—beyond just dialogue states. This ensures that more relevant examples are considered during re-ranking, improving the system’s ability to handle the linguistic phenomena present in the query. Second, rather than re-ranking individual examples in isolation, CombiSearch scores examples based on how they function together in tandem. By evaluating their combinatorial impact on DST performance, it accounts for synergistic effects that might be overlooked when scoring examples separately. Finally, the re-ranking step scores examples by directly optimizing Joint Goal Accuracy (JGA), a standard metric for DST, rather than relying on the indirect signal of dialogue state similarity between each example and the query. According to our evaluation, CombiSearch outperforms existing state-of-the-art methods on both the MultiWOZ 2.4 and Schema-Guided Dialogue (SGD) datasets. Notably, CombiSearch is highly data-efficient, enabling a retriever trained on CombiSearch-scored data to surpass all baseline models while using only 5% of the training data required by these models. Understanding the upper bound performance achievable with retriever training data without retriever errors is crucial, as this sets a hard limit on what practical retrievers can achieve. Under this ideal assumption of no retrieval errors, using examples scored by CombiSearch outperformed earlier approaches by 12% JGA, highlighting that prior methods rely on suboptimal data for training retrievers and that a more effective data preparation approach like CombiSearch is imperative for breakthroughs in DST. Notably, all these advances from CombiSearch’s combinatorial nature come with a running time that is linear in the number of examples to score. Our key contributions are as follows: 1. We present CombiSearch, an effective combinatorial method for constructing data to train retrievers of in-context examples in DST. 2. We demonstrate that CombiSearch outperforms baselines in DST, even with 20x data efficiency. 3. We reveal the significantly improved upper bound performance of CombiSearch when no retrieval errors are assumed, highlighting the importance of optimizing retriever training data. 2 Problem Setting Dialogue State Tracking DST focuses on predicting the dialogue state that captures the user’s intentions and goals, based on both the current user-agent interaction and the conversation history. Let A^{t} and U^{t} denote the agent’s and user’s utterances at turn t , respectively. The dialogue history up to turn t is C^{t}=[(A^{1},U^{1}),(A^{2},U^{2}),\dots,(A^{t},U^{t})] . The objective is to infer a dialogue state y^{t} from C^{t} , where y^{t} is a set of slot-value pairs: y^{t}=\{(s^{1},v^{1}),(s^{2},v^{2}),\dots,(s^{n},v^{n})\} . Following Hu et al. 2022 , we adopt a state-change formulation. Specifically, the model takes the previous dialogue state y^{t-1} and current utterances (A^{t},U^{t}) as input, denoted as x^{t}=[y^{t-1},(A^{t},U^{t})] , where y^{t-1} summarizes C^{t-1} . It predicts the dialogue state change \Delta y^{t}=\{+(s^{i},v^{i}),\dots,-(s^{j},v^{j})\} , with “+” indicating addition and “–” indicating removal of slot-value pairs. The t -th dialogue state is y^{t}=y^{t-1}\cup\Delta y^{t} . In-Context Learning for DST Given a test query x_{\text{test}} , the ICL approach retrieves k labeled