« Phase 01 · Warmup · Track Overview

Deep Dive — Mechanism & Internals

Data structures, algorithms, invariants, complexity, and a step-by-step trace of a run.

Table of Contents

• 1. The transition table as data
• 2. The scratchpad and the compaction algorithm
• 3. Memory: three indices, three keys
• 4. The snapshot and the CAS protocol
• 5. The ring: construction, lookup, and the movement proof
• 6. The run loop, traced
• 7. Invariants
• 8. Complexity
• 9. Determinism sources

1. The transition table as data

TRANSITIONS: Mapping[Tuple[RunState, Event], RunState]
TERMINAL_STATES: frozenset = {COMPLETED, FAILED, CANCELLED}

A dict keyed by (state, event). Two guards in transition(), in this order:

if state in TERMINAL_STATES:  raise IllegalTransition(state, event)
try:    return TRANSITIONS[(state, event)]
except KeyError:  raise IllegalTransition(state, event) from None

The terminal check comes first and is separate from the table. It could be expressed by simply omitting terminal rows — and then a typo that adds one would silently create a resurrectable state. As a separate guard it is one line that cannot be defeated by a table edit, which is the kind of defence you want on an invariant that an auditor cares about.

from None suppresses the KeyError context. Cosmetic, but the traceback an on-call engineer reads at 3 a.m. should say "illegal transition: completed --propose-->", not show them a dict lookup.

The table has 22 edges over 8 states. The full space is 8 × 10 = 80 pairs, so 58 pairs are illegal — and each of those is a bug that cannot happen. Enumerability is the point: you can print the machine into a design document, and a reviewer can check it by reading rather than by tracing code.

2. The scratchpad and the compaction algorithm

State: steps: List[Step], summary: str, max_tokens, keep_recent, compactions.

def compact_if_needed(self) -> bool:
    if self.token_count() <= self.max_tokens:   return False   # (1) under budget
    if len(self.steps) <= self.keep_recent:     return False   # (2) nothing foldable
    cutoff = len(self.steps) - self.keep_recent
    folded, self.steps = self.steps[:cutoff], self.steps[cutoff:]
    new = self.summarize(folded)
    self.summary = (self.summary + " " + new).strip() if self.summary else new
    self.compactions += 1
    return True

Guard (2) is the subtle one. It fires when the pad is over budget and the only steps left are the recent window — and it returns False, leaving the pad over budget. That looks like a bug and is the correct behaviour: the model needs the last step or two verbatim to decide what to do next. Over budget with context is recoverable (the provider may still accept it, or the token budget will stop the run); under budget with amnesia is not. The lab tests this case explicitly with max_tokens=1.

The summary accumulates. Each compaction appends to the previous summary rather than replacing it, so a long run has a summary-of-summaries. This is deliberately naive: real runtimes re-summarize the summary to stop it growing. Left as an extension, but worth knowing that the naive version has a slow leak.

Token accounting is a pure function of the text. token_count() re-renders and re-counts on every call — \( O(\text{total text}) \) each time, called once per loop iteration. At realistic sizes this is microseconds, and the alternative (an incrementally maintained counter) is a cache-invalidation bug waiting to happen. Choosing the recomputation is the right trade at this scale, and knowing why you chose it is the senior part.

3. Memory: three indices, three keys

The two ranking rules differ in their tie-break, and the difference is the design:

• Semantic breaks ties on key — deterministic and stable. A fact does not become more relevant because it was written recently; "the RM for Acme" is as true today as last month.
• Episodic breaks ties on -index, i.e. most recent first. Episodes decay: last week's lesson beats last year's. This encodes recency without a decay function, which would need a clock and would therefore need injecting.

SemanticMemory.search filters before ranking:

visible = [f for f in self._facts.values() if scopes.get(f.scope) == f.owner]
scored  = [(len(wanted & set(f.tags)), f) for f in visible]
scored  = [(s, f) for s, f in scored if s > 0 or not wanted]
scored.sort(key=lambda pair: (-pair[0], pair[1].key))

Note scopes.get(f.scope) == f.owner. A caller who does not hold a scope gets None, which never equals an owner string — so an empty scopes mapping returns nothing, whatever the tags. The alternative formulation (f.owner in scopes.values()) is a real bug: it would let a caller who is user wholesale read tenant wholesale's facts.

The or not wanted clause makes an empty tag list mean "everything visible" rather than "nothing" — a browse operation rather than a search.

4. The snapshot and the CAS protocol

SessionSnapshot is frozen and complete: identity (session_id, tenant, user_id), intent (goal), position (state, steps, summary, pending_question), accounting (tokens_used, cost_micros), concurrency (version), and timing.

The completeness matters: reconstruction is a pure function of the snapshot. run() rebuilds the scratchpad from snapshot.steps and snapshot.summary and nothing else. If any run state lived only in the kernel's local variables, resumption would silently differ from the original run, which is the hardest class of bug to find.

The CAS protocol:

create() → version 1
save(snapshot, expected_version=v):
    current = load(id)
    if current.version != v:  raise ConcurrentModification
    store(replace(snapshot, version=v+1))
    return stored

Three details:

• save returns the stored snapshot, not the caller's. The caller's has the old version; using it for the next save would fail. _checkpoint returns (stored, stored.version) for exactly this reason.
• The version is set by the store, not the caller. A caller-supplied version is a caller-supplied race.
• replace() on a frozen dataclass means every stored snapshot is a distinct immutable object. A mutable snapshot would let a checkpoint change under a reader.

