Incremental Hard Attention with a KV Cache
Updated
Problem statement
Implement a deterministic incremental attention adapter. The input contains n token embeddings and n position embeddings, each of dimension d, plus square key and value weight matrices.
At step t:
- Initialize the hidden vector as
h = tokenEmbeddings[t] + positionEmbeddings[t]. - Use
has the query. Computekey = h * keyWeightsandvalue = h * valueWeightswith row-vector matrix multiplication, then append them to separate key and value caches. - Apply the causal rule by considering only cached keys from steps
0throught. Select the index with maximum dot product between the query and a cached key. Break ties by choosing the earliest index. - Output the cached value at the selected index.
Return all output vectors in step order.
Function
cachedCausalHardAttention(tokenEmbeddings: int[][], positionEmbeddings: int[][], keyWeights: int[][], valueWeights: int[][]) → int[][]Examples
Example 1
tokenEmbeddings = [[1,0],[1,1]]positionEmbeddings = [[0,0],[0,0]]keyWeights = [[1,0],[0,1]]valueWeights = [[0,1],[1,0]]return = [[0,1],[1,1]]At each step, the newest key has the unique highest score. Values come from the separate value projection, not from the attention output.
Example 2
tokenEmbeddings = [[0,0],[0,0]]positionEmbeddings = [[1,0],[1,0]]keyWeights = [[1,0],[0,1]]valueWeights = [[2,0],[0,2]]return = [[2,0],[2,0]]Position embeddings initialize both hidden vectors. Equal scores at the second step select the earlier cached value.
Constraints
1 <= n <= 200.1 <= d <= 40.- Both embedding matrices have shape
n x d. - Both weight matrices have shape
d x d. - Every input value is between
-100and100. - Every matrix product, attention score, and output fits in a signed 32-bit integer; use 64-bit intermediates when comparing scores.
More OpenAI Phone Screen questions
- Secret Number Search with One-Call-Delayed FeedbackPHONE SCREEN · Seen Nov 2026
- Determine the Winner of Three-Card HandsPHONE SCREEN · Seen Nov 2026
- Grid Infection with Recovery After D DaysPHONE SCREEN · Seen Nov 2026
- Sparse Plant Infection SimulationPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Light Source Hits: Sample, Compare, and FitPHONE SCREEN · Seen Nov 2026
- Rectangle Point Coverage CountsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Adaptive Calibration ErrorPHONE SCREEN · Seen Nov 2026
- Elevator Scheduling SimulationPHONE SCREEN · Seen Nov 2026
- Evaluate Noisy AnnotatorsPHONE SCREEN · Seen Oct 2026
- Network Endpoint or Cycle BoundaryOA · PHONE SCREEN · Seen Oct 2026
Similar questions at other companies
- Spiral MatrixNike, Inc. · ONSITE INTERVIEWNike, Inc. interview questions
- Apply a 2048 Board MoveGlean · PHONE SCREENGlean interview questions
- Spiral Order with ObstaclesTemu · PHONE SCREENTemu interview questions
- Spiral Matrix TraversalByteDance · PHONE SCREENByteDance interview questions
- Stochastic Gradient Descent with MomentumMeta · ONSITE INTERVIEWMeta interview questions
- S-Shaped Matrix TraversalFox Corporation · PHONE SCREEN
- Longest Consecutive Same-Color LineGoogle · PHONE SCREENGoogle interview questions
- Process Minesweeper Game OperationsAmperity · PHONE SCREENAmperity interview questions
- Minesweeper Board UpdateUber · ONSITE INTERVIEWUber interview questions
- Diagonal TraverseHive · PHONE SCREENHive interview questions