Identity-Aware Array Diff

Date: 2026-02-09

Problem

diff() compares arrays by index. LLMs don't guarantee stable ordering. When recompute re-runs an extraction step that returns entities in a different order, every index reports as changed – even though nothing meaningful changed. This undermines the core value prop: showing humans what actually changed.

See ../verist-ops/docs/issues/index-based-array-diff.md for the full write-up and examples.

Analysis of Approaches

The issue doc proposes four approaches (A–D). Here's why none are optimal as stated, and what the right answer is.

A. keyBy on diff() – Pollutes the general-purpose structural diff with domain-specific concerns. diff() should stay a clean JSON comparator.

B. Normalize (sort) in user code – Zero framework changes, but burden on every step author, easy to forget, and still wrong for insertions/deletions (sorted index-based diff shows shifted indices, not the actual add/remove).

C. normalizeForDiff hook – Declared once per step, but only handles ordering. A step that adds or removes entities still produces misleading diffs. Also, an imperative normalization function is more boilerplate than necessary.

D. Identity-aware diff in the kernel – Correct, but the issue assumes this requires a new diff algorithm with heuristics. It doesn't.

Solution: keyBy + array-to-map normalization

The key insight: converting a keyed array to a map before diffing gives identity-aware comparison for free – the existing diff() already handles objects correctly (additions, removals, per-field changes).

const extract = defineStep({
  name: "extract-entities",
  input: z.object({ documentId: z.string() }),
  output: z.object({
    entities: z.array(EntitySchema),
  }),
  keyBy: {
    entities: "id",
  },
  async run(input, ctx) { /* ... */ },
});

When recompute compares outputs, it normalizes keyed arrays to maps before diffing. Normalization is transient – stored artifacts always contain the original arrays.

// Before normalization (arrays, unstable order)
before = { entities: [{id:"e1", text:"John"}, {id:"e2", text:"Acme"}] }
after  = { entities: [{id:"e2", text:"Acme"}, {id:"e1", text:"John"}] }

// After normalization (maps, keyed by identity)
before = { entities: {e1: {id:"e1", text:"John"}, e2: {id:"e2", text:"Acme"}} }
after  = { entities: {e2: {id:"e2", text:"Acme"}, e1: {id:"e1", text:"John"}} }

// diff() on maps → (no changes)
// Object key order doesn't matter – diff iterates sorted keys.

Why this works for all cases

Scenario	Index-based (broken)	Map-based (correct)
Reorder only	Every index shows as changed	No changes
Field change	Correct if same index, noisy if not	entities.e2.confidence: 0.9 → 0.7
Entity added	Shifted indices, misleading	+ entities.e4: {...}
Entity removed	Shifted indices, misleading	- entities.e1: {...}
Add + reorder	Complete noise	Clean addition only

Why this is optimal

1. diff() is unchanged – stays a general-purpose structural comparator. No new algorithm, no options, no complexity.
2. Correct for all cases – reordering, additions, removals, field changes – all handled by existing object diffing.
3. Minimal API – one field (keyBy) on step definition. Declarative.
4. Explicit – step author declares identity, no magic heuristics.
5. Readable paths – entities.e2.confidence instead of entities[1].confidence.
6. Zero-cost when unused – no keyBy declared → no normalization, behavior identical to today.

Key invariants

keyBy affects only diff normalization. It has no effect on execution, replay, validation, or storage.

Stored data stays raw. Normalization is transient, applied only at comparison time inside recompute and compareSnapshots. Snapshots and artifacts always store the original array order. This preserves:

• Exact reproduction via replay (byte-identical output)
• Round-trip fidelity with external systems
• Original insertion order when it matters downstream

KeyFn must be a pure function of the element. No external state, no randomness, no mutation. Called once per element.

keyBy type

type KeyFn = string | ((item: unknown) => string | number);

interface StepConfig<TInput, TOutput, TAdapters> {
  // ... existing fields ...

  /**
   * Identity keys for array fields in the output.
   * Used by recompute to match array elements by identity instead of
   * by index, producing clean diffs when LLMs return unstable ordering.
   *
   * Has no effect on execution, replay, validation, or storage.
   *
   * Key: dot-path to an array field in the output.
   * Value: field name within each element, or a function returning
   * a unique key.
   */
  keyBy?: Record<string, KeyFn>;
}

Examples:

keyBy: {
  entities: "id",                                       // simple field
  "results.claims": "claimId",                          // nested path
  lineItems: (item) => `${item.section}:${item.line}`,  // composite key
}

