---
title: "Tensor networks and contraction paths"
description: "Describe tensor networks with indices and dimensions, represent contraction order using trees and paths, and validate inputs and paths."
eyebrow: "Core concepts"
---

## Representing a tensor network {#structural-model}

A tensor network specifies which tensors to multiply and which indices to sum over. An index labels a tensor axis: matrix rows and columns are two axes, and the length of each axis is its dimension. For example, the product of three matrices can be written as

$$
Y_{ad}=\sum_b\sum_c A_{ab}B_{bc}C_{cd}.
$$

`b` and `c` are summed indices; `a` and `d` remain as the two result axes. ArcTN optimizes the contraction order from these connections and dimensions without reading tensor values.

```diagram
tensor-network
Nodes represent tensors and edges represent shared indices; a and d at the ends are output indices.
```

### Writing ArcTN inputs {#example}

Let $A$, $B$, and $C$ have shapes $2\times3$, $3\times4$, and $4\times5$:

```python
inputs = [("a", "b"), ("b", "c"), ("c", "d")]
output = ("a", "d")
size_dict = {"a": 2, "b": 3, "c": 4, "d": 5}
```

- The outer order of `inputs` matches the input array order: A, B, C in this example, supplied as `[A, B, C]` at execution. Each tuple lists indices in array-axis order; for example, `("a", "b")` assigns a to the rows and b to the columns of the first matrix. It does not specify a contraction order.
- `output` specifies the result axes. Here a labels the rows and d the columns, giving shape `(2, 5)`.
- `size_dict` gives the dimension of each index. Matching labels refer to the same index, regardless of the names themselves.

The Python interface accepts hashable labels and converts them to integer IDs before entering Rust. With Quimb, pass `ArcTNOptimizer` directly and let Quimb supply the network information; see the [Quimb example](/docs/tutorial-quimb).

### Edges, hyperedges, and output indices {#edges-and-open-legs}

An index connecting two distinct tensors can be drawn as an ordinary edge; one connecting three or more distinct tensors is a hyperedge. Indices not listed in `output` are eventually summed out, while output indices are retained.

Two axes of the same tensor may also share a label. If that index appears in neither other tensors nor the output, it is traced out, as in $\sum_i A_{ii}$. Otherwise, a diagonal is taken first, retaining one index for subsequent contraction.

The same index may appear at most twice in a single input tensor. Three or more occurrences cause network validation to fail.

## Contraction trees and paths {#what-a-path-decides}

The network defines the tensor expression to compute, but not which tensors to contract first. In the example above, either $AB$ or $BC$ can be computed first:

$$
Y=(AB)C=A(BC).
$$

Both orders yield the same mathematical result, but differ in work and intermediate tensor sizes:

| Contraction order | First result | Total scalar multiplications | Largest contraction result (elements) |
| --- | --- | --- | --- |
| $(AB)C$ | $2\times4$ | $2\cdot3\cdot4+2\cdot4\cdot5=64$ | 10 |
| $A(BC)$ | $3\times5$ | $3\cdot4\cdot5+2\cdot3\cdot5=90$ | 15 |

The largest contraction result includes the final output. Although the first path initially produces 8 elements, the final output still has 10.

The parenthesization corresponds to a binary contraction tree: leaves are inputs, internal nodes are binary contractions, and the root is the final result. A path lists these steps in execution order. Independent steps within the same tree may be reordered.

### SSA paths: fixed tensor IDs {#ssa-path}

ArcTN internally uses static single assignment (SSA) paths. Each input and each step result has a fixed ID, and every new result receives a new ID. With `n` inputs, input IDs are `0..n-1`; step `s` produces ID `n+s`, with `s` starting at 0. The two tensors consumed by a contraction cannot be used again, and the result uses its new ID.

Integers in a path refer to whole tensors. They are distinct from index labels such as `"a"` and `"b"` in `inputs`, which label tensor axes.

For the $A(BC)$ order in the three-tensor example:

```text
Input IDs: A = 0, B = 1, C = 2
SSA path: [(1, 2), (0, 3)]

Step 0: contract B with C; assign result ID 3
Step 1: contract A with result 3; assign final result ID 4
```

### Linear paths: positions in the current list {#linear-path}

An opt_einsum linear path uses positions in the current tensor list. Each step removes its two input tensors and appends the result, changing later positions. After the first step above, `[A, B, C]` becomes `[A, BC]`, so the second step uses `(0, 1)`. The complete linear path is `[(1, 2), (0, 1)]`.

```python
from arctn import arctn_path

linear_path = arctn_path(inputs, output, size_dict)
ssa_path = arctn_path(inputs, output, size_dict, use_ssa=True)
```

SSA and linear paths are both lists of integer pairs, but their IDs mean different things. Specify the path format whenever saving or passing a path.

## Comparing candidate contraction trees {#candidate-set}

The same tensor network admits different contraction trees. Search methods generate and improve candidates, then compare their complete-path objective values. The diagram below shows five parenthesizations of four inputs A, B, C, D:

```diagram
auto-candidate-selection
The five trees represent candidates for the same network; P₄ is assumed to have the lowest objective value. The count and shapes are illustrative, not a fixed set of five candidates searched by Light or Heavy.
```

### Selecting by the objective {#selection}

Let $\mathcal C$ be the complete candidate paths included in the final comparison of this search, and let $J(P)$ be the objective of path $P$. Select

$$
P^* \in \operatorname*{arg\,min}_{P\in\mathcal C} J(P).
$$

$P^*$ is one of the candidates with the lowest objective. How FLOPs and read/write volume form $J(P)$ is explained in [Path metrics and optimization objective](/docs/path-metrics#definition).

The diagram compares unsliced paths. With slicing, comparison uses total work across all slices; dynamic slicing may also adjust the path. See [Slicing principles](/docs/slicing).

### What “best candidate” means {#optimality}

Light and Heavy return the best candidate found during the current search, without guaranteeing local or global optimality. `simulate_path` can independently validate a path.

### Parallel search and random seeds {#public-comparison-code}

`RAYON_NUM_THREADS` sets the width of the Rayon thread pool used for search, and `seed` sets the base random seed for the call. Ordinary use needs just one Light or Heavy search. For the distinction between thread configuration and repeated measurements, see [Using Heavy](/docs/tutorial-heavy#repeats) and [Single-machine parallelism](/docs/parallelism#auto-starts).

## Input validation {#validation}

Input validation first checks that the network is fully defined: at least one input tensor, positive integer dimensions for all indices, and unique `output` indices drawn from the inputs. `size_dict` must not contain unused entries. For example, omitting `"b": 3` above leaves the dimension connecting A and B undefined.

Execution also checks array counts and shapes. For example, `inputs[0] = ("a", "b")`, `size_dict["a"] = 2`, and `size_dict["b"] = 3` require the first array to have shape `(2, 3)`. A dimension mismatch or a tensor element count beyond the platform-representable range causes an error.

When constructing [`TensorNetwork`](/docs/rust-api#core-types) directly through Rust struct fields, call `validate()` explicitly.

### Path validation {#replay}

`simulate_path` checks each SSA step and computes `PathStats`. It processes only network structure and dimensions, without contracting actual arrays. See [Path metrics and optimization objective](/docs/path-metrics#recompute-and-compare) for metric definitions and examples.

Each step must reference two different, still-available tensor IDs. Exactly one result must remain at the end, with indices matching `output`. A single-tensor network may use an empty path; required summation, traces, or diagonals are handled by unary operations. See [Validating inputs and handling errors](/docs/validation).