Skip to content

determinism.md

Latest commit

 

History

History
873 lines (797 loc) · 37 KB

determinism.md

File metadata and controls

873 lines (797 loc) · 37 KB
Raw

Neotoma Determinism Doctrine — Reproducibility and Predictability Guarantees

(Determinism Requirements Across All Subsystems)

Scope

This document covers:

  • Definition and requirements of determinism
  • Deterministic patterns for common operations
  • Sorting, ordering, and ID generation rules
  • Elimination of randomness and timing dependencies
  • Testing strategies for deterministic behavior This document does NOT cover:
  • Consistency models (see docs/architecture/consistency.md)
  • Specific extraction logic (see subsystem docs)
  • Database transaction isolation (implementation detail)

1. Determinism: Core Definition

1.1 What is Determinism?

Determinism: Given the same inputs, a system MUST always produce the same outputs, in the same order, with the same internal state.

1.2 Determinism Doctrine

Explicit Classification: Not all Neotoma components are deterministic. The following table explicitly classifies each component:

Component Deterministic? Notes
Content hashing (SHA-256) Yes Same bytes = same hash
Deduplication Yes (user_id, content_hash) uniqueness
Storage path Yes {user_id}/{content_hash}
Observation creation (given fixed validated fields + entity_id) Yes Pure insert
Reducer computation Yes Same observations + same merge rules → same snapshot
Entity merge Yes Deterministic rewrite of observations + snapshot recompute
Rule-based extraction Yes Same text + same rules → same fields
AI interpretation No Outputs vary; config logged for audit
Entity resolution (heuristic) No May drift; duplicates expected
Policy: Neotoma never claims replay determinism for AI interpretation. Interpretation config is logged for audit, but outputs may vary across runs. A first run may produce zero observations (e.g. empty extraction or misclassification); re-interpreting the same source may produce observations on retry. When debugging imports, retry interpretation if the first run yielded no entities.

1.3 Interpretation Auditability vs Replay Determinism

Key Distinction:

  • Replay Determinism: Same input always produces identical output
  • Auditability: Process is logged with enough detail to understand what happened AI interpretation is auditable but not replay-deterministic:
  • interpretations table stores interpretation_config (model, version, parameters)
  • Multiple interpretations for the same source create NEW observations
  • Prior observations are never modified (immutability preserved)
  • Audit trail shows exactly how data was interpreted at each point in time Implication: Entity resolution may create duplicates. The merge_entities() capability exists to repair duplicates deterministically after the fact.

1.4 Idempotence vs Determinism: Key Distinction

Determinism (Model-Level):

  • Same input → same output (byte-for-byte identical)
  • For LLMs: same prompt → same token sequence
  • Not achievable with stochastic LLMs (category error to expect this)

Idempotence (System-Level):

  • Same operation → same final state (no duplicates, no side effects)
  • For interpretation: same source + same config → same observations (no duplicates created)
  • Achievable even with stochastic LLMs through post-processing

How Idempotence Works Without Determinism:

  1. LLM produces stochastic output (not deterministic):

    • Run 1: {"amount": 1200.00, "currency": "EUR"}
    • Run 2: {"currency": "EUR", "amount": 1200}

  2. System canonicalizes (makes deterministic):

    • Both become: {"amount": 1200, "currency": "EUR"} (sorted keys, normalized numbers)

  3. System hashes (creates identity):

    • Both produce: hash = sha256(canonical) → same hash

  4. System checks for existing (enforces idempotence):

    • If observation with this hash exists → no duplicate created
    • Final state is the same regardless of LLM variance

Key Insight: Idempotence is enforced post-generation, not during generation.

Policy: Neotoma's architecture favors system-level idempotence over model-level determinism. The LLM is stochastic (not deterministic). The system enforces idempotence through canonicalization, hashing, and deduplication.

1.6 Agent-Layer Nondeterminism and Bounded Convergence

Problem: Sections 1.2–1.4 address nondeterminism in the interpretation layer (LLM extracting fields from a source). A distinct and broader source of nondeterminism exists at the agent tool-selection layer: the LLM deciding which MCP tools to call, when, and with what payloads.

