Symmetry-aware FLOP counting

How flopscope reduces the FLOPs charged for einsum, sum, mean, median, and friends when your tensors have symmetric structure.

You will learn:

The one mental model flopscope uses for all symmetry-aware FLOP savings
How that model applies to einsum
How it applies to reductions (sum, mean, median, …)
How to inspect what gets charged with flops.einsum_accumulation_cost and flops.reduction_accumulation_cost
When the savings don't materialize, and why

The mental model

When you declare symmetry on a tensor (with flops.as_symmetric) — or when flopscope detects it from a repeated operand object — some entries in the dense layout are mathematically interchangeable. An orbit groups together all entries that are interchangeable. flopscope charges one event per orbit, not per dense element.

For an (n, n) matrix declared symmetric in axes (0, 1), there are n*(n+1)/2 orbits among the n*n entries (the off-diagonal pairs share an orbit; diagonal entries are singleton orbits). Any cost that scales with "number of distinct entries" drops accordingly.

Einsum: one event per orbit of (multiplications, accumulations)

For an einsum, flopscope's charge in plain terms is:

total = (k − 1) × (unique multiplications across all operand axes) + (unique accumulations per output cell)

where k is the operand count. The savings come from output orbits — distinct output cells that flopscope can prove are interchangeable. The output gets symmetric structure either from declared symmetry on operands or from a repeated operand object appearing in multiple positions.

Worked example — triple outer product 'i,j,k->ijk' of three rank-1 vectors of length 4:

import numpy as np
import flopscope as flops

v1, v2, v3 = np.zeros(4), np.zeros(4), np.zeros(4)
print(flops.einsum_accumulation_cost('i,j,k->ijk', v1, v2, v3).total)  # → 192

v = np.zeros(4)
print(flops.einsum_accumulation_cost('i,j,k->ijk', v, v, v).total)  # → 60

When you pass three distinct vectors, every (i, j, k) output cell is its own orbit — 192 events. When you pass the same vector in all three operand positions, the operand swap induces an S₃ action on the output labels, collapsing the 64 dense output cells into 20 orbits — 60 events. The output is structurally symmetric and the cost reflects that.

The path that opt_einsum picks is irrelevant — the charge is path-independent. For multi-component expressions, each connected component is handled independently. Participants don't need to know which internal classifier fires for any given expression; only that the result is exact.

Reductions: `(unique inputs − unique outputs) + extra ops`

For reductions (sum, prod, max, min, mean, median, …), the formula is:

total = (unique input entries − unique output cells) + extra ops

The − unique output cells term is the off-by-one fix from #56: the first input element of each output cell is a free copy; only the remaining accumulations cost. So sum on (10,) charges 9 flops, not 10:

print(flops.reduction_accumulation_cost(np.zeros(10)).total)  # → 9

With declared symmetry, both terms drop. Summing a fully-symmetric rank-3 tensor:

T_dense = np.zeros((4, 4, 4))
T_sym   = flops.as_symmetric(np.zeros((4, 4, 4)), symmetry=(0, 1, 2))

print(flops.reduction_accumulation_cost(T_dense).total)  # → 63
print(flops.reduction_accumulation_cost(T_sym).total)    # → 19

mean adds one divide per unique output cell on top of the sum cost. median / percentile / quantile use a separate selection-style charge — see flops.tier2_reduction_cost(...).

Inspecting what gets charged

Two public inspection functions return the same AccumulationCost shape:

flops.einsum_accumulation_cost('ij,jk->ik', A, B).total
flops.reduction_accumulation_cost(T, axis=0).total

Both are LRU-cached; warm-call latency is in microseconds. See flops.einsum_cache_info() and flops.reduction_cache_info() for cache state.

When numbers might surprise you

The orbit savings come from the output having symmetric structure. Declared symmetry on an input doesn't automatically translate to savings — the question is always whether the output cells share orbits.

Gotcha 1 — input symmetry that doesn't reach the output. Declaring A symmetric in 'ij,j->i' doesn't save anything: the output index i doesn't share an orbit with anything under the (i, j) swap, so every output cell stays distinct.

A_dense = np.zeros((4, 4))
A_sym   = flops.as_symmetric(np.zeros((4, 4)), symmetry=(0, 1))
v       = np.zeros(4)

print(flops.einsum_accumulation_cost('ij,j->i', A_dense, v).total)  # → 32
print(flops.einsum_accumulation_cost('ij,j->i', A_sym,   v).total)  # → 32 (same!)

Gotcha 2 — reduction along an axis that breaks the symmetry. Summing along axis 0 of a (6, 6) S₂ matrix leaves a (6,) output. The (0, 1) swap doesn't fix axis 0, so the output has no residual symmetry and no savings appear:

S2 = flops.as_symmetric(np.zeros((6, 6)), symmetry=(0, 1))

print(flops.reduction_accumulation_cost(S2,              axis=0).total)  # → 30
print(flops.reduction_accumulation_cost(np.zeros((6,6)), axis=0).total)  # → 30
print(flops.reduction_accumulation_cost(S2).total)                        # → 20  (full reduction → saves)
print(flops.reduction_accumulation_cost(np.zeros((6,6))).total)           # → 35

If your symmetry savings aren't materializing, check whether the operation's output would still carry symmetric structure given how the indices flow.

What's actually happening

For curious contributor-level readers: the model is the α/M direct-event count, where α counts orbits of input entries projected onto the output and M counts orbits of inputs. The orbit calculation uses the pointwise symmetry group — the combination of declared symmetry on operands and the symmetries induced by repeated operand objects. The full classifier ladder (which picks between closed-form formulas like Young tableaux, singleton-cycle counts, and typed partition enumeration) lives in flopscope/_accumulation/_ladder.py and flopscope/_accumulation/_regimes.py.