Cheapest Cache TTL Meeting a Freshness SLA

hardPROProduction: Cost, Caching & EvalsAI AgentsAI Agents 1

Problem Statement

Choose the largest cache TTL (to save the most cost) such that the fraction of served responses that are stale stays within a freshness SLA, given a trace of requests and underlying-data change times.

Background

A cached entry created at time t is valid until t + ttl. For a request stream (sorted times), the cache serves a key from cache if a valid entry exists (created within ttl of now and after the last data change for that key); otherwise it recomputes and creates a fresh entry. A served-from-cache response is stale if the underlying data changed after the cached entry was created. We are given, per request, whether serving it from a cache of a given ttl would be stale — abstracted as: for candidate ttl values, a function tells us the stale fraction. Concretely: given candidates (sorted ascending ttl values) and a parallel list stale_fraction (the resulting stale fraction at each ttl, non-decreasing in ttl), return the largest ttl whose stale fraction <= sla. If even the smallest exceeds sla, return -1.

Your Task

def best_ttl(candidates, stale_fraction, sla):

candidates: ascending ttl values; stale_fraction[i] corresponds to candidates[i] and is non-decreasing.
Return the largest qualifying ttl, or -1.

Input Format

candidates (list of ints, ascending), stale_fraction (list of floats, non-decreasing), sla (float).

Output Format

An int (a ttl) or -1.

Sample

print(best_ttl([10, 60, 300], [0.0, 0.02, 0.2], 0.05))

Output:

Example

Input

print(best_ttl([10, 60, 300], [0.0, 0.02, 0.2], 0.05))

Output

Reasoning

We identify the valid range of TTLs by checking which candidates have a stale fraction $\le 0.05$ . The fractions are $[0.0, 0.02, 0.2]$ , so indices 0 and 1 qualify, while index 2 ( $0.2 > 0.05$ ) does not.
To find the largest valid TTL efficiently, we perform a binary search on the sorted candidates list $[10, 60, 300]$ , aiming to find the rightmost index where the condition holds.
In the first step, we check the middle element at index 1: the stale fraction is $0.02$ , which is $\le 0.05$ . Since this is valid, we record 60 as a potential answer and search the right half for a larger valid TTL.
In the next step, we check the new middle element at index 2: the stale fraction is $0.2$ , which is $> 0.05$ . This is invalid, so we discard this right half and stop searching further right.
The search concludes with the last recorded valid candidate, which is the largest TTL meeting the SLA.
The final output is 60

Constraints

stale_fraction is non-decreasing in ttl, so qualifying ttls form a prefix.
Return the largest ttl with stale_fraction <= sla (binary search the prefix).
Return -1 if none qualify.

More from AI Agents 1

Bootstrap Confidence Interval Width for Eval Accuracymedium Route to the Cheapest Model Meeting Qualitymedium pass@k Estimatormedium Savings from a Semantic Cachemedium Cache Hit Rateeasy

Concept primerPREVIEW

1. Background Knowledge

This problem sits at the intersection of caching economics and service-level agreements (SLAs). In production systems, a cache entry created at time $t$ with a time-to-live (TTL) of $\tau$ is considered valid until $t + \tau$ . When the underlying data changes, any cached entry created before that change is stale. Serving stale data can violate freshness guarantees, so systems often impose an SLA: the fraction of responses served from cache that are stale must not exceed a threshold $s_{\text{sla}}$ .

The key insight here is the monotonicity of the stale fraction with respect to TTL. As you increase the TTL, entries live longer, so more of them outlive data changes. Consequently, the stale fraction is a non-decreasing function of TTL. This monotonicity is what makes the problem tractable: instead of checking every candidate, you can exploit the ordered structure to find the boundary where the constraint flips from satisfied to violated.

In practice, you would measure or simulate the stale fraction for various TTLs. Here, that measurement is abstracted away: you are given a sorted list of candidate TTLs and their corresponding stale fractions, and your job is purely to find the optimal TTL under the constraint.

2. Algorithm Approach

Because stale_fraction is non-decreasing and candidates is ascending, the set of valid TTLs (those with stale fraction $\le$ sla) forms a prefix of the candidate list. You are looking for the rightmost element in this prefix.

This is a classic binary search scenario. Specifically, you want to find the largest index $i$ such that stale_fraction[i] <= sla. If no such index exists (i.e., even the first element exceeds the SLA), return -1.

Binary search works because the predicate stale_fraction[mid] <= sla is True for a contiguous prefix and False for the remaining suffix. You search for the boundary between these two regions.

3. Step-by-Step Strategy

PRO

Continue the full explanation

You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.