Why this matters:

  • Given the same user message, an LLM may choose different tools, different entity types, different field sets, or different relationship structures across runs.
  • Agent instructions (MCP instructions, rules, conventions) constrain behavior probabilistically, not deterministically. Instruction adherence is high but not guaranteed.
  • Each stochastic decision compounds: if run A stores entity_type: "purchase" and run B stores entity_type: "transaction" for the same real-world event, the deterministic core faithfully processes both — producing divergent entity graphs from identical inputs.

Explicit Classification:

Component Deterministic? Notes
Agent tool selection No LLM chooses which MCP action to call
Agent payload construction No LLM constructs entity_type, fields, values
Agent entity type selection No May vary: "purchase" vs "transaction"
Agent relationship creation No May create REFERS_TO or skip it
Agent retrieval-before-store No Soft instruction, may be skipped

Bounded Convergence:

Neotoma does not (and cannot) make the agent layer deterministic. Instead, the architecture targets bounded convergence: given reasonable LLM behavior, the entity graph converges toward a consistent state over time, with the deterministic core ensuring convergence is monotonic.

Properties of bounded convergence:

  1. Immutability prevents corruption: Stochastic variance accumulates as new observations, never overwrites existing truth
  2. Canonicalization narrows variance: Normalization + hashing collapses semantically equivalent but syntactically different LLM outputs to the same observation
  3. Reducers arbitrate conflicts: Merge policies resolve multi-observation conflicts deterministically regardless of observation order
  4. Entity merge repairs divergence: merge_entities() deterministically repairs duplicate entities created by variant tool-selection paths
  5. Schema validation constrains payloads: Write-time validation rejects structurally invalid observations before they enter the log

Convergence improvements (see docs/architecture/bounded_convergence.md):

  • Write-time entity suggestion (fuzzy-match on store)
  • Entity type normalization via taxonomy with aliases
  • Field alias mapping in schema definitions
  • Retrieval-augmented storing (auto-inject existing entities)
  • Post-store convergence diagnostics
  • Structured action templates
  • Agent action replay and convergence testing
  • Observation confidence scoring
  • Fixed-point convergence for critical stores

Policy: Neotoma's determinism guarantee is a property of the data layer, not the agent layer. The system is deterministic in the way a database is deterministic (same queries, same results), not in the way a compiler is deterministic (same source, same binary). The agent layer is more like a user — unpredictable in what it writes, but the system faithfully and deterministically processes whatever it receives.

Related Documents:

1.5 What is Determinism? (Continued)

Inputs include:

  • Function arguments
  • File contents
  • Database state (at time of query)
  • Configuration values Outputs include:
  • Return values
  • Database writes
  • Generated IDs
  • Event emissions
  • Log messages (excluding timestamps) Timing and Environment MUST NOT affect outputs:
  • ❌ Current timestamp (unless explicitly part of input)
  • ❌ Random number generation
  • ❌ Nondeterministic sorting (e.g., Map iteration order in some languages)
  • ❌ Network latency
  • ❌ Filesystem ordering (e.g., readdir() without sorting)

1.2 Why Determinism Matters for Neotoma

Correctness:

  • Users must trust Neotoma's extracted truth
  • Same document uploaded twice MUST produce same entities, events, graph Testability:
  • Tests must be reproducible (no flaky tests)
  • Property-based testing requires determinism Debuggability:
  • Bugs must be reproducible from inputs alone
  • No "works on my machine" issues from nondeterminism AI Safety:
  • AI agents depend on Neotoma for ground truth
  • Nondeterministic truth breaks AI reasoning Auditing:
  • Provenance requires deterministic extraction
  • "Why was this entity created?" must have reproducible answer

2. Sources of Nondeterminism (FORBIDDEN)

2.1 Random Number Generation

❌ FORBIDDEN:

// Nondeterministic: random UUID
const recordId = `rec_${uuidv4()}`; // Different every time

✅ REQUIRED:

// Deterministic: hash-based ID
const recordId = generateRecordId(fileHash, userId, uploadTimestamp);
// Same inputs → same ID

2.2 Timestamps (When Not Part of Input)

❌ FORBIDDEN:

// Nondeterministic: current time affects output
const recordId = `rec_${Date.now()}`;

✅ REQUIRED:

// Deterministic: use explicit timestamp from input
const recordId = generateRecordId(fileHash, explicitTimestamp);

