Many image reconstruction networks are built by "unrolling" a classical iterative solver. This approach, called deep unfolding, turns each iteration of an optimizer such as proximal gradient descent into one layer of a trainable network. The strongest of these networks also include a non-local step. At every iteration, each image patch searches the image for other patches that look like it and borrows information from them, which exploits the fact that natural images repeat themselves. That search is expensive, and current networks redo it from scratch at every unrolled stage, at every pixel, for every image. Late in the unrolling, however, the image estimate barely changes, so the matches found at stage $t$ are almost always the matches that stage $t+1$ will find again.
We propose to skip the search wherever a cheap mathematical certificate proves it would return the same neighbors. The certificate follows from the triangle inequality. If a patch and its candidates have each moved less than half the gap between the $k$-th and $(k+1)$-th best match distance, the set of top-$k$ neighbors cannot have changed. Computing this check costs one box filter and one max-pool per stage, and with it the network's output is identical to full search. A version with a tunable slack trades a measured amount of accuracy for further savings. The result is that compute is spent unevenly, and the unevenness is set by a provable bound: early stages and changing textured regions get re-searched, while converged or flat regions reuse their old matches. Unlike the learned difficulty predictors used in adaptive-compute work, this rule cannot be fooled by out-of-distribution inputs into stopping too early.
Core Claim
In non-local unfolded networks, most of the search compute in later stages is provably redundant, and a training-free stability certificate can remove it without changing the output. Once the non-local step is no longer the cost bottleneck, the saved budget can buy extra unrolled stages, which should improve reconstruction at equal wall-clock time. The central quantity is the following. Let $d^{(s)}_{k}(i)$ and $d^{(s)}_{k+1}(i)$ be the $k$-th and $(k+1)$-th smallest Euclidean feature-patch distances for location $i$, recorded at the last stage $s$ where $i$ was searched. Let $\Delta_i$ be the accumulated change of the patch at $i$ since stage $s$, and let $\Delta_{\max}(i)$ be the largest such change among the candidates in $i$'s search window. Location $i$ may reuse its neighbor list at stage $t$ when
$$d^{(s)}_{k+1}(i) - d^{(s)}_{k}(i) + \tau > 2\Delta_i + 2\Delta_{\max}(i),$$
where $\tau \ge 0$ is a slack. With $\tau = 0$, reuse is exact: the triangle inequality bounds how far any distance can move, so no outsider can overtake a current neighbor. The aggregation weights for the $k$ reused neighbors are still recomputed from current features, so only the search is skipped and the result remains differentiable in the usual way.
Relation to Prior Work
Three unfolded networks already pair unrolling with non-local modeling, and all three run it uniformly. MoG-DUN unrolls half-quadratic splitting into four stages with a non-local autoregressive module for super-resolution. DC-NLAR does the same for indoor depth and searches the whole image at every stage. DUN-CSNet makes gradient step sizes spatially adaptive, but applies its deformable non-local module everywhere and at every phase. These papers motivate the proposal by showing that non-local priors help inside unrolled networks. They leave untouched the question of whether the search must be repeated, and that question is ours.
Two papers supply the idea of non-uniform compute in unfolding, and they also show its usual form. DPC-DUN learns, through a differentiable relaxation of discrete choices, to skip whole gradient or prior modules per image, and reports about 18.2% fewer FLOPs on Set11 at a 30% sampling ratio. It has no non-local step, and it makes its decisions per image and with a learned gate. PADUT adapts per-pixel data-step parameters and uses spectral-only non-local attention over a fixed number of stages. Our allocation is per location and per stage, and it comes from a certificate rather than a trained gate.
Our method borrows its main tool from the classical work on search acceleration. The Cauchy–Schwarz kick-out search abandons a candidate once a partial distance bound exceeds a threshold, giving roughly a 5x speedup within a single search. We apply the same bounding logic across iterations instead of within one search. Monte Carlo non-local means and Self-Convolution make each search cheaper, the latter by recasting block matching as FFT multiplication for a 2x to 9x speedup. Both still search everywhere, every time, which makes them complementary to reuse rather than competitors with it.
The adaptive-compute literature for language models constrains our design. Probes that read difficulty from hidden states (The LLM Already Knows), quota controllers (DRQA) and consensus-based halting (early-stopping self-consistency) all show that learned stopping rules save compute. Surveys of this area (A Survey of Frontiers in LLM Reasoning) also flag miscalibration under distribution shift as an open failure. Our exact certificate is a direct response to that failure. Finally, the analysis of unrolled dictionary learning warns that simply unrolling deeper can become numerically unstable. That result tempers our secondary claim that saved compute should be reinvested in depth, so we treat the claim as something to test rather than assume.
Research Program
The first step is a diagnostic, because the premise is plausible but unmeasured. We will train a reference non-local unfolded network for image compressed sensing. It will unroll proximal gradient descent into $K$ stages, and each stage will run explicit top-$k$ block matching on learned features inside a $W \times W$ window, followed by weighted aggregation. For every stage, we log the fraction of locations whose top-$k$ set differs from the previous stage, the distribution of match margins $d_{k+1} - d_k$, and the per-pixel feature change. If neighbor sets churn heavily through the final stages, the idea fails early and cheaply.
The second step builds the certified-reuse module. This requires a per-stage map of patch change, computed by box-filtering squared feature differences. Change is accumulated since each location's last search, and the triangle inequality makes this accumulation valid. The window maximum $\Delta_{\max}$ is computed by max-pooling, and a stored pair of distances $(d_k, d_{k+1})$ is kept per location. Wall-clock speed matters on GPUs, and DPC-DUN-style per-element branching is known to erode savings from skipped FLOPs. We therefore evaluate the certificate at the level of tiles, taking the maximum over a tile. Failing tiles are gathered into a dense batch and re-searched in one kernel call. We will report the gap between pixel-level and tile-level refresh fractions.
The third step studies the slack $\tau$. With $\tau = 0$, the output equals full search up to floating-point error, which we will verify. With $\tau > 0$, near-tied neighbors may be swapped. These ties are common in repetitive textures, where the exact certificate will be conservative. Swapping near-ties should cost little, because tied neighbors carry nearly identical aggregation weights and content. We will trace PSNR against refresh fraction as $\tau$ varies, and we will choose whether $\tau$ is applied during training or only at test time.
The fourth step tests reinvestment. At a fixed wall-clock budget equal to the reference $K$-stage network, we train a deeper network that uses certified reuse and ask whether the extra stages improve accuracy or hit the instability ceiling.
Baselines
The naive reference is the same network with full non-local search at every stage and every location. It sets the accuracy ceiling for exact reuse and the compute cost everything else is measured against. A second naive point is the same backbone with the non-local module removed, which shows how much the search is worth in the first place.
The strongest simple competitor is schedule-based reuse: search at stage 1 or at a fixed stage $s^*$, then freeze or refresh every $r$ stages. We will tune $s^*$ and $r$ on a held-out split with the same tuning budget we give to $\tau$. It wins if it matches our PSNR at an equal or lower measured refresh fraction.
The strongest learned competitor is a DPC-DUN-style gate (DPC-DUN). This is a per-tile, per-stage selector trained with the same differentiable relaxation and a compute penalty, deciding whether to re-search. It is trained on the same data with the same number of epochs.
We also include a hand-crafted texture gate, which searches only where local variance exceeds a threshold, in the spirit of restricting search to texture-rich regions. Monte Carlo candidate subsampling (Monte Carlo NLM) serves as an approximate-search baseline. Self-Convolution full search (Self-Convolution) serves both as a speed reference and as a backbone we stack reuse on top of.
To anchor against published systems, we use the following reported numbers. DUN-CSNet reports 30.87 dB PSNR on Set11 at a 10% sampling rate (DUN-CSNet). MoG-DUN reports 32.60 dB on Set5 at ×4 super-resolution (MoG-DUN). DC-NLAR reports an RMSE of 0.102 on NYU-Depth V2 (DC-NLAR). DPC-DUN reports an 18.2% FLOPs reduction on Set11 at 30%. No reported result was found on Lacuna for any of these methods on Urban100.
"Beating" a baseline means one of two things. Either we reach equal PSNR, within 0.05 dB, at lower measured GPU latency and refresh fraction, or we reach higher PSNR at equal latency. The isolating ablation compares three versions of the refresh rule on identical networks: the certificate, the certificate with $\Delta_{\max}$ replaced by $\Delta_i$ alone (an unsafe shortcut), and random refresh at the same rate. This separates the value of the bound from the value of refreshing less often.
Why not just…?
Why not just compute matches once and reuse them for all stages? This is the most serious threat, and it is included as a tuned baseline. Its weakness is that the right freezing stage depends on the image and on the sampling ratio. At low sampling ratios, early iterates are heavily aliased and their matches are poor. A schedule tuned on average images will refresh too much on easy inputs and too little on hard ones. If the diagnostic shows that churn collapses at the same stage for every image and every ratio, a fixed schedule will match us. In that case, the contribution shrinks to the diagnostic plus a safety guarantee, and we will report it as such.
Why not just make every search cheap with FFT self-convolution or random sampling? Self-Convolution lowers the cost of each search by a constant factor but still searches uniformly at every stage. Reuse removes searches altogether, so the two multiply rather than compete, and we test them stacked. Random candidate sampling introduces approximation error at every stage, and that error compounds through the unrolled stages. The comparison at matched latency will show whether it holds PSNR.
Why not just learn when to re-search, as DPC-DUN learns when to skip? A learned gate may well be faster at matched in-distribution PSNR, because it can exploit statistics our bound ignores. Its known weakness is calibration under shift. We therefore also train on BSD500 and test on Urban100 and Manga109, whose dense repetitive line art and facades differ from the training images. If the learned gate's PSNR drop under shift is no worse than ours, the guarantee buys little, and we will say so.
Proposed Experiments
For compressed sensing, we train on BSD500 / Train400 and test on Set11, BSD68 and Urban100 at sampling ratios of 1%, 10%, 25% and 50%. Urban100 is the main diagnostic for non-local redundancy, and the 1% regime is where the file notes that unfolding struggles. For super-resolution, we use a MoG-DUN-like backbone at ×4 on Set5, Set14, BSD100, Urban100 and Manga109. For transfer to a different modality, we use NYU-Depth V2 with a DC-NLAR-like backbone, where planar indoor scenes should allow heavy reuse. We report PSNR, SSIM and RMSE, the refresh fraction per stage, and measured GPU latency at 256×256 and 1024×768, alongside FLOPs.
Four checks decide the outcome. First, the diagnostic must show that top-$k$ churn falls well below full refresh by the final stages; otherwise we stop. Second, exact reuse with $\tau = 0$ must match the full-search output to numerical precision while delivering real wall-clock savings after tiling; if tiling erases the savings, the method is of theoretical interest only. Third, the certificate must beat the tuned fixed schedule on refresh fraction at matched PSNR, especially across sampling ratios. Fourth, under the BSD500 to Urban100/Manga109 shift, the certificate must lose less PSNR than the learned gate. A secondary check asks whether a deeper network with certified reuse, at matched latency, beats the reference $K$-stage network or instead shows the instability predicted by the unrolled dictionary-learning analysis.
References
- Accurate and Lightweight Image Super-Resolution with Model-Guided Deep Unfolding Network
- Indoor Depth Recovery Based on Deep Unfolding with Non-Local Prior
- Deep Unfolding Network for Image Compressed Sensing by Content-Adaptive Gradient Updating and Deformation-Invariant Non-Local Modeling
- Dynamic Path-Controllable Deep Unfolding Network for Compressive Sensing
- Pixel Adaptive Deep Unfolding Transformer for Hyperspectral Image Reconstruction
- Fast Search of a Similar Patch for Self-Similarity Based Image Super Resolution
- Monte Carlo Non-Local Means: Random Sampling for Large-Scale Image Filtering
- Exploiting Non-Local Priors via Self-Convolution for Highly-Efficient Image Restoration
- The LLM Already Knows: Estimating LLM-Perceived Question Difficulty via Hidden Representations
- DRQA: Dynamic Reasoning Quota Allocation for Controlling Overthinking in Reasoning Large Language Models
- Escape Sky-high Cost: Early-stopping Self-Consistency for Multi-step Reasoning
- A Survey of Frontiers in LLM Reasoning: Inference Scaling, Learning to Reason, and Agentic Systems
- Understanding approximate and unrolled dictionary learning for pattern recovery