Inferring Query Intent from Click Entropy and Reformulation

A query string is a poor description of what a user wants. apple is a company, a fruit, a record label, and a Beatles album, and the string is identical in all four cases. The disambiguating evidence is not in the string; it is in what the user does next, and the two behavioural signals that carry the most information are where the clicks land and how the query is rewritten when the first attempt fails.

Both signals are observable without any explicit labels. That is what makes them useful: a system can derive intent classes from its own logs rather than from a hand-annotated set that goes stale.

Click distribution as a shape, not a count

For a given query, the clicks over some window form a distribution over the result set. The entropy of that distribution is a compact summary of how concentrated the interest is.

A navigational query, where the user wants one specific destination, produces clicks concentrated on one or two results, often at the top, and the entropy is low. An informational query that several documents answer well produces clicks spread over many results, and the entropy is higher. The measure is usually computed as

$$H(q) = -\sum_{d \in C(q)} p(d) \log_2 p(d)$$

over the documents receiving clicks, with $p(d)$ the share of clicks that went to $d$. The maximum possible value is $\log_2 |C(q)|$, so a normalized form divides by that bound to give a number in $[0,1]$ comparable across queries with different click volumes.

The raw number is unreliable at low counts. A query with three clicks has an entropy computed from three observations, and the estimate is dominated by noise. The practical fix is to require a minimum click volume before the statistic is used, and to smooth toward the collection’s mean entropy for queries below it. Shrinkage estimators do this formally; a threshold and a fallback do it informally and adequately.

Two confounds have to be removed before the statistic means anything. Position bias makes the top result receive clicks regardless of relevance, which lowers measured entropy for every query and compresses the differences between them. Clicks on the top result alone, with no clicks below, are consistent with both a perfect navigational answer and a user who clicked the first thing and left. Separating those requires the dwell or return behaviour described below.

The signals that separate satisfied from abandoned

A click is not evidence of satisfaction. The distinction that matters for intent is whether the user’s session ended after the click or continued.

Three observable events carry most of the information. A click followed by a return to the results page within a short interval suggests the destination did not answer the need. A click followed by no further query activity suggests it did. A reformulation, where the next query in the session modifies the current one, suggests the current results were inadequate in a specific way, and the direction of the modification is itself informative.

The last-click heuristic uses the final query in a session as the one that succeeded, on the assumption that the user stops when satisfied. This is the assumption behind learning-to-rank from query chains: a reformulation is evidence that the earlier query’s results were worse than the later query’s, and a pairwise preference can be extracted from the pair. The heuristic is wrong for sessions that end in frustration, and it is wrong for sessions that end because the user found the answer in the snippet without clicking. Both are known biases, and both are reasons to treat log-derived labels as noisy rather than as ground truth.

Session boundaries themselves are a decision. A common convention is a fixed idle timeout, with thirty minutes as a typical value, after which a new query is treated as a new session. Too short and multi-step tasks are fragmented; too long and unrelated queries are chained together.

Reformulation as a directed signal

Reformulations come in recognizable shapes, and each shape says something different about the failure.

A generalization removes terms: pizza new york brooklyn becomes pizza new york. This is what a user does after a query returns too few results, and it identifies the removed terms as over-constraining.

A specialization adds terms: pizza becomes pizza new york. This follows a query that returned too many, and it identifies the added terms as the discriminating ones.

A replacement substitutes a term for a near-synonym or a correction: receve to receive, or notebook to laptop. The first is a spelling correction and should be handled by the corrector described under edit-distance correction; the second is vocabulary mismatch and is what thesaurus expansion exists for. The log does not distinguish them by itself; string distance does.

A parallel move keeps the structure and swaps a slot: pizza new york to bagel new york. This indicates that the user is exploring a category, which is the strongest available signal for an exploratory intent, and it is the case where returning diverse results matters more than returning the single best match.

Classifying reformulations into these shapes is a string-alignment problem over the two term sequences, and the shapes are recoverable from the edit operations with reasonable accuracy. The classes then aggregate per original query: a query followed mostly by specializations behaves like an under-specified query, and one followed mostly by replacements behaves like a vocabulary problem.

Building the classifier from the signals

The output of this analysis is a small number of features per query, each with a direction:

• click entropy, normalized, low for navigational
• fraction of sessions ending after the first click, high for satisfied
• fraction of sessions with a reformulation within a short interval, high for inadequate results
• count of distinct reformulation shapes and their distribution
• whether the query contains a URL fragment or a site name, which is close to a direct navigational signal
• whether the query is a single rare term, which tends toward navigational or lookup

A classifier over these features does not need to be complex. The classes are coarse, the features are few, and a decision list or a shallow model trained on a few thousand queries is sufficient. The harder problem is keeping the labels current: intent drifts with the collection and with events, so a model trained once degrades.

import math
from collections import Counter

def click_entropy(clicks: Counter) -> float:
    total = sum(clicks.values())
    if total == 0:
        return 0.0
    h = -sum((c / total) * math.log2(c / total) for c in clicks.values())
    return h / math.log2(len(clicks)) if len(clicks) > 1 else 0.0

def intent_features(entropy: float, reformulation_rate: float,
                    ends_at_first_click: float) -> dict:
    # thresholds are policy, tuned per collection
    return {
        "navigational_score": (1.0 - entropy) * ends_at_first_click,
        "exploratory_score": entropy * reformulation_rate,
        "underspecified": reformulation_rate,
    }

The features are multiplied rather than summed because they are conjunctive: low entropy only implies navigational when the session also ends at the click. A low-entropy query with heavy reformulation is more likely a badly answered navigational query than a satisfied one.

What the labels are then used for

Intent labels change the retrieval configuration rather than the query string. A navigational query benefits from a strong prior on title and anchor text, from exact matching over expansion, and from returning one result rather than a page. An exploratory query benefits from diversification across results, from expansion, and from treating the top-ranked document as one of several rather than as the answer.

The label also gates rewrites. Expansion should be suppressed for navigational queries, where it dilutes the exact match, and enabled for exploratory ones. The threshold-on-results pattern described in synonym expansion is a cruder version of the same idea, and the two should not both fire.

The limitation is fundamental: the signals are only available for queries that have been seen enough times to accumulate behaviour. The long tail, which is most of the distinct queries in any log, has no clicks and no reformulations. For that portion, intent has to be inferred from the string itself, from the collection’s structure, or not at all. Systems that route on behaviour-derived labels must have a defined path for queries with no behaviour, and the natural default is the configuration that is least damaging when wrong: no aggressive expansion, no forced diversification, and a ranking that is correct for the average query rather than optimized for a class the system cannot detect.