Exception: created_at and updated_at timestamps for audit purposes are acceptable (but not used for ID generation or sorting when determinism required).

2.3 Unsorted Iteration

❌ FORBIDDEN:

// Nondeterministic: Map iteration order is not guaranteed in all JS engines
for (const [key, value] of myMap) {
  processField(key, value);
}

✅ REQUIRED:

// Deterministic: sort keys first
const sortedKeys = Array.from(myMap.keys()).sort();
for (const key of sortedKeys) {
  const value = myMap.get(key);
  processField(key, value);
}

2.4 Filesystem Ordering

❌ FORBIDDEN:

// Nondeterministic: readdir() order is filesystem-dependent
const files = await fs.readdir('/uploads');
for (const file of files) {
  await processFile(file);
}

✅ REQUIRED:

// Deterministic: sort before processing
const files = (await fs.readdir('/uploads')).sort();
for (const file of files) {
  await processFile(file);
}

2.5 Concurrent Execution Without Ordering

❌ FORBIDDEN:

// Nondeterministic: Promise.all() doesn't guarantee order
const results = await Promise.all(files.map(f => processFile(f)));
// Order of results depends on which promise resolves first

✅ REQUIRED (if order matters):

// Deterministic: process sequentially or sort after
const results = [];
for (const file of files.sort()) {
  results.push(await processFile(file));
}

2.6 LLM Outputs (Non-Deterministic by Nature)

❌ NON-DETERMINISTIC (but allowed with audit trail):

// Nondeterministic: LLM extraction varies
const entities = await llm.extract(rawText);
// Same text → different entities each run

Policy: AI interpretation is auditable but not replay-deterministic (see Section 1.2-1.3). Requirements for AI interpretation:

  • Config logging: model, temperature, prompt_hash, code_version
  • Immutable interpretations: reinterpretation creates NEW observations
  • Never claim replay determinism
  • Entity resolution may create duplicates; merge_entities() repairs Alternative (fully deterministic):
// Deterministic: rule-based extraction
const entities = extractEntitiesViaRegex(rawText, schemaRules);
// Same text + rules → same entities

Use rule-based extraction when determinism is critical; use AI interpretation when flexibility is needed.

2.7 Floating-Point Arithmetic (Edge Case)

❌ POTENTIALLY NONDETERMINISTIC:

// May vary across architectures or rounding modes
const score = (a * b) / c;

✅ SAFER:

  • Use fixed-precision decimals for financial amounts (e.g., Decimal.js)
  • Document rounding modes
  • Test across architectures

3. Deterministic Patterns

3.1 Deterministic ID Generation

Pattern: Use cryptographic hash of canonical inputs. Example:

import { createHash } from 'crypto';
export function generateEntityId(
  entityType: string,
  canonicalName: string
): string {
  // Normalize inputs
  const normalized = canonicalName.toLowerCase().trim();

  // Hash deterministically
  const hash = createHash('sha256')
    .update(`${entityType}:${normalized}`)
    .digest('hex');

  // Return stable ID
  return `ent_${hash.substring(0, 24)}`;
}
// Same inputs → same ID, always
generateEntityId('company', 'Acme Corp') === generateEntityId('company', 'Acme Corp'); // true

Why this works:

  • SHA-256 is deterministic
  • Same inputs → same hash
  • No timestamps, no randomness

3.2 Deterministic Sorting

Pattern: Always sort by stable, deterministic fields. Example:

// Sort records by created_at (stable timestamp), then by ID (tiebreaker)
const sortedRecords = records.sort((a, b) => {
  const timeDiff = a.created_at.localeCompare(b.created_at);
  if (timeDiff !== 0) return timeDiff;
  return a.id.localeCompare(b.id); // Tiebreaker
});

Tiebreaker Rules:

  • Primary sort: business-meaningful field (e.g., created_at, name)
  • Secondary sort: unique stable field (e.g., id)
  • Never sort by mutable field without tiebreaker

3.3 Deterministic Deduplication

Pattern: Use content hash to detect duplicates. Example:

