Average Precision and the Mean Over Topics

Precision at a single cutoff asks whether the top of a list is good. It cannot say whether the good documents are at the top or merely somewhere in the judged depth, and it cannot distinguish a list whose relevant documents arrive in the first five positions from one whose relevant documents arrive spread through the first fifty. Average precision is the accumulated answer: it walks the ranked list and, each time a relevant document appears, records the precision of the prefix ending there, then divides by the number of relevant documents.

$$AP = \frac{1}{|R|}\sum_{i=1}^{n} P@i \cdot \mathbb{1}[d_i \in R]$$

The measure has been the primary figure of merit in text retrieval evaluation for decades, largely because it makes a specific and useful trade explicit: a relevant document at rank 1 contributes 1.0, and a relevant document at rank 100 contributes 0.02. Position is priced according to how many documents the user had to scan past, and the price is the reciprocal of the rank at which the document was found.

What the sum is actually accumulating

The formula is usually read as an average of precisions. It can also be read as a sum over relevant documents of $1/(\text{number of results scanned to reach it})$, which is often clearer about what the measure rewards.

That reading exposes the measure’s behaviour at small numbers of relevant documents. For a topic with one relevant document at rank $r$, the average precision is $1/r$. For a topic with two relevant documents at ranks 1 and 100, the average precision is $(1/1 + 2/100)/2 = 0.51$, a score that looks respectable without any of the tail being present. The second relevant document contributes only 0.01 to the total, but the first contributes 0.5, and the measure’s range is 0 to 1 for every topic regardless of how many relevant documents exist.

Two properties follow. First, AP is bounded and comparable across topics in a way that recall is not, because both precision values and the count of relevant documents are folded into a single ratio. Second, AP is dominated by the head for topics with few relevant documents and by the tail for topics with many. A topic with 200 judged-relevant documents and a system that finds 100 of them all below rank 150 yields an AP barely above zero, while the same system on a topic with a single relevant document at rank 4 yields exactly 0.25. The two numbers are in the same units and are not the same kind of quantity.

The contribution of a relevant document is not independent of what precedes it, which is the mechanism behind that asymmetry. Each term is the ratio of two running counts: how many relevant documents have appeared so far, and how many positions have been traversed. A long prefix of nonrelevant results decays both numerator and denominator of every later term, so a system that finds relevant documents late pays twice, once for the position and once for the depressed precision of the prefix. Deep clusters of relevant results recover partially, because a burst of relevant documents raises the running precision faster than the positions advance. This is why AP rewards clustering of relevant material and punishes a single relevant document found after a long nonrelevant run, even when the total number of relevant documents found is identical.

Truncation changes the measure in a way that is easy to miss. Some tooling computes AP over the full returned run, others over the top 100 or top 1000 positions. The difference is small when runs are shallow and substantial when a system returns thousands of documents, because the untruncated version keeps adding small contributions from the tail while the truncated version stops. Both are legitimate; neither is comparable to the other, so the depth has to travel with the number.

The mean is a ratio of sums, not a mean of ratios

Mean average precision is the arithmetic mean of per-topic AP over the query set. The averaging is where the measure’s statistical problems begin, and they are not resolved by more topics.

Each per-topic AP is a ratio whose denominator is that topic’s relevant count. The mean of such ratios is not the same quantity as the ratio of the summed precisions to the summed relevant counts, and neither is a natural estimate of anything except the mean of the observed values. A mean of per-topic values weights a topic with three relevant documents identically to a topic with three hundred, which is a deliberate choice: difficulty should count as much as importance. It also means that the mean is heavily influenced by the mass of topics near zero, which is where difficult topics land, and that adding a few easy topics to a query set can move the mean more than improving the system on the hard ones.

