Stable Sort Keys for Out-of-Core Planning in Learned World Models

Planning from pixels gets dramatically easier once an agent can tell that it has returned to a state it has already seen. Recognizing revisits turns an exponentially branching search tree into a graph whose size is the number of distinct states. For combinatorial puzzles, though, that number can still run to hundreds of millions or billions, which is too many to hold in memory. Classical search solved the memory problem decades ago: write newly generated states to disk in sequence, then sort the file so duplicates land next to each other and can be removed in one pass. That trick needs every state to have an exact, repeatable identifier. Learned world models produce continuous vectors instead, and those vectors shift as the encoder keeps training, even when the model's behavior does not change. Two visits to the same physical state then receive different coordinates, and the disk-based duplicate check silently fails.

We propose to make learned world models compatible with disk-based search. The encoder emits a coarse-to-fine discrete code for each state and is trained so that the code stays fixed while the rest of the representation is free to move. The coarse part of the code places temporally neighboring states in the same disk block, so successors of a block mostly stay local. The full code acts as the exact sort key for batched duplicate removal. A small dense fingerprint, stored next to each key and read only in sequential sweeps, resolves the rare ambiguous merges. If this works, planning by recognizing revisited states should scale from RAM-sized graphs to disk-sized ones without falling back to random disk reads, and should survive continued training of the encoder.

Core Claim

The obstacle to out-of-core latent planning is not storage capacity. It is that learned state identities are neither discrete nor stable over time. We claim both properties can be engineered into the encoder's output without freezing the encoder, by separating a low-dimensional "key" readout from the drifting high-dimensional representation. This separation mirrors what neuroscience reports about drift. Population codes wander mainly within a null space that downstream readouts ignore (Xia et al.; Zavatone-Veth et al.), and downstream readouts can adapt to track whatever drifting part remains (Avidan et al.). We use that picture as a design rule rather than as a biological claim: let the encoder drift, but anchor the key.

Background and Positioning

Three lines of work supply the pieces, and none combines them.

Planning from Pixels in Environments with Combinatorially Hard Search Spaces (PPGS) motivates the proposal. It trains forward, inverse, and margin losses so that distinct states sit far apart on a hypersphere. It then merges a predicted latent with an earlier one whenever their distance falls under a threshold, and runs breadth-first search over the resulting graph. Its whole graph lives in memory, and its threshold assumes a fixed embedding. We keep its world-model losses and replace the threshold merge with exact key matching that works on disk.

Delayed duplicate detection (Delayed Duplicate Detection: Extended Abstract; Best-First Frontier Search with Delayed Duplicate Detection) and structured duplicate detection (Structured Duplicate Detection in External-Memory Graph Search) supply the disk method. The first sorts appended frontier files; the second partitions the state space so that expanding one block only requires a small, known set of neighboring blocks in memory. Both assume exact symbolic state keys. Our contribution is to manufacture such keys from a learned model.

Partitioned External-Memory Value Iteration (PEMVI) constrains the design. It shows that block-wise processing gains about an order of magnitude only when transitions stay within nearby blocks, and that the gains shrink in Racetrack, where actions jump across blocks. A learned partition therefore has to be judged by how local its transitions are, not only by how accurate its keys are. This is why the coarse code level is trained on consecutive-step pairs, using the temporal redundancy of trajectories: adjacent frames differ little (STTS finds temporal redundancy exceeds spatial redundancy in video), so they should share a coarse prefix.

Progressively Optimized Bi-Granular Document Representation for Scalable Embedding Based Retrieval (BiDR) supplies the two-tier storage idea: compressed codes in RAM, dense vectors on disk for verification. BiDR serves static documents with one-off queries and random verification reads. We apply the two tiers to a growing search frontier and replace per-query reads with sorted batch verification.

Two drift papers explain why the keys need explicit anchoring. Data symmetries generate drifting similarity matrices in manifold-tiling neural codes shows that stochastic gradient descent moves representations between symmetric, functionally equivalent configurations. Even a readout space can therefore rotate, and a stability term is needed rather than hoped for. Stability through plasticity suggests that drift can push units toward saturated or inactive regimes that resist noise, which hints that discrete keys built on saturated units may stay stable naturally. We test that hint instead of assuming it.

Method

The encoder maps an observation to a dense latent $z$, as in PPGS. A key head maps $z$ to a residual-quantized code $k = (k^{(1)}, \dots, k^{(L)})$; residual quantization means each level encodes what the previous levels left unexplained. The first level is trained so that $k^{(1)}(s_t) = k^{(1)}(s_{t+1})$ for most consecutive steps, and it defines the disk block. The full code is the duplicate-detection sort key. A short dense fingerprint, a low-bit projection of $z$, is stored next to each key on disk.

Key stability is enforced against an anchor: a slowly updated, exponential-moving-average copy of the key head, evaluated on a reservoir of stored observations. Writing $q_\theta$ for the current key head's soft code assignments and $\bar q$ for the anchor's, we add

$$ \mathcal{L}_{\text{key}} = \mathbb{E}_{x \sim \mathcal{R}} \, \mathrm{KL}\big(\bar q(x) \,\|\, q_\theta(x)\big) + \beta \, \mathbb{E}_{(s,s') \sim \text{diff}} \big[\, m - \| z_s - z_{s'} \| \,\big]_+ , $$

where $\mathcal{R}$ is the observation reservoir and the second term is PPGS's margin loss over pairs of distinct states, with margin $m$ and weight $\beta$. The encoder is otherwise unconstrained. The dense part of $z$ can drift, and the forward model adapts to it.

