skip to content

Kolmogorov complexity cannot be measured, so what do you put in a build gate meant to reject test fixtures carrying too little content?

level: principalimportance: should knowfreq 25%

answer

  1. sound in one direction only
  2. alarm on shrinking, never certify
  3. pin the coder and the version
  4. count the trained dictionary too
  5. close the gap with recorded provenance

basics

~20 s

Gate on the provable direction only: a fixture that compresses sharply demonstrably has a short description, so alarm on that. Never let the gate certify the opposite, and pair it with recorded provenance for the fixtures it passes.

solid answer

~40 s

Start from what is provable. A pinned coder that shrinks a fixture hands you a real program - payload plus decoder - so a high ratio is evidence of genuinely low content and is a legitimate rejection trigger. The reverse is not available at any price: a fixture the coder cannot shrink may still be one seed away from a few hundred bytes, and no better tool fixes that. So build a **one-directional** gate: reject on high compressibility, never pass-as-certified on low, pin the coder and its version so scores stay comparable across months, and count any trained dictionary in the measured size. Then cover the direction the metric cannot see with process - recorded provenance for each corpus, plus domain-level coverage checks that measure behaviour exercised rather than bytes.

go deeper

for a junior

The takeaway is that a compression-based data check can prove a file has little content but can never prove it has a lot. Read a passing result as no alarm, not as approval.

for a middle

Explain the asymmetry mechanically: a coder that shrinks a file has produced a short description, while a coder that fails has only searched its own narrow family of patterns.

for a senior

Operate it: pin the coder and version, include any trained dictionary in the measured size, alert on trend rather than an absolute ratio, and keep a recorded exception path for legitimately repetitive fixtures.

for a principal

Own the scope of the claim. Name the check for what it proves, print its limit where people read it, and close the direction it cannot see with provenance records and coverage checks rather than by buying a better estimator.

## Separate what is provable from what is wanted The wish is 'this corpus carries enough content to be worth testing against'. The quantity behind that wish is descriptive complexity, and no procedure returns it. What a build can compute is what a specific coder achieves on the bytes. Those two are related in exactly one direction, and the whole design follows from that asymmetry: - **Shrinks a lot**: a short description exists, because the coder just produced one. This is a proof, and it is a sound basis for rejecting. - **Does not shrink**: this coder found nothing. That is compatible with a two-hundred-byte generator having produced the whole corpus, so it certifies nothing at all. A gate that fires in the first case is measuring something real. A gate whose green light is read as 'rich data' has inverted an implication, and no amount of tuning or of buying a stronger coder repairs it. ## Designing the check 1. **Pin the coder and its version**, and record both with the score. The metric is coder-relative, so an upgrade that changes ratios by ten percent would otherwise look like a change in the data. 2. **Measure the full description.** Payload plus any dictionary the coder was trained on or preloaded with. A dictionary trained on the corpus moves bits out of the number without removing them from the data, and makes the gate score its own training set. 3. **Fire on the provable side only.** High ratio, or a ratio that jumped sharply since the last run, is the alarm. Passing is the absence of an alarm, never a certificate. 4. **Treat the threshold as a trend, not an absolute.** A corpus whose ratio moves from 3:1 to 60:1 between releases is the interesting signal; the absolute figure depends on the coder, the file format and the framing. 5. **Exempt nothing silently.** A fixture legitimately full of repeated structure should carry a recorded exception with a reason, so the gate stays honest for everything else. ## What the gate cannot see, and what covers it | Blind spot | Why the metric misses it | What covers it instead | |---|---|---| | Corpus grown from one seed | Output resists the coder by design | Recorded provenance of how it was produced | | Near-duplicate records across files | Repetition falls outside the coder's window | Similarity checks at the record level | | Right size, wrong domain shape | Bytes say nothing about behaviour | Coverage of the input space the code branches on | | Real content that happens to be repetitive | High ratio despite genuine value | A human-reviewed exception with a stated reason | The recurring theme is that an untestable property is governed by **process**, not measurement. If you cannot check that a corpus has content, you record how it was produced and you check the claim you can check. ## The organisational failure to design against The danger is not a wrong number; it is a green light that accumulates authority. A gate people pass every day quietly becomes a guarantee in everyone's mind, and six months later someone writes 'our fixtures pass the entropy gate' in a risk document. Two habits keep that honest: - **Name the check for what it proves.** Something like 'low-content fixture detector' survives translation into a risk document; 'data quality score' does not. - **Write the limit into the gate's own output.** One line on every pass saying that no lower bound on content is implied, in the place people actually read. ## Cost and proportion This check is cheap - one pass of a coder over each fixture - and it catches a real class of mistake: the accidentally truncated fixture, the file of repeated template rows, the corpus regenerated with a constant where a varying field was meant. That is worth having. It is not worth building an elaborate estimator around, because the extra sophistication improves an upper bound that was never the binding constraint, while the blind spot that actually bites - a mountain of bytes from one seed - is untouched by any of it and closed instead by a line in the corpus's provenance record. The judgement being probed here is whether a lead can take an unmeasurable property, choose a proxy that is sound in one direction, scope the claim the proxy is allowed to support, and close the remaining gap with process rather than with a better tool.

  • A team proposes replacing the coder with a better estimator to make the gate two-directional. What do you say?
    That no estimator can do it. The missing direction requires ruling out descriptions the tool cannot express, which is the uncomputable half of the problem. A stronger estimator tightens an upper bound that was never the binding constraint, and leaves the seeded-corpus blind spot exactly where it was.
  • How would you keep the gate's scores comparable across a year of releases?
    Pin the coder and its version, freeze the settings, and record both alongside every score, so a ratio change means a data change. Store the series and alert on movement rather than on an absolute threshold, and re-baseline deliberately, with a note, whenever the pinned coder is upgraded.
  • What would make you drop the gate entirely?
    If domain-level coverage checks already fail on everything this gate catches, it is redundant noise. It earns its place only while cheap byte-level pathologies - truncation, repeated template rows, a constant where a varying field was meant - still reach the corpus unnoticed.

saying these in an interview costs you the question

  • Reads a passing compressibility check as proof of rich data
  • Believes a stronger coder makes the check two-directional
  • Compares scores across coder versions without re-baselining
  • Scores a payload after training the dictionary on that corpus
  • Substitutes byte-level scoring for domain coverage checks