Real Time and Online Learning Systems Questions

Designing machine learning systems that learn, adapt, and act in real time on streaming data. Topics include online learning algorithms (online gradient descent, incremental learners, contextual bandits), handling concept drift, model freshness versus computational cost trade offs, low latency model updates and serving, streaming feature engineering and feature stores, feedback loops, evaluation strategies for online learners, exploration versus exploitation, data labeling and delayed feedback, reliability and monitoring of models in production, and integration with streaming processing frameworks for both inference and continuous training.

MediumTechnical

74 practiced

Implement incremental k-means (online Lloyd-style update) in Python for streaming data with a fixed number k and learning rate alpha. Provide a function that, given current centroids and a new example, updates the nearest centroid in O(k*d) time and explain initialization and corner cases.

Sample Answer

To implement online (incremental) k-means using a Lloyd-style update, we keep k centroids and for each incoming example x we find the nearest centroid (O(k*d)) and move it a small step toward x with learning rate alpha: c := c + alpha * (x - c). Initialization can use kmeans++, random sampling, or the first k points in the stream. Handle corner cases: empty centroids, invalid alpha, NaNs, and very large alpha.

python

import numpy as np

def online_kmeans_update(centroids, x, alpha):
    """
    centroids: np.ndarray shape (k, d)
    x: np.ndarray shape (d,)
    alpha: float in (0,1] - learning rate
    Returns: updated centroids (in-place modification allowed)
    Time: O(k*d)
    """
    if centroids is None or len(centroids) == 0:
        raise ValueError("centroids must be an array with shape (k,d) and k>0")
    x = np.asarray(x)
    if x.ndim != 1 or x.shape[0] != centroids.shape[1]:
        raise ValueError("x must be 1D and match centroid dimensionality")
    if not (0.0 < alpha <= 1.0):
        raise ValueError("alpha must be in (0,1]")

    # compute squared distances to avoid sqrt
    diffs = centroids - x  # shape (k,d)
    dists_sq = np.einsum('ij,ij->i', diffs, diffs)  # fast rowwise dot
    idx = int(np.argmin(dists_sq))  # nearest centroid index

    # update rule: move centroid toward x
    centroids[idx] += alpha * (x - centroids[idx])
    return centroids

Key points:- Complexity: O(k*d) per example (distance computation + update).- Initialization: kmeans++ for better starting positions; alternatively sample first k distinct points from stream.- Corner cases: if stream yields duplicates, centroids may collapse—use small alpha or add regularization; if centroids empty raise error; guard against NaNs and ensure consistent dtype.- Extensions: use adaptive alpha (e.g., alpha = 1 / (1 + n_assigned_to_centroid)) for convergence, maintain counts per centroid to implement that.

HardTechnical

54 practiced

Propose an architecture for federated online learning with streaming updates from edge devices: include communication-efficient protocols, secure aggregation, local personalization, client drift handling, compression/quantization of model deltas, and strategies for partial participation and stragglers.

Sample Answer

Requirements:- Online federated learning with streaming updates from many edge devices (mobile/IoT), strong communication efficiency, privacy (secure aggregation), support local personalization, robust to client drift, compression of model deltas, and partial participation/stragglers handling. Low-latency for continuous model improvement.

High-level architecture:Edge clients ⇄ Federated Orchestration Layer ⇄ Aggregation & Model Store ⇄ Evaluation / Personalization Service

Key components & responsibilities:1. Edge client:- Maintain local model copy + personalization head.- Continuously collect data; compute lightweight streaming updates (micro-batches or event-triggered gradients).- Compress/quantize model deltas (see below), sign/encrypt for secure aggregation; attach metadata: timestamp, data distribution summary, local validation metrics.- Apply local adaptation (e.g., fine-tune personalization head with small LR, or use meta-learning like Per-FedAvg / MAML).

2. Federated Orchestration Layer (server-side scheduler):- Manages rounds or streaming windows, selects clients via participation policy (stratified sampling to reduce bias), tracks staleness.- Handles incentives, bandwidth-aware selection, and fallback for stragglers.

