Design real-time ETA prediction

Question: Design real-time ETA prediction

Companies: Uber

Difficulty: Medium

Problem statement

Predict when a driver will arrive at pickup and drop-off, updated every few seconds during the trip, accurate to within a minute or two.

Problem framing

Business goal. Riders decide whether to request, wait or cancel based on the ETA. Dispatch, pricing and
driver earnings estimates also consume it. A wrong ETA costs money twice: a rider who waits 4 minutes longer
than shown cancels or churns, and a matcher fed biased ETAs assigns the wrong driver.

ML task. For an active trip at time t, predict the remaining seconds until (a) the driver reaches the
pickup point and (b) the trip ends at drop-off. Re-predict every ~5 s while the trip is live, plus one-off
predictions for quotes and dispatch candidate pairs before a trip exists.

Framing choice. Do not learn travel time from scratch. A routing engine already computes a physical ETA
(shortest path on a road graph weighted by segment travel times). The model predicts the residual
actual − routing_ETA and corrects for what the graph misses: pickup friction, turn and light delays, traffic
not yet in segment speeds, driver behavior, airport loops.

Scale and constraints (assumed).

• ~30M trips/day, ~25 min average from accept to drop-off → ~520k concurrent trips on average, ~1M at peak.
• In-trip refresh every 5 s → ~200k QPS at peak. Quotes and dispatch candidates add ~300k QPS (several
  driver candidates per request). Plan for ~500k QPS model inference.
• p99 latency for the full ETA call ≤ 100 ms; the ML part ≤ 10 ms, so it runs on CPU with a small model.
• Accuracy target from the prompt: for short horizons (<15 min) most predictions within ±1–2 min.

ML objective vs business metric. The model minimizes an asymmetric Huber loss on seconds of error.
The business cares about rider cancellations, request conversion, on-time pickups and matching efficiency.
They connect through bias as much as through MAE: a model that is 30 s optimistic on average with good MAE
still drives cancellations. So offline evaluation tracks signed error per segment, not only MAE.

Data and labels

Sources. Driver GPS pings (every 1–4 s, map-matched to road segments); trip events (request, accept,
arrived-at-pickup, trip start, trip end); routing engine outputs logged at prediction time; real-time segment
speeds from aggregated probes; map attributes; weather; venue and event calendars.

Labels.

• Pickup: t_arrive_pickup − t_prediction. "Arrived" is a driver tap, which is noisy: drivers tap early
  to start the wait timer, or late. Clean it with GPS: arrival = first ping within ~50 m of pickup with speed
  < 2 m/s; drop trips where tap and geofence disagree by > 90 s.
• Drop-off: t_trip_end − t_prediction, again cross-checked with GPS stop at the destination.
• Pickups that never happen (cancellations) have no label. They are censored, not negatives. Exclude them,
  but monitor whether cancellations skew to long ETAs, because that biases the training set toward easy trips.

Label delay. Minutes to ~1 hour; fine for daily retraining and 15-min bias monitoring.

Sampling. A 25-min trip at 5 s refresh yields 300 snapshots, all highly correlated. Sample one snapshot
every ~30 s per trip (~50/trip → ~1.5B rows/day), then keep ~10% → ~150M rows/day. Weight so that long trips
do not dominate and so each horizon bucket (0–2, 2–5, 5–15, 15–45, 45+ min) is represented.

Distribution. No class imbalance (regression), but the target is heavy-tailed: airports, ferries,
gridlock, wrong turns. Clip labels at e.g. 3× routing ETA + 10 min and drop GPS-broken trips (jumps > 200 m/s).

Leakage traps.

• Segment speeds aggregated over a window that ends after t_prediction (e.g. hourly averages computed
  for the hour the trip is in). Rebuild features as-of the prediction timestamp from logged values.
• Using the route actually driven instead of the route planned at time t.
• Trip-level aggregates (total distance, average speed) that include the future.
• Driver speed-ratio history that includes the trip being predicted.
  The fix is the same for all: log features at serving time and train on the logs, not on recomputed joins.

Splits. Time-based: train on 8 weeks, validate on the following week, test on the week after. Add
holdout cities to check transfer to new markets, and report holiday weeks separately.

Features

