file-server/model/DESIGN_clustering.md

Stage-5: Unknown-format discovery by Bayesian header clustering

Status: phases A and B implemented and calibrated (src/cluster.jl + src/catalog.jl, bin/cluster_calibrate.jl + bin/cluster_sweep.jl, tests in test/runtests.jl). Phase A (offline Gibbs) is calibrated; phase B's durable single-owner catalog, incremental sweep, and nomination writer are now built on top of the assign_file scoring core. Product of a design interview; captures the decisions and — as important — the assumptions we rejected so they don't get silently reintroduced. §11 records what building it actually taught us, including three assumptions in this document that the data corrected.

1. Goal

Discover recurring new file formats hiding in the binary/ bucket (the :unknown sink from classify.jl → stage-3 triage). A genuinely novel format is a plausible proxy for a genuinely novel producing application, but we do not try to identify producers directly (see §3). The output is a growing catalog of discovered formats, each with a magic-byte signature that can be promoted into the classifier's fast path.

Task shape (settled): unsupervised clustering with an unknown number of clusters. Not pairwise "same producer" scoring, not classification against a fixed label set.

2. Two phases — build (A) then run (B)

(A) Batch, offline — the science. Cluster the accumulated pile from scratch. Its job is not to be the catalog; it is to (i) prove the header-byte signal actually separates formats, cross-checked against an NCD baseline (§8), and (ii) calibrate hyperparameters against known formats (§7). Ship this first — it de-risks (B). If (A)'s clusters are garbage, (B)'s machinery is wasted.

(B) Online, live — the catalog. The target deliverable. A persistent catalog where each discovered format has a durable, frozen ID and stored sufficient statistics. New unknown files are scored against existing clusters; only genuinely novel ones spawn a new entry. Clusters that accumulate enough evidence are nominated for promotion into the classifier (§6).

3. What we are and are NOT clustering

We cluster by file format, not by producer. The first-n header bytes are format-mandated and producer-invariant: every valid PNG shares the same magic regardless of which program wrote it; a PDF's producer string lives deep inside the file, not in the header. Producer identity, where recoverable at all, is exiftool's job (stage 2), not this stage's.

Corollary already visible in ../training_set: extension labels are not header-format labels. docx is a PK zip; so/o/elf/out are all ELF. Merging those is correct, not error (see §7).

4. Model: DP mixture of per-position categoricals

A cluster is a product of independent per-position categorical distributions over the first n header bytes. Position i carries a distribution θᵢ over a 257-symbol alphabet: byte values 0–255, plus symbol 256 = "past EOF".

• Invariant positions (magic bytes) learn a spiked θᵢ; variable positions (lengths, timestamps) learn a flat one. A cluster's signature = the vector of modal symbols + per-position peakedness. That signature is a magic-number template — this is the entire reason for the categorical choice.
• 257 alphabet handles short files honestly: a format that is always 20 bytes produces a spiked "past-EOF" at positions 20–31, which is real, discriminative signal. No zero-padding (would collide 0x00 padding with real 0x00 bytes).

Priors: Dirichlet on each θᵢ (conjugate to Categorical); Dirichlet process (CRP) over cluster assignments → unknown k falls out natively.

Why categorical, not Euclidean. Bytes are categorical, not ordinal: 0x89 and 0x88 are not "close," 0x00 and 0xFF are not "far." k-means / Gaussian mixtures over scaled bytes assert a metric that does not exist in header space. Do not reuse model.jl's [0,1] byte scaling here — that scaling is correct for the Lux net and wrong for this model. We need the raw 0–255 byte as a categorical index.

4a. Background component (high-entropy handling)

Add a fixed, non-adaptive uniform component (each position uniform over 257) as the "junk drawer." Compressed/encrypted/structureless blobs are ~uniform after any magic and would otherwise either (i) mint a singleton per file or (ii) collapse into one flat cluster that then matches everything. The background absorbs them cleanly.

Two populations, to be precise:

• Structured prefix + random tail (gzip 1f 8b, PK zip, zstd, most encrypted containers): peaked at positions 0–3, flat after. These form real clusters for free — genuine discoveries, no special handling.
• Uniform from byte 0 (raw encrypted streams, key material): nothing in the header to cluster on → absorbed by background.

