/message_matching_notes.md

Message Array Matching for Tree Conversations

Problem Statement

When calling model.prompt(messages=[...]) with a full message array, we want to:

1. Check if this exact conversation path already exists in the database
2. If yes, return the existing response or branch from there
3. If no, create new responses and link them to the tree
4. Do this efficiently without scanning all responses

Key Challenge: Matching Messages

Given a messages array like:

[
    llm.System("you are a useful assistant"),
    llm.User("Capital of France?"),
    llm.Assistant("Paris"),
    llm.User("Germany?")
]

We need to find if there's an existing conversation path:

• Root: System("you are a useful assistant") + User("Capital of France?") → Response("Paris")
• Child: User("Germany?") → Response(???)

Design Questions

1. What to Hash?

• ✅ System message content
• ✅ User message content
• ✅ Assistant message content (for matching, not predicting)
• ❓ Attachments/images - hash the binary content?
• ❓ Tool calls - hash the function name + arguments?
• ❓ Tool results - hash the output?
• ❌ Timestamps - these should NOT affect matching
• ❌ Model used - same conversation, different models should be separate trees
• ❓ Options (temperature, etc.) - should these affect matching?

2. Where to Store Hashes?

Options:

• A) Store hash on each response row
• B) Store hash on prompt/response pairs
• C) Store hash representing entire path from root
• D) Combination approach

3. Hash Scope

• Per-response hash: Hash of (system + prompt) that created this response
• Path hash: Cumulative hash from root to this node
• Content hash: Hash of just the response content

4. Timestamp Handling

• Store actual timestamp separately
• Don't include in hash
• Use for display/sorting only

Initial Design Proposal

Schema Addition

ALTER TABLE responses ADD COLUMN prompt_hash TEXT;
ALTER TABLE responses ADD COLUMN path_hash TEXT;
CREATE INDEX idx_responses_prompt_hash ON responses(prompt_hash);
CREATE INDEX idx_responses_path_hash ON responses(path_hash);

Hash Strategy

prompt_hash: Hash of the input that created this response

• For simple text: hash(system + prompt)
• For images: hash(system + prompt + image_content_hash)
• For tools: hash(system + prompt + tool_results)

path_hash: Cumulative hash from root

• Represents the entire conversation history
• path_hash = hash(parent.path_hash + current.prompt_hash)
• Root nodes: path_hash = prompt_hash

Hashing Considerations

What to Include in Hash

Stable (include in hash):

• System message text
• User message text
• Assistant message text (when matching existing)
• Tool call names and arguments
• Tool result outputs
• Image content (via content hash)
• Attachment content (via content hash)

Unstable (exclude from hash):

• Timestamps
• Response IDs
• Duration
• Token counts
• Metadata about the call

Options/Parameters

Should temperature affect matching?

• Scenario: Same prompt with temperature=0 vs temperature=1
• Different temperatures could yield different responses
• Decision: Include relevant options in hash
• Create separate branches for different option sets

Algorithm: Finding Existing Path

Given messages array: [Sys, User1, Asst1, User2]

def find_or_create_path(db, conversation_id, messages):
    """
    Find existing path or create new responses.
    Returns the response_id of the last message.
    """
    current_parent = None
    
    for i in range(0, len(messages), 2):  # Process pairs
        if i + 1 >= len(messages):
            break  # Incomplete pair
            
        # Get prompt (User or System+User)
        prompt_msg = messages[i]
        if isinstance(prompt_msg, llm.System):
            system = prompt_msg.content
            prompt_msg = messages[i + 1]
            prompt = prompt_msg.content
            i += 1
        else:
            system = None
            prompt = prompt_msg.content
        
        # Get expected response
        if i + 1 < len(messages) and isinstance(messages[i + 1], llm.Assistant):
            expected_response = messages[i + 1].content
        else:
            expected_response = None
        
        # Calculate prompt hash
        prompt_hash = calculate_prompt_hash(system, prompt, attachments, tools)
        
        # Look for existing response with this prompt_hash and parent
        existing = db.execute("""
            SELECT id, response 
            FROM responses 
            WHERE conversation_id = ?
            AND parent_response_id IS ?
            AND prompt_hash = ?
        """, [conversation_id, current_parent, prompt_hash]).fetchone()
        
        if existing and expected_response:
            # Verify response matches
            if existing[1] == expected_response:
                current_parent = existing[0]
                continue
        
        # No match found - need to create new response
        # ...

