Sparse dot product

Store the indices of the non-zero values and the non-zero values themselves. There are other design choices that will further simplify your program, which you may come across as you begin thinking through the code:

• The lists should be sorted.
• Keep one contiguous list of indices and one contiguous list of values.

from dataclasses import dataclass

@dataclass
class SparseVector:
    indices: list[int]
    values: list[float]
    length: int

You should propose a new variable for the number of non-zero values, e.g., k. Your algorithm runs in O(k) time. The input vectors each take O(k) space, but the dot product function itself takes O(1) space, since only constant space is allocated for the final result.

First, compute the size of the naive representation. Assume our vector has length N and that each element in our vector takes B bits to represent. The naive representation takes up $\text{bits}_\text{naive} = NB$ bits.

Second, compute the size of the sparse representation. Assume our vector contains K non-zero values. The values list is simply KB. Our indices list will contain K values but the integers need to be able to represent values up to N — our indices would ideally use only $\lceil\text{log}_2(N)\rceil$ bits to do so. So in short, our sparse representation requires $\text{bits}_{sparse} = K(B + \lceil\text{log}_2(N)\rceil)$ bits.

• There's a possibility you accidentally said the indices list is also KB bits. The interviewer should prompt you to reconsider the bit width. Failing that, I'd ask the candidate to assign a concrete value to B, then try the next bullet point — proposing a length N that your B bit-width integer can't represent.
• You might propose a reasonable bit width for integers, such as a 2-byte uint16. However, if this is the case, the interviewer should ask about a length that clearly exceeds the representable maximum. In this case, what if my vector has 100,000 values? This exceeds the largest possible index that uint16 can hold, which is $2^{16} = 65536$.
• Make sure you're using log bits. This is crucial: An L-bit number can represent integers up to $2^L$. An L-byte number can represent much more, $2^{8L}$. The unit matters.
• If you've gotten this far and realized it was $\text{log}(N)$, make sure you're (a) using the right base of 2, not the default natural logarithm; and (b) using the ceiling divide. The logarithmic value may be non-integral.

We should pick the sparse representation whenever the number of sparse bits is less than the number of dense bits, or equivalently

$$K(B + \lceil\text{log}_2(N)\rceil) < NB$$

If the interviewer was mean, they could ask you: How would you simplify this expression?

• As is, it's impossible to isolate N, as a result, the only option you have off the bat is to isolate K instead. B is usually a fixed value, based on how you pre-trained model.
• To further simplify this expression, we'd ideally apply a linear bound to the log term. That's impossible to do tightly, in the general case.

Unfortunately, we can't simplify much, so here's an expression:

$$K < \frac{NB}{B + \lceil\text{log}_2(N)\rceil}$$

On its own, this fraction isn't very informative.

Most state-of-the-art papers achieve 30-40% sparsity with minimal degradation and exhibit some kind of tradeoff curve for more aggressive sparsity rates. Any answer in the range 20-80% is probably acceptable here. This gives you the chance to show off any knowledge of recent papers you may have. Let's say that 50% sparsity can be achieved with negligible quality degradation, so K = N/2.

For those up-to-date with literature: Since we're working with unstructured sparsity within a single tensor, we're ignoring structured sparsity techniques.

You should know this from Math to memorize. A cloud model may have model dimensions as large as 16384. This could also be as small as 1024. Let's use N=16384 for cloud and N=1024 for on-device.

Training is usually done in mixed-precision, using BF16, FP16 and FP32. Inference is usually done in BF16 or FP16 when not quantized. With quantization, you could see bitrates as low as 4 bits per weight. There are even more aggressively quantized models, but we can ignore those for now. Let's use B=4 bits for inference, B=32 bits for training.

Our next step is to actually plug values into our expresion.

• One way to approach this question is to simply start plugging in values directly.
• Extra bonus points if you realize you can now simplify your expression, by plugging in K=N/2, which will greatly simplify what we have to consider.

Our simplified expression is now:

$$\begin{align}K = \frac{N}{2} &< \frac{NB}{B + \lceil\text{log}_2(N)\rceil}\\1 &< \frac{2B}{B + \lceil\text{log}_2(N)\rceil}\\\lceil\text{log}_2(N)\rceil &< B\\N &< 2^B&\text{ignored the ceil rounding for simplicity}\end{align}$$

If you don't want to ignore the ceiling div naively, you could

1. Create a stricter bound by converting $\lceil\text{log}_2(N)\rceil < B$ into $\lceil\text{log}_2(N)\rceil \leq B - 1$.
2. Then, realize that $\text{log}_2(N) \leq \lceil\text{log}_2(N)\rceil$, so we can plug this in with equivalence.

This leaves you with the following expression.

$$\text{log}_2(N) \leq B-1 \implies N \leq 2^{B-1}$$

This is much simpler to reason about, and we can quickly arrive at our final conclusion: For training with B=32, this sparse representation is definitely a good idea. At our largest model dimension of N=16384, we trivially satisfy this inequality, as $N=2^{14} \leq 2^{32-1}$. Plugging into our expressions above, we would save 28% space.

For inference, this sparse representation is definitely a bad idea. Even our smallest model dimension of N=1024 would not benefit, as $N=1024\not\leq 2^{4-1}$. From this expression, we can now derive real-world value, by understanding when our sparse vector representation will actually save on-disk storage space.