CS Paper Radar

Degree-Equalized View-Graph Selection under Tight Pair Budgets

Minhyeok Im, Jongseong Brad Choi

cs.CV ·submitted 2026-11-05 06:01 UTC · v1
benchmark

Abstract

Fully matching all image pairs in Structure-from-Motion is quadratic in the number of images, so practical pipelines pass a budgeted subset to the final matching and reconstruction backend. One-shot selectors score candidates with image retrieval, cheap geometric probes, or a learned prior and finalize B pairs before full matching. Their priorities do not account for the degree already allocated to each image, which can concentrate edges on a few images. Across nine large 1DSfM internet photo collections at B=2N, the coverage top-B selector leaves 54% of covered images with realized degree at most two. Reconstruction can then fail even when the selected graph is nearly connected and almost fully verified. Our training-free greedy rule, Degree-Equalized Allocation (DEAL), exponentially downweights pairs whose endpoints are already well covered. On these collections, DEAL improves the one-shot selector built on the same prior (from 0.776 to 0.929) and matches the mean registered-image ratio of an SfM-supervised edge prior under the shared backend (0.929 vs 0.930), without training. On the largely saturated 38-scene standard benchmark suite, DEAL gives the highest mean among the evaluated training-free selectors (0.875 vs 0.858 one-shot).

Closest papers

Nearest neighbours by meaning across the whole index.

CertEx: Exact Visual Retrieval at Scale by Certified Exclusion

cs.CV ·2026-10-15 ·Dongfang Zhao
theory similarity 0.61
Abstract · 30 pages, 12 figures

Exact $k$-nearest-neighbor (kNN) search over image descriptors and embeddings underlies visual retrieval, near-duplicate detection, the evaluation of learned representations, and increasingly the memory of LLM agents. However, exhaustive search computes every distance at full precision, whereas approximate indexes return recall below one. We observe that exact search only needs a proof that each excluded vector cannot be a neighbor. Because such a proof only has to be conservative, it can be checked in low precision, much as the retina examines the whole scene at low resolution. We call this principle certified exclusion and realize it in an exact kNN method for GPUs, which we call CertEx. Specifically, CertEx stores a lower-bounding projection of each vector in half precision and folds a rounding certificate into the same tensor-core dot product, so that only the few vectors that the test keeps need exact distances. We prove that CertEx returns the exact kNN of every query. On sixteen datasets with up to 100M vectors, CertEx is exact for every query at 7.1$\times$ to 18.0$\times$ the throughput of the fastest cuVS search on one H100 (8.8$\times$ to 11.8$\times$ on an A100) and outperforms quantized and graph indexes whenever every query must be exact.

0.43

Layer-Matched Sparse Attention for Low-Redundancy 3D Reconstruction

cs.CV ·2026-11-17 ·Sammam Mahdi, Fariha Binta Salim, K. M. Jubair Sami, Rakin Bin Rabbani
similarity 0.57
Abstract

VGGT reconstructs cameras and geometry from unposed images in one pass, but its global attention grows quadratically with the number of views. Training-free accelerators thin this attention and work well on redundant video, but lose pose accuracy when views share little geometry. This paper traces these losses to two kinds of cross-view information that a uniform sparse approximation can fail to preserve together: diffuse layers aggregate distributed context, whereas matching layers depend on query-specific interactions that carry little attention mass. A per-layer statistic measures the log-mass missed by a mean token. Its row-free proxy is the logit variance, and it selects the estimator for each layer. Diffuse layers use shared, importance-sampled hub keys, with log-weights that make the softmax numerator and denominator unbiased. Matching layers stay exact: every aggressive thinning tested cost accuracy. At equal cost, the selected layers outperform the four shifted windows tested. On 13 unseen low-redundancy scenes with 32 views, LMSA stays within 1.4 AUC@5 of dense attention, compared with 10.3 for AVGGT and 4.5 for SAF3R; its difference from contemporaneous GPA-VGGT is not significant, and only its gains over AVGGT pass both scene-level tests. With 100 views, it stays within 1.9 AUC@5 while its aggregator runs $2.0\times$ faster. Used post hoc to choose the layers GPA-VGGT protects, the statistic improves it by 1.2 AUC@5 for 5% more FLOPs. Applied untuned to $π^3$, it beats AVGGT but remains further from dense accuracy.

0.22

CACO: Coverage-Aware Coordinated Optimization for Continuous Generative Retrieval

cs.IR ·2026-11-19 ·Pan Zhang, Nan Zhuang, Yongkang Zhang, Kun Xú, Zhongtao Jiang +3 more
similarity 0.57
Abstract · 21 pages, 16 figures, 12 tables

