# 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.