13.18.3 Tensor Contraction Cost Intermediate Size

Tensor Contraction Cost Intermediate Size refers to the computational effort required for contracting tensors of moderate dimensionality in algebraic operations.

Tensor Contraction Cost Intermediate Size is the number of components stored in a partially contracted tensor produced midway through a multi-step contraction sequence, treated as a distinct cost driver in its own right, since the size of this intermediate result directly determines the workload of every subsequent step that consumes it.

Definition

For an intermediate tensor $T_{i}$ arising after step $i$ of a contraction sequence, with free indices ranging over sizes $n_{1}, \dots, n_{s}$ , the intermediate size is:

size (T_{i}) = n_{1} \times \dots \times n_{s}

This value is tracked separately from the sizes of the original input tensors, since it depends on which indices happen to remain free at that particular stage of the sequence.

Why Intermediate Size Matters

Direct Multiplier for the Next Step

The cost of the step following the production of $T_{i}$ is directly proportional to $size (T_{i})$ , since every subsequent contraction must process each stored component of the intermediate tensor at least once.

cost of step i + 1 \propto size (T_{i})

Explaining the Sequence Cost Effect

The reason different groupings of the same contraction sequence yield different total costs is precisely that they produce intermediate tensors of different sizes at their first step, illustrating the mechanism underlying the sequence cost effect at a more granular level.

Minimizing Peak Intermediate Size

Strategy Consideration

A grouping that keeps every intermediate tensor small throughout the sequence tends to minimize total cost, since it avoids situations where a large intermediate tensor must be fully materialized before it can be reduced further by a later step.

Trade-Off With Memory

Even when two groupings achieve comparable total operation counts, the one with a smaller peak intermediate size is often preferable in practice, since it requires less memory to store the intermediate tensor while the remaining steps are carried out.

Diagram Comparing Two Intermediate Sizes

Relation to Cost Analysis

Intermediate size is one of the core quantities tracked during a full cost analysis of a contraction sequence, alongside the cost index range of each individual axis; while the cost index range determines the per-step cost formula, the resulting intermediate sizes determine how that formula compounds across the successive steps of the entire sequence.