[ScatterElements] Clarify the requirement on indices uniqueness

[masahi]

The spec of ScatterElements op doesn't tell if elements of indices tensor need to be unique or not along the scattered axis. I think there should be an explicit clarification on this, because it would determine if non-deterministic outputs from "embarassingly parallel" scatter implementation (e.g. on GPU) are allowed or not.

Here some data points for reference:

• ScatterND op spec does say indices must be unique.
• The PyTorch doc says indices must be unique.
• ONNXRuntime implementation of scatter op clearly does scattering in parallel, so it is making an implicit assumption that indices are unique.

[masahi]

cc @askhade @jcwchen What do you think?

[jcwchen]

Hi @masahi,
Thank you for providing the details. I think it makes sense to me. Could someone in @onnx/sig-operators verify this? Thanks.

[gramalingam]

I agree (personally speaking). I think an equivalent way of saying it is that the spec does not guarantee a specific execution ordering for the updates (and so a unique output is guaranteed only if there indices are unique). The question is: is there any user (model) that is assuming otherwise and has a dependence on it? It seems unlikely, but would be good to verify. Does TF have the same assumption?

[masahi]

TF also says the output is non deterministic if there are duplicated indices https://www.tensorflow.org/api_docs/python/tf/compat/v1/scatter_update

JAX too, https://jax.readthedocs.io/en/latest/_autosummary/jax.lax.scatter.html

So the industry clearly favors more performance than guaranteeing determinism. I highly doubt there is anyone relying on the deterministic result.

To be on the safe side and support both modes, we can add a new attribute to specify if indices are supposed to be unique or not. That's what I'm thinking I'll do for TVM, which currently guarantees determinism and hence slow.

[postrational]

I think we should avoid creating a new version of the operator, which acts a a superset of both behaviours. This would place the burden on implementors, to support both modes.

If the industry favours the parallel, non-deterministic approach, than we should document that this is what ONNX expects as well. If we do run into models, where this causes problems, we can come back to this issue and reconsider.

We should update our docs to be more explicit about the behaviour, but without introducing a new operator version.

[gramalingam]

I also agree. Let us clarify the specification, not add an attribute to support both mode now. We can add it if and when there is a need for the second mode.

[stale]

Is this still relevant? If so, what is blocking it? Is there anything you can do to help move it forward?

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs.

[jcwchen]

Reopen it since this issue hasn't been resolved yet.