Query-Document Feature Extraction for Learned Ranking

A learned ranker needs numbers, and the numbers come from a feature extraction stage that runs over the retrieved candidate set. The extraction is where the engineering difficulty actually lives: the model is a gradient-boosted tree or a small neural network, and the features are what determine whether the model can learn anything. Getting the features right is a question about what information the index exposes and what it costs to compute, which is a different question from how to weight the results.

What a term score cannot represent

A BM25 score per query term compresses the document into a count. Everything about arrangement is lost. Consider the query “backward compatibility” against two documents of equal length with equal term counts:

doc A: ... backward ... (32 tokens) ... compatibility ...
doc B: ... backward compatibility is ... 

Both produce identical bag-of-words contributions. The second is the one a reader wants. Recovering that difference requires access to the positions of the terms, not just their counts, and positions are expensive enough that they are stored in a form that must be decoded at query time.

An inverted index stores, per term, a posting list of document identifiers, each carrying a frequency and, if positions are enabled, a list of token positions. The delta encoding of position lists (gaps between successive positions rather than absolute positions) keeps them compact, but decoding costs time proportional to the number of occurrences, which is exactly the quantity that dominates for common terms. This is where the cost of proximity features comes from: they are evaluated over the decoded position lists of every query term in every candidate document, and a ten-term query against ten thousand candidates can mean millions of position comparisons.

The features that come from a single term

Before proximity, there are features that need only one term’s occurrence structure.

Coverage is the fraction of query terms present in the document, and it is the cheapest strong feature available. It differs from a sum of term scores because a document matching eight of ten query terms with weak individual scores can outrank one matching three terms strongly, depending on the model. Coverage is computed at extraction time from the posting lists already visited.

Term frequency in a specific field is a refinement of the folded frequency used by BM25. Rather than one number per term, the extractor emits the count in the title, the count in the body, and the count in the anchor text, each normalized by the corresponding field length statistic. This is the point where the hand-designed field weights of the dismax approach become learnable parameters. See Disjunction-Max Combination for Multi-Field Scoring for what those weights were compensating for.

Saturation-transformed frequency is often emitted alongside raw counts. Because a tree-based model splits on thresholds, feeding it a value that has already been compressed by the saturation curve lets the model use a small number of splits where it would otherwise need many to approximate the curve.

First-occurrence position is a weak but surprisingly durable feature. A term appearing in the first hundred tokens of a body field is more likely to be part of the document’s actual subject than a term appearing once at the end. Normalizing by document length makes this comparable across documents.

Proximity: windows, spans, and the ordered-pair count

The standard family of proximity features is built on an ordered span: a window of $w$ tokens containing at least one occurrence of each of a chosen set of query terms. The minimal window containing all terms is the tightest evidence of a phrase-like relation.

A practical feature is the minimum window width for the full query, reported as a distance: 0 if the terms are adjacent in query order, larger as they spread apart, and a sentinel value when no window exists. The complement is the number of windows of width $w$ containing all terms, which measures how many times the phrase-like relation occurs rather than how tightly.

Computing the minimal window over two position lists is a linear merge. For more than two terms, the full minimal window problem is harder but the common approximation is to compute it greedily over sorted positions, which is exact for a small number of terms in practice and much cheaper.

def min_window(positions, limit=10_000):
    """positions: list of sorted position lists, one per query term."""
    idx = [0] * len(positions)
    best = limit
    while all(i < len(p) for i, p in zip(idx, positions)):
        lo = min(positions[t][idx[t]] for t in range(len(positions)))
        hi = max(positions[t][idx[t]] for t in range(len(positions)))
        best = min(best, hi - lo)
        # advance the list holding the smallest position
        for t in range(len(positions)):
            if positions[t][idx[t]] == lo:
                idx[t] += 1
                break
    return best

