Repository: UKPLab/sentence-transformers
Issue category: Bug Report

Issue:
Same order of training samples with `NoDuplicatesBatchSampler`
It seems that  `NoDuplicatesBatchSampler` produces the same set of batches in the same order regardless of the epoch index.
Indeed, in [this piece of code](https://github.com/UKPLab/sentence-transformers/blob/e156f38b1007e7860218c27223e1d577f3a021fe/sentence_transformers/sampler.py#L184C3-L187C102), the order of the indices in `remaining_indices` does not depend on the random permutation `torch.randperm(len(self.dataset), generator=self.generator)` as it is reset to the ordered range with `set`.

Moreover, the seed in line 185 does not change from one epoch to another (the [`set_epoch`](https://github.com/UKPLab/sentence-transformers/blob/e156f38b1007e7860218c27223e1d577f3a021fe/sentence_transformers/sampler.py#L32) method does not seem to be used...)






Hints:
Hello!

`set_epoch` is used via the `transformers` `Trainer` which calls `set_epoch` of the `accelerate`-wrapped DataLoader, which should propagates it down into the sampler. However, it indeed seems that `accelerate` only propagates it into the `sampler`, not the batch sampler: https://github.com/huggingface/accelerate/blob/8ade23cc6aec7c3bd3d80fef6378cafaade75bbe/src/accelerate/data_loader.py#L591-L592
Perhaps this warrants a feature request/pull request on `accelerate` @muellerzr

As for the `set` - well spotted. I was falsely under the impression that the insertion order was kept, much like for `dict` instances. I'd like to avoid converting `remaining_indices` into a list, as that has an expensive `pop`. I'm open to suggestions here. 

- Tom Aarsen
It might be not the most elegant solution, but maybe remaining_indices could be an `OrderedDict`?
`remaining_indices = OrderedDict({k: None for k in torch.randperm(len(self.dataset), generator=self.generator).tolist()})`

It probably won't be as fast as with the set (because the `OrderedDict` will need to maintain the order after each deletion), but deleting an element from an `OrderedDict` is still of constant complexity in average.
I was also considering a dict. Because we're at Python 3.7+ now, I think we can just use a normal `dict`: 
> the insertion-order preservation nature of [dict](https://docs.python.org/3/library/stdtypes.html#typesmapping) objects [has been declared](https://mail.python.org/pipermail/python-dev/2017-December/151283.html) to be an official part of the Python language spec.

from https://docs.python.org/3/whatsnew/3.7.html

If the performance hit is not too large, then this is an acceptable solution I think.

I'll also look more into fixing the `set_epoch` issue in `accelerate`.

- Tom Aarsen
Yes, I agree. A normal dictionary can also be considered.

Even though, the behavior might be slightly less predictable. Because the declared "insertion-order preservation" does not necessarily mean the preservation of the order after the deletion of some elements.

Patch:
diff --git a/sentence_transformers/sampler.py b/sentence_transformers/sampler.py
index 7efc19bf1..f3021b42f 100644
--- a/sentence_transformers/sampler.py
+++ b/sentence_transformers/sampler.py
@@ -184,7 +184,10 @@ def __iter__(self) -> Iterator[list[int]]:
         if self.generator and self.seed:
             self.generator.manual_seed(self.seed + self.epoch)
 
-        remaining_indices = set(torch.randperm(len(self.dataset), generator=self.generator).tolist())
+        # We create a dictionary to None because we need a data structure that:
+        # 1. Allows for cheap removal of elements
+        # 2. Preserves the order of elements, i.e. remains random
+        remaining_indices = dict.fromkeys(torch.randperm(len(self.dataset), generator=self.generator).tolist())
         while remaining_indices:
             batch_values = set()
             batch_indices = []
@@ -209,7 +212,8 @@ def __iter__(self) -> Iterator[list[int]]:
                 if not self.drop_last:
                     yield batch_indices
 
-            remaining_indices -= set(batch_indices)
+            for index in batch_indices:
+                del remaining_indices[index]
 
     def __len__(self) -> int:
         if self.drop_last:


Test patch: