Path metrics and objectives

Compare paths using FLOPs, logical memory traffic, and memory-related metrics, and configure objectives and slicing limits.

On this page

The six PathStats metrics

PathStats computes work estimates and tensor sizes from network structure and contraction order, without numerical arrays. Three metrics accumulate computation and data access over the path; the other three describe tensor sizes relevant to memory requirements.

log10 and log2 in field names indicate logarithmic values. For example, log10_flops=6 means $10^6$ scalar multiplications, and log2_max_size=20 means the largest result contains $2^{20}=1{,}048{,}576$ elements. Compare logarithmic values directly for the same metric: smaller values mean less work or smaller tensors.

Let the inputs and result of pairwise step $s$ be $A_s$ , $B_s$ , and $C_s$ . Write $|X|$ for tensor element count and $F_s$ for the scalar-multiplication count at that step.

Field	Definition	What it measures
`log10_flops`	$\log_{10}\sum_s F_s$	Scalar multiplications over the complete path
`log2_total_size`	$\log_2\sum_s\lvert C_s\rvert$	Elements written across all results
`log2_read_write`	$\log_2\sum_s(\lvert A_s\rvert+\lvert B_s\rvert+\lvert C_s\rvert)$	Logical reads and writes over the complete path

Traffic counts two input reads and one result write per step, with original inputs counted at their full array sizes. Written elements and read/write elements are therefore different quantities, and neither measures hardware memory traffic.

log2_total_size accumulates result sizes across steps. A previous result can be freed after use, so this sum does not imply that all those tensors reside in memory simultaneously; the peak metric below describes simultaneous live storage.

Per-step accounting

Per-step FLOPs are the product of dimensions of the indices participating in the pairwise contraction; result size is the product of retained-index dimensions. Complete-path metrics use logarithms to avoid overflow of linear counts on large networks.

The result retains indices in output and indices still used by tensors other than the two inputs. Other indices participating in the step are summed out.

Let $I(X)$ be the set of distinct indices of input tensor $X$ at this step, and $d_i$ the dimension of index $i$ . Then

F_s=\prod_{i\in I(A_s)\cup I(B_s)}d_i, \qquad |C_s|=\prod_{i\in I(C_s)}d_i.

This count includes indices summed out in the step. If the executor first performs unary reductions, actual operations may differ; this metric measures the structural cost of the given pairwise path. A complex scalar multiplication still counts as one multiplication and is not converted into real-instruction counts.

These measure the largest result tensor, total input-and-result size of a single step, and total live tensor size during execution. All are element counts, reported as base-2 logarithms.

Metric	Field	Accounting scope
Largest result tensor	`log2_max_size`	$\max_s\lvert C_s\rvert$ , including the final output
Largest single-step size	`log2_max_contraction_size`	$\max_s(\lvert A'_s\rvert+\lvert B'_s\rvert+\lvert C_s\rvert)$
Peak live tensor size	`log2_peak_size`	$\max_t L_t$ , where $L_t$ is the total element count of tensors not yet freed at time $t$

$A'_s$ and $B'_s$ are logical inputs after unary summation and diagonal processing. Peak accounting includes full inputs; each step counts the new result before freeing that step's inputs.

For the three-matrix product on the previous page, the input shapes are $2\times3$ , $3\times4$ , and $4\times5$ :

Metric (elements, without logarithms)	$(AB)C$	$A(BC)$
Largest result tensor	10	15
Largest single-step size	38	47
Peak live tensor size	46	53

Both paths start with 38 input elements. Their first steps produce eight or 15 elements, so the peaks are $38+8=46$ and $38+15=53$ . For $(AB)C$ , the final ten-element output is larger than the first eight-element result, giving a largest-result size of ten.

Multiply element count by bytes per element to estimate tensor data size. For example, 46 float64 elements occupy $46\times8=368$ bytes. This still differs from process RSS or device-memory usage: temporary transpose arrays, allocator overhead, and backend workspace are excluded.

target_size bounds pairwise-result elements within each slice; single-tensor networks also check the final output. It therefore bounds the intermediate size represented by log2_max_size. It does not cover every unary temporary, directly constrain log2_peak_size, or equal RSS or device-memory usage.

With multiple slices executing concurrently, total resident memory can substantially exceed per-slice path metrics. Record dtype, thread count, concurrent-slice count, and measured RSS when evaluating memory.