export function deduplicateRecords(records: Record[]): Record[] {
  const seen = new Set<string>();
  const unique: Record[] = [];

  for (const record of records) {
    const contentHash = hashRecordContent(record);
    if (!seen.has(contentHash)) {
      seen.add(contentHash);
      unique.push(record);
    }
  }

  return unique;
}
function hashRecordContent(record: Record): string {
  // Hash only immutable fields
  const canonical = JSON.stringify({
    schema_type: record.schema_type,
    raw_text: record.raw_text,
    user_id: record.user_id,
  });

  return createHash('sha256').update(canonical).digest('hex');
}

Why this works:

  • Content hash is deterministic
  • Same content → same hash → detected as duplicate
  • No reliance on upload order or timing

3.4 Deterministic Entity Resolution

Pattern: Normalize, then hash. Example:

export function resolveEntity(
  entityType: string,
  rawValue: string
): { id: string; canonical_name: string } {
  // Step 1: Normalize
  const canonical = normalizeEntityValue(entityType, rawValue);

  // Step 2: Generate deterministic ID
  const id = generateEntityId(entityType, canonical);

  return { id, canonical_name: canonical };
}
function normalizeEntityValue(entityType: string, raw: string): string {
  let normalized = raw.trim().toLowerCase();

  if (entityType === 'company') {
    // Remove common suffixes deterministically
    normalized = normalized
      .replace(/\s+(inc|llc|ltd|corp|corporation)\.?$/i, '')
      .trim();
  }

  return normalized;
}
// Examples:
resolveEntity('company', 'Acme Corp').id === resolveEntity('company', 'Acme Corp').id; // true
resolveEntity('company', 'ACME CORP').id === resolveEntity('company', 'Acme Corp').id; // true (normalized)

3.5 Deterministic Event Generation

Pattern: One event per date field, deterministic event ID. Example:

export function generateEvents(
  recordId: string,
  extractedFields: Record<string, any>,
  schemaType: string
): Event[] {
  const events: Event[] = [];
  const dateFields = getDateFields(schemaType); // Deterministic schema-based

  // Sort fields for deterministic order
  for (const fieldName of dateFields.sort()) {
    const dateValue = extractedFields[fieldName];
    if (!dateValue) continue;

    const eventType = mapFieldToEventType(fieldName, schemaType);
    const eventId = generateEventId(recordId, fieldName, dateValue);

    events.push({
      id: eventId,
      event_type: eventType,
      event_timestamp: dateValue,
      source_record_id: recordId,
      source_field: fieldName,
    });
  }

  return events;
}
function generateEventId(recordId: string, fieldName: string, date: string): string {
  const hash = createHash('sha256')
    .update(`${recordId}:${fieldName}:${date}`)
    .digest('hex');
  return `evt_${hash.substring(0, 24)}`;
}

3.6 Deterministic Search Ranking

Pattern: Rule-based ranking with deterministic tiebreakers. Example:

export function rankSearchResults(results: Record[], query: string): Record[] {
  return results
    .map(record => ({
      record,
      score: calculateScore(record, query), // Deterministic scoring
    }))
    .sort((a, b) => {
      // Primary: score (higher first)
      if (a.score !== b.score) return b.score - a.score;

      // Tiebreaker 1: created_at (newer first)
      const timeDiff = b.record.created_at.localeCompare(a.record.created_at);
      if (timeDiff !== 0) return timeDiff;

      // Tiebreaker 2: ID (lexicographic)
      return a.record.id.localeCompare(b.record.id);
    })
    .map(({ record }) => record);
}
function calculateScore(record: Record, query: string): number {
  let score = 0;

  // Exact match in schema_type
  if (record.schema_type.toLowerCase().includes(query.toLowerCase())) {
    score += 10;
  }

  // Match in raw_text (count occurrences)
  const regex = new RegExp(query, 'gi');
  const matches = record.raw_text.match(regex);
  score += (matches?.length || 0);

  return score;
}

Why this works:

  • Score calculation is deterministic
  • Tiebreakers eliminate randomness
  • Same query + same DB state → same order

3.5 Reducer Determinism

3.5.1 Reducer Requirements

Reducers MUST be deterministic:

  • Same observations → same snapshot
  • Same merge policies → same result
  • Order-independent (observations sorted deterministically) Pattern:
function computeSnapshot(
  observations: Observation[],
  mergePolicies: MergePolicies
): EntitySnapshot {
  // 1. Sort observations deterministically
  const sorted = sortObservations(observations);

  // 2. Apply merge policies per field
  const snapshot = {};
  const provenance = {};

  for (const [field, policy] of Object.entries(mergePolicies)) {
    const { value, sourceId } = mergeField(field, sorted, policy);
    snapshot[field] = value;
    provenance[field] = sourceId;
  }

  return { snapshot, provenance };
}

