Measure fan-out amplification and the value of hedging

CodingIntermediate⏱ 1 hourAI Systemsfan-outtail latencyhedgingorder statisticssimulation

Theory: Tail Latency and Fan-Out Amplification →

Problem

Quantify what fan-out does to a tail, and what a hedged request buys back.

required_child_quantile(n, p) and parent_tail(n, child_tail) — the closed forms.
simulate_max_quantile(n, mean, p, trials, seed) — the empirical $p$ -quantile of the maximum of $n$ exponential latencies.
hedged_samples(mean, d, trials, seed) — latencies when a duplicate attempt starts at delay $d$ and the first response wins.
hedge_extra_load(p) — expected attempts per logical request when hedging at the $p$ -quantile.

Then confirm that the simulated hedged tail matches $\bar F(t)\bar F(t-d)$ for $t > d$ .

Implement it, then check the implementation against something you can verify independently.

Write it

Solve it here9 tests · Python runs in your browser

import numpy as np

def required_child_quantile(n, p):
    """The per-child quantile that a parent p-quantile demands.

A parent that waits for all n independent children meets its p-quantile at
    t exactly when every child's CDF reaches p**(1/n) at t. Return that
    probability.
    """
    raise NotImplementedError

def parent_tail(n, child_tail):
    """Probability the slowest of n independent children exceeds t, given that
    one child exceeds t with probability `child_tail`."""
    raise NotImplementedError

def simulate_max_quantile(n, mean, p, trials=20000, seed=0):
    """Empirical p-quantile of the maximum of n exponential latencies.

Draw a trials-by-n array of exponentials with the given mean from a
    generator seeded with `seed`, take the maximum of each row, and return the
    p-quantile of those maxima.
    """
    raise NotImplementedError

def hedged_samples(mean, d, trials=20000, seed=0):
    """Latency when a duplicate request is issued at delay d.

Draw two independent exponential attempts with the given mean. The first
    starts at time 0. If it has not finished by d, a second starts at d. The
    observed latency is whichever response arrives first. Return an array of
    `trials` such latencies.
    """
    raise NotImplementedError

def hedge_extra_load(p):
    """Expected number of attempts per logical request when the hedge fires at
    the p-quantile of the latency distribution."""
    raise NotImplementedError

⌘/Ctrl + ↵ to run · limit 90s · draft saved in this browser

9 tests will run against your code. The first run downloads the Python runtime — several megabytes, once per browser.

Hints

Hints — 0 of 2 revealed

Solution

Opening this before you have a real attempt on paper is the fastest way to feel like you understand something you cannot reproduce.

Problem	Field	Type	Difficulty	Time
Budget a latency target across a fan-out	AI Systems	Numerical	Beginner	15 min
Simulate distance contrast run	Classical ML	Coding	Beginner	30 min
Balls into bins, with one choice and with two run	AI Systems	Coding	Intermediate	1 hour
Cache hit rates under Zipf popularity run	AI Systems	Coding	Intermediate	1 hour
Measure anisotropy in an embedding space run	RAG	Coding	Intermediate	1 hour

Problem

Write it

Hints

Solution

Related problems