3. Secure Aggregation & Compression Service:- Perform cryptographic secure aggregation (e.g., Bonawitz et al.) on compressed deltas; support ephemeral key exchange, thresholding to tolerate dropouts.- Decompress aggregated deltas; update global model.

4. Personalization Service:- Maintain global backbone; serve aggregated global weights to clients; optionally compute cluster-specific models using client metadata.

Communication-efficient protocols:- Event-driven micro-updates batched into server windows (e.g., 1–10 min).- Delta compression: top-k sparsification + error feedback, and quantization (e.g., 8-bit or QSGD) before encryption.- Use sketching (CountSketch) for very large models, or marginal updates for embeddings.- Bandwidth-aware adaptive schemes: higher compression for low-bandwidth clients.

Secure aggregation:- Use threshold secure aggregation (Bonawitz) compatible with compressed tensors; perform compression before masking to reduce cost, or apply homomorphic-friendly quantization.- Include differential privacy at the server: add calibrated noise post-aggregation or use client-side DP when necessary.

Local personalization & client drift:- Hybrid model: shared global backbone (frozen or slowly updated) + local personalization head; use federated multi-task learning or fine-tuning with proximal term (FedProx) to limit drift.- Drift detection: clients send small distribution sketches (e.g., histogram or top-k features); server clusters clients and maintains per-cluster models; trigger targeted fine-tuning or model splitting when drift exceeds threshold.

Handling partial participation & stragglers:- Staleness-aware aggregation: weight updates by recency and client reliability, with bounded staleness decay.- Asynchronous aggregation with bounded delay windows (semi-synchronous): accept updates within window; late updates get applied to next epoch with compensation.- Graceful degradation: require only a quorum; secure aggregation protocol tolerant to dropouts; maintain per-client state for incremental updates and re-synchronization.

Compression/quantization specifics:- Pipeline: compute delta -> sparsify top-k (retain momentum/error-feedback) -> quantize (e.g., 8-bit stochastic) -> entropy coding (if needed) -> encrypt/mask.- Use error-feedback on client to preserve unbiasedness.- Analyze trade-offs between compression ratio and utility; adapt k/bitrate based on local validation.

Monitoring, metrics & ops:- Track model convergence, per-client loss, fairness metrics, communication stats.- Automated rollback and canary testing with small client cohorts before global rollout.- Logging and secure telemetry with privacy-preserving summaries.

Trade-offs:- Strong compression + encryption reduces bandwidth but complicates secure aggregation (requires compatible quantization).- Personalization reduces global accuracy per-client but improves user experience; cluster models balance both.- Asynchronous updates increase timely learning but complicate convergence guarantees; bounded staleness and learning rate schedules mitigate this.

This design balances privacy, bandwidth, personalization, and robustness for production federated online learning on edge devices.

HardTechnical

78 practiced

Scenario: you must migrate a stateful streaming online-learning service from Apache Flink to a managed cloud streaming service with different state and checkpoint semantics. Outline a migration plan covering state export/import, compatibility testing, online verification with shadow traffic, schema evolution, and rollback strategy.

Sample Answer

Situation: We need to move a stateful, online-learning streaming service from Apache Flink (custom state + savepoints) to a managed cloud streaming product whose checkpointing, state backend, and serialization semantics differ.

Plan (high-level phases):

1. Discover & design- Inventory Flink jobs: state types (keyed/operator), size, backend (RocksDB/in-memory), serializers (Kryo/Avro/Protobuf), checkpoint frequency, exactly-once guarantees, and external sinks.- Define target semantics: managed service’s state model (e.g., key-value vs. keyed operator state), checkpoint guarantees, retention, restore APIs, and supported serializers.

2. Export / transform state- Create tooling to create Flink savepoints (stable) and export state blobs per-key. Use Flink Savepoint API to read keyed/operator state.- Build a converter: - Map Flink state structures → target state model (e.g., flatten operator state into per-key stores). - Re-serialize using a portable schema (Avro/Protobuf/JSON) and include metadata (schema version, key hash, watermark). - For RocksDB SSTs too large, stream-key export in batches with consistent snapshots.- Store converted state in an intermediate durable storage (S3/GCS) organized by target restore partitions.

