DEV Community: Kyrylo Malovychko

The Best DTW Candidate Scored 9.97. That Still Wasn't a Decision...

Kyrylo Malovychko — Tue, 01 Sep 2026 15:38:14 +0000

I pointed a DTW scanner at the official Binance Spot ETHUSDT one-minute archive for July 2023.

The reference window was:

2023-07-01 12:13–12:23 UTC

The best non-overlapping candidate in the monthly scan was:

2023-07-27 17:45–17:55 UTC

The scanner returned:

distance=9.967796
path-steps=11
stretch-steps=2

Fine.

Is that a match?

No honest answer yet.

It is the smallest distance found under one preprocessing rule, one local cost, one Sakoe–Chiba window, and one slope penalty. The scanner found an argmin. It did not magically produce a trading decision.

That distinction is where most DTW demos stop being useful.

I also tried to use two Binance UI screenshots as provenance. I rejected them.

The visible price scales did not match the CSV rows used by the scanner: the reference file contains roughly 1925–1927, while the screenshot showed a different price region; the candidate file contains roughly 1864–1867, while its screenshot was around 1923–1929.

Wrong date, wrong market, wrong timezone, or a chart that never actually jumped to the requested archive — it does not matter. A pretty screenshot pointing at different candles is worse than no screenshot.

The figure below is rebuilt directly from the exact OHLC rows fed into the scan.

The two selected windows reconstructed from the exported Binance kline rows. Their nominal price levels differ, so the alignment model uses return shape rather than raw-price equality.

The score got four times smaller. It still did not become a probability.

The two windows live at different nominal price levels:

reference: around 1,926 USDT
candidate: around 1,865 USDT

Comparing raw closes would mostly measure that price-level difference. The scanner converts each window to close-to-close returns in basis points:

returnBPS := ((currentClose - previousClose) / previousClose) * 10000

That transformation is visible in the code. lvlath/dtw does not silently normalize the sequence behind the caller's back.

Hidden normalization is the sort of “help” that makes a demo look clean and a production incident miserable to reconstruct.

With strict index pairing, the ten return samples accumulate an absolute cost of:

39.893841

The selected DTW path accumulates:

9.967796

under the same absolute local cost and a 0.05 penalty for every horizontal or vertical move.

The objective fell by roughly 75%.

That is not a 75% similarity score. It only says that allowing a constrained time deformation explains the two return sequences much better than forcing sample i to match sample i.

The actual model input. Left: close-to-close returns in basis points. Right: the local absolute-cost surface and selected path.

A percentage without calibration is just a confident UI element.

What the real path says

The scanner called:

dtw.Align(candidateSignal, referenceSignal, ...)

The public coordinate contract is therefore:

Coord.I → candidate index
Coord.J → reference index

The selected path was:

{0,0}
{0,1}   horizontal
{1,2}
{2,3}
{3,4}
{4,5}
{5,6}
{6,7}
{7,8}
{8,9}
{9,9}   vertical

Most of the path runs diagonally with a one-step offset.

Two cells carry the temporal deformation:

{0,0} → {0,1}

The candidate's first return is held while the reference advances once.

At the other end:

{8,9} → {9,9}

The candidate advances while the final reference phase is held.

That is much more useful than “9.97”. It tells the reviewer exactly where the clocks were stretched.

The path also shows what DTW did not fix. The largest local contribution on the selected route is 3.578995, where candidate return -3.321707 is paired with reference return -6.900703. Warping can move time; it cannot turn a genuinely different price move into the same move.

This is why a warping path is evidence, not a permission slip.

“Best candidate” is not “accepted match”

The first scanner version printed only the minimum.

That is enough for ranking, not classification.

Suppose the best monthly distance is 9.967796. Is that excellent, mediocre, or awful?

The answer needs context the DTW recurrence does not own:

a labeled positive/negative corpus;
a threshold selected against false-positive and false-negative cost;
distance distributions for the same preprocessing and policy;
perhaps a second-stage rule that inspects path shape, stretch count, or domain constraints.

A threshold copied from a synthetic fixture would be especially bad. The deterministic repository example reports 0.89; that does not make 1.50 a valid production cutoff for this Binance corpus.

A cutoff from the synthetic fixture does not survive a change of data distribution.

The updated article scanner therefore uses two passes and can export every candidate score.

Scan every candidate with rolling rows. Recover a path only for the shortlist. Keep the business threshold outside the alignment kernel.

The architecture is simple:

1. preprocess explicitly
2. scan every window distance-only
3. rank / apply a calibrated threshold
4. rerun selected windows with path tracking

No need to allocate an O(n×m) backtracking surface for every candidate and then act surprised when the pod gets OOMKilled.

The current `lvlath/dtw` API

The package exposes three canonical facades because “time series” is not one data type.

`Align`: scalar sequences

Use Align when one scalar represents one time step:

res, err := dtw.Align(
    candidateReturns,
    referenceReturns,
    dtw.WithWindow(2),
    dtw.WithSlopePenalty(0.05),
)

The default local cost is absolute difference. Callers can select squared cost or provide a deterministic custom CostFunc.

This surface fits returns, temperatures, single-axis sensors, latency traces, or other scalar signals.

`AlignMatrix`: multivariate features

Use AlignMatrix when each time step has several features:

res, err := dtw.AlignMatrix(
    breakoutTemplate,
    liveWindow,
    dtw.WithWindow(4),
    dtw.WithSlopePenalty(0.15),
    dtw.WithReturnPath(true),
)

Rows are time steps. Columns are features. The two matrices must have the same feature dimension.

The facade builds pairwise local costs with squared L2 distance between rows.

It does not normalize the features.

Leaving preprocessing to the caller is an ownership decision.

