emba-course-solver/openspec/changes/decision-tree-leaf-cache/proposal.md at main

Files

T

Bill ee7ea352c4 v1.3.2: Leaf cache for instant pin/unpin + TopPlans block UX

Decision-tree leaf outcomes are now cached on the main thread keyed by
their full 12-course assignment. Pin operations filter the cache and
re-derive top-K + per-set ceilings instantly with no worker spawn. Unpin
operations show the cached subset immediately and stream improvements as
a background worker fills in the missing leaves. Cache survives pin,
unpin, and adopt-plan; only ranking or mode changes invalidate it.

Solver / worker:

- searchDecisionTree accepts skipKeys (Set<string>) and pinnedAssignments
  (Record<setId,courseId>). Leaves are emitted with their full 12-set
  assignment so cache keys are stable across pin/unpin operations.
- evaluateLeaf short-circuits when the leaf's assignmentKey is in
  skipKeys: increments iterations + emits progress, but skips the
  optimizer call and all callbacks. Keeps progress percentage honest
  (counts whole tree, not just delta).
- New deriveFromLeaves pure helper produces {topK, setAnalyses} from a
  leaf collection; used by the main-thread cache filter and gives a
  reusable derivation primitive for tests.
- Worker request gains skipKeys and pinnedAssignments fields. Worker
  response gains a leafEvaluated event so the main thread can populate
  its cache as the search streams.

App state:

- leafCacheRef holds Map<assignmentKey, PlanOutcome> scoped to the
  current (ranking, mode) pair. The search effect now: invalidates on
  ranking/mode change; computes the orderedCourses + expectedTotal;
  filters the cache against the current pinned/excluded state; calls
  deriveFromLeaves to render immediately; spawns the worker only when
  filtered.length < expectedTotal, passing skipKeys.
- Cache cap of 500,000 leaves with full clear on overflow. Bounds
  worst-case memory at ~150 MB.

UI (TopPlans):

- Course blocks in the per-plan row are now interactive buttons. Click
  pins (or unpins, if the course is currently pinned) the course in
  that set. Pinned blocks render in a selected blue color.
- Each plan row now shows the FULL 12-set sequence including pinned
  courses (interleaved with the search's recommended choices for the
  remaining open sets) so the displayed plan is always complete.
- Spec qualification tags removed from per-block display (kept the
  set-label + course-name treatment for clarity).

Tests:

- New app/src/solver/__tests__/leafCache.test.ts with 4 tests:
  skipKeys parity (second-pass run with skipKeys evaluates zero
  leaves), deriveFromLeaves parity (matches a fresh search), cache
  filter on pinned assignments, cache filter on excluded courses.
- All 78 prior tests continue to pass; 82 total.

Browser-verified: pin click on a Top Plans block from the cached
8-open-set scenario completes instantly with no spinner; unpin restores
the original cached subset (also instant when the prior space was
already cached); mode toggle correctly invalidates and re-runs the
search.

2026-05-09 16:27:52 -04:00

4.0 KiB

Raw Permalink Blame History

Why

After v1.3.1 made the decision-tree search exhaustive, every pin/unpin click triggers a fresh full search (~7s in the worker for the user's typical 8-open-set scenario). That re-run is wasteful: a leaf's outcome (achievedSpecs, priorityScore) depends only on its 12-course assignment plus ranking and mode. Pinning or unpinning a course never changes the value of any leaf that has already been evaluated; it only changes which leaves are reachable in the current search.

We should cache evaluated leaves and re-derive the top-K and per-set ceilings from the cache when pin/unpin operations leave ranking and mode untouched. Pin operations become 100% cache hits (instant). Unpin operations get a partial cache hit — show the cached subset immediately as a lower-bound result, then run the worker to fill in only the leaves that haven't been evaluated yet.

What Changes

Add a main-thread leaf cache: Map<assignmentKey, PlanOutcome> keyed by the existing assignmentKey (sorted setId:courseId join). Cache instance is held in a ref on useAppState.
Cache invalidation triggers: any change to state.ranking, state.mode, or the cancellation list (data version). Pin, unpin, and adopt-plan operations leave the cache intact.
New effect logic in useAppState: when the search-effect dependencies change, first FILTER the existing cache against the new pinned/excluded state and derive top-K + per-set ceilings from the filtered subset, rendering immediately. Then check whether the filtered count equals the expected cartesian-product size; if not, spawn a worker to compute the missing leaves only.
Add an optional skipKeys: Set<string> parameter to searchDecisionTree and to the worker's WorkerRequest. In evaluateLeaf, leaves whose assignmentKey is in skipKeys are skipped entirely — no optimizer call, no callback emit, no iteration counted toward progress (or counted but not evaluated; design choice in tasks).
The worker streams new leaves the same way it streams topKUpdate / choiceUpdate events today; main thread inserts each new leaf into the cache as it arrives.
Soft cap: if the cache exceeds 500,000 entries, clear it entirely. Subsequent searches recompute from scratch. The cap exists only to bound worst-case memory; typical exploration paths never approach it.
"Searching" UI indicators (per-set spinner, global progress bar) only appear when the worker actually runs (i.e., not on full-cache-hit pin clicks).

Capabilities

New Capabilities

None.

Modified Capabilities

optimization-engine: introduces leaf caching across search invocations, the skipKeys worker contract, the immediate-render-then-stream pipeline for partial cache hits, and the cache-cap eviction policy. The optimizer and LP feasibility checker are untouched.

Impact

app/src/state/appState.ts — add leafCacheRef (Map<string, PlanOutcome>); restructure the worker effect to filter cache, derive immediate state, and spawn the worker only for the delta. Reset cache on ranking/mode change. Apply the 500k cap.
app/src/solver/decisionTree.ts — add skipKeys?: Set<string> to SearchCallbacks/searchDecisionTree signature; in evaluateLeaf short-circuit when the leaf's assignmentKey is already in skipKeys. Export a deriveFromLeaves(leaves, K, mode, ranking, openSets, excludedCourseIds) helper that produces { topK, setAnalyses } from a leaf collection, used both by the worker (final emit) and the main-thread filter path.
app/src/workers/decisionTree.worker.ts — accept skipKeys?: string[] in WorkerRequest; convert to Set<string> and pass to searchDecisionTree.
app/src/solver/__tests__/searchDecisionTree.test.ts — add tests: skipKeys correctly bypasses optimizer; deriveFromLeaves matches a fresh search's output when given the same leaves; cache filter pin/unpin idempotence (same final state regardless of pin order).
New unit test file (or extension of existing): cache-cap eviction, ranking/mode invalidation.
app/vite.config.ts — bump to 1.3.2
CHANGELOG.md — release entry
No data-file changes

4.0 KiB Raw Permalink Blame History

Why