• The error memory feature is the strongest fix for unexpected events (a closure the map does not know
  about). It is built from trips that already finished in the last 15 min, so it only uses past labels.
• A feature store (offline Hive/Parquet tables + online key-value store fed by the same Flink jobs) gives
  point-in-time correct training joins and keeps train/serve definitions identical.

Model

Baseline 0. Routing engine ETA alone; its error is biased by city and hour. This is the bar.

Baseline 1. Gradient-boosted trees (~500 trees, depth 8) on the residual with the tabular features above.
Cheap; often cuts MAE 15–25% over routing alone. Weakness: high-cardinality spatial features
(millions of H3 cells) need hashing or target encoding, which leaks if done carelessly.

Production. A compact deep model on the residual:

• Continuous features bucketized (quantile bins) and embedded; categorical and H3 cells embedded with hashing;
  each feature becomes a token.
• A few layers of linear-time self-attention (or a wide MLP) over ~50–100 tokens, then a small MLP.
• Multi-task heads: pickup vs drop-off residual, and quantiles p10/p50/p90 for an ETA range.
• Bias-adjust layer: per-city/per-product learned offsets so a single global model serves all markets.
• Output: ETA = routing_ETA + predicted_residual, floored at a minimum (e.g. 30 s if not yet arrived).
• Size ~1–3M parameters, ~1 ms on CPU per request batch; no GPU needed at 500k QPS (a few hundred cores).

Losses.

• Point head: asymmetric Huber on seconds. Under-predicting (ETA shows 3 min, driver takes 5) is penalized
  more than over-predicting: weight ~1.5–2× on late errors, δ ≈ 60 s so outliers do not dominate.
• Quantile heads: pinball loss at 0.1/0.5/0.9.
• Weight samples by horizon so short-horizon accuracy (the part riders watch) is not drowned by long trips.

Temporal consistency. Raw predictions every 5 s jitter. Post-process the displayed ETA: it should count
down roughly 1 s per second; blend new prediction with previous − elapsed (exponential smoothing,
α ≈ 0.3), but snap immediately when the route changes or the gap exceeds 90 s. Show minutes, rounded up.

Evaluation

Offline (on the test week, per horizon bucket, city, phase).

