Frecency Ranking

An elegant ranking algorithm that unifies frequency and recency

I really love the UX of fuzzy finders. They are intuitive, flexible, fast, and keyboard driven. They are also ubiquitous: I use fuzzy finders on the command line with fzf, in my browser with the address bar, and on the desktop with Raycast.

The best fuzzy finders share a few properties:

They are fast
They correctly guess thing I'm looking and put it at the top of the list

If you squint, #2 is redundant. If the list of results isn’t ranked well, I need to either add more specificity to my fuzzy query (which takes time), or tab down the list to select the entry I want (which also takes time).

Even with no domain knowledge, fuzzy finders can provide some meaningful ranking with heuristics. For example: upranking exact substring matches.

In many cases, we can do much better. Past behavior tends to be good predictor of future behavior, so if I habitually type news.y in my address bar, I probably am looking for an orange site. If I cd ~/workstuff every Monday morning when I open my terminal, it's likely I'll want to do the same every Tuesday.

When using past behavior as a predictor, there are two ranking signals that tend to be intuitive:

Frequency (how many times I have visited an item), and
Recency (how long it's been since I've visited an item)

In this post, I'll explore how to combine those two ranking signals into a single, intuitive metric commonly known as frecency.

Individually, both frequency and recency are insufficient for an intuitive ranking. Pure frequency fails in situations where things can become irrelevant, so a project that I worked on 5 years ago still shows up high in my list. Pure recency fails to account for the "one-off" nature of things like jumping to a temp directory for debugging test output.

To account for these individual limitations, the two are commonly combined into a frecency score.

For some examples on the command line, fasd uses a frecency function that increases the weight of an entry based on how recently it was last visited.

function frecent(time) {
	dx = t-time
	if( dx < 3600 ) return 6
	if( dx < 86400 ) return 4
	if( dx < 604800 ) return 2
	return 1
}

Previously, z used an identical function, but switched to a continuous version with similar behavior.

function frecent(rank, time) {
	dx = t - time
	return int(10000 * rank * (3.75/((0.0001 * dx + 1) + 0.25)))
}

The problem with both these formulations is that the only take into account the time of the last visit. That means that if I was very active on a project years ago, but then visit it once to refer to some old code I wrote, it will be stuck towards the top of my list.

The way Firefox solves this is to store the last 10 visits. This way, a single aberrent visit does not force an item to the top. The tradeoff is having to store 10x the amount of data. It also suffers from an issue where many low-weighted visits can actually decrease the frecency score.

So how can we do better?

For the remainder of this post, I’ll be exploring a formulation of frecency based on exponential decay. Given a set of visit times $V = \{ v_1, v_2, \ldots, v_n \}$ , a half life $λ$ , and the current time $t$ , we define the frecency score $F$ for an entry as follows:

F(V, λ, t) = \sum_{v \in V} \left(\frac{1}{2}\right)^{\frac{t - v}{λ}}

To decode this a bit, each visit’s contribution is added to the total score, and its contribution decays exponentially over time. The $λ$ parameter is the half life—the time it takes for the contribution to decay by a factor of two.

This is not an original idea. An equivalent formulation was proposed to replace Firefox’s frecency algorithm, but was never implemented.

So, what's special about this definition of frecency?

A small thing that makes this formulation convenient to work with is that the contributions of each visit to the final frecency score are independent of one another. Adding a new visit does not change how the score from previous visits is calculated.

This is not the case for the other frecency schemes I covered. In particular, for schemes that only keep track of most recent visit time, all previous visits are effectively re-weighted as if they happened at the new time. In the Firefox frecency algorithm, if a visit is not in the last 10, its contribution is zeroed.

You might ask: why does this matter? For one, but I think it's more elegant and easier to reason about. More tangibly though, it means we can merge frecency scores without needing to know every visit time.

In an offline-first web app, scores can be kept in local storage and synced periodically with the server
For a shell utility that keeps track of common commands, scores can be synced and merged across devices
When a new user picks up the product for the first time, it's possible to make reasonable suggestions by merging the frecency scores from other users in their org

Another very cool property of this definition is that the half life parameter $λ$ provides a smooth slider between most-recent and most-frequent rankings. Consider how $λ$ affects the relative contributions of two visits $v$ and $v + Δ{}t$ :