Defining the optimization objective

Path metrics describe computation and intermediate sizes; the objective determines how paths are ranked. PlannerObjective uses complete-path FLOPs $F(P)$ and logical reads/writes $R(P)$ :

J(P)=w_F F(P)+w_R R(P).

Default weights are flops_weight=1 and read_write_weight=64. The report field planner_objective_score_log2 stores $\log_2 J(P)$ .

For example, suppose two candidates have $(F,R)$ values of $(1000,100)$ and $(1200,50)$ . FLOPs alone favor the first. With default weights, their objectives are 7400 and 4400, favoring the second because it reduces logical traffic. Individual metrics preserve these differences; the objective supplies the ranking used for this search.

Weights	Objective label	Comparison
(1, 64)	flops_read_write	Weighted sum of FLOPs and logical reads/writes
(1, 0)	total_flops	Total FLOPs only
(0, 1)	total_read_write	Total logical reads/writes only

Weights must be finite, nonnegative, and not both zero. The weight 64 is a relative objective coefficient, not a byte count, cache-line size, or measured bandwidth.

Specifying weights in Python

python

from arctn import arctn_schedule

# Optimize by FLOPs only; omitting both weights uses the default values (1, 64)
report = arctn_schedule(
    inputs, output, size_dict,
    flops_weight=1.0, read_write_weight=0.0,
)

Changing weights may change candidate rankings, acceptance of local improvements, and the returned path.

Report field	Meaning
planner_objective	Objective label for the call; flops_weight and read_write_weight report the weights separately
planner_objective_score_log2	log2 of the final weighted path objective; includes all slices when slicing is enabled
log10_flops / log2_read_write	Metrics for the returned path on the unsliced network; for all-slice totals, read sliced_log10_flops_total and planner_log2_read_write respectively

The objective during search

Weights are fixed at the search entry point. Generators may use different local heuristics, but complete candidates, tree improvement, and final selection use the same PlannerObjective.

A local heuristic generates candidates; it is not the complete-path objective. For example, randomized greedy search uses a local cost to select the next tensor pair, while complete paths from multiple trials are compared by $J(P)$ .

Objective versus slicing constraints

The objective compares plan quality; target_size imposes a per-slice result-size limit. Even a very low-FLOPs plan cannot be returned as satisfying the constraint if it exceeds the requested size. Search penalties do not replace the final size check.

For a chosen slicing set, slice count is the product of its index dimensions. ArcTN compares sliced plans by per-slice work multiplied by slice count. In base-2 logarithms, the total objective is the per-slice log objective plus log2_n_slices.

\begin{aligned} N_{\mathrm{slice}}&=\prod_{i\in S}d_i,\\ J_{\mathrm{sliced}}&=N_{\mathrm{slice}}J_{\mathrm{one\ slice}}. \end{aligned}

$S$ is the slicing-index set. Taking logarithms gives:

\log_2 J_{\mathrm{sliced}}=\log_2 J_{\mathrm{one\ slice}}+\log_2 N_{\mathrm{slice}}.

This structural model counts pairwise contractions in each slice, but excludes the extra additions that combine slice results.

Metrics such as log2_peak_size and log2_max_contraction_size are still reported, but are not terms in the weighted objective above. See slicing and target_size for the constraint details.

Computing and comparing path metrics

Given a network and SSA path, simulate_path validates the path and computes PathStats, without numerical arrays or another search:

rust

let stats = arctn::simulate_path(&net, &ssa_path)?;
println!("{:?}", stats);

When comparing methods or libraries, compute metrics with the same implementation on identical networks and dimensions. Libraries may account for FLOPs, traffic, and unary operations differently; per-slice metrics are also not directly comparable to all-slice totals. See the benchmark suite for datasets and their uses.

Reporting an empty path

A single-tensor network can use an empty path with no pairwise steps. Rust then uses negative infinity for log10_flops, log2_total_size, and log2_read_write to represent zero work; log2_max_contraction_size is 0. log2_max_size uses the final-output size, while log2_peak_size still includes the full input.

Python reports likewise use -inf for zero work on an empty path, including log10_flops, log2_total_size, log2_read_write, and the objective. With slicing requested, sliced_log10_flops_total is also -inf. This is the logarithmic representation of zero work, not a search or execution failure.

Download source Markdown ↓