Problems
Loading...
Step 1 of 7
N-gram Hashing
Medium

Qwen4-Max places one hashed N-gram Embedding layer at depth two. Before that layer can read its tables, every position has to be turned into the table rows addressed by the suffix n-grams that end at that position. This problem computes those rows with the multiplicative-XOR hash of the Engram demo code.

For a token sequence xx, a position tt and an offset kk, let xt−kx_{t-k} be the token kk positions back, or the pad id pp when t−k<0t-k<0. For each order nn from 2 to the maximum order NN, the mix of the suffix n-gram is

mix⁡t,n=(xtm0)⊕(xt−1m1)⊕⋯⊕(xt−n+1mn−1)\operatorname{mix}_{t,n}=(x_t m_0)\oplus(x_{t-1}m_1)\oplus\cdots\oplus(x_{t-n+1}m_{n-1})

where mkm_k is the odd multiplier for offset kk and ⊕\oplus is bitwise XOR on 64-bit integers. Head jj of order nn owns a table of prime size Mn,jM_{n,j} and addresses the row

zt,n,j=mix⁡t,n mod Mn,jz_{t,n,j}=\operatorname{mix}_{t,n}\bmod M_{n,j}

The token ids have shape (B,T)(B, T), the multipliers have shape (N,)(N,), and the prime sizes hold one list per order from 2 to NN with one prime per head. Raw token ids are hashed directly, with no tokenizer compression.

Return an int64 tensor of shape (B,T,H)(B, T, H), where HH is the total number of heads, with the heads ordered by n-gram order ascending and then by head index within each order.

Loading visualization...

Examples

Input: token_ids = [[11, 4, 11, 4]], pad_id = 2, multipliers = [3, 5, 7], prime_sizes = [[7], [11]]

Output: tensor([[[1, 4], [3, 9], [4, 10], [3, 6]]])

Explanation: At position 0 the bigram mixes 11 times 3 with the pad id 2 times 5, so 33 XOR 10 = 43 and 43 mod 7 = 1. XOR with the pad id times 7 gives 37 for the trigram, and 37 mod 11 = 4. Positions 1 and 3 both end in the bigram (11, 4), so both get bigram row 3.

Input: token_ids = [[17, 23, 17, 23, 5], [9, 9, 9, 40, 2]], pad_id = 1, multipliers = [101, 203, 307], prime_sizes = [[31, 37], [41, 43]]

Output: int64 tensor of shape (2, 5, 4)

Input: token_ids = [[120, 7, 33, 120, 7, 33]], pad_id = 3, multipliers = [1001, 2003, 3005, 4007], prime_sizes = [[53, 59], [61, 67], [71, 73]]

Output: int64 tensor of shape (1, 6, 6)

Hint 1

torch.nn.functional.pad\texttt{torch.nn.functional.pad} with a value argument prepends the pad id along the sequence axis.

Hint 2

torch.bitwise_xor\texttt{torch.bitwise\_xor} combines int64 tensors elementwise, and each order can extend the mix of the order below it.

Hint 3

torch.remainder\texttt{torch.remainder} reduces by a Python integer, and torch.stack(..., dim=-1)\texttt{torch.stack(..., dim=-1)} builds the head axis.

Requirements

  • Return a PyTorch tensor of dtype int64 with shape (batch, sequence length, total heads).
  • Positions before the sequence start use the pad id, and no position reads a later token.
  • Combine the scaled tokens of each n-gram with bitwise XOR before reducing by each head's prime.
  • Order the heads by n-gram order first and by head index second.
  • Leave every input unchanged.

Constraints

  • The token ids form an int64 tensor of shape (B, T) with B and T at least 1, and every id is non-negative.
  • The pad id is a non-negative integer.
  • The multipliers form an int64 tensor of N odd positive integers, where N is between 2 and 5 and equals the number of orders plus one.
  • The prime sizes hold N minus 1 lists, one per order from 2 to N, every order has the same number of heads, and all primes are distinct.
  • Every product of a token or the pad id with a multiplier fits in a signed 64-bit integer.