Codes near a quantization boundary are the expected failure mode. For these, the head emits a second key, and the state is written under both keys; this is multi-probe hashing. During sorting, groups that share a key but whose fingerprints disagree are flagged and resolved by one sequential read of their dense vectors.

Search then runs layer-synchronous breadth-first search with structured duplicate detection over coarse blocks. For each block in turn, the planner loads the block and its successor blocks, expands states with the forward model, appends children to per-block buffers, and sorts and deduplicates each buffer by full key. When the encoder is updated mid-search, stored keys stay valid as long as the anchor holds. We measure directly how often they do not.

Research Program

The work has three parts. The first builds the key head and the out-of-core planner on PPGS's codebase and environments. The second builds a family of scaled environments whose reachable graphs range from about $10^6$ to $10^9$ states, made by composing several IceSlider and DigitJump boards into one joint puzzle. Composition multiplies reachable-state counts while keeping ground-truth state identity available from the simulator. The third studies drift directly. We continue training the encoder on newly generated levels during search and track how quickly key agreement, dense-latent similarity, and similarity-matrix structure each decay. We expect dense latents to drift substantially while keys stay mostly fixed. If keys drift as fast as the dense latents, the core claim fails.

Baselines

The naive reference point is PPGS run as published, entirely in memory, with its distance-threshold reidentification. It shows how far in-memory planning gets before memory runs out. For its strongest reported result, PPGS reports a success rate near 97% on IceSlider using 400k random-policy samples (PPGS). On graphs that fit in RAM, our system must match that success rate within noise. Beyond RAM, PPGS cannot run at all, so the comparison moves to the baselines below.

The oracle is exact delayed duplicate detection with structured partitioning on the simulator's true discrete state (Korf; Structured Duplicate Detection). It runs on the same disk, RAM cap, and environments, with a hand-designed partition. It bounds the achievable input/output volume and wall-clock time. Beating it is not the goal. Coming within a small factor of it, for example within 2× in bytes read per expanded state, would count as success.

The strongest learned competitor is a BiDR-style two-tier index (BiDR). Product-quantized latents are kept in RAM for candidate filtering, dense latents sit on disk, and each newly generated state is verified against its shortlist with immediate disk reads. It gets the same encoder, the same RAM budget, and the same hyperparameter-tuning budget as our method, including tuned shortlist size. BiDR reports a +17.45% Recall@10 gain over STAR plus DiskANN on its billion-scale ad dataset at about 8 ms per query. Those figures concern single-shot retrieval, and no reported result found on Lacuna for out-of-core duplicate detection over learned world-model latents. Beating this baseline means equal or better duplicate precision and recall, with at least an order of magnitude fewer random reads per expanded state at $10^8$ states.

Three ablations isolate the ingredients. The first removes $\mathcal{L}_{\text{key}}$, so keys are a plain residual quantizer that drifts with the encoder; this isolates the stability term. The second replaces the temporally trained coarse level with a random hash partition; this isolates locality and tests the PEMVI coherence concern. The third removes boundary double-keying and fingerprint checks, which measures how much of the precision comes from verification.

Why not just…?

Why not just freeze the encoder once trained, so there is no drift? This is the most serious alternative. On a fixed set of levels it may work as well as our method. Freezing gives up adaptation to new levels during search, and LIBERO reports that naive pretraining can hurt downstream lifelong performance, which is indirect evidence that frozen representations transfer poorly. More importantly, a frozen continuous encoder still needs discrete keys, and quantization-boundary errors exist even without drift. We run a frozen-encoder variant with our key head both on held-in levels and on levels introduced mid-search. If the frozen variant matches us on the new levels too, the drift-stability component is unnecessary, and we would narrow the contribution to the disk-compatible key design.

Why not just re-encode all stored states whenever the encoder changes? This keeps keys consistent by brute force. Its cost grows with graph size: every update requires a full sequential pass over stored raw observations plus a forward pass of the encoder. We measure the total cost of re-encoding against our anchored keys at each graph size and update frequency. At small scale re-encoding may well be cheaper, and we will report where the two cost curves cross rather than claim a uniform win.

Why not just use a disk-based approximate nearest-neighbor index for every duplicate check? This is the BiDR-style baseline above. Each check is a lookup that triggers random reads, which is exactly what delayed duplicate detection was invented to avoid (Korf). The random-reads-per-expansion metric settles this question directly.

Proposed Experiments

We evaluate on IceSlider, DigitJump, and ProcgenMaze at their original sizes, which checks parity with PPGS, and on the composed variants from $10^6$ to $10^9$ reachable states, with RAM capped at 32 GB and data on a single NVMe drive. The metrics are planning success rate; duplicate precision and recall against simulator ground truth; distinct nodes stored divided by true distinct states; bytes read and written and random reads per expanded state; fraction of transitions that stay inside a block; and wall-clock time to a solution.

Three checks decide the outcome. First, keys must stay stable under drift: after continued encoder training, at least 99% of reservoir states keep the same full key, while dense-latent similarity matrices measurably change. Second, the learned partition must be local, with most transitions staying within a block, unlike PEMVI's Racetrack regime. Third, the method must keep a sub-linear random-read count as the graph passes RAM size, while the approximate nearest-neighbor baseline's random reads grow with graph size. Failing the first check falsifies the drift-anchoring claim. Failing the second means temporal redundancy does not buy disk locality in learned codes. As a secondary probe, we repeat the locality measurement on PointMaze and AntMaze-Hard from L3P, where continuous dynamics make key boundaries hardest, to show where the approach stops working.