3.5.2 Observation Ordering

Observations MUST be sorted deterministically before merging:

  1. Primary sort: observed_at DESC (most recent first)
  2. Secondary sort: id ASC (stable tie-breaker) Sorting Function:
function sortObservations(observations: Observation[]): Observation[] {
  return observations.sort((a, b) => {
    const timeDiff = b.observed_at.getTime() - a.observed_at.getTime();
    if (timeDiff !== 0) return timeDiff;
    return a.id.localeCompare(b.id);
  });
}

3.5.3 ID Generation for Observations

Observation IDs MUST be deterministic:

function generateObservationId(
  entityId: string,
  recordId: string,
  fieldHash: string
): string {
  const hash = createHash('sha256')
    .update(`${entityId}:${recordId}:${fieldHash}`)
    .digest('hex');
  return `obs_${hash.substring(0, 24)}`;
}

Determinism: Same entity + same record + same fields → same observation ID.

3.5.4 Testing Reducer Determinism

Test Pattern:

test('reducer is deterministic', async () => {
  const observations = [obs1, obs2, obs3];
  const snapshot1 = await reducer.computeSnapshot(entityId);

  // Recompute with same observations
  const snapshot2 = await reducer.computeSnapshot(entityId);

  expect(snapshot1.snapshot).toEqual(snapshot2.snapshot);
  expect(snapshot1.provenance).toEqual(snapshot2.provenance);
});
test('reducer handles out-of-order observations', async () => {
  const observations1 = [obs1, obs2, obs3];
  const observations2 = [obs3, obs1, obs2]; // Different order

  const snapshot1 = await reducer.computeSnapshot(entityId, observations1);
  const snapshot2 = await reducer.computeSnapshot(entityId, observations2);

  // Should produce same snapshot regardless of input order
  expect(snapshot1.snapshot).toEqual(snapshot2.snapshot);
});

Related Documents:

4. Determinism and Timestamps

4.1 Audit Timestamps (Acceptable Nondeterminism)

Acceptable:

const record = {
  id: generateRecordId(fileHash, userId), // Deterministic
  created_at: new Date().toISOString(),   // Nondeterministic, but acceptable
  raw_text: text,
};

Why acceptable:

  • created_at is metadata for auditing, not used for ID generation or business logic
  • Does not affect deterministic operations (entity resolution, event generation)
  • Two uploads of same file will have different created_at (expected)

4.2 Ingestion Timestamp as Input (Deterministic)

Pattern: If timestamp is part of input, use it deterministically. Example:

export function ingestFile(
  file: File,
  userId: string,
  explicitTimestamp: string // Provided by caller, deterministic
): Record {
  const fileHash = hashFile(file);
  const recordId = generateRecordId(fileHash, userId, explicitTimestamp);

  return {
    id: recordId,
    created_at: explicitTimestamp, // Use explicit input
    raw_text: extractText(file),
    user_id: userId,
  };
}

5. Determinism in Tests

5.1 Property-Based Testing

Pattern: Generate test cases, verify determinism. Example:

import fc from 'fast-check';
test('entity ID generation is deterministic', () => {
  fc.assert(
    fc.property(
      fc.string(), // Random entity name
      fc.constantFrom('company', 'person', 'location'), // Random type
      (name, type) => {
        const id1 = generateEntityId(type, name);
        const id2 = generateEntityId(type, name);
        return id1 === id2; // MUST be equal
      }
    )
  );
});

5.2 Snapshot Testing

Pattern: Capture output, verify it doesn't change. Example:

test('extraction output matches snapshot', () => {
  const input = loadFixture('invoice.pdf');
  const extracted = extractFields(input, 'FinancialRecord');

  expect(extracted).toMatchSnapshot(); // Fails if output changes
});

5.3 Deterministic Test Fixtures

Pattern: Use fixed timestamps, hashes, IDs in fixtures. Example:

