SESM — Self-Expanding State Machine

An experiment by Guru Cloud & AI: a finite state machine that starts sparse and grows.

A Pydantic model defines a bounded state space — the Cartesian product of its finite field domains (Literal[...], bool). The FSM explicitly maps only the combinations it has been taught. When a live instance lands on a combination that is valid but unmapped (or fails validation), that is not a crash — it is a discovery: a signal that the state space has territory nobody has mapped yet. A pluggable handler reacts — in our deployments that handler dispatches an AI agent to analyze the combination and propose whether to add a new named state, map it to an existing one, or flag a bug.

                 ┌───────────────────────────────┐
   event ──────► │  transition / apply_values    │
                 │                               │
                 │  1. Pydantic validation       │──✗──┐
                 │  2. validate_state() rules    │──✗──┤
                 │  3. explicit-state lookup     │──✗──┤
                 │                               │     ▼
                 │  ✓ new named state            │  DiscoveryEvent
                 └───────────────────────────────┘     │
                                                       ▼
                                    DiscoveryHandler(s): webhook,
                                    queue, function, agent, human…

Why bounded?

Because the ceiling is computable (compute_state_space_ceiling), coverage is a real metric: 6 of 24 states mapped = 25%. The FSM cannot grow without limit — discovery is coverage exploration of a finite space, not open-ended state invention. Schema evolution (adding variables or domain values, which changes the ceiling) is deliberately not the FSM's job; that belongs to your Pydantic model and your type checker.

Install

pip install sesm            # from PyPI
pip install -e .[dev]       # from a checkout, with test deps

Quickstart

from typing import Any, Literal
from pydantic import BaseModel
from sesm import SESMBase, InMemoryDiscoveryRecorder, WebhookDiscoveryHandler


class OrderState(BaseModel):                      # ceiling = 4 × 3 × 2 = 24
    payment: Literal["pending", "authorized", "captured", "refunded"]
    shipping: Literal["unfulfilled", "shipped", "delivered"]
    dispute: bool


class OrderFSM(SESMBase[OrderState]):
    @property
    def state_model_class(self):
        return OrderState

    @property
    def explicit_states(self) -> dict[str, dict[str, Any]]:
        return {
            "new_order": {"payment": "pending", "shipping": "unfulfilled", "dispute": False},
            "shipped":   {"payment": "captured", "shipping": "shipped",   "dispute": False},
            # ...only the combinations you have mapped so far
        }

    @property
    def transitions(self) -> dict[tuple[str, str], str]:
        return {("new_order", "ship_item"): "shipped"}


recorder = InMemoryDiscoveryRecorder()
fsm = OrderFSM(discovery_handlers=[recorder])

fsm.coverage                     # 2 / 24 ≈ 0.083
result = fsm.transition("new_order", "ship_item")          # ✓ "shipped"

result = fsm.apply_values(                                  # valid combo,
    "shipped",                                              # but unmapped →
    {"payment": "captured", "shipping": "shipped", "dispute": True},
    trigger_event="dispute_opened",                         # discovery!
)
result.discovery_triggered       # True
recorder.events[0].error_type    # "unmapped_state"

The reaction is yours to define

The framework never prescribes what a discovery does. DiscoveryHandler is a one-method protocol:

class DiscoveryHandler(Protocol):
    def handle(self, event: DiscoveryEvent) -> None: ...

Ship your own, or use the included ones:

Handlers compose — pass several and every discovery fans out to all of them. For an agent-driven loop, point a WebhookDiscoveryHandler at whatever dispatches your agent, or write a five-line handler that calls your agent runtime directly.

Validation funnel

Every transition (table-driven transition()) or direct assignment (apply_values()) passes through three gates, and a failure at any gate can trigger discovery:

1. Pydantic — type/domain errors (error_type="pydantic_validation")
2. validate_state() — your domain rules, raise StateValidationError (error_type="state_validation")
3. Explicit-state lookup — valid but unmapped combination (error_type="unmapped_state")

A missing transition (unknown (state, event) pair) fails cleanly without discovery — that is an API misuse, not uncharted state space.

The self-expanding loop (LLM analyst)

MutableSESM holds its definition in data instead of code, so it can be taught at runtime. LLMDiscoveryAnalyst closes the loop with any LLM — you hand it a complete: Callable[[str], str] (OpenAI, Anthropic, a local model, a stub in tests) and it turns a discovery into a validated proposal:

from sesm import MutableSESM, LLMDiscoveryAnalyst, apply_proposal

fsm = MutableSESM(OrderState, explicit_states={...}, transitions={...},
                  validate=my_domain_rules)          # rules optional
analyst = LLMDiscoveryAnalyst(complete=my_llm_call)  # any provider

proposal = analyst.analyze(fsm, event)   # add_state / map_to_existing / bug
if proposal.action == "add_state":
    apply_proposal(fsm, event, proposal) # definition grows; combo now maps

Proposals are schema- and semantics-validated (no colliding names, map_to_existing must name a real state, add_state only for genuinely unmapped combinations); invalid replies are re-prompted with the failure reason so the model corrects itself, bounded by max_attempts.

Live demo (examples/openai_demo.py, gpt-5.4-mini, reasoning_effort="none", output in examples/demo_evidence.json): starting from the 6/24-state order FSM, the analyst turned two legitimate gaps into well-named states that remapped cleanly and flagged delivered-but-never-paid as a bug, growing coverage 25% → 33.3% in one pass.

The proof

experiments/ contains a full blinded evaluation against a 75-combination order domain with oracle ground truth the analyst never sees — all 68 unmapped combinations judged per arm, plus 200-event convergence runs. Full scored report with figures: experiments/results/REPORT.md.

Headlines (all reasoning_effort="none", ~$0.02 total):

• Mechanics: flawless. 334 LLM analyses across all committed runs: 0 protocol failures, 0 misuse of map_to_existing, and every accepted add_state proposal (162/162) remapped its combination on the next attempt.
• Blind judgment is honest but limited — 59–63% verdict accuracy. The misses are systematic: business-specific rules can't be guessed from a schema. One neutral context paragraph nearly triples bug detection (19% → 50% recall); the residual misses concentrate exactly where reasonable businesses differ (ship-on-auth vs ship-on-capture).
• The layered design closes the gap by construction. In convergence runs on identical event streams: the blind FSM converges but over-expands to 74.7% coverage — past the 65.3% valid region (19 invalid states admitted). The guarded FSM (known rules wired as validate=) admits zero invalid states, because add_state is structurally illegal for rule-violating discoveries. Dedup keeps LLM spend sublinear: 65 analyses over 200 events, front-loaded and flattening.

Watch it happen: viewer/ builds a click-through replay of both convergence runs — the state-space map filling in turn by turn, each analyst verdict with its reasoning, invalid admissions glowing red in the blind run and validate= blocks in the guarded one (python -m viewer.build → viewer/dist/index.html).

Status & roadmap

Experimental (v0.1.0). Extracted from the GuruCloudAI platform where the design went through several human-review iterations (bounded-space model, two-tier discovery vs. schema evolution split). Possible next steps:

• Proposal loop: structured LLM verdicts (add state / map to existing / bug) with validation-retry, applied to a mutable definition
• Blinded oracle evaluation + convergence proof (experiments/)
• Persistence protocol + reference SQLAlchemy store (definitions, instances, discovery events)
• Human-approval gate between proposal and apply
• Coverage/discovery metrics surface
• PyPI release (pip install sesm)

Development

pip install -e .[dev]
pytest -q