## Context

v1.3.1 ships exhaustive decision-tree search. Per-cell ceilings and top-K plans are correct, but every pin/unpin click triggers a full re-search (~7s for an 8-open-set scenario). The compute is wasteful: leaf outcomes are pure functions of `(courseAssignments, ranking, mode)`. A leaf evaluated once stays correct as long as ranking and mode don't change.

Today the search effect in `useAppState` (`appState.ts:124-191`) lists `[selectedCourseIds, openSetIds, ranking, mode, excludedCourseIds]` as deps. Any change kills the running worker and starts a fresh search after a 300ms debounce.

This change adds an in-memory cache of leaf outcomes keyed by the existing `assignmentKey`. Pin operations become 100% cache hits (no worker). Unpin operations get a partial hit (cached subset rendered immediately, missing leaves computed in the background).

## Goals / Non-Goals

**Goals:**
- Pin clicks produce instant top-K + per-cell updates with no spinner
- Unpin clicks render the cached subset immediately as a lower bound, then improve as the worker streams new leaves
- "Adopt plan" (which fires multiple pin actions in quick succession) feels instant
- Cache memory is bounded (~80 MB worst case at the 500k cap)

**Non-Goals:**
- Persisting the cache across page reloads (no localStorage; recompute on first use after reload)
- Caching across ranking or mode changes
- Re-architecting the optimizer or worker protocol beyond the new `skipKeys` field
- A "tree of caches" keyed by ranking — keep one cache, invalidate on ranking change

## Decisions

### Cache key = `assignmentKey` only; cache scope = `(ranking, mode)`

`assignmentKey` already exists (`decisionTree.ts:79-84`) and is the deterministic stringification used by the comparator's tiebreaker. Reusing it avoids a parallel hashing scheme. Cache scope is bound to the current `(ranking, mode)` pair: when either changes, the cache is wiped and rebuilt from scratch on the next search.

**Alternative considered:** Keep multiple caches, one per `(ranking, mode)` pair the user has visited. Rejected — extra complexity for a workflow where ranking/mode changes are infrequent compared to pin clicks. If profiling later shows ranking-toggle becoming a hot path, can add then.

### Immediate render on partial hit (unpin), then stream improvements

When the user unpins a set, the new openSetIds product is larger than the cached subset. Today's UX would block on a fresh worker. Instead:

1. Filter the cache against the new pinned + excluded state. Derive top-K and per-set ceilings from the filtered leaves. Render immediately.
2. Compute missing leaves count. If non-zero, spawn the worker with `skipKeys = cache.keys()`. The worker DFS visits every leaf in the new search space but skips the optimizer call for keys already cached.
3. As the worker streams new leaves (existing `topKUpdate` / `choiceUpdate` events plus a final `allComplete`), insert each into the cache and re-derive top-K/ceilings via the existing streaming path.

The cached subset is a strict lower bound on the true result: top-K from cache is a valid (possibly incomplete) subset of the true top-K; per-set ceilings from cache are ≤ the true ceilings. Streaming improvements are monotonically non-decreasing under the existing comparator.

**Alternative considered:** Show a spinner and wait for the search to complete before rendering. Rejected — would feel like a regression after pin became instant. The streaming UI already handles monotonic improvement gracefully.

### Worker contract: `skipKeys: string[]`

The simplest extension. Main thread serializes `cache.keys()` to an array; worker reconstructs the Set on the receiving end. For 65k cached keys × ~30 chars each = ~2 MB transfer per worker spawn. structured-cloned in tens of milliseconds. Acceptable.

**Alternative considered:** Persistent worker that holds the cache internally. Rejected — adds lifecycle complexity (when to terminate, how to abort in-flight work, race conditions on cache writes). The fresh-worker model already exists and the transfer cost is bearable.

### `evaluateLeaf` short-circuit semantics

When a leaf's key is in `skipKeys`:
- Increment `iterations` (so progress reflects total leaves visited, not just newly-computed)
- Skip the optimizer call, skip `topK.tryInsert`, skip `choiceUpdate` emit
- Skip `evaluated` flag updates (those cells were already marked from the cached results on the main thread)
- Still emit `progress` events at the throttled rate