Dot-path resolution rules

Paths resolve through plain objects only. Keep it simple and predictable:

• "entities" – top-level field, must be an array
• "results.claims" – nested field via object traversal
• No numeric indexing ("items.0.sub" is NOT supported)
• No wildcards
• Terminal segment must point to an array; intermediates must be objects

Error handling

normalizeForDiff validates at normalization time (fail-fast, clear messages near the source):

Condition	Behavior
Path doesn't resolve (missing/non-obj)	Skip silently – expected for Partial<T> outputs
Path resolves but value is not array	Skip silently – suspicious but non-fatal; schema
	validation is a separate concern
Element lacks the key field	Throw: keyBy: element at entities[2] has no field "id"
Key extractor returns non-string	Throw: keyBy: key must be string or number, got object
Duplicate keys in same array	Throw: keyBy: duplicate key "e1" in entities
Empty keyBy / no keyBy	No-op, return value unchanged

Silent skips are necessary because step outputs are Partial<T> – a keyed array field may not be present in every run.

In recompute: normalization errors must be caught and returned as structured RecomputeError (code: "normalization_failed"), not uncaught throws. The current try/catch in recompute only covers step execution – normalization happens after, so it needs its own handling.

Integration points

recompute() (primary) – Before calling diff(), normalize both original and recomputed outputs using the step's keyBy. The step is already a parameter, so keyBy is available with no plumbing.

compareSnapshots() – Add optional keyBy parameter. Accept raw keyBy (not the full step) to keep the function focused.

normalizeForDiff() exported – Public utility for ad-hoc comparisons in tests or custom workflows. Pure function, no side effects.

What this does NOT change

• diff() signature and behavior – unchanged
• applyDiff() – not used in recompute; the normalized diff is for human review, not mechanical application to the original array
• formatDiff() – works as-is; map paths are strings, rendered as entities.e2.confidence
• Snapshot format – no changes to stored artifacts

Implementation

normalizeForDiff(value, keyBy) utility

/**
 * Normalize value for identity-aware diffing.
 * Converts arrays at keyed paths to Record<key, element>.
 *
 * Paths that don't resolve to an array are silently skipped
 * (partial outputs may omit keyed fields).
 */
export function normalizeForDiff(
  value: unknown,
  keyBy: Record<string, KeyFn>,
): unknown

• Walk the value, resolve each dot-path in keyBy
• At each matched array, convert to Record<string, element>
• Validate: duplicate keys, missing key fields → throw
• Shallow-copy only the parent object holding the array, not the entire value tree (performance, referential transparency)
• No-op when keyBy is empty

Changes to recompute.ts

const normalize = (v: unknown) =>
  normalizeForDiff(v, step.keyBy ?? {});

// Wrap normalization in try/catch → structured RecomputeError
let normalizedOriginal: unknown;
let normalizedNew: unknown;
try {
  normalizedOriginal = normalize(originalOutput);
  normalizedNew = normalize(outputForDiff);
} catch (cause) {
  return err({
    code: "normalization_failed",
    message: cause instanceof Error ? cause.message : String(cause),
    retryable: false,
    cause,
  });
}

const outputDiff = comparable
  ? diff(normalizedOriginal, normalizedNew)
  : undefined;

Changes to step.ts

• Add keyBy to StepConfig and Step interfaces
• Carry through in defineStep()

Tests

• Reordered array with key → equal: true
• Field change within matched entity → correct path and values
• Entity added → shows as object addition
• Entity removed → shows as object removal
• Composite key function → correct matching
• Nested dot-path → correct resolution
• Duplicate key → throws with message
• Missing key field on element → throws with message
• Key path absent in partial output → silently skipped
• Path resolves to non-array → silently skipped
• No keyBy declared → behavior unchanged (index-based)
• recompute with normalization error → structured RecomputeError

Connection to LangExtract

LangExtract returns extractions: Array<Extraction> with no guaranteed ordering. Each extraction has fields like extraction_class, extraction_text, attributes. A Verist step wrapping LangExtract:

keyBy: {
  extractions: (e) => `${e.extraction_class}:${e.extraction_text}`,
}

This produces clean diffs when re-running extraction with different models or prompts – showing exactly which entities changed, were added, or were removed.

Scope

Small, focused change:

• 1 new public utility (normalizeForDiff)
• 2 type changes (StepConfig, Step)
• 2 integration points (recompute, compareSnapshots)
• ~80 lines of implementation + ~150 lines of tests