Cadence-Aware Frontier Re-Detection for Zero-Shot Object-Goal Navigation

Abstract

Vision-and-Language Navigation systems built on large language models assume a pre-built scene graph from the simulator, like the Matterport3D connectivity graph recent agents rely on. That assumption breaks the moment the agent has to operate in an unmapped environment. We present a real-time dynamic-graph adapter that lets the released NavGPT-2 policy perform Object-Goal Navigation on HM3D scenes with no retraining and no pre-built connectivity, building the topology online from depth so the policy can run on a benchmark it was never trained for.

We then study the frontier re-detection cadence: how often the perception sweep should run. A failure analysis pins down the real bottleneck — exploration reaches the goal region, but in most failed episodes the agent stops in the wrong place. So we keep the substrate and replace the stop decision with a value-map explorer and a discriminative grounding stop, which commits only when the target wins a category comparison rather than merely looks present. Success rate rises from 17.7% to 33.3% and oracle reach from 36% to 94%, at an SPL of 2.4, with every experiment on a single consumer GPU.

Building the graph from depth

Every depth pixel is ray-marched into a top-down occupancy grid at 0.1 m resolution. A frontier cell is a free cell touching an unknown one; those cells are DBSCAN-clustered, and each centroid becomes a candidate viewpoint. Candidates are snapped to the navmesh, rendered as a 12-yaw × 3-elevation panorama, and encoded with frozen EVA-CLIP-g into a (36, 257, 1408) tensor — bit-compatible with NavGPT-2's released feature cache, so the Q-Former sees the input distribution it was trained on.

Three panels: a top-down occupancy grid from depth ray-marching, the same grid with frontier cells highlighted, and DBSCAN cluster centroids marked as candidate viewpoints.

(a) occupancy grid from depth; (b) Yamauchi frontier cells in magenta; (c) cluster centroids as candidate viewpoints. The height-band filter (floor + 0.1 m to eye + 0.3 m) matters more than it looks on HM3D, where camera height is fixed but the floor moves between scenes.

The adapter is policy-agnostic. What it reproduces is DUET's observation contract, which DUET, NavGPT-2 and other graph-based policies all share, so any policy consuming that dict can be dropped onto an unmapped scene unmodified. The contract is written out field by field in the README.

How often should you re-detect?

Once the graph is frontier-driven, a question appears that a pre-built graph never raises. Re-detecting every step keeps information fresh but pays full perception cost each step; never re-detecting is cheap but finds nothing the spawn pose could not see. A single integer, redetect_every_n_steps, dials between them.

HM3D val_mini, 30 episodes over 2 scenes, `max_steps` = 15. Intervals are 95% Wilson.
Cadence	SR	95% CI	SPL	Soft-SPL	DTG
N = 1 (every step)	23.33	[11.8, 40.9]	7.09	12.03	3.14
N = 2	26.67	[14.2, 44.4]	6.32	13.40	3.27
N = 3	26.67	[14.2, 44.4]	9.70	16.45	2.87
N = 5	26.67	[14.2, 44.4]	6.34	13.07	2.75
N = 0 (never)	23.33	[11.8, 40.9]	6.39	13.60	2.96

What this sweep can and cannot show. At 30 episodes the cadence values are not separable on success rate: the difference between N = 1 and N = 3 is a single episode (7/30 vs 8/30), nine episodes flip in both directions, and every pairwise McNemar exact test returns p = 1.000. The paired SPL difference is +2.62 pp with a 95% CI of [−4.61, +9.88], which crosses zero. What the sweep does establish is that success rate is insensitive to N across a 5× range while perception cost falls monotonically by construction — so the cheap end of that range comes free. Every number here is recomputable from the released per-episode records with python scripts/stats.py.

The effect is also budget-dependent: at a 15-step budget N = 3 reaches 26.67% while N = 1 reaches 23.33%, but give N = 1 a 25-step budget and it reaches 26.67% too. Whatever the cadence buys, it buys by not spending step budget on redundant re-perception.

The bottleneck is the stop decision

Sorting all 364 episodes of the larger validation run by final distance-to-goal turns the headline number into a to-do list. STOP is emitted in every episode — no timeouts — and only 20.6% are catastrophic wrong-room errors. Near-miss (DTG ≤ 2 m) and stopped-far (2–5 m) together account for 57%: the agent reliably reaches the right region, then commits in the wrong spot.

$Stacked bar chart per object category showing the fraction of episodes ending in success, near-miss, stopped-far, wrong-room, or timeout.$

Failure-mode decomposition at cadence N = 3 over 364 episodes and 13 scenes.

Taking that diagnosis at its word, we keep the substrate and change only the brain on top. Eight versions of the stop decision, on the same graph and the same evaluation, make the point by elimination. Oracle reach stays high throughout — the explorer is doing its job — yet success rate stays pinned near 23% through seven successive fixes: a verify sweep, a stop-in-place rule, scoring the detected box crop, multi-view agreement, SAM metric localization, a persistence gate, and approach-then-verify routing.

