Sequences and Deduplication

How INIF detects and shares token runs that repeat across every sample.

A document built from a typical eval has heavy repetition — the same system prompt, few-shot exemplars, MCQ scaffolding, or chat template delimiters appear at the start of every sample. INIF detects those shared runs and stores them once.

The two operations are symmetric methods on InifDocument:

compact = doc.deduplicate_sequences()           # default min_length=5
flat    = compact.expand_sequences()

Both return new documents — neither mutates the input. Tokens, sequences, metadata, and extras are deep-copied on the way out.

What gets deduplicated

A token run is eligible for collapse only if it appears as a contiguous subsequence in every sample (set-intersection, not pairwise). The dedup pass also skips:

  • Tokens already inside a sequence ref (refs are never re-wrapped).
  • Tokens with extras attached — extras are position-specific, so collapsing them would destroy data.
  • Tokens covered by any annotation — keeps tagged regions visible as real tokens for downstream analysis.

Both the token strings and their ids must match for a window to be collapsed. This guards against the rare case where two samples share a substring but tokenize it to different ids.

NoteReplacements never cross message boundaries

When samples carry chat-style texts, the dedup pass injects per-sample boundary markers at every Text.start > 0. Those markers break contiguity in the n-gram intersection so a single replacement run can never span the boundary between two messages — a shared <|im_end|><|im_start|>assistant delimiter that sits at the end of message i stays attached to that message rather than collapsing into a sequence that bridges into message i+1. Per-text token offsets stay coherent after dedup as a result.

What gets stored

A collapsed run becomes a Sequence:

Sequence(
    id="seq_0",
    n_tokens=14,
    tokens=[TokenOrSeqRef(id=..., token=...) for _ in range(14)],
)

Each sample’s matching window is replaced by a single sequence-ref token:

TokenOrSeqRef(id=None, token="seq_0")

The target sequence id lives in the token field (there is no separate sequence_id field); id is None is the discriminator that marks this as a reference rather than a vocabulary token.

Sequence.id is auto-assigned as seq_0, seq_1, …, skipping ids already present in doc.sequences so re-running dedup never collides.

The captured Sequence.tokens list keeps the real vocabulary ids, not just the strings. That is what makes the dedup → expand round-trip lossless for downstream tools that need ids (probing, logit-lens, anything that indexes into the model’s vocab matrix).

Tuning min_length

min_length (default 5) is both the smallest window the algorithm will collapse and the n-gram size used for the initial intersection. Smaller values find more matches at higher computational cost and produce noisier sequence lists; larger values miss small shared runs.

Short shared runs aren’t worth the indirection in practice — a two- or three-token bigram pays the sequence-ref overhead without saving meaningful space. Pass an explicit smaller value when you really do need to capture them:

compact = doc.deduplicate_sequences(min_length=3)

For chat-template-heavy eval documents, the default 5 finds the longer template prefixes (system prompt + few-shot exemplars) cleanly. For raw text without chat formatting, the same default is conservative and rarely surprising.

Expansion

doc.expand_sequences() rebuilds a flat document. Each ref token is replaced by fresh TokenOrSeqRef(id=t.id, token=t.token) instances drawn from the referenced sequence. The returned document drops the sequence list entirely — running deduplicate_sequences again will rediscover the same shared runs.

Annotations are remapped along with the tokens: a range [start, end) spanning a ref token in the compact view becomes the wider range covering all of the ref’s expanded positions. The Text.start / Text.end offsets on each message also get remapped, so per-message token ranges stay valid after dedup → expand. Round-tripping preserves the labelled regions exactly.

Materializing one position

Expansion is a whole-document operation. When you only need to write to a single position currently inside a ref — for example, attaching a probe score to position 137 — use Sample.materialize_position:

actual_index, real_token = sample.materialize_position(137, doc.sequences)
real_token.set_extra("probe_score", 0.42)

The containing ref is expanded in place, leaving the rest of the sample’s refs untouched. The returned (actual_index, real_token) pair is the position you can now address directly.

Performance

Both passes are O(total tokens) in practice. The detection algorithm:

  1. Indexes only length-min_length n-grams per sample (O(n) memory).
  2. Intersects keys across samples to find candidate anchors.
  3. Greedily extends each candidate rightward, dropping samples whose next token mismatches.

The replacement pass is also linear: sequences are indexed by their (first_token, first_id) pair so the common case (no match at this position) is O(1). The hot loop never re-walks the full sequence list.

When not to deduplicate

The Inspect AI / evaleval / text converters all run dedup by default. Pass deduplicate=False (or --no-dedup on the CLI) when:

  • You’re producing a single-sample document — there is nothing to share.
  • You’re going to attach interpretability outputs at every position immediately afterwards — extras-carrying tokens are skipped by the next dedup run anyway, so the savings collapse to zero.
  • You’re benchmarking and want the un-collapsed file size as a baseline.