Steiner Anchors for Sparse Listening Tests in a Decomposed Perceptual Space

Ranking speech enhancers by human listening is expensive, and the hardest part is the part that matters most. Modern noise suppressors mostly differ in how much they distort the voice, and neither absolute ratings nor learned quality predictors resolve those differences well. Paired comparisons ("which of these two clips has a more natural voice?") are more sensitive, but comparing all pairs grows quadratically with the number of systems. This note proposes treating the choice of which pairs to compare as a geometric network design problem. Each system's output sits at a point in a low-dimensional perceptual space, for example voice quality versus background-noise quality. The comparison design is a sparse graph on those points. Every pair of systems should be linked by a short chain of comparisons between perceptually nearby clips. We also add synthetic "anchor" clips with controlled degradations at chosen locations, so that the chains stay short even where real systems are sparse or clustered.

The bet rests on one empirical hypothesis. When a listener judges one quality dimension, the judgment is biased by how much the two clips differ on the other dimensions. If that holds, comparisons should only join clips that are close in every dimension. That requirement is exactly the setting where geometric spanners (sparse graphs whose paths approximate direct distances) apply, and where extra junction points buy large savings. If the hypothesis fails, the geometry is unnecessary, and the proposal says so up front.

Core Claim

Perceptual decomposition research found that telephone-speech quality is well described by a few roughly independent dimensions: noisiness, coloration, and discontinuity. Wältermann et al. report that a linear combination of these explains about 90% of the variance in overall quality. Learned predictors now estimate these dimensions from a single clip without a clean reference. NISQA does this with a CNN plus self-attention across 81 datasets, and DNSMOS P.835 predicts the ITU-T P.835 speech (SIG), background (BAK), and overall (OVRL) scores. That low dimensionality is what makes Euclidean spanner theory usable here. Spanner size grows exponentially with dimension, as Light Spanners for High Dimensional Norms via Stochastic Decompositions emphasizes, so a 2–3 dimensional perceptual space is the regime where sparse, low-stretch designs are cheap.

Two results about added junction points, called Steiner points, suggest large savings. Truly Optimal Euclidean Spanners shows that in the plane they cut the edge count needed for stretch $1+\epsilon$ from $\Theta(n/\epsilon)$ to roughly $n\epsilon^{-1/2}$. Here stretch is the ratio of path length to direct distance, and $n$ is the number of systems. Euclidean Steiner Spanners: Light and Sparse cuts total edge length from $O(\epsilon^{-2})$ to $O(\epsilon^{-1})$ times the minimum spanning tree.

In our setting a Steiner point is a synthetic anchor stimulus: a clean clip with a chosen SNR, band-limit, or packet-loss rate. Because each degradation mostly moves one perceptual dimension, we can place anchors roughly where we want them. The claim is that anchor-augmented, geometry-aware comparison designs recover system rankings on SIG and BAK more accurately per listener-hour than standard P.835 absolute ratings or random sparse comparisons. The gains should concentrate among top systems that differ mainly in voice distortion.

Research Program

The first piece is a measurement study of cross-dimensional bias. The design only pays off if it holds, so it comes first. We build stimulus pairs whose SIG difference is held fixed while their BAK difference varies, and the reverse. We then measure how the listener's SIG judgment shifts as a function of the BAK gap. The prior evidence is suggestive but indirect. Berger et al. and Möller et al. describe a dominant impairment bottlenecking perceived quality. Quality Degradation Diagnosis for Voice Networks found that separate per-dimension networks beat a shared multi-task model, which hints that the dimensions interfere in modeling, though not necessarily in perception. What we want out of this study is a bias curve, which directly sets how local a comparison must be.

The second piece is the design algorithm. We place real systems at pilot coordinates from DNSMOS P.835, then build a comparison graph with three properties. It must have bounded stretch, so any two systems are linked by a chain whose summed perceptual steps is close to their direct distance. It must have few edges. And it must stay planar in the (SIG, BAK) plane.

Planarity is not decoration. In a planar graph the bounded faces form a cycle basis, a set of small loops from which every other loop can be built. Each face is a local loop of comparisons whose differences should sum to zero if perception is additive. A face that fails this check localizes where in perceptual space the linear model breaks, which gives the nonlinear-interaction question from the decomposition literature a spatial map. A crossing graph offers no such local diagnostic.

Planar low-stretch Steiner networks are open in theory; Self-Approaching Graphs poses this explicitly for self-approaching networks. We therefore do not claim a theorem. We build them heuristically: a Delaunay triangulation of systems plus anchors, followed by greedy insertion of anchors on the longest remaining edges. We also track the path property from that paper. A self-approaching path is one along which the distance to the destination never increases, which bounds detour at 5.33. For listening chains it means the summed differences never partially cancel.

The third piece is the question the theory leaves open: how many Steiner points to add. Both Steiner-spanner papers treat the number of added points as free. Here every anchor costs listening time, so we measure empirically how ranking accuracy trades off against anchor count and edge count at a fixed budget.

