Adaptive KappaSharp: Condition-Number Shaping for Preferential Bayesian Optimization

# Adaptive KappaSharp: Condition-Number Shaping for Preferential Bayesian Optimization
Source: [https://arxiv.org/html/2608.07859](https://arxiv.org/html/2608.07859)
Ketong Shao1Jialu Wang2Xuekai Pei3Ali Mesbah1 1University of California, Berkeley2Independent3Wuhan University \{ketong\_shao, mesbah\}@berkeley\.edu luuyoyo1996@gmail\.compeixuekai@whu\.edu\.cn

###### Abstract

Preferential Bayesian optimization \(PBO\) optimizes objectives accessible only through pairwise user comparisons\. The standard approach fits a Gaussian process surrogate for observed pairwise comparisons \(PairwiseGP\) using the Laplace approximation and selects queries with the Expected Utility of Best Option \(EUBO\) acquisition function\. EUBO queries new candidates at each step, producing pairs that share no candidates with previous queries\. Each such pair forms an isolated component in the comparison graph, removing one degree of freedom from the likelihood Hessian and making it rank\-deficient\. This deficiency is structural and cannot be resolved by changing the surrogate modeling approach\. Existing approaches to remedy this issue either waste query budget by forcing comparisons to stay connected, or apply uniform regularization that also perturbs directions already well\-constrained by the observed comparisons\. We propose KappaSharp that enables a diagonal correction to the Hessian to reduce its condition number, with larger corrections where the prior uncertainty is higher\. The correction is only applied in the model fitting step, not query selection\. An adaptive variant of KappaSharp is also presented that activates the correction only when the surrogate is confident about recent comparisons, avoiding unnecessary corrections when the problem is well\-conditioned\. On 11 benchmarks \(5–20 dimensions\), including a 16\-dimensional controller tuning problem in plasma medicine, Adaptive KappaSharp outperforms the standard PBO baseline, with up to\+10\.9%\+10\.9\\%\(p=0\.003p\{=\}0\.003\)\.

## 1Introduction

Bayesian optimization \(BO\)\(Brochuet al\.,[2010](https://arxiv.org/html/2608.07859#bib.bib13)\)is a popular approach for optimizing expensive black\-box functions, but requires a scalar objective\. Preferential BO \(PBO\) removes this requirement by learning from pairwise user comparisons\(Chu and Ghahramani,[2005](https://arxiv.org/html/2608.07859#bib.bib2); Gonzálezet al\.,[2017](https://arxiv.org/html/2608.07859#bib.bib1)\), with applications in exoskeleton gait optimization\(Tuckeret al\.,[2020](https://arxiv.org/html/2608.07859#bib.bib19)\), materials design\(Mikkolaet al\.,[2020](https://arxiv.org/html/2608.07859#bib.bib11)\), and model\-based control design\(Shaoet al\.,[2025](https://arxiv.org/html/2608.07859#bib.bib14)\)\. Standard PBO approaches fit a Gaussian process surrogate for observed pairwise comparisons \(PairwiseGP\) via the Laplace approximation\(Chu and Ghahramani,[2005](https://arxiv.org/html/2608.07859#bib.bib2)\)and select queries using the Expected Utility of Best Option \(EUBO\) acquisition function\(Linet al\.,[2022](https://arxiv.org/html/2608.07859#bib.bib3); Astudilloet al\.,[2023](https://arxiv.org/html/2608.07859#bib.bib4)\), as implemented in BoTorch\(Balandatet al\.,[2020](https://arxiv.org/html/2608.07859#bib.bib12)\)\. Recent work has established regret bounds for PBO\(Xuet al\.,[2024](https://arxiv.org/html/2608.07859#bib.bib5)\), but potential structural limitations of the standard querying strategy have not been investigated\.

How queries are selected directly affects the Hessian that PairwiseGP uses to construct its posterior\. In the Laplace approximation, the posterior covariance is the inverse of the Hessian of the negative log\-posterior\(Rasmussen and Williams,[2006](https://arxiv.org/html/2608.07859#bib.bib20)\)\. Hence, when the likelihood Hessian is rank\-deficient, the full Hessian can become ill\-conditioned and, consequently, the posterior can be poorly determined in certain directions\. The problem is that observed pairwise comparisons are inherently limited: each comparison only informs the surrogate that one candidate’s utility is likely higher than another’s\. That is, ifAA,BBare compared in one query andCC,DDin another, the two utility gaps are learned independently\. All comparisons can be represented as a*comparison graph*, where nodes are candidates and edges are comparisons\. Candidates connected through shared comparisons form*connected components*; candidates in different components have no comparisons connecting them\. We show that each disconnected component introduces one zero eigenvalue in the likelihood Hessian, and that these directions are not informed by the observed comparisons\. With many disconnected components, the likelihood Hessian becomes severely rank\-deficient and the full Hessian can become ill\-conditioned\.

This becomes a practical challenge because most acquisition functions used in PBO, including EUBO, select two candidates independently per query\. When the decision variables are continuous, EUBO maximizes over the full input space, so the selected candidates almost never coincide with previously queried points\(Linet al\.,[2022](https://arxiv.org/html/2608.07859#bib.bib3)\)\. This means each query can add a new disconnected component to the comparison graph, rather than connecting existing ones\. Thus, the number of components grows with every query and the rank deficiency of likelihood Hessian worsens\. Existing approaches either force the comparison graph to stay connected by constraining query selection\(Xuet al\.,[2024](https://arxiv.org/html/2608.07859#bib.bib5)\), which limits exploration, or add uniform regularization to Hessian, which addresses the ill\-conditioning at the expense of perturbing directions where the observed comparisons provide sufficient information\.

Here, we take a different approach: instead of altering the disconnected comparison graph, we look to modify the Hessian of PairwiseGP selectively\. We propose KappaSharp, which improves conditioning of the Hessian by shaping its condition number \(κ\\kappa\)\. Rather than regularizing all Hessian entries uniformly, a correction is added to its diagonal entries\. The correction is larger where the prior uncertainty is high, and smaller where it is small\. The correction directly affects the maximum a posteriori \(MAP\) estimation of the PairwiseGP posterior; not the query selection step\. We additionally present an adaptive variant of KappaSharp that adaptively determines whether the correction must be applied based on PairwiseGP’s confidence inferred from recent comparisons\.[Figure˜1](https://arxiv.org/html/2608.07859#S1.F1)provides an overview of the comparison graph fragmentation problem and how KappaSharp addresses this challenge\. KappaSharp does not modify the acquisition function or the querying strategy; thus, it can be applied as a drop\-in addition to any PBO approach with minimal computational overhead\.

![Refer to caption](https://arxiv.org/html/2608.07859v1/x1.png)Figure 1:Left:An example comparison graph withN=6N\{=\}6candidates,M=4M\{=\}4pairwise comparisons, andNcc=2N\_\{\\mathrm\{cc\}\}\{=\}2disconnected components is shown alongside the corresponding Hessian𝐇=𝐊−1\+Hlik\\mathbf\{H\}=\\mathbf\{K\}^\{\-1\}\+H\_\{\\mathrm\{lik\}\}and corrected Hessian𝐇\+𝐑\\mathbf\{H\}\+\\mathbf\{R\}\. Arrows indicate preference direction\.Middle:The Hessian𝐇=𝐊−1\+Hlik\\mathbf\{H\}=\\mathbf\{K\}^\{\-1\}\+H\_\{\\mathrm\{lik\}\}\. Blue cells show the prior precision𝐊−1\\mathbf\{K\}^\{\-1\}\(dense, all entries\)\. Orange and red cells show the likelihood HessianHlikH\_\{\\mathrm\{lik\}\}, which contributes only within each connected component\. The cross\-component entries receive no contribution from the observed comparisons, soHlikH\_\{\\mathrm\{lik\}\}is rank\-deficient and𝐇\\mathbf\{H\}can be ill\-conditioned\.Right:The corrected Hessian𝐇\+𝐑\\mathbf\{H\}\+\\mathbf\{R\}\. Green diagonal cells show the KappaSharp correctionri=η2/\(η\+\(𝐊−1\)i​i\)r\_\{i\}=\\eta^\{2\}/\(\\eta\+\(\\mathbf\{K\}^\{\-1\}\)\_\{ii\}\), which is larger where the prior precision is low\. Square sizes reflect actual computed values for this example, illustrating that the correction is strongest where𝐊−1\\mathbf\{K\}^\{\-1\}is weakest\.#### Contributions\.

The main contributions of this work are as follows:

1. C1We prove that standard PBO querying fragments the comparison graph, making the likelihood Hessian rank\-deficient\. This is a characteristic of the disconnected comparison graph and cannot be resolved by using alternative surrogate modelling approaches\.
2. C2We propose KappaSharp, a diagonal correction to the Hessian applied in MAP estimation of the PairwiseGP posterior, with larger corrections where the prior precision is low\.
3. C3We present an adaptive variant of KappaSharp that determines whether to apply the correction based on PairwiseGP’s confidence inferred from recent comparisons\.
4. C4We evaluate the performance of KappaSharp on 11 benchmarks \(5–20 dimensions\) with 5 initializations and 60 seeds each, including a dose delivery problem in plasma medicine , in which PBO equipped with Adaptive KappaSharp improves over standard PBO without introducing losses\.

## 2Problem Setup

We aim to findx∗∈arg​maxx∈𝒳⁡f​\(x\)x^\{\*\}\\in\\operatorname\*\{arg\\,max\}\_\{x\\in\\mathcal\{X\}\}f\(x\)for a latent utilityf:𝒳→ℝf:\\mathcal\{X\}\\to\\mathbb\{R\},𝒳⊆ℝd\\mathcal\{X\}\\subseteq\\mathbb\{R\}^\{d\}, that cannot be evaluated directly\. At each iterationt∈\{1,…,T\}t\\in\\\{1,\\ldots,T\\\}, whereTTis the total number of queries, we select a pair of candidates\(xt,a,xt,b\)∈𝒳×𝒳\(x\_\{t,a\},x\_\{t,b\}\)\\in\\mathcal\{X\}\\times\\mathcal\{X\}and observe only a binary preference\. The user does not observe the utility values; instead, the preference is generated through noisy comparisons:

yt,a=f​\(xt,a\)\+ϵt,a,yt,b=f​\(xt,b\)\+ϵt,b,ϵt,a,ϵt,b​∼i\.i\.d\.​𝒩​\(0,σ2\),y\_\{t,a\}=f\(x\_\{t,a\}\)\+\\epsilon\_\{t,a\},\\quad y\_\{t,b\}=f\(x\_\{t,b\}\)\+\\epsilon\_\{t,b\},\\quad\\epsilon\_\{t,a\},\\epsilon\_\{t,b\}\\overset\{i\.i\.d\.\}\{\\sim\}\\mathcal\{N\}\(0,\\sigma^\{2\}\),\(1\)with noise scaleσ\>0\\sigma\>0\. The user reportsxt,a≻xt,bx\_\{t,a\}\\succ x\_\{t,b\}ifyt,a\>yt,by\_\{t,a\}\>y\_\{t,b\}\. This yields the probit likelihood

P​\(xt,a≻xt,b∣𝐟\)=Φ​\(f​\(xt,a\)−f​\(xt,b\)σ​2\),P\(x\_\{t,a\}\\succ x\_\{t,b\}\\mid\\mathbf\{f\}\)=\\Phi\\\!\\left\(\\frac\{f\(x\_\{t,a\}\)\-f\(x\_\{t,b\}\)\}\{\\sigma\\sqrt\{2\}\}\\right\),\(2\)where𝐟\\mathbf\{f\}denotes the vector of latent utilities at all queried candidates andΦ\\Phiis the standard normal cumulative distribution function \(CDF\)\. Each observation is recorded as an ordered pair\(xt\+,xt−\)\(x^\{\+\}\_\{t\},x^\{\-\}\_\{t\}\), wherext\+x^\{\+\}\_\{t\}is the preferred candidate\.

## 3Related Work

#### Preferential Bayesian Optimization\.

Chu and Ghahramani \([2005](https://arxiv.org/html/2608.07859#bib.bib2)\)introduced GP\-based preference learning, andGonzálezet al\.\([2017](https://arxiv.org/html/2608.07859#bib.bib1)\)formulated PBO as a sequential optimization approach\. The EUBO acquisition function\(Linet al\.,[2022](https://arxiv.org/html/2608.07859#bib.bib3)\)and its batch variant qEUBO\(Astudilloet al\.,[2023](https://arxiv.org/html/2608.07859#bib.bib4)\)are currently the standard choice for query selection under the Laplace approximation\.Xuet al\.\([2024](https://arxiv.org/html/2608.07859#bib.bib5)\)provided the first regret bounds for PBO by enforcing a connected comparison graph, at the cost of reduced exploration\. Alternative posterior approximations have also been proposed\.Benavoliet al\.\([2020](https://arxiv.org/html/2608.07859#bib.bib6)\)derived the exact skew\-GP posterior;Takeno and others \([2023](https://arxiv.org/html/2608.07859#bib.bib7)\)developed a practical implementation of SkewGP; andMikkolaet al\.\([2020](https://arxiv.org/html/2608.07859#bib.bib11)\)proposed Gibbs sampling as an alternative\. None of these developments addresses the rank deficiency problem identified in this work: when the comparison graph is disconnected, the observed comparisons provide no information linking different components \([Section˜4](https://arxiv.org/html/2608.07859#S4)\), regardless of the surrogate modelling approach\. SkewGP also requires substantially more computation per posterior evaluation than the Laplace approximation\.

#### Comparison Graphs and Spectral Structure\.

The connection between pairwise comparisons and graph Laplacians is investigated extensively in spectral ranking\(Jianget al\.,[2011](https://arxiv.org/html/2608.07859#bib.bib15)\)\.Shahet al\.\([2016](https://arxiv.org/html/2608.07859#bib.bib16)\)showed that the Fisher information matrix for pairwise comparison models inherits the Laplacian structure\. The fact that the probit Hessian takes a Laplacian form has been known since the work ofChu and Ghahramani \([2005](https://arxiv.org/html/2608.07859#bib.bib2)\), but its impact on the PairwiseGP posterior under standard querying has not been analyzed\. We show that EUBO withq=2q\{=\}2fragments the comparison graph into many disconnected components, causing the likelihood HessianHlikH\_\{\\mathrm\{lik\}\}to lose rank, which will in turn make the full Hessian ill\-conditioned \([Section˜4](https://arxiv.org/html/2608.07859#S4)\)\.

#### Posterior Stabilization in Gaussian Processes\.

Hartmann and Vanhatalo \([2019](https://arxiv.org/html/2608.07859#bib.bib8)\)replaced the Hessian with the Fisher information matrix for GP classification\.Kündig and Sigrist \([2024](https://arxiv.org/html/2608.07859#bib.bib9)\)introduced preconditioners for Vecchia\-Laplace approximations\. In continual learning, Elastic Weight Consolidation \(EWC\)\(Kirkpatricket al\.,[2017](https://arxiv.org/html/2608.07859#bib.bib17)\)and online Laplace\(Immeret al\.,[2021](https://arxiv.org/html/2608.07859#bib.bib18)\)add diagonal regularization based on the curvature of the loss\. These methods do not account for the graph\-Laplacian rank structure that arises in pairwise comparison models\. WhenHlikH\_\{\\mathrm\{lik\}\}is rank\-deficient, the Hessian does not receive contribution from the observed comparisons in certain directions\. Thus, the eigenvalues of the Hessian are determined solely by the prior precision, which can be much smaller than in directions whereHlikH\_\{\\mathrm\{lik\}\}contributes\. The proposed correction scheme addresses this imbalance by shaping the condition number of the Hessian\.

## 4Structural Analysis

The iterative PBO procedure starts fromN0N\_\{0\}initial candidate pointsx1,…,xN0∈𝒳x\_\{1\},\\ldots,x\_\{N\_\{0\}\}\\in\\mathcal\{X\}withM0M\_\{0\}comparisons among them, formingNcc,0N\_\{\\mathrm\{cc\},0\}connected components in the comparison graph\. As discussed in[Section˜1](https://arxiv.org/html/2608.07859#S1), under EUBO with batch sizeq=2q\{=\}2\(two candidate points per query\), each subsequent query selects two new candidate points independent of all previous ones\. Aftert−1t\{\-\}1such queries, we haveNt−1=N0\+2​\(t−1\)N\_\{t\-1\}=N\_\{0\}\+2\(t\{\-\}1\)candidates andMt−1=M0\+\(t−1\)M\_\{t\-1\}=M\_\{0\}\+\(t\{\-\}1\)comparisons\. With a slight abuse of notation, we writeN=Nt−1N=N\_\{t\-1\}andM=Mt−1M=M\_\{t\-1\}for the number of candidates and comparisons at iterationtt, respectively\.

A GP prior𝐟∼𝒩​\(𝟎,𝐊\)\\mathbf\{f\}\\sim\\mathcal\{N\}\(\\mathbf\{0\},\\mathbf\{K\}\)is placed over the latent utility values𝐟=\(f​\(x1\),…,f​\(xN\)\)⊤\\mathbf\{f\}=\(f\(x\_\{1\}\),\\ldots,f\(x\_\{N\}\)\)^\{\\top\}, where𝐊∈ℝN×N\\mathbf\{K\}\\in\\mathbb\{R\}^\{N\\times N\}withKi​j=k​\(xi,xj\)K\_\{ij\}=k\(x\_\{i\},x\_\{j\}\)for a kernel functionkk\. Accordingly, themm\-th comparison records thatxm\+x^\{\+\}\_\{m\}was preferred overxm−x^\{\-\}\_\{m\}\. We encode allMMcomparisons in an incidence matrix𝐂∈ℝM×N\\mathbf\{C\}\\in\\mathbb\{R\}^\{M\\times N\}, where rowmmhas\+1\+1in the column corresponding toxm\+x^\{\+\}\_\{m\},−1\-1in the column corresponding toxm−x^\{\-\}\_\{m\}, and zero elsewhere\. Let𝒟=\{\(xm\+,xm−\)\}m=1M\\mathcal\{D\}=\\\{\(x^\{\+\}\_\{m\},x^\{\-\}\_\{m\}\)\\\}\_\{m=1\}^\{M\}denote the set of observed pairwise comparisons, where each pair records the preferred and non\-preferred candidate\. The Laplace approximation gives the posteriorp​\(𝐟∣𝒟\)≈𝒩​\(𝐟^,𝐇−1\)p\(\\mathbf\{f\}\\mid\\mathcal\{D\}\)\\approx\\mathcal\{N\}\(\\hat\{\\mathbf\{f\}\},\\mathbf\{H\}^\{\-1\}\), where𝐟^=arg​min𝐟−log⁡p​\(𝒟∣𝐟\)\+12​𝐟⊤​𝐊−1​𝐟\\hat\{\\mathbf\{f\}\}=\\operatorname\*\{arg\\,min\}\_\{\\mathbf\{f\}\}\\,\-\\log p\(\\mathcal\{D\}\\mid\\mathbf\{f\}\)\+\\tfrac\{1\}\{2\}\\mathbf\{f\}^\{\\top\}\\mathbf\{K\}^\{\-1\}\\mathbf\{f\}is the MAP estimate of𝐟\\mathbf\{f\}and

𝐇=𝐊−1\+𝐂⊤​𝐖𝐂⏟Hlik\\mathbf\{H\}=\\mathbf\{K\}^\{\-1\}\+\\underbrace\{\\mathbf\{C\}^\{\\top\}\\mathbf\{W\}\\mathbf\{C\}\}\_\{H\_\{\\mathrm\{lik\}\}\}\(3\)is the posterior precision matrix, with𝐖=diag⁡\(ω1,…,ωM\)\\mathbf\{W\}=\\operatorname\{diag\}\(\\omega\_\{1\},\\ldots,\\omega\_\{M\}\)a diagonal matrix of positive weights that depend on𝐟^\\hat\{\\mathbf\{f\}\}, as defined in[Section˜4](https://arxiv.org/html/2608.07859#S4)\. The likelihood HessianHlikH\_\{\\mathrm\{lik\}\}has a specific structure\.

###### Proposition 1\(HlikH\_\{\\mathrm\{lik\}\}is a weighted graph Laplacian\)\.

For every𝐟∈ℝN\\mathbf\{f\}\\in\\mathbb\{R\}^\{N\}with finite comparison scores, the data\-dependent component of the Laplace precision,Hlik​\(𝐟\)=−∇𝐟2log⁡p​\(𝒟∣𝐟\)H\_\{\\mathrm\{lik\}\}\(\\mathbf\{f\}\)=\-\\nabla^\{2\}\_\{\\mathbf\{f\}\}\\log p\(\\mathcal\{D\}\\mid\\mathbf\{f\}\), satisfies

Hlik​\(𝐟\)=𝐂⊤​𝐖​\(𝐟\)​𝐂,H\_\{\\mathrm\{lik\}\}\(\\mathbf\{f\}\)=\\mathbf\{C\}^\{\\top\}\\mathbf\{W\}\(\\mathbf\{f\}\)\\,\\mathbf\{C\},\(4\)where𝐖=diag⁡\(ω1,…,ωM\)\\mathbf\{W\}=\\operatorname\{diag\}\(\\omega\_\{1\},\\ldots,\\omega\_\{M\}\)withωm=\(2​σ2\)−1​ψ​\(zm\)​\(ψ​\(zm\)\+zm\)\>0\\omega\_\{m\}=\(2\\sigma^\{2\}\)^\{\-1\}\\psi\(z\_\{m\}\)\\bigl\(\\psi\(z\_\{m\}\)\+z\_\{m\}\\bigr\)\>0,zm=𝐂m⊤​𝐟/\(σ​2\)z\_\{m\}=\\mathbf\{C\}\_\{m\}^\{\\top\}\\mathbf\{f\}/\(\\sigma\\sqrt\{2\}\),ϕ\\phiis the standard normal probability density function \(PDF\),Φ\\Phiis the CDF, andψ​\(z\)=ϕ​\(z\)/Φ​\(z\)\\psi\(z\)=\\phi\(z\)/\\Phi\(z\)is the inverse Mills ratio\. The rank ofHlikH\_\{\\mathrm\{lik\}\}is

rank⁡\(Hlik\)=N−Ncc,\\operatorname\{rank\}\(H\_\{\\mathrm\{lik\}\}\)=N\-N\_\{\\mathrm\{cc\}\},\(5\)whereNccN\_\{\\mathrm\{cc\}\}is the number of connected components of the comparison graph\.

Within each connected component,HlikH\_\{\\mathrm\{lik\}\}constrains relative utility differences\. That is, the likelihood cannot determine how utilities in one component relate to utilities in another\. Proofs for all propositions and theorems in this section and[Section˜5](https://arxiv.org/html/2608.07859#S5)are given in[Appendix˜A](https://arxiv.org/html/2608.07859#A1)\.

###### Proposition 2\(Likelihood\-null directions\)\.

Letker⁡\(𝐂\)=\{𝐟∈ℝN:𝐂𝐟=𝟎\}\\operatorname\{ker\}\(\\mathbf\{C\}\)=\\\{\\mathbf\{f\}\\in\\mathbb\{R\}^\{N\}:\\mathbf\{C\}\\mathbf\{f\}=\\mathbf\{0\}\\\}be the null space of𝐂\\mathbf\{C\}andrange​\(𝐂⊤\)\\mathrm\{range\}\(\\mathbf\{C\}^\{\\top\}\)be its orthogonal complement\. Let𝐐0∈ℝN×Ncc\\mathbf\{Q\}\_\{0\}\\in\\mathbb\{R\}^\{N\\times N\_\{\\mathrm\{cc\}\}\}and𝐐1∈ℝN×\(N−Ncc\)\\mathbf\{Q\}\_\{1\}\\in\\mathbb\{R\}^\{N\\times\(N\-N\_\{\\mathrm\{cc\}\}\)\}be orthonormal bases forker⁡\(𝐂\)\\operatorname\{ker\}\(\\mathbf\{C\}\)andrange​\(𝐂⊤\)\\mathrm\{range\}\(\\mathbf\{C\}^\{\\top\}\), respectively\. Decompose the latent utility vector as𝐟=𝐐0​ξ\+𝐐1​ζ\\mathbf\{f\}=\\mathbf\{Q\}\_\{0\}\\xi\+\\mathbf\{Q\}\_\{1\}\\zeta, whereξ∈ℝNcc\\xi\\in\\mathbb\{R\}^\{N\_\{\\mathrm\{cc\}\}\}are the null\-space coordinates andζ∈ℝN−Ncc\\zeta\\in\\mathbb\{R\}^\{N\-N\_\{\\mathrm\{cc\}\}\}are the range\-space coordinates\. Then:

1. \(a\)The likelihood does not depend onξ\\xi:p​\(𝒟∣ξ,ζ\)=p​\(𝒟∣ζ\)p\(\\mathcal\{D\}\\mid\\xi,\\zeta\)=p\(\\mathcal\{D\}\\mid\\zeta\)\.
2. \(b\)Under the Laplace approximation, the posterior overξ\\xigivenζ\\zetaequals the prior:pL​\(ξ∣ζ,𝒟\)=p0​\(ξ∣ζ\)p\_\{L\}\(\\xi\\mid\\zeta,\\mathcal\{D\}\)=p\_\{0\}\(\\xi\\mid\\zeta\)\.

The null\-space coordinatesξ\\xirepresent a constant shift in the utility of all candidates within the same connected component, i\.e\., a group of candidate pointsxxthat are linked through a chain of pairwise comparisons\. Since comparisons only measure utility*differences*within a pair, such shifts do not change any comparison outcome, and the posterior overξ\\xiis determined entirely by the GP prior\.

#### Comparison graph fragmentation under EUBO\.

Given the posterior𝒩​\(𝐟^,𝐇−1\)\\mathcal\{N\}\(\\hat\{\\mathbf\{f\}\},\\mathbf\{H\}^\{\-1\}\), the EUBO acquisition function withq=2q\{=\}2selects the pair\(xa,xb\)\(x\_\{a\},x\_\{b\}\)that maximizes the expected utility of the best option in the pair\. For a pair with posterior mean differenceδ=f^​\(xa\)−f^​\(xb\)\\delta=\\hat\{f\}\(x\_\{a\}\)\-\\hat\{f\}\(x\_\{b\}\)and predictive standard deviations=Var​\[f​\(xa\)−f​\(xb\)∣𝒟\]s=\\sqrt\{\\mathrm\{Var\}\[f\(x\_\{a\}\)\-f\(x\_\{b\}\)\\mid\\mathcal\{D\}\]\}, the EUBO score is then

EUBO​\(xa,xb\)=δ​Φ​\(δ/s\)\+s​ϕ​\(δ/s\),\\mathrm\{EUBO\}\(x\_\{a\},x\_\{b\}\)=\\delta\\,\\Phi\(\\delta/s\)\+s\\,\\phi\(\\delta/s\),\(6\)In continuous decision domains, these candidates are almost always new points\(Linet al\.,[2022](https://arxiv.org/html/2608.07859#bib.bib3)\)\. Thus, afterTTqueries fromN0N\_\{0\}initial points withNcc,0N\_\{\\mathrm\{cc\},0\}connected components, there areN0\+2​TN\_\{0\}\+2Tcandidates in up toNcc,0\+TN\_\{\\mathrm\{cc\},0\}\+Tcomponents\.

We now quantify how much the PairwiseGP surrogate can learn from the observed pairwise comparisons using the*effective degrees of freedom*deff∈\[0,N\)d\_\{\\mathrm\{eff\}\}\\in\[0,N\)\. Let𝐌~=𝐊1/2​Hlik​𝐊1/2\\tilde\{\\mathbf\{M\}\}=\\mathbf\{K\}^\{1/2\}H\_\{\\mathrm\{lik\}\}\\mathbf\{K\}^\{1/2\}, which captures how much information the observed comparisons add beyond the prior in each direction of the latent utility space\. Each eigenvalueμi\\mu\_\{i\}of𝐌~\\tilde\{\\mathbf\{M\}\}corresponds to one such direction, andμi/\(1\+μi\)\\mu\_\{i\}/\(1\+\\mu\_\{i\}\)is close to 1 when the comparisons dominate and close to 0 when the prior dominates\.deff=∑iμi/\(1\+μi\)d\_\{\\mathrm\{eff\}\}=\\sum\_\{i\}\\mu\_\{i\}/\(1\+\\mu\_\{i\}\)counts how many directions are effectively informed by the observed comparisons\.

###### Proposition 3\(Effective information dimension\)\.

Given𝐌~\\tilde\{\\mathbf\{M\}\}anddeffd\_\{\\mathrm\{eff\}\}as defined above:

1. \(a\)deff≤rank⁡\(Hlik\)=N−Nccd\_\{\\mathrm\{eff\}\}\\leq\\operatorname\{rank\}\(H\_\{\\mathrm\{lik\}\}\)=N\-N\_\{\\mathrm\{cc\}\}, with equality only in the limitμi→∞\\mu\_\{i\}\\to\\infty\.
2. \(b\)Under EUBOq=2q\{=\}2, assume each iteration queries a comparison between two previously unseen points and the initialN0N\_\{0\}points formNcc,0N\_\{\\mathrm\{cc\},0\}connected components\. Then,N=2​T\+N0N=2T\+N\_\{0\},Ncc=Ncc,0\+TN\_\{\\mathrm\{cc\}\}=N\_\{\\mathrm\{cc\},0\}\+T, anddeff/N≤\(N0\+T−Ncc,0\)/\(N0\+2​T\)d\_\{\\mathrm\{eff\}\}/N\\leq\(N\_\{0\}\+T\-N\_\{\\mathrm\{cc\},0\}\)/\(N\_\{0\}\+2T\), which approaches1/21/2asT→∞T\\to\\infty\.
3. \(c\)Under connected querying \(Ncc=1N\_\{\\mathrm\{cc\}\}\{=\}1\):deff≤N−1d\_\{\\mathrm\{eff\}\}\\leq N\{\-\}1\.
4. \(d\)With any positive\-definite augmentation𝐑≻0\\mathbf\{R\}\\succ 0satisfying𝐊1/2​𝐑𝐊1/2⪰β​𝐈\\mathbf\{K\}^\{1/2\}\\mathbf\{R\}\\mathbf\{K\}^\{1/2\}\\succeq\\beta\\mathbf\{I\}for some scalarβ\>0\\beta\>0, definedeffaugd\_\{\\mathrm\{eff\}\}^\{\\mathrm\{aug\}\}as the effective degrees of freedom computed from𝐇\+𝐑\\mathbf\{H\}\+\\mathbf\{R\}\(i\.e\., replacing𝐌~\\tilde\{\\mathbf\{M\}\}by𝐊1/2​\(Hlik\+𝐑\)​𝐊1/2\\mathbf\{K\}^\{1/2\}\(H\_\{\\mathrm\{lik\}\}\+\\mathbf\{R\}\)\\mathbf\{K\}^\{1/2\}\)\. Then: deffaug≥deff\+Ncc​β1\+β\.d\_\{\\mathrm\{eff\}\}^\{\\mathrm\{aug\}\}\\geq d\_\{\\mathrm\{eff\}\}\+\\frac\{N\_\{\\mathrm\{cc\}\}\\beta\}\{1\+\\beta\}\.\(7\)

In[Section˜4](https://arxiv.org/html/2608.07859#S4.SS0.SSS0.Px1), part \(a\) indicates that each disconnected component removes one effective degree of freedom\. Part \(b\) indicates that under standard EUBO, at most half the degrees of freedom are informed by the observed pairwise comparisons\. Part \(c\) indicates that connected querying removes this ceiling\. Part \(d\) indicates that adding a positive\-definite matrix to the Hessian can increasedeffd\_\{\\mathrm\{eff\}\}algebraically, but this does not represent real information from comparisons \(see[Section˜5](https://arxiv.org/html/2608.07859#S5)\)\.

## 5Condition\-Number Shaping of Hessian

In standard PBO, the posterior of PairwiseGP is estimated via MAP estimation in every iteration\. LetJ0​\(𝐟\)=−log⁡p​\(𝒟∣𝐟\)\+12​𝐟⊤​𝐊−1​𝐟J\_\{0\}\(\\mathbf\{f\}\)=\-\\log p\(\\mathcal\{D\}\\mid\\mathbf\{f\}\)\+\\tfrac\{1\}\{2\}\\mathbf\{f\}^\{\\top\}\\mathbf\{K\}^\{\-1\}\\mathbf\{f\}denote the negative log\-posterior up to a constant, and let𝐟^0=arg​min𝐟⁡J0​\(𝐟\)\\hat\{\\mathbf\{f\}\}\_\{0\}=\\operatorname\*\{arg\\,min\}\_\{\\mathbf\{f\}\}J\_\{0\}\(\\mathbf\{f\}\)be the standard MAP estimate\. As shown in[Section˜4](https://arxiv.org/html/2608.07859#S4), the likelihood HessianHlikH\_\{\\mathrm\{lik\}\}is rank\-deficient when the comparison graph is disconnected, which can make the full Hessian𝐇=𝐊−1\+Hlik​\(𝐟^0\)\\mathbf\{H\}=\\mathbf\{K\}^\{\-1\}\+H\_\{\\mathrm\{lik\}\}\(\\hat\{\\mathbf\{f\}\}\_\{0\}\)ill\-conditioned\. We propose to replace the standard MAP estimation with the augmented problem

𝐟^η=arg​min𝐟⁡J0​\(𝐟\)\+12​𝐟⊤​𝐑​\(η\)​𝐟,\\hat\{\\mathbf\{f\}\}\_\{\\eta\}=\\operatorname\*\{arg\\,min\}\_\{\\mathbf\{f\}\}\\,J\_\{0\}\(\\mathbf\{f\}\)\+\\tfrac\{1\}\{2\}\\mathbf\{f\}^\{\\top\}\\mathbf\{R\}\(\\eta\)\\,\\mathbf\{f\},\(8\)where𝐑​\(η\)=diag⁡\(r1​\(η\),…,rN​\(η\)\)\\mathbf\{R\}\(\\eta\)=\\operatorname\{diag\}\(r\_\{1\}\(\\eta\),\\ldots,r\_\{N\}\(\\eta\)\)is a diagonal correction matrix that adds a penalty to each diagonal entry of the Hessian\. The scalarη\>0\\eta\>0controls the overall correction strength\. After solving for𝐟^η\\hat\{\\mathbf\{f\}\}\_\{\\eta\}, we evaluate the Hessian ofJ0J\_\{0\}\(not the augmented objective\) at𝐟^η\\hat\{\\mathbf\{f\}\}\_\{\\eta\}, denoted as𝐇η=𝐊−1\+Hlik​\(𝐟^η\)\\mathbf\{H\}\_\{\\eta\}=\\mathbf\{K\}^\{\-1\}\+H\_\{\\mathrm\{lik\}\}\(\\hat\{\\mathbf\{f\}\}\_\{\\eta\}\), and use its inverse as the Laplace covariance:ΣMO=𝐇η−1\\Sigma\_\{\\mathrm\{MO\}\}=\\mathbf\{H\}\_\{\\eta\}^\{\-1\}\. That is,𝐑\\mathbf\{R\}shifts the MAP from𝐟^0\\hat\{\\mathbf\{f\}\}\_\{0\}to𝐟^η\\hat\{\\mathbf\{f\}\}\_\{\\eta\}but does not enter the covariance\. We describe the design of𝐑\\mathbf\{R\}next and justify the deployment of MAP\-only in the following\.

### 5\.1KappaSharp Correction

Each diagonal entryri​\(η\)r\_\{i\}\(\\eta\)depends on the prior precision\(𝐊−1\)i​i\(\\mathbf\{K\}^\{\-1\}\)\_\{ii\}at theii\-th candidate point\.

###### Proposition 4\(Correction properties\)\.

Defineai=\(𝐊−1\)i​i\>0a\_\{i\}=\(\\mathbf\{K\}^\{\-1\}\)\_\{ii\}\>0, which denotes the prior precision at theii\-th candidate point, and let

ri​\(η\)=η2η\+ai\.r\_\{i\}\(\\eta\)=\\frac\{\\eta^\{2\}\}\{\\eta\+a\_\{i\}\}\.\(9\)Then, forη\>0\\eta\>0:

1. \(a\)∂ri/∂ai<0\\partial r\_\{i\}/\\partial a\_\{i\}<0: larger prior precision→\\toless correction;
2. \(b\)0<ri<η0<r\_\{i\}<\\eta: the correction is bounded;
3. \(c\)asai→0a\_\{i\}\\to 0:ri→ηr\_\{i\}\\to\\eta\(maximum correction where the prior is weak\);
4. \(d\)asai→∞a\_\{i\}\\to\\infty:ri→0r\_\{i\}\\to 0\(no correction where the prior already dominates\)\.

The correction uses only the diagonal entries\(𝐊−1\)i​i\(\\mathbf\{K\}^\{\-1\}\)\_\{ii\}, not the likelihood HessianHlikH\_\{\\mathrm\{lik\}\}directly\. Adding𝐑\\mathbf\{R\}to the Hessian is equivalent to strengthening the prior precision from𝐊−1\\mathbf\{K\}^\{\-1\}to𝐊−1\+𝐑\\mathbf\{K\}^\{\-1\}\+\\mathbf\{R\}\. The ill\-conditioning of𝐇=𝐊−1\+Hlik\\mathbf\{H\}=\\mathbf\{K\}^\{\-1\}\+H\_\{\\mathrm\{lik\}\}is worst in directions whereHlikH\_\{\\mathrm\{lik\}\}contributes nothing and𝐊−1\\mathbf\{K\}^\{\-1\}is weak\. Under EUBO querying in continuous domains, these two conditions tend to occur simultaneously: newly queried points that form isolated components in the comparison graph tend to have low kernel correlation with existing points, so both their likelihood contribution and their prior uncertainty are high\. By applying larger corrections where\(𝐊−1\)i​i\(\\mathbf\{K\}^\{\-1\}\)\_\{ii\}is small,𝐑\\mathbf\{R\}boosts the weakest eigenvalues of𝐇\\mathbf\{H\}, improving its conditioning without requiring direct access to the structure ofHlikH\_\{\\mathrm\{lik\}\}\. The overall correction strengthη∗\\eta^\{\*\}is calibrated using a condition\-number target on the full Hessian𝐇\+𝐑\\mathbf\{H\}\+\\mathbf\{R\}, which accounts forHlikH\_\{\\mathrm\{lik\}\}indirectly\. The condition numberκ​\(𝐇\)=λmax​\(𝐇\)/λmin​\(𝐇\)\\kappa\(\\mathbf\{H\}\)=\\lambda\_\{\\max\}\(\\mathbf\{H\}\)/\\lambda\_\{\\min\}\(\\mathbf\{H\}\)measures the ratio between the largest and smallest eigenvalues of𝐇\\mathbf\{H\}\. A largeκ​\(𝐇\)\\kappa\(\\mathbf\{H\}\)indicates that some directions are much better determined than others\. We chooseη∗\\eta^\{\*\}as the smallestη\\etathat reducesκ​\(𝐇\+𝐑​\(η\)\)\\kappa\(\\mathbf\{H\}\+\\mathbf\{R\}\(\\eta\)\)to a target level, which we callκ\\kappa\-calibration\.

###### Proposition 5\(κ\\kappa\-calibration is well\-posed\)\.

Let𝐇=𝐊−1\+Hlik​\(𝐟^0\)\\mathbf\{H\}=\\mathbf\{K\}^\{\-1\}\+H\_\{\\mathrm\{lik\}\}\(\\hat\{\\mathbf\{f\}\}\_\{0\}\)be the Hessian at𝐟^0\\hat\{\\mathbf\{f\}\}\_\{0\}andα∈\(0,1\)\\alpha\\in\(0,1\)\. The correction𝐑​\(η\)\\mathbf\{R\}\(\\eta\)is continuous, positive semi\-definite, and monotonically increasing inη\\eta\(i\.e\.,η′\>η⇒𝐑​\(η′\)⪰𝐑​\(η\)\\eta^\{\\prime\}\>\\eta\\Rightarrow\\mathbf\{R\}\(\\eta^\{\\prime\}\)\\succeq\\mathbf\{R\}\(\\eta\)\);κ​\(𝐇\+𝐑​\(η\)\)→1\\kappa\(\\mathbf\{H\}\+\\mathbf\{R\}\(\\eta\)\)\\to 1asη→∞\\eta\\to\\infty; and therefore

η∗=min𝜂​\{η≥0:κ​\(𝐇\+𝐑​\(η\)\)≤κ​\(𝐇\)1−α\}\\eta^\{\*\}=\\underset\{\\eta\}\{\\min\}\\;\\left\\\{\\eta\\geq 0:\\kappa\(\\mathbf\{H\}\+\\mathbf\{R\}\(\\eta\)\)\\leq\\kappa\(\\mathbf\{H\}\)^\{1\-\\alpha\}\\right\\\}\(10\)exists and is finite\.

We setα=0\.1\\alpha=0\.1throughout, targetingκ​\(𝐇\)0\.9\\kappa\(\\mathbf\{H\}\)^\{0\.9\}\. A sensitivity analysis overα\\alphais shown in[Appendix˜I](https://arxiv.org/html/2608.07859#A9)\.

#### Bounded MAP shift\.

If the correction shifts the MAP too far from the original estimate, the resulting posterior may no longer reflect the observed pairwise comparisons\. The following proposition bounds the shiftΔ=𝐟^η−𝐟^0\\Delta=\\hat\{\\mathbf\{f\}\}\_\{\\eta\}\-\\hat\{\\mathbf\{f\}\}\_\{0\}\.

###### Proposition 6\(Bounded MAP shift\)\.

The shiftΔ=𝐟^η−𝐟^0\\Delta=\\hat\{\\mathbf\{f\}\}\_\{\\eta\}\-\\hat\{\\mathbf\{f\}\}\_\{0\}satisfies‖Δ‖𝐇¯≤μmax1\+μmax​‖𝐟^0‖𝐇¯\\left\\\|\\Delta\\right\\\|\_\{\\bar\{\\mathbf\{H\}\}\}\\leq\\frac\{\\mu\_\{\\max\}\}\{1\+\\mu\_\{\\max\}\}\\left\\\|\\hat\{\\mathbf\{f\}\}\_\{0\}\\right\\\|\_\{\\bar\{\\mathbf\{H\}\}\}, where∥⋅∥𝐇¯\\\|\\cdot\\\|\_\{\\bar\{\\mathbf\{H\}\}\}is the norm induced by the path\-averaged Hessian𝐇¯\\bar\{\\mathbf\{H\}\}ofJ0J\_\{0\}, andμmax\\mu\_\{\\max\}is the largest eigenvalue of𝐇¯−1/2​𝐑​𝐇¯−1/2\\bar\{\\mathbf\{H\}\}^\{\-1/2\}\\mathbf\{R\}\\bar\{\\mathbf\{H\}\}^\{\-1/2\}\(the path\-averaged Hessian and its norm are defined in the proof in[Appendix˜A](https://arxiv.org/html/2608.07859#A1)\)\.

Note that shifting the MAP changes the weights𝐖\\mathbf\{W\}but not the rank ofHlikH\_\{\\mathrm\{lik\}\}: since𝐖​\(𝐟\)≻0\\mathbf\{W\}\(\\mathbf\{f\}\)\\succ 0for all finite𝐟\\mathbf\{f\},rank⁡\(Hlik​\(𝐟\)\)=N−Ncc\\operatorname\{rank\}\(H\_\{\\mathrm\{lik\}\}\(\\mathbf\{f\}\)\)=N\-N\_\{\\mathrm\{cc\}\}regardless of𝐟\\mathbf\{f\}\(see[Section˜A\.3](https://arxiv.org/html/2608.07859#A1.SS3)in[Appendix˜A](https://arxiv.org/html/2608.07859#A1)\)\)\.

#### Why𝐑\\mathbf\{R\}should not enter the covariance\.

Recall from[Section˜4](https://arxiv.org/html/2608.07859#S4)that the observed pairwise comparisons provide no information in the null\-space directionsker⁡\(𝐂\)\\operatorname\{ker\}\(\\mathbf\{C\}\); thus, the posterior covariance in those directions should equal the prior\. If we were to include𝐑\\mathbf\{R\}in the covariance, the added𝐑\\mathbf\{R\}would shrink the posterior covariance in the null\-space directions to values smaller than the prior covariance\. PairwiseGP would then underestimate its uncertainty in those directions, and EUBO would stop exploring them\. By excluding𝐑\\mathbf\{R\}from the covariance, MAP\-only preserves the correct uncertainty in the null space\.

###### Theorem 7\(Pseudo\-confidence in null directions\)\.

Using the decomposition𝐟=𝐐0​ξ\+𝐐1​ζ\\mathbf\{f\}=\\mathbf\{Q\}\_\{0\}\\xi\+\\mathbf\{Q\}\_\{1\}\\zetafrom[Section˜4](https://arxiv.org/html/2608.07859#S4), let𝐀=𝐐0⊤​𝐊−1​𝐐0\\mathbf\{A\}=\\mathbf\{Q\}\_\{0\}^\{\\top\}\\mathbf\{K\}^\{\-1\}\\mathbf\{Q\}\_\{0\}be the prior precision on the null\-space coordinatesξ\\xi\. Full augmentation\(𝐇η\+𝐑\)−1\(\\mathbf\{H\}\_\{\\eta\}\{\+\}\\mathbf\{R\}\)^\{\-1\}shrinks the conditional covariance ofξ\\xi, givenζ\\zeta, to\(𝐀\+𝐐0⊤​𝐑𝐐0\)−1≺𝐀−1\(\\mathbf\{A\}\{\+\}\\mathbf\{Q\}\_\{0\}^\{\\top\}\\mathbf\{R\}\\mathbf\{Q\}\_\{0\}\)^\{\-1\}\\prec\\mathbf\{A\}^\{\-1\}since𝐐0⊤​𝐑𝐐0≻0\\mathbf\{Q\}\_\{0\}^\{\\top\}\\mathbf\{R\}\\mathbf\{Q\}\_\{0\}\\succ 0\. MAP\-only preserves𝐀−1\\mathbf\{A\}^\{\-1\}, matching the exact posterior \([Section˜4](https://arxiv.org/html/2608.07859#S4)\)\.

Full augmentation also reduces EUBO scores for all candidate pairs, which discourages exploration\.

###### Proposition 8\(Full augmentation contracts EUBO scores\)\.

LetΣaug:=\(𝐇η\+𝐑\)−1\\Sigma\_\{\\mathrm\{aug\}\}:=\(\\mathbf\{H\}\_\{\\eta\}\+\\mathbf\{R\}\)^\{\-1\}\. For any candidate pair\(xa,xb\)\(x\_\{a\},x\_\{b\}\), letsΣ2​\(a,b\)s^\{2\}\_\{\\Sigma\}\(a,b\)denote the predictive variance of the utility differencef​\(xa\)−f​\(xb\)f\(x\_\{a\}\)\-f\(x\_\{b\}\)under covarianceΣ\\Sigma\. SinceΣaug⪯ΣMO\\Sigma\_\{\\mathrm\{aug\}\}\\preceq\\Sigma\_\{\\mathrm\{MO\}\}, we havesaug2​\(a,b\)≤sMO2​\(a,b\)s\_\{\\mathrm\{aug\}\}^\{2\}\(a,b\)\\leq s\_\{\\mathrm\{MO\}\}^\{2\}\(a,b\)for every pair\. Sinceq=2q\{=\}2EUBO is strictly increasing in the predictive standard deviation at fixed mean, the EUBO score under full augmentation is lower than under MAP\-only for every candidate pair:

EUBOaug​\(a,b\)≤EUBOMO​\(a,b\)for every pair​\(xa,xb\)\.\\mathrm\{EUBO\}\_\{\\mathrm\{aug\}\}\(a,b\)\\leq\\mathrm\{EUBO\}\_\{\\mathrm\{MO\}\}\(a,b\)\\quad\\text\{for every pair \}\(x\_\{a\},x\_\{b\}\)\.\(11\)

#### The cost of MAP\-only is bounded\.

Excluding𝐑\\mathbf\{R\}from the covariance avoids both issues\. The acquisition gap from between the MAP\-only and full\-augmentation strategies is bounded\.

###### Theorem 9\(Bounded acquisition gap\)\.

The difference in EUBO between the MAP\-only maximizer and the full\-augmentation maximizer is at mostO​\(λ1\)O\(\\lambda\_\{1\}\), whereλ1\\lambda\_\{1\}is the largest eigenvalue of𝐇η−1/2​𝐑​𝐇η−1/2\\mathbf\{H\}\_\{\\eta\}^\{\-1/2\}\\mathbf\{R\}\\,\\mathbf\{H\}\_\{\\eta\}^\{\-1/2\}, measuring how large the correction𝐑\\mathbf\{R\}is relative to the Hessian𝐇η\\mathbf\{H\}\_\{\\eta\}\. The precise bound is given in[Appendix˜A](https://arxiv.org/html/2608.07859#A1)and is finite for any continuous kernel on a compact domain\.

### 5\.2Adaptive Activation

Applying KappaSharp at every iteration, referred to as*Static KS*in our experiments, is beneficial when the rank deficiency of the likelihood Hessian is the primary bottleneck limiting the surrogate\. However, it can be detrimental when the prior already provides sufficient conditioning\. We observe that PairwiseGP’s confidence on recently queried pairs separates these two regimes: when the rank deficiency of the likelihood Hessian dominates, the surrogate quickly becomes confident about individual comparisons; when the prior is already well\-conditioned, the surrogate remains uncertain\. The adaptive variant of KappaSharp uses this separation to decide when to activate the correction\.

#### Decisiveness score\.

After fitting the surrogate on𝒟t−1\\mathcal\{D\}\_\{t\-1\}, we measure how confidently it distinguishes a recently compared pair\. Letμdiff=\|f^​\(xt−1\+\)−f^​\(xt−1−\)\|\\mu\_\{\\mathrm\{diff\}\}=\|\\hat\{f\}\(x^\{\+\}\_\{t\-1\}\)\-\\hat\{f\}\(x^\{\-\}\_\{t\-1\}\)\|be the absolute posterior mean difference andσdiff2\\sigma\_\{\\mathrm\{diff\}\}^\{2\}the posterior variance off​\(xt−1\+\)−f​\(xt−1−\)f\(x^\{\+\}\_\{t\-1\}\)\-f\(x^\{\-\}\_\{t\-1\}\)\. The surrogate’s predicted probability that the comparison outcome matches its ranking ispt=Φ​\(μdiff/σdiff2\+2​σ2\)∈\[1/2,1\)p\_\{t\}=\\Phi\\\!\\left\(\\mu\_\{\\mathrm\{diff\}\}/\\sqrt\{\\sigma\_\{\\mathrm\{diff\}\}^\{2\}\+2\\sigma^\{2\}\}\\right\)\\in\[1/2,1\), where2​σ22\\sigma^\{2\}is the comparison noise variance from the probit model \([Equation˜1](https://arxiv.org/html/2608.07859#S2.E1)\)\. A high value ofptp\_\{t\}indicates that the surrogate predicts a clear utility difference between the two candidates, whereaspt≈0\.5p\_\{t\}\\approx 0\.5indicates that the comparison is ambiguous\. We define the*decisiveness score*as

sexp,t=1−ℋ​\(pt\)log⁡2,s\_\{\\mathrm\{exp\},t\}=1\-\\frac\{\\mathcal\{H\}\(p\_\{t\}\)\}\{\\log 2\},\(12\)whereℋ​\(p\)=−p​log⁡p−\(1−p\)​log⁡\(1−p\)\\mathcal\{H\}\(p\)=\-p\\log p\-\(1\{\-\}p\)\\log\(1\{\-\}p\)is the binary entropy\. The score ranges from0\(coin flip\) to11\(decisive\)\.

#### Activation rule\.

We track an exponential moving average to smooth the step\-to\-step variance ofsexp,ts\_\{\\mathrm\{exp\},t\}:

s¯t=\(1−αema\)​s¯t−1\+αema​sexp,t,αema=0\.2,\\bar\{s\}\_\{t\}=\(1\-\\alpha\_\{\\mathrm\{ema\}\}\)\\,\\bar\{s\}\_\{t\-1\}\+\\alpha\_\{\\mathrm\{ema\}\}s\_\{\\mathrm\{exp\},t\},\\quad\\alpha\_\{\\mathrm\{ema\}\}=0\.2,\(13\)initialized ats¯0=0\\bar\{s\}\_\{0\}=0\. The correction activates at stepttwhens¯t≥τ\\bar\{s\}\_\{t\}\\geq\\tau, with thresholdτ=0\.30\\tau=0\.30\. In each step,τ=0\.30\\tau=0\.30corresponds topt≥0\.81p\_\{t\}\\geq 0\.81\([Appendix˜D](https://arxiv.org/html/2608.07859#A4)in[Appendix˜D](https://arxiv.org/html/2608.07859#A4)\)\. The activation rule uses the EMAs¯t\\bar\{s\}\_\{t\}, not the per\-step score\. Thus,s¯t≥τ\\bar\{s\}\_\{t\}\\geq\\tauindicates sufficient average decisiveness over recent comparisons\.[Algorithm˜1](https://arxiv.org/html/2608.07859#alg1)summarizes the Adaptive KappaSharp approach\. When the correction is active, the additional computation consists of reading the diagonal of𝐊−1\\mathbf\{K\}^\{\-1\}to form𝐑\\mathbf\{R\}, searching over 60 log\-spaced values ofη\\etato solve theκ\\kappa\-calibration problem, and running one extra Newton solve for the augmented MAP\. The better\-conditioned Hessian often reduces the number of Newton iterations needed, partially or fully offsetting this cost \([Appendix˜L](https://arxiv.org/html/2608.07859#A12)\)\. When the correction is inactive, the only overhead per step is evaluatingsexps\_\{\\mathrm\{exp\}\}from a single posterior prediction\.

Algorithm 1Adaptive KappaSharp for Preferential BO0:Initial data

𝒟0\\mathcal\{D\}\_\{0\}, GP prior

𝐊\\mathbf\{K\}, threshold

τ=0\.30\\tau=0\.30, calibration

α=0\.1\\alpha=0\.1, EMA rate

αema=0\.2\\alpha\_\{\\mathrm\{ema\}\}=0\.2, minimum step

tmin=8t\_\{\\min\}=8
1:Initialize

s¯0←0\\bar\{s\}\_\{0\}\\leftarrow 0
2:for

t=1,2,…,Tt=1,2,\\ldots,Tdo

3:Fit PairwiseGP on

𝒟t−1\\mathcal\{D\}\_\{t\-1\}: compute MAP

𝐟^0\\hat\{\\mathbf\{f\}\}\_\{0\}, Hessian

𝐇=𝐊−1\+Hlik\\mathbf\{H\}=\\mathbf\{K\}^\{\-1\}\+H\_\{\\mathrm\{lik\}\}
4:Compute

sexp,ts\_\{\\mathrm\{exp\},t\}from PairwiseGP’s prediction on most recent comparison\{Eq\. \([12](https://arxiv.org/html/2608.07859#S5.E12)\)\}

5:Update

s¯t←\(1−αema\)​s¯t−1\+αema​sexp,t\\bar\{s\}\_\{t\}\\leftarrow\(1\-\\alpha\_\{\\mathrm\{ema\}\}\)\\,\\bar\{s\}\_\{t\-1\}\+\\alpha\_\{\\mathrm\{ema\}\}s\_\{\\mathrm\{exp\},t\}\{Eq\. \([13](https://arxiv.org/html/2608.07859#S5.E13)\)\}

6:if

t≥tmint\\geq t\_\{\\min\}and

s¯t≥τ\\bar\{s\}\_\{t\}\\geq\\tauthen

7:Compute

ai=\(𝐊−1\)i​ia\_\{i\}=\(\\mathbf\{K\}^\{\-1\}\)\_\{ii\}and

𝐑​\(η\)=diag⁡\(η2/\(η\+ai\)\)\\mathbf\{R\}\(\\eta\)=\\operatorname\{diag\}\(\\eta^\{2\}/\(\\eta\+a\_\{i\}\)\)\{Eq\. \([9](https://arxiv.org/html/2608.07859#S5.E9)\)\}

8:Solve

η∗=min𝜂​\{η≥0:κ​\(𝐇\+𝐑​\(η\)\)≤κ​\(𝐇\)1−α\}\\eta^\{\*\}=\\underset\{\\eta\}\{\\min\}\\;\\\{\\eta\\geq 0:\\kappa\(\\mathbf\{H\}\+\\mathbf\{R\}\(\\eta\)\)\\leq\\kappa\(\\mathbf\{H\}\)^\{1\-\\alpha\}\\\}\{Eq\. \([10](https://arxiv.org/html/2608.07859#S5.E10)\)\}

9:Re\-solve MAP:

𝐟^η←arg​min⁡J0​\(𝐟\)\+12​𝐟⊤​𝐑​\(η∗\)​𝐟\\hat\{\\mathbf\{f\}\}\_\{\\eta\}\\leftarrow\\operatorname\*\{arg\\,min\}J\_\{0\}\(\\mathbf\{f\}\)\+\\tfrac\{1\}\{2\}\\mathbf\{f\}^\{\\top\}\\mathbf\{R\}\(\\eta^\{\*\}\)\\mathbf\{f\}\{Eq\. \([8](https://arxiv.org/html/2608.07859#S5.E8)\)\}

10:Set approximate posterior:

𝒩​\(𝐟^η,𝐇−1\|𝐟^η\)\\mathcal\{N\}\(\\hat\{\\mathbf\{f\}\}\_\{\\eta\},\\;\\mathbf\{H\}^\{\-1\}\|\_\{\\hat\{\\mathbf\{f\}\}\_\{\\eta\}\}\)\{Unaugmented covariance at shifted MAP\}

11:else

12:Use standard posterior:

𝒩​\(𝐟^0,𝐇−1\|𝐟^0\)\\mathcal\{N\}\(\\hat\{\\mathbf\{f\}\}\_\{0\},\\;\\mathbf\{H\}^\{\-1\}\|\_\{\\hat\{\\mathbf\{f\}\}\_\{0\}\}\)
13:endif

14:Select next query

\(xa,xb\)\(x\_\{a\},x\_\{b\}\)via EUBO on the current posterior

15:Observe comparison outcome; update

𝒟t←𝒟t−1∪\{\(xt\+,xt−\)\}\\mathcal\{D\}\_\{t\}\\leftarrow\\mathcal\{D\}\_\{t\-1\}\\cup\\\{\(x^\{\+\}\_\{t\},x^\{\-\}\_\{t\}\)\\\}
16:endfor

## 6Experiments

We benchmark Adaptive KappaSharp against the standard PairwiseGP baseline and several alternatives on 11 problems spanning 5 to 20 dimensions\. The baselines include Static KS \(KappaSharp applied at every iteration without the activation rule\), Fixed20 \(correction activated only after step 20, without the decisiveness criterion\), Connected Querying \(one candidate per query is fixed to the previous query pointxt′=xt−1x^\{\\prime\}\_\{t\}=x\_\{t\-1\}, following the querying strategy ofXuet al\.\([2024](https://arxiv.org/html/2608.07859#bib.bib5)\); EUBO is retained as the acquisition function for fair comparison\), and the unmodified PairwiseGP\-Laplace \+ EUBO baseline \(B\)\. We report ablations and diagnostic comparisons with non\-Laplace inference\.

### 6\.1Setup

#### Benchmarks\.

The 11 benchmarks span 5 to 20 dimensions: DTLZ2\-8D, DTLZ2\-16D, DTLZ2\-20D \(multi\-objective PBO test functions\), Plasma\-16D \(model\-based control design in plasma medicine\(Shaoet al\.,[2025](https://arxiv.org/html/2608.07859#bib.bib14)\)\), Ackley\-8D, Hartmann\-6D, Levy\-10D, Levy\-20D, Vehicle\-5D \(single\-objective\), CarCab\-7D \(vehicle cabin design\), and RobotPush\-14D \(Box2D physics simulation\)\.

#### Protocol\.

All methods use PairwiseGP with the Laplace approximation and EUBO acquisition\(Linet al\.,[2022](https://arxiv.org/html/2608.07859#bib.bib3)\), implemented in BoTorch\(Balandatet al\.,[2020](https://arxiv.org/html/2608.07859#bib.bib12)\)\. Each run consists ofT=50T=50sequential pairwise queries, with comparison noiseσ=0\.1\\sigma=0\.1\. We test five initialization conditions:pool\_n6\_k15\(6 candidates, all 15 pairwise comparisons; primary\),pool\_n8\_k15\(8 candidates, 15 comparisons\), and three pure\-matching conditionspure\_k3,pure\_k5,pure\_k15\(kknon\-overlapping pairs among2​k2kcandidates\)\. Each condition uses 60 seeds with paired same\-node execution and common random numbers \(CRN\)\. The total number of runs in the main grid is16,50016\{,\}500\(11 benchmarks×\\times5 inits×\\times5 methods×\\times60 seeds\)\.

#### Evaluation\.

We report percentage improvement in final best utility over baseline B\. Significance is assessed via pairedtt\-test \(p<0\.05p<0\.05, uncorrected\)\. A benchmark\-method pair is classified as win \(W\), loss \(L\), or neutral \(N\) based on the sign and significance of the improvement\.

### 6\.2Baselines and ablations

Table 1:Benchmark results \(pool\_n6\_k15 init, 60 seeds\)\. B: PairwiseGP\-Laplace \+ EUBO baseline\. Static KS: KappaSharp without activation rule\. Fixed20: correction on at stept≥20t\{\\geq\}20\. Conn\. Query: connected querying strategy ofXuet al\.\([2024](https://arxiv.org/html/2608.07859#bib.bib5)\), with EUBO retained for fair comparison\. Adaptive KS: proposed method with confidence\-based activation \(τ=0\.30\\tau\{=\}0\.30\)\. Gain \(%\) relative to B\.Bold: best mean\.∗:p<0\.05p\{<\}0\.05,∗∗:p<0\.01p\{<\}0\.01\(pairedtt\-test\)\.BStatic KSFixed20Conn\. QueryAdaptive KSBenchmarkddmean±\\pmstdmean±\\pmstdGainmean±\\pmstdGainmean±\\pmstdGainmean±\\pmstdGainDTLZ2\-16D16\-1\.031±\\pm0\.341\-0\.778±\\pm0\.281\+24\.5%∗∗\-0\.783±\\pm0\.282\+24\.0%∗∗\-1\.016±\\pm0\.327\+1\.5%\-0\.875±\\pm0\.265\+15\.1%∗∗DTLZ2\-8D8\-0\.184±\\pm0\.134\-0\.142±\\pm0\.068\+23\.2%∗\-0\.167±\\pm0\.114\+9\.6%\-0\.357±\\pm0\.189\-93\.9%∗∗\-0\.163±\\pm0\.101\+11\.7%DTLZ2\-20D20\-1\.439±\\pm0\.390\-1\.183±\\pm0\.379\+17\.8%∗∗\-1\.256±\\pm0\.453\+12\.7%∗∗\-1\.350±\\pm0\.342\+6\.2%\-1\.268±\\pm0\.444\+11\.9%∗Plasma\-16D16\-92\.785±\\pm24\.954\-84\.005±\\pm20\.141\+9\.5%∗∗\-85\.676±\\pm22\.113\+7\.7%∗\-103\.451±\\pm38\.509\-11\.5%∗\-82\.642±\\pm21\.800\+10\.9%∗∗Levy\-10D10\-17\.193±\\pm11\.645\-13\.985±\\pm9\.807\+18\.7%∗\-13\.675±\\pm8\.420\+20\.5%∗∗\-20\.920±\\pm11\.493\-21\.7%∗\-13\.069±\\pm9\.307\+24\.0%∗∗Levy\-20D20\-64\.416±\\pm22\.656\-62\.420±\\pm29\.474\+3\.1%\-58\.497±\\pm23\.673\+9\.2%∗\-70\.013±\\pm22\.260\-8\.7%\-58\.167±\\pm27\.639\+9\.7%∗Ackley\-8D8\-1\.168±\\pm0\.756\-1\.350±\\pm0\.773\-15\.6%∗\-1\.265±\\pm0\.786\-8\.3%\-1\.891±\\pm0\.776\-61\.9%∗∗\-1\.184±\\pm0\.739\-1\.4%Hartmann\-6D62\.959±\\pm0\.3412\.818±\\pm0\.444\-4\.8%∗∗2\.810±\\pm0\.513\-5\.0%∗∗2\.611±\\pm0\.586\-11\.8%∗∗2\.934±\\pm0\.456\-0\.9%CarCab\-7D7\-3\.888±\\pm0\.081\-3\.900±\\pm0\.084\-0\.3%\-3\.894±\\pm0\.091\-0\.2%\-3\.895±\\pm0\.083\-0\.2%\-3\.889±\\pm0\.088\-0\.0%Vehicle\-5D5\-5038\.884±\\pm0\.261\-5038\.994±\\pm0\.945\-0\.0%\-5039\.100±\\pm0\.993\-0\.0%\-5039\.640±\\pm1\.875\-0\.0%∗\-5038\.873±\\pm0\.136\+0\.0%RobotPush\-14D143\.576±\\pm1\.7993\.639±\\pm1\.851\+1\.8%3\.736±\\pm1\.665\+4\.5%2\.691±\\pm1\.820\-24\.8%∗∗3\.776±\\pm1\.810\+5\.6%W / L / N5 / 2 / 45 / 1 / 50 / 7 / 45 / 0 / 6

[Table˜1](https://arxiv.org/html/2608.07859#S6.T1)compares all methods on the primary initialization \(pool\_n6\_k15, 60 seeds\)\. Static KS wins on 5 benchmarks \(DTLZ2\-16D\+24\.5%\+24\.5\\%, DTLZ2\-8D\+23\.2%\+23\.2\\%, DTLZ2\-20D\+17\.8%\+17\.8\\%, Plasma\+9\.5%\+9\.5\\%, Levy\-10D\+18\.7%\+18\.7\\%\) but loses on Ackley\-8D \(−15\.6%\-15\.6\\%\) and Hartmann\-6D \(−4\.8%\-4\.8\\%\)\. Connected Querying achieves 0W/7L/4N, with−93\.9%\-93\.9\\%on DTLZ2\-8D and−61\.9%\-61\.9\\%on Ackley\-8D \(bothp<0\.01p<0\.01\); see[Appendix˜J](https://arxiv.org/html/2608.07859#A10)for details\.

We ablate the correction design in[Table˜2](https://arxiv.org/html/2608.07859#A2.T2)\([Appendix˜B](https://arxiv.org/html/2608.07859#A2)\)\. Uniform jitter \(𝐑=c​I\\mathbf\{R\}=cI\): 0W/5L\. Uniform diagonal \(𝐑=η∗​I\\mathbf\{R\}=\\eta^\{\*\}I, without\(𝐊−1\)i​i\(\\mathbf\{K\}^\{\-1\}\)\_\{ii\}weighting\): 3W/2L\. MetricOnly \(𝐑\\mathbf\{R\}in the Newton step butJ0J\_\{0\}unchanged, so MAP is the same\): 1W/0L\. CovOnly \(MAP unchanged, covariance uses\(𝐇\+𝐑\)−1\(\\mathbf\{H\}\+\\mathbf\{R\}\)^\{\-1\}\): 1W/0L\. These results indicate that the MAP correction is the main source of improvement\. We also compare against EP\-EI and Gibbs\-EI\(Takeno and others,[2023](https://arxiv.org/html/2608.07859#bib.bib7)\)\. As discussed in[Section˜3](https://arxiv.org/html/2608.07859#S3), changing the inference method does not resolve the rank deficiency of the likelihood Hessian \([Section˜4](https://arxiv.org/html/2608.07859#S4)\)\. Both score worse than Laplace\+EUBO \([Appendix˜K](https://arxiv.org/html/2608.07859#A11)\); EP and Gibbs do not have an acquisition function like EUBO; hence, they use EI, designed for scalar observations rather than pairwise comparisons\.

### 6\.3Main results

Adaptive KS scores5W/0L/6Non the primary initialization: DTLZ2\-16D \(\+15\.1%\+15\.1\\%\), DTLZ2\-20D \(\+11\.9%\+11\.9\\%\), Plasma\-16D \(\+10\.9%\+10\.9\\%\), Levy\-10D \(\+24\.0%\+24\.0\\%\), Levy\-20D \(\+9\.7%\+9\.7\\%\)\. On Ackley\-8D and Hartmann\-6D, where Static KS loses, Adaptive KS is neutral \(−1\.4%\-1\.4\\%and−0\.9%\-0\.9\\%, respectively\)\. Fixed20 still loses on Hartmann \(−5\.0%\-5\.0\\%\), confirming that the decisiveness\-based activation is important\.[Figure˜2](https://arxiv.org/html/2608.07859#S6.F2)shows effect sizes; convergence curves are given in[Appendix˜E](https://arxiv.org/html/2608.07859#A5)\.

![Refer to caption](https://arxiv.org/html/2608.07859v1/x2.png)Figure 2:Effect sizes \(% improvement over baseline, 95% CI, pool\_n6\_k15, 60 seeds\)\. Filled markers indicatep<0\.05p<0\.05\. Adaptive KS: 5W/0L/6N\. Static KS: 5W/2L/4N\.#### Robustness across initializations\.

Across all 55 cells \(11 benchmarks×\\times5 initializations\): 18W/2L/35N\. Both losses occur on Hartmann\-6D under sparse pure\-matching initializations and are smaller than2\.5%2\.5\\%\. On pool initializations: 10W/0L\. On the plasma problem\(Shaoet al\.,[2025](https://arxiv.org/html/2608.07859#bib.bib14)\):\+10\.9%\+10\.9\\%\(p=0\.003p=0\.003\)\. The thresholdτ\\tauis stable:τ∈\{0\.25,0\.30,0\.35\}\\tau\\in\\\{0\.25,0\.30,0\.35\\\}produces zero losses on 4 representative benchmarks \([Appendix˜H](https://arxiv.org/html/2608.07859#A8)\)\.

## 7Discussion and conclusion

Standard EUBO querying in PBO yields disconnected comparison graphs, causing rank deficiency in the likelihood Hessian and ill\-conditioning irrespective of the inference method\. KappaSharp addresses this by adding a prior\-weighted diagonal correction during MAP estimation, with an adaptive variant that activates based on decisiveness\. Across 11 benchmarks, including a plasma medicine task, Adaptive KappaSharp consistently improves performance, with gains up to \+10\.9%\. Remaining limitations include an empirically chosen threshold and evaluation with oracle\-simulated preferences\. Future work will develop eigenvector\-aligned \(non\-diagonal\) corrections, extend analysis to larger batch sizes, and automate threshold selection\.

## References

- qEUBO: a decision\-theoretic acquisition function for preferential Bayesian optimization\.InInternational Conference on Artificial Intelligence and Statistics \(AISTATS\),Cited by:[§1](https://arxiv.org/html/2608.07859#S1.p1.1),[§3](https://arxiv.org/html/2608.07859#S3.SS0.SSS0.Px1.p1.1)\.
- M\. Balandat, B\. Karrer, D\. R\. Jiang, S\. Daulton, B\. Letham, A\. G\. Wilson, and E\. Bakshy \(2020\)BoTorch: a framework for efficient Monte\-Carlo Bayesian optimization\.InAdvances in Neural Information Processing Systems \(NeurIPS\),Cited by:[§1](https://arxiv.org/html/2608.07859#S1.p1.1),[§6\.1](https://arxiv.org/html/2608.07859#S6.SS1.SSS0.Px2.p1.8)\.
- A\. Benavoli, D\. Azzimonti, and D\. Piga \(2020\)Preferential Bayesian optimisation with skew Gaussian processes\.arXiv preprint arXiv:2008\.06677\.Cited by:[§3](https://arxiv.org/html/2608.07859#S3.SS0.SSS0.Px1.p1.1)\.
- E\. Brochu, V\. M\. Cora, and N\. de Freitas \(2010\)A tutorial on Bayesian optimization of expensive cost functions, with application to active user modeling and hierarchical reinforcement learning\.arXiv preprint arXiv:1012\.2599\.Cited by:[§1](https://arxiv.org/html/2608.07859#S1.p1.1)\.
- W\. Chu and Z\. Ghahramani \(2005\)Preference learning with Gaussian processes\.InInternational Conference on Machine Learning \(ICML\),Cited by:[§1](https://arxiv.org/html/2608.07859#S1.p1.1),[§3](https://arxiv.org/html/2608.07859#S3.SS0.SSS0.Px1.p1.1),[§3](https://arxiv.org/html/2608.07859#S3.SS0.SSS0.Px2.p1.2)\.
- J\. González, Z\. Dai, A\. Damianou, and N\. D\. Lawrence \(2017\)Preferential Bayesian optimization\.InInternational Conference on Machine Learning \(ICML\),Cited by:[§G\.1](https://arxiv.org/html/2608.07859#A7.SS1.SSS0.Px1.p1.1),[§1](https://arxiv.org/html/2608.07859#S1.p1.1),[§3](https://arxiv.org/html/2608.07859#S3.SS0.SSS0.Px1.p1.1)\.
- M\. Hartmann and J\. Vanhatalo \(2019\)Laplace approximation and natural gradient for Gaussian process regression with heteroscedastic student\-ttmodel\.Statistics and Computing29,pp\. 753–773\.Cited by:[§3](https://arxiv.org/html/2608.07859#S3.SS0.SSS0.Px3.p1.2)\.
- A\. Immer, M\. Korzepa, and M\. Bauer \(2021\)Improving predictions of Bayesian neural nets via local linearization\.InInternational Conference on Artificial Intelligence and Statistics \(AISTATS\),Cited by:[§3](https://arxiv.org/html/2608.07859#S3.SS0.SSS0.Px3.p1.2)\.
- X\. Jiang, L\. Lim, Y\. Yao, and Y\. Ye \(2011\)Statistical ranking and combinatorial Hodge theory\.Mathematical Programming127\(1\),pp\. 203–244\.Cited by:[§3](https://arxiv.org/html/2608.07859#S3.SS0.SSS0.Px2.p1.2)\.
- J\. Kirkpatrick, R\. Pascanu, N\. Rabinowitz, O\. Vinyals, G\. Desjardins, A\. A\. Rusu, K\. Milan, J\. Quan, T\. Ramalho, A\. Grabska\-Barwinska,et al\.\(2017\)Overcoming catastrophic forgetting in neural networks\.Proceedings of the National Academy of Sciences114,pp\. 3521–3526\.Cited by:[§3](https://arxiv.org/html/2608.07859#S3.SS0.SSS0.Px3.p1.2)\.
- P\. Kündig and F\. Sigrist \(2024\)Iterative methods for Vecchia\-Laplace approximations for latent Gaussian process models\.Journal of the American Statistical Association\.Cited by:[§3](https://arxiv.org/html/2608.07859#S3.SS0.SSS0.Px3.p1.2)\.
- J\. Lin, R\. Astudillo, P\. I\. Frazier, and E\. Bakshy \(2022\)Preference exploration for efficient Bayesian optimization with multiple outcomes\.InInternational Conference on Artificial Intelligence and Statistics \(AISTATS\),Cited by:[§1](https://arxiv.org/html/2608.07859#S1.p1.1),[§1](https://arxiv.org/html/2608.07859#S1.p3.1),[§3](https://arxiv.org/html/2608.07859#S3.SS0.SSS0.Px1.p1.1),[§4](https://arxiv.org/html/2608.07859#S4.SS0.SSS0.Px1.p1.10),[§6\.1](https://arxiv.org/html/2608.07859#S6.SS1.SSS0.Px2.p1.8)\.
- P\. Mikkola, M\. Todorović, J\. Järvi, P\. Rinke, and S\. Kaski \(2020\)Projective preferential Bayesian optimization\.InInternational Conference on Machine Learning \(ICML\),Cited by:[§1](https://arxiv.org/html/2608.07859#S1.p1.1),[§3](https://arxiv.org/html/2608.07859#S3.SS0.SSS0.Px1.p1.1)\.
- C\. E\. Rasmussen and C\. K\. I\. Williams \(2006\)Gaussian processes for machine learning\.MIT Press,Cambridge, MA\.Cited by:[§1](https://arxiv.org/html/2608.07859#S1.p2.4)\.
- N\. B\. Shah, S\. Balakrishnan, J\. K\. Bradley, A\. Parekh, K\. Ramchandran, and M\. J\. Wainwright \(2016\)Estimation from pairwise comparisons: sharp minimax bounds with topology dependence\.Journal of Machine Learning Research17\(58\),pp\. 1–47\.Cited by:[§3](https://arxiv.org/html/2608.07859#S3.SS0.SSS0.Px2.p1.2)\.
- K\. Shao, A\. Chakrabarty, A\. Mesbah, and D\. Romeres \(2025\)Coactive preference\-guided multi\-objective Bayesian optimization: an application to policy learning in personalized plasma medicine\.IEEE Control Systems Letters\.Cited by:[§G\.1](https://arxiv.org/html/2608.07859#A7.SS1.SSS0.Px2.p1.1),[§1](https://arxiv.org/html/2608.07859#S1.p1.1),[§6\.1](https://arxiv.org/html/2608.07859#S6.SS1.SSS0.Px1.p1.1),[§6\.3](https://arxiv.org/html/2608.07859#S6.SS3.SSS0.Px1.p1.6)\.
- S\. Takenoet al\.\(2023\)Towards practical preferential Bayesian optimization with skew Gaussian processes\.InInternational Conference on Machine Learning \(ICML\),Cited by:[§3](https://arxiv.org/html/2608.07859#S3.SS0.SSS0.Px1.p1.1),[§6\.2](https://arxiv.org/html/2608.07859#S6.SS2.p2.6)\.
- M\. Tucker, E\. Novoseller, C\. Kann, Y\. Sui, Y\. Yue, J\. Burdick, and A\. D\. Ames \(2020\)Preference\-based learning for exoskeleton gait optimization\.InInternational Conference on Robotics and Automation \(ICRA\),Cited by:[§1](https://arxiv.org/html/2608.07859#S1.p1.1)\.
- W\. Xu, W\. Wang, Y\. Jiang, B\. Svetozarevic, and C\. N\. Jones \(2024\)Principled preferential Bayesian optimization\.InInternational Conference on Machine Learning \(ICML\),Cited by:[Table 5](https://arxiv.org/html/2608.07859#A10.T5),[Appendix J](https://arxiv.org/html/2608.07859#A10.p1.3),[§1](https://arxiv.org/html/2608.07859#S1.p1.1),[§1](https://arxiv.org/html/2608.07859#S1.p3.1),[§3](https://arxiv.org/html/2608.07859#S3.SS0.SSS0.Px1.p1.1),[Table 1](https://arxiv.org/html/2608.07859#S6.T1),[§6](https://arxiv.org/html/2608.07859#S6.p1.1)\.

## Appendix AProofs

### A\.1Proof of[Section˜4](https://arxiv.org/html/2608.07859#S4)\(HlikH\_\{\\mathrm\{lik\}\}is a Weighted Graph Laplacian\)

###### Proof\.

For comparisonmm, the probit model \([Equation˜2](https://arxiv.org/html/2608.07859#S2.E2)\) givesP​\(xm\+≻xm−\)=Φ​\(sm\)P\(x^\{\+\}\_\{m\}\\succ x^\{\-\}\_\{m\}\)=\\Phi\(s\_\{m\}\)withsm=𝐂m⊤​𝐟/\(σ​2\)s\_\{m\}=\\mathbf\{C\}\_\{m\}^\{\\top\}\\mathbf\{f\}/\(\\sigma\\sqrt\{2\}\), so the log\-likelihood contribution isℒm​\(𝐟\)=log⁡Φ​\(sm\)\\mathcal\{L\}\_\{m\}\(\\mathbf\{f\}\)=\\log\\Phi\(s\_\{m\}\)\. The gradient is

∇𝐟ℒm=1σ​2​ψ​\(sm\)​𝐂m,where​ψ​\(z\)=ϕ​\(z\)Φ​\(z\)\\nabla\_\{\\mathbf\{f\}\}\\mathcal\{L\}\_\{m\}=\\frac\{1\}\{\\sigma\\sqrt\{2\}\}\\psi\(s\_\{m\}\)\\mathbf\{C\}\_\{m\},\\quad\\text\{where \}\\psi\(z\)=\\frac\{\\phi\(z\)\}\{\\Phi\(z\)\}\(14\)is the inverse Mills ratio\. Differentiating again:

∇𝐟2ℒm=−12​σ2​ψ​\(sm\)​\(ψ​\(sm\)\+sm\)​𝐂m​𝐂m⊤=−ωm​𝐂m​𝐂m⊤\.\\nabla^\{2\}\_\{\\mathbf\{f\}\}\\mathcal\{L\}\_\{m\}=\-\\frac\{1\}\{2\\sigma^\{2\}\}\\psi\(s\_\{m\}\)\\bigl\(\\psi\(s\_\{m\}\)\+s\_\{m\}\\bigr\)\\mathbf\{C\}\_\{m\}\\mathbf\{C\}\_\{m\}^\{\\top\}=\-\\omega\_\{m\}\\mathbf\{C\}\_\{m\}\\mathbf\{C\}\_\{m\}^\{\\top\}\.\(15\)*Positivity ofωm\\omega\_\{m\}\.*For all finitesms\_\{m\}, we needψ​\(sm\)​\(ψ​\(sm\)\+sm\)\>0\\psi\(s\_\{m\}\)\(\\psi\(s\_\{m\}\)\+s\_\{m\}\)\>0\. Sinceψ​\(z\)=ϕ​\(z\)/Φ​\(z\)\>0\\psi\(z\)=\\phi\(z\)/\\Phi\(z\)\>0for all finitezz, it suffices to showψ​\(z\)\+z\>0\\psi\(z\)\+z\>0\. This follows from the classical Mills ratio inequality:ψ​\(z\)\>−z\\psi\(z\)\>\-zfor allzz\(equivalently,ϕ​\(z\)/Φ​\(z\)\>−z\\phi\(z\)/\\Phi\(z\)\>\-z, which holds becauseΦ​\(z\)\>0\\Phi\(z\)\>0andϕ​\(z\)\>0\\phi\(z\)\>0, and forz≥0z\\geq 0it is immediate; forz<0z<0, the boundΦ​\(z\)<ϕ​\(z\)/\|z\|\\Phi\(z\)<\\phi\(z\)/\|z\|givesψ​\(z\)\>\|z\|=−z\\psi\(z\)\>\|z\|=\-z\)\.

Summing over allMMcomparisons yieldsHlik=−∇2log⁡p​\(𝒟∣𝐟\)=∑m=1Mωm​𝐂m​𝐂m⊤=𝐂⊤​𝐖𝐂H\_\{\\mathrm\{lik\}\}=\-\\nabla^\{2\}\\log p\(\\mathcal\{D\}\\mid\\mathbf\{f\}\)=\\sum\_\{m=1\}^\{M\}\\omega\_\{m\}\\mathbf\{C\}\_\{m\}\\mathbf\{C\}\_\{m\}^\{\\top\}=\\mathbf\{C\}^\{\\top\}\\mathbf\{W\}\\mathbf\{C\}\.

*Rank\.*Since𝐖\\mathbf\{W\}is positive diagonal \(allωm\>0\\omega\_\{m\}\>0\), we haveker⁡\(𝐂⊤​𝐖𝐂\)=ker⁡\(𝐖1/2​𝐂\)=ker⁡\(𝐂\)\\ker\(\\mathbf\{C\}^\{\\top\}\\mathbf\{W\}\\mathbf\{C\}\)=\\ker\(\\mathbf\{W\}^\{1/2\}\\mathbf\{C\}\)=\\ker\(\\mathbf\{C\}\)\. The kernel of the incidence matrix𝐂\\mathbf\{C\}of a \(multi\)graph onNNvertices withNccN\_\{\\mathrm\{cc\}\}connected components is spanned by theNccN\_\{\\mathrm\{cc\}\}component\-indicator vectors, sorank⁡\(𝐂⊤​𝐖𝐂\)=N−Ncc\\operatorname\{rank\}\(\\mathbf\{C\}^\{\\top\}\\mathbf\{W\}\\mathbf\{C\}\)=N\-N\_\{\\mathrm\{cc\}\}\. ∎

### A\.2Proof of[Section˜4](https://arxiv.org/html/2608.07859#S4)

###### Proof\.

Let𝐐=\[𝐐0​𝐐1\]\\mathbf\{Q\}=\[\\mathbf\{Q\}\_\{0\}\\;\\mathbf\{Q\}\_\{1\}\]be orthogonal with𝐐0\\mathbf\{Q\}\_\{0\}spanningker⁡\(𝐂\)\\operatorname\{ker\}\(\\mathbf\{C\}\)and𝐐1\\mathbf\{Q\}\_\{1\}spanningrange​\(𝐂⊤\)\\mathrm\{range\}\(\\mathbf\{C\}^\{\\top\}\)\. Write𝐟=𝐐0​ξ\+𝐐1​ζ\\mathbf\{f\}=\\mathbf\{Q\}\_\{0\}\\xi\+\\mathbf\{Q\}\_\{1\}\\zeta\.

*\(a\)*Since𝐂𝐐0=𝟎\\mathbf\{C\}\\mathbf\{Q\}\_\{0\}=\\mathbf\{0\}, every comparison score𝐂m⊤​𝐟=𝐂m⊤​𝐐1​ζ\\mathbf\{C\}\_\{m\}^\{\\top\}\\mathbf\{f\}=\\mathbf\{C\}\_\{m\}^\{\\top\}\\mathbf\{Q\}\_\{1\}\\zetadepends only onζ\\zeta\. Hencep​\(𝒟∣ξ,ζ\)=p​\(𝒟∣ζ\)p\(\\mathcal\{D\}\\mid\\xi,\\zeta\)=p\(\\mathcal\{D\}\\mid\\zeta\)\.

*\(b\)*By Bayes’ rule,p​\(ξ,ζ∣𝒟\)∝p​\(𝒟∣ζ\)​p0​\(ξ,ζ\)=p0​\(ξ∣ζ\)​p​\(𝒟∣ζ\)​p0​\(ζ\)p\(\\xi,\\zeta\\mid\\mathcal\{D\}\)\\propto p\(\\mathcal\{D\}\\mid\\zeta\)\\,p\_\{0\}\(\\xi,\\zeta\)=p\_\{0\}\(\\xi\\mid\\zeta\)\\,p\(\\mathcal\{D\}\\mid\\zeta\)\\,p\_\{0\}\(\\zeta\)\. Normalizing givesp​\(ξ,ζ∣𝒟\)=p0​\(ξ∣ζ\)​p​\(ζ∣𝒟\)p\(\\xi,\\zeta\\mid\\mathcal\{D\}\)=p\_\{0\}\(\\xi\\mid\\zeta\)\\,p\(\\zeta\\mid\\mathcal\{D\}\), sop​\(ξ∣ζ,𝒟\)=p0​\(ξ∣ζ\)p\(\\xi\\mid\\zeta,\\mathcal\{D\}\)=p\_\{0\}\(\\xi\\mid\\zeta\)\.

Under the Laplace approximation, write the prior precision in\(ξ,ζ\)\(\\xi,\\zeta\)\-coordinates as𝐐⊤​𝐊−1​𝐐=\[𝐀𝐁𝐁⊤𝐃0\]\\mathbf\{Q\}^\{\\top\}\\mathbf\{K\}^\{\-1\}\\mathbf\{Q\}=\\bigl\[\\begin\{smallmatrix\}\\mathbf\{A\}&\\mathbf\{B\}\\\\ \\mathbf\{B\}^\{\\top\}&\\mathbf\{D\}\_\{0\}\\end\{smallmatrix\}\\bigr\]\. The likelihood Hessian contributes only to theζ\\zeta\-block:𝐐⊤​𝐇𝐐=\[𝐀𝐁𝐁⊤𝐃0\+𝐋\]\\mathbf\{Q\}^\{\\top\}\\mathbf\{H\}\\mathbf\{Q\}=\\bigl\[\\begin\{smallmatrix\}\\mathbf\{A\}&\\mathbf\{B\}\\\\ \\mathbf\{B\}^\{\\top\}&\\mathbf\{D\}\_\{0\}\+\\mathbf\{L\}\\end\{smallmatrix\}\\bigr\]with𝐋=𝐐1⊤​Hlik​𝐐1⪰0\\mathbf\{L\}=\\mathbf\{Q\}\_\{1\}^\{\\top\}H\_\{\\mathrm\{lik\}\}\\mathbf\{Q\}\_\{1\}\\succeq 0\. The MAP satisfies the first\-order condition𝐀​ξ^\+𝐁​ζ^=𝟎\\mathbf\{A\}\\hat\{\\xi\}\+\\mathbf\{B\}\\hat\{\\zeta\}=\\mathbf\{0\}\(since the likelihood does not depend onξ\\xi\)\. The Gaussian conditional onξ\\xigivenζ\\zetatherefore has meanξ^−𝐀−1​𝐁​\(ζ−ζ^\)=−𝐀−1​𝐁​ζ\\hat\{\\xi\}\-\\mathbf\{A\}^\{\-1\}\\mathbf\{B\}\(\\zeta\-\\hat\{\\zeta\}\)=\-\\mathbf\{A\}^\{\-1\}\\mathbf\{B\}\\zetaand covariance𝐀−1\\mathbf\{A\}^\{\-1\}, matching the prior conditionalp0​\(ξ∣ζ\)p\_\{0\}\(\\xi\\mid\\zeta\)\.

If𝐁=𝟎\\mathbf\{B\}=\\mathbf\{0\}\(block\-diagonal prior\), thenp0​\(ξ∣ζ\)=p0​\(ξ\)p\_\{0\}\(\\xi\\mid\\zeta\)=p\_\{0\}\(\\xi\), sopL​\(ξ∣𝒟\)=p0​\(ξ\)p\_\{L\}\(\\xi\\mid\\mathcal\{D\}\)=p\_\{0\}\(\\xi\)and the null\-space covariance is unchanged\. ∎

### A\.3Rank Invariance under MAP Shift

###### Proposition 10\(Rank invariance\)\.

For every finite𝐟\\mathbf\{f\},ker⁡\(Hlik​\(𝐟\)\)=ker⁡\(𝐂\)\\operatorname\{ker\}\(H\_\{\\mathrm\{lik\}\}\(\\mathbf\{f\}\)\)=\\operatorname\{ker\}\(\\mathbf\{C\}\)andrank⁡\(Hlik​\(𝐟\)\)=N−Ncc\\operatorname\{rank\}\(H\_\{\\mathrm\{lik\}\}\(\\mathbf\{f\}\)\)=N\-N\_\{\\mathrm\{cc\}\}, since𝐖​\(𝐟\)≻0\\mathbf\{W\}\(\\mathbf\{f\}\)\\succ 0\.

###### Proof\.

By[Section˜4](https://arxiv.org/html/2608.07859#S4),Hlik​\(𝐟\)=𝐂⊤​𝐖​\(𝐟\)​𝐂H\_\{\\mathrm\{lik\}\}\(\\mathbf\{f\}\)=\\mathbf\{C\}^\{\\top\}\\mathbf\{W\}\(\\mathbf\{f\}\)\\mathbf\{C\}with𝐖​\(𝐟\)≻0\\mathbf\{W\}\(\\mathbf\{f\}\)\\succ 0\. Thenv⊤​Hlik​\(𝐟\)​v=‖𝐖​\(𝐟\)1/2​𝐂​v‖2v^\{\\top\}H\_\{\\mathrm\{lik\}\}\(\\mathbf\{f\}\)v=\\\|\\mathbf\{W\}\(\\mathbf\{f\}\)^\{1/2\}\\mathbf\{C\}v\\\|^\{2\}, sov∈ker⁡\(Hlik​\(𝐟\)\)v\\in\\operatorname\{ker\}\(H\_\{\\mathrm\{lik\}\}\(\\mathbf\{f\}\)\)iff𝐂​v=0\\mathbf\{C\}v=0\. Henceker⁡\(Hlik​\(𝐟\)\)=ker⁡\(𝐂\)\\operatorname\{ker\}\(H\_\{\\mathrm\{lik\}\}\(\\mathbf\{f\}\)\)=\\operatorname\{ker\}\(\\mathbf\{C\}\)for all finite𝐟\\mathbf\{f\}, andrank⁡\(Hlik​\(𝐟\)\)=N−Ncc\\operatorname\{rank\}\(H\_\{\\mathrm\{lik\}\}\(\\mathbf\{f\}\)\)=N\-N\_\{\\mathrm\{cc\}\}by rank\-nullity\. ∎

### A\.4Proof of[Section˜5\.1](https://arxiv.org/html/2608.07859#S5.SS1)\(Correction Properties\)

###### Proof\.

Letai=\(𝐊−1\)i​i\>0a\_\{i\}=\(\\mathbf\{K\}^\{\-1\}\)\_\{ii\}\>0andri​\(η\)=η2/\(η\+ai\)r\_\{i\}\(\\eta\)=\\eta^\{2\}/\(\\eta\+a\_\{i\}\)forη\>0\\eta\>0\.

*\(i\) Positivity\.*η\>0\\eta\>0andη\+ai\>0\\eta\+a\_\{i\}\>0immediately giveri\>0r\_\{i\}\>0\.

*\(ii\) Monotonicity inη\\eta\.*∂ri∂η=η​\(η\+2​ai\)\(η\+ai\)2\\frac\{\\partial r\_\{i\}\}\{\\partial\\eta\}=\\frac\{\\eta\(\\eta\+2a\_\{i\}\)\}\{\(\\eta\+a\_\{i\}\)^\{2\}\}\. The numerator is positive \(both factors positive forη\>0\\eta\>0,ai\>0a\_\{i\}\>0\), and the denominator is positive\.

*\(iii\) Decreasing inaia\_\{i\}\.*∂ri∂ai=−η2\(η\+ai\)2<0\\frac\{\\partial r\_\{i\}\}\{\\partial a\_\{i\}\}=\-\\frac\{\\eta^\{2\}\}\{\(\\eta\+a\_\{i\}\)^\{2\}\}<0\.

*\(iv\) Bounded\.*ri=η−η​aiη\+ai<ηr\_\{i\}=\\eta\-\\frac\{\\eta a\_\{i\}\}\{\\eta\+a\_\{i\}\}<\\etasinceη​aiη\+ai\>0\\frac\{\\eta a\_\{i\}\}\{\\eta\+a\_\{i\}\}\>0\.

*\(v\)–\(vi\) Limits\.*Asai→0a\_\{i\}\\to 0:ri/η=η/\(η\+ai\)→1r\_\{i\}/\\eta=\\eta/\(\\eta\+a\_\{i\}\)\\to 1\. Asai→∞a\_\{i\}\\to\\infty:ri/η=η/\(η\+ai\)→0r\_\{i\}/\\eta=\\eta/\(\\eta\+a\_\{i\}\)\\to 0\.

*Variational form\.*The objectiveq​\(r\)=ai2​r2\+η2​\(r−η\)2q\(r\)=\\frac\{a\_\{i\}\}\{2\}r^\{2\}\+\\frac\{\\eta\}\{2\}\(r\-\\eta\)^\{2\}is strictly convex withq′′​\(r\)=ai\+η\>0q^\{\\prime\\prime\}\(r\)=a\_\{i\}\+\\eta\>0\. Settingq′​\(r\)=\(ai\+η\)​r−η2=0q^\{\\prime\}\(r\)=\(a\_\{i\}\+\\eta\)r\-\\eta^\{2\}=0givesr∗=η2/\(η\+ai\)=rir^\{\*\}=\\eta^\{2\}/\(\\eta\+a\_\{i\}\)=r\_\{i\}\. ∎

### A\.5Proof of[Section˜5\.1](https://arxiv.org/html/2608.07859#S5.SS1)\(κ\\kappa\-Calibration is Well\-Posed\)

###### Proof\.

*Continuity and PSD\.*Eachri​\(η\)r\_\{i\}\(\\eta\)is a continuous, non\-negative function ofη≥0\\eta\\geq 0\(withri​\(0\)=0r\_\{i\}\(0\)=0\), so𝐑​\(η\)=diag⁡\(r1,…,rN\)\\mathbf\{R\}\(\\eta\)=\\operatorname\{diag\}\(r\_\{1\},\\ldots,r\_\{N\}\)is continuous and PSD\.

*Loewner monotonicity\.*Forη′\>η≥0\\eta^\{\\prime\}\>\\eta\\geq 0: eachri​\(η′\)\>ri​\(η\)r\_\{i\}\(\\eta^\{\\prime\}\)\>r\_\{i\}\(\\eta\)by property \(ii\), so𝐑​\(η′\)−𝐑​\(η\)\\mathbf\{R\}\(\\eta^\{\\prime\}\)\-\\mathbf\{R\}\(\\eta\)is a positive diagonal matrix, hence𝐑​\(η′\)≻𝐑​\(η\)\\mathbf\{R\}\(\\eta^\{\\prime\}\)\\succ\\mathbf\{R\}\(\\eta\)in the Loewner order\.

*Limiting behavior\.*Asη→∞\\eta\\to\\infty,ri​\(η\)/η→1r\_\{i\}\(\\eta\)/\\eta\\to 1for allii, so𝐑​\(η\)≈η​𝐈\\mathbf\{R\}\(\\eta\)\\approx\\eta\\mathbf\{I\}for largeη\\eta\. Since𝐇\\mathbf\{H\}and𝐑​\(η\)\\mathbf\{R\}\(\\eta\)are both symmetric but do not commute in general, we boundκ​\(𝐇\+𝐑​\(η\)\)\\kappa\(\\mathbf\{H\}\+\\mathbf\{R\}\(\\eta\)\)via Weyl’s inequalities\. By Weyl’s inequality for eigenvalue sums of Hermitian matrices:

λmax​\(𝐇\+𝐑\)\\displaystyle\\lambda\_\{\\max\}\(\\mathbf\{H\}\+\\mathbf\{R\}\)≤λmax​\(𝐇\)\+λmax​\(𝐑\)≤λmax​\(𝐇\)\+η,\\displaystyle\\leq\\lambda\_\{\\max\}\(\\mathbf\{H\}\)\+\\lambda\_\{\\max\}\(\\mathbf\{R\}\)\\leq\\lambda\_\{\\max\}\(\\mathbf\{H\}\)\+\\eta,\(16\)λmin​\(𝐇\+𝐑\)\\displaystyle\\lambda\_\{\\min\}\(\\mathbf\{H\}\+\\mathbf\{R\}\)≥λmin​\(𝐇\)\+λmin​\(𝐑\)=λmin​\(𝐇\)\+mini⁡ri​\(η\),\\displaystyle\\geq\\lambda\_\{\\min\}\(\\mathbf\{H\}\)\+\\lambda\_\{\\min\}\(\\mathbf\{R\}\)=\\lambda\_\{\\min\}\(\\mathbf\{H\}\)\+\\min\_\{i\}r\_\{i\}\(\\eta\),\(17\)where the second line uses that𝐑\\mathbf\{R\}is diagonal with eigenvaluesri​\(η\)r\_\{i\}\(\\eta\)\. Sinceri​\(η\)=η2/\(η\+ai\)=η​\(1−ai/\(η\+ai\)\)r\_\{i\}\(\\eta\)=\\eta^\{2\}/\(\\eta\+a\_\{i\}\)=\\eta\(1\-a\_\{i\}/\(\\eta\+a\_\{i\}\)\), we havemini⁡ri​\(η\)=η​\(1−amax/\(η\+amax\)\)\\min\_\{i\}r\_\{i\}\(\\eta\)=\\eta\(1\-a\_\{\\max\}/\(\\eta\+a\_\{\\max\}\)\)whereamax=maxi⁡aia\_\{\\max\}=\\max\_\{i\}a\_\{i\}\. Asη→∞\\eta\\to\\infty,mini⁡ri​\(η\)/η→1\\min\_\{i\}r\_\{i\}\(\\eta\)/\\eta\\to 1\. Therefore:

κ​\(𝐇\+𝐑​\(η\)\)≤λmax​\(𝐇\)\+ηλmin​\(𝐇\)\+η​\(1−amax/\(η\+amax\)\)→1as​η→∞\.\\kappa\(\\mathbf\{H\}\+\\mathbf\{R\}\(\\eta\)\)\\leq\\frac\{\\lambda\_\{\\max\}\(\\mathbf\{H\}\)\+\\eta\}\{\\lambda\_\{\\min\}\(\\mathbf\{H\}\)\+\\eta\(1\-a\_\{\\max\}/\(\\eta\+a\_\{\\max\}\)\)\}\\to 1\\quad\\text\{as \}\\eta\\to\\infty\.\(18\)
*Existence ofη∗\\eta^\{\*\}\.*Ifκ​\(𝐇\)=1\\kappa\(\\mathbf\{H\}\)=1, the targetκ​\(𝐇\)1−α=1\\kappa\(\\mathbf\{H\}\)^\{1\-\\alpha\}=1is already met atη∗=0\\eta^\{\*\}=0\. Otherwise, the functiong​\(η\)=κ​\(𝐇\+𝐑​\(η\)\)g\(\\eta\)=\\kappa\(\\mathbf\{H\}\+\\mathbf\{R\}\(\\eta\)\)is continuous,g​\(0\)=κ​\(𝐇\)\>1g\(0\)=\\kappa\(\\mathbf\{H\}\)\>1, andg​\(η\)→1<κ​\(𝐇\)1−αg\(\\eta\)\\to 1<\\kappa\(\\mathbf\{H\}\)^\{1\-\\alpha\}forα∈\(0,1\)\\alpha\\in\(0,1\)\. By the intermediate value theorem,\{η≥0:g​\(η\)≤κ​\(𝐇\)1−α\}\\\{\\eta\\geq 0:g\(\\eta\)\\leq\\kappa\(\\mathbf\{H\}\)^\{1\-\\alpha\}\\\}is nonempty\. As a preimage of a closed set under a continuous function, it is closed; its intersection with\[0,M\]\[0,M\]for sufficiently largeMMis compact, yielding the minimumη∗\\eta^\{\*\}\.

∎

### A\.6Proof of[Section˜5\.1](https://arxiv.org/html/2608.07859#S5.SS1.SSS0.Px1)\(Controlled MAP Shift\)

###### Proof\.

Let𝐟^0\\hat\{\\mathbf\{f\}\}\_\{0\}satisfy∇J0​\(𝐟^0\)=0\\nabla J\_\{0\}\(\\hat\{\\mathbf\{f\}\}\_\{0\}\)=0\(baseline MAP\) and𝐟^η\\hat\{\\mathbf\{f\}\}\_\{\\eta\}satisfy∇J0​\(𝐟^η\)\+𝐑​𝐟^η=0\\nabla J\_\{0\}\(\\hat\{\\mathbf\{f\}\}\_\{\\eta\}\)\+\\mathbf\{R\}\\hat\{\\mathbf\{f\}\}\_\{\\eta\}=0\(augmented MAP\)\. DefineΔ=𝐟^η−𝐟^0\\Delta=\\hat\{\\mathbf\{f\}\}\_\{\\eta\}\-\\hat\{\\mathbf\{f\}\}\_\{0\}\.

By the fundamental theorem of calculus:

∇J0​\(𝐟^η\)−∇J0​\(𝐟^0\)=\(∫01∇2J0​\(𝐟^0\+t​Δ\)​𝑑t\)​Δ=𝐇¯​Δ\.\\nabla J\_\{0\}\(\\hat\{\\mathbf\{f\}\}\_\{\\eta\}\)\-\\nabla J\_\{0\}\(\\hat\{\\mathbf\{f\}\}\_\{0\}\)=\\left\(\\int\_\{0\}^\{1\}\\nabla^\{2\}J\_\{0\}\(\\hat\{\\mathbf\{f\}\}\_\{0\}\+t\\Delta\)\\,dt\\right\)\\Delta=\\bar\{\\mathbf\{H\}\}\\Delta\.\(19\)From the augmented optimality:∇J0​\(𝐟^η\)=−𝐑​𝐟^η=−𝐑​𝐟^0−𝐑​Δ\\nabla J\_\{0\}\(\\hat\{\\mathbf\{f\}\}\_\{\\eta\}\)=\-\\mathbf\{R\}\\hat\{\\mathbf\{f\}\}\_\{\\eta\}=\-\\mathbf\{R\}\\hat\{\\mathbf\{f\}\}\_\{0\}\-\\mathbf\{R\}\\Delta\. Substituting:

𝐇¯​Δ=−𝐑​𝐟^0−𝐑​Δ⟹\(𝐇¯\+𝐑\)​Δ=−𝐑​𝐟^0\.\\bar\{\\mathbf\{H\}\}\\Delta=\-\\mathbf\{R\}\\hat\{\\mathbf\{f\}\}\_\{0\}\-\\mathbf\{R\}\\Delta\\implies\(\\bar\{\\mathbf\{H\}\}\+\\mathbf\{R\}\)\\Delta=\-\\mathbf\{R\}\\hat\{\\mathbf\{f\}\}\_\{0\}\.\(20\)Since𝐇¯⪰𝐊−1≻0\\bar\{\\mathbf\{H\}\}\\succeq\\mathbf\{K\}^\{\-1\}\\succ 0and𝐑⪰0\\mathbf\{R\}\\succeq 0, the matrix𝐇¯\+𝐑\\bar\{\\mathbf\{H\}\}\+\\mathbf\{R\}is invertible\. Setting𝐌=𝐇¯−1/2​𝐑​𝐇¯−1/2\\mathbf\{M\}=\\bar\{\\mathbf\{H\}\}^\{\-1/2\}\\mathbf\{R\}\\bar\{\\mathbf\{H\}\}^\{\-1/2\}:

𝐇¯1/2​Δ=−\(𝐈\+𝐌\)−1​𝐌​𝐇¯1/2​\(𝐟^0\)\.\\bar\{\\mathbf\{H\}\}^\{1/2\}\\Delta=\-\(\\mathbf\{I\}\+\\mathbf\{M\}\)^\{\-1\}\\mathbf\{M\}\\bar\{\\mathbf\{H\}\}^\{1/2\}\(\\hat\{\\mathbf\{f\}\}\_\{0\}\)\.\(21\)Taking norms:‖Δ‖𝐇¯=‖𝐇¯1/2​Δ‖≤‖\(𝐈\+𝐌\)−1​𝐌‖⋅‖𝐟^0‖𝐇¯\\left\\\|\\Delta\\right\\\|\_\{\\bar\{\\mathbf\{H\}\}\}=\\\|\\bar\{\\mathbf\{H\}\}^\{1/2\}\\Delta\\\|\\leq\\\|\(\\mathbf\{I\}\+\\mathbf\{M\}\)^\{\-1\}\\mathbf\{M\}\\\|\\cdot\\left\\\|\\hat\{\\mathbf\{f\}\}\_\{0\}\\right\\\|\_\{\\bar\{\\mathbf\{H\}\}\}\. Since𝐌⪰0\\mathbf\{M\}\\succeq 0with largest eigenvalueμmax\\mu\_\{\\max\}, the operator norm‖\(𝐈\+𝐌\)−1​𝐌‖=μmax/\(1\+μmax\)\\\|\(\\mathbf\{I\}\+\\mathbf\{M\}\)^\{\-1\}\\mathbf\{M\}\\\|=\\mu\_\{\\max\}/\(1\+\\mu\_\{\\max\}\)\. ∎

### A\.7Proof of[Section˜5\.1](https://arxiv.org/html/2608.07859#S5.SS1.SSS0.Px2)\(Full Augmentation Contracts EUBO\)

###### Proof\.

Both posteriors share the MAP𝐟^η\\hat\{\\mathbf\{f\}\}\_\{\\eta\}, so predictive means coincide:δa​b=ca​b⊤​𝐟^η\\delta\_\{ab\}=c\_\{ab\}^\{\\top\}\\hat\{\\mathbf\{f\}\}\_\{\\eta\}for contrastca​b=ea−ebc\_\{ab\}=e\_\{a\}\-e\_\{b\}\.

*Variance ordering\.*Since𝐑⪰0\\mathbf\{R\}\\succeq 0,𝐇η\+𝐑⪰𝐇η\\mathbf\{H\}\_\{\\eta\}\+\\mathbf\{R\}\\succeq\\mathbf\{H\}\_\{\\eta\}, so\(𝐇η\+𝐑\)−1⪯𝐇η−1\(\\mathbf\{H\}\_\{\\eta\}\+\\mathbf\{R\}\)^\{\-1\}\\preceq\\mathbf\{H\}\_\{\\eta\}^\{\-1\}\(inversion reverses Loewner order on the PD cone\)\. Thereforesaug2​\(a​b\)=ca​b⊤​\(𝐇η\+𝐑\)−1​ca​b≤ca​b⊤​𝐇η−1​ca​b=sMO2​\(a​b\)s\_\{\\mathrm\{aug\}\}^\{2\}\(ab\)=c\_\{ab\}^\{\\top\}\(\\mathbf\{H\}\_\{\\eta\}\+\\mathbf\{R\}\)^\{\-1\}c\_\{ab\}\\leq c\_\{ab\}^\{\\top\}\\mathbf\{H\}\_\{\\eta\}^\{\-1\}c\_\{ab\}=s\_\{\\mathrm\{MO\}\}^\{2\}\(ab\)\.

*EUBO monotonicity\.*Forq=2q\{=\}2EUBO withEUBO​\(δ,s\)=δ​Φ​\(δ/s\)\+s​ϕ​\(δ/s\)\\mathrm\{EUBO\}\(\\delta,s\)=\\delta\\Phi\(\\delta/s\)\+s\\phi\(\\delta/s\)\([Equation˜6](https://arxiv.org/html/2608.07859#S4.E6)\), differentiate at fixedδ\\delta:∂EUBO/∂s=ϕ​\(δ/s\)\>0\\partial\\,\\mathrm\{EUBO\}/\\partial s=\\phi\(\\delta/s\)\>0fors\>0s\>0\. \(Thez2​ϕ​\(z\)z^\{2\}\\phi\(z\)terms from the chain rule cancel exactly\.\) HencesMO≥saugs\_\{\\mathrm\{MO\}\}\\geq s\_\{\\mathrm\{aug\}\}impliesEUBOMO≥EUBOaug\\mathrm\{EUBO\}\_\{\\mathrm\{MO\}\}\\geq\\mathrm\{EUBO\}\_\{\\mathrm\{aug\}\}\.

*Distortion bound\.*By the mean value theorem,EUBOMO−EUBOaug=ϕ​\(δ/s~\)​\(sMO−saug\)\\mathrm\{EUBO\}\_\{\\mathrm\{MO\}\}\-\\mathrm\{EUBO\}\_\{\\mathrm\{aug\}\}=\\phi\(\\delta/\\tilde\{s\}\)\(s\_\{\\mathrm\{MO\}\}\-s\_\{\\mathrm\{aug\}\}\)for somes~∈\[saug,sMO\]\\tilde\{s\}\\in\[s\_\{\\mathrm\{aug\}\},s\_\{\\mathrm\{MO\}\}\]\. Sinceϕ≤1/2​π\\phi\\leq 1/\\sqrt\{2\\pi\}, we getEUBOMO−EUBOaug≤\(sMO−saug\)/2​π\\mathrm\{EUBO\}\_\{\\mathrm\{MO\}\}\-\\mathrm\{EUBO\}\_\{\\mathrm\{aug\}\}\\leq\(s\_\{\\mathrm\{MO\}\}\-s\_\{\\mathrm\{aug\}\}\)/\\sqrt\{2\\pi\}\.

*Spectral control\.*Let𝐌=𝐇η−1/2​𝐑𝐇η−1/2\\mathbf\{M\}=\\mathbf\{H\}\_\{\\eta\}^\{\-1/2\}\\mathbf\{R\}\\mathbf\{H\}\_\{\\eta\}^\{\-1/2\}with eigenvaluesλi\\lambda\_\{i\}\. ThensMO2/saug2≤1\+λmax​\(𝐌\)s\_\{\\mathrm\{MO\}\}^\{2\}/s\_\{\\mathrm\{aug\}\}^\{2\}\\leq 1\+\\lambda\_\{\\max\}\(\\mathbf\{M\}\), so the distortion is controlled by the spectrum of𝐇η−1/2​𝐑𝐇η−1/2\\mathbf\{H\}\_\{\\eta\}^\{\-1/2\}\\mathbf\{R\}\\mathbf\{H\}\_\{\\eta\}^\{\-1/2\}\.

*Extension to fresh query points\.*Letxa,xb∈𝒳x\_\{a\},x\_\{b\}\\in\\mathcal\{X\}be arbitrary query points \(possiblyxa,xb∉Xx\_\{a\},x\_\{b\}\\notin X\), and definera​b:=k​\(X,xa\)−k​\(X,xb\)∈ℝNr\_\{ab\}:=k\(X,x\_\{a\}\)\-k\(X,x\_\{b\}\)\\in\\mathbb\{R\}^\{N\}andνa​b:=k​\(xa,xa\)\+k​\(xb,xb\)−2​k​\(xa,xb\)−ra​b⊤​𝐊−1​ra​b≥0\\nu\_\{ab\}:=k\(x\_\{a\},x\_\{a\}\)\+k\(x\_\{b\},x\_\{b\}\)\-2k\(x\_\{a\},x\_\{b\}\)\-r\_\{ab\}^\{\\top\}\\mathbf\{K\}^\{\-1\}r\_\{ab\}\\geq 0\(nonnegative by the Schur complement of the joint GP prior\)\. Under a Laplace posterior𝒩​\(𝐟^η,Σ\)\\mathcal\{N\}\(\\hat\{\\mathbf\{f\}\}\_\{\\eta\},\\Sigma\)on the training latents, the GP conditional givesf​\(xa\)−f​\(xb\)∣𝐟∼𝒩​\(ra​b⊤​𝐊−1​𝐟,νa​b\)f\(x\_\{a\}\)\-f\(x\_\{b\}\)\\mid\\mathbf\{f\}\\sim\\mathcal\{N\}\(r\_\{ab\}^\{\\top\}\\mathbf\{K\}^\{\-1\}\\mathbf\{f\},\\nu\_\{ab\}\), so by total expectation and variance:

δa​b=ra​b⊤​𝐊−1​𝐟^η,sΣ2​\(a​b\)=νa​b\+ra​b⊤​𝐊−1​Σ​𝐊−1​ra​b\.\\delta\_\{ab\}=r\_\{ab\}^\{\\top\}\\mathbf\{K\}^\{\-1\}\\hat\{\\mathbf\{f\}\}\_\{\\eta\},\\quad s\_\{\\Sigma\}^\{2\}\(ab\)=\\nu\_\{ab\}\+r\_\{ab\}^\{\\top\}\\mathbf\{K\}^\{\-1\}\\Sigma\\,\\mathbf\{K\}^\{\-1\}r\_\{ab\}\.\(22\)For MAP\-only,ΣMO=𝐇η−1\\Sigma\_\{\\mathrm\{MO\}\}=\\mathbf\{H\}\_\{\\eta\}^\{\-1\}; for full augmentation,Σaug=\(𝐇η\+𝐑\)−1\\Sigma\_\{\\mathrm\{aug\}\}=\(\\mathbf\{H\}\_\{\\eta\}\+\\mathbf\{R\}\)^\{\-1\}\. Since\(𝐇η\+𝐑\)−1⪯𝐇η−1\(\\mathbf\{H\}\_\{\\eta\}\+\\mathbf\{R\}\)^\{\-1\}\\preceq\\mathbf\{H\}\_\{\\eta\}^\{\-1\}and congruence preserves Loewner order,ra​b⊤​𝐊−1​\(𝐇η\+𝐑\)−1​𝐊−1​ra​b≤ra​b⊤​𝐊−1​𝐇η−1​𝐊−1​ra​br\_\{ab\}^\{\\top\}\\mathbf\{K\}^\{\-1\}\(\\mathbf\{H\}\_\{\\eta\}\+\\mathbf\{R\}\)^\{\-1\}\\mathbf\{K\}^\{\-1\}r\_\{ab\}\\leq r\_\{ab\}^\{\\top\}\\mathbf\{K\}^\{\-1\}\\mathbf\{H\}\_\{\\eta\}^\{\-1\}\\mathbf\{K\}^\{\-1\}r\_\{ab\}, givingsaug2​\(a​b\)≤sMO2​\(a​b\)s\_\{\\mathrm\{aug\}\}^\{2\}\(ab\)\\leq s\_\{\\mathrm\{MO\}\}^\{2\}\(ab\)\. The meanδa​b\\delta\_\{ab\}is identical \(shared MAP\)\. EUBO monotonicity then givesEUBOaug​\(a,b\)≤EUBOMO​\(a,b\)\\mathrm\{EUBO\}\_\{\\mathrm\{aug\}\}\(a,b\)\\leq\\mathrm\{EUBO\}\_\{\\mathrm\{MO\}\}\(a,b\)for all pairs, including fresh query points\. Whenxa,xb∈Xx\_\{a\},x\_\{b\}\\in X,ra​b=𝐊​\(ea−eb\)r\_\{ab\}=\\mathbf\{K\}\(e\_\{a\}\-e\_\{b\}\)andνa​b=0\\nu\_\{ab\}=0, recovering the in\-sample case\. ∎

### A\.8Proof of[Theorem˜7](https://arxiv.org/html/2608.07859#Thmtheorem7)\(Pseudo\-Confidence in Null Directions\)

###### Proof\.

In\(ξ,ζ\)\(\\xi,\\zeta\)\-coordinates, the MAP\-only precision is𝐐⊤​𝐇η​𝐐=\[𝐀𝐁𝐁⊤𝐃η\]\\mathbf\{Q\}^\{\\top\}\\mathbf\{H\}\_\{\\eta\}\\mathbf\{Q\}=\\bigl\[\\begin\{smallmatrix\}\\mathbf\{A\}&\\mathbf\{B\}\\\\ \\mathbf\{B\}^\{\\top\}&\\mathbf\{D\}\_\{\\eta\}\\end\{smallmatrix\}\\bigr\]\(with𝐀=𝐐0⊤​𝐊−1​𝐐0\\mathbf\{A\}=\\mathbf\{Q\}\_\{0\}^\{\\top\}\\mathbf\{K\}^\{\-1\}\\mathbf\{Q\}\_\{0\}, since𝐐0⊤​Hlik​𝐐0=𝟎\\mathbf\{Q\}\_\{0\}^\{\\top\}H\_\{\\mathrm\{lik\}\}\\mathbf\{Q\}\_\{0\}=\\mathbf\{0\}\), and the augmented precision adds𝐐⊤​𝐑𝐐=\[𝐑00𝐑01𝐑01⊤𝐑11\]\\mathbf\{Q\}^\{\\top\}\\mathbf\{R\}\\mathbf\{Q\}=\\bigl\[\\begin\{smallmatrix\}\\mathbf\{R\}\_\{00\}&\\mathbf\{R\}\_\{01\}\\\\ \\mathbf\{R\}\_\{01\}^\{\\top\}&\\mathbf\{R\}\_\{11\}\\end\{smallmatrix\}\\bigr\]\. The Gaussian conditional covariance ofξ\\xigivenζ\\zetaequals the inverse of the\(ξ,ξ\)\(\\xi,\\xi\)\-block of the precision\. For MAP\-only this is𝐀−1\\mathbf\{A\}^\{\-1\}; for full augmentation it is\(𝐀\+𝐑00\)−1\(\\mathbf\{A\}\+\\mathbf\{R\}\_\{00\}\)^\{\-1\}\. Since𝐑≻0\\mathbf\{R\}\\succ 0and𝐐0\\mathbf\{Q\}\_\{0\}has full column rank,𝐑00=𝐐0⊤​𝐑𝐐0≻0\\mathbf\{R\}\_\{00\}=\\mathbf\{Q\}\_\{0\}^\{\\top\}\\mathbf\{R\}\\mathbf\{Q\}\_\{0\}\\succ 0, so\(𝐀\+𝐑00\)−1≺𝐀−1\(\\mathbf\{A\}\+\\mathbf\{R\}\_\{00\}\)^\{\-1\}\\prec\\mathbf\{A\}^\{\-1\}\. ∎

### A\.9Proof of[Theorem˜9](https://arxiv.org/html/2608.07859#Thmtheorem9)\(Argmax Stability\)

###### Proof\.

Let\(aaug∗,baug∗\)\(a^\{\*\}\_\{\\mathrm\{aug\}\},b^\{\*\}\_\{\\mathrm\{aug\}\}\)maximizeEUBOaug\\mathrm\{EUBO\}\_\{\\mathrm\{aug\}\}\. Telescoping givesEUBOMO​\(aMO∗,bMO∗\)−EUBOMO​\(aaug∗,baug∗\)≤2​supa,b\|EUBOMO​\(a,b\)−EUBOaug​\(a,b\)\|\\mathrm\{EUBO\}\_\{\\mathrm\{MO\}\}\(a^\{\*\}\_\{\\mathrm\{MO\}\},b^\{\*\}\_\{\\mathrm\{MO\}\}\)\-\\mathrm\{EUBO\}\_\{\\mathrm\{MO\}\}\(a^\{\*\}\_\{\\mathrm\{aug\}\},b^\{\*\}\_\{\\mathrm\{aug\}\}\)\\leq 2\\sup\_\{a,b\}\|\\mathrm\{EUBO\}\_\{\\mathrm\{MO\}\}\(a,b\)\-\\mathrm\{EUBO\}\_\{\\mathrm\{aug\}\}\(a,b\)\|\. By the mean value theorem and∂EUBO/∂s=ϕ​\(δ/s\)≤1/2​π\\partial\\,\\mathrm\{EUBO\}/\\partial s=\\phi\(\\delta/s\)\\leq 1/\\sqrt\{2\\pi\}, each pointwise gap is at most\(sMO−saug\)/2​π\(s\_\{\\mathrm\{MO\}\}\-s\_\{\\mathrm\{aug\}\}\)/\\sqrt\{2\\pi\}\. For each pair\(a,b\)\(a,b\), letba​bb\_\{ab\}denote the contrast vector such thatsMO2​\(a,b\)=νa​b\+ba​b⊤​𝐇η−1​ba​bs\_\{\\mathrm\{MO\}\}^\{2\}\(a,b\)=\\nu\_\{ab\}\+b\_\{ab\}^\{\\top\}\\mathbf\{H\}\_\{\\eta\}^\{\-1\}b\_\{ab\}\(withνa​b≥0\\nu\_\{ab\}\\geq 0the Schur\-complement term from[Section˜5\.1](https://arxiv.org/html/2608.07859#S5.SS1.SSS0.Px2)\)\. Thensaug2≥sMO2/\(1\+λ1\)s\_\{\\mathrm\{aug\}\}^\{2\}\\geq s\_\{\\mathrm\{MO\}\}^\{2\}/\(1\+\\lambda\_\{1\}\), sosMO−saug≤sMO​λ1/2s\_\{\\mathrm\{MO\}\}\-s\_\{\\mathrm\{aug\}\}\\leq s\_\{\\mathrm\{MO\}\}\\lambda\_\{1\}/2\. Combining: the gap is at mostsupa,bsMO​\(a,b\)​λ1/2​π\\sup\_\{a,b\}s\_\{\\mathrm\{MO\}\}\(a,b\)\\lambda\_\{1\}/\\sqrt\{2\\pi\}\. The supremum is finite when the kernelkkis continuous and𝒳\\mathcal\{X\}is compact: by the Cauchy–Schwarz inequality for positive\-definite kernels,\|k​\(x,y\)\|≤k​\(x,x\)​k​\(y,y\)\|k\(x,y\)\|\\leq\\sqrt\{k\(x,x\)k\(y,y\)\}, sosMO2​\(a,b\)≤4​supxk​\(x,x\)s\_\{\\mathrm\{MO\}\}^\{2\}\(a,b\)\\leq 4\\sup\_\{x\}k\(x,x\)for all\(a,b\)\(a,b\)\. Sinceλ1≤‖𝐑‖/λmin​\(𝐇η\)<η/λmin​\(𝐇η\)\\lambda\_\{1\}\\leq\\\|\\mathbf\{R\}\\\|/\\lambda\_\{\\min\}\(\\mathbf\{H\}\_\{\\eta\}\)<\\eta/\\lambda\_\{\\min\}\(\\mathbf\{H\}\_\{\\eta\}\), the gap isO​\(η/λmin​\(𝐇η\)\)O\(\\eta/\\lambda\_\{\\min\}\(\\mathbf\{H\}\_\{\\eta\}\)\)\. ∎

### A\.10Frozen\-Utility Monotonicity

###### Proposition 12\(Frozen\-utility monotonicity\)\.

Fix latent utilities𝐟∈ℝN\\mathbf\{f\}\\in\\mathbb\{R\}^\{N\}\. LetHlik​\(𝐟\)=∑m=1Mωm​\(𝐟\)​𝐂m​𝐂m⊤H\_\{\\mathrm\{lik\}\}\(\\mathbf\{f\}\)=\\sum\_\{m=1\}^\{M\}\\omega\_\{m\}\(\\mathbf\{f\}\)\\,\\mathbf\{C\}\_\{m\}\\mathbf\{C\}\_\{m\}^\{\\top\}and letHlik′​\(𝐟\)H\_\{\\mathrm\{lik\}\}^\{\\prime\}\(\\mathbf\{f\}\)denote the Hessian after removing comparisonm′m^\{\\prime\}, with all weights evaluated at the same fixed𝐟\\mathbf\{f\}\. ThenHlik′​\(𝐟\)=Hlik​\(𝐟\)−ωm′​\(𝐟\)​𝐂m′​𝐂m′⊤⪯Hlik​\(𝐟\)H\_\{\\mathrm\{lik\}\}^\{\\prime\}\(\\mathbf\{f\}\)=H\_\{\\mathrm\{lik\}\}\(\\mathbf\{f\}\)\-\\omega\_\{m^\{\\prime\}\}\(\\mathbf\{f\}\)\\,\\mathbf\{C\}\_\{m^\{\\prime\}\}\\mathbf\{C\}\_\{m^\{\\prime\}\}^\{\\top\}\\preceq H\_\{\\mathrm\{lik\}\}\(\\mathbf\{f\}\)\. This is a frozen\-curvature statement: it does not compare Hessians obtained after refitting the MAP on the reduced dataset, since refitting changes the remaining weights\.

###### Proof\.

ωm′​\(𝐟\)​𝐂m′​𝐂m′⊤⪰0\\omega\_\{m^\{\\prime\}\}\(\\mathbf\{f\}\)\\,\\mathbf\{C\}\_\{m^\{\\prime\}\}\\mathbf\{C\}\_\{m^\{\\prime\}\}^\{\\top\}\\succeq 0sinceωm′​\(𝐟\)\>0\\omega\_\{m^\{\\prime\}\}\(\\mathbf\{f\}\)\>0, soHlik​\(𝐟\)−Hlik′​\(𝐟\)⪰0H\_\{\\mathrm\{lik\}\}\(\\mathbf\{f\}\)\-H\_\{\\mathrm\{lik\}\}^\{\\prime\}\(\\mathbf\{f\}\)\\succeq 0\. ∎

## Appendix BMechanism Ablation

Table 2:Mechanism ablation: gain \(%\) over baseline B \(pool\_n6\_k15, 60 seeds\)\. Static KS: full prior\-gated diagonal correction\. Jitter: uniformR=c​IR\{=\}cI\(no prior gating\)\. Diagonal: uniform diagonal regularization \(R^=η​I\\hat\{R\}\{=\}\\eta I\)\. MetricOnly / CovOnly: partial mechanisms\.∗:p<0\.05p\{<\}0\.05,∗∗:p<0\.01p\{<\}0\.01\(pairedtt\-test vs\. B\)\.Uniform jitter adds a fixed constantccto every diagonal entry of the posterior precision \(R=c​IR\{=\}cI, whereccis chosen to match the trace of the KS correction\); it scores 0W/5L\. Diagonal regularization \(R^=η​I\\hat\{R\}\{=\}\\eta I\) uses theκ\\kappa\-calibrated strengthη∗\\eta^\{\*\}but applies it uniformly without the\(𝐊−1\)i​i\(\\mathbf\{K\}^\{\-1\}\)\_\{ii\}weighting; it scores 3W/2L, with\+30\.7%\+30\.7\\%on DTLZ2\-16D but the same losses as Static KS\.

MetricOnly adds𝐑\\mathbf\{R\}to the Hessian used in the Newton step for computing the MAP, but evaluatesJ0J\_\{0\}\(the original objective without𝐑\\mathbf\{R\}\) at each Newton iterate\. Since the objective being minimized is unchanged, the MAP estimate is the same as the baseline; only the Newton search direction is affected\. CovOnly keeps the standard MAP estimate𝐟^0\\hat\{\\mathbf\{f\}\}\_\{0\}but uses\(𝐇\+𝐑\)−1\(\\mathbf\{H\}\+\\mathbf\{R\}\)^\{\-1\}instead of𝐇−1\\mathbf\{H\}^\{\-1\}as the Laplace covariance\. Both score 1W/0L/7N, indicating that the improvement comes from shifting the MAP estimate \(as in the full KappaSharp correction\), not from changing the Newton search direction or tightening the covariance alone\.

## Appendix CInitialization Robustness

![Refer to caption](https://arxiv.org/html/2608.07859v1/x3.png)Figure 3:Adaptive KS improvement \(%\) over baseline for each of the 55 benchmark–initialization cells\. Each cell shows the mean improvement over 60 seeds\. Bold with asterisk \(∗\):p<0\.05p<0\.05\(pairedtt\-test\)\. Green = improvement, red = regression\. The two losses \(Hartmann\-6D under pure\_k5 and pure\_k15\) are both below2\.5%2\.5\\%\.### C\.1Proof of[Section˜4](https://arxiv.org/html/2608.07859#S4.SS0.SSS0.Px1)\(Effective Information Dimension\)

###### Proof\.

Let𝐌~=𝐊1/2​Hlik​𝐊1/2⪰0\\tilde\{\\mathbf\{M\}\}=\\mathbf\{K\}^\{1/2\}H\_\{\\mathrm\{lik\}\}\\mathbf\{K\}^\{1/2\}\\succeq 0with eigenvaluesμ1≥⋯≥μN≥0\\mu\_\{1\}\\geq\\cdots\\geq\\mu\_\{N\}\\geq 0\. SinceHlikH\_\{\\mathrm\{lik\}\}has rankN−NccN\{\-\}N\_\{\\mathrm\{cc\}\}\([Section˜4](https://arxiv.org/html/2608.07859#S4)\),𝐌~\\tilde\{\\mathbf\{M\}\}has exactlyNccN\_\{\\mathrm\{cc\}\}zero eigenvalues\.

*\(a\)*deff=∑i=1Nμi/\(1\+μi\)d\_\{\\mathrm\{eff\}\}=\\sum\_\{i=1\}^\{N\}\\mu\_\{i\}/\(1\+\\mu\_\{i\}\)\. Each term satisfies0≤μi/\(1\+μi\)<10\\leq\\mu\_\{i\}/\(1\+\\mu\_\{i\}\)<1, with equality to0iffμi=0\\mu\_\{i\}=0\. Since exactlyNccN\_\{\\mathrm\{cc\}\}eigenvalues are zero, at mostN−NccN\{\-\}N\_\{\\mathrm\{cc\}\}terms are positive, givingdeff≤N−Nccd\_\{\\mathrm\{eff\}\}\\leq N\{\-\}N\_\{\\mathrm\{cc\}\}\. Equality requires all nonzeroμi→∞\\mu\_\{i\}\\to\\infty\.

*\(b\)*Under the fresh\-pair assumption withNcc,0N\_\{\\mathrm\{cc\},0\}initial connected components: each of theTTqueries adds two unseen points and one new component, soNcc=Ncc,0\+TN\_\{\\mathrm\{cc\}\}=N\_\{\\mathrm\{cc\},0\}\+TandN=2​T\+N0N=2T\+N\_\{0\}\. Thereforerank⁡\(Hlik\)=N−Ncc=N0\+T−Ncc,0\\operatorname\{rank\}\(H\_\{\\mathrm\{lik\}\}\)=N\-N\_\{\\mathrm\{cc\}\}=N\_\{0\}\+T\-N\_\{\\mathrm\{cc\},0\}anddeff≤N0\+T−Ncc,0d\_\{\\mathrm\{eff\}\}\\leq N\_\{0\}\+T\-N\_\{\\mathrm\{cc\},0\}\. Hencedeff/N≤\(N0\+T−Ncc,0\)/\(2​T\+N0\)→1/2d\_\{\\mathrm\{eff\}\}/N\\leq\(N\_\{0\}\+T\-N\_\{\\mathrm\{cc\},0\}\)/\(2T\+N\_\{0\}\)\\to 1/2asT→∞T\\to\\infty\(withN0,Ncc,0N\_\{0\},N\_\{\\mathrm\{cc\},0\}fixed\)\.

*\(c\)*Connected \(Ncc=1N\_\{\\mathrm\{cc\}\}\{=\}1\):deff≤N−1d\_\{\\mathrm\{eff\}\}\\leq N\{\-\}1\. The rank ceiling is lifted toN−1N\{\-\}1, though the realized value depends on the magnitude of comparison weights \(a connected graph with vanishing edge weights can still havedeff≪N−1d\_\{\\mathrm\{eff\}\}\\ll N\{\-\}1\)\.

*\(d\)*Let𝐁=𝐊1/2​𝐑𝐊1/2⪰β​𝐈\\mathbf\{B\}=\\mathbf\{K\}^\{1/2\}\\mathbf\{R\}\\mathbf\{K\}^\{1/2\}\\succeq\\beta\\mathbf\{I\}withβ\>0\\beta\>0\. Defineg​\(𝐗\)=tr⁡\(𝐗​\(𝐈\+𝐗\)−1\)=N−tr⁡\(\(𝐈\+𝐗\)−1\)g\(\\mathbf\{X\}\)=\\operatorname\{tr\}\\bigl\(\\mathbf\{X\}\(\\mathbf\{I\}\+\\mathbf\{X\}\)^\{\-1\}\\bigr\)=N\-\\operatorname\{tr\}\\bigl\(\(\\mathbf\{I\}\+\\mathbf\{X\}\)^\{\-1\}\\bigr\)\. Sinceggis monotone increasing under the Loewner order \(adding PSD mass decreases\(𝐈\+𝐗\)−1\(\\mathbf\{I\}\+\\mathbf\{X\}\)^\{\-1\}\), and𝐌~\+𝐁⪰𝐌~\+β​𝐈\\tilde\{\\mathbf\{M\}\}\+\\mathbf\{B\}\\succeq\\tilde\{\\mathbf\{M\}\}\+\\beta\\mathbf\{I\}, we havedeffaug=g​\(𝐌~\+𝐁\)≥g​\(𝐌~\+β​𝐈\)d\_\{\\mathrm\{eff\}\}^\{\\mathrm\{aug\}\}=g\(\\tilde\{\\mathbf\{M\}\}\+\\mathbf\{B\}\)\\geq g\(\\tilde\{\\mathbf\{M\}\}\+\\beta\\mathbf\{I\}\)\. Sinceβ​𝐈\\beta\\mathbf\{I\}commutes with𝐌~\\tilde\{\\mathbf\{M\}\}:

g​\(𝐌~\+β​𝐈\)=∑i=1Nμi\+β1\+μi\+β=deff\+∑i=1Nβ\(1\+μi\)​\(1\+μi\+β\)\.g\(\\tilde\{\\mathbf\{M\}\}\+\\beta\\mathbf\{I\}\)=\\sum\_\{i=1\}^\{N\}\\frac\{\\mu\_\{i\}\+\\beta\}\{1\+\\mu\_\{i\}\+\\beta\}=d\_\{\\mathrm\{eff\}\}\+\\sum\_\{i=1\}^\{N\}\\frac\{\\beta\}\{\(1\+\\mu\_\{i\}\)\(1\+\\mu\_\{i\}\+\\beta\)\}\.\(23\)Each term in the sum is nonnegative, and theNccN\_\{\\mathrm\{cc\}\}terms withμi=0\\mu\_\{i\}=0each contributeβ/\(1\+β\)\\beta/\(1\{\+\}\\beta\), giving the bounddeffaug≥deff\+Ncc​β/\(1\+β\)d\_\{\\mathrm\{eff\}\}^\{\\mathrm\{aug\}\}\\geq d\_\{\\mathrm\{eff\}\}\+N\_\{\\mathrm\{cc\}\}\\beta/\(1\{\+\}\\beta\)\. ∎

## Appendix DThreshold Interpretation

###### Proposition 13\(Per\-step decisiveness threshold\)\.

Sincept=Φ\(\|⋅\|\)∈\[1/2,1\)p\_\{t\}=\\Phi\(\|\\cdot\|\)\\in\[1/2,1\)by construction, the mappingp↦sexp=1−ℋ​\(p\)/log⁡2p\\mapsto s\_\{\\mathrm\{exp\}\}=1\-\\mathcal\{H\}\(p\)/\\log 2is strictly increasing on\[1/2,1\)\[1/2,1\)\. Hencesexp,t≥τs\_\{\\mathrm\{exp\},t\}\\geq\\tauimpliespt≥p​\(τ\)p\_\{t\}\\geq p\(\\tau\)\. Atτ=0\.30\\tau=0\.30:pt≥0\.81p\_\{t\}\\geq 0\.81\.

###### Proof\.

ℋ​\(p\)/log⁡2\\mathcal\{H\}\(p\)/\\log 2is maximized atp=0\.5p=0\.5and strictly decreasing on\(0\.5,1\)\(0\.5,1\)\. Solving1−ℋ​\(p\)/log⁡2=0\.301\-\\mathcal\{H\}\(p\)/\\log 2=0\.30yieldsp≈0\.8107p\\approx 0\.8107\. ∎

On multi\-objective benchmarks where the disconnected\-graph problem is severe, the model quickly becomes confident about queried comparisons ands¯t\\bar\{s\}\_\{t\}rises aboveτ\\tau, activating the correction\. On smooth single\-objective basins \(e\.g\., Ackley\), the model remains uncertain during exploration ands¯t\\bar\{s\}\_\{t\}stays low, keeping the correction off\.

## Appendix EConvergence Curves

![Refer to caption](https://arxiv.org/html/2608.07859v1/x4.png)Figure 4:Convergence \(mean±\\pms\.e\., 60 seeds\)\. Left: DTLZ2\-16D\. Center: Ackley\-8D\. Right: Plasma\-16D \(\+10\.9%\+10\.9\\%\)\.
## Appendix FActivation Behavior

![Refer to caption](https://arxiv.org/html/2608.07859v1/x5.png)Figure 5:Activation behavior on WIN \(DTLZ2\-16D\) vs\. LOSS→\\toNEUTRAL \(Ackley\-8D\) benchmarks\. On DTLZ2\-16D, the activation rule enables the correction frequently \(median≈40%\\approx 40\\%of steps\); on Ackley\-8D, low model decisiveness keeps the correction largely off \(median≈12%\\approx 12\\%\), preventing the MAP shift that causes Static KS’s loss\.
## Appendix GAdditional Experimental Details

### G\.1Benchmark Descriptions

#### DTLZ2 \(8D, 16D, 20D\)\.

Standard multi\-objective test function\[Gonzálezet al\.,[2017](https://arxiv.org/html/2608.07859#bib.bib1)\]withdd\-dimensional input mapped to a 4\-dimensional outcome space, then to scalar utility via a piecewise\-linear aggregation\. The Pareto front is a unit hypersphere in outcome space\.

#### Plasma\-16D\.

Real industrial application: calibrating a 16\-parameter model predictive controller for atmospheric plasma surface treatment\[Shaoet al\.,[2025](https://arxiv.org/html/2608.07859#bib.bib14)\]\. Each function evaluation solves an MPC optimization with physics simulation\. The utility combines temperature uniformity and treatment speed, assessed by human inspection of temperature distributions\.

#### Ackley\-8D\.

Standard global optimization benchmark on\[−1,1\]8\[\-1,1\]^\{8\}with many shallow local optima surrounding a single global minimum\. The smooth basin structure provides strong local curvature, making the Laplace approximation already well\-conditioned\.

#### Hartmann\-6D\.

Standard 6\-dimensional test function with 6 local minima\. Like Ackley, the smooth landscape provides sufficient local curvature for the baseline\.

#### Levy\-10D, Levy\-20D\.

Multi\-modal test functions with increasingly complex landscape at higher dimensions\. The 20D variant tests scalability\.

#### CarCab\-7D, Vehicle\-5D, RobotPush\-14D\.

CarCab: 7\-dimensional vehicle cabin design\. Vehicle: 5\-dimensional crash safety optimization\. RobotPush: 14\-dimensional robotic pushing task simulated with Box2D physics, featuring contact discontinuities\.

### G\.2Hyperparameters

All experiments use BoTorch 0\.6\.0, GPyTorch 1\.6\.0, PyTorch 1\.11\.0\. PairwiseGP uses default RBF kernel with automatic relevance determination \(ARD\)\. EUBO is optimized with 4 restarts and 32 raw samples\. The precision correction activates at step 8 withα=0\.1\\alpha=0\.1\. Theη∗\\eta^\{\*\}solve uses a grid search on 60 log\-spaced points from10−610^\{\-6\}to10810^\{8\}\.

Init tables are generated with hash\-based independent RNG per \(benchmark, seed, stream\) usinggen\_init\_tables\_v3\.py\. Pool initializations use nested point sets \(n6⊂n8n\_\{6\}\\subset n\_\{8\}\) with independently shuffled comparison orderings\.

#### Activation step\.

The correction is eligible from step 8 by default\. In a preliminary study using Static KS on DTLZ2\-16D \(30 seeds, separate from the main 60\-seed runs\), we tested eligibility at steps 5, 8, 10, and 12; final improvement ranged from\+19%\+19\\%to\+24%\+24\\%, indicating low sensitivity to the exact activation step\. Earlier eligibility \(step 5\) occasionally produced unstableη∗\\eta^\{\*\}estimates; later eligibility \(step 12\) delayed the benefit without improving it\. All main\-table results use step 8 with 60 seeds\.

#### Compute\.

Experiments were run on a university HPC cluster \(AMD EPYC 7543 and Intel Xeon Platinum CPUs, 64\-core nodes\)\. Total compute: approximately 5,000 CPU\-hours across16,50016\{,\}500BO runs in the main grid plus ablations and sensitivity studies\. All 60\-seed conditions use paired same\-node execution with common random numbers \(CRN\)\.

## Appendix HThreshold Sensitivity

Table 3:Threshold sensitivity: Adaptive KS gain \(%\) over baseline forτ∈\{0\.25,0\.30,0\.35\}\\tau\\in\\\{0\.25,0\.30,0\.35\\\}on 4 representative benchmarks \(pool\_n6\_k15, 60 seeds\)\. All three thresholds produce zero losses\.∗:p<0\.05p\{<\}0\.05,∗∗:p<0\.01p\{<\}0\.01\(pairedtt\-test\)\.The thresholdτ=0\.30\\tau=0\.30has a per\-step interpretation: whensexp,t≥0\.30s\_\{\\mathrm\{exp\},t\}\\geq 0\.30, the model’s confidence in its own prediction satisfiespt≥0\.81p\_\{t\}\\geq 0\.81\([Appendix˜D](https://arxiv.org/html/2608.07859#A4)\)\. The implementation triggers on the EMAs¯t\\bar\{s\}\_\{t\}rather than the raw score; sincesexps\_\{\\mathrm\{exp\}\}is nonlinear inpp,s¯t≥τ\\bar\{s\}\_\{t\}\\geq\\taudoes not imply an EMA\-weighted averagep≥0\.81p\\geq 0\.81, but it does indicate that recent steps have exhibited high decisiveness on average\. Lowerτ\\tau\(more aggressive\) increases activation rate and gains on WIN benchmarks\. All three thresholds produce zero statistically significant losses\.

## Appendix ICalibration Parameterα\\alphaSensitivity

Table 4:Static KS gain \(%\) over baseline forα∈\{0\.05,0\.1,0\.2\}\\alpha\\in\\\{0\.05,0\.1,0\.2\\\}on 4 benchmarks \(pool\_n6\_k15\)\. Largerα\\alphatargets a lower condition number, producing stronger augmentation\.α=0\.1\\alpha=0\.1is a reasonable operating point; the tradeoff is not monotone \(e\.g\., Ackley atα=0\.05\\alpha\{=\}0\.05is worse than atα=0\.1\\alpha\{=\}0\.1\)\.∗:p<0\.05p\{<\}0\.05,∗∗:p<0\.01p\{<\}0\.01\.
## Appendix JConnected Querying Full Results

Table 5:Connected querying\[Xuet al\.,[2024](https://arxiv.org/html/2608.07859#bib.bib5)\]detailed results \(pool\_n6\_k15, 60 seeds\)\. One candidate per query is fixed to the previous query point \(xt′=xt−1x^\{\\prime\}\_\{t\}=x\_\{t\-1\}\); EUBO is retained as the acquisition function for fair comparison\.∗:p<0\.05p<0\.05,∗∗:p<0\.01p<0\.01\.Connected querying enforces a connected comparison graph by fixing one candidate per query to the previous query point \(xt′=xt−1x^\{\\prime\}\_\{t\}=x\_\{t\-1\}\)\. Note that the original algorithm ofXuet al\.\[[2024](https://arxiv.org/html/2608.07859#bib.bib5)\]uses a different acquisition function based on optimistic likelihood\-ratio confidence sets; here we adopt only their querying strategy and retain EUBO as the acquisition function so that the comparison isolates the effect of graph connectivity\. Fixing one candidate to the previous point limits exploration, resulting in losses on 7 of 11 benchmarks, including−93\.9%\-93\.9\\%on DTLZ2\-8D and−61\.9%\-61\.9\\%on Ackley\-8D\.

## Appendix KNon\-Laplace Inference Baselines

EP\-EI and Gibbs\-EI results on 4 representative benchmarks \(pool\_n6\_k15, 60 seeds\):

Table 6:Non\-Laplace inference baselines \(diagnostic\)\. Both use EI acquisition, not EUBO, which contributes to the poor performance\.∗:p<0\.05p<0\.05,∗∗:p<0\.01p<0\.01\.
## Appendix LWall\-Clock Overhead

Table 7:Wall\-clock time \(seconds\) per 50\-step BO run\. KappaSharp adds negligible overhead and is often*faster*due to improved Hessian conditioning\.The correction adds per\-step overhead when active\. On 4 of 8 benchmarks, the method is actually*faster*than baseline \(−2%\-2\\%to−13%\-13\\%wall\-clock\) because the better\-conditioned Hessian reduces Newton iterations; on others, the extra MAP solve adds up to\+23%\+23\\%wall\-clock time\.

## Appendix MFull Per\-Initialization Numeric Results

The heatmap in[Figure˜3](https://arxiv.org/html/2608.07859#A3.F3)summarizes Adaptive KS’s improvement across all 55 benchmark–initialization conditions\. Numeric values for each cell are available in the figure\. Key observations:

- •Pool initializations\(n6\_k15, n8\_k15\): 10W/0L/12N across all benchmarks\. The nested pool structure \(n6⊂n8n\_\{6\}\\subset n\_\{8\}\) provides a dense initial comparison graph that combines well with the activation rule\.
- •Pure matching initializations\(k3, k5, k15\): 8W/2L/23N\. Both losses occur on Hartmann\-6D \(pure\_k5:−2\.2%\-2\.2\\%,p<0\.05p<0\.05; pure\_k15:−1\.1%\-1\.1\\%,p<0\.05p<0\.05\)\. These are the smallest significant effects in the entire study, and both occur on a benchmark where the baseline is already well\-conditioned\.
- •High\-dimensional benchmarks\(DTLZ2\-16D, DTLZ2\-20D, Levy\-20D, Plasma\-16D\): positive across all initializations, which is consistent with the disconnected\-graph problem being the main bottleneck in those settings\.
- •Low\-dimensional benchmarks\(Vehicle\-5D, Hartmann\-6D, CarCab\-7D\): mostly neutral\. At low dimensionality, the comparison graph provides sufficient curvature relative to the prior, and the correction has little to add\.