export const TEST_FIXTURES = {
  user: {
    id: 'usr_test_fixed_id',
    created_at: '2024-01-01T00:00:00Z', // Fixed timestamp
  },
  file: {
    name: 'invoice.pdf',
    hash: 'abc123...', // Fixed hash
    content: 'Invoice #123...', // Fixed content
  },
};

6. Determinism and External APIs

6.1 Non-Deterministic External Calls

Problem: External APIs (OpenAI, Gmail) are not deterministic. Mitigation Strategies: Strategy 1: Cache + Replay (Testing)

// In tests, use cached responses
const mockOpenAI = {
  createEmbedding: jest.fn().mockResolvedValue(FIXED_EMBEDDING),
};

Strategy 2: Idempotency Keys (Production)

// Use idempotency keys to ensure same input → same API call → same result
const embedding = await openai.createEmbedding({
  input: text,
  model: 'text-embedding-ada-002',
  idempotency_key: hashText(text), // Deterministic key
});

Strategy 3: Isolate Non-Determinism (Architecture)

  • Embeddings are bounded eventual, not part of core truth (see consistency.md)
  • Core extraction (entities, events) MUST NOT depend on embeddings

6.2 Gmail Attachments (Deterministic Content, Non-Deterministic Timing)

Pattern: Content is deterministic (same email → same attachment), but retrieval timing is not. Solution:

  • Treat Gmail as deterministic source (email ID + attachment ID → content)
  • Ingestion timestamp is nondeterministic (acceptable, metadata only)

7. Determinism Violations and Debugging

7.1 Detecting Nondeterminism

Symptom: Flaky tests (pass sometimes, fail others). Diagnosis Steps:

  1. Run test 100 times: for i in {1..100}; do npm test; done
  2. If any failures, nondeterminism likely
  3. Check for:
    • Random IDs (UUIDs without seeds)
    • Unsorted iteration
    • Timestamp dependencies
    • Race conditions (concurrent execution) Example Debugging:
// Add determinism check to test
test('is deterministic', () => {
  const results = [];
  for (let i = 0; i < 10; i++) {
    results.push(performOperation(input));
  }

  // All results MUST be identical
  const first = JSON.stringify(results[0]);
  for (const result of results) {
    expect(JSON.stringify(result)).toBe(first);
  }
});

7.2 Common Nondeterminism Bugs

Bug 1: UUID in ID generation

// ❌ Bug
const id = uuidv4();
// ✅ Fix
const id = generateDeterministicId(input);

Bug 2: Date.now() in logic

// ❌ Bug
if (Date.now() % 2 === 0) { /* ... */ }
// ✅ Fix
if (explicitTimestamp % 2 === 0) { /* ... */ }

Bug 3: Unsorted Map iteration

// ❌ Bug
for (const [key, value] of map) { }
// ✅ Fix
for (const key of Array.from(map.keys()).sort()) {
  const value = map.get(key);
}

8. Determinism Checklist for Code Review

Use this checklist when reviewing code:

  • No Math.random(), crypto.randomBytes() without fixed seed
  • No Date.now() or new Date() in business logic (metadata only)
  • No UUIDs (uuidv4()) without deterministic generation
  • All iteration over Maps/Sets/Objects is sorted
  • All filesystem reads are sorted
  • All IDs are hash-based (not random)
  • All sorting has deterministic tiebreakers
  • LLM extraction (if used) has config logging and immutable interpretations
  • Tests are reproducible (run 100 times, all pass)
  • External API calls are isolated from core truth

9. Determinism and Performance

9.1 Determinism Cost

Sorting overhead:

  • Sorting adds O(n log n) cost
  • Acceptable for most operations (n < 10,000) Hashing overhead:
  • SHA-256 is fast (~1 microsecond per hash)
  • Negligible for ID generation Sequential processing:
  • May need to process files sequentially (not concurrently) for determinism
  • Use batching if performance critical

9.2 Optimization Strategies

Strategy 1: Cache deterministic results

const cache = new Map<string, string>();
function getCachedEntityId(type: string, name: string): string {
  const key = `${type}:${name}`;
  if (!cache.has(key)) {
    cache.set(key, generateEntityId(type, name));
  }
  return cache.get(key)!;
}

Strategy 2: Batch deterministic operations

// Process 100 files at a time (deterministic order within batch)
for (const batch of chunk(files.sort(), 100)) {
  await Promise.all(batch.map(f => processFile(f)));
}

