---
icon: arrows-split-up-and-left
---
# Path Frank-Wolfe
The Path Frank-Wolfe algorithm extends Bellman-Ford with **split routing**: instead of sending the entire input through a single path, it discovers multiple candidate paths and optimally distributes the input across them. For large trades where price impact is a binding constraint, splitting across parallel paths can produce meaningfully better output than any single route.
## Overview
The algorithm runs in three stages:
1. **Initial route**: Run Bellman-Ford at full input to find the best single path
2. **Frank-Wolfe loop**: Iteratively discover additional paths and shift flow toward them
3. **Final comparison**: Return the split route if it beats the single-path result net of gas
The key insight is that price impact is the enemy. A constant-product pool that returns a good rate on 100 USDC returns a progressively worse rate as you push more through it. By splitting the same total input across multiple pools, each pool sees a smaller amount and operates at a better rate.
## When does splitting help?
The algorithm computes a **price impact estimate** before attempting any split. If price impact is negligible relative to gas costs, splitting can't pay for itself — extra swaps cost gas, and the marginal gain from reducing impact is too small. The algorithm skips the Frank-Wolfe loop and returns the single-path result directly.
Splitting is most valuable when:
* **Large trades relative to pool depth**: A trade of 10% of a pool's reserves has meaningful price impact; 0.01% does not.
* **Multiple parallel pools exist**: Splitting only helps when there are alternative paths to absorb the extra flow.
* **Multi-hop paths share entry pools**: Paths that start differently but converge on the same intermediate token can be split at the entry, reducing impact on all shared segments.
## Stage 1: Initial route
Bellman-Ford (BF) runs at the full order amount to find the best single-path route. This serves two purposes: it gives a quality baseline for the final comparison, and it provides an initial allocation — 100% of flow on one path — from which the Frank-Wolfe loop starts.
## Stage 2: Frank-Wolfe loop
### Probe amount
Before each iteration, the algorithm computes a **probe amount**: the minimum trade size where an additional path would pay for its gas cost. This is `gas_cost / price_impact`. If price impact has fallen enough (because prior splits already reduced it), the probe exceeds the configured `max_probe` cap and the loop stops.
### Finding a candidate path
To find the next candidate path, the algorithm constructs a **post-swap market state** that reflects the current allocation:
1. Simulate all current path allocations through their respective pools
2. Store the post-swap pool states as overrides
3. Zero out gas costs for pools already committed in the current solution (they are already executed once on-chain; their gas is already priced in)
Bellman-Ford then runs on this degraded state at `probe_amount`. It finds the best path *given that prior allocations have already moved the committed pools*. If a previously-committed pool has absorbed so much flow that its rate degraded, BF naturally routes around it.
### Duplicate detection
If BF returns the same path that already exists in the allocation (same sequence of `(pool, token_in, token_out)` triples), exploration is exhausted and the loop stops. Paths that share only a prefix but diverge at a later hop are not duplicates — shared prefixes are handled by the route builder, not by splitting.
### Line search
Once a candidate path is found, the algorithm uses **golden-section search** to find the optimal `step_size ∈ [0, 1]`: the fraction of total flow to shift from the existing allocation to the new candidate. At each probe point, the algorithm re-simulates all paths and computes total output; the step size that maximises output is selected.
This line search is the Frank-Wolfe "descent direction" computation. It runs `line_search_evals` function evaluations (default: 12), which is enough for ~4-5 decimal digits of precision.
### Applying the step
The chosen step size is applied:
* All existing path fractions are scaled by `(1 - step_size)`
* The candidate is added at `step_size`
* Paths whose fraction falls below `min_split` are dropped and the remaining fractions are renormalized
* All paths are re-simulated at their new allocations to refresh amounts and per-hop outputs
The loop then repeats with the updated allocation as the new starting point.
## Stage 3: Final comparison
After the loop completes (due to `max_paths`, timeout, price impact exit, or duplicate detection), the algorithm builds the full split route and compares it against the initial single-path result by **net amount out** (gross output minus gas cost). The better result is returned.
If only one path survived (because all splits were too small), the initial single-path result is returned directly without building a split route.
## Shared pools and route assembly
Paths can share intermediate pools. For example:
```
Path 1: WETH → [P1] → USDC → [P2] → DAI
Path 2: WETH → [P1] → USDC → [P3] → DAI
```
Both paths use pool P1. On-chain, P1 is called once with the combined WETH input; P2 and P3 each receive a fraction of the resulting USDC. The route builder:
1. **Merges shared hops**: identifies hops with the same `(pool, token_in, token_out)` across all paths and combines them into a single swap
2. **Assigns split fractions**: sorts within each branch by flow fraction (largest first); the last swap in each branch receives `split = 0.0` (the TychoRouter "use remaining balance" convention)
3. **Topological ordering** (Kahn's algorithm): swaps are emitted only after all upstream swaps producing their input token are done. This is necessary when paths of different lengths converge on the same intermediate token — the shared downstream pool must wait for all inflows to complete before its swap is emitted
Gas for shared pools is counted once, not once per path.
## Configuration
```toml
[pools.path_frank_wolfe_3_hops]
algorithm = "path_frank_wolfe"
num_workers = 4
max_hops = 3
timeout_ms = 500
```
The PFW-specific tuning parameters are not currently exposed in `worker_pools.toml`; they use defaults:
| `max_paths` | 4 | Maximum number of distinct paths to split across |
| `max_probe` | 25% | Probe amount cap as a fraction of total input |
| `min_split` | 5% | Minimum flow fraction for any path; smaller shares are dropped |
| `line_search_evals` | 12 | Golden-section evaluations per step size search |
## Design tradeoffs
### Versus Bellman-Ford
Bellman-Ford finds the best **single path**. PathFrankWolfe wraps BF and adds a split optimization layer on top. For trades with negligible price impact, PFW produces the same result as BF. For large trades with meaningful impact, PFW can produce better net output by spreading flow across multiple pools.
The cost is additional simulation work: each Frank-Wolfe iteration runs one BF solve plus `line_search_evals` evaluations of the total-output function. With `max_paths = 4` and `line_search_evals = 12`, the worst case is roughly 3 BF solves and ~36 path simulations on top of the initial BF run.
### Single-path fallback
The algorithm always compares the split result against the single-path baseline before returning. If the split route doesn't beat the single path net of gas (this can happen when the gas overhead of extra swaps outweighs the reduced impact), the single-path result wins.
### Timeout safety
The Frank-Wolfe loop checks elapsed time at the start of each iteration. If the timeout is exceeded, the loop stops and the algorithm proceeds with however many paths it has found. The result is always valid — just potentially less optimal than a full-budget run.
## Source reference
| `fynd-core/src/algorithm/path_frank_wolfe.rs` | Algorithm implementation and Frank-Wolfe loop |
| `fynd-core/src/algorithm/split_primitives.rs` | Shared primitives: path simulation, route assembly, line search |
| `fynd-core/src/algorithm/bellman_ford.rs` | Inner BF solver used for path discovery |
| `fynd-core/src/algorithm/mod.rs` | `Algorithm` trait definition |
| `fynd-core/src/worker_pool/registry.rs` | Maps `"path_frank_wolfe"` to `PathFrankWolfeAlgorithm` |
| `worker_pools.toml` | Worker pool configuration (add a `path_frank_wolfe` pool to enable) |