• MAE and p90 absolute error in seconds; MAPE for long trips only (MAPE explodes near 0).
• Share within ±60 s and ±120 s for horizons < 15 min (the prompt's accuracy target).
• Mean signed error (bias), target |bias| < 15 s per city-hour bucket; a biased segment is a bug even if
  overall MAE improves.
• Quantile calibration: the p10–p90 interval should cover ~80% of outcomes; check per bucket.
• Stability: mean absolute change in displayed ETA between consecutive updates, beyond the expected countdown.

Online A/B. Randomize by rider (display) and by city-time slice when ETA feeds dispatch, since dispatch
effects cross riders (one rider's assignment changes another's driver).

• Primary: actual-vs-shown ETA error on live trips; rider cancellation rate after request.
• Secondary: quote-screen conversion. Guardrails: p99 latency, dispatch metrics (average pickup time, driver utilization), surge price changes,
  driver cancellations, support tickets about ETA.

Serving and monitoring

The online path, from request to smoothed ETA:

{"type":"excalidraw","elements":[
 {"type":"rectangle","id":"app","x":0,"y":0,"width":180,"height":90,"label":{"text":"Rider/driver\napp"}},
 {"type":"rectangle","id":"gw","x":300,"y":0,"width":180,"height":90,"label":{"text":"ETA gateway"}},
 {"type":"rectangle","id":"route","x":600,"y":0,"width":200,"height":90,"label":{"text":"Routing engine\n(graph + live\nspeeds)"}},
 {"type":"rectangle","id":"model","x":920,"y":0,"width":200,"height":90,"label":{"text":"Residual model\n(CPU)"}},
 {"type":"rectangle","id":"smooth","x":1240,"y":0,"width":180,"height":90,"label":{"text":"Smoother +\nbias offsets"}},
 {"type":"ellipse","id":"os","x":920,"y":240,"width":220,"height":90,"label":{"text":"Online feature\nstore"}},
 {"type":"rectangle","id":"gps","x":0,"y":440,"width":180,"height":70,"label":{"text":"GPS pings"}},
 {"type":"rectangle","id":"mm","x":300,"y":440,"width":180,"height":70,"label":{"text":"Map matcher"}},
 {"type":"rectangle","id":"ts","x":600,"y":440,"width":200,"height":70,"label":{"text":"Traffic stream\n(Flink)"}},
 {"type":"arrow","id":"app-gw","x":180,"y":45,"width":120,"height":0,"start":{"id":"app"},"end":{"id":"gw"}},
 {"type":"arrow","id":"gw-route","x":480,"y":45,"width":120,"height":0,"start":{"id":"gw"},"end":{"id":"route"}},
 {"type":"arrow","id":"route-model","x":800,"y":45,"width":120,"height":0,"start":{"id":"route"},"end":{"id":"model"}},
 {"type":"arrow","id":"model-smooth","x":1120,"y":45,"width":120,"height":0,"start":{"id":"model"},"end":{"id":"smooth"}},
 {"type":"arrow","id":"smooth-app","x":1330,"y":0,"width":-1240,"height":0,"points":[[0,0],[0,-60],[-1240,-60],[-1240,0]],"start":{"id":"smooth"},"end":{"id":"app"}},
 {"type":"arrow","id":"gw-os","x":390,"y":90,"width":530,"height":195,"points":[[0,0],[0,195],[530,195]],"start":{"id":"gw"},"end":{"id":"os"}},
 {"type":"arrow","id":"os-model","x":1030,"y":240,"width":1,"height":-150,"start":{"id":"os"},"end":{"id":"model"}},
 {"type":"arrow","id":"gps-mm","x":180,"y":475,"width":120,"height":0,"start":{"id":"gps"},"end":{"id":"mm"}},
 {"type":"arrow","id":"mm-ts","x":480,"y":475,"width":120,"height":0,"start":{"id":"mm"},"end":{"id":"ts"}},
 {"type":"arrow","id":"ts-os","x":800,"y":455,"width":160,"height":-135,"start":{"id":"ts"},"end":{"id":"os"}}
]}

The logging, labeling and training loop behind it:

{"type":"excalidraw","elements":[
 {"type":"rectangle","id":"model","x":0,"y":0,"width":200,"height":70,"label":{"text":"Residual model\n(CPU)"}},
 {"type":"rectangle","id":"smooth","x":320,"y":0,"width":180,"height":70,"label":{"text":"Smoother +\nbias offsets"}},
 {"type":"ellipse","id":"plog","x":620,"y":-5,"width":200,"height":80,"label":{"text":"Prediction log"}},
 {"type":"rectangle","id":"join","x":940,"y":0,"width":200,"height":70,"label":{"text":"Point-in-time\njoin"}},
 {"type":"rectangle","id":"train","x":1260,"y":0,"width":180,"height":70,"label":{"text":"Daily training"}},
 {"type":"rectangle","id":"val","x":1260,"y":-200,"width":180,"height":70,"label":{"text":"Offline eval\n+ shadow"}},
 {"type":"rectangle","id":"trips","x":620,"y":200,"width":200,"height":70,"label":{"text":"Trip events"}},
 {"type":"rectangle","id":"lb","x":940,"y":200,"width":200,"height":70,"label":{"text":"Label builder\n(GPS-cleaned)"}},
 {"type":"rectangle","id":"em","x":940,"y":400,"width":200,"height":70,"label":{"text":"15-min residual\naggregator"}},
 {"type":"ellipse","id":"os","x":1260,"y":395,"width":220,"height":80,"label":{"text":"Online feature\nstore"}},
 {"type":"arrow","id":"model-smooth","x":200,"y":35,"width":120,"height":0,"start":{"id":"model"},"end":{"id":"smooth"}},
 {"type":"arrow","id":"smooth-plog","x":500,"y":35,"width":120,"height":0,"start":{"id":"smooth"},"end":{"id":"plog"}},
 {"type":"arrow","id":"plog-join","x":820,"y":35,"width":120,"height":0,"start":{"id":"plog"},"end":{"id":"join"}},
 {"type":"arrow","id":"join-train","x":1140,"y":35,"width":120,"height":0,"start":{"id":"join"},"end":{"id":"train"}},
 {"type":"arrow","id":"train-val","x":1350,"y":0,"width":1,"height":-130,"start":{"id":"train"},"end":{"id":"val"}},
 {"type":"arrow","id":"val-model","x":1260,"y":-165,"width":-1160,"height":165,"points":[[0,0],[-1160,0],[-1160,165]],"start":{"id":"val"},"end":{"id":"model"},"label":{"text":"canary then rollout"}},
 {"type":"arrow","id":"trips-lb","x":820,"y":235,"width":120,"height":0,"start":{"id":"trips"},"end":{"id":"lb"}},
 {"type":"arrow","id":"lb-join","x":1040,"y":200,"width":1,"height":-130,"start":{"id":"lb"},"end":{"id":"join"}},
 {"type":"arrow","id":"lb-em","x":1040,"y":270,"width":1,"height":130,"start":{"id":"lb"},"end":{"id":"em"}},
 {"type":"arrow","id":"em-os","x":1140,"y":435,"width":120,"height":0,"start":{"id":"em"},"end":{"id":"os"}}
]}

Latency budget (p99, 100 ms). Gateway 5 ms; routing + map match 40–60 ms (the bulk; cache routes for
in-trip refreshes and only re-route on deviation); feature fetch 5–10 ms (batched multi-get); model 2–5 ms;
smoothing and logging 2 ms. In-trip refreshes reuse the route, so most calls take ~20 ms.

Fallback. On model or feature-store timeout, return routing ETA plus a per-city static offset.

Monitoring.

• Live accuracy: labels arrive within minutes, so compute MAE and bias per city every 15 min. Alert when
  bias exceeds 30 s for 30 min (map change, closures, a bad traffic feed).
• Feature drift: null rate and distribution (PSI) of traffic speeds and GPS ping intervals; a broken probe
  feed looks like free-flow traffic and makes ETAs optimistic.

Feedback loops. ETA drives matching: drivers chosen because of short predicted ETAs are the training
data, so the model sees few "far" driver-rider pairs. Keep a small exploration slice in dispatch logging and
weight by propensity. Displayed ETA also changes behavior (riders walk out on time, drivers rush), so measure
model changes online, not only offline.

Retraining. Daily retrain on a sliding 8-week window, warm-started; gated by offline eval (no city
worsens MAE > 2% or bias > 10 s), then shadow for 24 h, canary 5% of cities, then full. Faster adaptation
(hours) comes from the error-memory feature and bias offsets, not from retraining.

Trade-offs

• Residual on routing vs end-to-end model: keeps physics and map updates for free and stays robust on
  unseen routes, but inherits routing engine errors and couples releases of two systems.
• Small CPU model vs larger GPU model: meets 500k QPS and 10 ms cheaply; gives up some accuracy on
  complex urban pickups.
• Asymmetric loss: fewer "driver is late" surprises; ETAs are slightly pessimistic, which can lower
  quote conversion.
• Smoothing: stable countdown that riders trust; reacts 10–20 s slower to real changes.
• Daily retrain + streaming bias features: cheap and stable; a structural shift (new bridge, policy)
  takes a day to be learned fully.
• Excluding cancelled pickups: clean labels; the model under-represents the worst cases, so watch bias
  on long-ETA requests.

Interviewer expectations

Mid-level (L4)

• Defines the target as remaining seconds at prediction time, for pickup and drop-off separately.
• Proposes a sensible baseline (routing ETA, then GBDT) and uses MAE plus a time-based split.

Senior (L5)

• Frames the model as a residual over the routing engine and justifies the asymmetric loss.
• Handles label noise (driver taps), snapshot sampling, as-of feature joins, and censored cancellations.
• Evaluates bias per segment and horizon, quantile coverage, and runs A/B with dispatch guardrails.
• Gives a latency budget and a fallback path.

Staff (L6+)

• Sees the dispatch and display feedback loops and proposes exploration, propensity weighting and
  switchback/geo experiments.
• Designs temporal consistency (smoothing, snap on reroute) as part of the product, not an afterthought.
• Plans the platform: shared feature store, streaming error memory, per-city bias layers, release gating
  across routing and model teams, and cost at 500k QPS.