Expected Reciprocal Rank (ERR)

Background

Expected Reciprocal Rank (ERR) is the cascade-model graded-relevance ranking metric. Unlike NDCG, ERR models user satisfaction probabilistically: each result has a chance of satisfying the user (depending on its grade), and once satisfied, lower positions contribute nothing.

Problem statement

Implement err(grades, g_max=4):

$$R_i \;=\; \frac{2^{g_i} - 1}{2^{g_{\max}}}, \quad \text{ERR} \;=\; \sum_{r=1}^{n} \frac{1}{r}\,R_r \prod_{i < r}(1 - R_i)$$

where $g_i \in [0, g_{\max}]$ is the relevance grade at rank $r$. Walk the list top-down, accumulating $\text{survive} = \prod_{i<r}(1-R_i)$ as you go.

Input

• grades — sequence of int graded relevance values in $[0, g_{\max}]$, in rank order (rank 1 first).
• g_max — int >= 1, the maximum grade (default $4$, matching the standard TREC relevance scale).

Output

Returns a Python float in $[0, 1]$.

Examples

Example 1 — all zero grades

Input:  grades=[0, 0, 0, 0]
Output: 0.0

Example 2 — single max-grade item

Input:  grades=[4], g_max=4
Output: 15/16 ≈ 0.9375

Explanation: $R_1 = (2^4-1)/2^4 = 15/16$. Contribution = $1 \cdot 15/16 / 1 = 15/16$.

Example 3 — hand-computed two-position case

Input:  grades=[2, 4], g_max=4
Output: 291/512 ≈ 0.5684

Explanation: $R_1=3/16$. Contribution $= 3/16$. Survive = $13/16$. $R_2=15/16$. Contribution $= 13/16 \cdot 15/16 / 2 = 195/512$. Sum $= 3/16 + 195/512 = 291/512$.

Constraints

• Returns a plain Python float.
• g_max >= 1.

Notes

• vs NDCG. NDCG is independent across positions; ERR is dependent — high relevance at the top lowers the influence of everything below.
• Maximum possible value. Even with $g_i = g_{\max}$ everywhere, ERR < 1 because $R < 1$ at $g_{\max}$.