Alle Herausforderungen
Mittel 0 gelöst 0% Erfolgsquote

Causal (Masked) Self-Attention

Implement the masked attention GPT models use, where each token can only look at itself and earlier tokens.

Das lernst du

  • Hide future tokens with a causal mask
  • Apply softmax over allowed positions only
  • Understand how language models generate text

Problem

Übersetzung anzeigen

A language model must not peek at future words. Causal attention masks the future: query row i may only attend to key rows 0 to i.

For each row i (queries, keys and values all have n rows):

  1. Score each allowed key j ≤ i: score = (queries[i] · keys[j]) / √d, where d is the number of columns of keys.
  2. Apply softmax over those allowed scores only (subtract the largest before taking e^x).
  3. Output row i = Σ weight_j × values[j] over j ≤ i.

Implement causal_attention(queries, keys, values).

Input

queries, keys: n rows of d numbers each.

values: n rows of v numbers each.

Output

Return the n × v output matrix.

Einschränkungen

1 ≤ n ≤ 50, 1 ≤ d, v ≤ 32

-10 ≤ each value ≤ 10

Beispiele

Beispiel 1
Eingabe:
queries = [
    [0.0],
    [0.0],
    [0.0]
]
keys = [
    [1.0],
    [2.0],
    [3.0]
]
values = [
    [3.0],
    [6.0],
    [9.0]
]

Erwartete Ausgabe:
expected = [
    [3.0],
    [4.5],
    [6.0]
]
Eingabe:
std::vector<std::vector<double>> queries = {
    {0.0},
    {0.0},
    {0.0}
};
std::vector<std::vector<double>> keys = {
    {1.0},
    {2.0},
    {3.0}
};
std::vector<std::vector<double>> values = {
    {3.0},
    {6.0},
    {9.0}
};

Erwartete Ausgabe:
std::vector<std::vector<double>> expected = {
    {3.0},
    {4.5},
    {6.0}
};
Eingabe:
double[][] queries = new double[][] {
    new double[] {0.0},
    new double[] {0.0},
    new double[] {0.0}
};
double[][] keys = new double[][] {
    new double[] {1.0},
    new double[] {2.0},
    new double[] {3.0}
};
double[][] values = new double[][] {
    new double[] {3.0},
    new double[] {6.0},
    new double[] {9.0}
};

Erwartete Ausgabe:
double[][] expected = new double[][] {
    new double[] {3.0},
    new double[] {4.5},
    new double[] {6.0}
};

Erläuterung

All scores are 0, so each row averages the values it may see: row 0 sees only 3, row 1 averages 3 and 6 (4.5), row 2 averages all three (6).

Beispiel 2
Eingabe:
queries = [
    [1.0, 0.0],
    [1.0, 0.0]
]
keys = [
    [1.0, 0.0],
    [1.0, 0.0]
]
values = [
    [1.0, 2.0],
    [3.0, 4.0]
]

Erwartete Ausgabe:
expected = [
    [1.0, 2.0],
    [2.0, 3.0]
]
Eingabe:
std::vector<std::vector<double>> queries = {
    {1.0, 0.0},
    {1.0, 0.0}
};
std::vector<std::vector<double>> keys = {
    {1.0, 0.0},
    {1.0, 0.0}
};
std::vector<std::vector<double>> values = {
    {1.0, 2.0},
    {3.0, 4.0}
};

Erwartete Ausgabe:
std::vector<std::vector<double>> expected = {
    {1.0, 2.0},
    {2.0, 3.0}
};
Eingabe:
double[][] queries = new double[][] {
    new double[] {1.0, 0.0},
    new double[] {1.0, 0.0}
};
double[][] keys = new double[][] {
    new double[] {1.0, 0.0},
    new double[] {1.0, 0.0}
};
double[][] values = new double[][] {
    new double[] {1.0, 2.0},
    new double[] {3.0, 4.0}
};

Erwartete Ausgabe:
double[][] expected = new double[][] {
    new double[] {1.0, 2.0},
    new double[] {2.0, 3.0}
};

Erläuterung

Row 0 can only see itself, so it copies values[0] = [1, 2]. Row 1 gives both keys the same score, so it averages them: [2, 3].

So gehst du vor

Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.

Hinweis 1

Each output row can only use keys and values from the current row and earlier rows.

Hinweis 2

Compute dot products, scale by the square root of the key dimension, then apply a stable softmax over only the allowed rows.

Hinweis 3

Remember to normalize separately for every query row, and handle the first row with just one allowed key.

Erwartete Komplexität

O(n^2 * (d + v)) time, O(n * v) extra space

Referenzen

Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.

Die beste bestandene Lösung jedes Coders. Schnellere, sparsamere und besser bewertete Lösungen stehen weiter oben.

Noch keine bestandene Lösung. Löse sie und hol dir Platz eins.

Von anderen lernen

Community-Lösungen

Noch keine veröffentlichten Lösungen. Löse die Aufgabe und teile als Erster eine Lösung.