Coverage-Aware Retrieval over Online 3D Scene Memory

A robot that answers questions while it explores a building is a retrieval system whose knowledge base is still being written. Its "documents" are the objects and views it has observed so far, and that collection is always incomplete. Some rooms have not been visited. Some surfaces were seen only from far away. Some views were thrown out to save compute. Asked "where is the fire extinguisher?" before it has seen one, today's systems retrieve the nearest match in embedding space, perhaps a red bin, and the language model answers confidently from it. This is the coverage failure studied in text and image retrieval: when the needed item is missing, the retriever returns similar-looking distractors and the generator trusts them. The embodied setting has one advantage that text retrieval lacks. Its gaps can be located. An online 3D reconstruction knows which parts of space it has observed, which it has seen to be empty, and which it has never seen.

We propose to turn that geometric record into a coverage signal that sits next to retrieval similarity. A system using it can do three things. It can answer from memory when the evidence is there. It can state that something is absent when the places it could be have been inspected. It can say "not yet observed" and trigger exploration when they have not. The claim is narrow and testable. On questions asked partway through a scan, an estimate of coverage derived from the map should separate "observed and absent" from "not yet observed" far better than retrieval-score thresholds or a language model's own judgment of whether it has enough information. That separation should sharply reduce confident wrong answers without hurting accuracy on questions the memory can answer.

Core Claim

Retrieval similarity measures how well the best stored item matches the query. It says nothing about whether the right item could be stored somewhere the system has not looked. Two situations produce identical retrieval scores and need opposite responses: a mug was never in the kitchen, or the kitchen was never seen. Online mapping already computes the quantity that tells them apart. Seeing Once is Enough? keeps a global grid of visited voxels, the small 3D cells that tile the scanned space. It uses that grid only to delete redundant visual tokens, the image patches fed to the language model. Occupancy predictors such as EmbodiedOcc maintain observed and unknown space as the agent moves. We reuse this bookkeeping as evidence about what the agent's memory covers.

Concretely, for a query entity $e$, let $c_e \in [0,1]$ be the fraction of plausible placement regions for $e$ that the map has observed at adequate resolution. For a mug, those regions are tabletops, counters and shelves within the query's spatial scope. Let $r$ be the recall of the perception pipeline for objects in observed space, measured once on held-out scans. Let $\pi_e$ be a prior that $e$ exists in a scene of this type, taken from dataset statistics or a language model. Suppose retrieval finds no match above a fixed similarity threshold. Bayes' rule then gives the probability that $e$ is still present:

$$ p(\text{present} \mid \text{no match}) = \frac{\pi_e (1 - c_e r)}{\pi_e (1 - c_e r) + (1 - \pi_e)}. $$

When coverage is high and recall is good, this probability collapses toward zero and the system may say "absent." When coverage is low, it stays near the prior, and the honest output is "not yet observed." The formula is deliberately simple. It treats detection in observed space as independent of location, and that assumption is part of what the experiments test.

A second, smaller use of coverage concerns attributes. A node can exist in memory while its color, state or label was read from a single distant, oblique view. This is the attribute-loss problem flagged for Building a Mind Palace and the irreversible-pruning concern raised by the authors of Seeing Once is Enough?. We record per-node view coverage: the number of distinct viewing directions and the closest viewing distance. When an attribute question targets a poorly covered node, the system pulls the pruned image patches for that node back from a cheap store instead of discarding them. This keeps the token savings of pruning while making them reversible exactly where coverage says the first look was inadequate.

Relation to Prior Work

The closest system is Open-World 3D Scene Graph Generation for Retrieval-Augmented Reasoning (OSU-3DSG). It builds an open-vocabulary 3D scene graph, stores its nodes in a vector database, and retrieves subgraphs to prompt a multimodal model. It assumes the database covers whatever the query needs, so an unobserved object is silently replaced by its nearest neighbor. That is precisely the failure we target. ConceptGraphs and Clio supply the scene-memory machinery we build on: incremental open-vocabulary graphs, and in Clio's case local updates fast enough for a laptop. Both are bounded by what was seen, and neither represents what was not seen. Clio makes this sharper by design, because its task-driven compression discards objects irrelevant to a preset task list. Our coverage map is a natural companion: it can report that the discarded region was observed and compressed, as opposed to never observed.

Two embodied systems already decide when memory is insufficient, and they are the real threats to novelty. Enter the Mind Palace uses a value-of-information criterion, an estimate of how much further retrieval or exploration would improve the answer, to stop retrieving and start exploring. Its authors note that answers remain bounded by trajectory coverage. ExRAP raises the uncertainty of memory entries as they age and steers exploration toward uncertain regions, but it works over symbolic simulator states rather than open-vocabulary 3D reconstructions. Our proposal differs from both in where the sufficiency signal comes from. They judge sufficiency over stored memory items. We judge it over the geometry of observed versus unobserved space, which lets the system reason about items that are not in memory at all. That is the case where retrieval-based judgment has nothing to inspect.

On the retrieval side, RA-TTA and MOTOR motivate the problem: both report that when the reference library lacks the needed concept, retrieval-based adaptation and diagnosis fail. Multi-step remedies such as Chain-of-Knowledge and SearChain constrain our design. They cannot manufacture missing knowledge, and they add per-query latency that an embodied agent cannot afford. Our signal is a lookup into a voxel grid the mapper already maintains, so it adds almost no cost.

Research Program

We will build on a voxel-hashed online mapper that fuses streamed RGB-D frames (color plus depth video) into three things. The first is an occupancy grid with unknown, free and occupied states. The second is an open-vocabulary object graph in the style of ConceptGraphs. The third is per-node view statistics. Placement regions for an entity are horizontal and vertical support surfaces extracted from occupied voxels and filtered by a language-model prior over where such objects typically rest.

