Alle Herausforderungen
Schwierig 1 gelöst 100.0% Erfolgsquote

Scaled Dot-Product Attention

Implement the attention operation at the heart of Transformers and large language models.

Das lernst du

  • Score queries against keys
  • Apply softmax to get attention weights
  • Mix values with those weights

Problem

Übersetzung anzeigen

Attention lets each position in a sequence look at every other position and mix their information. It is the core of the Transformer architecture used by large language models:

Attention(Q, K, V) = softmax(Q × Kᵀ / √d) × V

For each query row q:

  1. Score every key row k: score = (q · k) / √d, where d is the number of columns of K.
  2. Turn the scores into weights with softmax (subtract the largest score before taking e^x).
  3. The output row is the weighted sum of the value rows: Σ weight_j × values[j].

Implement attention(queries, keys, values).

Input

queries: n rows, each with d numbers.

keys: m rows, each with d numbers.

values: m rows (one per key), each with v numbers.

Output

Return the n × v output matrix.

Einschränkungen

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

-10 ≤ each value ≤ 10

Beispiele

Beispiel 1
Eingabe:
queries = [
    [1.0, 0.0]
]
keys = [
    [1.0, 0.0],
    [1.0, 0.0]
]
values = [
    [2.0, 4.0],
    [6.0, 8.0]
]

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

Erwartete Ausgabe:
std::vector<std::vector<double>> expected = {
    {4.0, 6.0}
};
Eingabe:
double[][] queries = new double[][] {
    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[] {2.0, 4.0},
    new double[] {6.0, 8.0}
};

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

Erläuterung

Both keys give the same score, so the softmax weights are 0.5 and 0.5. The output is the average of the value rows: [(2 + 6) / 2, (4 + 8) / 2] = [4, 6].

Beispiel 2
Eingabe:
queries = [
    [0.0, 0.0]
]
keys = [
    [3.0, 1.0],
    [-2.0, 5.0],
    [7.0, 7.0]
]
values = [
    [1.0],
    [2.0],
    [6.0]
]

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

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

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

Erläuterung

A zero query scores 0 against every key, so attention is spread evenly: (1 + 2 + 6) / 3 = 3.

So gehst du vor

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

Hinweis 1

For each query, compare it with every key using a dot product scaled by the square root of the key dimension.

Hinweis 2

Convert the scores into weights with a numerically stable softmax, then blend the value rows using those weights.

Hinweis 3

Each query produces one output row, and the value vectors determine the output width rather than the queries or keys.

Erwartete Komplexität

O(n m (d + v)) time, O(m) 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.

# Coder Sprache Zeit Speicher KI-Bewertung Lösung
1 ННикита Python 833 ms - 5/5 Code ansehen

Von anderen lernen

Community-Lösungen

Achtung Spoiler: 1 vollständige Lösung unten Versuche es zuerst selbst zu lösen. Du kannst trotzdem einen Blick auf den Code und die KI-Reviews anderer Entwickler werfen. Melde dich an und löse die Aufgabe, um an der Diskussion teilzunehmen.