---
title: "Annealing and replica exchange"
description: "Explore alternative contraction-tree structures with simulated annealing, or exchange search states across temperatures."
eyebrow: "Path-finding algorithms"
---

## Local changes to a contraction tree {#tree-neighborhood}

Simulated annealing and parallel tempering / replica exchange both start from an existing complete path. Local updates change how a few tree nodes are grouped without executing arrays.

```diagram
tree-rotation
a, c, and d can each represent a subtree. Rotation changes how they are combined, not their internal structures.
```

These methods can temporarily accept higher-cost states while separately retaining the best path seen.

## Simulated annealing {#annealing}

Higher temperatures make worse candidates easier to accept. As temperature falls, the search increasingly favors improvements. For energy increase $\Delta E$, the Metropolis acceptance probability is:

$$
p=\min\left(1,\exp\left[-\beta\Delta E\right]\right).
$$

$\beta$ is inverse temperature. In `treesa_path`, the energy in this expression is $E=\log_2 J$, where $J$ is the [complete-path optimization objective](/docs/path-metrics#definition). `anneal_path` instead computes acceptance from relative objective changes and relative temperature, so the same temperature parameters are not directly interchangeable.

```pseudocode
current = initial tree
best = initial tree
Search over the temperature schedule:
    Repeat local updates:
        candidate = apply a local rotation to current
        Use the Metropolis criterion to decide whether to accept candidate
        If accepted, set current = candidate
        If current sufficiently improves best, set best = current
return best
```

`anneal_path` runs one chain; `anneal_paths` runs independent chains in parallel from the same starting point; `treesa_path` sweeps the tree at progressively increasing inverse temperatures. All return one best path.

## Replica exchange {#tempering}

Multiple replicas search at different temperatures. After each round of local search, exchanges between adjacent-temperature states are attempted. This exchange step distinguishes the method from independently running several annealing chains.

```diagram
parallel-tempering
Temperature positions stay fixed; tree states are exchanged. P and Q accept the exchange, while R and S stay in place.
```

```pseudocode
Initialize replicas at different temperatures from the starting path
Repeat search rounds until the round limit or stopping condition:
    Run local searches for all replicas in parallel
    Try swapping replica states at neighboring temperatures
    Update the best path seen so far
return the better of the historical best and best starting paths
```

Rotations within each replica are accepted based on relative objective changes. Exchanges between adjacent replicas use $E_i=\ln J_i$ and $\beta_i=1/T_i$, with probability:

$$
p_{\mathrm{swap}}=
\min\left(1,\exp\left[(\beta_i-\beta_j)(E_i-E_j)\right]\right).
$$

`temper_path` initializes every replica from the same path; `temper_paths` can initialize from multiple paths. The replica count is not the number of returned paths: both functions return only one.

## Interfaces and local reconfiguration {#selection}

| Method | Interface |
| --- | --- |
| Simulated annealing | `anneal_path`, `anneal_paths` |
| Tree sweeps by inverse temperature | `treesa_path` |
| Replica exchange | `temper_path`, `temper_paths` |

See the [Rust API](/docs/rust-api#tree-search) for complete parameters, temperature definitions, and stopping settings. These methods retain the best input as a fallback, but do not guarantee global optimality.

### Periodic subtree reconfiguration {#reconfiguration}

Local search in replica exchange can periodically invoke [subtree reconfiguration](/docs/reconfiguration). It directly solves a small local network, rather than performing a single tree rotation.