Latest / The CTO Podcast with Fexingo: Technical Leadership, Architecture, and Engineering Org / How Lyft Rebuilt Its Ride Matching Algorithm
Transcript
- Lucas: Lyft's ride matching algorithm used to be a classic operations research problem — solve a linear assignment in real time. But as cities grew and demand patterns got spiky, that approach started hitting a wall. Luna: Yeah, I remember reading that by early 2024, wait times in dense cities like San Francisco and New York were actually increasing despite more drivers on the road. Lucas: Exactly. And that's what pushed Lyft to essentially tear down and rebuild their entire dispatch system. Today, we're going to look at what they did and why it matters for any CTO running a real-time matching platform. Luna: Before we get into the technical weeds — I just want to say, we deliberately keep this show ad-free because we think these deep engineering conversations should stand on their own. If you find them useful, you can support that choice at buy me a coffee dot com slash fexingo. Lucas: Yeah, it's a small way to help us keep the signal strong and avoid the noise. So, back to the rebuild — what did Lyft actually change? Lucas: First, they moved away from a pure linear programming approach, where every few seconds you'd solve the Hungarian algorithm across all open requests and available drivers. That works fine for a few hundred variables, but Lyft's network in a city like Los Angeles involves tens of thousands of drivers and requests. Luna: And the combinatorial complexity grows pretty fast. So they switched to a graph neural network model that learns spatial and temporal patterns. Lucas: Right. The GNN takes in a graph where nodes are drivers and requests, and edges have features like distance, traffic, and historical acceptance rates. It predicts a score for each potential match, and then they run a lightweight optimization on top. Luna: One thing I find fascinating is that they had to make the GNN inference sub-second — because you can't have the dispatch loop waiting 500 milliseconds. Lucas: Yeah, they aimed for under 100 milliseconds end to end. That meant model quantization, using ONNX Runtime, and careful partitioning of the graph across CPU cores. They also designed a stateful model that keeps a latent representation of each driver's recent activity. Luna: So the model isn't just looking at a snapshot; it remembers that this driver just dropped off someone in a certain neighborhood and might be heading home. Lucas: Exactly. That improved driver satisfaction and utilization. In their rollout across two pilot cities — Austin and Chicago — they saw a 15% reduction in passenger wait time and a 10% increase in driver utilization during peak hours. Luna: Those are concrete numbers. And it wasn't just the model — they also rebuilt the data pipeline to feed the model fresh data every second. Lucas: Right. The old pipeline used batch processing with a five-minute lag. The new one uses Kafka streams and a Flink-based feature store that updates driver and request features in real time. That alone reduced stale matches by a huge margin. Luna: How did they handle the rollout? A big change like that could easily break the entire matching system. Lucas: They used a shadow mode approach. For weeks, they ran both the old linear assignment and the new gnn based system in parallel. The shadow output was compared without affecting actual dispatching. Only when they saw consistent improvements did they start switching traffic gradually. Luna: Smart. And I imagine they had to build a lot of observability specifically for this — to detect regressions in match quality. Lucas: Absolutely. They instrumented everything: match latency, driver acceptance rate, ride cancellation rate. They even tracked the 'regret' metric — how much better the optimal linear assignment would have been versus the GNN recommendation. It converged quickly. Luna: So what are the main lessons for CTOs who might be considering a similar rebuild in their own systems? Lucas: The first is that you don't need to abandon classic algorithms entirely. Combining ML with a small optimization step gives you the best of both. The second is that real-time inference at scale is a software engineering challenge as much as a data science one. Lucas: And third — instrument your shadow system ruthlessly. You need to trust the new system before you let it touch production. Lyft spent three months in shadow mode, and that patience paid off. Luna: That's a good reminder. It's easy to get excited about the new tech and rush it out. But the CTO's job is to balance that enthusiasm with the rigor of production safety. Lucas: Exactly. And I think that's a great note to end on. Thanks for listening.