How Many Metric Calls Does MBR Decoding Need? A Random-Matrix Account of Utility-Matrix Collapse

Minimum Bayes Risk (MBR) decoding picks a translation by sampling many candidates and choosing the one that agrees most, on average, with all the others. "Agreement" is measured by a learned quality metric such as COMET or BLEURT, which is a large neural network. With $N$ candidates the decoder needs every pairwise score, so $N^2$ network calls: about a million for $N=1024$. Recent work shows most of these calls are wasted. The table of pairwise scores is close to rank one, so a small random sample of entries, filled in by matrix completion, recovers the decision (Efficient Minimum Bayes Risk Decoding using Low-Rank Matrix Completion Algorithms). That completion also breaks down abruptly at extreme sampling rates (Agreement-Constrained Probabilistic Minimum Bayes Risk Decoding). Nobody can currently say, for a given sentence, where that breakdown sits. Practitioners therefore pick one global sampling budget and either overpay on easy sentences or fail on hard ones.

We propose to treat the subsampled utility matrix as a random matrix of the kind studied in matrix-model quantum gravity: a dominant "signal" direction buried in structured noise. We would then use that field's spectral tools to derive a per-sentence sampling threshold below which the MBR winner cannot be identified. The practical result is an adaptive budget rule. A tiny pilot sample of metric calls estimates the signal strength, the noise spectrum and the winner's margin. The rule then sets how many more calls that sentence needs, with no distilled helper model and no held-out tuning calls. The quantum gravity direction plays a narrow, honest role here. It supplies the resolvent and loop-equation calculus, meaning the algebraic equations that determine eigenvalue distributions of random matrices with non-Gaussian weights (A matrix model for 2D quantum gravity defined by Causal dynamical triangulations, LOOP EQUATIONS AND THE TOPOLOGICAL PHASE OF MULTI-CUT MATRIX MODELS). The neural-metric direction supplies the problem and every benchmark.

Core Claim

Write the observed utility matrix as $U = \theta\, a b^\top + Z$. Here $\theta$ is the strength of the dominant direction, $a$ and $b$ are unit vectors describing how good each candidate is as a hypothesis and as a pseudo-reference, and $Z$ is the residual. Each row's expected utility is approximately $\theta\, a_i \bar b$, where $\bar b$ is the mean of the entries of $b$. In the rank-one regime the MBR winner is therefore just the largest entry of $a$.

Suppose each entry is observed independently with probability $p$. Spiked-random-matrix theory predicts a sharp transition in that setting: the leading singular vector of the rescaled sample carries information about $a$ only when

$$\theta \sqrt{pN} > \sigma_{\text{eff}},$$

where $\sigma_{\text{eff}}$ is the effective noise scale set by the spectrum of $Z$. The form comes from the standard argument that subsampling at rate $p$ shrinks the signal by $p$ but the noise only by $\sqrt{p}$.

Getting the winner right is stricter than detecting the signal. The estimation error in $a$ must be smaller than the gap $\Delta$ between its two largest entries. This gives a per-sentence budget $p^\star(\theta, \sigma_{\text{eff}}, \Delta, N)$. Our claim is that $p^\star$ can be estimated from a pilot sample of a few hundred calls. We also claim it predicts where PMBR (the probabilistic MBR method of Trabelsi et al.) and its variants collapse, and that spending calls according to it reaches full-MBR quality at a lower average cost than any fixed budget.

The residual $Z$ in real metric matrices is unlikely to be Gaussian or independent across entries. Candidates sampled from one model share errors, and metric scores are bounded and skewed. This is where the matrix-model machinery does work that a textbook Marchenko–Pastur law, which describes the spectrum of pure independent noise, cannot. Loop equations give the eigenvalue density, and with it the threshold, for matrix ensembles weighted by a general potential $V(M)$ rather than a Gaussian one, including multi-cut spectra where the noise eigenvalues split into separate bands. We would fit a low-order potential to the empirical residual spectrum and solve for the edge of its bulk, which sets $\sigma_{\text{eff}}$.

Research Program

The first phase is empirical spectroscopy of utility matrices. We would compute full $1024 \times 1024$ matrices for BLEURT-20, COMET and chrF on WMT23 En↔De candidates from M2M100, the setting of the AC-PMBR paper. We would also use WMT22 en↔de and en↔ru for COMET-family utilities, since the file reports PaLM-8B results there. For each sentence we would measure $\theta$, the residual spectrum and $\Delta$. We would then test whether the residual follows Marchenko–Pastur, a fitted non-Gaussian potential, or neither.

