---
title: "Greedy and randomized greedy search"
description: "Greedy search selects tensor pairs step by step; randomized greedy search generates multiple paths and compares their complete-path objectives."
eyebrow: "Path-search algorithms"
---

## Greedy search: selecting tensor pairs {#greedy-loop}

Greedy search selects one tensor pair at a time, records the contraction, and replaces the pair with its result. It updates index structure without performing array computation.

The basic local score is:

$$
c(A,B)=|C|-\alpha\bigl(|A|+|B|\bigr).
$$

$C$ is the contraction result, $|\cdot|$ denotes element count, and $\alpha$ corresponds to `costmod`. Lower scores take priority. This score selects the next step; it is not the [complete-path optimization objective](/docs/path-metrics#definition).

The following pseudocode omits candidate-set maintenance:

```pseudocode
path = []
while there are candidate tensor pairs sharing an index:
    (A, B) = candidate with the lowest local score
    C = compute the contraction result index structure
    Append (A, B) to path
    Replace A and B with C and update candidates
Merge remaining components by outer product in increasing tensor size
return path
```

A shared index is eliminated in a step only if it is absent from the output and no other tensor still uses it.

## Randomized greedy search: comparing trials {#greedy-vs-random}

`random_greedy` repeatedly generates complete paths using different parameters. At positive temperature, it also samples with weights from a window of leading candidates, rather than always choosing the top candidate.

```pseudocode
Run ntrials attempts in parallel:
    parameters = parameters for this attempt
    path = generate a greedy path using parameters
    score = objective value J(path) of the complete path
return the path with the lowest score
```

The first three trials, when present, use zero-temperature starts with `costmod=1, 4, 8`; subsequent trials sample parameters randomly. Trials can run in parallel, but contraction choices within one path remain sequential.

This temperature controls tensor-pair selection; it differs from the temperature used to accept tree changes in [simulated annealing](/docs/tree-search#annealing).

## Interfaces {#public-api}

| Entry point | Purpose |
| --- | --- |
| `greedy` | Generate one deterministic greedy path |
| `random_greedy` | Run the specified number of trials and return the path with the lowest objective |

Randomized greedy search selects candidates using the objective for the current call. In the automatic [Light and Heavy](/docs/auto-light-heavy) pipeline, the top-level interface supplies the objective. Standalone calls use the library [default weights](/docs/path-metrics#definition) unless an objective is specified. See the [Rust API](/docs/rust-api#random-greedy) for usage. `ntrials` must be at least 1. Neither greedy nor randomized greedy search guarantees global optimality.

### Parallelism {#parallelism}

Thread count determines how many trials can run concurrently; it does not automatically increase `ntrials`. See the [Rust API](/docs/rust-api#greedy) for full parameter and return types.