\documentclass{article}
\usepackage[utf8]{inputenc}
\usepackage[a4paper, total={6in, 8in}]{geometry}
\usepackage{amsmath, amsfonts}
\usepackage{hyperref, graphicx}

\title{CSCI 145 Problem 20: Build an Associative Memory}
\author{} % TODO: Put your name here
\date{\today}

\begin{document}
\maketitle

\subsection*{Submission Instructions}
Please upload your work to Gradescope by \textbf{11:59pm on DATE}. % TODO: date
\begin{itemize}
\item Turn in a single PDF of \textit{handwritten} solutions. Typed (including \LaTeX) solutions will not be accepted.
\item Problems are grouped into three-week \textbf{cycles}. Once per cycle, you will meet with the grader and present the solution to \emph{one} problem from that cycle, selected at random when you arrive; bring your work and be ready to explain any of them.
\end{itemize}

\newpage \section*{Problem 20: Build an Associative Memory \hfill \textnormal{2 points}}

A memory contains at most $n\geq2$ records $(t_j,\mathbf{u}_j)$, where token $t_j$ comes from a vocabulary of size $V$ and $\mathbf{u}_j\in\mathbb R^p$ is its stored value. A query token $q$ should return the value paired with it. Treat token identities as one-hot vectors and the $\mathbf{u}_j$ as the value vectors already produced by $\mathbf{W}_V$. Assume $0<\delta<1/2$.

Consider the single-head construction $\mathbf{W}_Q=\mathbf{W}_K=s\mathbf{I}_V$, with key dimension $d_k=V$. Audit how well it acts as an associative memory. Whenever $q$ occurs exactly once, determine how $s$ must depend on $n$ and $\delta$ to give its record attention weight at least $1-\delta$, uniformly over memories of length at most $n$.

Now allow the same token to occur twice with different stored values, and require the most recent occurrence. Prove that a content-only head cannot meet this requirement for every memory, regardless of its learned query and key matrices. Describe one concrete kind of positional information that would break the tie in favor of the later duplicate, and explain how it removes the obstruction. You do not need to optimize a positional scale.

\paragraph{Results you may use.}
You may use the scaled dot-product attention and row-wise softmax definitions from the reading. A content-only attention layer is permutation equivariant.

%\input{solutions/solution20}
\end{document}
