/challenges

Consider the vanilla linear attention mechanism:where $v_t k_t^T$ is the outer product of $v_t$ and $k_t$.

Unrolling the recurrence, we get:where $s_i$ is the inner product $k_i^T q_t$.

It turns out that we can obtain this recurrence by maximizing the following Lagrangian:where $I_t$ is the $t \times t$ identity matrix, and $\alpha = (\alpha_1, \ldots, \alpha_t)$ is some vector of indeterminates.

Question: The update mechanism for DeltaNet is:Find a Lagrangian that leads to the coefficients in front of $v_i$ for $o_t$ in the DeltaNet formulation.

For $n \geq 2$, define the graph $G_n$:

• Vertices: Ordered pairs $(x, y)$ with $1 \leq x, y \leq n$ and $x \neq y$.
• Edges: $(x_1, y_1) \sim (x_2, y_2)$ if $x_1 + y_1 = x_2 + y_2$ or $x_1 - y_1 = x_2 - y_2$.

Define $L(G_n)$, the line graph of $G_n$:

• Vertices: Edges of $G_n$.
• Edges: Two vertices are adjacent if their corresponding edges share a vertex in $G_n$.

Find the number of induced subgraphs of $L(G_n)$ where every vertex has degree 2.
Express this count as an explicit function of $n$.