0

Group prompts into templates under concurrent ingestion

by Frontier Interview· about 4 hours ago· ⑂ 0 remixes

Question: Group prompts into templates under concurrent ingestion

Companies: Anthropic

Difficulty: Medium

Problem statement

An API receives prompts from many threads. Most come from a few templates filled with different values: Summarize ticket 48213 for alice@acme.com and Summarize ticket 1007 for bo@x.io share the template Summarize ticket <NUM> for <EMAIL>.

  • template_of(prompt) replaces quoted strings, URLs, emails, UUIDs and whole-token numbers with <STR>, <URL>, <EMAIL>, <UUID> and <NUM>, and collapses whitespace. gpt4 and v2 are not numbers.
  • TemplateIndex counts prompts per template while many threads call add at once, keeps the first 3 example prompts per template, and answers count(template), examples(template) and top(k) (most frequent first, ties alphabetical).
  • Counts must be exact, and threads adding different templates should rarely wait for each other.
def template_of(prompt): ...


class TemplateIndex:
    def __init__(self, shards=64, examples_per_template=3): ...
    def add(self, prompt): ...
    def count(self, template): ...
    def examples(self, template): ...
    def top(self, k): ...
    def total(self): ...

Approach

The setting. An API sees millions of prompts a day. Most are produced by a few hundred templates in customers' code: Summarize ticket 48213 for alice@acme.com and Summarize ticket 1007 for bo@x.io are the same template with different values. Grouping them shows which templates dominate traffic (for caching, cost reports, abuse detection). Prompts arrive from many threads at once.

Clarify first. Which spans count as variables (numbers, emails, URLs, UUIDs, quoted strings here; names are not detectable with rules, say so)? Case-sensitive (yes: case changes meaning in code)? Is an exact count required under concurrency (yes)? How many distinct templates (assume up to ~10⁶, so they fit in memory)?

Step 1: normalize a prompt to its template. Replace each kind of variable with a placeholder, in an order that avoids partial matches:

  1. Quoted strings → <STR> first, so digits inside quotes do not become <NUM>.
  2. URLs → <URL> before emails (a URL can contain @).
  3. Emails → <EMAIL>.
  4. UUIDs → <UUID> before numbers (UUIDs contain digit runs).
  5. Numbers → <NUM>, only as whole tokens: v2 and gpt4 stay as they are.
  6. Collapse runs of whitespace.

Compile the patterns once; regex compilation inside the hot path is a common slowdown.

Step 2: the index — "array plus hash map". One dict behind one lock serializes every thread. Instead keep an array of S shards, each a dict with its own lock. A template goes to shard hash(template) % S. Two threads collide only if their templates land on the same shard, so with S = 64 and evenly spread templates, contention drops ~64×. Use a stable hash (from hashlib), not Python's hash(), so shard placement and template ids are the same in every process.

Step 3: reads. count(template) locks one shard. top(k) visits every shard, taking each lock briefly, and keeps a size-k heap. The result is not a single atomic snapshot (counts can move while it runs), which is fine for reporting; say so.

Numbers. 50k prompts/s, ~2 KB each: normalization runs ~5–10 regex passes over 2 KB, roughly 20–50 µs per prompt in Python, so one core handles ~20–50k/s: a few worker processes (regex work holds the GIL) feeding per-process indexes that are merged periodically. Memory: 10⁶ templates × (~500 B template + counters + 3 examples) ≈ 1–2 GB; cap stored examples and truncate long templates.

Code

import hashlib
import heapq
import re
import threading

_PATTERNS = [
    (re.compile(r'"(?:[^"\\]|\\.)*"'), "<STR>"),
    (re.compile(r"\bhttps?://\S+"), "<URL>"),
    (re.compile(r"\b[\w.+-]+@[\w-]+(?:\.[\w-]+)+\b"), "<EMAIL>"),
    (re.compile(r"\b[0-9a-fA-F]{8}-[0-9a-fA-F]{4}-[0-9a-fA-F]{4}-[0-9a-fA-F]{4}-[0-9a-fA-F]{12}\b"), "<UUID>"),
    (re.compile(r"(?<![\w.])\d+(?:\.\d+)?(?![\w.])"), "<NUM>"),
]
_SPACES = re.compile(r"\s+")


def template_of(prompt):
    text = prompt
    for pattern, placeholder in _PATTERNS:
        text = pattern.sub(placeholder, text)
    return _SPACES.sub(" ", text).strip()


def template_id(template):
    return hashlib.sha1(template.encode()).hexdigest()[:12]


class _Shard:
    __slots__ = ("lock", "counts", "examples")

    def __init__(self):
        self.lock = threading.Lock()
        self.counts = {}
        self.examples = {}