\begin{align*} \frac {F(\{v + Δ{}t\}, λ, t)} {F(\{v\}, λ, t)} &= \frac {\left(\frac{1}{2}\right)^{\frac{t - (v + Δ{}t)}{λ}}} {\left(\frac{1}{2}\right)^{\frac{t - v}{λ}}} \\ &= \left(\frac{1}{2}\right)^{\frac{- Δ{}t}{λ}} \\ &= 2^{Δ{}t / λ} \\ \end{align*}

For $Δ{}t > 0$ , $\lim_{λ\to{}0} 2^{Δ{}t / λ} = \infty$ , meaning that the contribution of the most recent visit dominates the score for small $λ$ . This provides a ranking approaching to most-recent.

Similarly, $\lim_{λ\to\infty} 2^{Δ{}t / λ} = 1$ , meaning that each visit contributes equally to the score for large $λ$ . This provides a ranking approaching to most-frequent.

Another small thing I like about this definition is that the meaning of $λ$ is at least somewhat intuitive. If I set $λ$ to one week, that means it will take two visits from a week ago to outrank a single visit now. Because it's an explainable parameter, it can even be useful to expose it as a user-configurable option.

My personal favorite characteristic of this frecency scheme is that we don’t actually need to store the full vector of visit times. Consider how the score changes as the evaluation time changes (adding $Δ{}t$ ).

\begin{align*} F(V, λ, t + Δ{}t) &= \sum_{v \in V} \left(\frac{1}{2}\right)^{\frac{t + Δ{}t - v}{λ}} \\ &= \left(\frac{1}{2}\right)^{\frac{Δ{}t}{λ}} \sum_{v \in V} \left(\frac{1}{2}\right)^{\frac{t - v}{λ}} \\ &= \left(\frac{1}{2}\right)^{\frac{Δ{}t}{λ}} F(V, λ, t) \end{align*}

This means, for a constant $λ$ , we can calculate the current score given only a previous score and the time elapsed since that score was calculated. This means that we do not need to store the full set of visit times, making the space requirement constant per entry.

But we can actually go one step further. Instead of having to keep track of a score and the time it was calculated at, we can combine both into a “time at which the score would decay to 1”, which we'll call $T_1(V, λ)$ .

\begin{align*} 1 &= F(V, λ, T_1(V, λ)) \\ 1 &= \sum_{v \in V} \left(\frac{1}{2}\right)^{\frac{T_1(V, λ) - v}{λ}} \\ 1 &= \left(\frac{1}{2}\right)^{\frac{T_1(V, λ)}{λ}} \sum_{v \in V} \left(\frac{1}{2}\right)^{\frac{-v}{λ}} \\ 2^{\frac{T_1(V, λ)}{λ}} &= \sum_{v \in V} 2^{\frac{v}{λ}} \\ T_1(V, λ) &= λ \log_2{ \sum_{v \in V} 2^{\frac{v}{λ}}} \end{align*}

$F$ can then be defined in terms of $T_1$ .

F(V, λ, t) = \left(\frac{1}{2}\right)^{\frac{t - T_1(V, λ)}{λ}}

We still need a way to update the stored value though, so let’s consider what it would look like to merge visit sets when using $T_1$ .

\begin{align*} T_1(V_a \cup V_b, λ) &= λ \log_2\left(\sum_{v \in V_a} 2^{\frac{v}{λ}} + \sum_{v \in V_b} 2^{\frac{v}{λ}}\right) \\ &= λ \log_2\left(\sum_{v \in V_a} 2^{\frac{v}{λ}} \cdot \left(1 + \frac{\sum_{v \in V_b} 2^{\frac{v}{λ}}}{\sum_{v \in V_a} 2^{\frac{v}{λ}}} \right)\right) \\ &= λ \log_2\sum_{v \in V_a} 2^{\frac{v}{λ}} + λ \log_2\left(1 + \frac{\sum_{v \in V_b} 2^{\frac{v}{λ}}}{\sum_{v \in V_a} 2^{\frac{v}{λ}}} \right) \\ &= T_1(V_a, λ) + λ \log_2\left(1 + \frac{\sum_{v \in V_b} 2^{\frac{v}{λ}}}{2^\frac{T_1(V, λ)}{λ}} \right) \\ &= T_1(V_a, λ) + λ \log_2\left(1 + \sum_{v \in V_b} 2^{\frac{v - T_1(V_a, λ)}{λ}} \right) \\ \end{align*}

It’s not pretty, but we’ve successfully defined $T_1(V_a \cup V_b, λ)$ in terms of $T_1(V_a, λ)$ and $V_b$ . This buys us a few niceties:

