Build Causal Mask with Position Offsets for Cached Attention

MediumML Coding

Problem statement

During incremental decoding with a key-value cache, the query sequence is short (often just the newly generated tokens) while the key sequence contains all cached past tokens plus the current ones. A correct causal mask must reflect the absolute positions of the queries within the full sequence so that each query attends only to keys at the same or earlier absolute position.

Implement a function build_causal_mask(q_len, k_len, start_pos) that returns a 2D boolean mask of shape (q_len, k_len) such that mask[i][j] is True if and only if key position j is allowed to be attended by query i. The absolute position of query i is start_pos + i, and a query at absolute position p may attend to all key positions j with j <= p.

Return the mask as a nested Python list of booleans (use .tolist() on a numpy array).

Assume q_len >= 0, k_len >= 0, and start_pos >= 0. When q_len or k_len is 0, return an empty list or a list of empty lists accordingly.

Example

Input:

q_len = 2, k_len = 6, start_pos = 4

Output:

[[True, True, True, True, True, False], [True, True, True, True, True, True]]

Reasoning: Query 0 has absolute position 4, so it may attend to key indices 0..4 (True) but not 5 (False). Query 1 has absolute position 5, so it may attend to all 6 keys.

Show hint

Where does each new query token sit in the full sequence once the cache is included?

Relevant roles: LLM Engineer, ML Engineer, AI Engineer and Deep Learning Engineer.

Related free problems