fathom/internal/insights/minhash.go

package insights

import (
	"hash/fnv"
	"math"
	"sort"
)

// Near-duplicate prompt detection, via shingling and MinHash.
//
// This is the part of the design that an embedding model would conventionally
// own, and it is worth being explicit about why it does not. The question being
// asked is "have I paid for this same request before", which is near-duplicate
// detection over short strings — the problem MinHash was built for. An
// embedding answers a strictly harder question, "do these mean the same thing",
// at the cost of a model file, a dependency, and a similarity score nobody can
// debug when it is wrong.
//
// The tradeoff is real and worth stating: two prompts that share no vocabulary
// but mean the same thing ("diagnose the intermittent failure" / "fix the flaky
// test") will not match here, and would match under embeddings. That miss is
// acceptable because the consequence is a finding that goes unreported, not a
// finding that is wrong — and because the tool-call sequence, which is the
// stronger signal for this whole feature, catches that pair anyway.

const (
	// shingleSize is in words. Two is small enough that short prompts still
	// produce a usable set, and large enough that word order carries weight.
	shingleSize = 2

	// numHashes trades accuracy for speed. At 64 the expected error on a
	// Jaccard estimate is roughly 1/sqrt(64), about 12%, which is far finer
	// than the threshold needs.
	numHashes = 64
)

// signature is a MinHash sketch of a token set.
type signature [numHashes]uint64

// shingle turns tokens into overlapping n-grams. A token list shorter than the
// shingle size degrades to the tokens themselves rather than producing nothing.
func shingle(tokens []string, n int) []string {
	if len(tokens) == 0 {
		return nil
	}
	if len(tokens) < n {
		return tokens
	}
	out := make([]string, 0, len(tokens)-n+1)
	for i := 0; i+n <= len(tokens); i++ {
		s := tokens[i]
		for j := 1; j < n; j++ {
			s += " " + tokens[i+j]
		}
		out = append(out, s)
	}
	return out
}

// minhash computes a sketch. The i-th hash is derived from one base hash by
// mixing in i, which avoids keeping 64 independent hash functions around and is
// standard practice for sketches this size.
func minhash(shingles []string) signature {
	var sig signature
	for i := range sig {
		sig[i] = math.MaxUint64
	}
	if len(shingles) == 0 {
		return sig
	}
	for _, sh := range shingles {
		h := fnv.New64a()
		h.Write([]byte(sh))
		base := h.Sum64()
		for i := 0; i < numHashes; i++ {
			v := mix(base, uint64(i))
			if v < sig[i] {
				sig[i] = v
			}
		}
	}
	return sig
}

// mix is a cheap 64-bit avalanche (splitmix64's finaliser).
func mix(x, seed uint64) uint64 {
	x += seed * 0x9e3779b97f4a7c15
	x ^= x >> 30
	x *= 0xbf58476d1ce4e5b9
	x ^= x >> 27
	x *= 0x94d049bb133111eb
	x ^= x >> 31
	return x
}

// similarity estimates the Jaccard index of the two underlying sets.
func (s signature) similarity(other signature) float64 {
	same := 0
	for i := range s {
		if s[i] == other[i] {
			same++
		}
	}
	return float64(same) / float64(numHashes)
}

// empty reports a sketch built from no shingles, which must never be treated as
// similar to anything — otherwise every prompt-less trace clusters together.
func (s signature) empty() bool {
	for _, v := range s {
		if v != math.MaxUint64 {
			return false
		}
	}
	return true
}

// cluster groups items whose sketches exceed the threshold.
//
// Greedy single-link assignment against cluster seeds, not full pairwise
// comparison: at the scale of one machine's traces the difference is
// irrelevant, and the greedy form keeps clusters tied to a representative,
// which is what the UI shows.
func clusterBySimilarity(sigs []signature, threshold float64) [][]int {
	type group struct {
		seed    signature
		members []int
	}
	var groups []group

	for i, sig := range sigs {
		if sig.empty() {
			continue
		}
		placed := false
		for g := range groups {
			if groups[g].seed.similarity(sig) >= threshold {
				groups[g].members = append(groups[g].members, i)
				placed = true
				break
			}
		}
		if !placed {
			groups = append(groups, group{seed: sig, members: []int{i}})
		}
	}

	out := make([][]int, 0, len(groups))
	for _, g := range groups {
		if len(g.members) < 2 {
			continue // a cluster of one is just an item
		}
		sort.Ints(g.members)
		out = append(out, g.members)
	}
	// Largest clusters first: they are the ones worth acting on.
	sort.SliceStable(out, func(i, j int) bool { return len(out[i]) > len(out[j]) })
	return out
}