3. Compatibility testing (offline)- Stand up a small cluster of the managed service in test mode that can ingest converted state.- Unit-level: deserialize a sample of saved keys, compare values and invariants with original Flink job outputs.- Integration: replay historical Kafka topics into both Flink (replay from checkpoint) and target service (restore converted state) and assert deterministic divergence bounds on model parameters, feature stores, and output events.- Property checks: idempotency, monotonic counters, timestamp/watermark alignment.

4. Online verification with shadow traffic- Run the managed service in parallel to Flink receiving the same live input (shadow/canary mode) but initially not publishing to production sinks.- Compare outputs per key in real-time: response latency, predicted labels/scores, internal model parameters (sampled keys).- Use a divergence detector with thresholds (e.g., >0.1% label diff or >5% probability drift triggers investigation).- Gradually increase proportion of traffic validated (A/B canary), then route non-critical traffic to managed service for end-to-end pathway testing (including sinks) behind feature flags.

5. Schema evolution & backward compatibility- Adopt explicit versioned schemas (Avro/Protobuf) for state and events. Include schema registry.- Implement migration paths: compatibility checks (backward/forward) and conversion scripts for incremental upgrades.- When changing model state structure, create adapters that read older schema versions and transform at restore time lazily (on first access) to spread cost.

6. Rollback strategy- Preserve Flink savepoints and full snapshots; retain the original cluster until cutover stability.- Use traffic steering: canary → 25% → 50% → 100%; at each step, maintain dual-run for 24–72h before progressing.- Automatic rollback triggers: - Divergence thresholds exceeded - SLA breaches (latency/error rate) - Data loss indicators (missing keys)- Rollback actions: - Stop routing new traffic to managed service - Restore Flink from saved savepoint (or resume original pipeline) - If partial state was written to downstream sinks, run compensating jobs to reconcile (idempotent writes, tombstones).- Postmortem and state reconciliation: capture failing keys, generate focused re-import or repair jobs.

Verification & observability- Metrics: output divergence, per-key state checksum, end-to-end latency, error rates, consumer lag, model accuracy on labeled sampled traffic.- Logging: maintain per-key trace for sampling, distributed tracing for flows.- Tests: chaos testing (failover), snapshot/restore tests, end-to-end correctness test suite.

Risks & mitigations- Large state transfer time: use parallel export/import, chunking, and lazy on-demand migration.- Semantic mismatch (exactly-once → at-least-once): design idempotent sinks and de-duplication, or use dedup windows.- Serialization incompatibilities: rely on schema registry and adapters.

Result: phased, measurable migration with preserved ability to rollback, explicit schema/versioning, and confidence through offline and shadow testing before full cutover.

HardTechnical

77 practiced

Explain how to combine online learning with large pre-trained language models (LLMs) to personalize behavior without catastrophic forgetting. Discuss parameter-efficient approaches (LoRA, adapters), memory-based retrieval augmentation, episodic memory, and safety/privacy controls for personalization data.

Sample Answer

Start with the goal: adapt a large pre-trained LLM to user-specific behavior online while avoiding catastrophic forgetting of base capabilities and preserving privacy.

Approach overview- Keep the base LLM frozen and apply parameter-efficient updates for personalization (reduces risk of forgetting and compute cost).- Combine small, continual updates (online) with retrieval-augmented context and an episodic memory/replay buffer to preserve prior knowledge.- Enforce safety/privacy by design: local storage, encryption, DP/Federated schemes, consent and auditing.

Parameter-efficient personalization- LoRA: inject low-rank delta matrices into attention/FFN weights and learn only those small matrices online. Benefits: tiny parameter footprint, easy rollback, and lower interference with base weights.- Adapters: add small bottleneck modules between layers; learn per-user adapter layers or per-user prefixes. Benefits: modularity, selective activation, and ability to mix-and-match adapters (compose base + user).- Practical pattern: initialize user-specific LoRA/adapters, train online with conservative learning rates and gradient clipping; checkpoint and version updates.

