Efficiency-Effectiveness Reranking FLOPs for LLM-based Rerankers

• LLM rerankers improve ranking quality but incur substantial compute, while latency, call counts, and token usage miss important cross-system cost differences.Source: §1 · p. 1
• RPP measures ranking quality per PetaFLOP, while QPP measures queries per PetaFLOP as a hardware-agnostic throughput metric.Source: §1 · pp. 1–2
• A closed-form, interpretable FLOPs estimator and open-source calculator estimate reranker compute without experiments across models and decoding settings.Source: §1 · p. 2
• The paper conducts the first large-scale study of the efficiency–effectiveness trade-off across LLM-based rerankers.Source: §1 · p. 2

2.1 LLM-based Rerankers

• Rerankers can score query-document pairs, compare documents pairwise, select among document sets, or directly generate a ranked list.Pairwise sorting embeds comparisons in sorting algorithms, while sampling aggregates wins; setwise methods output the best of three or more documents in one call (Zhuang et al., 2024).Source: §2.1 · p. 2

2.2 FLOPs Calculation

• Existing FLOPs profilers either lack token-level generation with KV-cache support or require full model execution, and none provide closed-form generation-aware estimation.Source: §2.2 · p. 2
• Prior reranking FLOPs estimates use coarse parameter-count rules or tooling that does not explain which factors determine the FLOPs count.Source: §2.2 · p. 3

3 Method

• The method estimates FLOPs for one LLM call, then combines call counts with that estimate to compare rerankers’ total compute.This provides the basis for comparing rerankers with different models, algorithms, and runtime choices.Source: §3 · p. 3

3.1 Metrics

• RPP and QPP compare rerankers’ effectiveness–efficiency trade-off without tying the evaluation to specific hardware.RPP measures ranking quality per compute, while QPP measures FLOPs-normalized throughput.Source: §3.1 · p. 3, §3.1.1 · p. 3, §3.1.2 · p. 3

3.1.1 Ranking metrics per PetaFLOP (RPP)

• RPP measures ranking metrics per PetaFLOP; higher RPP means better ranking quality for a fixed compute budget.The ranking metric can be NDCG, MRR, or MAP.Source: §3.1.1 · p. 3

3.1.2 Queries per PetaFLOP (QPP)

• QPP measures how many queries can be processed per PetaFLOP, capturing FLOPs-normalized throughput.Together, RPP and QPP trace the efficiency–effectiveness frontier.Source: §3.1.2 · p. 3

3.2 FLOPs Estimator

• The estimator models decoder-only and encoder–decoder rerankers using Transformer dimensions and a prompt-plus-output sequence.The prompt combines a task-specific prefix, query, and documents; the output is generated by the model.Source: §3.2 · p. 3

3.2.1 Decoder-only

• For decoder-only models, the estimator accounts for parameter and attention operations over the prompt and generated tokens.It estimates prompt length from the task prompt, query, and document list, using average document length.Source: §3.2.1 · pp. 3–4

3.2.2 Encoder-Decoder

• For encoder–decoder models, prompt-consumption FLOPs match the encoder-only estimate, while cross-attention setup adds a cost.Output-generation cost follows the decoder-only expression, with a different Ndec value.Source: §3.2.2 · pp. 4–5

Backbones

• Flan-T5 is the backbone for most rerankers; IRL and Tourrank use Llama-3.1-8B-Instruct because their longer contexts exceed Flan-T5’s input limit.Qwen2.5 models are also included to compare estimated FLOPs with profiler-reported FLOPs; they use grouped-query attention.Source: §4 · p. 5

Evaluation

• Rerankers are evaluated on TREC-DL19, TREC-DL20, and two BEIR datasets using the top 100 documents retrieved by BM25.Performance is reported using the new metrics.Source: §4 · p. 5

FLOPs measurement

• DeepSpeed’s FLOPs profiler and calflops produce identical measured FLOPs, so only one set is reported.BM25 FLOPs are reported in Appendix A.1.Source: §4 · p. 5

5 Experimental Results and Analysis