Eight stop decisions on the same dynamic-graph substrate. Reach is high throughout; success moves only at the last row.
Stop decision	SR	OSR
S1 strict re-detect + verify	17.4	90.3
S2 stop-in-place on close detection	20.1	63.0
S3 match score on detected box crop	22.9	60.0
S4 box-crop score + multi-view trust	19.4	83.0
S5 SAM-mask metric localization	23.6	67.0
S6 multi-view persistence gate	22.2	80.0
S7 approach-and-verify routing	23.7	75.0
S8 discriminative CLIP argmax	33.3	93.8

All seven fixes gate on presence, and presence is the wrong question. The image-text-match scores of correct and wrong stops overlap almost completely: the detected category was right, but the instance was wrong or simply was not a goal. "Is a bed visible?" is passed by any bed-like furniture. Only the argmax test — "is this more bed than sofa, chair, or wall?" — tells the two apart, and it is worth +9.7 pp on its own, more than every other module combined.

Results

On the same substrate and the same evaluation, swapping the stop decision nearly doubles success rate and takes oracle reach from a third of episodes to almost all of them:

HM3D ObjectNav-v2 validation, all on a single RTX 3080 (10 GB). Intervals are 95% Wilson, except the 364-episode row, which uses a scene-level cluster bootstrap.
Explorer / stop	Evaluation	SR	95% CI	OSR	SPL
Frozen NavGPT-2	144 ep, 36 scenes	17.7	—	36.1	—
Value map + discriminative stop	144 ep, 36 scenes	33.3	[26.2, 41.4]	93.8	2.4
Frozen NavGPT-2, N = 3	364 ep, 13 scenes	22.25	[17.3, 26.9]	—	6.97
Frozen NavGPT-2, N = 3	30 ep, val_mini	26.67	[14.2, 44.4]	—	9.70

Per-category success on the 364-episode run ranges from 36.4% (bed) to 4.5% (toilet). Per-scene success ranges from 3.6% to 35.7% — a spread far larger than anything the cadence axis moves, and the reason two scenes cannot resolve one.

Where this sits among published methods

The table below is not a leaderboard — it locates our operating point. HM3D is training on HM3D data. Infer. FM is the class of foundation model queried at inference: an open-vocabulary vision-language model (V), an autoregressive LLM (L), both, or none. ObjNav is whether the policy or planner was designed for Object-Goal Navigation.

HM3D ObjectNav-v2 val; every number is from the cited paper's own val table. † ZSON trains on HM3D ImageNav episodes rather than ObjectNav. * our agent acts topologically, at most 15 teleports per episode, where every other entry acts in continuous space over hundreds of low-level steps — which bears on both SR and SPL.
Method	HM3D	Infer. FM	ObjNav	SR	SPL
PIRLNav	yes	—	yes	64.1	27.1
OVRL-V2	yes	—	yes	64.7	28.1
RATE-Nav	yes	V+L	yes	67.8	31.3
VLFM	no	V	yes	52.2	30.4
L3MVN	no	L	yes	50.4	23.1
PanoNav	no	L	yes	43.5	23.7
SemExp	yes	—	yes	37.9	18.8
ZSON	yes^†	V	yes	25.5	12.6
Ours: frozen NavGPT-2	no	V+L	no	17.7	—^*
Ours: + discriminative stop	no	V	no	33.3	2.4^*

We do not claim state-of-the-art success rate. Our value-map agent does query foundation models at inference — BLIP-2 image-text matching for the value map, Grounding DINO, SAM and CLIP for the stop — exactly as VLFM does, so it belongs in the same column as VLFM, L3MVN and PanoNav, all of which score higher. Likewise the frozen-policy row runs a Q-Former and FlanT5-XL in its forward pass. What distinguishes both of our rows is the ObjNav column: every other entry was designed for this task, while ours was trained for instruction following on a different benchmark and a different scene dataset, and is used without retraining a single parameter. SPL of 2.4 reflects an explorer that covers much of a scene before committing; path efficiency is not what this design optimizes, and a continuous local controller is the natural next layer.

Top-down view of a successful episode: the agent starts at a green star, teleports between numbered frontier candidates, and stops within one metre of the target plant.

A successful run on an unseen HM3D scene. The agent starts at the green star, explores the dynamic graph by teleporting between numbered frontier candidates, and stops (green cross) within 1 m of the target plant (gold star, with its 1 m success ring).

BibTeX

@inproceedings{kelenyi2026cadence,
  title     = {Cadence-Aware Frontier Re-Detection for Zero-Shot Object-Goal
               Navigation with a Frozen Vision-Language Policy},
  author    = {Kelenyi, Benjamin and Tamas, Levente},
  booktitle = {2026 30th International Conference on System Theory,
               Control and Computing (ICSTCC)},
  year      = {2026}
}