Avoiding catastrophic forgetting- Replay/Episodic memory: maintain a curated buffer of representative global and user interactions. During online updates, interleave rehearsal from this buffer (experience replay) to preserve global behaviors.- Regularization-based methods: use importance-weighted penalties (EWC or fisher-based) on adapter/LoRA updates to prevent overwriting parameters critical to base tasks.- Constrained optimization: use trust-region updates or small-step optimizers (e.g., Adam with low LR) and early stopping based on validation tasks.- Periodic consolidation: occasionally distill personalized adapters into a consolidated model while testing on held-out global tasks.

Memory-based retrieval augmentation- Store user facts/long-term preferences as embeddings in a vector DB; at inference, retrieve relevant memories and prepend or fuse them into LLM context (RAG-style). This keeps personalization out of model weights and is reversible.- Use hybrid retrieval: short-term context (session) + long-term episodic memory (vector index). Apply reranking and filtering to avoid hallucination and stale info.- Consistency checks: use verifiers or constrained decoding when retrieved facts are critical.

Safety and privacy controls- Data minimization & consent: explicitly request consent, allow opt-out, and limit what is stored (hashed identifiers, filtered sensitive entities).- Local/on-device personalization: perform adapter/LoRA updates or store memories on-device; only share aggregated, anonymized updates if needed.- Differential privacy: add DP-SGD to online training to bound leak risk; combine with secure aggregation in federated setups.- Access controls & encryption: encrypt vector DB and checkpoints at rest; use key management and strict RBAC for servers.- Auditability & rollback: log update provenance, provide user-visible summaries of personalized data, enable adapter rollback or delete (forget) operations.- Safety layers: content filters, guardrails, and safety classifiers on outputs; avoid over-personalizing for risky topics.

Example deployment pattern- Frozen base LLM hosted securely. User-specific LoRA/adapters stored per-user (locally or encrypted server-side).- Online loop: collect interaction → sanitize & extract preferences → update adapter with small steps + rehearsal (sample from global buffer) → update user memory index.- Inference: retrieve relevant memories → condition LLM with user adapter active → post-filter output through safety checks.

Trade-offs- Weight updates (LoRA/adapters) give fast, compact personalization but require careful regularization and replay to avoid drift.- Retrieval-based personalization is safer/reversible but may increase latency and requires secure vector stores.- Federated + DP reduces central risk but increases engineering complexity and reduces utility.

This hybrid—LoRA/adapters + episodic replay + RAG + strong privacy controls—provides efficient, reversible personalization with mitigations for forgetting and privacy risk.

HardSystem Design

116 practiced

Design a GPU-based online training architecture to support frequent small updates for many tiny models with low latency. Discuss batching of updates, model multiplexing on GPUs, cold/warm model placement, GPU kernel fusion opportunities, and strategies to maximize GPU utilization without violating latency SLAs.

Sample Answer

Requirements & constraints:- Serve frequent small online updates (per-model few-10s of examples) for many tiny models (KB–MB parameters) with strict low-latency SLAs for both update acknowledgement and subsequent inference.- Maximize GPU utilization without breaking latency SLOs; multi-tenant, elastic scale.

High-level architecture:- Ingress -> Frontend API -> Update Router/Policy -> Multiplexing Scheduler -> GPU Workers (model cache + trainer kernels) -> Persistent Parameter Store (CPU DRAM / NVMe) + Asynchronous Checkpointer -> Metrics & Autoscaler.

Key components & responsibilities:1. Update Router / Policy- Classify updates by model id, priority, SLA, and staleness tolerance.- Buffer micro-updates into per-model queues; expose admission control to ensure SLO.

2. Multiplexing Scheduler- Aggregate compatible small updates into dynamic batches (across models) using batching windows and priority. Batches respect per-update latency SLO (deadline-aware batching).- Pack many tiny models into a single GPU “packing” tensor (model multiplexing): allocate contiguous slots for model parameters to enable vectorized ops.

3. GPU Worker (on-GPU model cache + training)- Maintain warm model cache in GPU memory for hot models; store cold models compressed/quantized in DRAM/NVMe.- Use CUDA streams with prioritized execution; run multiple independent model updates concurrently via stream parallelism and cooperative kernels.- Use fused kernels and CUDA Graphs for recurring micro-update patterns (forward + backward + optimizer step) to reduce kernel launch overhead.- Support mixed-precision and quantized storage for parameter packing to increase throughput.- Apply micro-batching: accumulate gradients over tiny sub-batches (e.g., 1–8 examples) then apply a single optimizer step; for per-model strict consistency, use synchronous apply; otherwise allow asynchronous apply with staleness bounds.

