Algorithmic Replicability through Shared Randomness

27 concepts20 papers2 proposals

When two independent researchers train the same machine learning model on different samples drawn from the exact same population, they rarely end up with the identical model. Minor variations in sampling noise, combined with internal algorithmic randomness, cause their training trajectories to diverge. This variance lies at the heart of the modern reproducibility crisis in data science.

Traditional algorithmic stability frameworks, such as Differential Privacy (DP), protect against this divergence by ensuring that an algorithm's distribution of outputs remains relatively constant when the input data changes slightly. However, a stable distribution does not mean identical results; two draws from the same distribution can still yield entirely different hypotheses.

To bridge this gap, a new paradigm has emerged: algorithmic replicability. Formally introduced by Russell Impagliazzo et al. in Reproducibility in Learning, replicability demands a much stricter standard. A randomized algorithm is considered replicable if it outputs the exact same result with high probability when executed on two completely independent datasets from the same source, provided the algorithms share a common internal random seed.

Without Shared Randomness:
Dataset A ──> [ Randomized Learner (Seed 1) ] ──> Hypothesis X
Dataset B ──> [ Randomized Learner (Seed 2) ] ──> Hypothesis Y (Divergence)

With Shared Randomness:
Dataset A ──> [ Replicable Learner (Seed R) ] ──> Hypothesis X
Dataset B ──> [ Replicable Learner (Seed R) ] ──> Hypothesis X (Identical!)

The Intuition: Shared Randomness as a Rounding Grid

Why does a shared random seed allow different datasets to converge on the exact same output?

If an algorithm's internal random seed is kept private, randomness acts as an additional source of variance, compounding the differences between datasets. But when the random seed is shared across independent runs, it transforms from a source of noise into a coordinated, global anchor. As noted by Alkis Kalavasis et al. in On the Computational Landscape of Replicable Learning, this shared randomness distinguishes replicability from other privacy-centric stability notions, enabling a form of coordinated algorithmic stability.

To understand why this works, imagine a continuous space of possible solutions (such as the weights of a classifier). Dataset $A$ and Dataset $B$ provide slightly different empirical estimates within this space. A deterministic algorithm might split these estimates across a sharp decision boundary, leading to different outputs.

A replicable algorithm uses the shared random seed to construct a randomized "rounding grid" over the solution space. Because the grid is generated by the same seed, the grid lines are identical for both researchers. If the empirical estimates from Dataset $A$ and Dataset $B$ are close enough together, they will fall into the same cell of the randomized grid. The algorithm then "snaps" both estimates to the exact same canonical representative of that cell. The shared randomness ensures that the boundaries of the grid cells adapt to the data distribution, minimizing the probability that the two datasets fall on opposite sides of a line.

This concept is closely related to pseudo-determinism in computational complexity. As explored by Ofer Grossman et al. in Tight Space Lower Bound for Pseudo-Deterministic Approximate Counting, pseudo-deterministic algorithms use randomness internally but are constrained to output a unique, canonical result with high probability. This prevents adversaries or sampling anomalies from manipulating the specific solution returned, a property that Michel X. Goemans et al. demonstrate is vital for verifying distributed or cryptographic systems in Doubly-Efficient Pseudo-Deterministic Proofs.

Replicable Machine Learning and Clustering

Applying this rounding intuition to practical machine learning requires redesigning core optimization workflows.

For geometric problems, such as finding a separating hyperplane, Alkis Kalavasis et al. demonstrate in Replicable Learning of Large-Margin Halfspaces that combining dimensionality reduction with a structured rounding scheme forces identical model outcomes. The dimensionality reduction ensures that minor data variations are smoothed out, while the rounding scheme uses the shared seed to lock the final halfspace into place.

Unsupervised learning is notoriously sensitive to initialization and data perturbations; a single outlier can completely alter the cluster centers in a $k$-means algorithm. To address this, Hossein Esfandiari et al. introduced the first algorithms for Replicable Clustering. By leveraging shared randomness to define canonical spatial partitions, their algorithms guarantee that independent researchers drawing different subsets from the same population will arrive at the exact same partition of the sample space.

The framework has also been extended to dynamic environments. In Replicable Online Learning, Saba Ahmadi et al. prove that sequential decision-making algorithms can produce the exact same sequence of actions across different data streams while still minimizing cumulative regret, proving that adaptivity does not have to come at the cost of replicability.

Distribution Testing and Local Consistency

Beyond model training, replicability is transforming statistical verification and local computing.

Standard statistical tests often flip their conclusions when faced with edge-case data. To stabilize these tests, Sihan Liu et al. developed a framework for Replicable Uniformity Testing. By using a shared seed to govern the test's internal thresholds, they ensure that the test yields identical binary conclusions on identical distributions. This was expanded into a generalized "random walk" framework by Ilias Diakonikolas et al. in Replicable Distribution Testing, providing near-optimal bounds for testing properties like closeness and independence.

This consistency is also valuable when algorithms must make coordinated decisions without communicating. In Local Computation Algorithms for Knapsack: impossibility results, and how to avoid them, Clément L. Canonne et al. show that treating consistency as a replicability problem allows independent, localized queries to arrive at an identical global approximation. The shared randomness acts as a decentralized coordination mechanism, ensuring that disparate parts of a network respect the same global decision boundaries.

Fundamental Limits of Replicability

Replicability is a powerful guarantee, but it comes at a computational and statistical cost. How many random bits do we need to achieve this level of stability, and when is it mathematically impossible?

In The Role of Randomness in Stability, Max Hopkins et al. establish a "weak-to-strong" boosting theorem for randomness. They prove that the number of random bits required to make an algorithm replicable is fundamentally dictated by its global stability—the maximum probability that a completely deterministic version of the algorithm can output a single "heavy-hitter" solution. If a problem inherently lacks a dominant, clear-cut solution, a randomized algorithm will require significantly more random bits to successfully anchor independent runs to a shared outcome.

Furthermore, there are topological barriers to perfect replicability. By adapting classical theorems from algebraic topology, Bogdan Chornomaz et al. in Local Borsuk-Ulam, Stability, and Replicability demonstrate that certain continuous data spaces possess inherent geometric obstructions. When mapping high-dimensional data distributions to discrete algorithmic decisions, these topological boundaries make a certain degree of divergence unavoidable, mapping out the exact mathematical limits of what can be replicated.

Key Foundational Work

Forming Classifier Ensembles with Deterministic Feature Subspaces (2016) — contributed 1 concept elements to this direction.
How Should We Solve Search Problems Privately? (2010) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_algorithmic_replicability_c8f1c617,
  title = {algorithmic replicability},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/algorithmic-replicability/rdr_c8f1c617e4b7484abc1b278246eca95e},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_algorithmic_replicability_c8f1c617_v1,
  title = {algorithmic replicability},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/algorithmic-replicability/rdr_c8f1c617e4b7484abc1b278246eca95e/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake