Grounded Derivation Trees for Spoken Dialogue State Tracking, Scored with Reset-Based Evaluation

When people book a hotel by phone, they rarely say the key facts cleanly in one sentence. They read out a phone number in chunks across three turns, say "me, my wife and our two kids" instead of "four," and say "the day after tomorrow" instead of a date. On the SpokenWOZ benchmark, which records exactly these phone-style conversations, the best reported system tracks the full set of user constraints correctly on only 25.65% of turns. Zero-shot ChatGPT reaches only 13.75%, largely because it invents values that were never spoken (SpokenWOZ). This proposal targets that failure. The system does not ask a model to emit slot values directly. It asks the model to emit a small derivation tree for each value. The leaves must quote spans of the transcript, identified by turn and position. The internal nodes are a handful of deterministic operations: copy, concatenate, add, count, and date offset. A value whose leaves cannot be found in what was actually said is rejected rather than trusted.

The second half of the proposal concerns how such a system should be measured. Dialogue state tracking is normally scored by joint goal accuracy (JGA): a turn counts as correct only if every tracked slot is correct. Because each turn inherits the state of the previous one, a single early mistake contaminates every later turn, and one number mixes "how accurate is the model while on track" with "how often does it go off track." Visual object tracking faced the same problem and solved it with reset-based evaluation, which splits performance into separate accuracy and robustness numbers (VOT2013). We port that protocol to spoken dialogue and use it to find out which part of the derivation tree (leaf extraction, aggregation, or ASR noise) causes each failure.

Core Claim

The claim is that most spoken-specific state-tracking errors in SpokenWOZ come from two sources. One is hallucinated values. The other is multi-turn or multi-step values being forced through single-step slot filling. A shallow, transcript-grounded decomposition removes both sources more reliably than either fine-tuning an end-to-end tracker or prompting an LLM to reason freely. "Shallow" here means value, then operation, then quoted spans. This is testable in a way the existing literature does not allow. SpokenWOZ separates cross-turn and reasoning slots, and removing cross-turn slots lifts the best model's JGA to 28.15% (SpokenWOZ). That result tells us where difficulty lives, but it does not diagnose why models fail there.

The closest existing decomposition methods all work on clean written single-turn questions. ProbTree builds question trees and gates between retrieval and parametric knowledge using token likelihoods (ProbTree). RoHT schedules sub-questions across a knowledge base and text (RoHT). Human-written atomic decompositions lift GPT-3 on MathQA from 31.1 to 82.5 F1 (Patel et al.). These papers motivate the design, and Patel et al. also constrain it. They show the "weakest link" failure: once a leaf is wrong, everything above it is wrong. Our response to that failure is to make leaves checkable against the transcript instead of calibrated by likelihood. We also keep the trees deliberately shallow, because SpokenWOZ reasoning slots are short computations, not four-hop Wikipedia chains.

Research Program

Operation vocabulary. The derivation vocabulary is a small declarative set, in the spirit of the authoring languages that made spoken systems buildable by non-specialists. VoiceXML treated speech input as form filling (Bennett et al.). ClippyScript kept state updates deterministic instead of statistical (Seide et al.). Our operations are:

  • COPY(span), which returns a quoted span unchanged;
  • CONCAT(spans), which joins quoted spans in turn order;
  • SUM or COUNT over spans that mention people or items;
  • DATE_OFFSET(anchor, relative expression);
  • NORMALIZE(span, ontology), which maps a quoted span to a value in the domain ontology.

A domain developer extends the system by adding an operation or an ontology, not by collecting training dialogues. This is how the proposal addresses development cost. Visual tools such as DIAGRAPH author static flows. Our operations are instantiated at runtime by the model.

Annotation. We will annotate derivation trees for all cross-turn and reasoning slots in a held-out slice of SpokenWOZ, targeting roughly 1,000 dialogues. Two annotators will label each tree, and we will measure agreement between them. We will also produce manually corrected transcripts for a 300-dialogue subset, so that ASR noise can be separated from reasoning error.

Tree generator and executor. An LLM generates trees from the dialogue history using few-shot prompting, and a fine-tuned variant is trained on SpokenWOZ training dialogues. Gold trees are produced for the training split semi-automatically: we search for operation-plus-span combinations that reproduce the gold slot value, then filter the results by hand. The executor then processes each tree in three steps:

  1. It checks each quoted leaf against the ASR transcript, allowing a phonetic edit-distance tolerance so that misrecognized digits are not dropped outright.
  2. It applies the operations to the verified leaves.
  3. It updates the dialogue state.

A tree with an unverifiable leaf yields no value for that slot. The system then either keeps the previous value or, in the full system, asks the user a confirmation question.

Reset-based protocol. This is the standardization component. At each turn we compare the predicted state with the gold state. At the first divergence we log a failure and score the turn as wrong. We then re-initialize the state to gold at the next turn and continue. This mirrors VOT's automated re-initialization after drift (VOT2013; VOT2019). The protocol yields two numbers:

  • Accuracy: slot-level correctness on turns scored while the tracker has not yet diverged since its last re-initialization.
  • Robustness: failures per 100 turns.

