Implementation:LMCache LMCache Memory Bloom Filter Strategy

Knowledge Sources	LMCache
Domains	Probabilistic Data Structures, Cache Statistics
Last Updated	2026-02-09 00:00 GMT

Overview

MemoryBloomFilterStrategy is a memory-based record strategy that uses a Bloom filter to track and deduplicate KV cache chunks.

Description

This class extends RecordStrategy and maintains an in-memory Bloom filter for tracking which cache chunks have been observed across requests. During preprocessing, token IDs are split into chunks and each chunk is hashed into multiple Bloom filter positions. The record method atomically inserts these positions into the global Bloom filter and counts unique chunks (those not previously seen). Configuration parameters for expected chunk capacity (default 20 million) and false positive rate (default 0.01) are read from the engine's extra configuration. The strategy also exports Prometheus metrics for Bloom filter memory usage and fill rate.

Usage

Use this strategy when you need lightweight, memory-efficient approximate tracking of unique KV cache chunks across requests. It is suitable for high-throughput scenarios where exact counting is not required and a small false positive rate is acceptable.

Code Reference

Source Location

• Repository: LMCache
• File: lmcache/v1/lookup_client/record_strategies/memory_bloom_filter.py
• Lines: 1-81

Signature

class MemoryBloomFilterStrategy(RecordStrategy):
    def __init__(self, config, chunk_size: int): ...

    def preprocess(self, token_ids: list[int]) -> list[list[int]]: ...

    def record(self, chunk_bloom_positions: list[list[int]], lookup_id: str) -> None: ...

    def get_statistics(self) -> dict: ...

    def setup_metrics(self, prometheus_logger) -> None: ...

    def reset(self) -> None: ...

Import

from lmcache.v1.lookup_client.record_strategies.memory_bloom_filter import MemoryBloomFilterStrategy

I/O Contract

Inputs

Name	Type	Required	Description
config	LMCacheEngineConfig	Yes	Engine configuration providing extra config values for Bloom filter sizing
chunk_size	int	Yes	Number of tokens per chunk for hash computation
token_ids	list[int]	Yes	Token IDs to preprocess into Bloom filter hash positions
chunk_bloom_positions	list[list[int]]	Yes	Pre-computed Bloom filter hash positions for each chunk
lookup_id	str	Yes	Identifier for the lookup request associated with this record call

Outputs

Name	Type	Description
preprocess result	list[list[int]]	List of Bloom filter hash positions per chunk, each inner list has hash_count elements
statistics	dict	Dictionary with total_chunks, unique_chunks_count, and bloom_filter sub-statistics

Usage Examples

from lmcache.v1.lookup_client.record_strategies.memory_bloom_filter import MemoryBloomFilterStrategy

# Initialize with engine config and chunk size
strategy = MemoryBloomFilterStrategy(config, chunk_size=256)

# Preprocess tokens into bloom filter positions
positions = strategy.preprocess(token_ids=[1, 2, 3, 4, 5])

# Record the positions (updates bloom filter and statistics)
strategy.record(positions, lookup_id="req-001")

# Get statistics
stats = strategy.get_statistics()

# Reset all state
strategy.reset()