How I Cut LLM Inference Cost by 84% with Epsilon-Greedy Routing

When I started building production ML systems on AWS, every inference request went to Bedrock's Claude Haiku. It worked great. It was also costing $0.25 per 1,000 requests. For high-throughput workloads, that number compounds fast.

The problem is that not every query needs a frontier LLM. A simple classification request that a fine-tuned sklearn model can answer in 43ms and $0.01/1K shouldn't be routed to a model that costs 25× more. But hardcoding routing rules — 'if query is short, use sklearn' — breaks the moment your traffic distribution changes.

This is the problem the Model Arbitration Engine solves. Here's exactly how it works.

The three-tier model pool

I benchmarked three model tiers before writing a single line of routing logic:

• —sklearn (logistic regression): 43ms avg latency, $0.01/1K — handles simple classification
• —XGBoost: 118ms avg latency, $0.05/1K — handles structured data with feature interactions
• —Bedrock Claude Haiku: 780ms avg latency, $0.25/1K — handles open-ended, reasoning-heavy queries

The routing decision needs to happen in milliseconds and must adapt as query complexity shifts over time. Static rules can't do this. A multi-armed bandit can.

Epsilon-greedy routing: the basics

The multi-armed bandit problem asks: given N options with unknown reward distributions, how do you maximise reward over time? The simplest solution is epsilon-greedy: with probability ε, explore (pick randomly); with probability 1-ε, exploit (pick the current best).

In my system, 'reward' is a composite score of accuracy, latency, and cost. Each model accumulates a running score based on outcomes. With ε=0.1, 90% of requests go to the current best model for that query type, and 10% explore the other tiers to keep estimates fresh.

import random

EPSILON = 0.1

def select_model(query_type: str, model_scores: dict) -> str:
    if random.random() < EPSILON:
        # explore: pick randomly
        return random.choice(list(model_scores.keys()))
    # exploit: pick highest composite score
    return max(model_scores[query_type], key=lambda m: model_scores[query_type][m])

EWMA latency tracking

Raw latency averages are noisy and slow to adapt. A single spike from a cold Lambda container can skew your average for hours. I use Exponentially Weighted Moving Average (EWMA) instead — it weights recent observations more heavily, so the routing adapts quickly to real latency changes.

ALPHA = 0.1  # smoothing factor — lower = slower adaptation

class LatencyTracker:
    def __init__(self):
        self.ewma: dict[str, float] = {}

    def update(self, model: str, latency_ms: float):
        if model not in self.ewma:
            self.ewma[model] = latency_ms
        else:
            self.ewma[model] = ALPHA * latency_ms + (1 - ALPHA) * self.ewma[model]

    def get(self, model: str) -> float:
        return self.ewma.get(model, float("inf"))

With α=0.1, a new observation has ~10% weight on the current estimate. The system reacts to real latency trends (cold starts, throttling) without overreacting to individual spikes.

The DynamoDB decision ledger

Every routing decision gets logged to DynamoDB: which model was selected, the query type, actual latency, cost, and the accuracy signal (where available). This gives you two things: a complete audit trail for debugging, and the training data to improve your routing model over time.

The table schema is simple — partition key on query_type, sort key on timestamp. Querying 'how did this query type perform on XGBoost over the last 7 days?' becomes a single DynamoDB query.

Results

After two weeks of production traffic with the bandit routing in place:

• —Inference cost dropped 84% vs routing everything to Bedrock
• —Overall accuracy held at 95.3% — within 0.7% of the Bedrock-only baseline
• —Average latency improved from 780ms to 87ms (most requests now hitting sklearn or XGBoost)
• —Exploration budget (the 10% random routes) provided enough signal to detect two cases where XGBoost had degraded on a query subtype

The full system is serverless — API Gateway → Lambda → SageMaker + Bedrock. No infrastructure to manage, auto-scales to zero when idle, and the Lambda cold start penalty gets amortised by the EWMA tracker.