We only need to store a single number
If we only care about the ranking, we don’t need to calculate any scores at query time since $T_1$ provides an equivalent ranking to $F$
Since $T_1$ is directly comparable between entries and never needs recalculated unless updated, we can use it to build an index, storing our entries in sorted order

In some cases, we have extra information that we want to incorporate. For example, in Firefox, if a user types a URL, it gets a massive boost compared to if the user navigated to a URL via a link.

Let’s say we want to be able to weight a visit by multiplicative factor $\omega$ such that $\omega = 2$ is scored as if the entry was visited twice. A new score can be defined using a set of weighted visits $V_\omega = \{(v_1, \omega_1), (v_2, \omega_2), \ldots, (v_n, \omega_n))\}$ .

F(V_\omega, λ, t) = \sum_{(v, \omega) \in V_\omega} \omega \left(\frac{1}{2}\right)^{\frac{t - v}{λ}}

Repeating our derivation from above,

T_1(V_\omega, λ) = λ \log_2{ \sum_{(v, \omega) \in V_\omega} \omega 2^{\frac{v}{λ}}}

And the formula for updating:

\begin{align*} T_1({V_\omega}_a \cup {V_\omega}_b, λ) &= T_1({V_\omega}_a, λ) + λ \log_2\left(1 + \sum_{(v, \omega) \in {V_\omega}_b} \omega 2^{\frac{v - T_1(V_a, λ)}{λ}} \right) \\ \end{align*}

And that's it! ...TODO: except it's super overflowy. Talk about softmax and the log-sum-exp trick.

This is all well and good, but it’s pretty meaningless if it doesn’t improve real-world outcomes. I started trying to run an A/B test on myself, but quickly realized it was going to take much too long to gather a meaningful amount of data.

Then it struck me that I already have a convenient data set right at my fingertips: commit history! Each commit has a timestamp and a list of modified files, so I can evaluate how well various ranking strategies predict what files I’ll be working on next.

I don't want this somewhat-unnecessarily-long-and-math-heavy post to give the impression that this is a complex thing to use. To prove it, here is a fully functional implementation in 14 lines of (SQLite-flavored) SQL. Give it a try!

CREATE TABLE frecency (
	name TEXT PRIMARY KEY NOT NULL,
	t_unit_frecency REAL NOT NULL
);

CREATE INDEX frecency_score_idx ON frecency (t_unit_frecency DESC);

-- Add a visit for an entry. The parameter is the entry name.
INSERT INTO frecency (name, t_unit_frecency) 
VALUES (?, unixepoch()) 
ON CONFLICT (name) DO UPDATE SET 
	t_unit_frecency = t_unit_frecency 
		+ 604800 * log2(1 + pow(2, (unixepoch() - t_unit_frecency) / 604800));

-- Return the top ten items with the highest frecency scores
SELECT name
FROM frecency
ORDER BY t_unit_frecency DESC
LIMIT 10;

When trying to combine frecency with other ranking inputs (like boosting exact substring matches in a fuzzy finder), it can be annoying that the frecency score is unbounded because it’s difficult to predict and limit how much frecency will impact the final ranking. One way to solve this is to remap the score to a range between 0 and 1.

Any monotonically-increasing function that maps from $\mathopen[0,\infty\mathclose)$ to $\mathopen[0, 1\mathclose)$ will do the trick (“the trick” meaning “maintain the same ranking”), but I particularly like $\frac{S}{1 + S}$ .

For one, it’s simple. But it’s also meaningfully interpretable as the relative contribution of the current score to a new score if another visit were to be added. Intuitively, if the score is currently low, it won't be a significant factor in the new score, which will be dominated by the a new, un-decayed visit.

If you’re familiar with cache eviction algorithms, you might have drawn a connection between cache eviction and ranking. At a high level, they have the same goal: predict which things are most likely to be useful in the future. And, in fact, common cache eviction algorithms like ARC do use a form of frecency by maintaining both LRU and LFU lists.

For user-facing ranking though, our goals our slightly different because we care much more about the most relevant results than the least relevant. Also unlike cache eviction, we care about applying a meaningful order to a filtered set of results, so we need to maintain ranking information even for rarely-relevant items.

TODO: review the cache eviction literature to see if I can find the one I'm thinking about

Frecency Ranking

Frecency in the Wild

A Satisfying Formulation

Visits are Independent

A Smooth Transition

Compressibility

Adding weights

Measuring Performance

A Simple API

Bonus material

Remapping the Range

Frecency in Cache Eviction