Which Images Deserve Twenty Minutes? Online Triage for Zero-Shot Super-Resolution

The best blind super-resolution methods for unusual blur now train a model on the single input image itself. Blind super-resolution means sharpening an image when the blur that degraded it is unknown. These methods pay heavily in compute for that choice. KernelFusion trains a patch diffusion model on crops of one low-resolution image and jointly recovers the blur kernel. On the Blind144 stress test of 144 non-Gaussian kernels it reaches 27.19 dB PSNR against 24.82 dB for the best externally trained network, but it needs about twenty minutes per image on an L40S GPU. In any real pipeline, whether a camera archive being ingested or a stream of scientific or forensic images, you cannot run it on everything. You can afford it on a handful of images. The problem is to decide, as each image arrives and before seeing the rest, whether to spend one of those few expensive runs on it or to settle for a fast external model.

We propose to treat this as online selection with a small, granular inventory: a budget of $k$ runs, with $k$ between 2 and about 10, spread over a stream of hundreds of images. Each run consumes a whole unit of the budget and cannot be split. The core idea is that the value of an expensive run can be estimated cheaply, and without any reference image, from the image's own cross-scale self-similarity. Natural images repeat their small patches across scales, and an unusual blur breaks that repetition. How strongly the input and a cheap restoration violate cross-scale consistency is therefore a label-free signal of how much the internal method will help. We combine that signal with acceptance thresholds that are specific to each remaining budget unit and that are recalibrated after every executed run, whose actual gain becomes observable once it finishes.

Core Claim

Our claim is that a low-dimensional vector of cross-scale recurrence statistics predicts the PSNR gain of internal super-resolution over a fast external model. It should do so better than generic deep image embeddings, whose dominant directions describe content rather than degradation. Fed into unit-specific online thresholds that correct themselves from realized gains, this predictor should recover a large fraction of the offline-oracle gain even when $k$ is tiny and the arrival order is adversarial. That combination is new. The online-allocation work closest to it, A Learning-Augmented Approach to Online Allocation Problems and Augmenting Online Algorithms for Knapsack Problem with Total Weight Information, assumes items are infinitesimal and values are given as scalars. The internal-learning work assumes each image will be processed and never asks which images should be.

Why the pieces fit

The four ingredients play different roles.

The small-inventory setting defines the problem. When each item takes a large share of capacity, fluid methods break down. Dual mirror descent in the style of Balseiro et al. adjusts prices smoothly, but a single acceptance can exhaust the budget (Kang et al.), and there are no large numbers to average out a bad call (Ma et al.). The closest structural template is r-Dynamic from Posted Price Mechanisms for Online Allocation with Diseconomies of Scale, which keeps a separate threshold distribution for each of the $k$ units. It is proven optimal at $k=2$ and asymptotically, but not for the intermediate $k$ that we care about. We reuse its unit-specific structure. Where it assumes known value distributions, we supply predicted values and recalibrate the thresholds online.

Cross-scale self-similarity supplies the value signal. Super-resolution from a single image showed that over 90% of small patches recur across scales in natural images. Separating Signal from Noise Using Patch Recurrence across Scales showed that corruption becomes visible as a break in that recurrence down a scale hierarchy. KernelGAN turned the principle into kernel estimation: the correct kernel is the one that best preserves patch statistics across scales. We do not estimate the kernel at triage time. We only measure, cheaply, how far the image departs from that ideal.

Feature redundancy acts as a design constraint and as a hypothesis to test. Gaussian Image Anomaly Detection with Greedy Eigencomponent Selection showed that in deep CNN features the high-variance components encode normal content, while the subtle signal of interest sits in low-variance components. A handful of well-chosen dimensions beat full PCA. We expect the same for predicting degradation severity. The standard move of embedding each image with a pretrained network and regressing gain should fail under shift in the kernel family, because its dominant axes separate buildings from faces rather than benign kernels from strange ones.

Adaptive parameter control makes the thresholds robust to poor calibration. The feedback-driven controllers in AdaEvolve and Adaptive TPOT adjust search parameters from observed progress. We borrow the principle, not the machinery. Each executed run reveals a true gain, which we use to update the mapping from predicted to realized gain. ExTS warns that a diagnostic pilot phase eats into a tight budget. Our feedback therefore comes only from runs the policy would have chosen anyway, and cheap features are computed on every image without spending budget.