A query passes through a small parser that extracts the target entity and any spatial scope. The system then runs retrieval and computes the coverage score $c_e$ and the posterior above. A three-way decision rule selects among answering, declaring absence, and reporting non-observation. The decision thresholds are calibrated on a held-out split. We will also measure recall $r$ separately by object size class, since small objects such as remotes and keys are where uniform recall is least plausible.

For attribute questions, pruned patches are kept in a compressed per-node store and reloaded when view coverage falls below a threshold. In the active setting, a "not yet observed" output hands the unobserved placement regions to a frontier planner, a standard explorer that drives toward the boundary between known and unknown space.

Baselines

The naive reference point is a multimodal model given every frame streamed up to the question time, with no retrieval structure and no option to abstain. We use Qwen2.5-VL-7B, because Seeing Once is Enough? reports it on the same benchmarks. This shows how often a capable model invents answers about unseen content when nothing stops it.

The strongest existing online method is geometry-aware token pruning from Seeing Once is Enough?. It reports ScanQA exact match rising from 24.1 to 25.1, and SQA3D accuracy rising from 46.5 to 47.3, with Qwen2.5-VL-7B. We run it with the same backbone, frame stream and voxel resolution as our system, so the only difference is what the coverage grid is used for. Those reported numbers are for full scans. On our truncated-stream splits there is no reported result found on Lacuna, and we will report our reproduction. For OpenEQA, the OpenEQA paper reports roughly 50% for GPT-4V, 33.5% for blind GPT-4 and nearly 87% for humans. Those numbers bound the full-memory setting.

The strongest structured-retrieval competitor is an OSU-3DSG-style pipeline: the same scene graph, vector retrieval, and a multimodal prompt. We implement it on our mapper rather than relying on its released numbers, so that perception quality is held fixed.

Two abstention baselines isolate what coverage adds. The first rejects an answer when the top retrieval similarity falls below a threshold tuned on the same calibration split. The second asks the language model, given the retrieved evidence, whether it has enough information, in the spirit of Mind Palace's sufficiency judgment. All abstaining methods share the calibration data and the same tuning budget of threshold sweeps.

Two ablations isolate the key ingredient. One replaces geometric coverage with a crude proxy, the number of frames seen so far. The other drops the recall term by setting $r=1$.

Beating the baselines means two things at a matched abstention rate. First, our system's rate of confident wrong answers on questions about not-yet-observed content must be clearly lower than the best abstention baseline's. Second, its accuracy on answerable questions must be no worse than pruning alone.

Why not just…?

Why not just abstain when retrieval similarity is low? This is the most serious competitor. When the queried object has no lookalike in memory, it may work nearly as well as our method. It fails when a similar distractor exists, such as a blue mug standing in for a missing red one, because similarity is then high. More fundamentally, it cannot tell "observed and absent" from "never observed," since both produce the same low score. Our splits are built to contain both cases in equal numbers, and the three-way decision accuracy on them settles the question directly. If thresholding matches us on that distinction, the coverage machinery is unnecessary and we will say so.

Why not just let the language model judge whether it has enough information? Mind Palace-style sufficiency judgments reason over what was retrieved. When the needed object was never seen, nothing relevant is retrieved, and the model must infer absence of evidence from an absence of tokens. Language models are known to handle this poorly. Still, a strong model may know that "the kitchen was not mentioned" implies non-observation. We therefore give this baseline the room labels of the visited areas as extra context, which makes the comparison generous.

Why not just keep every frame, or explore exhaustively? Keeping all tokens does not help with unvisited space. Pruning already beats full context on accuracy according to Seeing Once is Enough?. The authors of Enter the Mind Palace note that exhaustive search is the costly fallback when memory falls short. Our active experiment measures path length to a correct answer, so the cost of exhaustive exploration can be compared directly with exploration triggered by coverage.

Proposed Experiments

The central benchmark is constructed from existing data. ScanQA questions come with ground-truth object identifiers, and ScanNet trajectories come with camera poses. From these we can compute the frame at which each question's target objects first become visible. We truncate each stream at several fractions of its length. Each question then gets one of three labels: answerable, not yet observed, or absent from the scene. The absent label comes from a held-out set of plausible-but-missing objects, verified against scene annotations. We apply the same construction to OpenEQA episodic-memory episodes, scoring answers with its LLM-Match protocol, which correlates with human judgment at Spearman 0.909. We also apply it to SQA3D.

The metrics are accuracy on answerable questions, three-way decision accuracy, the rate of confident wrong answers on not-yet-observed questions, and selective accuracy as a function of how often the system abstains.

The decisive check is the subset where a similar distractor exists in memory and the true target lies in unobserved space. There, similarity thresholding and model self-judgment should fail, and coverage should succeed. A second check probes the recall assumption. We stratify errors by object size and test whether a size-dependent $r$ removes the false "absent" claims for small objects. If it does not, the independence assumption behind the posterior is wrong and needs revision.

Attribute recovery is tested on ScanQA and SQA3D questions about color and state. We compare pruning alone with pruning plus coverage-triggered reloading, and report the tokens reloaded per question.

In the active setting, on LA-EQA from Enter the Mind Palace, "not yet observed" outputs drive frontier exploration toward unobserved placement regions. We compare answer correctness and path length against value-of-information stopping. That paper reports gains of 12 to 28% in correctness over prior baselines, but gives no absolute value in the file that we can quote. We will therefore reproduce it under our perception stack.

The outcome that would falsify the proposal is simple. If, on the distractor subset, geometric coverage does not beat the frame-count proxy and the similarity threshold in three-way decision accuracy, then where the map has looked carries no information beyond what retrieval already gives.