class TemplateIndex:
    def __init__(self, shards=64, examples_per_template=3):
        self.shards = [_Shard() for _ in range(shards)]
        self.keep = examples_per_template

    def _shard(self, tid):
        return self.shards[int(tid, 16) % len(self.shards)]

    def add(self, prompt):
        template = template_of(prompt)  # outside the lock: the expensive part
        tid = template_id(template)
        shard = self._shard(tid)
        with shard.lock:
            shard.counts[template] = shard.counts.get(template, 0) + 1
            kept = shard.examples.setdefault(template, [])
            if len(kept) < self.keep:
                kept.append(prompt)
        return tid

    def count(self, template):
        shard = self._shard(template_id(template))
        with shard.lock:
            return shard.counts.get(template, 0)

    def examples(self, template):
        shard = self._shard(template_id(template))
        with shard.lock:
            return list(shard.examples.get(template, []))

    def top(self, k):
        """[(template, count)], most frequent first, ties by template."""
        heap = []
        for shard in self.shards:
            with shard.lock:
                items = list(shard.counts.items())
            for template, c in items:
                entry = (c, _Desc(template))
                if len(heap) < k:
                    heapq.heappush(heap, entry)
                elif entry > heap[0]:
                    heapq.heapreplace(heap, entry)
        return [(d.s, c) for c, d in sorted(heap, reverse=True)]

    def total(self):
        return sum(sum(s.counts.values()) for s in self.shards)


class _Desc:
    """Orders strings in reverse, so a min-heap on (count, _Desc) keeps
    the higher count and, on ties, the alphabetically smaller template."""

    __slots__ = ("s",)

    def __init__(self, s):
        self.s = s

    def __lt__(self, other):
        return self.s > other.s

    def __eq__(self, other):
        return self.s == other.s

Normalization runs before taking the lock: the critical section is just a dict update, which is what keeps contention low.

Complexity

  • add: O(L) for normalization of a prompt of length L (a few regex passes), plus O(1) under one shard lock.
  • count, examples: O(L) to hash the template, O(1) lookup.
  • top(k): O(T log k) over T distinct templates; shard locks are held only while copying each shard's items.
  • Memory: O(T × template length) plus the kept examples.

Test cases

import threading

from solution import TemplateIndex, template_of


def test_normalization():
    assert template_of('Summarize ticket 48213 for alice@acme.com') == "Summarize ticket <NUM> for <EMAIL>"
    assert template_of('Fetch https://x.io/a?id=7 then say "hi 42"') == "Fetch <URL> then say <STR>"
    assert template_of("id 123e4567-e89b-12d3-a456-426614174000 costs 3.50") == "id <UUID> costs <NUM>"
    assert template_of("use gpt4 and v2   now") == "use gpt4 and v2 now"


def test_counts_examples_and_top():
    idx = TemplateIndex(shards=4)
    for i in range(5):
        idx.add(f"Summarize ticket {i} for u{i}@acme.com")
    for i in range(3):
        idx.add(f"Translate {i} lines")
    idx.add("hello")
    t = "Summarize ticket <NUM> for <EMAIL>"
    assert idx.count(t) == 5
    assert len(idx.examples(t)) == 3
    assert idx.top(2) == [(t, 5), ("Translate <NUM> lines", 3)]
    assert idx.top(10)[-1] == ("hello", 1)


def test_ties_break_alphabetically():
    idx = TemplateIndex(shards=8)
    for text in ["b", "a", "c"]:
        idx.add(text)
    assert idx.top(2) == [("a", 1), ("b", 1)]


def test_concurrent_adds_are_exact():
    idx = TemplateIndex(shards=16)
    threads, per = 8, 2500

    def work(n):
        for i in range(per):
            idx.add(f"Job {i} for team {n} in region {i % 7}")

    ts = [threading.Thread(target=work, args=(n,)) for n in range(threads)]
    for t in ts:
        t.start()
    for t in ts:
        t.join()
    assert idx.total() == threads * per
    assert idx.count("Job <NUM> for team <NUM> in region <NUM>") == threads * per

Follow-ups

  1. Better templates than regexes. Rules miss names and free text. Cluster prompts by token-level alignment (the log-parsing approach: group by length and leading tokens, then mark positions that vary as wildcards), or by embedding similarity with a threshold. Regexes stay as the cheap first pass.
  2. Approximate counts at huge scale. With 10⁸ distinct templates, exact dicts do not fit. Use a count-min sketch for counts and a heavy-hitters structure (space-saving) for the top k, with known error bounds.
  3. Many processes or machines. Each worker keeps a local index and ships (template_id, count) deltas every few seconds to an aggregator partitioned by template id; counts are additive, so merging is a sum.
  4. Hot templates. One template with 50% of traffic makes its shard hot. Keep per-thread local counters for the hottest keys and flush them periodically (striped counters), trading a little staleness for no contention.
  5. Privacy. Stored examples are customer prompts. Keep them only with consent, redact them with the same placeholders, and expire them.

Interviewer expectations

Mid-level (L4)

  • Normalizes variable spans with regexes and counts templates in a dict.
  • Makes ingestion thread-safe with a lock.
  • Returns the top k correctly with ties handled.

Senior (L5)

  • Orders the replacements to avoid partial matches and compiles patterns once.
  • Shards the map with a lock per shard and a stable hash, and keeps expensive work outside the lock.
  • Tests exact totals under concurrency and explains what top guarantees while writes continue.

Staff (L6+)

  • Sizes CPU and memory for real traffic and notes that regex work holds the GIL (processes, not threads, for throughput).
  • Proposes sketches for approximate counts, distributed aggregation by template id, and relief for hot keys.
  • Raises the privacy handling of stored examples and better template extraction beyond rules.

Sign in to comment, vote or remix.