Hunting Overconfident Empty Space with Replica Exchange

Image classifiers are often most confident exactly where they have seen no data. The final softmax layer carves feature space into regions that extend without limit, so an input landing in a gap between known classes can still receive a 99% prediction. A productive fix is to generate synthetic "outlier" points in those gaps and train the classifier to be unsure about them. Current generators find these gaps only locally. They add Gaussian noise around the edges of known classes (VOS, NPOS), blend pairs of class features (PROSER), or push boundary points with gradient ascent (BOOD). Each of these finds the gaps next to where it starts. None of them searches for the places where the model is actually overconfident.

We propose to treat outlier synthesis as a sampling problem with a clear target. The target is a probability distribution over feature space that puts high weight on points that are far from any training feature but still get a confident prediction. That distribution has many separate peaks, one per overconfident gap, with high-density class regions between them. It also changes during training, because the classifier stops being confident wherever we have already placed outliers. This is the setting that parallel tempering was built for. Parallel tempering, also called replica exchange, runs several copies of a sampler at different "temperatures" and lets them trade positions. Hot copies roam widely, cold copies settle into peaks, and the trades carry newly found peaks down to the cold copies. We use the cold copies as a continually refreshed supply of synthetic outliers.

Core Claim

The claim has three parts. First, the useful outliers are the points in empty, overconfident regions. Second, a replica-exchange sampler kept running across training steps finds and tracks these regions better than local noise, pair blending or single-chain gradient methods, for the same number of classifier evaluations. Third, the advantage comes from the swaps between temperatures, not merely from using several noise scales.

Concretely, let $z$ be a feature vector normalised to the unit sphere, as NPOS does for CLIP features. Let $h$ be the classifier head and $d_k(z)$ the distance from $z$ to its $k$-th nearest training feature. We define an energy

$$U(z) = -\log \max_c \mathrm{softmax}(h(z))_c \;+\; \lambda\,\mathrm{softplus}\big(r - d_k(z)\big),$$

where $r$ is a distance threshold and $\lambda$ sets how strongly points near training data are penalised. Low energy therefore means "confident, yet at least distance $r$ from any real feature." Each replica $m$ samples $\pi_m(z) \propto \exp(-\beta_m U(z))$ on the sphere, where the inverse temperatures satisfy $\beta_1 > \dots > \beta_N$. Adjacent replicas swap positions with the standard Metropolis probability $\min(1, \exp((\beta_i-\beta_j)(U(z_i)-U(z_j))))$.

The sphere keeps the search space bounded. Without it, the sampler would drift toward infinite feature norm, where confidence grows without limit. The temperature also gives a principled answer to the "Goldilocks" problem that DREAM-OOD describes: outliers placed too far out teach nothing, and outliers placed too close contaminate the known classes. Hot rungs sample broadly, cold rungs concentrate on the most confident gaps, and the $r$ term keeps every rung off the data. The manual sampling radii and perturbation steps in NPOS and BOOD are replaced by a ladder whose spacing we set by measuring swap acceptance rates.

Research Program

The method has three parts. The first is the energy above, computed on a backbone's penultimate features, with the same $k$-nearest-neighbour feature queue that NPOS maintains. The second is a set of persistent replica chains. Each chain takes a few Langevin steps per classifier update and then attempts swaps. The chains are not restarted, so the burn-in cost that CREPE identifies as the main drawback of replica exchange is spread over the whole training run. The third is a regulariser that uses the cold-rung samples. We will test both VOS's energy-based uncertainty loss and PROSER's extra "unknown" output class, so that the sampler is judged separately from the loss.

The temperature ladder is adapted online so that acceptance between neighbouring rungs stays roughly constant. We borrow this idea from work that optimises the ladder or path of parallel tempering (Parallel tempering on optimized paths). The approach is constrained by a known fact: swaps only work when the energy distributions of adjacent rungs overlap (Bonomi et al.). In 512- to 768-dimensional features this could demand many rungs. We will therefore record acceptance against the number of rungs and treat collapsing acceptance as a reportable failure, not something to tune away.

The main analysis measures coverage. We fit nothing to real OOD test features. After training, we ask what fraction of them fall within distance $\epsilon$ of some synthetic outlier, and how many separate overconfident regions the synthetic outliers occupy, measured by clustering the samples. If coverage does not explain the detection gains, the mechanism story is wrong.

A pixel-space extension is secondary. It would feed cold-rung samples through DREAM-OOD's feature-to-text-embedding alignment into its diffusion decoder, so that the samples can be inspected as images. It will only be pursued if the feature-space version wins.

Baselines

The naive reference point is a classifier trained with cross-entropy and scored by maximum softmax probability. On ImageNet-100 with a CLIP-B/16 backbone, NPOS reports an FPR95 of 41.87% for this baseline; FPR95 is the false-positive rate on OOD inputs at 95% recall of in-distribution inputs. This shows how much room outlier synthesis has.