The background is never promotable. But it is not a silent sink: its size / growth / entropy histogram is surfaced as a first-class signal ("12% of this week's unknowns are structureless"). If sub-clustering the structureless residue ever matters, that needs a different feature (byte histogram / entropy), a separate v3 model — header bytes genuinely cannot do it.

4b. Feature window

Front-only, n = 32 (config knob; try 64 if under-resolved). Magic lives at offset 0. Tail window deferred to v2 — a minority of formats have trailers (ZIP EOCD, ID3v1, PDF %%EOF); add as an independent second block of positions only if real trailer-formats show up in the residue.

Known blind spot: tar. ustar magic is at offset 257, outside the window, so all 100 training tars scatter to background. Accepted for v1 — tar is already a known format, so discovery doesn't need it. General lesson: a minority of formats put magic at a fixed deeper offset; the fix (if ever needed) is a sparse probe window at that offset (e.g. bytes 257–262 as a third block), not densely modeling 257 front bytes — that would 8× every cluster's n×257 sufficient-stat table to catch one format.

5. Inference: different mode per phase (resolves the Bayesian-vs-catalog tension)

A sampler yields a posterior over partitions; a catalog needs one partition with durable IDs. Two MCMC gotchas: label switching (cluster #3 is not a stable identity across iterations/runs) and distribution-not-answer (1000 partitions, not one). We sidestep both by using two inference modes:

• Phase (A), offline: full collapsed Gibbs sampler over the Dirichlet-Categorical (conjugacy → ~100 lines, no continuous approximation, unknown k native). Used to validate signal, tune α + Dirichlet strength, and seed the initial catalog (summarize to a point partition once, via a VI/Binder loss over the posterior similarity matrix — tolerated because it is offline, never in the hot path).
• Phase (B), live: deterministic sequential CRP-predictive assignment. Each catalog cluster stores per-position 257-count vectors (sufficient stats). A new file's CRP predictive probability of joining each existing cluster vs. the background vs. spawning a new cluster is computed; assign to the argmax. A new cluster is minted only if the new-cluster evidence beats the background by a margin. IDs are frozen at birth → no label switching. This is exactly the Gibbs predictive rule with existing assignments held fixed — same math, not an ad-hoc hack.
• Periodic compaction, offline: re-run Gibbs seeded from the current catalog to merge drifted clusters / split bloated ones.

6. Promotion (closing the loop to the classifier)

Layered known-check at ingest becomes:

1. Match against promoted signatures (exact, fast) — runs before the net.
2. Else the Lux :known / :unknown classifier.
3. Else route to binary/ for this stage.

Promotion = append a magic-byte signature to a registry. A cluster's spiked positions (posterior max-prob > ~0.9) become required bytes; flat positions become wildcards — a libmagic-style signature. This is a data change, not a retrain; interpretable, auditable, reversible. Retraining the Lux net is a separate, optional periodic activity using accumulated signature-labeled files, never the promotion mechanism itself.

Nominate automatically, activate by hand. A cluster crossing thresholds — ≥ N members (start N ≈ 20–50, loose dial since a human is the backstop) and ≥ ~3 magic positions and not the background — is written to a nominated/ registry with its signature, member count, and example files. A human glance promotes it into the active set. Human gate guards the one hard-to-reverse action (redefining "known"); everything upstream stays automatic.

7. Calibration: recover known formats, then trust on unknowns

Do not pick priors blind. We have ground truth: ../training_set (100 each of tgz/tar/pdf/docx, 98 zip, 93 jpg, ELF family) and the data/done corpus.

1. Run labeled known files through the exact clustering pipeline.
2. Ground truth = magic-collapsed classes, not extensions: {gzip (tgz), PKzip (docx≡zip), ELF (so/o/elf/out/x86_64), JPEG, PDF, tar}. Merging docx+zip and the ELF family is the correct answer — scoring against raw extensions would penalize correctness and mistune α.
3. Measure recovered-vs-truth agreement with Adjusted Rand Index / V-measure.
4. Grid-tune α and the Dirichlet pseudocount to maximize agreement — the settings at which the machine rediscovers formats we already know.
5. Freeze, deploy on the :unknown pile.

Splitting docx from zip is a later tier: the discriminating info (central-directory filenames like word/document.xml) sits at a variable offset, not a fixed position — a different feature problem, deferred.

8. Julia package surface

• Hand-rolled collapsed Gibbs over Dirichlet-Categorical — recommended. The conjugacy makes it short/fast; we own the online + promotion logic; no library impedance. Distributions.jl for Dirichlet/Categorical primitives.
• CodecZlib for the NCD (Normalized Compression Distance) baseline — model-free gzip-similarity clustering. Excellent at format grouping and a great step-(A) sanity check, but O(N²), non-generative (no signature, no online scoring, no promotion) → baseline only, cannot be the catalog.
• Clustering.jl — randindex / vmeasure for the §7 calibration metric, plus a throwaway k-modes-ish baseline. Not the real model (its k-means is the Euclidean trap of §4).
• Turing.jl — considered and rejected: discrete assignment latents + DP are awkward, and we'd still hand-roll the online path. Overkill.

9. Architecture: single-owner batch stage, NOT inline inference

The classifier is stateless, immutable, shared read-only across worker threads (see classify.jl). The catalog is the opposite: mutable, learned, shared — every assigned file updates a cluster's counts. It therefore must not copy the classifier's concurrency model (concurrent workers → lock contention, torn reads of sufficient stats, CRP assignment against stale mass).

Because promotion is human-gated, nothing here is latency-sensitive. So:

• Workers stay stateless — they deposit :unknown files into binary/ exactly as today. No catalog access on the hot path.
• A separate stage-5 process (periodic / cron, single-threaded) owns the catalog exclusively: sweeps newly-arrived binary/ files, runs sequential CRP-predictive assignment, updates sufficient stats, writes nominations. One writer, zero locks, no cross-thread shared mutable state.
• The catalog is a durable file mutated by one process — reuse the stage-2 sidecar-first durable-commit discipline (commit_enriched!: temp write → fsync bytes → rename → fsync dir) so a crash can't corrupt it or lose a rename.

This slots in as a batch stage, matching how stages 2/3/4 already work. New Config knobs follow the existing FS_* env-override convention (e.g. FS_CLUSTER_DIR, FS_CLUSTER_N, FS_CLUSTER_ALPHA, FS_CLUSTER_PSEUDOCOUNT, FS_PROMOTE_MIN_MEMBERS).

10. Concrete test assertions (write these first)

1. Discovers nothing from noise. Current data/binary = 20 small random blobs + 1 giant PDF. Correct output: PDF is a singleton that never promotes (N=1), 20 blobs absorbed by background, zero promoted clusters. Any promoted cluster from this pile = broken.
2. Recovers known formats. On a ../training_set sample, calibrated settings cluster into the ~6 magic-collapsed classes with high ARI (docx+zip merged, ELF family merged, tar in background as the accepted blind spot).
3. NCD agreement. Step-(A) Bayesian clusters broadly agree with the NCD baseline on the same input; large disagreement is a red flag to investigate before trusting the generative model.

11. Implementation status & calibration results (v1)

Shipped. src/cluster.jl — feature extraction (header_symbols, 257-symbol alphabet), collapsed Gibbs (gibbs_cluster, phase A), the sequential CRP-predictive rule (assign_file, phase B core), signatures/promotion (signature, is_promotable), and calibration metrics (adjusted_rand_index, v_measure). All base-Julia — a base-only Lanczos loggamma keeps the Dirichlet-multinomial marginal dependency-free (no Manifest churn). Config knobs FS_CLUSTER_* (§9) added. bin/cluster_calibrate.jl runs the §7 grid and the §8 NCD baseline. Concrete §10 assertions are in the test suite (hermetic synthetic corpora, so they need neither ../training_set nor gzip).

Calibrated defaults (grid over the 700-file training_set, ranked by ARI excluding tar): n=32, α=1.0, β=0.1, bg_mass=5.0 → ARI 0.77 (0.885 excl. tar), V-measure 0.83, homogeneity 0.87. Clusters are clean and promotable: pkzip:197 (docx+zip correctly merged, §7.2 ✓), gzip:100, jpeg, and several pdf clusters all self-nominate. The NCD baseline agrees (§10.3): on a 150-file subsample, NCD 1-NN label purity 0.90 vs. the model's same-cluster purity 0.987 — the generative header model separates formats at least as well as model-free gzip similarity.

Three assumptions the data corrected

1. Tar is not in the background here; it merges into ELF. §4b/§7 assumed tar's ustar-at-257 magic is out of window so tars scatter to background. But 98/100 tars in the corpus are Hex/Elixir package tarballs whose first archived file is named VERSION → a constant, strongly-peaked VERSION\0 prefix at offset 0. They do form a peaked cluster — but it merges with ELF, because ELF's ident padding and tar's name-field zero-padding give the two a long shared run of 0x00 in bytes 5–31; they differ in only ~3 magic bytes, and 32 equally-weighted positions let ~20 shared zeros outvote 3 real ones. No β both separates ELF/tar and keeps the other formats whole. The honest v1 position: this is the same "tar is hard" reality §4b flagged, just wearing a different mask. Fix (v2): weight positions by inverse entropy so a low-information shared-zero run stops dominating a few high-information magic bytes — this generalizes beyond tar and is the highest-value next lever.

2. You cannot cold-start every point in the background. A natural reading of §4a/§5 is "everything starts in the junk drawer, real clusters condense out." That deadlocks: at a format's first file a fresh cluster and the background are both uniform, so with the bg_mass ≥ α that §4a needs for absorption, the background always wins and no cluster is ever seeded. Fix: initialize every file in its own singleton; same-format singletons merge and snowball, while a lone random-blob singleton dissolves on resample and is reclaimed by the (stickier) background. Absorption still works — just not as the initial state.

3. Two pieces of math that look optional but aren't. (a) Signature peakedness is a Bernoulli question ("is this position fixed to byte v?"), so it uses a 2-way posterior (count+β)/(members+2β), not the 257-way mixture predictive — the alphabet-wide denominator drags even a unanimous position below 0.9 once β<1, which would make promotion impossible. (b) Ranking Gibbs restarts needs the collapsed Dirichlet-multinomial marginal (with its loggamma normalizer / Occam penalty); a plain product-of-predictives score omits the penalty and actively rewards merging everything into one blob (observed, then fixed).

Known v1 limitations (accepted)

• β=0.1 over-splits PDF and JPEG into several pure sub-clusters (e.g. PDF by version byte). This costs completeness/ARI but not the mission: each sub-cluster still carries valid magic and promotes independently, and a human dedupes overlapping %PDF-1.x nominations at the gate.
• The point partition is the best of N Gibbs restarts by marginal likelihood, a MAP-style stand-in for the VI/Binder posterior summary §5 defers — adequate because the formats are strongly separated; revisit if compaction (§5) needs it.
• Phase B's live single-owner batch process (§9) and the durable catalog file are implemented in src/catalog.jl (the Catalog durable state, the incremental catalog_sweep!, the offline compact! seed/recompaction, and write_nominations!), driven by bin/cluster_sweep.jl (cron/periodic; the first run auto-compacts to seed, subsequent runs sweep incrementally). The catalog is persisted with the stage-2 sidecar-first temp→fsync→rename→fsync-dir discipline. As §5B predicts, under the calibrated bg_mass > α the live sweep never mints single-file clusters — new formats are discovered by the offline compact! re-clustering the background residue, not by the live path.

Open items (deferred, intentionally)

• v2, now top priority: inverse-entropy position weighting (unblocks ELF/tar and any format pair that shares a long constant run — see §11).

• v2: tail-window block; sparse deep-offset probe (tar-class).

• v3: sub-clustering structureless high-entropy residue (needs entropy/histogram feature, not header bytes).

• Later tier: docx-vs-zip split via variable-offset central-directory names.

• Periodic Lux retrain from accumulated signature-labeled files.