Foundry/retrieval

Retrieval

ASIC-accelerated hash-based document retrieval for LLM memory augmentation.

Why Hash-Based Retrieval?

Traditional retrieval uses dense embeddings + cosine similarity:

• Compute 768+ dim embedding for query
• Compare against millions of document embeddings
• GPU-heavy, memory-bound

Hash-based retrieval uses locality-sensitive hashing:

• Compute hash signature for query (fast)
• Find documents with similar hash signatures (bit operations)
• CPU/ASIC-friendly, embarrassingly parallel

The ASIC advantage: SHA-256 miners compute billions of hashes per second at ~1W. If retrieval reduces to hashing, you get 1000x better cost/watt than GPU.

Architecture

┌─────────────────────────────────────────────────────────────────┐
│                     Foundry LLM                                 │
│                                                                 │
│  ┌──────────┐    ┌───────────┐    ┌──────────────────────────┐ │
│  │ Tokenize │───▶│ Attention │───▶│ Generate                 │ │
│  └──────────┘    └─────┬─────┘    └──────────────────────────┘ │
│                        │                                        │
│                        │ retrieve context                       │
│                        ▼                                        │
│              ┌─────────────────┐                                │
│              │  fr_retrieval   │ ◀── This module               │
│              └────────┬────────┘                                │
│                       │                                         │
└───────────────────────┼─────────────────────────────────────────┘
                        │
          ┌─────────────┴─────────────┐
          │                           │
          ▼                           ▼
   ┌─────────────┐            ┌─────────────┐
   │ CPU Backend │            │ASIC Backend │
   │ (fallback)  │            │ (hash-hdc)  │
   └─────────────┘            └─────────────┘
                                     │
                              ┌──────┴──────┐
                              │ USB/UART    │
                              │ ASIC Miner  │
                              └─────────────┘

Hash Techniques

Technique	Use Case	How It Works
SimHash	Text similarity	Hash of weighted token features
MinHash	Set similarity (Jaccard)	Min of many hash permutations
LSH	Approximate nearest neighbor	Hash buckets group similar items

SimHash for Text

Document: "the quick brown fox"

1. Extract features: {"the": 1, "quick": 1, "brown": 1, "fox": 1}
2. For each feature, compute SHA256(feature) → 256 bits
3. For each bit position:
   - If bit is 1, add feature weight (+1)
   - If bit is 0, subtract feature weight (-1)
4. Final signature: sign(sum) for each position → 256 bits

Similar documents have similar bit patterns.
Hamming distance ≈ cosine distance.

LSH Index Structure

┌─────────────────────────────────────────┐
│              LSH Index                  │
├─────────────────────────────────────────┤
│ Band 0: hash(sig[0:32])   → bucket_id   │
│ Band 1: hash(sig[32:64])  → bucket_id   │
│ Band 2: hash(sig[64:96])  → bucket_id   │
│ ...                                     │
│ Band 7: hash(sig[224:256]) → bucket_id  │
└─────────────────────────────────────────┘

Query: Check all bands, candidates = union of matching buckets
       Then rank candidates by full signature similarity

Integration with hash-hdc

The ASIC backend uses hash-hdc's device abstraction:

// hash-hdc provides:
typedef struct asic_device asic_device;
asic_device* asic_open_mock(void);
asic_device* asic_open_lv03(const char *port);
int asic_hash_batch(asic_device *dev, uint8_t **inputs, size_t n, uint8_t **outputs);

This module builds on top:

// Compute SimHash signature using ASIC
fr_signature* fr_simhash_asic(asic_device *dev, const char *text);

// Batch compute signatures (saturates ASIC throughput)
int fr_simhash_batch_asic(asic_device *dev, const char **texts, size_t n,
                          fr_signature **sigs);

API Overview

Types

fr_signature     // 256-bit hash signature
fr_index         // LSH index structure
fr_result        // Single retrieval result (doc_id, score)
fr_results       // List of retrieval results
fr_config        // Retrieval configuration

Core Functions

// Signatures
fr_signature* fr_simhash(const char *text);
fr_signature* fr_minhash(const char **tokens, size_t n);
int fr_hamming(fr_signature *a, fr_signature *b);

// Indexing
fr_index* fr_index_new(fr_config *config);
int fr_index_add(fr_index *idx, uint64_t doc_id, fr_signature *sig);
int fr_index_add_text(fr_index *idx, uint64_t doc_id, const char *text);

// Retrieval
fr_results* fr_search(fr_index *idx, fr_signature *query, int top_k);
fr_results* fr_search_text(fr_index *idx, const char *query, int top_k);

// ASIC acceleration
void fr_set_backend(fr_index *idx, asic_device *dev);

Usage Example

Basic RAG Pipeline

#include "retrieval/retrieval.h"
#include "../hash-hdc/lib/asic/asic.h"

// Setup
fr_config config = fr_config_default();
fr_index *idx = fr_index_new(&config);

// Optional: Enable ASIC acceleration
asic_device *asic = asic_open_lv03("/dev/tty.usbserial-0001");
if (asic) {
    fr_set_backend(idx, asic);
}

// Index documents
fr_index_add_text(idx, 0, "The capital of France is Paris.");
fr_index_add_text(idx, 1, "Python is a programming language.");
fr_index_add_text(idx, 2, "Paris is known for the Eiffel Tower.");
// ... millions more

// Query
fr_results *results = fr_search_text(idx, "What is the capital of France?", 5);

// Use results to augment LLM context
for (int i = 0; i < results->count; i++) {
    printf("Doc %llu (score: %d): %s\n",
           results->items[i].doc_id,
           results->items[i].score,
           get_document_text(results->items[i].doc_id));
}

// Cleanup
fr_results_free(results);
fr_index_free(idx);
asic_close(asic);

Tight Integration (Retro-style)

// During transformer forward pass
tm_tensor* transformer_layer(tm_tensor *x, int layer_idx, fr_index *memory) {
    // Standard attention
    tm_tensor *attn = fa_self_attention(x, weights->qkv, weights->o, &config);

    // Retrieve relevant context based on hidden state
    char *query_text = extract_query_from_hidden(x);  // Implementation-specific
    fr_results *retrieved = fr_search_text(memory, query_text, 4);

    // Cross-attention with retrieved context
    tm_tensor *context = embed_retrieved_docs(retrieved);
    tm_tensor *cross_attn = fa_cross_attention(attn, context, weights->cross, &config);

    // FFN
    tm_tensor *out = ffn_forward(cross_attn, weights->ffn);

    fr_results_free(retrieved);
    return out;
}

Performance Targets

Metric	CPU Baseline	With ASIC
Index 1M docs	~60 sec	~2 sec
Query latency	~5 ms	~0.5 ms
Throughput	~10K qps	~100K qps
Power	~50W	~5W

File Format

Index Format (.fri)

[Header: 16 bytes]
  magic: "FRI1" (4 bytes)
  version: uint16
  num_docs: uint64
  config_flags: uint16

[Config: variable]
  num_bands: uint8
  band_size: uint8
  signature_bits: uint16

[Signatures: num_docs * 32 bytes]
  For each doc:
    signature: uint8[32]  // 256 bits

[LSH Tables: num_bands * variable]
  For each band:
    num_buckets: uint32
    For each bucket:
      bucket_hash: uint32
      num_docs: uint32
      doc_ids: uint64[num_docs]

Dependencies

• ../tensor/ - For embedding integration (optional)
• ../tokenizer/ - For text tokenization
• ../../hash-hdc/lib/asic/ - ASIC device abstraction