The second phase is theory. We would derive $p^\star$ under the fitted noise model and build a pilot estimator. The estimator uses a random 0.1–0.5% of entries: row and column means give a rough $a$ and $\theta$, residual moments give $\sigma_{\text{eff}}$, and bootstrap resampling of the pilot gives a confidence interval on $\Delta$.

The third phase is the decoder. We would allocate remaining calls per sentence in proportion to estimated difficulty under a fixed corpus-level budget. We would then recover the winner, either by ALS completion as in PMBR or directly from the leading singular vector of the rescaled sample. Comparing these two recovery steps tests whether full completion is needed at all.

We deliberately set aside two ideas suggested by the gravity literature. Causal-foliation analogies for redundant candidates did not survive scrutiny, and neither did multigraph spectral dimension as a way to skip encoder passes. A two-stage cascade that prefilters candidates with chrF and then reranks with the neural metric is simpler and very likely matches anything the diffusion picture would offer. We would rather not dress that cascade in physics vocabulary.

Baselines

The reference points are MAP beam search and vanilla full-matrix MBR. The file reports COMET 83.9 for MBR against 77.3 for MAP on En-De (mbrs: A Library for Minimum Bayes Risk Decoding). Vanilla MBR defines the target, which is the top-1 match rate with its selected candidate together with the final COMET and XCOMET scores.

The main competitor is PMBR at a fixed sampling fraction (Efficient Minimum Bayes Risk Decoding using Low-Rank Matrix Completion Algorithms). That paper reports matching vanilla MBR quality while computing 6.25% of utility scores on WMT22 with PaLM-8B and 1024 samples. Beating it means matching vanilla quality at a clearly lower average fraction of calls. It also means degrading more gracefully at matched low budgets.

The strongest method at extreme budgets is AC-PMBR (Agreement-Constrained Probabilistic Minimum Bayes Risk Decoding). It reports about 2.5% higher XCOMET and 2% higher chrF than PMBR at 1024x reduction on WMT23 En↔De with M2M100. We would run it with its BLEURT-20-D6 helper and count the helper's calls in wall-clock time. Beating it at the same target-metric budget without a helper model is the decisive win. If we only tie, we would test whether adaptive budgeting stacks on top of AC-PMBR.

We would also include CBMBR (Centroid-Based Efficient Minimum Bayes Risk Decoding) and RAMBR and PruneMBR from the mbrs library as further speed baselines. All methods share candidate pools, metric checkpoints, hardware and the mbrs profiler.

Two ablations isolate the key ingredient. The first assigns random per-sentence budgets with the same mean, which shows whether gains come from difficulty estimation rather than from variance in allocation. The second replaces the fitted non-Gaussian $\sigma_{\text{eff}}$ with the Marchenko–Pastur value, which shows whether the matrix-model machinery matters at all.

Why not just…?

Why not just keep PMBR at a fixed 1/16 budget? It works on average. But a single budget cannot be right for both near-unanimous sentences and contested ones, and AC-PMBR shows fixed budgets fail sharply at extreme reductions. Our matched-mean comparison measures directly how much adaptivity buys. If the per-sentence spread of $p^\star$ turns out narrow, the gain will be small and we will report that.

Why not just choose the budget by cross-validation on held-out entries? This is the real threat. Sequentially sampling until held-out completion error stabilizes could reach similar budgets. Its costs are extra metric calls spent on validation and serial rounds that hurt batching. We would implement it with the same total call count, including validation calls. If it matches us, the theory's contribution reduces to explaining why the stopping point lands where it does.

Why not just use a distilled metric or chrF as a prefilter? Distilled and lexical utilities correlate worse with human judgments (Results of WMT22 Metrics Shared Task: Stop Using BLEU - Neural Metrics Are Better and More Robust). A cascade can still be cheap and good, so we include a chrF-top-64-then-neural cascade at matched wall-clock time. We would also apply our budget rule inside the cascade's second stage, since the two ideas are complementary rather than competing.

Decisive Checks

The theory stands or falls on whether the predicted $p^\star$, computed from pilot samples alone, matches the empirical sampling rate at which PMBR's top-1 agreement with vanilla MBR falls below 90%, sentence by sentence. Our working expectation is a rank correlation clearly above what $\Delta$ alone predicts. If prediction and observed collapse disagree, the spiked-plus-noise model is wrong for metric matrices, and that negative result is itself informative about why AC-PMBR's helper model is needed.

The second check uses chrF as the utility. CBMBR does not apply there, and a method grounded in spectral structure rather than embeddings should transfer. The third check is end-to-end. It measures corpus COMET and XCOMET against total metric calls and wall-clock time on WMT23 En↔De and WMT22 en↔de/ru. The question is whether adaptive allocation shifts the quality-versus-calls curve beyond both PMBR and AC-PMBR.