State count grows past what you can test

What it is

Dialogue state is not the handful of prompt boxes on the diagram. It is the tuple slot values × retry counts × confirmation flags × error types. Each added slot or confirmation multiplies reachable combinations; it does not add them. Once that product outruns scripts and people, the uncovered cells are where users get stuck in scenes nobody rehearsed. Testability is eaten by quantity, not by a missing exit on one node.

Why it happens

Linear narrative (“one more question”) fits design meetings; actual state is a Cartesian product. Six slots each empty / filled / low-confidence, times zero-to-two retries, times confirm-or-not, is already hundreds of cells. Ten happy-path scripts cover an additive slice and miss the multiplicative corners: slot three low-confidence, slot one already confirmed, user suddenly changing slot two. Those corners appear only in production, as “occasional freezes.”

Enumerating every combination forces copy-pasted nodes; a missed edge then makes explosion and traps arrive together. The root is the product, not the missed edge. A frame plus a policy (what the frame holds; ask the highest-priority empty slot) collapses what must be enumerated. The test surface becomes the policy rules plus typical frames, not every cell.

Studying it

Derive reachable state count (or the number of equivalence classes of frames) from the spec, then compare with states actually visited by scripts and by logs. Dependents: coverage, count of states that appear in logs but never in tests, and task-failure rate in those states. Pairwise combinatorial tests (value of slot A × value of slot B) can stand in for the full product; check whether leftover higher-order interactions still hurt in logs.

Number of test cases is a bad progress metric: ten cases that are all success chains barely touch the product. Computing reachable count before and after adding a slot dismantles the “it's just one more question” additive illusion.

Where it stops holding

One-shot, slotless skills barely have a product. Tiny keypad menus (four nodes) can be exhausted. Prompt-based large-model dialogue has no explicit nodes; the explosion becomes implicit — behavior of the same sentence under different histories cannot be enumerated — so testability is worse, not waived. Professional dispatch systems can have huge theoretical state, but user paths repeat; effective state is much smaller than the grid, and coverage can follow real paths rather than theoretical cells.

Applying it

• Before adding a slot, a retry, or a confirmation, compute the multiplier: new reachable count, and what fraction of it current scripts still cover. If the multiplier cannot be written down, do not add yet.
• Do not draw a node per slot combination. Represent filled content as a frame and decide the next question with a few rules. Merge equivalent states, then test.
• A test set should at least cover: empty opening, fully filled first utterance, changing one already-filled slot mid-way, and a single slot failing to its retry cap. Pairwise combinations beat another pile of success chains.
• How to check: mark every production state as script-visited or not. A log state with no mark gets a test or a merge, not another happy-path demo.

Related

• Same group: M2.07.1 Happy-path-only flows leave failure and walk-away unspecified · M2.07.2 Every dialogue state needs a way out · M2.07.3 A flowchart is not a substitute for real utterances · M2.07.4 Slot filling should accept scrambled order · M2.07.5 Cancel, restart, and help must work from every state
• Nearby: M1.03 Dialogue turns · M2.03 Confirmation strategies · M1.05 Topic switching and task nesting
• Search terms: state-space explosion · combinatorial testing · frame-based dialogue