The fourth piece is estimation. From the sparse comparisons we fit per-dimension scores with a Thurstone-style model, a standard statistical model that turns paired preferences into scale values. The fit uses graded two-scale judgments, so one trial rates both SIG and BAK. Face-cycle residuals are reported as the interaction diagnostic.

Baselines

The naive reference point is the pilot automated score alone: rank systems by DNSMOS P.835 with no human data. DNSMOS P.835 reports model-level Pearson correlations with human ratings of 0.94 for SIG, 0.98 for BAK, and 0.98 for OVRL on DNS Challenge data. Clip-level correlations are 0.71–0.83. The ICASSP 2022 Deep Noise Suppression Challenge reports 0.92–0.96 between DNSMOS and human ratings. We use the identical pilot scores that seed our design, so this baseline shares our only automated input. Beating it means a higher Kendall rank correlation with ground truth on SIG among the top systems, where an overall 0.94 can still hide many swaps.

The strongest existing method is standard ITU-T P.835 absolute rating by crowd listeners, the protocol behind the DNS Challenge ground truth. It is strong because its cost is linear in the number of systems and it is the accepted standard. We found no reported result on Lacuna for P.835 test-retest reliability or ranking accuracy at reduced listener budgets, so we measure it ourselves. It runs on the same clips, the same crowd platform, the same listener-screening rules, and an equal total count of listener-seconds. Beating it means matching its ranking accuracy with at most half the listener time, or exceeding it at equal time.

The strongest comparison-based competitor is a random sparse comparison graph with the same edge count and the same estimator. A random regular graph is well connected, so connectivity alone gives it good statistics.

Three ablations each isolate one ingredient. The first is our geometric design without anchors, which isolates the Steiner points. The second uses anchors but allows crossing edges, which isolates planarity and loses the face diagnostic. The third is a per-dimension sorted chain, which isolates the cross-dimensional-locality claim.

Why not just…?

Why not just use P.835 absolute ratings, which cost only linear time? This is the main threat. If absolute ratings already rank the top systems stably at modest budgets, sparse comparisons add complexity for nothing. The ICASSP 2022 finding that no submission improved SIG over the noisy input suggests the relevant differences are small. Small differences are exactly where comparisons usually beat absolute scales, but that is an expectation, not evidence. The equal-listener-time comparison in the experiments settles it, and we will report it even if P.835 wins.

Why not just compare along one dimension at a time, sorted by pilot score? Such a chain needs only about $2(n-1)$ comparisons, fewer than any two-dimensional spanner. It fails only if cross-dimensional bias is real. Adjacent clips in a SIG-sorted chain can differ greatly in BAK, and a dominant noise difference would then contaminate the SIG judgment. The bias study in the research program is the direct test. If it finds a flat bias curve, the per-dimension chain is the right design and we abandon the geometric construction.

Why not just use random or actively chosen comparison pairs? Random sparse graphs are statistically efficient, and active sampling can target uncertain pairs. Neither controls how far apart the two clips in a pair are perceptually. Neither provides small face loops for detecting where the additive model breaks. Under strong cross-dimensional bias, random pairs frequently join perceptually distant clips. The random-graph baseline at equal edge count measures whether this costs accuracy.

Why not just trust DNSMOS or NISQA? Their clip-level SIG correlation of 0.71–0.83 is too low to separate close systems. Aligning Generative Speech Enhancement with Perceptual Feedback, which optimizes against the automated judge UTMOS, shows how enhancers can drift on properties a scalar judge does not see, in its case speaker identity. Automated scores seed our design, but human judgments decide the ranking.

Proposed Experiments

The primary testbed is DNS Challenge processed audio. We use the ICASSP 2022 challenge's clips from its suppression models where available, and otherwise public enhancers run on the 850-clip DNSMOS P.835 test categories. We take a 20-system subset and collect dense all-pairs comparisons, 190 pairs with many repetitions, as ground truth. We then subsample every design at matched listener-seconds.

Anchors are synthesized on the same clean speech using additive noise, band-limiting, and packet loss, mirroring the degradations in NISQA's simulated training sets. The NISQA test sets (P501, FOR, LIVETALK), which carry separate noisiness, coloration, and discontinuity labels, provide a three-dimensional replication. NISQA's own reported error range, RMSE 0.16–0.56 across dimensions, gives the precision of the pilot coordinates in that setting. The metrics are Kendall rank correlation with ground truth per dimension, top-5 ranking accuracy on SIG, listener-seconds to reach a target correlation, and face-cycle residual magnitude against pilot location.

The decisive checks come in order. First, the bias curve must show that a BAK gap measurably shifts SIG judgments; otherwise we stop and adopt per-dimension chains. Second, the full design must beat equal-budget P.835 and the equal-edge random graph on top-system SIG ranking. Third, removing anchors must hurt, which shows the Steiner points earn their listening cost. Fourth, large face residuals should cluster where noise and distortion are jointly severe, the region where the decomposition literature expects additivity to fail, rather than scattering uniformly.