Fast road-network routers first preprocess the graph into a hierarchy of "important" nodes and shortcut edges. A query climbs up this hierarchy and then climbs back down toward the target, and the climb down is where most of the time goes. The best known way to speed up the descent attaches a small bounding box to every downward edge, recording where that edge can lead. The search then skips any edge whose box does not contain the target. This works very well but costs several coordinates per edge and a heavy preprocessing pass. We propose replacing each box with a short bit string. Every node gets a learned binary code. Every downward edge stores the bitwise OR of the codes of all nodes it can optimally lead to. At query time an edge is skipped whenever its code and the target's code share no set bit. Because each edge's code is built by OR-ing true reachability, a needed edge can never be pruned, so paths stay exactly optimal whatever codes are chosen. The node codes only decide how many unneeded edges survive the test, and choosing them is a discrete optimization over binary weights.
This puts discrete weight optimization in an unusual role. It does not compress a neural network that must be evaluated at every search step. It optimizes the binary parameters of a search index, where the objective is a count of wasted edge visits and correctness is guaranteed by construction. That sidesteps the two weaknesses of learned search guidance named in the literature: the latency of a network forward pass at each expanded node, and the loss of optimality when learned heuristics overestimate. The discrete-optimization side supplies the machinery: flipping individual bits by exact discrete directional derivatives, as in Sharpness-Aware Minimization Directly on the Boolean Hypercube, or relaxing the bits through continuous shadow weights, as analyzed in Training Quantized Nets: A Deeper Understanding.
Core Claim
At a fixed memory budget of $b$ bits per downward edge, node codes found by native bit-flip optimization will prune more of the downward search than two alternatives: fixed partition-based codes, where each node carries a one-hot flag for a geometric or clustered region, and geometric bounding boxes. All three variants return exactly optimal paths. If the claim holds, learned codes should reach bounding-box query speed at a fraction of the per-edge storage, or beat bounding boxes at equal storage.
Formally, let $c_t \in \{0,1\}^b$ be the code of node $t$, with $c_t \neq 0$. Let $T(e)$ be the set of targets whose optimal up-then-down path uses downward edge $e$. The edge code is
$$m_e = \bigvee_{t \in T(e)} c_t ,$$
and the search follows $e$ toward target $t$ only if $m_e \wedge c_t \neq 0$. Since $t \in T(e)$ implies $c_t$ is contained in $m_e$, needed edges always pass the test. The quantity to minimize is the weighted number of false passes,
$$L(c) = \sum_{t} q_t \sum_{e \in D(t),\, t \notin T(e)} \mathbf{1}\left[ m_e \wedge c_t \neq 0 \right],$$
where $q_t$ is the query frequency of target $t$ (uniform by default) and $D(t)$ is the set of downward edges the unpruned search would examine for $t$. The loss is piecewise constant in $c$, so ordinary gradients give no signal. This is exactly the setting discrete weight optimization addresses.
Relation to Prior Work
The motivating evidence comes from Forward Search in Contraction Hierarchies. It replaces bidirectional search with an up-then-down forward search, identifies the downward phase as the bottleneck, and shows that per-edge bounding boxes ("Geometric Containers," labeled by a full Dijkstra pass) make forward search over ten times faster than bidirectional CH on Florida. Our proposal keeps its search policy and its reachability labeling pass, which is exactly what computes $T(e)$. We change only the container: a learned Hamming-space code instead of a rectangle in the plane.
Beyond Millisecond Latency kNN Search on Commodity Machine shows the other end of the memory spectrum. It attaches a single reachability bit per hierarchy node, costing about 2.85 MB for the full US network. Those bits come from static object assignment rather than optimization. Our codes generalize this one bit to $b$ bits whose meaning is learned.
Understanding Subgoal Graphs by Augmenting Contraction Hierarchies constrains the scope. On uniform-cost grids its canonical reachability relation already prunes 97–98% of nodes and edges without any stored containers. We therefore do not expect gains there, and we target weighted road networks, where no such geometric relation exists.
On the learning side, three systems learn guidance evaluated during search: TransPath: Learning Heuristics for Grid-Based Pathfinding via Transformers, Learning Graph Search Heuristics and Learning Admissible Heuristics for A*: Theory and Practice. The last is the most instructive. Its asymmetric loss achieved zero overestimation on a small Rubik's Cube abstraction but still produced thousands of overestimated states on larger ones, so enforcing a one-sided guarantee through training fails at scale. We move the guarantee out of the learned object entirely. Similarly, Subgoal-Guided Policy Heuristic Search with Learned Subgoals learns a discrete codebook of subgoals through a vector-quantized autoencoder but pays several network passes per expansion. Our codes are consumed by one AND and a zero test.
For the optimizer, BOLD-SAM supplies the method. It operates directly on binary weights, uses a discrete directional derivative to rank bit flips, and argues that continuous latent-weight proxies distort Hamming geometry and lose their perturbation signal as latent magnitudes grow. The shadow-weight analysis in Training Quantized Nets supplies the main alternative optimizer. It also supplies a negative result we heed: stochastic rounding stagnates at an error floor as step sizes shrink, so we do not use stochastic rounding.
Research Program
We build the index in three stages.
First, CH preprocessing and forward-search downward labeling, reused from the geometric-container pipeline, produce $T(e)$ for every downward edge. We store $T(e)$ implicitly through per-edge, per-bit counters of how many targets in $T(e)$ set that bit.
Second, we optimize the codes. The native optimizer repeatedly proposes flipping bit $j$ of some $c_t$. The counters tell exactly which edge codes change: an edge's bit $j$ toggles only when its counter crosses zero. Inverted lists over target bits then give the exact change in $L$ for that flip. The optimizer accepts improving flips in a greedy sweep with occasional restarts, which is BOLD-SAM's Boolean-variation descent without the sharpness term. The competing optimizer holds a real-valued shadow score per node bit. It computes the edge OR with a smooth maximum whose temperature is annealed toward a hard OR, following the continuation methods described in the file, and binarizes with a straight-through estimator.
Third, we add the sharpness term as a separate, clearly secondary hypothesis. It penalizes the worst-case loss within a small Hamming ball of codes. The hypothesis is that flat codes need fewer bit changes when edge weights change, for example under traffic updates that alter $T(e)$.
The analysis asks three questions. How does the false-pass rate fall as $b$ grows? Do learned codes become multi-hot, with nodes sharing bits across regions like a superimposed code, and does that explain any advantage over one-hot partitions? And where do surviving false passes concentrate in the hierarchy?
Baselines
The naive reference point is forward CH search with no containers, alongside standard bidirectional CH. Every container method must beat bidirectional CH to be worth storing. The file reports only relative figures for these, not absolute query times.
The strongest existing competitor is forward CH search with geometric containers labeled by full Dijkstra, from Forward Search in Contraction Hierarchies. It attacks exactly the downward bottleneck we target and is reported to be over ten times faster than bidirectional CH on the Florida DIMACS graph. No absolute query time or per-edge memory figure for it was found on Lacuna, so we reimplement it inside the same codebase. It will share the hierarchy, node ordering, query set and machine with our method. Beating it means either matching its average query time with fewer bits per edge, or lower average query time at equal bits per edge. Equal bits means $b$ set to the storage of its per-edge box, which is four coordinates under our encoding.
The key ablation isolates learning. We build the same OR-coded structure with fixed one-hot codes: $b$ regions from k-means on coordinates, and separately from a balanced graph partition. Each edge stores which regions it reaches, in the spirit of arc flags, and no optimization is applied. The $b=1$ special case recovers a Guide-Forest-style single reachability bit.
A second ablation isolates the optimizer. It compares native bit-flip descent against the annealed shadow-weight relaxation under the same wall-clock preprocessing budget and the same random initialization, which is the partition codes themselves. Learned methods therefore start from the ablation baseline and can only be credited with what optimization adds.
Why not just…?
Why not just use bounding boxes, which already give a tenfold speedup? Boxes describe reachability with an axis-aligned rectangle. On road networks, the set of nodes optimally reachable through a downward edge is often elongated or disconnected, for instance along a highway, so a rectangle admits many false targets. Learned codes can describe arbitrary shapes. Whether that matters in practice is exactly what the equal-bits comparison decides. If boxes win at equal storage, the proposal fails on its main claim, and we will report that.
Why not just use fixed region partitions with one bit per region, which needs no learning? This is the most serious threat. Partition flags are simple, fast to build and also exactly correct. If k-means or balanced-partition codes come within a few percent of optimized codes at every $b$, then the discrete optimization is not earning its preprocessing cost. The fixed-code ablation is designed to expose exactly that. Our reason to expect a gap is that one-hot codes waste capacity: with $b$ bits they distinguish only $b$ regions, while multi-hot codes can separate far more target groups whose reachability sets rarely overlap. We will measure whether the optimizer actually finds such codes.
Why not just train a small binarized neural heuristic, since the file's learned heuristics already cut expansions several-fold? Any network evaluated per expanded node, even an XNOR-and-bitcount one, costs more than a single AND of two machine words. Learned heuristics also give up exactness unless admissibility is enforced, and the CEA results show that enforcement breaking down on larger abstractions. Our design keeps learning entirely in preprocessing and keeps exactness by construction, so we compare against search-time learning only in discussion, not as a competitor.
Why native bit flips rather than a continuous relaxation? BOLD-SAM argues that latent-space proxies distort the Hamming structure. The OR in our loss is even more brittle under smoothing than the sign function. Still, annealed relaxations are cheap and might suffice, so the optimizer ablation settles the question empirically rather than by assumption.
Proposed Experiments
We use the 9th DIMACS road networks NY, BAY, COL and FLA (264K to over 1M nodes). The query sets are uniformly random source–target pairs plus a locality-skewed set, which tests whether weighting by $q_t$ helps.
The metrics are average and 99th-percentile query time, downward edges examined per query, false-pass rate, bits per edge and total index size, and preprocessing time. For every method we verify exact optimality against Dijkstra on a held-out sample of queries.
The first decisive check is the curve of query time against bits per edge on FLA, for learned codes, fixed partition codes and bounding boxes. The claim survives only if the learned curve lies below both others near the box's storage point. The second decisive check is the optimizer ablation on the same curve. The third, secondary check perturbs 1% of edge weights, recomputes $T(e)$, and counts how many bit flips each optimizer needs to restore its original loss, with and without the Hamming-ball sharpness term.
A negative control on GPPC grid maps checks the prediction that CH-SG-R's built-in geometric pruning leaves little room for any container. We expect little or no gain there, and seeing one would itself be informative.
References
- Sharpness-Aware Minimization Directly on the Boolean Hypercube
- Training Quantized Nets: A Deeper Understanding
- Forward Search in Contraction Hierarchies
- Beyond millisecond latency kNN search on commodity machine
- Understanding Subgoal Graphs by Augmenting Contraction Hierarchies
- TransPath: Learning Heuristics for Grid-Based Pathfinding via Transformers
- Learning Graph Search Heuristics
- Learning Admissible Heuristics for A*: Theory and Practice
- Subgoal-Guided Policy Heuristic Search with Learned Subgoals