`reduce` is under-specified for non-commutative operations over multiple axes

[jakevdp]

What happened?

Reported to JAX at jax-ml/jax#36011 (click through for a JAX reproduction).

TL;DR: reduce requires a monoid, which guarantees associativity but not necessarily commutativity. For non-commutative reductions when multiple dimensions are specified, the order of the reduction over dimensions can affect the output, but the StableHLO spec does not specify which order should be used.

As I see it, there are three options here for StableHLO:

1. support non-commutative reductions & specify a particular reduction order in the multi-axis case (possibly with a user-defined order).
2. support non-commutative reductions but explicitly state that reduction order is platform-dependent.
3. explicitly disallow non-commutative reductions in the spec.

[carlosgmartin]

To echo my comment here, I think option 2 is likely to lead to bugs, and therefore oppose it.

[jakevdp]

To echo my comment here, I think option 2 is likely to lead to bugs, and therefore oppose it.

Option 2 would be the easiest solution, to be honest, and from the user side all you'd have to do is avoid multi-axis reductions when your operator is not commutative. Both the examples you give in your linked comment (a chain of matrices, a chain of affine maps) are inherently 1D and would not be affected.