Calibrated Switching Between Immediate and Delayed Duplicate Detection

When a graph search, such as A over a planning problem or a puzzle, outgrows RAM, it has to store its record of already-visited states on disk. There are two ways to check whether a newly generated state is a repeat. Immediate duplicate detection looks the state up right away, which costs a random disk read. Delayed duplicate detection* appends new states to a file and removes repeats later in one large sequential pass. For two decades the field has treated this as a fixed design decision tied to a particular era of hardware: delayed detection for spinning disks, and, since Revisiting Immediate Duplicate Detection in External Memory Search, immediate detection on SSDs for planning problems. That paper also found that the delayed method still wins on the 15-puzzle. The answer therefore depends on the problem, and we argue it also depends on the platform the search runs on.

The proposal is to treat the choice as a measured quantity rather than a design decision. We will build one external-memory search code base that runs natively on Linux, Windows and macOS and as WebAssembly under several runtimes. On each platform it calibrates the actual cost of a random read and of a sequential pass. It then switches each disk partition between immediate and delayed detection during the search, using a simple cost inequality. The cross-platform setting is the stress test that makes the question sharp. Portable runtimes are known to distort I/O costs: eWAPA shows Tokio-based WebAssembly runtimes split large writes into small chunks, "effectively doubling the execution cost". The crossover between the two strategies should therefore move from one platform to another. If it does, any fixed choice is wrong somewhere.

Core Claim

The crossover between immediate and delayed duplicate detection is predicted by a small number of quantities. Two are measurable on the platform and three are measurable during the search. A search that measures them and switches per partition will match or beat the better of the two fixed strategies on every combination of domain and platform. Neither fixed strategy manages that.

Concretely, for states landing in a given partition, deferring is cheaper when

$$q \cdot t_{\text{rand}} \;>\; k \cdot \frac{b}{B_{\text{seq}}} + \delta \cdot t_{\text{exp}},$$

where the symbols are as follows. $q$ is the fraction of generated states that still need a disk probe after the in-memory filter of segmented compression. $t_{\text{rand}}$ is the platform's measured time for one random page read. $k$ is the number of sequential read/write passes the delayed merge needs. $b$ is the state size in bytes. $B_{\text{seq}}$ is measured sequential bandwidth. $\delta$ is the number of extra expansions per state caused by pruning late, which includes the "final layer penalty". $t_{\text{exp}}$ is the time to expand one state.

The inequality explains the Lin and Fukunaga split without anything specific to a domain. Puzzle states have tiny $b$ and tiny $t_{\text{exp}}$, so the right side is small and deferring wins. Planning states have larger $t_{\text{exp}}$ and heavier final-layer waste, so probing wins. The inequality also makes a prediction nobody has tested: a runtime that inflates $t_{\text{rand}}$ or degrades $B_{\text{seq}}$ should shift the boundary.

Research Program

We will implement both strategies in one C++ code base that compiles natively and to the WebAssembly System Interface (WASI), the standard that lets WebAssembly programs make file and OS calls portably.

The delayed path follows the hash-bucketed design of Best-First Frontier Search with Delayed Duplicate Detection. States are mapped by hash to bucket files, and each bucket is deduplicated in RAM when it is loaded. This avoids the full external sort of Delayed Duplicate Detection: Extended Abstract. The immediate path re-implements segmented compression from Revisiting Immediate Duplicate Detection in External Memory Search. That method keeps an in-memory table of secondary hash partitions so that a state is read from the SSD only if it might really be there, and the paper reports false-positive probes eliminated at $p=100$.

The engineering idea that makes switching cheap is to give both paths the same on-disk layout. Each bucket's closed states live in sorted segments, and each segment has a partition summary in RAM. In immediate mode, new states probe these segments. In delayed mode, they go to an append log that is merged into the segments the next time the bucket is loaded. A mode change therefore moves no data; it only changes where the next state goes.

Calibration has two parts. The platform terms $t_{\text{rand}}$ and $B_{\text{seq}}$ come from a startup microbenchmark run through the same I/O path the search uses: native POSIX calls, Win32 calls, or WASI calls inside a given runtime. The search terms $q$, $\delta$ and $t_{\text{exp}}$ are estimated online from counters kept per bucket over a sliding window. The controller re-evaluates the inequality each time a bucket is loaded, with hysteresis to avoid oscillating between modes.

The analysis half of the project asks how much of the boundary shift across platforms is explained by the two platform terms alone. If the model is right, a run's best strategy should be predictable from a five-number summary, without trying both.

Baselines

The naive reference point is pure in-memory A, which fails on the 24-puzzle. On Parallel External-Memory Bidirectional Search calls in-memory A and BAE "impractical to run" there. Alongside it we run OS-paged A: the same in-memory hash table placed in a memory-mapped file, so the operating system's virtual memory decides what lives on disk. This is the do-nothing answer to running out of RAM. It is run on every platform with the same RAM cap, and beating it is expected rather than informative.