The strongest feature-space competitor is NPOS. It finds in-distribution features with large $k$-nearest-neighbour distance, sprays Gaussian noise around them, and rejects candidates that land near training points. It is the closest in spirit, the most expressive existing feature-space sampler, and it reports an FPR95 of 5.76% on ImageNet-100 with CLIP-B/16.

VOS samples from the low-likelihood tails of Gaussians fitted to each class. It is the parametric reference; the file's comparisons put it well behind NPOS on ImageNet-100.

PROSER blends features from different classes and labels the blend as an extra "unknown" class. It is the reference for synthetic-class construction, with a reported CIFAR-10 open-set AUROC of 89.1% and a Tiny-ImageNet AUROC of 69.3%.

For all of these we reuse their released settings and give each the same backbone, training epochs, feature queue, and hyperparameter search budget. We also match the number of classifier-head evaluations spent per accepted outlier. Beating NPOS means a lower FPR95 in the same CLIP-B/16 ImageNet-100 setting, averaged over at least three seeds, with in-distribution accuracy unchanged.

Numbers vary across papers. DREAM-OOD reports NPOS at 44.00% FPR95 on ImageNet-100 in its own setup, versus 5.76% in the NPOS paper. We will therefore rerun every baseline ourselves instead of quoting mixed setups.

Pixel-space methods are reported for context, not as like-for-like competitors, since they use a Stable Diffusion generator. BOOD reports an FPR95 of 10.67% and an AUROC of 97.42% on CIFAR-100. FodFoM reports an FPR95 of 8.43% on CIFAR-10.

Three ablations isolate the key ingredient. The first runs the same energy with a single cold Langevin chain. The second runs $N$ chains at the same temperatures with swaps disabled. The third restarts the chains every epoch instead of keeping them.

Why not just…?

Why not just widen NPOS's spray or tune its rejection threshold? Wider isotropic noise around boundary points still explores only near where it starts. It is also not aimed at confidence, so many samples land in regions the classifier is already unsure about. The coverage analysis tests this directly. If a tuned NPOS, given the same evaluation budget, matches our coverage of held-out OOD features and our FPR95, the proposal loses. We will report that honestly.

Why not just run gradient ascent or single-chain Langevin on the same energy? This is the most serious threat. It inherits the confidence-seeking target, and a reviewer could argue the target does all the work. BOOD's gradient-ascent pushes can get trapped in local adversarial artifacts, which suggests single chains stall in the first gap they find. The single-chain and no-swap ablations settle the question. The mechanism is supported only if swaps add coverage and detection gains beyond these ablations, and especially late in training, when earlier gaps have been closed and chains must relocate.

Why not just use several noise scales, or deep ensembles, or temperature scaling? Several independent noise scales are exactly the no-swap ablation. Deep ensembles tend to agree when they are confidently wrong, because the members extrapolate in the same direction, so disagreement vanishes on OOD inputs (Kotelevskii et al.). Temperature scaling calibrates in-distribution data but breaks down under distribution shift (Roschewitz et al.). We include a five-member ensemble and temperature scaling as cheap reference rows. We do not expect either to compete on semantic OOD detection.

Why not just use real auxiliary outliers? DREAM-OOD reports that boundary-targeted synthetic outliers match or beat training on the 300K Random Images set. Real auxiliary data is also unavailable in the specialised domains that motivate this work. We therefore include real-outlier exposure only as an upper-reference row on CIFAR.

Proposed Experiments and Decisive Checks

The benchmarks are CIFAR-10 and CIFAR-100 with a WideResNet, and ImageNet-100 with CLIP-B/16 and with a ResNet. OOD test sets follow the cited papers: Textures, Places365, iNaturalist, SUN and SVHN, plus NINCO and OpenImage-O as cleaner OOD sets. We also report open-set AUROC on the CIFAR-10 and Tiny-ImageNet splits used by PROSER. Metrics are FPR95, AUROC, in-distribution accuracy, and wall-clock time per training epoch. Mechanism diagnostics are swap acceptance per rung, coverage of held-out OOD features, the number of distinct overconfident regions found, and how fast those regions are rediscovered after the classifier closes them.

Three checks decide the outcome. First, beat our rerun of NPOS on ImageNet-100 with CLIP-B/16 and on CIFAR-100 at matched evaluation budget. Second, beat the no-swap and single-chain ablations by more than seed variance. Third, show that the gains track coverage of held-out OOD features.

A clean negative result would also be informative. If acceptance collapses in the feature dimensions that matter, feature-space replica exchange is ruled out for this problem. If the no-swap ablation ties, the contribution shrinks to the confidence-seeking energy alone. We would then report that energy as the finding.