OHLC, returns, z-scores, volatility-adjusted values, sensor channels, and embeddings are different mathematical inputs. A library that silently rescales them has changed the problem while pretending to save the caller a few lines.

`AlignCostMatrix`: bring your own local model

Use AlignCostMatrix when another system already produced the n×m pairwise cost surface.

The voice-command example feeds a 10×14 acoustic local-cost matrix. An embedding model, phoneme recognizer, frame matcher, or domain-specific rule engine could own the same layer.

DTW then does one job: find the cheapest admissible monotone path through that surface.

The local costs still have a contract. They must be finite and non-negative.

Window and slope are not decorative tuning knobs

The window

WithWindow(w) defines the Sakoe–Chiba band:

w = -1   no band constraint
w =  0   strict diagonal
w >= 0   only cells with |i-j| <= w

0 does not mean “disabled”. It means no temporal deformation at all.

A finite band blocks ridiculous alignments: the first phoneme should not match the end of a command; the onset of a vibration event should not match recovery.

The policy can also make alignment impossible. If the band contains no valid path:

Reachable=false
Distance=+Inf

That is a legitimate model result, not a panic.

The slope penalty

WithSlopePenalty(p) adds p only to horizontal and vertical steps.

Those are exactly the moves that hold one sequence while the other advances.

A positive penalty makes temporal stretching cost something. Zero leaves it free except for local mismatch.

Neither choice is universally correct.

A voice command may tolerate a held vowel. A machinery signature may treat an extra peak frame as suspicious. A market scanner may allow a one- or two-candle delay but reject a pattern smeared across half an hour.

The number belongs to the domain, not to DTW folklore.

The path is deterministic on purpose

lvlath/dtw returns one deterministic representative optimal path.

type Coord struct {
    I int
    J int
}

type Path []Coord

Several predecessor cells can have equal accumulated cost. The package uses a fixed backtracking order:

diagonal
then vertical/up
then horizontal/left

This does not claim the mathematical optimum is unique.

It means a stable distance also produces a stable explanation.

That matters when tests assert phase anchors, incident reports compare paths, or downstream logic counts stretch steps. Without a tie-break law, an internal refactor can leave the scalar unchanged and quietly rewrite the witness.

Ask for a path and the bill changes. It should.

The benchmark suite measures separate DTW contracts rather than pretending they are one workload.

On this machine:

darwin/amd64
Intel Core i9-9880H @ 2.30GHz
10 benchmark runs

The saved output did not include go version. Add the actual toolchain before publication; guessing it later would undermine the reproduction block.

benchstat reported:

Contract	Workload	Time/op	B/op	allocs/op
Scalar distance, `TwoRows`	`500×500`	2.169 ms	8.156 KiB	4
Reachable band, `w=10`	`500×500`	527.8 µs	8.156 KiB	4
Strict-diagonal no path, `w=0`	`500×501`	455.0 µs	8.156 KiB	4
`FullMatrix` + path	`250×250`	1.232 ms	1004.2 KiB	9
`AlignMatrix`, squared L2, `d=8`	`200×200`	1.935 ms	1007.3 KiB	20

This is not a speed ranking. The dimensions and returned artifacts differ.

It does expose three useful facts.

First, the finite w=10 band ran about 4.1× faster than unconstrained scalar 500×500 distance on this fixture while keeping the same rolling-row allocation profile.

Second, the smaller 250×250 path workload allocated roughly 123× more bytes per operation than scalar 500×500 distance-only mode.

That is the cost of retaining accumulated state and recovering a witness. The lower runtime is not a contradiction; the path benchmark has only one quarter as many grid cells.

Third, AlignMatrix also sits around one megabyte per operation at 200×200×8 because the facade materializes the multivariate local-cost surface.

So the honest memory statement is not:

DTW uses O(m) memory.

It is:

Scalar distance-only Align can keep accumulated DP state in O(m). Path recovery needs O(n×m), and AlignMatrix has an additional O(n×m) local-cost surface.

Different workloads, different artifacts. The table is not a universal solver ranking; it exposes the resource contract of each mode.

Returning `nil` and making the caller play detective is lazy API design

The result carries the state needed to interpret it:

type Result struct {
    Distance  float64
    Reachable bool

    Path        Path
    PathTracked bool

    Window       int
    SlopePenalty float64
    MemoryMode   MemoryMode

    Accumulated *matrix.Dense
    LocalCost   *matrix.Dense
}

PathOrError() distinguishes:

nil result
    → ErrNilResult

no admissible alignment
    → ErrNoPath

finite alignment, path not requested
    → ErrPathNotTracked

A distance-only scan is a successful operation. It should not look like an alignment failure merely because no path slice was allocated.

A too-tight window is a different outcome. Caller logic may widen the band, reject the candidate, or record a policy failure.

Different decisions deserve different states.

Crypto is only one workload

The same result model appears in two other runnable examples.

Voice command

distance=0.83
path-steps=14
stretch-steps=4
decision=accepted with stretched pronunciation

The local acoustic-cost surface is computed elsewhere; AlignCostMatrix recovers the monotone correspondence.

Vibration signature

distance=0.0776
path-steps=17
stretch-steps=3
peak={6,8}
decision=signature match

Here AlignMatrix compares three sensor features per time step and accepts a delayed-but-normal spindle impact.

Other plausible uses follow the same shape:

gesture and motion alignment;
production-cycle timing;
latency-profile comparison;
ECG or respiratory phase alignment;
video-frame or embedding correspondence;
event-sequence template matching.

The API does not make those domains equivalent. It gives each one the same honest set of artifacts:

distance
path
local cost
accumulated cost
reachability
memory policy

Reproduce the real-data scan