Research Program

We define the problem as follows. Images $y_1,\dots,y_N$ arrive in sequence. For each image, a fast default restorer produces $\hat{x}_t$ at negligible cost. An irrevocable choice $s_t\in\{0,1\}$ decides whether to also run the expensive internal method, which yields gain $g_t$, its PSNR improvement over the default. The goal is

$$\max \sum_{t=1}^{N} g_t s_t \quad \text{subject to} \quad \sum_{t=1}^{N} s_t \le k,$$

where $g_t$ becomes known only if $s_t=1$ and the run finishes. We call the decision irrevocable because a run cannot be taken back once started, and a skipped image has already been passed downstream.

The first component is the cross-scale value predictor. For each image we compute a small set of statistics at three to four pyramid levels. The first is the distribution of nearest-neighbor patch distances between $y_t$ and its own downscaled copies, which measures how intact internal recurrence is. The second is the back-projection residual obtained by downscaling $\hat{x}_t$ and comparing it with $y_t$, which measures how inconsistent the fast model's output is with the input. The third is the same pair of statistics computed along localized columns across scales, in the spirit of the needles of descendants in Separating Signal from Noise. Together these give a vector of a few dozen numbers, computed in seconds. A small monotone regressor maps them to a predicted gain $\hat{g}_t$. It is fit on a calibration set drawn from kernel families that are disjoint from the test families.

The second component is the threshold policy. When $i$ of the $k$ units have been used, image $t$ is accepted if $\hat{g}_t$ exceeds a threshold $\phi_i(t/N)$ that depends on the unit index and on the fraction of the stream elapsed. The thresholds start from a secretary-style initialization and are shaped like r-Dynamic's unit-specific distributions, with randomization to guard against adversarial orderings. After each executed run, the realized pair $(\hat{g}_t, g_t)$ updates an isotonic recalibration of the predictor. The thresholds are then recomputed on the recalibrated scale. To keep a worst-case floor when the predictor is wrong, we add a fallback in the manner of Cohen and Panigrahi: if realized gains fall persistently below prediction, the policy reverts to a prediction-free random-threshold rule.

The third component is an analysis of intermediate $k$. We will compute, numerically and exactly by dynamic programming over small instances, the best achievable competitive ratio for $k$ from 3 to 10 under noisy value predictions. We then ask how close the unit-specific adaptive policy comes. This addresses, empirically, the regime Posted Price Mechanisms leaves unproven. We make no claim to close it theoretically.

Baselines

The naive reference points come first. The first is the fast default model applied to every image, which gives zero gain by definition. The second is random selection of $k$ images, which gives the expected gain of spending the budget blindly. The third is the offline oracle that sees every $g_t$ and takes the top $k$. It is the upper bound, and dividing by its gain gives our empirical competitive ratio. For the default we will use CATANet, which reports a 0.33 dB PSNR gain over SPIN at ×4 on Urban100 at about twice the speed. It is exactly the kind of cheap external model a pipeline would run by default. For the expensive method we will use KernelFusion, and in a cheaper variant KernelGAN plugged into internal super-resolution, which reports about 1.0 dB PSNR gain at ×2 on DIV2KRK at 60–100 seconds per image.

The strongest selection competitor is a learned gain regressor. It is trained on the same calibration kernels as our predictor, but on pretrained deep image embeddings, both full-dimensional and PCA-reduced, and it is paired with the same adaptive threshold policy. This is the approach a practitioner would try first. It isolates whether the cross-scale features matter.

The strongest allocation competitor pairs our own cross-scale predictor with a classical fixed-threshold secretary rule, which observes a fraction of the stream and then accepts anything above the best seen. It also pairs the predictor with a fluid dual-price rule in the Balseiro style. These isolate whether the unit-specific adaptive thresholds matter.

Two ablations remove recalibration and remove the fallback. All policies see the same image streams, orderings, calibration sets, and budget $k$. Every learned component gets the same hyperparameter search budget, and the expensive runs are identical across policies, so gains are computed from a single cached table of $g_t$.

