△ Mechanism confirmed, baseline not beaten 2026

Local separating-code positional encodings

Implementation & benchmark of arXiv:2608.04608 — Information and Locality in Cayley Graphs

Usefulness7/10

Difficulty5/10

Novelty7/10

Architecture Accuracy Sample efficiency Scalability Graph nn Embedding Attention Combinatorics Graph theory Information theory

Source paper: Information and Locality in Cayley Graphs arXiv:2608.04608 ⓘ · analyzed Aug 31, 2026

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

Idea description

Replace globally unique node IDs with a small discrete alphabet labeling whose ordered local neighborhood words uniquely identify nodes. Feed these separating words to a GNN or graph transformer as positional features, preserving node distinguishability with bounded local receptive fields.

Formulas

$$W_{f,Y}(g)=\bigl(f(gy_{1}),\ldots,f(gy_{k})\bigr).$$

$$(f,Y)\text{ is separating}\quad\Longleftrightarrow\quad W_{f,Y}(g)\neq W_{f,Y}(h)\ \text{for all }g\neq h.$$$$

$$\mathcal{L}_{\mathrm{sep}}(f,Y)=\sum_{(u,v)\in\mathcal{P}}\exp\!\left(-\frac{\|\phi(W_{f,Y}(u))-\phi(W_{f,Y}(v))\|_2^2}{\tau}\right),$$

$$\operatorname{csep}_{q}(G,S)=\min\{|Y|:\ Y\text{ is a connected Cayley window containing }\{1\}\cup S\text{ and }(f,Y)\text{ is separating for some }f:G\to[q]\}.$$

Mathematical statement

Let G be a finite group, let [q] be an alphabet of q symbols, let f:G o[q] be a labeling, and let Y=(y_1,\ldots,y_k) be an ordered pattern of distinct group elements. The translated observation is W_{f,Y}(g)=(f(gy_1),\ldots,f(gy_k)). The pair (f,Y) is separating when W_{f,Y}(g)
e W_{f,Y}(h) for every distinct g,h\in G. The connected parameter restricts Y to a connected Cayley-graph window containing the identity and generators. For a general graph, replace group offsets gy_i by deterministic ordered walk endpoints or canonical neighbor slots. The transferable property is injectivity of a finite local code, which gives an explicit collision criterion for positional representations.

Implementation notes

Integrate this at the input of a message-passing GNN or graph transformer as a local positional-code module. Choose an ordered connected window Y=(y_1,...,y_k), with y_1 equal to the center node and the remaining offsets defined by graph distances, generator directions, or fixed canonical neighbor slots. Maintain label logits A[v,i,c] for the symbol at local position i of node v, where c is one of q symbols. During training, convert logits to soft labels with Gumbel-Softmax; during evaluation, use argmax labels. For each node v, gather the ordered code C_v=[one_hot(f(v\cdot y_1)),...,one_hot(f(v\cdot y_k))], flatten it, and map it through a small MLP before adding it to the node embedding or concatenating it to transformer query and key inputs. Sample node pairs (u,v), compute d_uv=||C_u-C_v||_2^2, and optimize the collision surrogate L_sep=sum exp(-d_uv/tau), where P is the sampled pair set and tau is annealed from a high to low temperature. Add a hard collision metric by hashing the discrete code words and reporting the fraction of duplicate hashes. The paper’s exact mathematical target is injectivity of v\mapsto W(v); the soft exponential loss and Gumbel relaxation are engineering adaptations. Test first on 2D grid graphs, cycles, and small Cayley-like graphs, comparing no positional encoding, random IDs, Laplacian eigenvectors, and separating codes. Measure node-classification accuracy, graph isomorphism discrimination, collision rate, and the number of GNN layers required to reach baseline accuracy. Success is higher accuracy at fixed depth or zero code collisions with q^k much smaller than the number of nodes.

Verification

Mechanism confirmed, baseline not beaten

Stage 1 · Toy mechanism gate: Passed ✓

Stage 2 · Mechanism transferred to benchmark: Confirmed ✓

Stage 2 · Practical benchmark result: No measurable effect

Methodology: 8 paired seeds, permutation test (p<0.05) against a learning-rate-tuned baseline. How verification works

Stage 1 — Mechanism check agent confidence 8/10

Built and ran a cyclic-Cayley local separating-code verifier plus a tiny downstream linear readout. The mechanism manifested: random collision pair probability followed q^-k, expected collision counts followed n(n-1)/(2q^k), and optimized codes became separating at k=ceil(log_q n) in all tested settings while remaining impossible below the code-capacity bound. The positional code improved the toy held-out readout over a constant baseline, but this is not evidence of broad GNN accuracy or cross-graph generalization.

Agent confidence: 8/10

Baseline: Random/constant code: collision probability followed q^-k; constant-label downstream accuracy was 0.3125 for q=4,n=32.
Idea: Optimized q-ary local codes achieved zero collision pairs for q=4,n=32,k=3/4; for q=2,n=16 and n=24, separation first appeared at k=4 and k=5 respectively, matching ceil(log_q n). Code linear-readout accuracy was 0.625 versus 0.3125 constant baseline.

Limitations: Tested only cyclic graphs with overlapping windows and a small synthetic readout, not 2D grids, general graphs, trained message-passing GNNs, Gumbel-softmax optimization, Laplacian/random-ID baselines, runtime/FLOPs, or cross-graph transfer.

How to run: python3 verify_local_codes.py && /home/maxwelhelp/main/bin/python3 toy_classifier.py

Stage 2 — Benchmark vs. tuned baseline (arXiv:2608.04608) Sep 2, 2026

Ahead of the baseline (−0.4%) but not statistically significant (p=0.8074, wins 5 / 8 paired seeds).

Benchmark: Sequence modeling
Model: transformer_tiny
Paired seeds: 8
Baseline mean: 0.4599
Idea mean: 0.458
Effect (Δ): -0.0019 (−0.4%; negative = idea better)
Wins: 5 / 8 paired seeds
p-value: 0.8074 (permutation test, 20 000 shuffles)
Smallest detectable effect: ±4.0%
Mechanism: Confirmed ✓
Practical effect: No effect
Baseline tuning: swept over 3 configs

Limitations:

Only the built-in sequence track and transformer_tiny model were tested; no grid/general-graph GNN, Laplacian/random-ID baselines, Gumbel-softmax training, cross-graph transfer, runtime/FLOPs, or larger datasets were evaluated.

How to run: python3 bench_local_codes.py

Verdict computed by deterministic test code from paired-seed statistics — not by the language model.

Stage 2 — Benchmark Aug 31, 2026 latest Failed ✗

Agent confidence: 9/10

Implemented local separating-code positional features for the matched sequence/transformer_tiny benchmark and ran the full 8-seed paired protocol with a shared three-value learning-rate sweep. The idea achieved MSE 0.458007 versus baseline 0.459898, a small delta of -0.001891, but the permutation p-value was 0.8074, so there was no significant or measurable win. The mechanism signature confirmed zero code collisions and larger observed positional pair distance, but that did not improve task performance.

Baseline: Best lr=0.001; 8-seed test MSE mean=0.4598984905, std=0.0545394236.
Idea: Best lr=0.001; 8-seed test MSE mean=0.4580072127, std=0.0545826327; paired delta=-0.0018912777; 5/8 wins; permutation p=0.8074; verdict=no measurable effect.

Benchmark result