Many questions about generated audio reduce to a nearest-neighbor query. Did the model copy a training clip? Which real recordings is this sample closest to? Does a set of generated clips cover the real distribution? Each query is only as good as its distance function. Cheap distances, such as spectrogram differences or a single clip-level embedding, are fast to index but disagree with listeners. Perceptually faithful comparisons, such as frame-by-frame alignment of self-supervised audio features or learned similarity models, are too slow to run against millions of clips. A recent result on "bi-metric" search offers a way out. You build a proximity graph using the cheap distance, walk it with the cheap distance to reach the right region, then switch to the expensive distance for the final steps (A Bi-metric Framework for Efficient Nearest Neighbor Search). The guarantee holds only if the two distances never disagree by more than a bounded factor, and the method was tested only on text retrieval.
This note argues that in audio, the well-documented mismatch between objective and perceptual distances is exactly a violation of that bound, and that the violation is concentrated rather than uniform. A time shift of a few milliseconds or a gain change makes a cheap distance large while listeners hear no difference. A drum loop with the right spectrum but chaotic timing makes a cheap distance small while listeners hear a different thing. We propose to measure where the cheap and perceptual distances disagree, and to repair the search graph with a small budget of expensive comparisons placed where the disagreement is worst. The test is whether audio nearest-neighbor queries under a perceptual distance can be answered at close to the cost of the cheap one. The two applications are memorization audits and neighborhood-based evaluation of generated audio.
Core Claim
Define the cheap distance $d$ (for example, cosine distance between clip-level CLAP embeddings) and the expensive perceptual distance $D$ (for example, a shift-tolerant alignment distance between frame-level MERT or wav2vec 2.0 features, validated against human similarity labels). For a pair of clips $x, y$, define the local distortion as the ratio $\rho(x,y) = D(x,y)/d(x,y)$. Bi-metric search assumes $\rho$ stays within a constant factor across the dataset.
Our claim has three parts. First, in audio $\rho$ is heavy-tailed in both directions. Second, its extremes are predictable from cheap signals: transformation families such as shift, gain, reverb and resampling, plus rhythm-level structure. Third, two failure modes follow. When $d$ is large but $D$ is small, perceptual neighbors are never joined by graph edges, so search cannot reach them. When $d$ is small but $D$ is large, the graph is crowded with perceptually useless edges, which waste expensive evaluations.
A graph built under $d$ and then given a budget of "bridge" edges chosen by estimated distortion should recover nearly exact $D$-neighbors. It should also use far fewer $D$ evaluations than either reranking or plain bi-metric traversal. What is new is treating the perceptual-objective gap as a measurable property of the index, and spending expensive comparisons according to that property. Prior work only reports the gap as a correlation failure.
Research Program
The first stage is diagnostic. On a corpus of real audio drawn from AudioCaps, FMA and MTG-Jamendo, plus generated audio from DCASE 2023 Task 7 systems, we sample pairs and compute both distances. We map the distribution of $\rho$ by transformation type and by content class.
The expensive distance $D$ needs grounding, because "perceptual" must mean something. We will use two candidates: a frame-level alignment distance in the spirit of the manifold geometry of MAPSS, which projects self-supervised features so that Euclidean distance tracks perceptual dissimilarity, and the learned similarity model of CDPAM, which is trained on human just-noticeable-difference judgments. Each candidate is checked against held-out human pairwise similarity labels before use. The motivation for expecting heavy tails comes from three findings. Time-alignment metrics catastrophically penalize perceptually transparent shifts (ViSQOL v3). Spectrum-matched but unmetered drum loops fool distribution metrics (FreeSound Loop benchmark). Spectral distance saturates at 3 codec layers while listeners prefer 9 (Geometric Iterative Retrieval for Neural Audio Codec Resynthesis).
The second stage builds the index. We construct a navigable proximity graph (DiskANN-style, following the bi-metric paper) under $d$. We then train a cheap regressor that predicts each node's distortion, meaning how often its true $D$-neighbors lie outside its $d$-neighborhood. Its inputs are features computable from $d$ alone, such as embedding norms, onset-density statistics and the spread of the node's neighbors. Given a construction budget of $B$ expensive evaluations, we run small $D$-neighborhood probes from the highest-distortion nodes and add the resulting bridge edges. Queries then follow the bi-metric recipe: route with $d$, finish with $D$.
We will also make $d$ cheaply invariant to the transformations the diagnostic flags as dominant, for example by taking the minimum over a few frame offsets and normalizing gain. This tests how much of the gap a better proxy closes by itself.
The third stage applies the index. The first application is a memorization audit. Generation or Replication found that audio latent diffusion models replicate training clips, and identified 88 duplicate clusters inside AudioCaps. That pipeline used brute-force comparisons and manual inspection. The second application is perceptual-neighborhood evaluation, where Clipped Density and Coverage are computed with $D$-neighborhoods instead of a single static embedding. That paper reports calibrated neighborhood metrics on FMA correlating with human error rates at $r > 0.8$, using exhaustive k-nearest-neighbor computation.
Baselines
The naive reference point is exhaustive search under $D$ on a 50,000-clip subset where this is affordable. It defines ground-truth neighbors and the maximum cost. Next to it sits exhaustive or flat-index search under $d$ alone, which costs nothing extra but gives the recall a cheap proxy achieves by itself.
The first real competitor is retrieve-then-rerank. A flat or graph index under $d$ returns the top-$K$ candidates, and $D$ reranks them, with $K$ swept from 100 to 2,000. This is what practitioners actually do, so it must be beaten at every $K$, not just one.
The strongest existing method is plain bi-metric traversal as described in A Bi-metric Framework for Efficient Nearest Neighbor Search. On BEIR HotpotQA it matched reranking recall with about 200 instead of about 800 expensive calls, a 4x reduction, and 260 instead of 1,040 seconds per query. There is no reported result found on Lacuna for bi-metric search on audio, so we will rerun it ourselves on the same graph, proxy, expensive distance and corpus.
Fairness is enforced by matching every method on the same total budget of $D$ evaluations, construction plus query, and on wall-clock time on the same hardware. Graph hyperparameters get one shared tuning budget. Beating the strongest baseline means a statistically clear gain in recall@10 under $D$ at equal $D$-evaluation budget, on the high-distortion query slice, without losing recall elsewhere.
Two ablations isolate the key ingredient. The first adds the same number of bridge edges at random nodes instead of predicted high-distortion nodes. The second applies the invariance-augmented proxy with no bridge edges. If random bridges match targeted bridges, the distortion predictor is not doing the work.
Why not just…?
Why not just rerank a large top-K from a cheap index? Reranking has a hard recall ceiling. A $D$-neighbor that $d$ ranks outside the top-$K$ is never seen. This is precisely the shifted-copy case, where $d$ is large and $D$ is small, and it is exactly the case a memorization audit cares about. The bi-metric paper documents both the ceiling and the 4x cost penalty on text. Our $K$ sweep will show whether the ceiling persists on the high-distortion slice even at $K=2{,}000$.
Why not just use a better single embedding with an off-the-shelf fast index? This is the most serious threat. If an invariance-augmented or distilled proxy shrinks the distortion enough, the bridge edges become redundant. The ablation with the invariant proxy and no bridges tests this directly. We will also train a small student embedding to imitate $D$ and index it alone. If either matches our method at equal budget, the honest conclusion is that the proxy, not the graph repair, is the contribution, and we will report it that way. We expect a residual gap because some failures are structural, such as rhythm and grammar, which a clip-level vector compresses away (FreeSound Loop benchmark). That expectation is the hypothesis being tested, not an assumption.
Why not just skip neighborhoods and use a global distance like Kernel Audio Distance? For evaluation of whole systems, KAD is strong. It reports 0.93 Spearman correlation with human rankings on DCASE 2023 Task 7, against 0.238 for FAD in the challenge report. We do not claim to beat it at system ranking. A global score cannot say which generated clip copies which training clip, or which real modes are uncovered, so audits and fidelity/coverage diagnostics still need per-sample neighbors. We include KAD as a reference column so readers can see whether perceptual neighborhood metrics add anything at the system level.
Proposed Experiments
The first decisive check is the distortion diagnostic. If $\rho$ under the validated $D$ turns out to be tightly bounded on real audio, the premise fails and plain bi-metric search suffices. We will report this outcome either way.
The second is the search benchmark. We plot recall@10 under $D$ against expensive evaluations per query and against wall-clock time on a corpus of about one million AudioSet and AudioCaps clips, with exact neighbors computed on a stratified subset. Results are reported separately for queries the diagnostic labels high- and low-distortion. Queries include real training clips and outputs from a text-to-audio diffusion model trained on AudioCaps.
The third is the memorization audit. The known AudioCaps duplicate clusters serve as labeled positives. The task is to recover them, and then to estimate the replication rate of the diffusion model at full scale. Generation or Replication reports 5 to 10 instances per 10,000 generations at full AudioCaps scale. Success means recovering that rate and the known clusters at a small fraction of brute-force $D$ cost, with any newly found replications confirmed by blinded listeners.
The fourth is evaluation. We recompute Clipped Density and Coverage with $D$-neighborhoods on FMA and on DCASE 2023 Task 7 submissions, compare their per-system correlation with the challenge's human ratings against static-embedding neighborhoods and against KAD's 0.93, and confirm that the accelerated index gives the same scores as exhaustive $D$.
References
- A Bi-metric Framework for Efficient Nearest Neighbor Search
- MAPSS: Manifold-based Assessment of Perceptual Source Separation
- CDPAM: Contrastive Learning for Perceptual Audio Similarity
- ViSQOL v3: An Open Source Production Ready Objective Speech and Audio Metric
- A Benchmarking Initiative for Audio-domain Music Generation using the FreeSound Loop Dataset
- Geometric Iterative Retrieval for Neural Audio Codec Resynthesis
- Generation or Replication: Auscultating Audio Latent Diffusion Models
- Enhanced Generative Model Evaluation with Clipped Density and Coverage
- KAD: No More FAD! An Effective and Efficient Evaluation Metric for Audio Generation
- Foley Sound Synthesis at the DCASE 2023 Challenge