The source dataset is the official Binance Spot monthly kline archive:

ETHUSDT
1-minute candles
July 2023
UTC

The article package includes the exact selected windows, path CSV, screenshots, and an updated two-pass scanner.

Run:

go run ./dtw_binance_real_scan_v2.go \
  -csv ETHUSDT-1m-2023-07.csv \
  -reference-start 2023-07-01T12:13:00Z \
  -candles 11 \
  -window 2 \
  -slope 0.05 \
  -exclude 30 \
  -top 10 \
  -out-prefix ethusdt-dtw

The scanner deliberately prints:

classification=not-configured

until the caller supplies a calibrated threshold.

That line is not missing functionality. It prevents the monthly argmin from being smuggled into business logic as a verified pattern match.

The useful boundary

A distance answers:

Which candidate is closest under this preprocessing and policy?

A path answers:

Which time steps correspond, and where did the clock stretch?

A local-cost matrix answers:

Which feature pairs created the mismatch?

An accumulated matrix answers:

Why did dynamic programming choose this route through the cost surface?

A threshold answers another question entirely:

Is this candidate good enough for my application?

One float should not pretend to answer all five.

Source and reproduction material

Package: https://github.com/lvlath/go/tree/main/dtw
Go Reference: https://pkg.go.dev/github.com/lvlath/go@v0.1.0/dtw
Current API: https://github.com/lvlath/go/blob/main/dtw/api.go
Current options: https://github.com/lvlath/go/blob/main/dtw/options.go
Current result types: https://github.com/lvlath/go/blob/main/dtw/types.go
Runnable examples: https://github.com/lvlath/go/blob/main/dtw/example_test.go
Deterministic long-stream scanner: https://github.com/lvlath/go/blob/main/examples/dtw_signal_alignment.go
Playground: https://go.dev/play/p/96eGjJQxauW
Benchmarks: https://github.com/lvlath/go/blob/main/dtw/bench_test.go

Three Correct TSP Solvers. Three Incompatible Promises.

Kyrylo Malovychko — Thu, 13 Aug 2026 12:02:46 +0000

The cold-chain fixture returns a 114-minute tour. The validated thermal window is 120 minutes.

Six minutes of margin.

The dispatcher asks a perfectly reasonable question:

Is 114 the best possible route?

For this run, the answer is not proven.

The tour came from Christofides with exact minimum-weight perfect matching. lvlath/tsp publishes ApproximationRatio=1.5 and Optimal=false.

The difference matters because the public call looks identical.

TL;DR

Tour and Cost are not enough for a production TSP result. In a 30-matrix experiment, 2-opt matched the exact optimum cost 24/30 times and 3-opt 27/30 times, yet neither solver can honestly publish Optimal=true. Christofides + Blossom matched the optimum only 8/30 times, but it is the heuristic regime with a formal 1.5 worst-case guarantee. Runtime, observed solution quality, and proof strength are different axes.

Textbooks explain permutations, NP-hardness, Branch-and-Bound, and 2-opt well enough. The awkward part appears later, when all of those algorithms are hidden behind one friendly function:

result, err := tsp.SolveMatrix(dist, ids, opts)

The call looks uniform. The result is not.

One result type, several very different claims

This is the public Result in github.com/lvlath/go@v0.1.0/tsp:

type Result struct {
    Tour  []int
    Cost  float64
    IDs   []string

    Algorithm Algorithm
    Exact     bool
    Optimal   bool
    TimedOut  bool

    MetricClosureApplied bool
    Symmetric             bool
    ApproximationRatio   float64

    Iterations    int
    NodesExpanded int
}

Those fields are intentionally redundant with the solver choice. A caller should not have to reconstruct what happened from old options, log text, or a function name.

A few valid states:

Run	`Exact`	`Optimal`	`TimedOut`	`ApproximationRatio`
Held-Karp completed	true	true	false	0
Branch-and-Bound completed	true	true	false	0
Branch-and-Bound stopped by time limit	true	false	true	0
Christofides + Blossom	false	false	false	1.5
Christofides + Greedy	false	false	false	0
2-opt / 3-opt	false	false	false	0

Route one: six minutes of cold-chain margin

The first runnable example is a six-stop symmetric metric travel-time matrix for vaccine distribution.

opts := tsp.DefaultOptions()
opts.Algo = tsp.Christofides
opts.Symmetric = true
opts.StartVertex = 0
opts.MatchingAlgo = tsp.BlossomMatch
opts.EnableLocalSearch = false

result, err := tsp.SolveMatrix(dist, nil, opts)

The relevant output is short:

route-minutes=114.0
formal-ratio=1.5
thermal-margin=6.0 minutes

The 114 is empirical: it belongs to this matrix and this returned tour.

The 1.5 comes from a theorem, and it survives only if the whole Christofides contract survives.

Same outer pipeline, different matching policy. The proof obligation changes even when both paths return a valid tour.

One caveat matters here: v0.1.0 documents metric input as a precondition; it does not prove the triangle inequality for every arbitrary matrix before solving. Symmetry and completeness can be validated mechanically. Metricity may still be a domain fact the caller has to defend. If that assumption is not trustworthy, the downstream system should not present 1.5 as an unconditional theorem.

The load-bearing stage here is minimum-weight perfect matching on the odd-degree vertices of the MST.

lvlath/tsp exposes that choice directly:

const (
    GreedyMatch MatchingAlgo = iota
    BlossomMatch
)

BlossomMatch is exact MWPM. GreedyMatch is deterministic and cheaper, but heuristic.

So this is a valid explicit configuration:

opts := tsp.DefaultOptions()
opts.Algo = tsp.Christofides
opts.Symmetric = true
opts.MatchingAlgo = tsp.GreedyMatch
opts.EnableLocalSearch = false