• Latency, call counts, and token counts miss aspects of compute: latency varies with hardware and runtime, while calls and tokens omit model size and sequence-length costs.On DL19, two 100-call pointwise methods have RPP 72.67 versus 61.89; scaling the backbone from large to xl to xxl drops RPP/QPP from 72.67/111.1 to 18.06/27.78 and 4.50/6.99.Source: §5 · p. 5
• TourRank with Llama-3.1-8B-Instruct achieves the highest NDCG on DL19 and DL20, but nearly the lowest RPP and QPP across the evaluated systems.Table 2 covers reranking the top 100 BM25-retrieved documents and reports NDCG@10.Source: §5 · p. 5, Table 2 · p. 6
• 72.67 RPP on DL19 and 68.3 on DL20, plus 111 queries/PetaFLOPs QPP, make pointwise.yes_no on Flan-T5-large the strongest reported pointwise variant.Pointwise methods yield 10%–30% relative NDCG gains over BM25 with negligible FLOPs compared with other LLM rerankers.Source: §5 · pp. 5–6
• 0.670→0.693→0.706 NDCG for setwise.Heapsort accompanies RPP 26.8→7.22→1.84 and QPP 40.0→10.42→2.61 as Flan-T5 scales from large to xl to xxl.Most rerankers gain NDCG from large to xl, with only marginal improvement from xl to xxl, while efficiency falls much more sharply.Source: §5 · p. 6
• Allpair sorting reaches 0.713 NDCG on Flan-T5-xl but uses 9,900 calls per query, with RPP around 0.10 and QPP 0.15; sorting variants remain orders less efficient than pointwise methods.Heapsort- and bubblesort-based variants cut calls by roughly 90%.Source: §5 · p. 6
• Estimated FLOPs follow linear trends with measured FLOPs across decoder-only and encoder-decoder models of varying sizes on DL19, with the same pattern on DL20.The comparison supports the estimator’s accuracy across model families and architectures.Source: Figure 1 · p. 6, §5 · p. 7
• 0.88 for Qwen-7B and 0.94 for Flan-T5-XXL are the Pearson correlations between latency and estimated FLOPs.Latency increases with FLOPs for both representative models, and estimated counts track the measured-FLOP relationship.Source: §5 · p. 7, Figure 2 · p. 7
• 1 is the reported Pearson correlation between prompt length and FLOP counts; estimated and actual FLOPs both rise as prompts lengthen.This prompt-length pattern is reported on DL19 and provides an additional check of the estimator.Source: §5 · p. 7, Figure 3 · p. 7

6 Conclusion and Future Works

• RPP and QPP quantify reranker performance, while a closed-form, interpretable calculator estimates FLOPs for LLM-based rerankers.The estimator is validated experimentally on decoder-only and encoder-decoder architectures, with estimated counts strongly linearly correlated with measured values.Source: §6 · p. 7
• Estimated FLOPs approximate real-world computational cost without requiring model execution.The conclusion bases this on the observed strong linear correlation with measured FLOPs.Source: §6 · p. 7
• Future work includes refining estimates through linear regression between measured and estimated FLOPs and adapting to more advanced architectures.Source: §6 · p. 7

Limitations

• The estimator assumes consistent implementation across frameworks, which library optimizations or kernel differences may violate.Its FLOP estimates may be less accurate for future models with more advanced architectures.Source: Limitations · p. 8
• FLOPs do not capture memory bandwidth, energy consumption, or inference-time variability under dynamic system loads.Source: Limitations · p. 8
• The estimator shows strong linear correlation with actual FLOP measurements, but its approximation may become less accurate for advanced architectures.Source: Limitations · p. 8

A.1 BM25

• BM25’s runtime FLOP estimate assumes term frequencies and inverse document frequencies are precomputed and excluded from scoring cost.Source: §A.1 · p. 10
• For reranking top-100 documents, the estimate uses query length LQ and document count ND = 100, and assumes every query token appears in every document.The all-tokens-appear assumption makes the estimate an upper bound.Source: §A.1 · p. 10
• When a query token is absent from a document, its term-document pair contributes zero FLOPs rather than 11.Source: §A.1 · p. 10

A.2 BEIR results

• Pointwise rerankers consistently achieve the strongest RPP and highest QPP, while stronger models improve performance at the cost of RPP and QPP.The same efficiency–effectiveness patterns appear on TREC-COVID and Robust04.Source: §A.2 · p. 10
• On TREC-COVID, Flan-T5-large setwise.heapsort versus setwise.bubblesort yields RPP 20.76 vs. 5.72 and QPP 27.03 vs. 7.52.Source: §A.2 · p. 10
• Scaling pointwise.yes_no reduces QPP from 100.00 to 26.32 to 6.58 on TREC-COVID and from 100.00 to 25.64 to 6.49 on Robust04, with modest NDCG gains.Source: §A.2 · p. 10