Tất cả thử thách
Khó 1 đã giải Tỷ lệ chấp nhận 100.0%

Scaled Dot-Product Attention

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

Bạn sẽ học được gì

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

Đề bài

Xem bản dịch

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.

Ràng buộc

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

-10 ≤ each value ≤ 10

Ví dụ

Ví dụ 1
Đầu vào:
queries = [
    [1.0, 0.0]
]
keys = [
    [1.0, 0.0],
    [1.0, 0.0]
]
values = [
    [2.0, 4.0],
    [6.0, 8.0]
]

Kết quả mong đợi:
expected = [
    [4.0, 6.0]
]
Đầu vào:
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}
};

Kết quả mong đợi:
std::vector<std::vector<double>> expected = {
    {4.0, 6.0}
};
Đầu vào:
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}
};

Kết quả mong đợi:
double[][] expected = new double[][] {
    new double[] {4.0, 6.0}
};

Giải thích

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].

Ví dụ 2
Đầu vào:
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]
]

Kết quả mong đợi:
expected = [
    [3.0]
]
Đầu vào:
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}
};

Kết quả mong đợi:
std::vector<std::vector<double>> expected = {
    {3.0}
};
Đầu vào:
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}
};

Kết quả mong đợi:
double[][] expected = new double[][] {
    new double[] {3.0}
};

Giải thích

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

Hướng tiếp cận

Hãy tự thử trước, sau đó mở từng gợi ý một.

Gợi ý 1

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

Gợi ý 2

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

Gợi ý 3

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

Độ phức tạp mong đợi

O(n m (d + v)) time, O(m) extra space

Tham khảo

Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.

Lời giải đạt tốt nhất của mỗi người. Lời giải nhanh hơn, tốn ít bộ nhớ hơn và được đánh giá cao hơn sẽ đứng trên.

# Người giải Ngôn ngữ Thời gian Bộ nhớ AI đánh giá Lời giải
1 ННикита Python 833 ms - 5/5 Xem code

Học hỏi từ người khác

Giải pháp cộng đồng

Cảnh báo: Có 1 lời giải đầy đủ bên dưới Hãy thử tự giải trước. Bạn vẫn có thể xem mã của người khác và đánh giá AI. Đăng nhập và giải thử thách để tham gia thảo luận.