Continuous generative retrievers powered by flow matching and diffusion sample multiple queries in item embedding space for parallel approximate nearest-neighbor (ANN) search under fixed retrieval budgets. However, optimizing distribution diversity or target-level interest separation ignores set-level retrieval geometry: sampled queries collapse onto overlapping ANN neighborhoods, while discrete top-K lookup and single-target supervision block end-to-end coverage optimization. We introduce CACO (Coverage-Aware Coordinated Optimization), a lightweight self-supervised post-training framework that coordinates queries from frozen flow-matching and diffusion retrievers toward complementary item coverage with negligible additional inference latency. CACO uses empirical retrieval frequencies across sampled reference queries as a relevance proxy, formulating a label-free coverage objective that improves recall across all 30 backbone-dataset settings in offline greedy selection experiments. To avoid the inference overhead of generating a large query pool, CACO employs a coordinated query adjustment network that combines inter-query bidirectional attention with gated relative directions, finally updating queries by bounded tangent-space projection and spherical retraction. During training, CACO applies tangential antithetic perturbations and measures each query's marginal gain via counterfactual single-query replacement, yielding an unbiased gradient estimator of smoothed set coverage across non-differentiable ANN search. On eight public benchmarks and an in-house 24-partition streaming industrial dataset, CACO improves Recall@100 by up to 23.7% and Recall@400 by up to 23.9% over the strongest baseline, cuts inter-query overlap by 53.3%-64.9%, and adds only 0.5%-3.0% inference latency.

0.21

A $59/33$ Cut-LP Guarantee for Matching Augmentation

cs.DS ·2026-09-22 ·Morteza Alimi, Tobias Mömke
theory similarity 0.57
Abstract · 20 pages, 6 figures

The Matching Augmentation Problem (MAP) asks for a minimum-cardinality set of unit-cost edges that, together with a zero-cost matching, forms a 2-edge-connected spanning multigraph. We study the standard cut relaxation. Bamas, Drygala, and Svensson proposed a particularly simple LP-guided algorithm: compute an extreme optimum, run a depth-first search that prioritizes large LP coordinates, and augment the resulting DFS tree optimally. We give a new structural analysis of the Bamas--Drygala--Svensson LP-guided DFS algorithm. The analysis combines an exact primal--dual identity for the residual uplink problem with a rank bound that measures fractional support relative to the unit-valued skeleton. The result is that for every root and every deterministic tie-breaking order consistent with the LP priorities, the algorithm returns a solution of cost at most $\frac{59}{33}c(x^*)-\frac{25}{33}=\left(2-\frac7{33}\right)c(x^*)-\frac{25}{33}\approx1.788c(x^*)-0.758$, where $x^*$ is an optimum of the cut LP. Consequently, the integrality gap of the relaxation is at most $59/33\approx1.788$. No new algorithmic step is required; the improvement is analytical. The exact packing certificate for the residual uplink problem yields a cost identity with a packing-slack term, while a rank theorem bounds fractional support relative to the unit-valued skeleton. A regional classification accounts for the non-tree edges, and a two-cut identity handles self-holes. As a direct corollary, the same $59/33\approx1.788$ bound holds for Forest Augmentation in the minimum-value regime. The proof is self-contained apart from one theorem on the dimension of minimum-cut vectors.

0.33

Web Scale on a Budget: Tail-Aware Retrieval Evaluation

cs.CV cs.IR ·2026-10-13 ·Boaz Meivar, Shai Avidan
benchmark similarity 0.57
Abstract · 19 pages, 8 figures, 10 tables

A common practice in instance retrieval is to grow the gallery size to improve a benchmark's discrimination capability. One prominent example is ILIAS, which adds up to 100 million distractor images. The prevailing assumption is that faithful evaluation demands web scale, and that indexing all 100M images through the backbone is the unavoidable price of a comparable number. That price is steep: hundreds of GPU-hours and ~200 GB of descriptors per model, paid again for every method or ablation. We show the web-scale indexing price is largely avoidable: evaluation itself obeys a scaling law. The number of distractors that outrank a positive is Binomial in the gallery size. We define the per-query retrieval hardness, a gallery-scale agnostic quantity that yields a retrieval metric at any scale, and demonstrate it can be derived from a small random sample. The underlying sampled-rank machinery is long established in recommender-system and biometric evaluation, but to our knowledge has never been adapted to visual retrieval. We make the law per-query and estimable, and validate it at true 100M scale on ILIAS and INSTRE, and on the full 759k-distractor Google Landmarks v2 pool. Concretely, within a 5% sample (a flat 20x less indexing), every backbone's tail-aware (EVT) estimate has converged onto the large-scale mAP, to within ~0.01 (mean absolute error 0.005), across five backbones, three benchmarks, and two distractor pools (mAP@1000 at 100M on ILIAS/INSTRE; the official mAP@100 at the full 759k pool on GLDv2); the recommender-systems count baseline over-predicts everywhere (+0.037 to +0.068). This is an order of magnitude better than naively reporting the metric on the same subset (+0.08 to +0.13). We release code and the per-query hardness to facilitate faster, cheaper, and greener retrieval evaluation.

