Probabilistic Data Structures

Bloom filters, Count-Min Sketches, and HyperLogLog — the primitives behind Quint’s behavioral fingerprint

Status: shipped. The primitives (Bloom, Count-Min, HyperLogLog, EWMA, Markov chain) are in production inside Stage 1’s fingerprint; Stage 1 itself is in shadow mode.

Probabilistic Data Structures

Quint’s behavioral fingerprint stores per-agent history in roughly six kilobytes. It updates on every tool call in nanoseconds and answers membership and frequency queries in nanoseconds. No database, no hash set, no sorted list can meet those three constraints simultaneously. The solution is a family of algorithms that trade bounded, configurable error for dramatic wins in memory and time complexity.

Three primitives do the heavy lifting: Bloom filters for set membership, Count-Min Sketches for frequency estimation, and HyperLogLog for cardinality estimation. Every part of the fingerprint reduces to one of these three or to a small composition of them with a capability distribution and a Markov chain.

Bloom Filter: “Has this agent ever seen X?”

A Bloom filter is a bit array plus a handful of independent hash functions. To insert an element X, hash X with each function and set the corresponding bits to 1. To query membership, hash X again and check the same bits — if any bit is 0, X is definitively absent; if all bits are 1, X is probably present with a configurable false-positive rate.

Properties that matter

• Zero false negatives. If the filter says “never seen,” the element was never inserted. This property is load-bearing for novelty detection — an attacker cannot hide a novel action from a Bloom filter.
• Constant time. Insert and query are O(k) where k is the number of hash functions. Typical k is 4–7.
• Tiny memory. A 128-byte Bloom filter holds thousands of entries at 1% false positive rate.
• No deletions. Bloom filters cannot unlearn. For agent histories, this is a feature — the filter accumulates monotonically.

Quint’s usage

The agent fingerprint contains three hierarchical Bloom filters, each 64–128 bytes:

Filter	Size	Answers
DomainSeen	64 bytes	Has this agent ever contacted this protocol domain?
ServerSeen	128 bytes	Has this agent ever used this MCP server?
ToolSeen	128 bytes	Has this agent ever called this specific tool?

Gate 1 of the scoring pipeline checks all three on every tool call. A novel domain is a stronger signal than a novel server, which is stronger than a novel tool — the hierarchy is intentional and reflects the semantic weight of each transition.

Count-Min Sketch: “How often has this agent done X?”

A Count-Min Sketch is a 2D array of counters plus multiple hash functions. Insertion increments one counter per row at a hash-determined column. Querying returns the minimum counter across all rows.

The minimum is the trick. Hash collisions cause counters to overestimate — if two elements hash to the same column in a row, that counter gets incremented for both. The minimum across multiple independent rows gives the tightest upper bound on the true count because collisions rarely align across all rows simultaneously.

Properties that matter

• Overestimates never, underestimates never. The return value is always ≥ the true count and < the true count plus a bounded error that depends on the sketch dimensions.
• Constant time. O(r) for a sketch with r rows. Typical r is 4.
• Fixed memory regardless of input size. A 2 kilobyte CMS tracks millions of distinct keys with ~1% error.
• Streaming-friendly. No resizing, no rehashing, no bulk operations.

Quint’s usage

The fingerprint contains two CMSes:

Sketch	Shape	Use
Primary CMS	4 rows × 256 columns (2 KB)	Tool frequency tracking
Compact CMS	4 rows × 64 columns (512 B)	Per-session resource flow

Gate 1 queries the primary CMS to validate that a tool’s observed frequency falls within the established envelope. Gate 2 uses the count to compute relative frequency ratios and detect spikes — a tool used 5 times yesterday and 500 times today produces a measurable spike signal regardless of whether either count is individually alarming.

HyperLogLog: “How many distinct things has this agent done?”

HyperLogLog is the most mathematically elegant of the three. To count unique elements without storing them, HLL hashes each element and tracks the position of the leftmost 1-bit in the hash. Rare patterns — hashes with many leading zeros — occur only when many distinct elements have been seen. The maximum leading-zero position across many parallel registers gives a probabilistic estimate of the total distinct count.

Properties that matter

• Fixed memory for any input size. A typical HLL uses 16 kilobits (roughly 2 KB) to count up to billions of distinct items.
• Bounded error. Standard HLL achieves ~0.8% relative error on cardinality estimates.
• Mergeable. Two HLLs counting different sets can be merged into an HLL counting the union, enabling cross-agent and fleet-wide aggregates.

Quint’s usage

The fingerprint contains three HLL sketches tracking distinct-element counts:

Sketch	Tracks
UniqueTools	Distinct tools this agent has ever invoked
UniqueServers	Distinct MCP servers this agent has connected to
UniqueDomains	Distinct protocol domains this agent has touched

Beyond raw cardinality, HLL enables a growth-rate signal. Comparing the current cardinality to a snapshot from 60 seconds ago produces a sudden-exploration indicator — an agent that has used 47 distinct tools historically and suddenly uses 3 new ones in a 10-second burst is exhibiting exploration behavior characteristic of reconnaissance or lateral movement.

Jensen-Shannon Divergence: shape comparison

The three primitives above answer categorical questions: is X in the set, how often has X been seen, how many distinct things have been observed. Attacks that shift an agent’s behavioral shape — moving the agent from primarily file-read activity to primarily network-outbound activity — require a different signal.

Jensen-Shannon Divergence (JSD) measures the difference between two probability distributions on the same finite support. It is bounded between 0 (identical) and 1 (completely disjoint), symmetric, and robust to zero-probability support mismatches that break naive KL-divergence.

The fingerprint maintains a capability distribution — a vector tracking how often the agent uses each of twelve abstract capability categories (Read, Write, Execute, Network, Search, Edit, and others). Every action updates the distribution. Every new action’s capability produces a one-hot vector that is compared against the historical distribution via JSD. A JSD below 0.1 means the action aligns with the agent’s shape. A JSD above 0.3 means the action represents a meaningful capability shift.

Why probabilistic?

Every structure described here has configurable, bounded error. The error is the price paid for constant-time operations and tiny memory footprints. Stage 1 does not promise perfect recall — it promises rare errors in predictable directions, combined with sub-microsecond latency that makes the detection practical to run on every event inline.

The bounded error is the reason the full 4-gate pipeline exists. Gate 1 catches the common-case agreement between action and fingerprint with high confidence. Gate 2 expands the signal set when gate 1 fires. Gate 3 requires corroboration across multiple independent signals before escalating, which mathematically cancels most of the individual structures’ false-positive rates — three signals with 1% error independently agreeing produces a combined false-positive rate below 0.001%.

This is why probabilistic data structures are the correct foundation for hot-path security detection. They are fast enough to run on every event, accurate enough in the common case that their errors are dominated by corroboration in the uncommon case, and compact enough that the full per-agent history fits in the cache of a single CPU core.