Bidirectional search runs two searches at once, one forward from the start and one backward from the goal, and stops when they meet. With no guidance it is dramatically cheaper than a single search, because two small balls of radius $d/2$ contain far fewer states than one ball of radius $d$. Add a good heuristic, meaning an estimate of remaining distance that steers the search, and the advantage disappears or reverses. Limitations of Front-To-End Bidirectional Heuristic Search calls the middle ground a "no-man's land." With mediocre heuristics, bidirectional heuristic search loses to brute-force bidirectional search when the heuristic is weak and to ordinary A* when it is strong. Nearly every algorithm in that study, and most since, splits effort between the two directions by a fixed rule: alternate expansions, balance frontier sizes, or use a fixed cost fraction.
This proposal treats the no-man's land as a symptom of uniform compute allocation, the same diagnosis that input-adaptive methods have made for language-model inference. We propose that the search decide, expansion by expansion, which direction to spend its next unit of work on. The measure is how fast each direction has recently been raising the proven lower bound on the optimal solution cost, per unit of wall-clock time. When the backward search stops contributing, as it does in regions where the heuristic is strong, the allocation drifts toward unidirectional A. When states near the goal have misleadingly low heuristic values, the backward direction proves them useless cheaply, its contribution rises, and it gets more budget. The claim is that one algorithm with this rule can match the better of A and a modern bidirectional search on every instance. It should also beat both on instances where heuristic quality varies within a single problem.
Core Claim
An optimal search terminates when its best known solution cost $U$ meets a lower bound $LB$ on the optimal cost $C^*$. In meet-in-the-middle style searches, $LB$ is the maximum of several quantities: the smallest forward priority $\min f_F$, the smallest backward priority $\min f_B$, and $\min g_F + \min g_B + \varepsilon$. Here $g$ is cost-so-far in each direction and $\varepsilon$ is the minimum edge cost. The termination conditions in Bidirectional Search while Ensuring Meet-In-The-Middle via Effective and Efficient-to-Compute Termination Conditions (MEET) are cheap-to-compute versions of this bound. We reuse them as the stopping rule.
Our addition is the allocation rule. For each direction $D \in \{F, B\}$, we keep an exponentially weighted estimate $\hat{r}_D$ of the increase in $LB$ per second of search time. The estimate is attributed to $D$'s expansions over a recent window. The next batch of expansions goes to
$$ D^{*} = \arg\max_{D \in \{F,B\}} \; \hat{r}_D, \qquad \hat{r}_D = \frac{\mathbb{E}_{\text{recent}}[\Delta LB \mid \text{expand } D]}{\mathbb{E}_{\text{recent}}[\text{seconds per expansion in } D]}. $$
We add a small forced-exploration floor, so that neither estimate becomes stale. When the backward direction's share falls below a threshold for a sustained window, backward bookkeeping is suspended. Collision checks, which are a major overhead in bidirectional search according to Limitations of Front-To-End Bidirectional Heuristic Search, then stop. The search runs as plain A*, with the frozen backward $g$-values still usable for pruning.
Correctness does not depend on the allocation. Any expansion order paired with admissible heuristics and a valid bound-based termination returns an optimal path. We give up the meet-in-the-middle guarantee, which MEET enforces, in exchange for adaptivity. Whether that trade is worth it is an empirical question the experiments are built to answer.
The theory behind the rule comes from Predicting the Effectiveness of Bidirectional Heuristic Search. That paper shows bidirectional search wins mainly through "critical states": states far from the start with low heuristic values that a backward search dismisses cheaply. It measures their density before search (its M2 measure) and uses that to choose between A* and a bidirectional algorithm, all or nothing. Our rule turns that static diagnostic into an online one. A burst of critical states shows up directly as a jump in the backward direction's contribution to $LB$.
Research Program
The work has three parts. First, we build the allocator on top of a MEET implementation, so that the only difference from the strongest optimal bidirectional baseline is how the next expansion is chosen. The allocator attributes each change in $LB$ to the direction whose expansion caused it. It measures per-direction time per expansion, including collision checks, so that a direction that is cheap in node count but expensive in bookkeeping is charged fairly. Suspending and resuming the backward search is part of the same implementation.
Second, we analyze the rule. We will show optimality under admissible heuristics. We will also bound the worst-case overhead relative to the better of forward-only and fixed-alternation search: with forced-exploration rate $\eta$, the rule wastes at most roughly an $\eta$ fraction of expansions on the losing direction when one direction's contribution is consistently zero. We will characterize when an online rate estimate can be fooled. The main failure is a direction whose contribution arrives in a delayed jump, such as a plateau of equal $g$-values. That is exactly where a greedy rule would starve a direction that is about to pay off.
Third, we build a benchmark family of instances with a "patchy" heuristic. The heuristic is accurate in some regions of the state space and deliberately weakened in others, for example Manhattan distance divided by 5 only near the goal. Heuristic strength then varies within an instance, not just across domains. This is the regime that Predicting the Effectiveness of Bidirectional Heuristic Search and W-restrained Bidirectional Bounded-Suboptimal Heuristic Search leave open, and it is where any per-instance static choice must lose. As a secondary extension, the same allocator can replace the fixed frontier cost fraction $p = 0.5$ in the bounded-suboptimal algorithm of that second paper (Weighted MM).
Baselines
The naive reference points are unidirectional A and brute-force bidirectional search with fixed alternation. We run both in the same codebase, with the same heuristics, duplicate detection and priority queues, so that wall-clock comparisons are fair. On strong heuristics A is the bar. Limitations of Front-To-End Bidirectional Heuristic Search reports A running 32% to 74% faster than BS on the 15-puzzle and Rubik's Cube. On the Pancake puzzle with the full GAP heuristic, Predicting the Effectiveness of Bidirectional Heuristic Search reports about 30 expansions for A versus about 101 for NBS, the Near-Optimal Bidirectional Search algorithm. Beating A there is not required. Matching it within a small constant factor is.
The strongest existing optimal bidirectional method is MEET (Bidirectional Search while Ensuring Meet-In-The-Middle via Effective and Efficient-to-Compute Termination Conditions). It reports runtime at least two orders of magnitude better than MM on the 10-Pancake puzzle with GAP and GAP-X heuristics, and competitiveness with A* on the brc203 and orz100d grid maps. Because our method shares MEET's termination conditions, comparing against MEET isolates the allocation rule.
The strongest adaptive-allocation competitor is Incremental KKAdd from Robust Bidirectional Search via Heuristic Improvement. It uses the backward search to correct the forward heuristic, with either a fixed 1:100 interleaving ratio or an online regression that predicts which direction makes more progress. It reports a 6x reduction in time and expansions over A* on Towers of Hanoi and robot path planning. We run both its fixed and adaptive variants, tuning the ratio on held-out instances with the same budget we spend tuning our window length and exploration floor.
The most important baseline is a static selector. We define it two ways. The first is a per-instance oracle that runs whichever of A and MEET is faster on that instance, which is an upper bound on any pre-search predictor. The second is the realistic Rule-2 selector driven by M2 from Predicting the Effectiveness of Bidirectional Heuristic Search. Beating the oracle on homogeneous domains is impossible by construction. Beating it means two things. On standard domains we come within about 10–20% of its runtime without being told which algorithm to use. On patchy-heuristic instances we beat the oracle outright, because no single fixed choice fits the whole instance. The file reports no number for the oracle or the Rule-2 selector on our patchy instances, since the instances are new. The reference figures for the underlying algorithms on GAP-3 Pancake are NBS at about 32k expansions and A at about 379k, from Predicting the Effectiveness of Bidirectional Heuristic Search.
Two ablations isolate the key ingredient. The first replaces the lower-bound-gain signal with frontier-size balancing, the geometric rule used in A phase search-enhanced Bi-RRT path planning algorithm for mobile robots and Bi-directional smooth A-star algorithm for navigation planning of mobile robots. The second keeps the signal but disables backward suspension, which separates the gain from smarter allocation from the gain from dropping bookkeeping.
Why not just…?
Why not just run A* with the best available heuristic? Where the heuristic is strong, this is the right answer, and our method is designed to converge to it. The evidence that it is not enough everywhere comes from the file. On four-peg Towers of Hanoi, bidirectional brute force is 3.65x faster than the best unidirectional heuristic search (Limitations of Front-To-End Bidirectional Heuristic Search). On GAP-3 Pancake, A expands about 379k states against about 32k for NBS (Predicting the Effectiveness of Bidirectional Heuristic Search). Strong heuristics are often unavailable, and on patchy instances A pays for the weak region no matter how good the strong region is. The strong-heuristic experiments test whether our overhead above A* stays small.
Why not just pick A* or bidirectional search before starting, using M2 or a learned difficulty probe? This is the real threat. If heuristic quality is roughly uniform within instances, as it may be on standard puzzles, a static selector captures almost all of the gain, and our contribution shrinks to "no need to calibrate a selector." We settle this directly. On standard domains we report how close the Rule-2 selector and the oracle come to our method. On patchy instances we test the mechanism the selector cannot represent. System 1.x: Learning to Balance Fast and Slow Planning with Language Models gives indirect evidence that mixed-difficulty instances punish whole-problem choices: 70.4% plan validity for segment-level allocation, against 48.7% and 37.2% for its two pure modes. If the oracle static choice matches us on patchy instances too, we will report that the within-instance variation we hypothesize does not translate into exploitable signal.
Why not just use Incremental KKAdd's adaptive interleaving, or balance frontier sizes? KKAdd's adaptive variant already decides online between directions, so novelty rests on the signal. Its regression predicts heuristic-correction progress. Our rule measures the quantity that actually determines when an optimal search can stop, and charges each direction its real bookkeeping cost. That cost is what makes bidirectional search slow in wall-clock time even when it saves expansions. Size balancing ignores heuristics entirely. Both run as tuned baselines. The size-balancing ablation tells us whether the lower-bound signal matters or whether any sensible balancing gets the same result.
Proposed Experiments
The domains are the 15-puzzle with Manhattan distance and Manhattan distance divided by 5; the 10-, 14- and 17-Pancake puzzles with GAP, GAP-3 and GAP divided by 2; four-peg Towers of Hanoi with the zero heuristic and pattern databases; the MovingAI grids brc203 and orz100d with octile distance; and road networks with travel-time costs. We then add patchy-heuristic versions of each, weakening the heuristic within a radius of the goal, of the start, or of randomly placed regions. We report node expansions, wall-clock time and fraction of instances solved within a memory cap. On the patchy family, we add the per-instance ratio of our runtime to the oracle static choice.
The first decisive check is the strength sweep. We interpolate each heuristic continuously from zero to full strength and plot runtime for A*, brute-force bidirectional search, MEET, KKAdd and ours. The hypothesis predicts that our curve tracks the lower envelope of the others across the whole sweep, with the no-man's land flattened rather than merely shifted. The second check is the patchy family, where we must beat the oracle static choice for the claim of within-instance adaptivity to hold. The third is a diagnostic: we log the backward budget share over time and correlate it with the density of critical states actually encountered, computed after the fact following Predicting the Effectiveness of Bidirectional Heuristic Search. This confirms the allocator is tracking the mechanism we claim rather than noise.
A clean negative result would also be informative. That would be large overhead on strong heuristics, or no gain over the oracle on patchy instances. It would indicate that the no-man's land comes from termination and bookkeeping costs rather than from how compute is split between the two directions.
References
- Limitations of Front-To-End Bidirectional Heuristic Search
- Bidirectional Search while Ensuring Meet-In-The-Middle via Effective and Efficient-to-Compute Termination Conditions
- Predicting the Effectiveness of Bidirectional Heuristic Search
- W-restrained Bidirectional Bounded-Suboptimal Heuristic Search
- Robust Bidirectional Search via Heuristic Improvement
- A phase search-enhanced Bi-RRT path planning algorithm for mobile robots
- Bi-directional smooth A-star algorithm for navigation planning of mobile robots
- System 1.x: Learning to Balance Fast and Slow Planning with Language Models