0.20

MatcherCompass: A Deployment-Aware Benchmark to Guide Image Matcher Selection in the Wild

cs.RO ·2026-09-22 ·Hyunwoo Kim, Giseop Kim
benchmarkcode/data similarity 0.56
Abstract · 8 pages, 7 figures

Field robots operating across time of day and sensing modalities require accurate image correspondences within onboard time and resource budgets. However, accuracy and runtime reported for individual methods on a single device provide limited guidance for choosing a matcher and its configuration on a target platform. We present MatcherCompass, a deployment-aware benchmark for choosing local feature matchers in field robotics. Under common input and pose-evaluation procedures, we compare nine classical and learned matching pipelines across four image resolutions and supported numerical precisions. Four visual conditions cover viewpoint variation, day--night matching in visible and thermal imagery, and daytime visible--thermal matching. We evaluate pose accuracy using the area under the error--recall curve (AUC) at $5^\circ$, $10^\circ$, and $20^\circ$, and measure runtime, GPU memory, and energy per image pair on four GPU platforms spanning workstation and onboard computers. The results show that changes in hardware, input resolution, and numerical precision can move a matcher across a runtime budget boundary, altering the feasible choices. We organize the measurements into a selection guide that returns all configurations satisfying user-specified time and resource limits, together with their accuracy under the selected visual condition. MatcherCompass provides measured evidence for choosing matching pipelines that fit a robot's sensing conditions and computing hardware. Project page: https://matchercompass.github.io/.

0.38

When Does Sliced Inference Pay Off? Resolution, Tiling and Dense Fusion for Small Object Detection

cs.CV ·2026-11-09 ·Stefan Becker, Jens Bayer, David Münch, Wolfgang Hübner
code/datahot direction similarity 0.56
Abstract

Sliced inference such as SAHI is the standard remedy for small objects in high-resolution imagery, but its gains are usually measured against low-resolution baselines. We revisit sliced inference with scale as the explicit variable and ask when tiling actually pays off. We compare nine dense detectors, eight YOLO models of four generations and FCOS, on VisDrone and DOTA, under pre-specified hypotheses, calibration-only tuning and a single evaluation on held-out test data. Two findings emerge. First, much of the benefit attributed to slicing is a resolution effect: on VisDrone, a single pass trained at a higher resolution outperforms tiling with box fusion (merging decoded boxes) for every detector that could be trained at that resolution, and at equal compute a higher resolution helps more than a larger model. Second, tiles carry complementary information that box fusion wastes. We introduce SCAHI (Slicing with Coverage-Aware Hyper Inference), which accumulates the dense outputs of all passes with weights that give every image position the same total coverage, and reads objects off a peak grid fine enough to keep crowded neighbours apart. On identical passes, SCAHI outperforms box fusion for every YOLO detector on both datasets and matches it for FCOS. On DOTA, whose images far exceed the resolution a single pass can be trained at, tiles with SCAHI beat the best single pass for every detector, by 4.3 to 5.6 mAP50 at 2048 px, and replacing only SAHI's merge step by SCAHI adds 2.3 to 4.0 mAP50. An ablation attributes the gain to the border weighting and the resolution of the peak grid. Source code is available at https://github.com/beckerio/scahi.

0.42

MINER: Multi-crop INference-time Enhancement for Rare-Object Retrieval with Frozen Dual Encoders

cs.CV ·2026-09-22 ·Abdulmalik Alquwayfili, Faisal AlMeshal, Jumanah Almajnouni, Huda Abdulhadi Alamri, Muhammad Kamran J Khan
top venuebenchmarkcode/data similarity 0.56
Abstract · 29 pages, 10 figures, 19 tables. Accepted at ACML 2026. To appear in Proceedings of Machine Learning Research, volume 353. This version incl…

Text-to-image retrieval with frozen dual encoders degrades when the query names a small, visually subordinate object in a cluttered scene: a single global image embedding underrepresents the localized visual evidence. We present MINER, a training-free inference framework that augments a frozen dual encoder's global image embedding with a small bank of region-level embeddings and a hubness-correcting similarity rescoring, recovering visual evidence that global pooling underweights. To evaluate this setting, we introduce ROCS, a benchmark built from high-clutter subsets of Flickr30K and MS COCO whose images are re-captioned to name a single low-salience object. Experiments on CLIP, SigLIP, and SigLIP 2 show that MINER improves retrieval on every backbone, on ROCS and on the standard splits. Analyses show that these gains come primarily from broader spatial coverage rather than precise crop placement, revealing a simple and general way to recover localized evidence from frozen representations. Code: https://github.com/aalquwayfili/MINER. Dataset: https://huggingface.co/datasets/aalquwayfili/ROCS.

0.48