10. Determinism Invariants (MUST/MUST NOT)

MUST

  1. ID generation MUST be deterministic (hash-based)
  2. Entity resolution MUST be deterministic (same name → same ID) — note: heuristic matching may create duplicates; merge is the repair mechanism
  3. Event generation MUST be deterministic (same fields → same events)
  4. Search ranking MUST be deterministic (tiebreakers required)
  5. Sorting MUST use deterministic tiebreakers (never rely on insertion order)
  6. Tests MUST be reproducible (run 100 times, all pass)
  7. Iteration MUST be sorted (Maps, Sets, filesystem)
  8. Rule-based extraction MUST be deterministic (same text + rules → same fields)
  9. Deduplication MUST use content hash (not timing)
  10. All nondeterminism MUST be documented (e.g., AI interpretation, audit timestamps)
  11. Reducer computation MUST be deterministic (same observations → same snapshot)
  12. Entity merge MUST be deterministic (observations rewritten, snapshot recomputed)
  13. Reinterpretation MUST create NEW observations (never modify existing)

MUST NOT

  1. MUST NOT use random IDs (UUIDs without seeds)
  2. MUST NOT use Date.now() in business logic (metadata only)
  3. MUST NOT iterate unsorted (Maps, Sets, Objects)
  4. MUST NOT rely on filesystem order (always sort)
  5. MUST NOT claim replay determinism for AI interpretation (config is logged, outputs may vary)
  6. MUST NOT use AI interpretation without config logging (provider, model, temperature, prompt_hash)
  7. MUST NOT use nondeterministic ranking (no random sorting)
  8. MUST NOT introduce race conditions (concurrent writes to shared state)
  9. MUST NOT skip tiebreakers (all sorting must have secondary sort)
  10. MUST NOT allow flaky tests (fix or remove)
  11. MUST NOT hide nondeterminism (document if unavoidable)
  12. MUST NOT modify existing observations (immutability invariant)
  13. MUST NOT merge entities across users (user isolation)

11. Deterministic Retrieval vs Similarity-Based Retrieval

11.1 The Read/Write Nondeterminism Split

Neotoma's determinism guarantee applies asymmetrically across the read and write paths:

Path Deterministic? Notes
Read path (retrieval, queries) Yes Same query + same DB state → same results, same order, every execution
Write path (AI interpretation) No LLM extraction is stochastic; mitigated by canonicalization + hashing + deduplication
Write path (agent tool selection) No LLM chooses entity types, fields, relationships stochastically; see Section 1.6
Query formulation (agent constructs query) No LLM decides which MCP tool to call and with what parameters; see Section 11.3

Key insight: Once data enters the graph, all retrieval operations are fully deterministic. Nondeterminism is confined to the write path and query formulation layer, never the retrieval mechanism itself.

11.2 Why Structured Retrieval Differs from Vector Retrieval

Common retrieval systems (RAG, vector databases) use similarity-based search: embed the query into a vector, return the k nearest neighbors. Neotoma uses predicate-based queries over typed entities. These produce categorically different failure modes:

Property 1: Discrete vs continuous query space

Vector search projects a query into a continuous embedding space where small perturbations shift results. Structured retrieval operates over a discrete, schema-constrained space: entity types, field names, relationship types, sort orders. Two differently-phrased queries that target the same entity type and fields return identical results.

Property 2: Exact vs approximate execution

Vector search returns approximate results ranked by distance. A relevant result at position k+1 is silently excluded. Structured retrieval returns every record matching the predicate — no threshold, no top-k cutoff, no relevance score that might exclude a valid result. If the query is correct, the results are complete.

Property 3: Detectable vs silent failures

When vector retrieval returns 8 out of 10 relevant results, the output looks identical to 10 out of 10 — the missing 2 are invisible. When structured retrieval targets the wrong entity type, it returns zero results or obviously wrong results. The failure is visible and correctable.

Property 4: Stable vs drift-prone ordering

Vector retrieval rankings shift with embedding model updates, index rebuilds, or quantization settings. Structured retrieval returns results in a deterministic sort order with explicit tiebreakers (e.g., created_at DESC, entity_id ASC). The order is a property of the data, not of a scoring function.

