# Improving Dialogue State Tracking through Combinatorial Search for In-Context Examples

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

## Key facts

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

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

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [Llama 2: Open Foundation and Fine-Tuned Chat Models](https://mlsanity.com/paper/2307.09288/) (2023)
- [Sentence-BERT: Sentence Embeddings using Siamese BERT-Networks](https://mlsanity.com/paper/1908.10084/) (2019)
- [Representation Learning with Contrastive Predictive Coding](https://mlsanity.com/paper/1807.03748/) (2018)
- [PaLM: Scaling Language Modeling with Pathways](https://mlsanity.com/paper/2204.02311/) (2022)
- [OPT: Open Pre-trained Transformer Language Models](https://mlsanity.com/paper/2205.01068/) (2022)
- [What Makes Good In-Context Examples for GPT-3?](https://mlsanity.com/paper/2101.06804/) (2021)
- [Learning To Retrieve Prompts for In-Context Learning](https://mlsanity.com/paper/2112.08633/) (2021)
- [Dynamic Prompt Learning via Policy Gradient for Semi-structured Mathematical Reasoning](https://mlsanity.com/paper/2209.14610/) (2022)
- [A Simple Language Model for Task-Oriented Dialogue](https://mlsanity.com/paper/2005.00796/) (2020)
- [Surface Form Competition: Why the Highest Probability Answer Isn't Always Right](https://mlsanity.com/paper/2104.08315/) (2021)
- [Better Zero-Shot Reasoning with Role-Play Prompting](https://mlsanity.com/paper/2308.07702/) (2023)
- [Transferable Multi-Domain State Generator for Task-Oriented Dialogue Systems](https://mlsanity.com/paper/1905.08743/) (2019)
- [Compositional Exemplars for In-context Learning](https://mlsanity.com/paper/2302.05698/) (2023)
- [Does Prompt Formatting Have Any Impact on LLM Performance?](https://mlsanity.com/paper/2411.10541/) (2024)
- [Diverse Demonstrations Improve In-context Compositional Generalization](https://mlsanity.com/paper/2212.06800/) (2022)
- [Dialogue State Tracking with a Language Model using Schema-Driven Prompting](https://mlsanity.com/paper/2109.07506/) (2021)
- [In-context Example Selection with Influences](https://mlsanity.com/paper/2302.11042/) (2023)
- [Data Curation Alone Can Stabilize In-context Learning](https://mlsanity.com/paper/2212.10378/) (2022)
- [Coverage-based Example Selection for In-Context Learning](https://mlsanity.com/paper/2305.14907/) (2023)
- [Revisiting Demonstration Selection Strategies in In-Context Learning](https://mlsanity.com/paper/2401.12087/) (2024)
- [MultiWOZ 2.3: A multi-domain task-oriented dialogue dataset enhanced with annotation corrections and co-reference annotation](https://mlsanity.com/paper/2010.05594/) (2020)
- [SynthDST: Synthetic Data is All You Need for Few-Shot Dialog State Tracking](https://mlsanity.com/paper/2402.02285/) (2024)
- [DiSTRICT: Dialogue State Tracking with Retriever Driven In-Context Tuning](https://mlsanity.com/paper/2212.02851/) (2022)
- [Stabilized In-Context Learning with Pre-trained Language Models for Few Shot Dialogue State Tracking](https://mlsanity.com/paper/2302.05932/) (2023)

## Abstract (arXiv)

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 20x 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.