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 x, a position t and an offset k, let xt−k be the token k positions back, or the pad id p when t−k<0. For each order n from 2 to the maximum order N, the mix of the suffix n-gram is
mixt,n=(xtm0)⊕(xt−1m1)⊕⋯⊕(xt−n+1mn−1)where mk is the odd multiplier for offset k and ⊕ is bitwise XOR on 64-bit integers. Head j of order n owns a table of prime size Mn,j and addresses the row
zt,n,j=mixt,nmodMn,jThe token ids have shape (B,T), the multipliers have shape (N,), and the prime sizes hold one list per order from 2 to N with one prime per head. Raw token ids are hashed directly, with no tokenizer compression.
Return an int64 tensor of shape (B,T,H), where H is the total number of heads, with the heads ordered by n-gram order ascending and then by head index within each order.
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 with a value argument prepends the pad id along the sequence axis.
Hint 2
torch.bitwise_xor combines int64 tensors elementwise, and each order can extend the mix of the order below it.
Hint 3
torch.remainder reduces by a Python integer, and 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.
All steps in Qwen4-Max
Accepts: array
Accepts: number
Accepts: array
Accepts: array
N-gram Hashing
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 x, a position t and an offset k, let xt−k be the token k positions back, or the pad id p when t−k<0. For each order n from 2 to the maximum order N, the mix of the suffix n-gram is
mixt,n=(xtm0)⊕(xt−1m1)⊕⋯⊕(xt−n+1mn−1)where mk is the odd multiplier for offset k and ⊕ is bitwise XOR on 64-bit integers. Head j of order n owns a table of prime size Mn,j and addresses the row
zt,n,j=mixt,nmodMn,jThe token ids have shape (B,T), the multipliers have shape (N,), and the prime sizes hold one list per order from 2 to N with one prime per head. Raw token ids are hashed directly, with no tokenizer compression.
Return an int64 tensor of shape (B,T,H), where H is the total number of heads, with the heads ordered by n-gram order ascending and then by head index within each order.
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 with a value argument prepends the pad id along the sequence axis.
Hint 2
torch.bitwise_xor combines int64 tensors elementwise, and each order can extend the mix of the order below it.
Hint 3
torch.remainder reduces by a Python integer, and 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.
All steps in Qwen4-Max
Accepts: array
Accepts: number
Accepts: array
Accepts: array