Long-Context Retrieval and Prompt Assembly

What's being tested

Interviewers probe your ability to design a scalable, low-latency retrieval and prompt-assembly service that integrates many pieces: indexing, ranking, token accounting, caching, and operational tradeoffs. They want to see system-design instincts (sharding, replication, SLOs), algorithmic awareness (ANN vs exact search, multi-stage ranking), and pragmatic engineering decisions (batching, memoization, observability). The focus is on delivering correct, timely context to an LLM under real-world constraints (token limits, throughput, freshness).

Core knowledge

Token budget math — compute available tokens: $T_{avail}=T_{context\_limit}-T_{expected\_response}-T_{prompt\_overhead}$ ; enforce with conservative safety margin (e.g., 10%).
Chunking & overlap — split documents into chunks sized by tokens (e.g., 200–1000 tokens) with configurable overlap (10–30%) to preserve context across boundaries; too-large chunks reduce granularity, too-small increase retrieval noise.
Vector representation & storage — embeddings dimensionality (e.g., 768–2048) drives memory: float32 costs ~4 bytes × dim per vector; quantization (PQ, OPQ) reduces memory/IO at recall cost. Tools: FAISS, Annoy, HNSW.
ANN tradeoffs — Approximate Nearest Neighbor gives latency/throughput wins at recall cost; tune index parameters (ef, M for HNSW; nprobe for IVF) to balance p95 latency vs recall.
Multi-stage retrieval — use a two-stage pipeline: cheap coarse ANN to get top-K, then expensive reranker (text-similarity or cross-encoder) on CPU/GPU for top-R (R ≪ K) to improve precision while containing cost.
Sharding & replication — shard by document id or time window to scale memory/CPU; replicate shards for read SLOs and enable leader election for writes; consider consistent hashing to rebalance.
Caching & memoization — cache frequent queries and assembled prompts (Redis or in-memory LRU). Cache key = (query fingerprint, schema version, prompt template hash). Invalidate on document updates using versioned keys.
Latency SLOs & instrumentation — set p50/p95/p99 SLOs and measure each stage: embedding lookup, ANN query, rerank, tokenization, prompt assembly. Instrument with traces and per-component budget.
Batching & concurrency — vectorization benefits from batching embeddings/reranking but introduces latency tail; use adaptive batching with max-wait and size thresholds to meet p95 SLOs.
Tokenization and encoding effects — token counts depend on tokenizer (BPE/byte-level). Always measure tokenized size for chunk decisions and prompt assembly; do not approximate by character count.
Freshness & consistency — choose update model: near-real-time incremental indexing vs periodic rebuilds. Incremental updates require write-path indexing and background index-merge; note transient inconsistencies during merges.
Cost and IO profile — estimate RAM: vectors_count × dim × bytes; network IO for reranker results; GPU vs CPU cost for cross-encoders. Use quantized indices and caching to limit cloud spend.

Worked example — "Design a low-latency retrieval service that assembles a 50k-token context for LLM prompts"

First 30s: ask clarifying questions — required p95 latency (e.g., <300ms?), QPS, document corpus size, freshness window, expected response length, allowed cost. Declare assumptions: 10M documents, context limit 50k tokens, p95 500ms, near-real-time freshness (1–5m).

Skeleton of answer:

Ingestion & chunking: tokenize and chunk docs into ~1k-token chunks with 20% overlap; compute and store chunk metadata and embeddings in an index.
Index layer: use sharded HNSW/IVF+PQ indices for ANN; shard by doc-id ranges and replicate for reads.
Two-stage retrieval: ANN returns top-K (e.g., 200); cross-encoder reranks top-R (e.g., 20) on CPU/GPU; apply score thresholding.
Prompt assembly: tokenize selected chunks, apply token budget greedy selection (largest relevance-per-token first), enforce deduping and stable ordering; add template and safety placeholders.
Caching & batching: cache frequent query → assembled-prompt; batch embedding and rerank calls where latency allows.

One tradeoff to flag: pushing recall higher (bigger K, heavier reranker) improves quality but increases p95 latency and cost — tune to SLOs, possibly degrade gracefully (serve cached prompts under load). Close: "if time, add telemetry dashboards, A/B experiments on chunk size, and a background index compaction job."

A second angle — "Implement deterministic prompt assembly under high concurrency and document updates"

This variant emphasizes determinism and idempotency. Key changes: use versioned document IDs and a prompt-template hash in cache keys so identical inputs always yield identical prompts. Ensure stable ordering by sorting selected chunks by (document_version, chunk_offset) rather than dynamic scores alone; record selection signatures (checksums) to detect nondeterministic regressions. For concurrency, make index updates append-only with background compaction to avoid in-place mutability; use optimistic concurrency and publish index-version metadata so retrievals use a consistent snapshot. Here you trade some freshness and extra storage for deterministic behavior and easier debugging.

Common pitfalls

Pitfall: Ignoring tokenization mismatches — many engineers estimate tokens by characters; this causes silent prompt truncation or OOMs. Always measure tokenized tokens with the exact tokenizer used by the LLM.

Pitfall: Designing without SLOs or workload numbers — proposing heavy rerankers or huge K without throughput/latency constraints makes the design infeasible. Ask SLOs and target them explicitly.

Pitfall: Focusing only on embedding quality — embedding improvements matter, but production problems often come from missing caches, poor sharding, or no observability; prioritize operational robustness before micro-optimizing retrieval models.

Connections

This topic often leads to adjacent areas: distributed caching & consistency (cache invalidation strategies), index maintenance & compaction (background merges, offline rebuilds), and observability & SLO engineering (tracing, dashboards for p99 latency and recall metrics).