Repository: pytorch
Issue: Tolerance for non-determinism operators in gradcheck
Labels: module: autograd,module: tests,triaged,module: determinism

For calls to gradcheck utilizing functions in:
https://pytorch.org/docs/stable/generated/torch.use_deterministic_algorithms.html
a `nondet_tol` value tentatively set to `1e-12` is now being passed. (edit: once https://github.com/pytorch/pytorch/pull/55237 lands)

Lets take the example of `scatter_add_`, which is used in the backward implementation of `cummin`
old gradcheck did not encounter non-determinism issues with scatter_add_ previously because it passes in one-hot vectors as  grad_out as to reconstruct the Jacobian row by row. This is no longer the case though with the new gradcheck, and we begin to see failures due to the nondeterminism of backward.

In the below output we see that the likelihood of nonzero differences increases as the size of the vector increases. And the magnitude of this difference scales linearly with the values of the 'src' tensor.

Since for sizes less than (20, 20), it may be difficult to observe the non-deterministic behavior, we preemptively set nondet_tol for gradcheck to some small value for all (most?) ops in the page linked above. (the list of offending ops was identified by running through test_ops/test_nn/test_autograd and setting torch.use_deterministic_algorithms(True) in gradcheck)

```python
import torch
import random
from statistics import stdev, median

def run(index, src, device, dtype):
    return torch.zeros(shape, dtype=dtype, device=device).scatter_add_(0, index, src)

for device in ("cpu", "cuda"):
    for one_hot in (True, False):
        for shape in ((18, 16), (100, 10), (1000, 10)):
            for scale in (1, 10, 100, 1000):
                dtype = torch.float64
                count = 0
                max_diffs = []
                for i in range(100):
                    index = torch.randint(0, shape[0], shape, device=device)

                    if one_hot:
                        src = torch.zeros(shape, device=device, dtype=dtype)
                        src.view(-1)[random.randint(0, src.numel() - 1)] = 1.0
                    else:
                        src = torch.rand(shape, device=device, dtype=dtype) * scale

                    out1 = run(index, src, device, dtype)
                    out2 = run(index, src, device, dtype)

                    if not torch.equal(out1, out2):
                        max_diffs.append((out1 - out2).max().item())
                        count += 1
                msg = f"device: {device}, one-hot: {one_hot}, shape: {shape}, scale: {scale}, count: {count}"
                if len(max_diffs) > 1:
                    msg += f" stdev max diffs: {stdev(max_diffs):.2}, median max diffs: {median(max_diffs):.2}"

                print(msg)
```

Sample output:
```
device: cuda, one-hot: True, shape: (18, 16), scale: 1, count: 0
device: cuda, one-hot: True, shape: (18, 16), scale: 10, count: 0
device: cuda, one-hot: True, shape: (18, 16), scale: 100, count: 0
device: cuda, one-hot: True, shape: (18, 16), scale: 1000, count: 0
device: cuda, one-hot: True, shape: (100, 10), scale: 1, count: 0
device: cuda, one-hot: True, shape: (100, 10), scale: 10, count: 0
device: cuda, one-hot: True, shape: (100, 10), scale: 100, count: 0
device: cuda, one-hot: True, shape: (100, 10), scale: 1000, count: 0
device: cuda, one-hot: True, shape: (1000, 10), scale: 1, count: 0
device: cuda, one-hot: True, shape: (1000, 10), scale: 10, count: 0
device: cuda, one-hot: True, shape: (1000, 10), scale: 100, count: 0
device: cuda, one-hot: True, shape: (1000, 10), scale: 1000, count: 0
device: cuda, one-hot: False, shape: (18, 16), scale: 1, count: 0
device: cuda, one-hot: False, shape: (18, 16), scale: 10, count: 4 stdev max diffs: 1.7e-15, median max diffs: 4.4e-16
device: cuda, one-hot: False, shape: (18, 16), scale: 100, count: 3 stdev max diffs: 1.6e-14, median max diffs: 2.8e-14
device: cuda, one-hot: False, shape: (18, 16), scale: 1000, count: 1
device: cuda, one-hot: False, shape: (100, 10), scale: 1, count: 39 stdev max diffs: 2.3e-16, median max diffs: 1.1e-16
device: cuda, one-hot: False, shape: (100, 10), scale: 10, count: 60 stdev max diffs: 2.1e-15, median max diffs: 1.8e-15
device: cuda, one-hot: False, shape: (100, 10), scale: 100, count: 62 stdev max diffs: 2e-14, median max diffs: 2.8e-14
device: cuda, one-hot: False, shape: (100, 10), scale: 1000, count: 65 stdev max diffs: 1.8e-13, median max diffs: 2.3e-13
device: cuda, one-hot: False, shape: (1000, 10), scale: 1, count: 100 stdev max diffs: 1.7e-16, median max diffs: 4.4e-16
device: cuda, one-hot: False, shape: (1000, 10), scale: 10, count: 100 stdev max diffs: 2e-15, median max diffs: 7.1e-15
device: cuda, one-hot: False, shape: (1000, 10), scale: 100, count: 100 stdev max diffs: 1.3e-14, median max diffs: 5.7e-14
device: cuda, one-hot: False, shape: (1000, 10), scale: 1000, count: 100 stdev max diffs: 1.5e-13, median max diffs: 4.5e-13
```

cc @ezyang @albanD @zou3519 @gqchen @pearu @nikitaved @soulitzer @Lezcano @Varal7 @mruberry @VitalyFedyunin @walterddr @kurtamohler