Both numbers are broken down by SpokenWOZ category (cross-turn, reasoning, ordinary) and by transcript condition (ASR versus corrected), following CDnet's lesson that category-level scores reveal failure modes that one average hides (CDnet 2014). We report standard JGA alongside for comparability. Systems whose per-dialogue scores are not significantly different under a Wilcoxon signed-rank test share a rank, as in VOT. We will release the protocol as a scoring script together with the tree annotations.

Baselines

Do-nothing reference. The naive reference is a tracker that carries forward the previous state and fills a slot only when an ontology value appears verbatim in the current ASR turn. It shows how much of SpokenWOZ is solvable by string matching alone. We run it on the identical test split. It needs no tuning.

Strongest published system. The strongest existing method is SPACE+WavLM_aligned, the dual-modal tracker released with SpokenWOZ. It aligns transcript words with acoustic timestamps, and the paper reports 25.65% JGA (SpokenWOZ). It is the strongest competitor because it is trained on the task and sees audio, whereas our system sees text only. We will run the released model on our split under both standard JGA and the reset protocol. Beating it means exceeding its JGA on the full test set and showing lower failures per 100 turns on cross-turn and reasoning slots, with Wilcoxon significance. Matching it with a text-only system would already be informative.

Unconstrained LLM tracker. This baseline uses the same LLM as our generator, prompted with the same few-shot examples to emit the state directly. The reported zero-shot ChatGPT figure is 13.75% JGA (SpokenWOZ). We rerun it with our model and prompt budget, so that differences reflect output structure rather than model choice.

Ablations isolating the key ingredient. Two ablations test which part of the method matters:

  • Flat grounded ablation. The LLM outputs each slot value together with supporting spans, and the same verification is applied, but there are no operations. This isolates grounding from hierarchy.
  • Ungrounded tree ablation. Trees are generated and executed, but leaves are not verified. This isolates hierarchy from grounding.

Every LLM variant gets the same number of prompt-tuning iterations on the development set and the same decoding budget. We also report tokens and latency per turn.

Why not just…?

Why not just fine-tune a stronger end-to-end tracker? This is a real threat. A larger pretrained tracker in the SOLOIST family, which folds understanding, state tracking and generation into one language model (SOLOIST), trained on SpokenWOZ could close much of the gap on ordinary slots. The evidence against it is specific rather than general. Removing cross-turn slots moves the best tracker only from 25.65% to 28.15% JGA, which suggests that single-pass slot prediction struggles with piecemeal values regardless of training. Our category-level reset scores will show whether a fine-tuned tracker's failures cluster on cross-turn and reasoning slots. If they do not, the case for decomposition is weak and we will say so.

Why not just prompt the LLM to reason step by step and call a calculator? Free-form chain of thought can derive "four people" from "me, my wife and two kids." But it does not stop the model from inventing a phone digit that was never said, and that invention is the documented failure mode on spoken transcripts. Linear reasoning also propagates early mistakes (ProbTree). The flat grounded ablation is the honest test of this alternative. If span-cited values without operations match the full trees, the contribution reduces to grounding plus a scoring protocol, and we will report it that way.

Why not just rewrite each turn into a standalone query first? Contextual query rewriting turns "how's the traffic?" into a self-contained sentence and raised downstream slot F1 from 0.89 to 0.91 (CQR). However, a rewrite still produces a sentence. A downstream slot filler must then extract a 16-digit number that the rewrite concatenated from possibly misheard fragments, and nothing checks the rewrite against the audio transcript. We include a rewrite-then-track pipeline in the cross-turn category comparison, using the same LLM for rewriting.

Proposed Experiments

Headline comparison. All systems are compared on the SpokenWOZ test split under standard JGA and under the reset protocol, broken down by slot category. Success means our system beats SPACE+WavLM_aligned's 25.65% JGA, with the gain concentrated in cross-turn and reasoning slots.

First decisive check: grounding versus hierarchy. We compare the full system with the two ablations on the corrected-transcript subset and on the ASR subset. The comparison tells us whether grounding, hierarchy, or both carry the gain, and whether decomposition amplifies ASR errors or isolates them. Amplification would appear as spurious subtrees spawned by misrecognized tokens. Isolation would appear as noisy clauses confined to rejected leaves.

Second decisive check: does resetting change conclusions? If reset-based accuracy and robustness reorder any pair of systems relative to JGA, the protocol exposes trade-offs that JGA hides. If they never reorder systems across SpokenWOZ and a secondary run on written MultiWOZ (budzianowski/multiwoz), the protocol is redundant and we will drop it.

Error attribution. Tree annotations let us attribute every reset-triggering failure to one of three causes: a missed leaf, a wrong operation, or a verified-but-misrecognized span. This produces the diagnostic breakdown that the benchmark currently lacks.