The loop advances the list with the smallest current position, which is the standard technique: shrinking the window from the left is the only move that can reduce the width, so the scan enumerates the minimal window in $O(\sum |p_t|)$ steps. Note the greedy tie-break: when two lists hold the same minimum, only one is advanced, and advancing the wrong one can skip a minimal window. Advancing all lists tied at the minimum is the correct variant.

A cheaper, coarser feature uses the same machinery over buckets rather than exact positions. Positions are quantized into blocks of 64 or 128 tokens, and proximity becomes “terms appear in the same block”. This trades precision for a large reduction in the number of list entries to merge, and it is robust to small differences in tokenization between the query and the document.

Computing features at query time versus index time

Proximity over the full candidate set is the expensive part, and there are two ways to avoid paying for it everywhere.

Index-time precomputation stores, for a fixed set of term pairs, the count of documents in which the pair appears within $w$ tokens. At query time the pair feature becomes a lookup rather than a merge. The limitation is that the pair set is fixed: a query containing two terms whose pair was not precomputed gets no feature, and the number of precomputed pairs scales quadratically in vocabulary size.

Two-stage extraction is the more general answer. A cheap first stage computes the bag-of-words features, applies the model, and keeps the top few hundred candidates. Only those are sent to the expensive stage that decodes positions and computes proximity. The first stage’s features are a strict subset, so the model has two variants, or two models, one for ranking the full set and one for reranking the head. The cascade’s recall is bounded by the first stage: a document that the cheap features place at rank 800 never gets the proximity features that would have promoted it. Choosing the cutoff is choosing that bound.

Feature independence and the redundancy trap

A model trained on features that are linear functions of one another cannot separate their contributions, and the tendency in feature design is to add near-duplicates. Frequency in the body, frequency in the body normalized by length, and a BM25 score for the term in the body are three views of nearly the same quantity. Adding all three does not add information; it adds variance in the estimated weights and slows training.

The features that carry genuinely new information are the ones that measure different things: coverage measures how much of the query is present, proximity measures arrangement, field frequency measures which part of the document matched, and the static features measure the document in the absence of the query. Four families, each with a small number of members, is a healthier design than forty variations on term frequency.

There is a second kind of redundancy that is harder to see: features computed over the same position lists are correlated through the document’s length. A long document produces more windows, larger counts, and higher coverage of everything. Without per-document normalization, the model can learn “length” as a feature through the back door, which is usually not the intent.

The leakage problem

A feature that encodes information about the label is worse than useless, because it produces a model that scores well on offline data and degrades once deployed. Two forms are common.

The first is query-level leakage: a feature computed from the whole candidate set, such as the maximum score across candidates, tells the model how difficult the query is. If the training data has harder queries labelled with fewer relevant documents, the model learns to predict label density from the query’s score range. This is not entirely useless, since query difficulty is real, but it is not a ranking signal, and it makes the model’s behaviour depend on the candidate set it was given.

The second is label-derived leakage: a feature that includes any aggregate of clicks or editorial judgments on the same query-document pair. It is easy to introduce accidentally when engagement signals are joined into the feature store, since the join key is the pair itself. The aggregate must be computed over a window that excludes the evaluation period, and even then the exclusion is by time, not by label.

Sparse features and the boundaries of the representation

Exact match between a query term and a document term produces a binary feature, and its negation, whether a near-miss morphologically or a synonym, produces nothing. Adding a stemmed-match feature and a synonym-match feature recovers some of that, at the cost of more feature families and a dependency on the analyzer that produced them.

The deeper boundary is that positional features are computed on tokens, and tokens come from an analyzer whose behaviour the feature extractor inherits. A document tokenized with a different stopword list than the query produces position lists that do not align, and the proximity window then measures something the reader would not recognize. Consistency between the indexing analyzer and the query analyzer is a precondition for every feature in this section, and it is the most common cause of proximity features that behave well on one corpus and badly on another.

When the feature set is settled, the next question is how the model is trained on it, which is the subject of Learning-to-Rank Objective Functions, and how the resulting scores are made comparable across queries, which is Score Calibration for Blended Ranking.