Segmentation models are ranked by numbers such as mean intersection-over-union (IoU, the overlap between predicted and true regions divided by their combined area) or pixel-level precision-recall curves. These numbers are dominated by large regions. Roads and sky count for millions of pixels, while a fallen tire or a distant pedestrian counts for a few hundred. The vision community has answered with many corrected metrics: per-image, per-class, per-instance and worst-case IoU, component-wise scores for road obstacles, and size-invariant errors. Each one, though, yields a single new number computed by a one-off script. None of them can say which images or objects drive the number, whether a model ranking would survive removing a handful of small objects, or how much a fixed choice such as "ignore components under 50 pixels" moves the result.
We propose to treat segmentation evaluation as a database query and to run it under semiring provenance. Semiring provenance is a technique from databases that records, alongside each query answer, an algebraic expression saying which input facts it came from and how they were combined. We first reduce every size-aware metric in the literature to an aggregate query over a small relation: the bipartite overlap graph between predicted and ground-truth connected components, with a pixel count on each edge. We then annotate that relation with tokens for components, images and attributes, and evaluate the query once with an off-the-shelf provenance engine on an unmodified database. The result is a reusable symbolic object. From it we can recompute any metric variant exactly under deletions, label edits and size cutoffs, attribute metric gaps to individual objects, and certify how many small objects would have to change before two models swap rank.
Core Claim
The claim has three parts. The first is a reduction. Dataset-level, image-level, class-balanced and instance-approximated IoU (Revisiting Evaluation Metrics for Semantic Segmentation), component-wise sIoU (SegmentMeIfYouCan), Cityscapes instance-level iIoU (Cityscapes), image-wise NmIoU (Evaluating the Adversarial Robustness of Semantic Segmentation) and size-invariant error over foreground frames (Towards Size-invariant Salient Object Detection) are all ratios of sums over this overlap relation, sometimes followed by an average or a percentile. That relation is orders of magnitude smaller than the pixel grid.
The second part is that several of these metrics are non-monotonic. Adding a fact can remove a contribution. For example, sIoU excludes from a predicted component's false positives any pixels that overlap other ground-truth components, and a component-level false positive is "a predicted component that matches no true object". Because of this, the naive shortcut of storing per-group confusion counts and subtracting them is not exact under counterfactual edits. Exactness requires provenance with a difference operator, in the sense of the spm-semirings of Algebraic Structures for Capturing the Provenance of SPARQL Queries.
The third part is a capability that scripts lack. Once a metric is a provenance expression, the question "what is the smallest set of components whose removal or relabeling reverses the ranking of models A and B" becomes a constraint problem a solver can attack. This mirrors how Proving Cypher Query Equivalence turns semiring-annotated graph queries into SMT problems (satisfiability modulo theories, i.e. logical constraint solving).
Concretely, let $x_c \in \{0,1\}$ indicate whether component $c$ is kept. Let $I_M(x)$ and $U_M(x)$ be the provenance-derived intersection and union pixel counts of model $M$ for a class, written as polynomials in the $x_c$ (non-monotonic metrics add Boolean conditions on neighbouring components). A ranking certificate is then the smallest $|\{c : x_c = 0\}|$ such that
$$I_A(x)\,U_B(x) < I_B(x)\,U_A(x),$$
which is a quadratic pseudo-Boolean constraint. The single-number corrected metrics cannot express this question at all.
Research Program
The pipeline starts from saved prediction masks or score maps. It never instruments the network. The first stage extracts connected components from ground truth and from thresholded predictions, plus a small number of score bins per component for curve metrics. It then writes the overlap relation as rows of the form (image, ground-truth component, predicted component, class, score bin, pixel count), together with component attributes such as area, distance band and weather condition. Pixels are never tokens. This avoids the token explosion and the false independence assumption that come from treating spatially correlated pixels as separate facts, a limitation flagged by Using A Probabilistic Database in an Image Retrieval Application. That paper is the closest prior work. It loads YOLOv5 bounding boxes into ProvSQL and uses provenance probabilities and Shapley values to rank retrieved images. It never touches dense masks, and it never treats evaluation metrics themselves as queries. We do the latter, and we use counting and Boolean interpretations rather than probabilities, so tuple independence is not needed.
The second stage writes each metric as standard SQL over this relation. The non-monotonic pieces, such as matching, exclusion and ignore regions, become NOT EXISTS or EXCEPT clauses. We run these queries through ProvSQL, which builds provenance circuits through PostgreSQL's planner hook without kernel changes and supports a difference operator. We use GProM as a second middleware backend to check that the approach is not tied to one engine. This is the sense in which the engine-agnostic direction enters: it is an implementation constraint, not a contribution. We deliberately do not attempt provenance rewriting of tensor runtimes.
Both systems support aggregates only weakly, and that limitation shapes our design. ProvSQL lacks full semimodule support for SUM, and SPARQLprov handles aggregates in a way that breaks homomorphisms, meaning the provenance can no longer be translated faithfully into other interpretations. We therefore keep provenance on the sums only, as tensors of counts and polynomials. The final ratio, average or percentile is applied after the provenance expression has been evaluated under a concrete assignment of the tokens.
The third stage builds analyses on these circuits. Exact counterfactual recomputation evaluates a circuit under a Boolean assignment. Attribution computes Shapley values over components, which estimate each component's average contribution to the metric across subsets of the data, following the circuit-based Shapley computation of the image-retrieval paper. We compute these by Monte Carlo sampling, because ratio metrics are not linear in the tokens. Ranking certificates are solved with an SMT or integer-programming solver. To keep the solver tractable, we restrict the variables to components whose removal changes either model's counts by more than a tolerance.
Baselines
The naive reference point is the official evaluation code for each benchmark, rerun from the saved masks for every counterfactual or Shapley sample. This is the SMIYC sIoU and component scripts, the Cityscapes iIoU script, and our reimplementations of the fine-grained IoU family checked against the published definitions. This baseline is exact by construction and defines ground truth for every exactness measurement. It is beaten if our system returns identical numbers while answering thousands of counterfactual queries orders of magnitude faster.
The strongest competitor is a cached-overlap script: Python code that reads the same overlap relation we build and recomputes each metric directly, including hand-written matching logic. It has the same compact data and the same compute, and it is the obvious thing a careful vision researcher would write. We will give it the same precomputation, the same hardware, and an equal engineering budget of one bespoke function per metric. On speed for single counterfactuals it may tie or win, and we will report that honestly. The proposal beats it only where it has no counterpart. One case is the minimal-flip certificate, where the script can only do brute-force or greedy search; we compare the certified minimum against greedy deletion by the script. The other case is adding a new metric or slicing rule, which needs a new SQL query for us but new matching code for the script.
The third baseline is grouped-count subtraction: per-(image, component, class) confusion counts stored in a dataframe, with counterfactuals computed by subtracting removed groups. This is exact for monotone metrics. The key ablation is the same pipeline with positive-only provenance, which drops the difference operator. It isolates whether the non-monotonic algebra is what buys exactness.
For context on what the models being audited achieve, the survey Out-of-Distribution Segmentation in Autonomous Driving reports 95.12% pixel AUPRC (area under the precision-recall curve) and 0.08% FPR95 for RbA, and 94.38% AUPRC for UEM, on SMIYC-OT. UGainS reports 29.75% instance AP on Fishyscapes Lost and Found, against about 17% for connected-component grouping. For provenance overhead, SPARQLprov reports 36–56% average runtime overhead on Wikidata depending on query type. No reported result was found on Lacuna for provenance overhead on any vision evaluation workload.
Why not just…?
Why not just store per-component confusion counts in a dataframe and subtract? This is the most serious threat. For dataset-level and per-image IoU under whole-image deletion, it is exactly right, and we expect to say so. It fails when one edit changes another component's status. Removing a ground-truth obstacle can turn an overlapping prediction into a false positive. A size cutoff can merge or drop components. Under sIoU's exclusion rule, a pixel's role depends on its neighbours. Experiment two measures the size of this error directly. If it is negligible on SMIYC and Lost and Found, the non-monotonic machinery is unjustified for those metrics, and we will narrow the claim accordingly.
Why not just recompute the official metric for each what-if? These benchmarks are small: 327 images in RoadObstacle21 and 1,043 in Lost and Found. A single recomputation is therefore cheap, and for a handful of questions this is the right tool. Shapley estimates need thousands of evaluations per model pair, and certificate search is combinatorial, which is where recomputation stops scaling. Experiment four reports where the crossover lies rather than assuming it.
Why not just report the existing instance-aware metrics? sIoU, iAP and the fine-grained IoU family fix the weighting, and we use them as the query targets. Each still gives one number per model, and each embeds its own choices. One example is the small-component filters the out-of-distribution survey criticizes. Another is the worst-case percentile, which Revisiting Evaluation Metrics found to be 0% for every model on PASCAL Context and which its authors could only diagnose by manual inspection. Our contribution is to measure how stable these numbers and rankings are, not to replace them.
Proposed Experiments
The first experiment establishes correctness. On Cityscapes, PASCAL Context, SMIYC (RoadAnomaly21 and RoadObstacle21) and Lost and Found, the declarative queries must reproduce every reference metric to numerical tolerance, for every model whose predictions or checkpoints are available.
The second experiment tests exactness under counterfactual edits. We sample component deletions, ground-truth relabelings, and size-cutoff sweeps from 0 to 100 pixels. For each edit we compare three things against full recomputation: grouped-count subtraction, positive-only provenance, and full provenance with the difference operator. We report the error distribution separately for each metric.
The third experiment is the scientific payoff. For model pairs that are close under pixel AUPRC, such as the 0.74-point gap between RbA and UEM on SMIYC-OT, and for pairs on Cityscapes under the IoU variants, we compute Shapley attributions and minimal ranking-flip certificates at fixed operating thresholds. This sidesteps the threshold-free curve problem the survey raises. Curve metrics are handled approximately through score bins. We hypothesize that pixel-metric rankings flip under the removal of a few large-component images, while component-metric rankings hinge on a few small, distant obstacles. Either outcome tells benchmark designers which reported gaps are meaningful.
The fourth experiment measures cost: wall-clock time and memory against both script baselines across query counts, plus provenance-construction overhead relative to plain SQL evaluation.
The decisive checks are experiment two, which decides whether the provenance algebra is needed at all, and the certificate comparison in experiment three, which decides whether the provenance representation gives answers that greedy scripted search cannot.
References
- Revisiting Evaluation Metrics for Semantic Segmentation: Optimization and Evaluation of Fine-grained Intersection over Union
- SegmentMeIfYouCan: A Benchmark for Anomaly Segmentation
- The Cityscapes Dataset for Semantic Urban Scene Understanding
- Evaluating the Adversarial Robustness of Semantic Segmentation: Trying Harder Pays Off
- Towards Size-invariant Salient Object Detection: A Generic Evaluation and Optimization Approach
- Algebraic Structures for Capturing the Provenance of SPARQL Queries
- Proving Cypher Query Equivalence
- Using A Probabilistic Database in an Image Retrieval Application
- ProvSQL: Provenance and Probability Management in PostgreSQL
- GProM - A Swiss Army Knife for Your Provenance Needs
- Computing How-Provenance for SPARQL Queries via Query Rewriting
- Out-of-Distribution Segmentation in Autonomous Driving: Problems and State of the Art
- UGainS: Uncertainty Guided Anomaly Instance Segmentation