result, err := tsp.SolveMatrix(dist, ids, opts)
if err != nil {
    return err
}

fmt.Println(result.ApproximationRatio) // 0: no formal ratio claimed

There is no hidden "Blossom failed, quietly use Greedy" fallback. A failed stronger policy stays visible instead of returning weaker mathematics with stronger-looking metadata.

Route two: asymmetric cost is domain information

The second example models armored cash-in-transit routing. Cost combines time, fuel, guard exposure, and interception risk, so A -> B can legitimately differ from B -> A.

The solver is directed 2-opt*:

opts := tsp.DefaultOptions()
opts.Algo = tsp.TwoOptOnly
opts.Symmetric = false
opts.StartVertex = 0
opts.EnableLocalSearch = true

result, err := tsp.SolveMatrix(dist, nil, opts)

It returns:

directed-risk-cost=34.0
exact=false
optimal=false
approximation-ratio=0

The result is a deterministic locally improved ATSP tour under the selected policy. ApproximationRatio=0 states the missing guarantee explicitly instead of leaving the caller to infer it from Algorithm.

Route three: exact search can still return a non-optimal result

The semiconductor example has five drilling sites and an offline planning stage, so Branch-and-Bound with a 1-tree lower bound is a sensible exact choice:

opts := tsp.DefaultOptions()
opts.Algo = tsp.BranchAndBound
opts.Symmetric = true
opts.StartVertex = 0
opts.BoundAlgo = tsp.OneTreeBound
opts.EnableLocalSearch = false

result, err := tsp.SolveMatrix(dist, nil, opts)

The example completes with:

single-board-latency=16.8 ms
exact=true
optimal=true

Now add a wall-clock limit.

Branch-and-Bound is still an exact algorithm, but an interrupted search has not completed the proof. v0.1.0 may return a non-nil incumbent together with ErrTimeLimit:

result, err := tsp.SolveMatrix(dist, ids, opts)

if errors.Is(err, tsp.ErrTimeLimit) {
    if result == nil {
        return errors.New("time limit without incumbent")
    }

    fmt.Printf("cost=%.3f exact=%v optimal=%v timedOut=%v\n",
        result.Cost,
        result.Exact,    // true
        result.Optimal,  // false
        result.TimedOut, // true
    )
    return nil
}
if err != nil {
    return err
}

Exact describes the algorithm family. Optimal describes what this invocation actually proved.

That is a distinction a single Success bool cannot encode.

180 runs: observed quality vs. formal proof

For the article I generated 30 deterministic Euclidean metric matrices:

n = 8, 10, 12
10 fixed seeds per size

Each matrix was solved by six policies, for 180 solver runs. Held-Karp supplied the exact-cost baseline. Before writing a CSV row, an independent harness checked that the returned witness was a closed Hamiltonian cycle, visited every matrix vertex once, used finite non-negative edges, and recomputed the published cost from the source matrix.

I kept solution-quality measurements separate from testing.B: duration_ns in that CSV is diagnostic single-run timing, not benchmark evidence.

Across all 30 matrices:

Solver	Median gap to exact	Worst observed gap	Matched exact cost	What that proves
Held-Karp	0%	0%	30 / 30	exact baseline
Branch-and-Bound	0%	0%	30 / 30	completed exact search
Christofides + Blossom	3.059%	12.234%	8/30	empirical quality + formal 1.5 bound
Christofides + Greedy	8.261%	34.568%	5/30	empirical quality only
2-opt	0%	1.634%	24/30	empirical quality only
3-opt	0%	1.222%	27/30	empirical quality only

Local search won the empirical hit-rate on these small fixtures; Christofides + Blossom retained the theorem.

This is where the experiment gets uncomfortable.

2-opt hit the exact optimum cost 24 times. Christofides + Blossom did it 8 times. Yet Christofides is the one allowed to publish a worst-case mathematical guarantee.

The apparent contradiction disappears once the two questions are separated:

How did this solver behave on these 30 fixtures?
What can the algorithm prove outside this sample?

The first is empirical evidence. The second is a theorem.

Observed quality and proof strength are different axes.

Treating "the route was close to the optimum in my benchmark" as a formal guarantee is benchmark-driven overfitting.

One matrix makes the distinction even sharper

The equal-size benchmark used the same deterministic n=10, seed-47 matrix for every solver. testing.B measured only SolveMatrix; fixture construction stayed outside the timed region.

Solver	Median time	B/op	allocs/op	Gap on the same seed-47 matrix	Published claim
Held-Karp	313.6 µs	172.1 KiB	68	0%	exact + proven optimal
Branch-and-Bound	388.9 µs	14.39 KiB	197	0%	exact + proven optimal
Christofides + Blossom	25.24 µs	9.887 KiB	158	1.409%	formal 1.5 approximation
Christofides + Greedy	16.26 µs	5.809 KiB	96	1.409%	no formal ratio
2-opt	7.008 µs	1.562 KiB	10	0%	heuristic; no proof of optimality
3-opt	37.60 µs	3.844 KiB	21	0%	heuristic; no proof of optimality

The CSV for that exact fixture records:

Branch-and-Bound      cost=26037.596462281  nodes=3663  exact=true  optimal=true
2-opt                 cost=26037.596462281  iters=9     exact=false optimal=false
3-opt                 cost=26037.596462281  iters=0     exact=false optimal=false
Christofides/Blossom  cost=26404.536340990  ratio=1.5
Christofides/Greedy   cost=26404.536340990  ratio=0

The costs are identical, while the metadata differs because only the exact runs completed a proof of global optimality.

