app/src/content/chapters/06-prediction.mdx

import HtmlEmbed from '../../components/HtmlEmbed.astro';
import Wide from '../../components/Wide.astro';
import Note from '../../components/Note.astro';
import Sidenote from '../../components/Sidenote.astro';
import Accordion from '../../components/Accordion.astro';

# Prediction: Next Step and Failure

The same FSM state answers both questions an operator asks: what the agent will do next, and whether this run is heading for failure. The estimand is one object, the per-state transition distribution, and compactness is what makes it reliable.

## Next-Step Prediction

At each step the predictor estimates $P(a_t \mid \text{context})$, scored by [cross-entropy](https://texonom.com/fefc71fd930a41a7842f39bccb3abcc9) in bits via 5$\times$5-fold [cross-validation](https://texonom.com/184e7cfc80d6410188922d27ef4ef52c) (CV). Conditioning on FSM state alone, with no learning beyond an [order-1 Markov model](https://texonom.com/3bde15938b6b4c79981a3e0523b9877d), accounts for 83 to 99% of the total cross-entropy improvement on each dataset. The average drops to **0.93 bits**, a **62% cut** from the unigram baseline at 2.44 bits.

<Sidenote>
RPNI goes the other way: 3.40 bits, worse than a unigram. Its state count, from hundreds to tens of thousands, spreads each transition estimate too thin, so the per-state distributions are noise.
</Sidenote>

The cleanest test holds the predictor fixed and adds FSM state as a feature. Under absolute discounting, FSM state conditioning adds **+0.155 bits on average** (0.580 vs 0.735) and helps on every one of six datasets, from +0.016 on SWE-agent to +0.364 on Mind2Web, whose branching web-action vocabulary gains most from knowing where in the workflow it is. Combine FSM state with a small learned model and you get the best predictor in the study at **0.73 bits**.

## Workflow Memory

The gain generalizes to the agent's own LLM. Feeding the current FSM state as context for choosing the next action beats Agent Workflow Memory (AWM) [@wang2024agent_workflow_memory] on **all eight** ground-truth datasets, with six gaps significant at $p < 10^{-8}$.

| Dataset | N | AWM | Ours | Δ |
|:--------|--:|----:|----:|--:|
| WebArena | 4,800 | 65.5 | **81.2** | +15.7 |
| SWE-smith | 300 | 74.7 | **100.0** | +25.3 |
| SWE-agent | 1,200 | 67.7 | **70.5** | +2.8 |
| tau2-bench telecom | 1,095 | 28.5 | **45.6** | +17.1 |
| tau2-bench retail | 1,095 | 52.9 | **65.1** | +12.2 |
| tau2-bench airline | 480 | 56.5 | **57.3** | +0.8 |
| ATBench | 600 | 47.8 | **62.5** | +14.7 |
| OSWorld | 1,286 | 55.0 | **70.7** | +15.7 |

AWM extracts workflows from successful traces only, so on low-success datasets it has little to say. That is exactly where the gap is widest.

<Note variant="danger" title="The win is not automatic">
Handing the LLM the full FSM, every state and transition, actually loses to AWM (52.2% vs 52.9% on tau2-bench retail). Dumping the whole graph drowns the next-step signal. The format that wins at **65.1%** is minimal: next-action probabilities plus a few top continuations from the current state, with no structure dump. Finding the right minimal context is part of the contribution, the same way AWM's linear-workflow format is part of its.
</Note>

| Context given to the LLM (tau2-bench retail) | Top-1 % |
|:---------------------------------------------|--------:|
| No memory, just the trace so far | 27.6 |
| Linear workflows from successful runs (AWM) | 52.9 |
| Full machine: current state, every transition, the whole graph | 52.2 |
| Full machine, plus multi-step continuations | 49.2 |
| Full machine, from successful traces only | 50.3 |
| **Minimal: next-action probabilities and a few likely continuations** | **65.1** |

Step through the workflow-memory comparison per dataset in the [memory view](https://seongland.com/article/asg/browser?tab=memory).

## Predicting Failure

Replay a trace through the FSM and read off **per-state behavioral features** (visit frequency, message-length statistics, error rate, early/late entropy drift) plus five cross-entropy anomaly features. A single [gradient-boosted](https://texonom.com/b841ada1c339440eb058a4d3654cf5a7) classifier on a fixed 80/20 split reaches held-out AUROC **up to 0.94**.

<Note>
Raw fitness is useless here (AUROC near 0.50): successful and failed traces both replay perfectly. The signal is in the **per-state decomposition** and in *surprise*, failing traces take low-probability transitions under the FSM.
</Note>

Failure prediction scales with machine size: more states give a finer map of where a run can go wrong. The 43-state telecom agent tops out at **0.941**; WebArena (0.903) and AgentNet (0.890) follow; SWE-agent, with 25 states, reaches 0.799. ATBench, the only safety-labeled benchmark, reaches 0.894 (0.864 ± 0.024 under repeated CV). Across all eight real-trace datasets the CV standard deviation stays in 0.012 to 0.031, so these are not single-split artifacts.

<Wide>
<HtmlEmbed
  src="embeds/failure-features.html"
  title="Failure Prediction"
  caption="Held-out AUROC across the nine labeled datasets, with the top predictive feature for each. Larger FSMs (more states, more tools) predict better."
/>
</Wide>

Inspect per-state feature importances and failure modes in the [failure view](https://seongland.com/article/asg/browser?tab=failure).

The predictors are interpretable. On SWE-agent the single strongest feature is whether the trace reaches the `submit` state: 94.8% of successes get there, only 55.7% of failures do. And this is not a length proxy, structural features score 0.790 against 0.659 for trace length alone. Successful runs touch only 9 of 25 states along a focused `search`, `edit`, `submit` path, while failures spread across all 25 (Jaccard overlap 0.206).

## Runtime Monitor

Deployed online, a two-rule monitor fires when the cycle-rate exceeds 0.778 and the unique-state count clears a warm-up floor. On all four evaluated datasets it reaches **rank-AUROC 0.66 at the 25% trace checkpoint**, against 0.5 for a flag-everything baseline by construction. On SWE-agent it fires at **32% of trace completion**, stopping the run before two-thirds of its remaining compute is spent (precision 85.9%, recall 95.5%). By the halfway checkpoint, FSM features alone already recover 92% of the full-trace signal.

<Note variant="info" title="Why rank-AUROC, not F1">
When 84% of runs fail, flagging everything scores a high [F1](https://texonom.com/10b78f54e2d1464ba65e8709f2679ff2) by default (0.914, versus the monitor's 0.904). The point of a monitor is not whether to flag but *when*. Rank-AUROC measures exactly that early-warning utility, which a base-rate-inflated F1 hides. The pipeline is FSM replay only, 0.006 ms per step, with no ML model in the loop.
</Note>

Watch the monitor flag a failing run in real time in the [monitor view](https://seongland.com/article/asg/browser?tab=monitor).