The file contains no reported result for budgeted or online selection of images for internal super-resolution, so there is no published number to beat on the selection task itself. The relevant reported numbers bound the stakes instead. The 2.37 dB gap on Blind144 between KernelFusion's 27.19 dB and the best external network's 24.82 dB is the per-image gain that correct triage captures. Beating the baselines means reaching a competitive ratio of at least 0.8 of oracle gain at $k=5$ under random order, and staying above the embedding regressor by a statistically clear margin on held-out kernel families, including adversarial order. For reference, r-Dynamic's reported empirical ratio under adversarial sorted order is about 4.1 in the setting of its own paper, which shows how far fixed and deterministic rules fall under bad orderings.

Why not just…?

Why not just run a shortened version of the expensive method on every image? This is the most serious threat, because it would turn the chunky problem into a smooth one and make selection unnecessary. Test-time training needs some minimum number of steps before the internal prior is useful, and a diffusion model's quality usually does not scale linearly with fewer steps. That is a hypothesis, not a result in the file. Our first experiment therefore measures KernelFusion's gain as a function of compute on Blind144 and DIV2KRK. It then compares an equal-compute schedule that spreads the budget across all $N$ images against spending it on $k$ images. If the spread schedule matches selection, we will report that and reframe the work around choosing a per-image compute level, a knapsack with variable item sizes, rather than admit or reject.

Why not just run the cheaper internal method, KernelGAN, on everything? At 60–100 seconds per image this may be affordable for moderate streams. Its reported gain is about 1.0 dB on Gaussian-family DIV2KRK kernels, whereas KernelFusion's advantage is concentrated on the non-Gaussian Blind144 kernels. We include KernelGAN on all images as an equal-wall-clock baseline, and we also test a hierarchical variant that triages between three tiers. If KernelGAN everywhere matches our policy's total gain at equal compute, the problem is not worth solving at this budget.

Why not just train a supervised gain predictor on deep embeddings? The variance findings of Gula and Bertoldo suggest that the dominant embedding directions carry scene content. They also show that KernelFusion's external baselines break down on unfamiliar kernels, so a predictor trained on external features may inherit the same blindness. The held-out-kernel-family split tests this directly. If the embedding regressor matches the cross-scale features there, the self-similarity contribution is not supported, and we would say so.

Why not just process the stream offline? When the whole batch is available, sorting by predicted gain is the right thing to do, and the offline sort of predictions appears among our results. The online setting applies to pipelines that must hand off each image before the next arrives. We report the gap between online and offline-sorted-prediction policies so that readers can see what the irrevocability constraint costs.

Proposed Experiments

Streams are built from DIV2KRK, Blind144, and DIV2KFK degradations, together with Urban100 and B100 content, at ×2 and ×4. A mixing parameter sets how many images carry non-Gaussian kernels, so that the prevalence of valuable images ranges from rare, around 5%, to common, around 40%. We use $N$ between 100 and 300 and $k$ in $\{2,3,5,10\}$. We cache $g_t$ for every image once, which costs about 20 GPU-minutes per image for KernelFusion. All policies are then evaluated offline over 200 random orderings, plus adversarial orderings with high-gain images first, last, or clustered.

The first decisive check is the compute curve described above. The second is predictive: the rank correlation of $\hat{g}_t$ with $g_t$ on held-out kernel families, for cross-scale features versus embeddings versus a greedily selected subset of embedding components. The third is the allocation question: the competitive ratio against $k$ and against ordering, for the unit-specific adaptive policy versus fixed-threshold and fluid rules at identical predictor quality. We also report the ratio against the exact dynamic-programming optimum for $k \le 10$.

A secondary experiment tests redundancy across images. In streams where several images share a camera kernel, a kernel recovered by one expensive run can be reused on its neighbors. The value of a unit then depends on what has already been selected. We test whether a DPP-style repulsion over predicted kernel descriptors, following Priors for Diversity in Generative Latent Variable Models, keeps the policy from spending several units on the same degradation. The descriptor set here is small, so the cubic cost of the determinant is not a concern.

The proposal fails cleanly if the evenly spread schedule matches selection, or if embeddings predict gain as well as cross-scale statistics on unseen kernels. It succeeds if cross-scale features plus adaptive unit-specific thresholds capture most of the oracle gain at $k \le 5$ under adversarial order, where simpler rules do not.