Dialogue state tracking

Deep dive

How it works

Parts:

• NLU front end — per-turn hypotheses (inform, deny, don't-care, request) with confidences; see intent classification and slot filling.
• State store — (domain, slot) → (value, confidence, turn) plus the requested set.
• Update rule — merges hypotheses into the old state: overwrite, agree, remove, keep.
• Confirmation check — slots below a confidence threshold; the policy asks before acting.
• Policy — reads the state, picks the next system act; that act is input to the next update.

Per turn:

1. Take the NLU output and the last system act (a "yes" only means something relative to "Friday?").
2. Resolve references from the old state: "same hotel", "there" copy a value across slots or domains.
3. Apply denials first: a denial of the held value lowers its confidence or removes it.
4. Apply informs: a value for an empty slot is stored; the same value reinforces (noisy-or); a different value overwrites unless much weaker than the held one.
5. Store "don't care" as an explicit value, distinct from "unset"; rebuild requested from scratch.
6. List slots below the confirm threshold; the policy confirms them or proceeds.
7. Emit the state to the policy and to downstream calls.

user turn ─► NLU ─► hypotheses ┐
last system act ──────────────┤
                              ▼
 old state ──────────► [ update rule ] ──► new state ──► policy ──► system act ─┐
      ▲                                       │ low conf?                       │
      └───────────────────────────────────────┴──► confirm slot   ◄─────────────┘

Code

use std::collections::BTreeMap;
pub const DONTCARE: &str = "dontcare";

#[derive(Clone, Debug)]
pub struct Slot { pub value: String, pub conf: f32, pub turn: u32 }

#[derive(Clone, Debug)]
pub enum Hyp {
    Inform { slot: &'static str, value: &'static str, conf: f32 },
    Deny { slot: &'static str, value: &'static str, conf: f32 },
    DontCare { slot: &'static str, conf: f32 },
    Request { slot: &'static str },
}

#[derive(Default)]
pub struct State { pub slots: BTreeMap<&'static str, Slot>, pub requested: Vec<&'static str>, pub turn: u32 }

impl State {
    pub fn update(&mut self, hyps: &[Hyp]) {
        self.turn += 1;
        self.requested.clear();
        for h in hyps { // denials first: "no, make it Friday" = Deny(Thu) + Inform(Fri)
            if let Hyp::Deny { slot, value, conf } = h {
                if let Some(s) = self.slots.get_mut(slot) {
                    if s.value == *value { s.conf -= conf; if s.conf <= 0.0 { self.slots.remove(slot); } }
                }
            }
        }
        for h in hyps {
            match *h {
                Hyp::Inform { slot, value, conf } => self.put(slot, value, conf),
                Hyp::DontCare { slot, conf } => self.put(slot, DONTCARE, conf),
                Hyp::Request { slot } => self.requested.push(slot),
                Hyp::Deny { .. } => {}
            }
        }
    }
    fn put(&mut self, slot: &'static str, value: &str, conf: f32) {
        match self.slots.get_mut(slot) {
            Some(s) if s.value == value => { s.conf = 1.0 - (1.0 - s.conf) * (1.0 - conf); s.turn = self.turn; }
            Some(s) if conf < 0.5 * s.conf => {} // much weaker than what we hold: ignore
            _ => { self.slots.insert(slot, Slot { value: value.into(), conf, turn: self.turn }); }
        }
    }
    pub fn needs_confirm(&self, thresh: f32) -> Vec<&'static str> {
        self.slots.iter().filter(|(_, s)| s.conf < thresh).map(|(k, _)| *k).collect()
    }
    pub fn view(&self) -> Vec<(&'static str, String)> { self.slots.iter().map(|(k, s)| (*k, s.value.clone())).collect() }
}

type Gold = Vec<(&'static str, &'static str)>; // sorted by slot name, like the BTreeMap
/// Joint goal accuracy: share of turns whose WHOLE state equals the gold state.
pub fn jga(dialogues: &[Vec<(Vec<Hyp>, Gold)>]) -> f32 {
    let (mut ok, mut n) = (0, 0);
    for d in dialogues {
        let mut st = State::default();
        for (hyps, gold) in d {
            st.update(hyps);
            let want: Vec<_> = gold.iter().map(|(k, v)| (*k, v.to_string())).collect();
            ok += (st.view() == want) as u32;
            n += 1;
        }
    }
    ok as f32 / n as f32
}

fn main() {
    use Hyp::*;
    let d1 = vec![
        (vec![Inform { slot: "hotel-day", value: "thursday", conf: 0.8 }], vec![("hotel-day", "thursday")]),
        (vec![Deny { slot: "hotel-day", value: "thursday", conf: 0.9 }, Inform { slot: "hotel-day", value: "friday", conf: 0.9 }],
         vec![("hotel-day", "friday")]),
        (vec![DontCare { slot: "hotel-price", conf: 0.9 }, Request { slot: "hotel-phone" }],
         vec![("hotel-day", "friday"), ("hotel-price", "dontcare")]),
        (vec![Inform { slot: "hotel-area", value: "south", conf: 0.4 }], // mis-heard: gold says "north"
         vec![("hotel-area", "north"), ("hotel-day", "friday"), ("hotel-price", "dontcare")]),
    ];
    let mut s = State::default();
    for (h, _) in &d1 { s.update(h); }
    assert_eq!(s.slots["hotel-day"].value, "friday");          // correction applied
    assert_eq!(s.slots["hotel-price"].value, DONTCARE);        // explicit don't-care
    assert_eq!(s.needs_confirm(0.6), vec!["hotel-area"]);      // low confidence -> ask
    let j = jga(&[d1]);
    assert!((j - 0.75).abs() < 1e-6);                          // 3 of 4 turns exactly right
    println!("JGA {j}");
}

Complexity and constants

• Frame update: O(h · log s) for h hypotheses and s slots (ordered map); a flat array per domain makes it O(h).
• Neural DST re-encodes the history; cost grows with turns unless the previous state replaces old turns.

Efficiency

• Cost: measured by me on an Apple M4 Pro, release build, one thread: the code above (frame update plus a view clone and compare per turn, a few String allocations) ran about 6.5 million turn updates/s over a 4-turn dialogue (two runs: 6.6 and 6.5 M), so order of 150 ns per turn. Bound: allocation. An LLM tracker turn costs order of 100 ms to seconds; the frame tracker is never the bottleneck.
• Levers:
  • Pass the previous state plus the latest turn instead of the full history — input per turn stays flat instead of growing (arithmetic, not measured) — whenever the model takes the state as input.
  • Only active domains' slots in the prompt — shorter prompt, fewer invented slots — when many services are registered.
  • Emit only the changed slots, apply them in code — fewer output tokens — for LLM trackers.
  • Prefix-cache the schema and instructions (provider feature) — less latency and cost on the repeated part — for stable prompts.
  • Calibrated confidences — fewer needless confirmations — when NLU scores drive the threshold.
• Naive → standard → state of the art:
  • Re-run an LLM over the full transcript each turn · tokens per dialogue grow quadratically.
  • Frame tracker, confidences, confirm threshold · order of 150 ns per turn here, accuracy bounded by NLU.
  • LLM with schema in the prompt, previous state as input, validated delta output · one call per turn, flat input.

Implementation notes

• Keep "unset", "don't care" and "unknown" distinct; collapsing them is the commonest silent bug.
• Key slots as domain-slot with types (enum, number, date); normalise before comparing ("fri"/"friday", "7pm"/"19:00").
• Persist the state per conversation outside the process (Rasa: tracker store); a restart must not lose it.
• Archive a domain's slots when its booking is done, or the next request inherits the old date.
• LLM trackers: parse the JSON, check slot names and types against the schema, reject unknown slots, retry once, else keep the old state.

Pitfalls

• JGA is brutal: one wrong slot, or a differently spelt right value, fails the turn; compare normalised values.
• Label noise caps measured accuracy: MultiWOZ was corrected in later versions (2.1, 2.2, 2.4); check which version a number uses.
• Carrying slots across domains blindly: a "Friday" for the restaurant is not always the hotel's.
• Uncalibrated NLU scores: the confirm threshold then means nothing.
• Overwriting a confident value with ASR noise, or never overwriting (stuck on a wrong value). Test both.
• Reading "yes" without the last system act.

Variants and alternatives

In production

• Rasa keeps a tracker per conversation in a tracker store; its forms fill slots until required ones are set.
• Voice assistants and customer-service bots use slot frames and confirm identifiers or amounts below a threshold.
• LLM agents: tool calling arguments are the state; context window management and memory consolidation decide what of it stays in the prompt across sessions.

Implementations

Sources

• Jason D. Williams, Antoine Raux, Matthew Henderson, The Dialog State Tracking Challenge Series: A Review, Dialogue & Discourse 7(3), 2016. paper
• Chien-Sheng Wu et al., Transferable Multi-Domain State Generator for Task-Oriented Dialogue Systems, ACL 2019. paper · code
• Abhinav Rastogi et al., Towards Scalable Multi-domain Conversational Agents: The Schema-Guided Dialogue Dataset, AAAI 2020. paper · data
• Paweł Budzianowski et al., MultiWOZ - A Large-Scale Multi-Domain Wizard-of-Oz Dataset for Task-Oriented Dialogue Modelling, EMNLP 2018. paper · data
• Fanghua Ye, Jarana Manotumruksa, Emine Yilmaz, MultiWOZ 2.4: A Multi-Domain Task-Oriented Dialogue Dataset with Essential Annotation Corrections to Improve State Tracking Evaluation, SIGDIAL 2022. paper · code
• Ehsan Hosseini-Asl et al., A Simple Language Model for Task-Oriented Dialogue (SimpleTOD), arXiv 2020. paper