Data flow & placement:- Cold/warm placement: maintain LRU / LFU + cost model (update frequency, inference rate, model size). Hot models pinned to GPU; semi-warm reside in host DRAM with prefetchers; cold on NVMe and fetched on demand with priority prefetching based on predicted next access.- Prefetch pipeline: when router detects incoming updates / inference for a cold model, schedule asynchronous transfer to GPU and possibly serve inference from CPU with lower throughput if SLO allows.- Checkpointing: periodic batched writebacks to persistent store to avoid write amplification.

Batching strategies:- Cross-model dynamic batching: merge updates for different models into a single GPU kernel when same operator shapes and optimizer used. Use meta-data to indicate per-slot parameter offsets.- Deadline-aware micro-batching: small time window (e.g., 5–20 ms) to accumulate updates but bound by SLO; use admission control to bypass batching for high-priority low-latency updates.- Gradient accumulation for extremely small updates reduces kernel overhead; use per-model accumulation counters.

Model multiplexing on GPUs:- Parameter packing: pack many tiny models into a larger tensor with an index mapping layer; kernels are written to operate on packed layout (strided accesses).- Use block-sparse or grouped-gemm techniques if model sizes vary; maintain padding minimalization.- For inference + update co-location: store both model weights and optimizer state in packed arrays to avoid cross-memory transfers.

GPU kernel fusion opportunities:- Fuse forward, backward, and optimizer steps into single kernel per update pattern to eliminate multiple kernel launches and intermediate writes.- Use CUDA Graphs for repeated micro-update DAGs; replay graphs with different parameter offsets to amortize overhead.- Fuse cross-model elementwise ops when packing is used.- For small GEMMs, use batched GEMM or custom fused kernels leveraging tensor cores for throughput.

Maximizing utilization without violating latency SLAs:- Priority-aware scheduler: prioritize requests nearing deadline; give them immediate dispatch or smaller micro-batches.- Admission control & SLO-aware batching window: dynamically shrink batch windows under load to respect latency SLOs.- Work stealing across GPUs to balance hot-cold skew.- Mixed execution modes: dedicate a fraction of GPU streams/SMs to latency-critical tasks (preemptible) and run throughput tasks on remaining resources.- Use model-aware packing to increase arithmetic intensity; prefer mixed-precision to increase compute per byte.- Autoscale worker count and GPU memory pool based on observed hot-model working set and queue latency.- Continuous profiling: track kernel latencies, memory transfer times, batch formation delays; use these to update batching window, cache thresholds, and placement policy.

Trade-offs & alternatives:- Strong consistency per-update (sync optimizer) increases latency; allow bounded staleness (ASGD) for throughput-sensitive models.- Packing reduces per-model isolation and complicates preemption—mitigate with fine-grained mapping and per-slot locks.- Kernel fusion reduces flexibility; keep a library of fused kernels for common optimizer/model primitives and fall back to modular kernels for rare cases.

Metrics & monitoring:- Per-model update latency, inference latency, update-to-serve freshness, GPU occupancy, memory hit rate (GPU/DRAM), kernel launch overhead.- Use these for autoscaling and adaptive batching.

Example numbers (toy):- Each tiny model: 200 KB weights → pack 5k models per 1GB GPU segment.- Batching window 10 ms yields average batch size 50 updates → fused kernel amortizes launch overhead reducing per-update latency by 5–10x.- Warm cache hit target >95% for hot models to keep SLA.

Closing note:- The design balances SLOs and utilization by making batching and placement latency-aware, using packing and fused kernels to amortize overhead, and employing admission-control + prioritized scheduling to protect low-latency requests. Continuous profiling and autoscaling complete the operational control loop.

Unlock Full Question Bank

Get access to hundreds of Real Time and Online Learning Systems interview questions and detailed answers.

Join thousands of developers preparing for their dream job.