📘

Trigger Summarization at a Budget Fraction

Problem Statement

An agent summarizes old turns once its running context grows past a fraction of the model's window. Given cumulative message token sizes, find the first message index at which summarization should trigger.

Background

Let budget be the context window and threshold a fraction (e.g. 0.75). Walking messages in order and accumulating tokens, summarization triggers at the first message whose inclusion makes the running total strictly exceed threshold * budget. If the total never exceeds it, no trigger fires.

Your Task

Implement:

def summarize_trigger(sizes, budget, threshold):

sizes: list of per-message token counts, in order.
Return the 0-based index of the first message at which the running sum > threshold * budget, or -1 if it never happens.

Input Format

sizes (list of ints), budget (int), threshold (float).

Output Format

An int index or -1.

Sample

print(summarize_trigger([100, 100, 100, 100], 500, 0.75))

Output:

Example:

Input:

print(summarize_trigger([100, 100, 100, 100], 500, 0.75))

Output:

Reasoning:

Calculate the token limit by multiplying the budget by the threshold: $500 \times 0.75 = 375$ . This defines the strict upper bound for the running sum before summarization triggers.
Process the first message (index 0) with 100 tokens. The running sum becomes $0 + 100 = 100$ . Since $100 \ngtr 375$ , the trigger condition is not met.
Process the second message (index 1) with 100 tokens. The running sum becomes $100 + 100 = 200$ . Since $200 \ngtr 375$ , the trigger condition is not met.
Process the third message (index 2) with 100 tokens. The running sum becomes $200 + 100 = 300$ . Since $300 \ngtr 375$ , the trigger condition is not met.
Process the fourth message (index 3) with 100 tokens. The running sum becomes $300 + 100 = 400$ . Since $400 > 375$ , the threshold is exceeded, and the function returns the current index.
The final output is 3

Constraints:

0 <= len(sizes) <= 100000, budget >= 1, 0 < threshold <= 1.
Trigger is the first index where the running sum strictly exceeds threshold*budget.
Return -1 if never exceeded.

More from AI Agents 1

Cheapest Cache TTL Meeting a Freshness SLAHard Bootstrap Confidence Interval Width for Eval AccuracyMedium Route to the Cheapest Model Meeting QualityMedium pass@k EstimatorMedium Savings from a Semantic CacheMedium

1. Background Knowledge

This problem models a core mechanism in LLM agent memory management. Large language models have a fixed context window (measured in tokens). As an agent converses, the cumulative token count of the conversation grows. To prevent exceeding the window, systems often summarize older turns, effectively compressing history. The trigger point is defined by a budget fraction: summarization activates once the running total of tokens strictly exceeds threshold * budget.

The mathematical core is a prefix sum (or running total). Given a sequence of non-negative integers $s_0, s_1, \dots, s_{n-1}$ , the prefix sum at index $i$ is:

P_i = \sum_{k=0}^{i} s_k

You are searching for the smallest index $i$ such that $P_i > T$ , where $T = \text{threshold} \times \text{budget}$ . If no such $i$ exists, the answer is $-1$ . This is a classic first-exceedance query over a monotonically non-decreasing sequence (since all token sizes are non-negative, prefix sums never decrease).

2. Algorithm Approach

The pattern here is a linear scan with early termination. Because prefix sums are monotonically non-decreasing, once the running total exceeds the threshold, you can immediately return the current index — no further messages need to be inspected.

The algorithm:

Compute the threshold value $T = \text{threshold} \times \text{budget}$ .
Iterate through sizes, maintaining a running sum.
After adding each element, check if the running sum strictly exceeds $T$ .
If yes, return the current index. If the loop completes without triggering, return $-1$ .

This is essentially a prefix-sum first-exceedance search. Because the sequence is monotonic, a binary search over precomputed prefix sums is theoretically possible ( $O(\log n)$ after $O(n)$ preprocessing), but for a single query a simple linear scan is optimal and simpler.

3. Step-by-Step Strategy

Compute the threshold: Calculate limit = threshold * budget. Store this as a float or compare carefully to avoid repeated multiplication.
Initialize a running total: Set running = 0.
Iterate with index: Loop over sizes using enumerate so you have both the index and the token count.
Accumulate: Add the current token count to running.
Check condition: After each addition, test whether running > limit. Note the strict inequality — equal to the limit does not trigger.
Early return: If the condition is met, return the current index immediately.
Fallback: If the loop finishes without any trigger, return -1.

👑

Continue the full explanation

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

🔒

Editor locked

The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.

solution.py

Python 3.13

Test Results

0/0

Run code to see test results.