What this does not provide: atomicity across the store and the outside world. Between tool(args) and save(...) the effect has happened and the record has not. See WARMUP §5.3.

5. The ring: construction, lookup, and the movement proof

Construction. For each replica r and i in [0, V), add (blake2b(f"{r}#{i}")[:8] as int, r). Sort by hash. _replicas is kept sorted so that construction order cannot influence the result — two routers built with ["a","b","c"] and ["c","b","a"] produce identical rings, which the lab tests.

Lookup.

point = _hash_to_int(session_id)
candidates = [e for e in self._ring if e[0] >= point] + self._ring   # clockwise, then wrap
for _, replica in candidates:
    if replica not in self._draining:
        return replica

The concatenation implements the wrap: walk from the key's position to the end, then from the start. It is \( O(RV) \) as written; a binary search (bisect) plus a bounded scan would be \( O(\log(RV)) \). At R=20, V=64 the list is 1 280 entries and the constant factor is irrelevant — but the bisect version is the right extension, and knowing that the list comprehension is the slow part is the point of reading the code.

The movement property, proved. Model the ring as the unit circle with replica points placed by a uniform hash. Adding replica d with V points inserts V new arcs; a key moves iff it falls in an arc now owned by d. With n replicas each holding V uniformly-distributed points, the expected fraction of the circle owned by any one replica is \( 1/n \) after the addition — so the expected fraction of keys that move is \( 1/n \), and by construction they all move to d, because no existing point moved.

Contrast modulo: a key stays iff \( h \bmod n = h \bmod (n+1) \). For n=3 → 4 that holds for roughly a quarter of keys, so ~75% move, scattered across all replicas.

The lab tests both halves: the fraction bound (10–45%, wide enough to be robust at 600 sessions) and the stronger invariant that every moved session lands on the new replica.

Draining is a filter at lookup time, not a ring change. The draining replica keeps its points, so removing the drain (a rollback) restores the previous assignment exactly. Removing and re-adding would not — the ring would be rebuilt identically here, but in a weighted or dynamically-seeded implementation it would not, and the habit is worth keeping.

6. The run loop, traced

The scripted policy in solution.py's worked example: look up a payment, screen the beneficiary, call a nonexistent tool, then finish. Clock ticks 0.1 s per call. max_steps=8, scratchpad_max_tokens=120.

Then: final _checkpoint, and because the state is terminal, an Episode is recorded tagged with sorted({lookup_payment, check_sanctions, teleport_funds}).

Three things to notice.

Step 3 is not a failure. The unknown tool produces error="unknown tool: 'teleport_funds'", the state goes ACTING → OBSERVE → PLANNING, and the model sees the error on its next turn. The run completes. This is the recoverable/fatal taxonomy in one row.

Token accounting is asymmetric. decision.tokens_in + decision.tokens_out is added before the dispatch (you pay for the model call regardless of what the tool does); result.tokens and result.cost_micros are added after. A kernel that adds them together after dispatch under-reports when the tool throws.

The step index survives compaction. step_no is derived from pad.steps[-1].index + 1, and after a compaction pad.steps starts at the recent window — so the index continues from where the window starts, not from 1. If it were len(pad.steps) + 1 the chain would restart its numbering mid-run, which would be both confusing and an audit defect. This is why Step.index is stored rather than implied by position.

Resume trace (the HITL section): first run() ends at waiting_input with pending_question persisted. Second run(resume_answer=...) transitions WAITING_INPUT --resume_input--> PLANNING, appends a synthetic step at _next_index(snapshot) recording the human input as an observation, and continues. The human's answer is therefore in the chain, attributable and timestamped — which is the whole point of doing HITL inside the kernel rather than in the channel.

7. Invariants

Each is asserted by at least one test:

1. Terminal absorption — no event applies to a terminal state.
2. No trap states — every non-terminal state has an edge to a terminal state.
3. Recent-window preservation — compact_if_needed never leaves fewer than min(keep_recent, len(steps)) steps.
4. Chain completeness — len(execution_chain(id)) == len(result.steps) even after compactions.
5. Scope confinement — search with scopes={} returns [] for any tags.
6. Single writer — a stale save raises; the store's version is monotone.
7. Routing determinism — same replicas (any order) + same session id → same replica.
8. New-replica-only churn — after add, a moved session is on the new replica.
9. Budget precedence — the policy is called at most max_steps times.
10. Index monotonicity — Step.index strictly increases across a run, including across a resume.

8. Complexity

9. Determinism sources

No wall clock (now is injected and ticks a fixed increment in tests), no RNG, no uuid4, no hash(). Identifiers are derived: step indices from a counter, episode ids from f"{session_id}#{len(episodic)+1}", ring points from a stable digest.

Two places where non-determinism could sneak in and does not:

• Dict iteration in SemanticMemory.search. Python dicts preserve insertion order, but the sort's tie-break on key makes the result independent of it anyway.
• Set ordering in the episode tags. tuple(sorted({s.tool for s in pad.steps if s.tool})) — the sorted is load-bearing; without it the tag tuple varies by set iteration order and two identical runs produce different episodes.

The test test_two_identical_kernels_produce_identical_runs compares steps, counters, and the full execution chain across two independently constructed kernels. If any of the above regressed, it fails.