Rationale: the user-visible "iterations explored" should reflect tree size, not just delta. Otherwise an unpin would show "Searching… 100,000/200,000" jumping from 100k mid-search, which is confusing.

**Alternative considered:** Don't increment iterations for skipped leaves. Rejected — the percentage in the progress bar would be misleading.

### `deriveFromLeaves` extracted as a pure helper

To produce top-K and per-set ceilings from a leaf collection on the main thread, factor out the relevant logic from `searchDecisionTree`. The helper takes `(leaves, K, mode, ranking, openSetIds, excludedCourseIds)` and returns `{ topK: PlanOutcome[], setAnalyses: SetAnalysis[] }`.

The worker uses the same helper at `allComplete` to produce its final emission. The main thread uses it for the immediate-render path.

**Alternative considered:** Maintain top-K and per-set ceilings incrementally in the cache structure itself. Rejected — too coupled; recomputing from leaves is O(cache.size) which is fast (linear scan + small comparator work).

### Cache cap = 500k leaves with full clear on overflow

500k × ~300 bytes ≈ 150 MB. Comfortable on desktop, snug on mobile. Tripping the cap requires extreme exploration paths (≥10 open sets + repeated cycles); typical sessions stay under 100k.

When the cap fires, clear the entire cache. Simplest possible policy. Subsequent searches behave as v1.3.1 (full recompute).

**Alternative considered:** LRU eviction. Rejected for v1 — adds bookkeeping overhead per insert; benefit is marginal given cap is rarely hit. Add later if profiling shows churn.

### Cache invalidation events

| Event | Cache action |
|---|---|
| Pin a course | Keep cache; filter |
| Unpin a course | Keep cache; filter (partial hit) |
| Adopt plan | Keep cache; filter |
| Ranking re-order | Clear cache; re-search from scratch |
| Mode toggle | Clear cache; re-search from scratch |
| Cancellation toggle (data file edit) | Clear cache (data version changed) |
| Cache size exceeds 500k | Clear cache |

The ranking/mode/cancellation changes are uncommon compared to pin clicks, so the simplification is worth it.

## Risks / Trade-offs

- **Memory footprint** → Mitigation: 500k cap clears the cache when exceeded; typical sessions stay well under
- **Worker transfer of `skipKeys`** → ~2 MB per worker spawn at 65k cached keys; acceptable, measure and revisit if it becomes painful at scale
- **Cached subset can briefly disagree with worker's final result** during streaming → Existing streaming UI handles monotonic improvement; the only visible effect is some cells starting at a lower count and improving as the worker fills in
- **Iteration counter semantics** during skip-mode runs → Counts total leaves visited (cached + new). Decision documented above; clear in the proposal scenarios so users understand "Searching… 50,000/200,000" early in an unpin run
- **First-time experience unchanged** → Empty cache means full search; no improvement on initial page load. Subsequent operations are where the win happens

## Migration Plan

Single-PR change. No data migration. No persistent state to migrate.

1. Implement `skipKeys` plumbing through `searchDecisionTree` and worker
2. Extract `deriveFromLeaves` helper
3. Add cache to `useAppState`; restructure the worker effect to filter-then-spawn
4. Tests for skip-keys correctness, derive helper parity, cache-cap eviction, ranking/mode invalidation
5. Browser verify: pin/unpin behave instantly after the first search
6. Bump version (`1.3.2`); CHANGELOG entry; ship

Rollback: revert. v1.3.1 behavior restored — every pin/unpin runs a fresh worker.

## Open Questions

- Memory measurement on representative scenarios (8-set typical, 10-set extreme) — instrument once for the changelog notes
- Whether `skipKeys` transfer becomes a bottleneck at very large cache sizes — defer; haven't observed it in typical use
- Whether to expose a debug toggle to disable the cache (useful for A/B feel testing) — defer; can add as a query param if needed