---
title: "Subtree reconfiguration"
description: "Use dynamic programming to recombine a subtree with fixed local inputs and output, accepting only objective improvements."
eyebrow: "Path-search algorithms"
---

## Recombining local inputs {#reconfiguration}

Subtree reconfiguration selects a local root in an existing contraction tree, expands downward to obtain several input nodes, and recombines them with [subset dynamic programming](/docs/structured-search#optimal-dp).

A local input can be an original tensor or the result of a subtree. Each input's internal structure, local output indices, and external connections stay fixed; only the contraction order among these inputs changes.

```diagram
subtree-reconfiguration
F₀…F₃ are fixed local inputs. Both trees preserve the same inputs and output; the original tree is replaced only when the candidate's objective value is sufficiently low.
```

Costs are computed solely from indices and dimensions; **no numerical contraction is performed**.

## Search procedure {#search}

```pseudocode
tree = initial contraction tree
For at most max_sweeps rounds:
    For each local root in the tree:
        inputs = at most subtree_size local inputs after expansion
        candidate = solve the small network by subset DP with fixed local output
        If the objective improves beyond numerical tolerance, attach candidate to tree
    Stop if this round makes no improvement
return the path represented by tree
```

Local updates use the same [optimization objective](/docs/path-metrics#definition) as the complete path. An update is accepted only if its improvement exceeds numerical tolerance, unlike [simulated annealing](/docs/tree-search#annealing), which may temporarily accept worse states.

## Interfaces and stopping conditions {#interfaces}

`reconfigure_path` accepts an existing path, the local size `subtree_size`, and sweep limit `max_sweeps`. `subtree_size=8` means at most eight local inputs, each of which may be an original tensor or an existing subtree. See the [Rust API](/docs/rust-api#reconfigure-path) for the full signature.

Final subtree reconfiguration in Light and Heavy can also stop early based on relative improvement: after the minimum sweep count, it stops if improvement stays below a threshold. It can also converge naturally when no acceptable improvement remains.

Dynamic programming optimizes only the local problem with fixed inputs, output, and allowed partitions; it does not guarantee global optimality for the entire tree.