The equal-n table is a performance comparison for one fixed workload, not a universal solver ranking. That caveat matters: the permanent package benchmarks deliberately exercise very different regimes (n=12 Held-Karp, n=14 Branch-and-Bound, n=200 Christofides, n=500 2-opt), so putting those permanent numbers into one "fastest TSP algorithm" chart would be nonsense.

What does the 1.5 guarantee cost here?

The cleanest apples-to-apples regression pair in the package changes only the matching policy inside Christofides. Both use the same deterministic metric n=200 fixture. Local search is disabled.

Matching policy	sec/op	B/op	allocs/op	Formal ratio
Blossom exact MWPM	70.13 ms	2.714 MiB	8,925	`1.5`
Greedy matching	2.655 ms	450.4 KiB	1,401	none

Same n=200 fixture and outer Christofides pipeline; only the matching policy changes.

On this machine and fixture, the exact-matching pipeline is about 26.4× slower, uses 6.2× the bytes per operation, and performs 6.4× the allocations.

This comparison is narrow enough to be useful: the outer algorithm, matrix family, size, and local-search setting stay fixed. The changed subroutine is also the one that carries the proof obligation.

The isolated dense Blossom benchmark makes the growth visible:

32 odd vertices   2.350 ms
64               12.36  ms
128              57.72  ms

From 32 to 128 odd vertices, measured solve time increased about 24.6× on this workload.

That does not make Greedy "better" or Blossom "slow". It tells me what the stronger matching policy costs in this implementation, on this machine, for these fixtures.

A claim-first way to choose the solver

A size-only rule is too vague for exact TSP. v0.1.0 ships Held-Karp with a soft MaxExactN guard whose default is 16. Callers may raise that option, but the underlying cost remains O(n²·2ⁿ) time and O(n·2ⁿ) memory. Branch-and-Bound has no comparable fixed vertex cap; its worst case is exponential and its practical limit depends on the matrix, lower bound, incumbent quality, and wall-clock budget.

Requirement	Start here	Do not say
Predictable exact DP and `n` fits the configured `MaxExactN` plus memory/time budget (default guard: 16)	Held-Karp	Raising `MaxExactN` makes the exponential state space cheap.
Global optimum required but Held-Karp's DP budget is unattractive; pruning may help and runtime may be instance-dependent	Branch-and-Bound + explicit `TimeLimit`; use an admissible bound	A timeout incumbent is optimal.
Symmetric complete metric input; formal approximation bound required	Christofides + Blossom	Greedy matching keeps the 1.5 proof.
Locally optimal route required; global proof is unnecessary or computationally infeasible	2-opt / 3-opt with explicit move limits	Local optimum is global optimum.
Directed/asymmetric cost	Held-Karp / Branch-and-Bound when exact search is feasible, otherwise directed local search	Symmetrization is harmless cleanup.
Missing edges encoded as `+Inf`	Metric closure only when that transformation is valid for the domain	Derived closure distances are original edges.
Metric assumptions are unknown	Validate them or publish no ratio	Symmetry alone proves triangle inequality.

Reproduction details

The benchmark output recorded:

goos: darwin
goarch: amd64
cpu: Intel(R) Core(TM) i9-9880H CPU @ 2.30GHz

The repository's permanent regression benchmarks live in tsp/bench_test.go. The equal-n benchmark and the CSV quality harness were article-only local files; I ran them, kept the raw results, and did not add them to the library.

Exact regression:

GOMAXPROCS=1 go test ./tsp \
  -run '^$' \
  -bench 'Benchmark(HeldKarp|BranchBound)' \
  -benchmem -cpu=1 -count=10 -benchtime=3x

Practical regimes:

GOMAXPROCS=1 go test ./tsp \
  -run '^$' \
  -bench 'Benchmark(Christofides|TwoOpt|ThreeOpt)' \
  -benchmem -cpu=1 -count=10 -benchtime=1s

Blossom regression:

GOMAXPROCS=1 go test ./tsp \
  -run '^$' \
  -bench 'BenchmarkBlossom' \
  -benchmem -cpu=1 -count=10 -benchtime=1s

For strict reproduction, publish the exact commit SHA alongside the raw benchmark files. The Go version was not present in the benchmark outputs I kept, so I would not invent it after the fact.

There was no single winner in these fixtures. Local search often matched the exact optimum cost; Christofides carried the stronger worst-case statement; exact methods were the only ones allowed to set Optimal=true. The benchmark and the theorem ranked the same solvers differently.

If a caller cannot distinguish proven, bounded, timed out, and merely good on this run, the solver is hiding state it already knows.

Code and contracts:

The Algorithm Was Correct. The Graph Contract Was Not.

Kyrylo Malovychko — Wed, 05 Aug 2026 15:01:45 +0000

I tried to build an algorithm-heavy service with AI before I understood the algorithms well enough to specify them. A few days later I had a lot of code, no coherent graph, and one decision that changed the next two years of my work.

I began with a shortcut.

The service I wanted to build depended on a long list of algorithms. Some were familiar. Some I remembered from university only as names, formulas, and half-erased diagrams. A few I did not understand well enough to control at all.

AI looked like the obvious accelerator. I could describe the pieces, ask for implementations, join them later, and learn the difficult parts while the product was already taking shape.

Several days of hard work produced files at an impressive rate.

There were interfaces. Options. Callbacks. Result types. Comments that sounded confident.

Almost none of it belonged to the same system.

I could not even make BFS and DFS work against one graph model that I understood. One implementation expected adjacency in one shape, the other quietly assumed another. Options changed behaviour I had never defined. Results returned values, but not guarantees. I could not explain what had happened, why the answer was correct, or which part of it would remain stable after the next refactor.

I was not mildly dissatisfied. I was completely disappointed.

