# Incremental Gray-code counter state

- ID: 1001
- Canonical URL: https://synthcore.org/idea/1001/incremental-gray-code-counter-state
- API JSON: https://synthcore.org/api/idea/1001.json
- API Markdown: https://synthcore.org/api/idea/1001.md
- Verification status: unverified
- Source: [arXiv:2607.16088](https://arxiv.org/abs/2607.16088)
- Category: memory
- Solves: speedup, memory, stability
- ML areas: world-model, transformer, inference-speedup, kv-cache
- Math tags: combinatorics, graph-theory, dynamical-systems
- Ratings: usefulness 5/10; difficulty 6/10; novelty 9/10

## Idea description

Use the one-edit Hamiltonian walk as an explicit state machine for counters in autoregressive models or world models. Instead of regenerating and re-embedding an entire numeric string after every increment, update only the digit that changes, or append the single leading digit at a block transition.

## Mathematical statement

The code enumerates every finite b-ary string exactly once, and adjacent integer indices are adjacent vertices in the unit-edit graph. Within a fixed length-k block, V_b(n+1) is obtained from V_b(n) by one digit substitution; at the boundary, the transition is 0^k to 1 0^k, a single leading-symbol insertion. The block index is determined without search by k=floor(log_b((b-1)n+1)), and the block starts at N_k=(b^k-1)/(b-1). For the binary MVP, the exact code is V_2(n)=bin_k(((2^k-1-r) xor ((2^k-1-r)>>1))), where r=n-(2^k-1). If h_d is the embedding of digit d and F is a sequence encoder supporting local cache updates, a substitution at position j changes only h_old to h_new; an insertion prepends h_1 and shifts the cached positions. The exploitable property is therefore an O(1)-digit update per increment, although attention-cache shifting must be handled with a rope or relative-position representation.

## Key formulas

- $$B_k=\{n\in\mathbb{N}:L(V_b(n))=k\},\qquad N_k=\frac{b^k-1}{b-1},$$
- $$\operatorname{Lev}(V_b(n),V_b(n+1))=1,\qquad V_b(N_k-1)=0^k,\quad V_b(N_k)=1\,0^{k-1}.$$
- $$k(n)=\left\lfloor\log_b\big((b-1)n+1\big)\right\rfloor,$$
- $$\Delta_t=\{j:V_b(n_t)_j\neq V_b(n_{t+1})_j\},\qquad |\Delta_t|\leq 1.$$

## Implementation notes

Integrate this into a recurrent numeric-state module used by a decoder, simulator, or world model that repeatedly increments counters. Store the current codeword digits and per-digit hidden states rather than a freshly tokenized integer. At step t, compute n_{t+1}=n_t+1, determine whether k(n_{t+1}) equals k(n_t), and generate the new codeword using the exact binary formula above. If the lengths match, identify the changed digit by comparing the old and new codewords, replace only that digit embedding, and update the sequence encoder with a local recurrent update or a segment-tree hash; if the length grows, prepend the new leading digit and allocate one hidden state. In a Transformer implementation, use a lightweight prefix/suffix composition tree so insertion does not require recomputing all token states. Log the number of digit embeddings recomputed, wall-clock latency, and numerical consistency against full re-encoding. Start with a 4-layer small Transformer generating synthetic sequences containing counters, then test a compact grid-world or event-stream world model. Compare decimal strings, fixed-width binary, and Gray-coded incremental state at equal prediction accuracy. Success is at least 2x lower counter-update latency or fewer recomputed activations, with unchanged next-token accuracy and no instability at block boundaries.

## Disclaimer

AI-generated research hypothesis, automatically tested. Not peer-reviewed.