The variance around that mean is large. Per-topic AP distributions in standard collections are typically far from normal, with a spike at zero for topics the system fails and a long mass in the middle. Reporting a mean without an interval hides this. Resampling the topic set, with replacement, and recomputing the mean gives a bootstrap interval that reflects the spread across topics; with a few dozen topics the interval is often wide enough to swallow the differences between systems that a leaderboard displays as distinct.

The spread is not merely uncomfortable, it changes what a leaderboard means. A table sorted by mean AP presents a total order over systems, but the underlying estimates are uncertain by amounts that scale with the dispersion of per-topic scores and inversely with the square root of the topic count. Two systems separated by one place in the table may be separated by an amount smaller than the interval on either estimate. The ordering is then a summary of point estimates, not a claim about which system is better.

Comparing two systems on the same topics

Paired comparison is the only comparison that has power, because the same topics drive both systems and the topic-to-topic variation largely cancels. The standard test recomputes the mean under many resamples of topics and counts how often one system comes out ahead. A typical outcome for two systems whose means differ by a few percentage points is that the interval on the difference straddles zero: the systems are not distinguishable at this query-set size, and a larger difference or a larger query set is needed to make the claim.

The practical consequence is a habit worth keeping. Report the mean, the number of topics, and whether a paired test found the difference significant. A leaderboard that reports only means is reporting a sample statistic with no indication of sampling error, and the ordering it displays is unstable under the resampling that would produce the error bars.

There is a second, subtler issue with AP as a comparison target. Two systems can have identical MAP while differing in how their gains are distributed across topics, and the distribution matters if the deployment cares about worst cases. One system that is uniformly good and one that is excellent on half the topics and broken on the other half average out to the same number. Reporting the per-topic spread, or the number of topics on which a system falls below a floor, distinguishes them.

A third issue concerns what a paired test is testing. The null hypothesis is that the two systems are equally effective on the topic population from which the evaluated topics were drawn, and the resampling procedure approximates the distribution of the difference under that hypothesis. When the systems are not similar, when one of them is a baseline built years earlier, the assumption of exchangeable topics becomes strained: the newer system may be better on exactly the topics that the collection’s authors did not write. The test then answers a narrower question than the one being asked, and the narrower question is the one that can be answered from the data.

Where the measure stops making sense

AP assumes binary relevance. Given a graded judgment set, the tooling either binarises at a threshold, treating labels above the cut as relevant and the rest as not, or computes a graded variant where the credit is scaled by the label. The binarised version discards the distinction between a document that answers the question and one that merely mentions the subject, which is exactly the distinction a graded collection was built to preserve. Which threshold to use is a modelling decision that the measure does not make, and different thresholds produce different orderings of systems on the same data.

AP also assumes that all relevant documents are interchangeable and that each one is worth finding. For navigational topics, where a user wants one specific page, AP is indifferent between returning that page in position 1 and returning it in position 3 after two other documents that are also about the site. Reciprocal rank, described in Reciprocal Rank and Rank-Biased Precision, encodes the preference for a single answer more directly.

The measure is also blind to the difference between two relevant documents that say the same thing and two that say different things. A run that returns five near-duplicates covering one aspect of a query and a run that returns five documents covering five aspects receive the same credit, provided both are judged relevant at the document level. Sub-topic judgments change that calculation, as covered in Sub-topic Judgments and Diversity Metrics, but they require a different judgment structure than the one AP was designed for.

Finally, AP is sensitive to the judgment pool in a way that grows with the number of relevant documents. Undetected relevant documents in the tail reduce the number of positive contributions and inflate the denominator, so a system that finds documents the pool missed is penalised for finding them. The bias is systematic rather than random and it affects systems differently according to how much they contributed to the pool. It is the reason pooled evaluation requires care at depth, taken up in Pooling Depth and the Unjudged Tail.

For all of these reasons the recommendation that has settled in the literature is not to pick one measure. A binary summary, a graded summary, and a per-topic spread reported together cost little to compute from the same run files and prevent the specific misinterpretations that each single number invites.