There was exactly one useful result: I stopped trusting AI with the parts I had not learned. If these algorithms were going to sit under a real service, I had to understand them and build them myself.

That was the point of no return.

Code was not the missing part

It would be easy to turn this into another story about AI producing bad code. That is not the lesson.

The deeper mistake was mine. I had asked for implementations before I could state the contract around them.

What graph shapes were legal? Was neighbour order observable? Who owned tie-breaking? Could edges be directed, undirected, or mixed? What did 0 mean inside a matrix? How was an unreachable target represented? Did a result carry a path, a predecessor map, a cut, a tree, or only a number? Could a caller classify failures without parsing an error string?

I had no precise answers. AI filled the gaps with plausible assumptions.

That is what makes this class of failure dangerous. Broken syntax is cheap to reject. Plausible code is not. It compiles, returns something, and invites the rest of the system to depend on decisions nobody made consciously.

A function can be mathematically correct and still publish an unusable software contract.

The first example was neighbour order.

Code insert 1: the graph that looks harmless

This is a reduced reconstruction of the pattern, not the original generated code.

package naive

type Graph map[string]map[string]struct{}

func (g Graph) AddUndirected(a, b string) {
    if g[a] == nil {
        g[a] = make(map[string]struct{})
    }
    if g[b] == nil {
        g[b] = make(map[string]struct{})
    }

    g[a][b] = struct{}{}
    g[b][a] = struct{}{}
}

func (g Graph) Neighbors(id string) []string {
    out := make([]string, 0, len(g[id]))
    for neighbor := range g[id] {
        out = append(out, neighbor)
    }
    return out
}

This graph is small, normal Go. It stores undirected connections and exposes neighbours.

It also returns a slice without defining its order.

Go map iteration order is not a public ordering policy. The same topology can reach a traversal through a different neighbour sequence. The graph has already influenced the result before BFS or DFS runs, but no package owns the decision and no caller knows whether the order can be relied on.

Maybe order does not matter to the mathematics. It still matters to software.

The slice may be logged, serialised, compared in a golden test, used for equal-cost tie-breaking, or shown to a user. Once callers can observe it, “we never intended the order to matter” is not much of a defence.

Code insert 2: a correct BFS inherits the uncertainty

package naive

func BFS(g Graph, start string) []string {
    seen := map[string]bool{start: true}
    queue := []string{start}
    order := make([]string, 0, len(g))

    for len(queue) > 0 {
        current := queue[0]
        queue = queue[1:]
        order = append(order, current)

        for _, next := range g.Neighbors(current) {
            if seen[next] {
                continue
            }
            seen[next] = true
            queue = append(queue, next)
        }
    }

    return order
}

Suppose api connects to both auth and cache, and both are one hop away.

These outputs can both satisfy the BFS distance property:

[api auth cache db worker]
[api cache auth db worker]

The algorithm is not necessarily wrong.

The product can still be wrong.

If the sequence drives a deployment plan, chooses the first equal candidate, appears in a reproducible report, or becomes part of a test fixture, two mathematically legal answers are not an adequate API contract.

That was the first thing I had failed to specify. I had named the algorithm. I had not defined the observable law around it.

Back to the mathematics, one stubborn step at a time

I stopped generating more code and went back to theory.

That phase was slower than I expected. Article after article, I found dense formulas with almost no reasoning, implementations without a mathematical explanation, questionable translations, and examples that demonstrated syntax but taught very little about behaviour.

I had been naïve enough to think I would quickly recover the university mathematics and continue with the product.

Instead, I moved one stubborn step at a time.

Graphs and matrices came back first. BFS and DFS followed. Dijkstra and minimum spanning trees were where irritation turned into a decision.

The foundations were not new. Much of the mathematics predates the modern software industry. Yet the useful knowledge was split across papers, tutorials, source repositories, paid material, shallow snippets, and documentation that stopped exactly where the uncomfortable production questions began.

I kept asking the same thing:

Why is there no free, coherent source where the mathematics is explained, the implementation is open, the contracts are explicit, and the examples are worth running?

Eventually the answer became obvious.

Build it.

Not another catalogue of textbook functions. The source I had been looking for: something a developer could study, use, challenge, and improve without surrendering the difficult parts to a black box.

A graph is not “vertices plus edges”

My early model of a graph was too weak. I treated it as a container.

A graph is also a domain of legal states.

Are edges directed? Are non-zero weights allowed? Can directed and undirected edges coexist? Are loops valid? Are parallel edges distinct facts or duplicate input? Does adding an edge create missing vertices? Can an option rewrite endpoints after validation? What survives a clone? Which values alias live storage?

If these answers live only in comments, invalid topology travels until a later algorithm discovers it in the worst possible place.

Dijkstra should not be the first layer to reveal that the graph never validated weights. An MST implementation should not guess whether parallel edges are legal. DFS should not discover halfway through cycle analysis that “directed” meant “usually directed.”

The capabilities belong at construction and mutation boundaries.

Code insert 3: make the graph policy executable

package main

import (
    "fmt"
    "log"

    "github.com/lvlath/go/core"
)

func main() {
    g, err := core.NewGraph(core.WithDirected(false), core.WithWeighted())
    if err != nil {
        log.Fatal(err)
    }

    if _, err = g.AddEdge("api", "db", 3, core.WithID("edge-api-db")); err != nil {
        log.Fatal(err)
    }

    if _, err = g.AddEdge("api", "cache", 1, core.WithID("edge-api-cache")); err != nil {
        log.Fatal(err)
    }

    if _, err = g.AddEdge("api", "auth", 2, core.WithID("edge-api-auth")); err != nil {
        log.Fatal(err)
    }

    ids, err := g.NeighborIDs("api")
    if err != nil {
        log.Fatal(err)
    }

    fmt.Println(ids) // [auth cache db]
}

