Subtree reconfiguration

Use dynamic programming to recombine a subtree with fixed local inputs and output, accepting only objective improvements.

Recombining local inputs

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.

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.

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

Search procedure

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 as the complete path. An update is accepted only if its improvement exceeds numerical tolerance, unlike simulated annealing, which may temporarily accept worse states.

Interfaces and stopping conditions

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 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.