Gray-coded numeric embeddings
Implementation & benchmark of arXiv:2607.16088 — Variable-length Gray codes for the Natural Numbers
Source paper: Variable-length Gray codes for the Natural Numbers arXiv:2607.16088 ⓘ · analyzed Aug 30, 2026
AI-generated research hypothesis, automatically tested. Not peer-reviewed.
Idea description
Replace a learned embedding for each integer with a compositional embedding of its variable-length Gray codeword. Add an auxiliary constraint that numerically adjacent values have nearby representations, while preserving the ordinary task loss so that the model can learn when numerical adjacency matters.
Formulas
Mathematical statement
The code partitions the natural numbers into blocks B_k={n:L(V_b(n))=k}, with block start N_k=sum_{i=0}^{k-1}b^i=(b^k-1)/(b-1). Its length theorem is L(V_b(n))=floor(log_b((b-1)n+1)), so the representation is variable-length and monotone. Consecutive codewords have Levenshtein distance one: within a block they differ by one digit substitution, and at a block boundary 0^k changes to 1 0^k by one leading-symbol insertion. For a fully specified binary implementation, let k=floor(log_2(n+1)), r=n-(2^k-1), and g(x)=x xor floor(x/2) be the reflected binary Gray map. Then V_2(n) is the k-bit representation of g(2^k-1-r), with V_2(0) the empty string. This gives V_2(2^k-1)=1 0^{k-1} and V_2(2^{k+1}-2)=0^k. The proposed neural representation maps each digit d to an embedding e_d, applies a small digit sequence encoder f, and regularizes ||f(V(n+1))-f(V(n))|| so that the mathematical one-edit adjacency becomes a learned smoothness prior.
Implementation notes
Integrate this at the numeric-feature embedding or tokenizer boundary. For every integer-valued field n, first compute its binary codeword using k=floor(log2(n+1)), r=n-(2^k-1), q=(2^k-1)-r, and codeword bits equal to q xor (q>>1), padded to exactly k bits; represent n=0 by an empty sequence plus a dedicated empty-vector marker. Feed digit embeddings through a two-layer Transformer, GRU, or mean-pooling encoder f, and project the resulting vector to the model dimension. During training, retain the original supervised or language-model loss and sample integer pairs (n,n+1), plus harder pairs at distance d. Apply the displayed adjacent-pair penalty only to valid non-overflowing values; optionally use a hinge version max(0, ||f(V(n))-f(V(m))||-c|n-m|). The code itself is computed exactly; no Gray-code statistics need estimating. Measure sequence length, embedding-table size, and the correlation between embedding distance and |n-m|. The first experiment should use a small decoder Transformer on synthetic arithmetic sequences and a tabular regression/classification benchmark containing counters and indices. Compare one-hot integer embeddings, decimal digit embeddings, and Gray-coded embeddings at equal parameter count. Success is lower validation error and better extrapolation to unseen larger integers, with no increase in training FLOPs; a useful signal is smooth prediction of n+1 from n and reduced sample count to learn monotone arithmetic relations.
Verification
This idea has not been verified yet.
Verification happens in two stages: Stage 1 — a mechanism check on a toy system confirms the claimed mathematical phenomenon reproduces; Stage 2 — a benchmark implements the idea on a real (small) neural network task and compares it against a tuned baseline over 8 paired seeds with a permutation test.
Artifacts
Artifacts unavailable.