On WikiQA, a question-answering benchmark built from real Bing search queries, one correct answer sentence in five shares no content word with its question (WikiQA). A frozen sentence encoder, which maps each question and each candidate answer to one vector, has to represent "who played the lead in that film" and "the role went to an actor from Chicago" as close points. It also has to decide when no candidate answers the question at all. This proposal learns a distance on top of such a frozen encoder with two properties. First, each candidate answer is represented by several points, called prototypes: its own embedding, embeddings of questions it could plausibly answer, and embeddings of short descriptions of the entities it mentions. A question matches the answer through whichever prototype is nearest. Second, the distance is a Mahalanobis metric, meaning a learned positive semidefinite matrix $M$ that stretches and rotates the embedding space. It is fit by a sequence of convex problems, so each step has a unique optimum and the result does not depend on random initialization.
The underlying bet is about where the lexical gap sits. Classic convex metric learning collapses each class toward a single target and breaks when the data is multi-modal (Metric Learning by Collapsing Classes). Multi-prototype methods handle multi-modality but are trained with non-convex objectives that tend to collapse their prototypes onto each other (SoftTriple Loss; Multi-Proxy Wasserstein Classifier). In this setting the prototypes are fixed vectors produced by the encoder, and only the metric is learned. That separation makes almost the whole problem convex. The one non-convex choice left is which prototype of the correct answer explains the question. We handle it with a majorization step whose inner problems are all convex.
Core Claim
Let $d_M(x,y)=(x-y)^\top M(x-y)$ with $M\succeq 0$. Answer $a$ has fixed prototypes $p_1,\dots,p_K$, and we define its soft-min distance to question $q$ as $D_M(q,a) = -\tau\log\sum_k \exp(-d_M(q,p_k)/\tau)$, where $\tau>0$ is a smoothing temperature. Because $d_M$ is linear in $M$, $D_M$ is concave in $M$.
Concavity helps and hurts in different places. In the "push" term, which drives wrong answers away, we penalize $-D_M$, and that term is convex. The "pull" term, which draws the correct answer $a^+$ closer, penalizes $D_M(q,a^+)$, and that term is not convex. We fix this with the standard variational bound: for any weights $r$ on the simplex, $D_M(q,a^+)\le \sum_k r_k d_M(q,p_k^+) + \tau\sum_k r_k\log r_k$. Equality holds when $r=\mathrm{softmax}(-d_M/\tau)$. Holding $r$ fixed gives the inner problem
$$\min_{M\succeq 0,\,b}\ \sum_{q}\Big[\gamma + \sum_k r_{qk}\, d_M(q,p^+_k) - \min_{a^-}{}^{\tau} D_M(q,a^-)\Big]_+ + \sum_{q\in\mathcal{U}}\big[\,b - \min_{a}{}^{\tau} D_M(q,a)\big]_+ + \sum_{q\notin\mathcal{U}}\Big[\gamma + \sum_k r_{qk}\, d_M(q,p^+_k) - b\Big]_+ + \lambda\,\mathrm{KL}(M\,\|\,I).$$
Here $\gamma$ is a margin, $\min^\tau$ is soft-min over the negative (or all) candidates, $\mathcal{U}$ is the set of questions with no correct candidate, $b$ is a learned rejection radius, and $\mathrm{KL}(M\|I)$ is the LogDet divergence to the identity that Information-theoretic metric learning (ITML) uses as a prior. Every term is a hinge of a convex function of $(M,b)$, so the inner problem is convex. We alternate between solving it exactly and updating $r$ in closed form. This is a concave-convex procedure: the objective decreases monotonically, and every iterate is the unique minimizer of its inner problem.
We do not claim global optimality for the full problem. When $K=1$ the method reduces exactly to a convex large-margin problem in the style of LMNN, with an added rejection term.
The claim to be tested has two parts. On the zero-overlap slice of WikiQA, this metric beats both cosine similarity on the same prototypes and a single-prototype convex metric. It also beats an identically parameterized metric trained by stochastic gradient descent in the regimes where convexity should matter: few labels, label noise, and variance across random seeds. The learned radius $b$ gives better answer triggering, the task of deciding whether any candidate answers the question, than a threshold tuned after the fact on a fine-tuned encoder's scores.
Research Program
Prototypes. Each candidate sentence gets three kinds of fixed prototypes from one frozen encoder. The first is its own embedding. The second is the embeddings of several synthetic questions generated from it, following the pseudo-query view of MINDER. MINDER uses such views as token strings scored by sequence likelihood in a generative retriever; we use them as continuous points under a learned metric. The third is the embeddings of short knowledge-base descriptions of entities that appear in both the question and the candidate, following the "intersection entities" idea of DP-KB. DP-KB prepends this text to a cross-encoder's input during training. Here the descriptions are separate prototypes, so the metric decides how much to trust each one. Prototype cardinality, a known weak point of multi-prototype methods (Fewer is More), is controlled by the soft-min, which gives unhelpful prototypes almost no weight. We will report how weight concentrates across prototypes rather than tune $K$ by grid search.
Relation to prior convex and prototype methods. Sparse Multi-Prototype Classification (SMP) smooths prototype assignment into a convex-concave saddle-point problem. It learns prototype locations under a fixed Euclidean distance and was tested on low-dimensional tabular data. We do the reverse: prototypes are fixed and the metric is learned, in 768-dimensional text space, with an asymmetric structure where only answers carry prototypes. C2LM combines local metrics over regions found beforehand by $k$-means and runs into a "comparison gap" between regions. Our prototypes are semantically meaningful views attached to each answer, so there is no partition of the space and no gap between regions. The global metric is shared, and multi-modality lives entirely in the prototypes.
Solver. For $d=768$, projecting onto the positive semidefinite cone costs roughly $4.5\times 10^8$ floating-point operations per eigendecomposition, which is tolerable. The known cubic bottleneck of these methods (Xing et al.) therefore matters only for the larger-scale variant. We will use projected subgradient steps on a PCA-reduced space (256 dimensions) as the default. We will compare this against ITML-style Bregman projections, which use rank-one updates, on the full space. Every inner solve is certified by its duality gap, so "converged" has a checkable meaning.
Baselines
The naive reference points are word-count overlap and cosine similarity between frozen encoder embeddings of the question and the candidate sentence. For word count, WikiQA reports 0.4891 MAP; no reported result was found on Lacuna for frozen-encoder cosine. Both will be run on the same test splits.
The ablation that isolates the prototypes is a single-prototype convex metric: the same objective with $K=1$, which is LMNN-like and fully convex. The ablation that isolates the learned metric is multi-prototype soft-min with $M=I$. That is the MINDER-style multi-view idea moved into dense space with no learning.
The ablation that isolates convexity is the same parameterization, $M=L^\top L$ with $L$ of matching rank, trained with Adam on the true soft-min objective. It gets the same data, the same prototypes, and the same hyperparameter search budget of 30 configurations, and it is reported over ten seeds.
The strongest competitor in the same deployment class, meaning a two-tower scorer that can index answers ahead of time, is the frozen encoder fine-tuned end to end as a bi-encoder with in-batch negatives. It gets the same labeled data and a larger compute budget. No reported WikiQA number was found on Lacuna for this configuration, so we run it ourselves.
The strongest existing method overall is the cross-encoder of TANDA. It first transfers on the ASNQ answer-selection corpus and then adapts to the target set, and it reports 92.0 MAP on WikiQA and 94.3 MAP on TREC-QA. DP-KB reports a further 1.3 MAP on WikiQA. We treat these as an upper reference, not a target. A frozen bi-encoder with a linear metric is not expected to match a cross-encoder that reads both texts jointly.
What counts as winning. The method must clearly beat the fine-tuned bi-encoder and all three ablations on MAP and MRR over the zero-overlap slice. It must beat the gradient-trained twin on seed variance and on degradation under 20% label noise, the noise level TANDA uses in its robustness analysis. Finally, it must close part of the gap to TANDA when TANDA's scores are restricted to the zero-overlap slice. For answer triggering, the reference is the roughly 31.6% F1 reported in WikiQA, plus a validation-tuned threshold on the fine-tuned bi-encoder's scores.
Why not just…?
Why not just fine-tune the encoder, or use TANDA? For accuracy on small reranking sets, that is the right answer, and we say so: TANDA's 92.0 MAP is out of reach for a frozen bi-encoder. The case for our method rests on three settings. The first is where answers must be indexed ahead of time. The second is where labels are few or noisy; TANDA itself documents unstable, all-or-nothing behavior when a transformer is fine-tuned directly on small data. The third is where an explicit rejection radius is needed. If the fine-tuned bi-encoder beats us on the zero-overlap slice and on triggering at matched data, the contribution fails, and the experiment is designed to show that.
Why not just train the same metric with SGD, since convexity may not matter for one linear map? This is the most serious threat. Low-rank linear adapters trained by gradient descent often behave well. We isolate it directly with the gradient-trained twin. If that twin matches us in accuracy, seed variance, low-label performance, and noise robustness, we will report that convexity buys nothing here and reframe the result around the prototypes.
Why not just take the maximum over MINDER-style views with plain cosine similarity? This tests whether the learned metric is doing any work. The $M=I$ ablation answers it. We also report per-view weights, to show whether the metric learns to trust entity prototypes differently from pseudo-question prototypes.
Why not just rewrite the query with an LLM? Rewriting works on the question side and is prone to semantic drift (RaFe). Our pseudo-questions are generated offline, once per answer, so there is no cost at query time. Query rewriting also combines with our method rather than competing with it. We will add rewritten queries as an extra condition for both our method and the bi-encoder.
Proposed Experiments
The main study uses WikiQA and TREC-QA with MAP, MRR, and precision at 1. Every metric is reported separately on the zero-overlap slice. WikiQA is also used for answer triggering, measured by F1. Label-efficiency curves use 10%, 25%, and 100% of the WikiQA training questions. Noise curves inject 0% to 20% label flips. Every number comes with mean and standard deviation over ten seeds. For the convex method, seeds vary only the prototype generation, so any variance that remains can be traced to that source.
A scale check fits $M$ on a subset of ASNQ with ITML-style updates and applies it zero-shot to WikiQA. A retrieval check reranks BM25 top-100 lists on TREC 2019 Deep Learning passages, reporting NDCG@10 alongside the 0.675 that LTRe reports for a fully trained dense retriever.
The decisive checks come from three comparisons. The zero-overlap gain over the $K=1$ convex metric tests whether multiple prototypes help. The gap to the $M=I$ soft-min tests whether the learned metric helps. The stability gap to the gradient-trained twin at 10% of the labels and 20% noise tests whether convexity helps. If the last comparison is null, the paper's title loses its first word, and we will say so.
References
- WikiQA: A Challenge Dataset for Open-Domain Question Answering
- Metric Learning by Collapsing Classes
- SoftTriple Loss: Deep Metric Learning Without Triplet Sampling
- Multi-Proxy Wasserstein Classifier for Image Classification
- Information-theoretic Metric Learning
- Distance Metric Learning for Large Margin Nearest Neighbor Classification
- Multiview Identifiers Enhanced Generative Retrieval
- DP-KB: Data Programming with Knowledge Bases Improves Transformer Fine Tuning for Answer Sentence Selection
- Fewer is More: A Deep Graph Metric Learning Perspective Using Fewer Proxies
- Sparse Multi-Prototype Classification
- Metric Learning as Convex Combinations of Local Models with Generalization Guarantees
- Distance Metric Learning with Application to Clustering with Side-Information
- TANDA: Transfer and Adapt Pre-Trained Transformer Models for Answer Sentence Selection
- RaFe: Ranking Feedback Improves Query Rewriting for RAG
- Learning To Retrieve: How to Train a Dense Retrieval Model Effectively and Efficiently