TL;DR
CompRank is a novel, token-efficient framework that drastically accelerates Large Language Model (LLM) reranking for long document lists. By decoupling document representations, compressing document tokens uniformly, and introducing a decoding-free attention scoring mechanism, it achieves up to a 9.5× speedup over generation-based listwise rerankers while retaining 98.7% of full-token ranking performance.
What Problem Does This Paper Address?
In modern Information Retrieval (IR) and Retrieval-Augmented Generation (RAG) pipelines, LLMs are frequently used as "rerankers" to fine-tune the order of documents retrieved by first-stage search models. While listwise LLM rerankers provide high precision by looking at multiple documents simultaneously, they hit a massive computational wall when candidate lists grow long (e.g., top-100 documents).
Two primary bottlenecks cause this:
- Quadratic Attention Cost: Standard Transformers perform full attention across all concatenated documents, leading to computational complexity that scales quadratically with the total number of tokens.
- Autoregressive Decoding Overhead: Most listwise rerankers are trained to generate document identifiers (like
[1] > [2] > [3]) token-by-token. This sequential generation is slow and highly prone to failure when scaling to longer lists than seen during training, often resulting in duplicate, missing, or out-of-range document IDs.
Methods
CompRank tackles these bottlenecks through three core architectural innovations:
- Document Representation Decoupling: CompRank organizes the input into independent document blocks followed by a query block. It applies an inter-document attention mask (preventing documents from attending to each other) and uses shared positional offsets. This eliminates sensitivity to candidate ordering and allows document Key-Value (KV) states to be pre-computed and cached independently of the query.
- Segment-Wise Token Compression: To reduce the query-document interaction cost, CompRank compresses the document-side KV states before query-side scoring. Among several strategies tested, Segment-wise Compression (retaining exactly one token every $k$ positions) proved most effective, providing uniform coverage across the document text.
- CopyNet-Style Decoding-Free Scoring: Instead of forcing the LLM to generate text strings of ranked IDs, CompRank extracts relevance scores directly from the internal attention weights of a single forward pass. It trains the model using a CopyNet-style pointer loss, maximizing the attention mass allocated from a query-side decision token to the positive document's tokens. Reranking then becomes a simple, parallelizable sorting task.
Datasets
The authors trained CompRank on a 50,000-example subset of the MS MARCO corpus (using the data construction pipeline from BlockRank).
For evaluation, they utilized seven diverse datasets from the BEIR benchmark:
- FiQA
- SciFact
- TREC-COVID
- DBPedia
- Climate FEVER
- NF Corpus
- SciDocs
Key Insights and Ideas
- Uniform Sampling Beats Saliency: Surprisingly, uniformly sampling tokens across a document (Segment-wise) preserves ranking signals much better than relying on the final tokens (Last-$k$) or using internal attention weights to select "important" tokens (Intrinsic Importance). Saliency-based methods often fail because document-internal importance does not necessarily align with query-specific relevance.
- The Fragility of Token Generation at Scale: Generation-based listwise rerankers suffer severe distribution shifts when evaluated on longer candidate lists than they were trained on. CompRank's decoding-free approach sidesteps this entirely, converting a sequential generation problem into a robust, parallelizable scoring problem.
Key Results
- High Performance with Minimal Tokens: Using a
Step-10segment-wise compression strategy, CompRank retains only 10.2% of document tokens but achieves an average NDCG@10 of 39.2 across the BEIR datasets, remarkably close to the 39.7 achieved under full-token attention. - Substantial Speedups: In scaling experiments on TREC-COVID, CompRank achieved an end-to-end speedup of 4.9× to 9.5× over generation-based listwise reranking (
Direct-List) when scaling candidate lists from 30 up to 500 documents. It also yielded a 1.3× speedup over its own full-token variant. - Extrapolation Stability: When trained on 30 documents and tested on up to 500, generation-based models break down due to decoding errors, dropping from 75.8 to 59.7 NDCG@10. CompRank remains highly stable, even improving to 79.5 NDCG@10 at 500 documents due to its robust attention-aggregation design.
Limitations and Future Work
While CompRank demonstrates excellent efficiency gains, the authors note a few limitations:
- Model Scope: The primary experiments were conducted using Mistral-7B as the backbone; validation across other large model families is still needed.
- Simulated Caching: Although the architecture mathematically allows for offline document KV-caching, the current evaluation pipeline still recomputes document blocks online. Fully optimizing a physical KV-cache storage and loading system remains future work.
- Static Compression: Static segment-wise compression might discard crucial information if the relevance evidence is highly localized or sparse within a long document. Developing adaptive, query-conditioned token selection mechanisms is a promising next step.
Summary updated