Summary: Vector retrieval is a search operation (approximate, ranked, threshold-dependent). Structured retrieval is a query operation (exact, predicate-based, sort-stable). Queries against stable data are deterministic by construction. Searches against projected representations are not.

11.3 Query Formulation Stochasticity

When an LLM agent retrieves data from Neotoma, it constructs the query stochastically — choosing which MCP tool to call and with what parameters. This is real nondeterminism, but it differs from vector retrieval nondeterminism in important ways:

Schema constrains the query space. MCP tool definitions specify exactly which parameters are available (entity_type, filters, limits, relationship types). The LLM selects from a finite menu of valid query formulations, not a continuous embedding space.

Execution adds zero variance. Once the query is formed — however it was formed — the system returns every matching record in deterministic order. The retrieval mechanism contributes no additional nondeterminism. In vector systems, both query formulation AND retrieval are nondeterministic (two compounding sources).

Errors are visible. A malformed or misdirected structured query produces zero results, an error, or obviously wrong results. A slightly-off embedding query silently returns plausible but incomplete results.

Equivalent queries converge. retrieve_entities(entity_type="task", status="open") and retrieve_entities(entity_type="task", filters={status: "open"}) execute identically despite different formulations. The discrete query space has many-to-one mappings from formulation to execution.

Policy: Neotoma does not claim zero nondeterminism in the agent-memory interaction. The claim is variance concentration: all nondeterminism resides in the query formulation layer (discrete, schema-bounded, detectable on failure) and is eliminated from the retrieval layer (where in similarity-based systems it is continuous and silent).

Improvements roadmap: Architectural improvements to narrow query formulation variance — including query-time entity type normalization, parameter validation, retrieval templates, result diagnostics, and replay testing — are defined in query_convergence.md. Write-path convergence improvements are defined in bounded_convergence.md.

11.4 Nondeterminism Location Summary

System Query formulation Retrieval mechanism Failure mode
Vector/RAG Stochastic (embedding) Approximate (top-k similarity) Silent incompleteness
Neotoma Stochastic (tool selection) Deterministic (predicate match) Visible errors

Agent Instructions

When to Load This Document

Load docs/architecture/determinism.md when:

  • Implementing any extraction, entity resolution, or event generation logic
  • Writing ID generation or hashing functions
  • Implementing sorting or ranking algorithms
  • Writing tests that must be reproducible
  • Reviewing code for nondeterminism bugs
  • Debugging flaky tests
  • Adding any operation that processes collections

Required Co-Loaded Documents

  • docs/NEOTOMA_MANIFEST.md (determinism as core principle)
  • docs/architecture/architecture.md (layer boundaries)
  • docs/architecture/consistency.md (eventual vs strong consistency)
  • docs/architecture/bounded_convergence.md (write-path convergence improvements)
  • docs/architecture/query_convergence.md (query formulation convergence improvements)
  • docs/subsystems/schema.md (schema-based extraction)
  • docs/testing/testing_standard.md (deterministic test patterns)

Constraints Agents Must Enforce

  1. All IDs MUST be hash-based (no UUIDs without seeds)
  2. All iteration MUST be sorted (Maps, Sets, filesystem)
  3. All sorting MUST have deterministic tiebreakers
  4. No Math.random() or Date.now() in business logic
  5. Entity resolution MUST normalize then hash
  6. Event generation MUST be deterministic per schema
  7. Search ranking MUST use rule-based scoring + tiebreakers
  8. Tests MUST be reproducible (no flaky tests)
  9. External API calls MUST be isolated from core truth
  10. All nondeterminism MUST be documented

Forbidden Patterns

  • Random UUID generation for IDs
  • Date.now() in business logic
  • Unsorted iteration over collections
  • LLM extraction without config logging and immutable interpretations
  • Nondeterministic ranking or sorting
  • Flaky tests left unfixed
  • Race conditions in concurrent code
  • Undocumented nondeterminism

Validation Checklist

  • All IDs are hash-based (not random)
  • All collections are sorted before iteration
  • All sorting has deterministic tiebreakers
  • No Date.now() or Math.random() in business logic
  • Entity resolution normalizes before hashing
  • Event generation is schema-driven
  • Search ranking is rule-based with tiebreakers
  • Tests pass 100 times in a row (no flakes)
  • External API nondeterminism is isolated
  • Code review checklist completed (Section 8)