SREA (Stochastic Ranking Error Analysis)

This repository contains the code accompanying the paper:

Debasis Ganguly (2026)

A Theoretical Framework for Risk Analysis of Stochastic Rankers

ICTIR 2026

Stochastic ranking policies introduce randomness into the ordering of retrieved documents, enabling objectives such as fairness and diversity. However, this randomisation also induces uncertainty in retrieval effectiveness.

This repository implements the experimental framework used to study reranking risk, defined as the change in effectiveness caused by stochastic rank perturbations applied to a fixed retrieved list.

The code is designed to:

• Quantify reranking-induced effectiveness variation

• Validate theoretical predictions under different perturbation models

• Compare empirical behaviour with asymptotic trends derived in the paper

• Analyse real-world stochastic ranking systems

• Reranking Risk

The change in effectiveness (e.g., DCG) induced by stochastic reranking.

• Uniform Perturbations

All rank swaps are equally likely, representing a worst-case scenario.

• Locality-Biased Perturbations

Rank movements are more likely to be small, reflecting realistic ranking policies.

• Evaluation Metrics

• Reciprocal Rank (RR)

• Discounted Cumulative Gain (DCG)

The main analysis is provided via a Jupyter notebook:

stochastic-reranker-analysis-cv

Open the notebook and execute the cells to reproduce the experiments.

The experimental pipeline follows these steps:

1. Load ranking data

   • Query-level ranked lists (e.g., TREC Fairness runs)
   • Relevance judgments (qrels)

2. Apply stochastic reranking

   • Uniform rank swaps
   • Locality-biased perturbations (distance-based kernels)

3. Measure effectiveness changes

   • Reciprocal Rank (single relevant document setting)
   • DCG (multi-relevance setting)

4. Estimate theoretical risk

   • Using derived asymptotic bounds

5. Compare theory vs. empirical observations

   • Pointwise comparisons
   • Distributional trends (head vs. tail analysis)

To reproduce the results in the paper:

1. Provide:

   • Ranking runs (e.g., TREC format)
   • Relevance judgments

2. Run the analysis notebook

3. The code will generate:

   • DCG comparison plots
   • Risk estimation curves
   • Rank displacement distributions

Typical outputs include:

• Predicted vs. observed effectiveness changes
• Distribution of rank displacements under different policies
• Sensitivity of results to parameters (e.g., locality parameter, calibration factors)
• Query-level reranking risk estimates

Theoretical analysis relies on simplified stochastic perturbation models, whereas real systems may include:

• Exploration strategies (e.g., $\epsilon$-decay)
• Metadata-driven adjustments (e.g., fairness constraints)

As a result:

• Exact pointwise agreement with theory is not expected
• The primary objective is to evaluate trend alignment and scaling behaviour

This framework can be extended to:

• Implement alternative stochastic ranking policies
• Evaluate additional ranking metrics (e.g., NDCG, ERR)
• Develop risk-aware reranking strategies
• Study query-specific or system-level variation in reranking risk

If you use this code, please cite:

@inproceedings{ganguly2026risk,
  title={A Theoretical Framework for Risk Analysis of Stochastic Rankers},
  author={Ganguly, Debasis},
  booktitle={ICTIR},
  year={2026}
}