Pre-Retrieval Query Performance Prediction

Not every query can be answered well. Some are ambiguous, some name concepts the collection does not contain, and some are so broad that no ranking is meaningfully better than another. A retrieval system that could tell which of these it is facing could route the hard cases to a different configuration, ask for clarification, or at least avoid promising a definitive answer.

Query performance prediction is the attempt to make that estimate without relevance judgments. Two families of method exist: those that look only at the query and the collection before retrieval, and those that look at the ranked list after it. The pre-retrieval family is cheaper and is what a routing decision needs, since it must run before the expensive path.

What specificity alone measures

The simplest predictor is a property of the query terms in the collection. A query whose terms are rare has a narrow candidate set and, if the collection contains the concept at all, is likely to be answered precisely. A query of common terms has a huge candidate set and the ranking has to do the work.

The summary statistic is the average inverse document frequency of the query terms, or equivalently the sum of the negative log probabilities under a collection language model:

$$\text{specificity}(q) = \frac{1}{|q|}\sum_{t \in q} \log\frac{N}{df(t)}$$

Higher is more specific. The measure is cheap: one dictionary lookup per term, no scoring pass.

It is also close to useless on its own, because it measures the collection rather than the query’s relationship to it. A rare term that does not occur at all produces a high specificity and zero results. A query made of rare terms that are rare for unrelated reasons produces a high specificity and a scattered result set. The predictor captures one failure mode, the overly broad query, and misses the others.

Term-level variants improve the coverage slightly: the maximum IDF rather than the mean captures the case where one term is doing all the discriminating work; the variance of the IDFs captures the case where the query mixes a rare and a common term, which behaves differently from a query of uniformly medium terms.

Clarity and the divergence from the collection

The clarity predictor asks a different question: how much the query’s own language model diverges from the collection’s.

The query model is estimated from the query terms, smoothed against the collection, and the divergence is measured with KL divergence:

$$D_{\mathrm{KL}}(P_q ,|, P_C) = \sum_{w} P_q(w) \log \frac{P_q(w)}{P_C(w)}$$

A high divergence means the query names things the collection talks about rarely, relative to the collection’s average vocabulary. The intuition, borne out in the published evaluations, is that such queries have a more peaked relevant set and are easier to answer precisely, while a query whose model resembles the collection’s own distribution is broad and its results will be a diffuse sample.

The estimate requires the query model to be smoothed, because a maximum-likelihood model over a three-term query is a distribution with three non-zero entries and its divergence from the collection is dominated by how rare those three terms are, which reduces the measure to a weighted IDF. The smoothing parameter controls how much of the collection’s distribution leaks in, and the measure’s behaviour changes with it. This is a recurring theme in this family: every predictor has a smoothing knob, and the knob is not derivable from the model.

Clarity is computed before retrieval, over the collection model, and costs a lookup of each query term’s probability plus the entropy of the query model. It does not require scoring documents.

Score distributions and the shape of the ranked list

Post-retrieval predictors use the scores that retrieval produced. The oldest and most reliable is the score gap: the difference between the top score and some lower score, or the ratio between the top score and the mean of the top $k$. A large gap suggests a clear winner, and a clear winner suggests an easy query.

The distributional version fits a model to the scores and asks how separable the top is. The standard approach treats the scores of retrieved documents as a mixture of a relevant component and a non-relevant component and estimates the separation between them; a wide separation predicts good performance, an overlapping one predicts that the ranking is not distinguishing anything.

Clustering-based variants apply $k$-means or a simpler gap statistic to the sorted scores and count the size of the top cluster. A small top cluster with a large score margin predicts an easy query; a smooth decay with no elbow predicts a hard one.

These methods are more accurate than the pre-retrieval family in published comparisons, which is expected: they observe the system’s actual behaviour. They are also useless for the routing decision that motivated the exercise, since the routing decision must be made before the retrieval that produces the scores. The reconciliation is to use a post-retrieval predictor for evaluation and monitoring, and a pre-retrieval predictor for routing, accepting the accuracy gap.

import math

def specificity(terms, df, n_docs):
    vals = [math.log(n_docs / max(df.get(t, 0), 1)) for t in terms]
    return sum(vals) / len(vals) if vals else 0.0

def score_gap(scores, k=10):
    """Ratio of top score to mean of ranks 2..k; needs a scored list."""
    if len(scores) < 2:
        return 0.0
    head = scores[0]
    tail = scores[1:min(k, len(scores))]
    mean_tail = sum(tail) / len(tail)
    return head / mean_tail if mean_tail > 0 else float("inf")

The gap statistic above is sensitive to the number of documents scored and to whether the scorer’s output is bounded. A scorer whose scores are probabilities compresses differences near 1.0, so the ratio understates the gap for good queries; an unbounded scorer such as a raw inner product does not. Comparing the statistic across scorers is therefore meaningless, and even within one scorer it should be normalized against the distribution for the collection.

The correlation ceiling and what it implies

Every published predictor is evaluated by correlating its per-query predictions against the per-query effectiveness of the system, usually with Kendall’s $\tau$ or Spearman’s $\rho$. The correlations are modest. A predictor that reaches a strong rank correlation across a query set is a good result; most reach weak-to-moderate.

The modest numbers are not only an implementation problem. Per-query effectiveness is itself noisy: a query’s score depends on which documents were judged, how many were judged, and where the cutoffs are. Two runs of the same system with slightly different judgment sets produce different per-query effectiveness values, which caps the achievable correlation. A predictor cannot correlate more strongly with a quantity than that quantity correlates with itself.

The practical consequence is that a predictor should be used as a coarse signal, not as a decision rule with a precise threshold. Three bands, easy, uncertain, and hard, are defensible; a continuous estimate used to weight a fusion parameter is not.

Where the prediction is actually used

Four uses survive contact with the accuracy ceiling.

Selective expansion. Queries predicted hard are the ones where thesaurus expansion and pseudo-relevance feedback help most, because their initial result set is unreliable. The same logic appears in synonym expansion as a threshold on result count, but prediction is a better gate because it fires on queries that return many results of low quality, which the count threshold misses.

Rank fusion. Two retrieval configurations disagree more on hard queries than on easy ones, and a prediction-weighted combination of their scores reduces the damage when one of them is wrong.

Clarification prompts. A query predicted ambiguous can be answered with a disambiguation page rather than a ranked list, and the ambiguity itself is often the same property that click-entropy and reformulation measure from behaviour. The threshold for triggering this is high, because a wrong prompt costs more than a bad ranking.

Monitoring. Aggregate prediction over a query stream detects collection drift: if the mean predicted difficulty rises, the index has probably fallen behind the corpus. That is a use where the per-query accuracy matters less than the aggregate trend.

The limitation that binds all four is the same. Prediction estimates whether the system can answer the query, not whether the collection contains the answer. A query about a topic absent from the index is predicted as hard, correctly, and no configuration change will fix it. Distinguishing “the collection lacks this” from “the ranking cannot find this” is a different problem, and the signals that address it come from the retrieval itself rather than from the query.