Context Window Token Budget Fittingmedium

Context Window Token Budget Fitting

medium RAG & Retrieval 15 min

NumPy allowed · plain Python earns 10 bonus points

A query retrieves context

Embedding similarity ranks the documents before generation.

Open lesson →

01query

02embed

03retrieve

04context

What is RAG?→ embed →top context

retrieval.md44%

rag-systems.md33%

agents.md24%

Cosine-like similarity scores ranked before context assembly

Implement context-window budget fitting: greedily including the highest-scored retrieved chunks until the token budget runs out.

Task

Implement fit_context_budget(chunks, token_budget). chunks is a list of {"id": str, "text": str, "score": float, "tokens": int}. Sort by score descending, then greedily include chunks (in that order) as long as the running token total stays <= token_budget. Return the included chunks' ids in the order they were included.

Function Signature

fit_context_budget(chunks: list[dict], token_budget: int) -> list[str]

Examples

Example 1: all fit
Input: chunks = [{'id': 'a', 'text': 'x', 'score': 0.9, 'tokens': 100}, {'id': 'b', 'text': 'y', 'score': 0.5, 'tokens': 100}]
token_budget = 500
Output: ['a', 'b']

Example 2: budget forces skipping lowest
Input: chunks = [{'id': 'a', 'text': 'x', 'score': 0.9, 'tokens': 300}, {'id': 'b', 'text': 'y', 'score': 0.5, 'tokens': 300}]
token_budget = 400
Output: ['a']

Example 3: smaller chunk fits after larger skipped
Input: chunks = [{'id': 'a', 'text': 'x', 'score': 0.9, 'tokens': 500}, {'id': 'b', 'text': 'y', 'score': 0.5, 'tokens': 100}]
token_budget = 400
Output: ['b']

Constraints

token_budget >= 0

Python3Saved ✓

def fit_context_budget(chunks, token_budget):

# Your implementation here

pass

Case 1: all fit

Input: chunks = [{'id': 'a', 'text': 'x', 'score': 0.9, 'tokens': 100}, {'id': 'b', 'text': 'y', 'score': 0.5, 'tokens': 100}]
token_budget = 500

Expected: ['a', 'b']

Case 2: budget forces skipping lowest

Input: chunks = [{'id': 'a', 'text': 'x', 'score': 0.9, 'tokens': 300}, {'id': 'b', 'text': 'y', 'score': 0.5, 'tokens': 300}]
token_budget = 400

Expected: ['a']

Case 3: smaller chunk fits after larger skipped

Input: chunks = [{'id': 'a', 'text': 'x', 'score': 0.9, 'tokens': 500}, {'id': 'b', 'text': 'y', 'score': 0.5, 'tokens': 100}]
token_budget = 400

Expected: ['b']