The first strong fixed baseline is always-delayed detection: hash-bucketed External A* in our code base. Running it in the same code base, with the same buckets, RAM cap and buffer sizes, keeps the comparison fair. Its buffer size is tuned per platform under the same grid search the hybrid gets, so the hybrid cannot win merely because the delayed baseline's buffers were too small.

The strongest existing method is A with immediate detection and segmented compression. Revisiting Immediate Duplicate Detection in External Memory Search reports that it solved 33 of 34 International Planning Competition (IPC) instances, against 27 of 34 for standard compression, with 3x to 5x speedups over DDD-based External A. We will first try to reproduce these figures on native Linux with an NVMe SSD before running anything else. The partition count $p$ is tuned per platform. On the sliding-tile and Towers of Hanoi domains, our only reference points are the parallel external bidirectional searches. On the 24-puzzle, PEM-BAE expanded 4.4% of AIDA's nodes and ran 4.5 times faster, per On Parallel External-Memory Bidirectional Search. We report this only as context because it is bidirectional and multi-threaded. No reported result was found on Lacuna for any external-memory search on Windows, macOS or WASI.

The decisive baseline is the static oracle. For each pair of instance and platform, we run both fixed strategies and keep whichever was faster afterwards. This baseline isolates the key ingredient of the proposal, which is switching within a run rather than choosing well once.

Two ablations accompany it. The first uses the cost model only to make one choice at startup, from the platform microbenchmark and a short pilot search. The second freezes the platform terms at native-Linux values everywhere, which tests whether per-platform calibration matters.

Beating the strongest method has a precise meaning here. The hybrid's wall-clock time must be within 10% of the static oracle on every cell and below the worse fixed strategy on every cell. To show that within-run switching earns its complexity, the hybrid must also beat the oracle on at least a meaningful fraction of cells.

Why not just…?

Why not just always use immediate detection on SSDs? Lin and Fukunaga's own 15-puzzle result rules this out as a universal answer, since delayed detection stayed more efficient there. Under a WebAssembly runtime the problem should get worse. eWAPA's 17:1:1 amplification, 17 Wasm fwrite calls producing 1 WASI call and 1 writev syscall, measures per-call overhead at the boundary of the portable runtime. Many small probes pay that overhead far more often than a few large streams. Our platform grid measures this directly.

Why not just always use delayed detection with large buffers? Sequential I/O is the one thing every platform does well. This is a real threat. If large buffers neutralise the async tax on every runtime, always-delayed detection becomes a portable, robust default, and on cheap domains it may match the hybrid. The experiments settle it on the IPC set. Lin and Fukunaga's 3x to 5x gap came from delayed detection's over-expansion and final-layer waste, which no buffer size fixes. If always-delayed detection with tuned buffers comes within 10% of the hybrid on the planning tasks across platforms, we will report that the switching mechanism is unnecessary and the contribution reduces to the measurement study.

Why not just benchmark both strategies once per platform and pick one? This is the static-oracle baseline, and it is the most likely way the proposal partly fails. Switching within a run can only win where the inequality flips during a search. We expect flips because early layers are small and duplicate-heavy, while late layers are large and have high $\delta$, but that expectation is untested. If the oracle ties the hybrid, the surviving contribution is the startup ablation: a cost model that predicts the oracle's choice without running both strategies. That still saves the cost of benchmarking per platform.

Why not just let the operating system page a memory-mapped hash table, or use an embedded key-value store? Paging is included as a baseline because the cost is easy to show. Research Challenges in Combinatorial Search and Korf's original analysis explain that scattered lookups make each access fault in a whole page. A log-structured key-value store pays logarithmic lookups per point query and adds layered overhead of the kind eWAPA measures. A store built on log-structured merge trees is essentially a general-purpose version of our delayed path with worse constants, so we treat it as a secondary comparison rather than a main baseline.

Proposed Experiments

The domains are the 34-instance IPC set used by Lin and Fukunaga, the 15-puzzle and 24-puzzle, and the four-peg Towers of Hanoi. Together they span cheap, small states and expensive, large ones. The platforms are native Linux (ext4), Windows (NTFS) and macOS (APFS) on comparable NVMe SSDs, plus one SATA SSD and one HDD on Linux to widen the range of $t_{\text{rand}}/B_{\text{seq}}$. On Linux we also run three WASI runtimes from the eWAPA study: Wasmtime Preview 2 and Wasmer, which are async-backed, and WAMR. All runs are single-threaded with an identical RAM cap. Parallel bucket skew, documented in Parallel Structured Duplicate Detection and in PEM-BiHS, is deliberately left out so that it does not confound the detection question.

The metrics are instances solved within a time limit, wall-clock time, expansions, bytes read and written, and disk probes per generated state.

Three checks decide the outcome. The first is whether the winning fixed strategy actually changes across platforms for the same instance. If it never changes, cross-platform calibration is moot and only the domain dependence remains. The second is whether the five-number cost model predicts the static oracle's choice above a majority-class baseline on held-out platforms. The third is whether the hybrid beats the static oracle anywhere, and whether those cells are the ones where the logged per-bucket inequality actually flipped mid-run. A positive answer to the third, explained by logged flips, is what would make within-run switching a real contribution rather than an engineering convenience.