Complex Content Hashing

Images

def hash_image_attachment(attachment):
    if attachment.content:
        return hashlib.sha256(attachment.content).hexdigest()
    elif attachment.url:
        # Store URL but flag that content may change
        return f"url:{hashlib.sha256(attachment.url.encode()).hexdigest()}"
    else:
        return hashlib.sha256(attachment.path.encode()).hexdigest()

Tool Calls

def hash_tool_call(tool_call):
    data = {
        'name': tool_call.name,
        'arguments': tool_call.arguments,
    }
    return hashlib.sha256(json.dumps(data, sort_keys=True).encode()).hexdigest()

Tool Results

def hash_tool_result(tool_result):
    data = {
        'name': tool_result.name,
        'output': tool_result.output,
    }
    # Include attachment hashes if present
    if tool_result.attachments:
        data['attachments'] = [hash_image_attachment(a) for a in tool_result.attachments]
    return hashlib.sha256(json.dumps(data, sort_keys=True).encode()).hexdigest()

Edge Cases

1. Partial Match

Messages: [User1, Asst1, User2] Existing: [User1, Asst1] with different Asst1 response

Solution: Create branch from User1 with different response

2. Multiple Models

Same prompt, different models Solution: prompt_hash doesn't include model, so they share the same tree

3. Non-deterministic Responses

Same prompt, same model, different responses (temperature > 0) Solution:

• Multiple responses with same parent + prompt_hash
• Tree shows different attempts
• Can compare results

4. Streaming vs Non-streaming

Same prompt, different streaming setting Solution: streaming is implementation detail, not conversation content

Experiments to Run

1. ✅ Test basic hash calculation
2. ✅ Test hash with images
3. ✅ Test hash with tool calls
4. ✅ Test matching algorithm
5. ✅ Test path hash calculation
6. ✅ Test with real conversation scenarios

Notes

Will be filled in as experiments progress

Implementation Complete ✅

Date: September 27, 2025

Schema Changes:

• Added 3 hash columns to responses table via migration m023_response_hashing
• prompt_hash: Hash of the input that created this response
• response_hash: Hash of the response content
• path_hash: Cumulative hash representing path from root

Indexes Created:

• Index on prompt_hash for fast lookup
• Index on path_hash for finding exact conversation paths
• Composite index on (conversation_id, parent_response_id, prompt_hash) for matching children

Test Results: 23/23 tests passing ✅

Key Findings

1. Hash Stability

• Text hashing is straightforward and deterministic
• Binary content (images) hashed via SHA-256 of bytes
• Tool calls/results hashed via JSON serialization (sorted keys)
• Timestamps explicitly EXCLUDED from hashes

2. Hash Composition

prompt_hash includes:

• System message text
• User prompt text
• Attachment hashes (content, URL, or path)
• Tool call hashes (name + arguments)
• Tool result hashes (name + output + attachment hashes)
• Deterministic options only (temperature=0, max_tokens, stop_sequences)

prompt_hash excludes:

• Timestamps (stored separately)
• Non-deterministic options (temperature > 0)
• Response IDs
• Token counts
• Duration metrics

3. Path Hash Strategy

Two-level hashing:

1. prompt_hash: Identifies unique input context
2. path_hash: Identifies unique conversation path

Path hash calculation:

Root node: path_hash = prompt_hash
Child node: path_hash = hash(parent.path_hash + ":" + current.prompt_hash)

This creates a unique fingerprint for every path through the tree.

4. Matching Algorithm

# Find existing response by:
1. conversation_id (which conversation)
2. parent_response_id (position in tree)  
3. prompt_hash (what input created it)

# If found: reuse existing response
# If not found: create new response

5. Handling Non-Determinism

Same prompt, different responses:

• Temperature > 0 can produce different outputs
• Multiple responses can share same (parent, prompt_hash)
• Tree naturally represents these alternatives
• Query returns first match (LIMIT 1) or all for comparison

Example:

Root: "Tell me a joke"
  -> Response A: "Why did chicken..." (first attempt)
  -> Response B: "What do you call..." (second attempt)

Both have same parent and prompt_hash but different response_hash.

6. Attachment/Tool Hashing

Images:

• If content available: hash the bytes
• If URL only: hash the URL (note: content may change)
• If path only: hash the path (note: file may change)

Tools:

• Tool calls: hash(name + arguments)
• Tool results: hash(name + output + [attachment_hashes])

7. Timestamp Strategy

Problem: Need timestamps for auditing but they break matching

Solution:

• Store timestamp in datetime_utc column
• EXCLUDE from all hashes
• Use for display and sorting only
• Each call records its own timestamp even if reusing response

Benefits:

• Can track when each call was made
• Can see response was reused (same hash, different timestamp)
• Can analyze response caching patterns

Use Cases Enabled

1. Efficient Message Array Handling

# First call
response = model.prompt(messages=[
    llm.System("You are helpful"),
    llm.User("Capital of France?")
])
# Creates: root response

# Second call with same context
response = model.prompt(messages=[
    llm.System("You are helpful"),
    llm.User("Capital of France?")
])
# Finds: existing root, reuses it

# Third call extending conversation
response = model.prompt(messages=[
    llm.System("You are helpful"),
    llm.User("Capital of France?"),
    llm.Assistant("Paris"),
    llm.User("Germany?")
])
# Finds: root, verifies "Paris" matches, creates/finds child for "Germany?"

2. Conversation Caching

• Avoid redundant API calls for identical prompts
• Track which responses were generated vs cached
• Analyze cache hit rates

3. A/B Testing

• Same prompt, different models
• Same prompt, different temperature
• Compare results in tree structure

4. Debugging

• Trace exact conversation path via path_hash
• Find all instances of a particular prompt
• Compare different response branches

Performance Considerations

Index Strategy:

• Primary lookup: (conversation_id, parent_response_id, prompt_hash)
• Alternative: path_hash for finding exact paths
• All hash columns indexed for fast queries

Hash Collision:

• SHA-256: effectively zero collision probability
• 64 hex characters = 2^256 possible values
• More hashes exist than atoms in universe

Storage Overhead:

• 3 hash columns × 64 bytes = 192 bytes per response
• Negligible compared to prompt/response content
• Enables O(1) lookups vs O(n) content comparison

Edge Cases Handled

✅ Images with same content but different paths ✅ URLs that may point to changing content
✅ Tool calls with complex nested arguments ✅ Multiple responses with same prompt (non-deterministic) ✅ Empty/null values in various fields ✅ Unicode text in prompts/responses ✅ Very long prompts (hashed efficiently)

Integration Path

Phase 1: Schema (Complete)

• ✅ Add hash columns
• ✅ Create indexes
• ✅ Test hashing functions

Phase 2: Response Logging (Next)

• Calculate hashes when logging responses
• Populate hash columns automatically
• Backfill existing responses

Phase 3: Matching API (Next)

• Implement find_or_create_from_messages()
• Integrate with model.prompt()
• Handle cache hits/misses

Phase 4: CLI/UI (Future)

• Show cache hit indicators
• Display path hashes in logs
• Visualize response reuse

Open Questions Resolved

❓ Include timestamps in hash? ✅ NO - timestamps stored separately

❓ Include model name in hash? ✅ NO - same conversation, different models = separate branches

❓ Include temperature in hash? ✅ ONLY if temperature=0 (deterministic)

❓ How to hash images? ✅ Hash content bytes, or URL/path if no content

❓ Handle tool calls? ✅ Hash function name + arguments as JSON

❓ Multiple responses with same prompt? ✅ Allowed - tree shows alternatives

Recommendations

1. Always calculate hashes: Even for new responses
2. Index all hash columns: Essential for performance
3. Use path_hash for exact matches: Fast full-path lookups
4. Log cache hits separately: Track reuse metrics
5. Consider hash column in UI: Show when response was cached

Next Steps

1. Create migration for hash columns ✅
2. Update Response.log() to calculate hashes
3. Implement find_or_create_from_messages()
4. Test with real LLM API calls
5. Add cache hit tracking
6. Update documentation