reduceLogSumExp reference decomposition contradicts conformance test; accuracy requirements missing

[mtavenrath]

Summary

The spec’s reference algorithm for reduceLogSumExp overflows for inputs that the conformance tests expect to succeed. Additionally, the spec does not define any accuracy or numerical stability requirements for this operation, making it unclear what a conformant implementation must do.

The contradiction

The spec defines reduceLogSumExp with this reference decomposition:

function reduceLogSumExp(builder, input, options) {
  return builder.log(builder.reduceSum(builder.exp(input), options));
}

However, the conformance tests include:

{
  'name': 'reduceLogSumExp avoids overflows caused by taking the exp of large inputs',
  'graph': {
    'inputs': {
      'reduceLogSumExpInput': {
        'data': [100.0],
        'descriptor': {shape: [1], dataType: 'float32'}
      }
    },
    'operators': [{
      'name': 'reduceLogSumExp',
      'arguments': [
        {'input': 'reduceLogSumExpInput'},
        {'options': {'axes': [0], 'keepDimensions': false}}
      ],
      'outputs': 'reduceLogSumExpOutput'
    }],
    'expectedOutputs': {
      'reduceLogSumExpOutput': {
        'data': [100.0],
        'descriptor': {shape: [], dataType: 'float32'}
      }
    }
  }
}

Tracing through the reference decomposition with this input:

exp(100.0) ≈ 2.69 × 10⁴³ → overflows float32 (max ≈ 3.40 × 10³⁸) → +inf
reduceSum([+inf]) → +inf
log(+inf) → +inf

Expected result: 100.0
Actual result from reference algorithm: +inf

The test name even acknowledges the issue (“avoids overflows caused by taking the exp of large inputs”), yet the normative algorithm does not avoid it.

Root cause

The log-sum-exp operation is numerically stable only when computed using the well-known max-subtraction trick:

reduceLogSumExp(x, axes) = max + log(sum(exp(x - max)))

where max = reduceMax(x, axes). This works because the outer log algebraically absorbs the exp(max) factor. Without the log wrapper (i.e., for plain reduceSum(exp(x))), no such trick is possible. The overflow is inherent to the result.

The entire purpose of reduceLogSumExp existing as a fused operation (rather than being decomposed by the user) is to enable this stable computation. The current spec text undermines that purpose.

Proposed fix

Replace the reference decomposition with the numerically stable formulation:

function reduceLogSumExp(builder, input, options) {
  const max = builder.reduceMax(input, { ...options, keepDimensions: true });
  const shifted = builder.sub(input, max);
  const sumExp = builder.reduceSum(builder.exp(shifted), options);
  const maxSqueezed = builder.reduceMax(input, options); // without keepDims
  return builder.add(maxSqueezed, builder.log(sumExp));
}

Add normative text stating that implementations must compute reduceLogSumExp using a numerically stable algorithm, or at minimum specify accuracy bounds, e.g., the result must not overflow for any input where the mathematically exact result is representable in the output data type.

Additional concern: underspecified accuracy for reductions generally

The broader reduction operations section does not specify accuracy requirements for any reduction op. For reduceLogSumExp specifically, this means an implementation that naively follows the decomposition and returns +inf for exp(89) inputs is technically spec-conformant — but fails the conformance tests. The spec should be clear about what it expects.

[fdwr]

The spec’s reference algorithm for reduceLogSumExp overflows for inputs that the conformance tests expect to succeed

That's no good - it's wrong for WPT to fail using the spec's decomposition, meaning we:

• (a) loosen the WPT's to the spec reference - this is viable as we already have boundary cases we can't ensure consistently across all backends (notably around data type limits and NaN's). So we could remove that particular case.
• (b) update the spec decomposition to yield a less infinitish result - this isn't the first time someone proposed the alternate more stable decomposition fix reduceLogSumExp, softplus, and tanh decompositions to not overflow so easily by vmukhachev.

I'm fine with either. The only gotcha might be is that if we change to more stable version, and there's a backend that uses the simplistic decomposition, then it could fail, and we'd have to emulate reduceLogSumExp on that backend to keep conformance (but that backend already would fail anyway). I bet most implementations use the more stable form though, and so it should be okay to switch it, would be more consistent with general practice, and would be more stable (albeit as a perf cost).

The broader reduction operations section does not specify accuracy requirements for any reduction op.

The WebNN spec doesn't list operator tolerances, as we worried the WPT and spec would just get out of sync, and thus thought the WPT should be the source of truth, but we do have some early issues recording our first stabs at per-operator tolerances.

• WPT tests tracker #265 (comment)
• WPT tests tracker / 2 for remaining ops #338 (comment)