Certifying Pairwise Readouts under Rank-Two Representation Uncertainty

In graph-based decision systems, some node representations may be missing when a score must be compared with a threshold. Certifying the decision then requires a bound over all admissible completions. We study this problem for nonnegative weighted sums of pairwise inner products. Unknown vectors vary independently in the unit cube, with coordinatewise-bounded orthogonal residuals from a supplied rational rank-two subspace; observed vectors lie in that subspace. In a computable small-radius regime, we construct the exact projected domain and ordered sets of projected candidates, reducing their coupled optimization to a polynomial-size minimum-cut problem. Feasible lifting provides a witness and a quadratic-width interval for the original maximum, whose first-order perturbation coefficient is exactly recoverable. Thresholding the second-order coefficient is strongly NP-complete in a fixed sixteen-dimensional geometry, even with a unique zero-radius optimizer. At every fixed sufficiently small positive rational radius in that geometry, maximum-value thresholding remains strongly NP-complete and maximization admits no fully polynomial-time approximation scheme unless $\mathrm{P}=\mathrm{NP}$. Exact comparisons on constructed instances quantify certificate quality, while coupled multi-label examples demonstrate the role of joint optimization. As an application, a monotone deviation certificate supports selecting vectors to fix at reference values. Together, these results separate efficient certification from exact residual optimization in the rank-two uncertainty model.