One-sentence Summary

Researchers at the University of Glasgow introduce a trie-based experiment plan that replaces sequential linear plans for efficient comparative evaluation of cascading IR pipelines, achieving a $26\%$26% reduction in experiment duration on a BM25, MonoT5, and DuoT5 pipeline over MSMARCO v2.

Key Contributions

• The paper proposes a trie (radix tree) based experiment plan that identifies shared prefix overlaps across retrieval pipelines, enabling a single execution of common stages and reducing redundant computation in comparative IR experiments.
• Experiments on MSMARCO v2 with BM25, MonoT5, and DuoT5 demonstrate a 26% reduction in total experiment duration compared to a sequential execution plan.
• A user study with undergraduate and postgraduate students shows that the trie-based visualization improves understanding of pipeline structure, complementing the efficiency gains.

Introduction

Modern information retrieval pipelines often chain a fast first-stage retriever with progressively more expensive neural rerankers, and PyTerrier enables declarative composition of these cascades. A practical pain point is that experimenters evaluating many related pipeline variants waste significant computation re-running identical early stages, because PyTerrier’s existing optimisation only reuses the longest common prefix shared by every pipeline in an experiment. The authors introduce an experiment-planning approach that uses a radix tree (trie) to identify and reuse all shared prefixes across any subset of pipelines, transforming the set of pipelines into a minimal tree execution plan. This method reduces redundant work, yielding up to a 26% decrease in overall experiment duration on MSMARCO and improving clarity through the resulting pipeline visualisation.

Method

PyTerrier represents indexingand retrieval components, such as rankers, rerankers, and feature extractors, as transformers. Each transformer takes a dataframe as input and produces a transformed dataframe as output. These transformations typically act upon standard dataframe types, including documents, queries, retrieved documents $\mathcal{R} \subset \mathcal{D} \times \mathcal{Q}$R⊂D×Q, and question answers. A retrieval transformer $t$t can be executed upon a set of queries $Q \subset \mathcal{Q}$Q⊂Q using the notation $[t](Q)$[t](Q).

To combine different transformers, the framework implements a set of operators that allow for declarative expression. The >> operator, known as compose, enables multi-stage pipelines through transformer function composition, defined as $[[t_1 \gg t_2]](Q) := [[t_2]]([[t_1]](Q))$[[t1​≫t2​]](Q):=[[t2​]]([[t1​]](Q)). Other operators include rank cutoffs and linear combination, which can be applied to transformers within the pipeline. This notation allows researchers to express complex retrieval pipelines concisely.

Refer to the framework diagram:

The schematic above illustrates a multi-stage retrieval pipeline. The initial stage retrieves the top 100 candidate documents using BM25, applies MonoT5 to re-rank this candidate set, and finally applies DuoT5 pairwise re-ranking to the top 20 results to compute refined relevance scores and produce the final ranking.

PyTerrier extends this flexible pipeline construction model with a declarative API for evaluating and comparing retrieval pipelines. The pt.Experiment function provides an abstraction for comparative evaluation, accepting a list of retrieval pipelines, a set of queries, corresponding relevance assessments, and evaluation measures. It outputs a dataframe containing the computed measures for each system.

A key challenge with a declarative approach is the duplication of execution. For instance, in an experiment comparing multiple pipelines that share an initial BM25 retrieval stage, that stage would be executed multiple times. To address this, the authors propose experiment plans to decompose a set of pipeline comparisons involving shared components into a minimal set of executions. While earlier work utilized the longest common prefix algorithm to detect and reuse shared initial stages, this approach fails to optimize shared components that are not prefixes. To overcome this limitation, the authors formulate a tree experiment plan that identifies and reuses all possible shared prefixes by instantiating a trie data structure to detect overlapping pipeline prefixes, thereby avoiding redundant recomputation across the entire pipeline structure.

Experiment

The empirical evaluation compared linear, longest common prefix, and tree-based radix trie experiment plans on multi-stage pipelines using BM25, MonoT5, and DuoT5 over MSMARCO v1 and v2 corpora with TREC Deep Learning Track queries. The tree-based plan consistently reduced total execution time while preserving identical nDCG@10 scores, with larger savings when redundant retrieval on a bigger index was avoided. A user study with both undergraduate and postgraduate students confirmed that switching to the tree plan felt intuitive and that its live visualization helped participants understand how shared prefixes eliminate recomputation.

The tree-based experiment plan substantially reduces execution time compared to linear plans, cutting runtime by roughly a fifth on MSMARCO v1 and over a quarter on MSMARCO v2 while producing identical effectiveness scores. Linear plans with prefix precomputation offer minimal efficiency gains over the naive linear approach, with improvements under 6%. Relative to the linear baseline without precomputation, the tree plan executes roughly 19% faster on MSMARCO v1 and 26% faster on MSMARCO v2. Adding LCP precomputation to a linear plan yields only marginal speedups, reducing execution time by 1% on the smaller corpus and 6% on the larger one.

The evaluation compares tree-based and linear experiment plans on MSMARCO v1 and v2, with and without LCP precomputation. The tree plan cuts execution time by about 19% on v1 and 26% on v2 versus a naive linear baseline while producing identical effectiveness scores. Adding prefix precomputation to a linear plan yields only minimal speedups (up to 6%), indicating that the plan structure itself accounts for most of the observed gains.