The policy is visible.

The graph is undirected by default. Non-zero weights are legal. Edge identities are explicit. NeighborIDs publishes unique adjacent vertex IDs in lexicographic order.

The insertion order is not the contract.

A caller can dislike the policy, measure the cost, or propose another one. Fine. At least the disagreement is now concrete and testable.

That is the point of a contract. It does not eliminate trade-offs. It stops them hiding inside incidental implementation behaviour.

The number is not the meaning

Ordering was only the first hidden contract.

Numeric meaning was worse because the wrong answer could still look perfectly reasonable.

A 0 can be a real zero-cost edge. In a classic adjacency matrix, the same 0 can mean no edge at all. +Inf can mean no direct edge, no known path, or an uninitialised cell. A negative weight is legal for one algorithm and forbidden for another. NaN can poison a matrix while every surrounding type remains valid.

No number carries its domain semantics with it.

The representation has to declare the policy.

This became a hard boundary in lvlath/matrix. Zero-preserving weighted adjacency uses finite 0 for a real edge and +Inf for absence. Metric closure uses 0 on the diagonal and +Inf for unreachable pairs. Then it refuses to export those derived distances as if they were original graph edges.

That refusal is not inconvenience. It prevents a false topology.

The matrix problem deserves its own article, but the lesson belongs here: a perfect algorithm cannot recover information that the representation erased before the algorithm started.

Errors should survive better wording

The prototypes returned error values. That did not make the failures useful.

If a caller has to compare text, improved diagnostics become breaking changes. More importantly, different operational states collapse into one vague failure path.

Unknown is not unreachable. Unreachable is not “path tracking was disabled.” Cancellation is not resource exhaustion. Invalid topology is not an empty result.

Named error identity is not exciting. It is dependable.

Code insert 4: classify the failure, do not parse the sentence

package main

import (
    "errors"
    "fmt"
    "log"

    "github.com/lvlath/go/core"
)

func main() {
    g, err := core.NewGraph() // unweighted by default
    if err != nil {
        log.Fatal(err)
    }

    _, err = g.AddEdge("A", "B", 3)
    fmt.Println(errors.Is(err, core.ErrBadWeight)) // true
}

ErrBadWeight is useful because code can react to its identity while the surrounding diagnostics improve.

The same discipline continues above the graph layer. A shortest-path package should distinguish an unknown target from a known unreachable one. A cycle detector should return a witness. A max-flow result should expose the residual network when the caller needs to inspect the bottleneck. A DTW result should distinguish alignment cost from the recovered path.

A number without evidence is often just a polite version of “trust me.”

I had already tried that approach.

v0.0.1: publish the weakness, not the mythology

The first architecture looked sensible when it lived only in my head:

graph/
├── algorithms/
├── core/
└── matrix/

BFS, DFS, Dijkstra, Prim, and Kruskal shared one algorithm directory. core held the graph. matrix handled adjacency and incidence representations.

Simple.

Too simple.

Figure 1. The v0.0.1 structure. Useful as a public baseline; not a structure worth preserving.

Each algorithm wanted its own options, result type, errors, examples, ownership rules, complexity statement, and failure surface. Keeping them together encouraged convenient shared assumptions and made every explanation blur into the next one.

My second mistake was more expensive because I made it deliberately: implement first, document later.

I told myself that serious documentation should wait until the code worked. In practice, the delay allowed unclear behaviour to spread. When I finally tried to describe every public option, error, result, complexity claim, ownership rule, and edge case in one consistent format, the contradictions became impossible to ignore.

Another restructuring followed.

Documentation written after an API hardens is often archaeology. I had created my own dig site.

I shelved a chess engine. I abandoned the deeper-analysis service that had started the whole journey. The list of planned algorithms changed too. Early ambitions included SAX, HMM, ARIMA, GBM, and GJR-GARCH. Shipping that breadth on a weak foundation would have repeated the original mistake at a larger scale.

So I narrowed the path.

Graph and matrix first. Then BFS, DFS, Dijkstra, MST, flow, TSP, and DTW in an order a reader could actually follow.

I released v0.0.1 anyway.

It was primitive. Some parts were awkward. That was the point. I needed a real tag, a version I could install outside the IDE, and a public baseline that made weak seams visible.

Then the first email arrived.

The first user changed the quality bar

Another Go developer had found lvlath while looking for a graph library.

He was building a package for scheduling binary execution. Users could define arguments, conflicts, and dependencies between those arguments. He wanted to know whether graph theory, and lvlath specifically, could help him check those relationships efficiently even at a small scale.

Figure 2. The first external question was not about an academic demo. It was about conflicts, dependencies, and a real package design.

That message did not prove the library was good.

It proved the problem was not mine alone.

Until then, I could still treat the quality bar as personal. After that email, every ambiguous contract became someone else's risk. Another developer was ready to build on assumptions I had made.

“Works” stopped being enough.

So did 80 percent. Then 90. Then 95.

Not because a percentage can certify a library. It cannot. The numbers describe the movement of the bar: from a personal prototype toward public responsibility. Tests had to cover validation, medium cases, adversarial boundaries, deterministic repetition, race safety, and result witnesses. Documentation had to match the implementation. Examples had to compile against the public API and teach a problem worth recognising.

Praise would have felt good.

A concrete question was better. It forced the project to answer somebody else's reality.

v0.1.0: separate the contracts

The rebuilt structure is wider and much less accidental.

Figure 3. By v0.1.0, each algorithm owns a package boundary, while docs/ and examples/ are visible parts of the system.

One algorithm, one package.

