Cornerstone Engineering Monograph · UK Patent Pending

Eliminating O(N x M) Graph Spaghetti: Pushdown Automata (TaskStack) for Conversational Digressions

Why flat directed graphs explode into O(N x M) edges when users ask off-topic questions mid-form, and how Blockstate uses a bounded LIFO pushdown automaton (TaskStack) to isolate and resume conversations cleanly.

1. Why Flat Directed Graphs Collapse on Human Digressions

Every conversational workflow looks clean on a whiteboard when you only draw the happy path:

$$\text{Verify Identity} \longrightarrow \text{Collect Claim Details} \longrightarrow \text{Assess Damage Tier} \longrightarrow \text{Disburse Payout}$$

Then real human customers interact with the system. Halfway through providing the six fields required for a motor insurance claim, right after giving their policy number (POL-884120) and incident postcode (M1 1AG), the customer pauses and asks:

"Wait, before I give you the street name and garage quote, will claiming for a cracked bumper affect my no-claims discount?"

In a flat Finite State Machine (FSM) or a standard directed graph runner (such as a manual LangGraph node/edge topology), supporting $M$ off-topic FAQ or clarification handlers across $N$ data-collection stages requires:

• Routing conditional edges from every collection stage $n_i \in \{1 \dots N\}$ to every FAQ handler $m_j \in \{1 \dots M\}$;
• Maintaining manual return-stage pointers in global state dictionaries so the FAQ handler knows which collection node to jump back to; and
• Ensuring the FAQ handler's prompt or tools do not accidentally overwrite or clear the partial fields already collected in stage $n_i$.

This creates $\mathcal{O}(N \times M)$ edge explosion. For a 10-stage mortgage or insurance workflow with 8 FAQ topics, a developer must wire and test 80 cross-cutting return edges.

2. From Finite State Machines to Pushdown Automata (TaskStack)

In formal language theory, nested interruptions with guaranteed return-to-origin semantics are modelled by a Pushdown Automaton (PDA): a state machine equipped with a Last-In, First-Out (LIFO) call stack.

Blockstate implements a two-tier memory architecture in src/blockstate/core/stack.py (Claims 5 & 6):

1. Global SessionState Tier: Holds persistent session metadata, the encrypted PIIVault token map, and the monotonic revision counter.
2. Bounded LIFO TaskStack Tier: A stack of isolated TaskFrame instances. Each TaskFrame encapsulates its own stage_name, hydrated slot dictionary, dot-separated locked_slots set, turn counter, and allow_slot_overrides policy flag.

sequenceDiagram
    autonumber
    actor User as "Customer"
    participant Stack as "TaskStack (LIFO)"
    participant Gate as "ToolGatekeeper"
    participant RAG as "query_policy_handbook_rag"

    User->>Stack: Turn 1: "Policy POL-884120, personal use, bumped in Manchester M1 1AG"
    Note over Stack: Frame[0] ('intake_claim'): Lock 4 validated leaves.<br/>Compute Delta = {location.street, estimated_damage_gbp}
    Stack-->>User: "What is the street name and estimated damage?"

    User->>Stack: Turn 2: "Wait, will a bumper claim under £250 affect my no-claims bonus?"
    Note over Stack: Push Frame[1] (stage='ncd_policy_faq', allow_slot_overrides=False)<br/>Frame[0] suspended with 4 locked slots untouched
    Stack->>Gate: Construct MappingProxyType for 'ncd_policy_faq'
    Gate->>RAG: query_policy_handbook_rag(topic="no-claims bonus")
    RAG-->>Gate: "Claims under £250 do not affect NCD."
    Note over Stack: Execute Transition.pop_frame()<br/>Pop Frame[1], restore Frame[0] ('intake_claim')
    Stack-->>User: "Policy Handbook: Claims under £250 do not affect NCD. What is the street and cost?"

3. Declarative Digression Wiring in Python 3.12+

With TaskStack, declaring a digression requires zero manual return edges:

class MotorInsuranceClaimAgent(Agent):
    @Stage(
        name="intake_claim",
        initial=True,
        collect=MotorClaimSlots,
        allow_digressions=["ncd_policy_faq", "excess_fee_faq"],
        allow_slot_overrides=False,  # Child frames cannot mutate parent slots
        on_breach="commercial_fleet_desk",
        on_max_turns_exceeded="human_claims_handler",
        max_turns=6,
    )
    @Transition(targets=("tier_auto_payout", "tier_adjuster_review"))
    async def intake_claim(
        self, slots: MotorClaimSlots
    ) -> Transition["tier_auto_payout" | "tier_adjuster_review"]:
        if slots.estimated_damage_gbp <= 250.0:
            return Transition.to("tier_auto_payout")
        return Transition.to("tier_adjuster_review")

    @Stage(
        name="ncd_policy_faq",
        tools=["query_policy_handbook_rag"],
        max_turns=2,
    )
    async def ncd_policy_faq(self, query: str) -> Transition[None]:
        excerpt = await self.tools.query_policy_handbook_rag(topic=query)
        # Pop the child frame and return automatically to whichever parent stage pushed it!
        return Transition.pop_frame(message=f"Policy Handbook: {excerpt}")

Adding a new FAQ handler to 10 collection stages reduces from $\mathcal{O}(N \times M)$ edges to $\mathcal{O}(N + M)$ declarations.

4. Security Invariants on the Call Stack (BLK-SEC-002 & BLK-SEC-003)

To prevent adversarial abuse of the pushdown automaton, TaskStack enforces three strict runtime invariants:

1. Bounded Stack Depth (BLK-SEC-003): If a user attempts to chain recursive digressions beyond the configured max_stack_depth, TaskStack.push() raises StackOverflowError (BLK-SEC-003), halting the loop deterministically.
2. Dot-Separated locked_slots Immutability (BLK-SEC-002): When a leaf field on the parent frame (e.g. location.postcode or policy_number) passes validation, its dot-separated path is added to locked_slots. Any attempt to overwrite a locked slot when allow_slot_overrides=False raises UnauthorisedMutationError (BLK-SEC-002).
3. Controlled SlotMutation on Transition.pop_frame: When a child frame pops via Transition.pop_frame, any explicit SlotMutation payload is verified against the parent frame's allow_slot_overrides and locked_slots policy before merging.

5. Step Through a Live TaskStack Trace

Run Scenario 3 in the Blockstate Interactive Simulator to inspect the live TaskStack frames, locked_slots, and TurnLedger hashes across a multi-turn motor insurance claim.

Statutory Notice: Blockstate is UK Patent Pending ("Process execution control system", UKIPO priority filing 28 October 2026, UK Patents Act 1977 s.62(1)) and distributed under a Source-Available Dual Licence (LICENSE & PATENTS.md).