Streaming 3D reconstruction systems estimate camera motion and scene geometry one frame at a time while keeping only a small memory of past frames. Each new pose is computed relative to that memory, so small errors compound into large global distortions, known as drift. The usual way to fill the memory is greedy: keep the frames that add the most geometric information. Work on submodular optimization, the study of selection problems with diminishing returns, shows a specific weakness in greedy selection. It concentrates value in a few "super-items" and picks the remaining items mainly because they complement those few. If the super-items are later lost, what is left is nearly worthless.
We argue that this is exactly what happens when a streaming reconstructor's best keyframe is later found to be corrupted by a passing occluder, motion blur, or a bad registration. The proposal is to manage keyframe memory with deletion-robust selection. The memory is organized as a chain of disjoint sub-memories, each chosen to cover the scene well on its own. When a keyframe is flagged as corrupted, the system re-anchors to a surviving sub-memory rather than to complements of the lost frame. The claim to test is concrete: under bursts of corrupted frames, a deletion-robust memory of fixed size gives lower post-event drift than three alternatives of the same size, namely a first-in-first-out window, uniform striding, and a larger greedy memory.
Core Claim
Two failure modes are usually treated separately. On the vision side, causal reconstructors such as STream3R process unbounded streams with a cached transformer memory. Its sliding-window variant keeps an anchor frame plus the most recent frames. STream3R itself reports that this design drifts on long trajectories with no chance to close a loop, and nothing in it replaces anchoring frames that turn out to be uninformative or corrupted. On the optimization side, Deletion-Robust Submodular Maximization proves that taking $k+d$ greedy items does not protect against $d$ deletions. Its ROBUST-STREAMING algorithm instead chains $m+1$ streaming selectors, passing each selector's rejects down to the next, so that at least one selector survives $m$ deletions intact.
Our claim is that keyframe corruption in streaming reconstruction behaves like deletion in this sense. Because the memory was chosen greedily, losing a keyframe costs far more than that frame's own information. Chained, disjoint memories therefore matter specifically for drift after the corruption event, not for average accuracy.
Corruption in video differs from the deletions assumed by the theory in two ways, and both are central to the proposal:
- Corruption arrives in contiguous temporal bursts. An occluder spans many consecutive frames. This links the problem to the contiguous-removal setting of Robust Sequence Submodular Maximization. That paper also shows greedy sequences front-load value into early positions, which parallels the reliance of STream3R and incremental structure-from-motion on the first anchor frames (Structure-from-Motion Revisited).
- Corruption is detected late. A bad frame may already have conditioned the poses registered after it. Deletion therefore means removing an item and also re-anchoring everything that depended on it.
Research Program
The utility being maximized. Every frame the model has processed comes with a predicted point map. We discretize the scene into voxels crossed with coarse viewing-direction bins. A frame's utility is a facility-location coverage score: how well its predicted points cover each (voxel, direction) cell, weighted by the model's own confidence. Coverage of this kind is monotone submodular, and it encodes the same intuition as COLMAP's spatial-distribution voting (Structure-from-Motion Revisited), now as an explicit objective. One caveat: the utility is computed from the model's own possibly drifted geometry, so its evaluations are noisy and not exact. We measure how much this noise erodes robustness by also computing utility from ground-truth geometry.
The memory structure. A memory budget of $k$ frames is split into $r$ disjoint sub-memories. Each is filled by a threshold-based streaming selector of the Sieve-Streaming type, and frames rejected by sub-memory $j$ cascade to sub-memory $j+1$, following ROBUST-STREAMING. Three variants are compared:
- a randomized-pool variant in the style of Scalable Deletion-Robust Submodular Maximization, which samples among candidates that pass the threshold;
- an "uselessness sampling" coreset in the style of Coresets remembered and items forgotten, which keeps low-gain frames with higher probability;
- a burst-aware variant that forbids two sub-memories from drawing their highest-value frames from the same temporal segment, which is the contiguous-removal idea transplanted from the sequence setting.
Detection and re-anchoring. Corruption is flagged in two ways: by a drop in confidence in the model's predictions, or by an inconsistency in the frame's reprojection against the other sub-memories. When a sub-memory loses its high-value frames, attention is redirected to the best surviving sub-memory. Recent poses are then re-estimated against it inside a short re-registration window.
Where theory stops. The randomized guarantees in these papers assume an oblivious adversary, meaning one that does not see the algorithm's random choices. Nature roughly meets this condition, but corruption correlates with content: textureless walls are both low-utility and easy to lose tracking on. We will report utility retention against the theoretical floor, which is $1/2-\epsilon$ for the randomized pool, and identify which correlated corruptions fall below it.
A known risk. STream3R was trained on temporally contiguous windows. A memory of non-contiguous frames may therefore be out of distribution for it. We run training-free first. If the contiguity ablation below shows a penalty, we add a short fine-tune on randomly gapped windows and apply it to all memory policies equally.
Baselines
Every policy runs inside the same STream3R backbone with the same memory budget $k$ (measured in frames, which sets the size of the key-value cache), the same input streams, the same corruption schedule, and the same tuning budget for any hyperparameters.
Do nothing: STream3R-W. The naive reference point is the released sliding window (STream3R), which keeps the anchor frame plus the most recent frames. It is the deployed default and the reason the question arises. STream3R reports real-time speed above 32 FPS on an A100, but the file gives no numerical accuracy figure for it on Sintel. Beating it means lower post-event drift at a comparable frame rate.
Unbounded cache. The full-cache causal model is run wherever memory allows. It is an upper reference for how much information a memory can hold, not a competitor at equal cost.
Uniform stride. Every $N$-th frame is kept, with $N$ chosen to match budget $k$.
Greedy coverage with budget $k+d$. The same coverage objective is used with an expanded budget and no robust structure. This is the strongest competitor on the specific question, because it tests whether a larger budget, rather than the chained structure, is what helps. The proposal beats it if a robust memory of size $k$ matches or beats greedy at $k+d$ on post-event drift.
Reservoir sampling. Frames are sampled uniformly at random under the same budget, followed by the same confidence filtering and re-anchoring used in the proposal. This isolates whether coverage-driven selection adds anything beyond random diversity combined with re-anchoring.
Offline accuracy reference. FastVGGT, an offline geometry transformer that merges image tokens, reports a Chamfer distance of 0.425 on 1,000-frame ScanNet-50 sequences. The same paper reports 0.471 for a memory-efficient VGGT baseline and 0.684 for Fast3R. FastVGGT sees all frames at once, so it is not an equal-cost comparison. Matching it is not the bar. Narrowing the gap between STream3R-W and 0.425 under corruption is.
Ablations. Three ablations isolate the key ingredient:
- the chained memory without re-anchoring;
- a single diversity-maximizing memory without disjoint sub-memories;
- the chain built with per-frame random scores in place of coverage.
Why not just…?
Why not just store more keyframes? The submodular result (Deletion-Robust Submodular Maximization) says extra greedy items tend to complement the lost super-items rather than replace them. Memory is also tight in this setting: original VGGT runs out of memory at about 350 frames on an 80GB GPU, and full token sets raise Chamfer distance from 0.425 to 0.471 (FastVGGT). Still, video frames may be redundant enough that $k+d$ greedy quietly works, and the comparison against greedy at $k+d$ settles this. If it ties our method, we conclude that budget, not structure, matters.
Why not rely on periodic global bundle adjustment or loop closure? Bundle adjustment jointly refines all poses and points, and loop closure corrects drift when the camera revisits a place. Loop closure does nothing on exploratory paths with no revisits (Elastic Fragments). Global refinement is costly and depends on a reasonable initialization (Structure-from-Motion Revisited). The two approaches are complementary. We also report results after one final global bundle adjustment, to see whether better streaming memory leaves the optimizer a better starting point.
Why not just sample randomly and filter bad frames? This is the most serious threat. The randomized-pool algorithms are themselves largely random sampling, and random memories are naturally diverse. The reservoir-plus-re-anchoring baseline and the random-score ablation exist to settle this. If coverage-driven selection does not beat them on burst corruption, we will report that the benefit comes from disjointness and re-anchoring, not from submodular utility.
Proposed Experiments
Data and corruption. The primary benchmark is long ScanNet sequences, specifically the 1,000-frame ScanNet-50 protocol (ScanNet; FastVGGT). ETH3D multi-camera video (ETH3D) adds outdoor scenes and laser-scan ground truth. Sintel follows STream3R's own evaluation. Into these streams we inject corruption bursts (synthetic occluders, blur, and dropped frames) with burst length, rate, and timing controlled. We also evaluate on the naturally hard segments of each sequence without injection.
Metrics. We report absolute trajectory error, Chamfer distance, and drift per meter measured over the 200 frames following each corruption event. We also report the coverage utility retained after deletion, normalized against an offline greedy solution computed with ground-truth geometry.
Decisive checks. Three results would decide the question:
- Gap grows with corruption. As burst rate increases, the post-event drift gap between the robust memory and greedy at $k+d$ should widen. With no corruption, the two should be nearly equal. If the gap is flat across corruption levels, the mechanism is not deletion robustness.
- Content-correlated corruption. When corruption is made to correlate with content by targeting high-utility frames, the randomized variants should degrade more than the burst-aware chain. This tests the oblivious-adversary assumption directly.
- Short sequences and overhead. On short 5–10 frame sequences, where FastVGGT notes that aggressive reduction hurts, the robust memory should perform no worse than the full cache. Selection overhead should keep throughput within a stated fraction of STream3R-W's 32 FPS.
References
- STream3R: Scalable Sequential 3D Reconstruction with Causal Transformer
- Deletion-Robust Submodular Maximization: Data Summarization with "the Right to be Forgotten"
- Robust Sequence Submodular Maximization
- Structure-from-Motion Revisited
- Scalable Deletion-Robust Submodular Maximization: Data Summarization with Privacy and Fairness Constraints
- Coresets remembered and items forgotten: submodular maximization with deletions
- FastVGGT: Fast Visual Geometry Transformer
- Elastic Fragments for Dense Scene Reconstruction
- ScanNet: Richly-Annotated 3D Reconstructions of Indoor Scenes
- A Multi-view Stereo Benchmark with High-Resolution Images and Multi-camera Videos