Not because directories are architecture by themselves, but because boundaries force questions into the open. BFS and DFS no longer need to pretend they share one result contract. Dijkstra can own target semantics. MST can separate strict-tree and forest behaviour. Flow can expose residual-network evidence. TSP can state solver method, assumptions, and stopping policy. DTW can distinguish cost from path recovery and memory mode.

The documentation layer changed too.

example_test.go scenarios are not decorative snippets. They are executable teaching material. The long-form docs/*.md files explain the mathematics, the public contract, the failure modes, the complexity, and the operational traps. GoDoc states the API. Tests defend it. Source should not invent a fourth interpretation.

This combination is the part I am most proud of.

Not one clever function.

The agreement between code, explanation, example, and test.

Tests should defend promises, not accidents

A happy-path test can preserve the wrong behaviour forever.

If a test expects one traversal order but the API never promises an order, the test has converted an accident into a hidden requirement. If it reaches into private maps, it protects storage rather than caller behaviour. If it checks only a scalar cost, it can miss a broken witness.

For neighbour ordering, the useful test is not “this insertion sequence produced this slice once.”

It is “all supported construction histories publish the same documented surface.”

Code insert 5: build the same graph three ways

package core_test

import (
    "slices"
    "testing"

    "github.com/lvlath/go/core"
)

func TestNeighborIDsIgnoreInsertionOrder(t *testing.T) {
    orders := [][]string{
        {"db", "cache", "auth"},
        {"auth", "db", "cache"},
        {"cache", "auth", "db"},
    }
    want := []string{"auth", "cache", "db"}

    for _, order := range orders {
        g, err := core.NewGraph(core.WithDirected(false))
        if err != nil {
            t.Fatal(err)
        }

        for _, target := range order {
            if _, err = g.AddEdge("api", target, 0); err != nil {
                t.Fatal(err)
            }
        }

        got, err := g.NeighborIDs("api")
        if err != nil {
            t.Fatal(err)
        }

        if !slices.Equal(got, want) {
            t.Fatalf("insertion %v: got %v, want %v", order, got, want)
        }
    }
}

The test does not care whether adjacency is stored in maps, sorted slices, trees, or a compact representation not yet implemented. It defends only the behaviour the caller is entitled to observe.

That kind of test survives a real refactor.

The same idea scales. Validate a path independently from the solver. Verify that an MST is acyclic and spans the required component. Check flow conservation and residual capacity instead of trusting one maximum. Permute insertion order. Fuzz invalid option combinations. Separate race safety from snapshot guarantees.

A green suite is not proof by itself.

But every public guarantee needs evidence strong enough to fail when the guarantee is broken.

The current public promise

The present module is not just a repository tree. It publishes a contract where people already look for Go packages.

Figure 4. The current public promise: the same input and policy should produce the same observable result surface, witness semantics, and failure class.

The sentence at the top of the documentation is deliberately strict:

Same graph, same options, same algorithm - same result surface, same witness semantics, same failure class.

That promise is harder to maintain than implementing BFS.

It has to survive new packages, performance work, refactors, better diagnostics, more examples, and eventually new major versions. It requires boring details: stable identities, explicit capabilities, sentinel errors, documented ownership, numerical semantics, cancellation behaviour, partial results, and tests that do not depend on private storage.

Those details are the library.

The algorithm is only the centre.

What remains unfinished

There is plenty left to argue about.

Matching implementations such as blossom and greedy matching currently sit inside tsp; they may deserve clearer package boundaries. The planned catalogue is much larger than the current release. Future major versions will have to decide how far the ecosystem should expand without repeating the old mistake of breadth before a stable foundation.

The project uses one Go module with multiple packages. That is deliberate today. It gives users one versioned dependency surface while each algorithm owns its public API. Splitting packages into separate modules would add release and compatibility cost; it should happen only when user evidence justifies it, not because more module files look more modular.

v0.1.0 is not a monument.

Good.

There is still time to challenge the contracts before they harden.

The rule I use now

Before I blame an algorithm, I inspect the layer beneath it.

Does the graph publish a stable vertex, edge, and neighbour order?

Are directedness, weights, loops, parallel edges, and mixed edges validated as capabilities rather than suggested by comments?

Do 0, +Inf, NaN, negative values, and absence have one documented meaning in the current representation?

Are identity, cloning, views, aliases, metadata, and ownership clear?

Can software classify failures without parsing prose?

Does the result carry enough evidence to inspect the answer: path, predecessor map, cycle witness, tree, cut, residual graph, tour, or alignment?

Do the examples, tests, GoDoc, and long-form documentation describe the same behaviour?

If the answer is “it depends,” that is not always a bug.

It is a policy waiting for an owner.

The point of no return, revisited

The original service never became the product I had imagined.

The chess engine was shelved. The deeper-analysis project was abandoned. The first architecture was replaced. Documentation forced another round of redesign. The list of future algorithms kept growing while the release scope had to become narrower.

That cost was real.

It also produced something I had not planned: a public source for the next engineer who reaches the same wall.

AI still has a place in my workflow. It can accelerate scaffolding, propose adversarial cases, compare designs, and reduce repetitive work. It cannot take responsibility for a mathematical contract I have not written.

That responsibility remains mine.

The first external user changed lvlath from a private attempt into a public obligation. The current structure, examples, documentation, and tests are how I am trying to honour it.

If a guarantee is weak, open an issue. If an example is confusing, say exactly where. If an algorithm is missing, describe the real problem before naming the package. If the mathematics is wrong, bring a counterexample.

I paid for the confusion once.

The next engineer should not have to.

Before debugging the algorithm, ask whether the graph underneath it ever made a promise.

Which hidden contract has cost you the most: ordering, topology, numerical meaning, identity, mutation, or missing evidence?