Native binary embeddings experiment: curious about your thoughts

Research
1

I spent a few days testing a simple hypothesis: does training a binary embedding model natively (with a binary loss) produce better retrieval than just binarizing a float model post-hoc?

The setup is deliberately small : bert-mini (~11M params), CPU-only training on a Mac Mini M4 Pro, NLI 550k pairs, 3 epochs.

Key results on SciFact Recall@10:

  • Float32 384-dim: 0.313
  • Post-hoc binary 384-dim: 0.236 (−25%)
  • Native binary 2048-dim: 0.276 (−12% vs float, but +17% vs post-hoc)
  • Native binary 4096-dim: 0.296 (−5% vs float, +25% vs post-hoc)

And at 1M vectors with FAISS (AVX2+POPCNT on x86):

  • Native binary 2048-dim: 12× faster than float32, index 6× smaller

The three things that made the binary model actually converge:

  1. STE with {-1,+1} (not {0,1})
  2. tanh contrastive loss (aligns with the Hamming metric at eval)
  3. Differential learning rate — projection head at 50× the encoder LR

Models and code on GitHub / HuggingFace (korben99/bne-binary-2048).

Happy to hear if you’ve seen similar or contradictory results, especially at larger scales or with bigger backbones. Also curious whether the 2048-dim sweet spot holds with e.g. MiniLM.

2

Hmm…? I found quite a few things for now:

My read is: this looks less like an isolated “binary embedding trick” and more like a small, reproducible experiment in learned binary retrieval / compression-aware dense retrieval.

So I would answer your question roughly like this:

yes, I think this is a worthwhile direction, but I would be careful about what the current result proves. It is promising evidence that metric-aligned native binary training can recover quality compared with simple post-hoc binarization, but it is not yet a clean proof that native binary always beats post-hoc binary under the same bit, memory, or latency budget.

The interesting part, to me, is not only that Hamming search is fast. FAISS/vector-DB practice already makes that part plausible. The more interesting question is whether training the representation for the compressed/discrete search space gives a better quality-memory-latency tradeoff than current post-hoc binary/int8/PQ-style baselines.

Short version

I would frame this as:

a small SentenceTransformer-style experiment in learned binary retrieval.

The closest reference point I found is probably Binary Passage Retriever / BPR, because it uses learned binary codes for efficient candidate generation and continuous vectors for reranking:

https://aclanthology.org/2021.acl-short.123/

There is also a broader family of related work where the retriever and the compressed/discrete representation are trained together, rather than treating compression as a purely post-hoc step:

And for the practical baseline, I would compare against the current Sentence Transformers / HF-style quantization path, especially binary/int8 retrieval with rescoring, not only simple sign-threshold post-hoc binary:

https://www.sbert.net/examples/sentence_transformer/applications/embedding-quantization/README.html

https://huggingface.co/blog/embedding-quantization

My main caveat

The current result is promising, but the comparison mixes two things:

Setting What changes
post-hoc binary 384-dim simple binary conversion, 384 bits
native binary 2048-dim native binary training, but also much larger bit budget
native binary 4096-dim native binary training, and even larger bit budget

So the gain might come from the native binary objective, the larger bit budget, redundancy, the projection head, the tanh/contrastive surrogate, the {-1,+1} representation, or some mixture of these.

That is not a criticism. It just means the next clean experiment is probably an equal-bit / equal-memory ablation.

A minimal next comparison could be:

Bit budget Post-hoc binary Native binary
384 yes yes
768 yes yes
1024 yes yes
2048 yes yes
4096 yes yes

If native binary still wins at the same bit budget, that would make the claim much stronger.

Suggested next smallest experiment

If you want the smallest next step that would clarify the result a lot, I would do this:

  1. Train native binary at 384, 768, 1024, and 2048 bits.
  2. Create post-hoc binary baselines at the same dimensions.
  3. Evaluate SciFact with both Recall@10 and nDCG@10.
  4. Add one or two more BEIR/MTEB retrieval tasks, for example NFCorpus or FiQA.
  5. Add one rescoring setup: binary top-100 or top-200 → float/int8 rescore → final top-10.
  6. Inspect the binary codes directly: bit entropy, bit balance, dead bits, collision rate, and positive/negative Hamming-distance histograms.

The last point is important. A 2048-bit model may not actually be using 2048 useful bits. Some bits may be dead, redundant, or heavily biased.

Longer reasoning / related work map

1. Why this looks like learned binary retrieval, not just quantization

The simple view is:

train float embeddings → convert to binary → search with Hamming distance.

Your experiment is different because the model is being trained with the binary representation in mind. That puts it closer to learned hashing / compression-aware retrieval.

The strongest conceptual point is:

post-hoc compression loses quality because the encoder was not trained for that compressed/discrete search space. Native binary training tries to align the encoder/head/loss with the representation actually used at retrieval time.

This is similar in spirit to several retrieval-compression papers.

Binary Passage Retriever / BPR

BPR is the closest match I found:

Efficient Passage Retrieval with Hashing for Open-domain Question Answering - ACL Anthology

BPR integrates learning-to-hash into Dense Passage Retriever. It uses compact binary codes for candidate generation, then continuous vectors for reranking. That candidate-generation + reranking split seems especially relevant.

A useful practical lesson from BPR is that the strongest deployment path may not be pure binary-only retrieval. It may be:

  1. native binary code for cheap first-stage retrieval;
  2. retrieve more candidates than final top-k;
  3. rescore with float/int8/continuous vectors or a reranker.

That would make your method useful even if pure Hamming retrieval does not fully match the float model.

JPQ / RepCONC / MoPQ / Distill-VQ

These are not exactly binary embedding models, but they address the same bigger problem: dense retrieval is effective, but full dense indexes are expensive, and naive post-hoc compression can hurt retrieval.

JPQ:

[2108.00644] Jointly Optimizing Query Encoder and Product Quantization to Improve Retrieval Performance

JPQ jointly optimizes the query encoder and Product Quantization. The key idea is that separating encoding and compression can damage retrieval quality, so compression should be part of the retrieval objective.

RepCONC:

[2110.05789] Learning Discrete Representations via Constrained Clustering for Effective and Efficient Dense Retrieval

RepCONC jointly trains dual encoders and quantized/discrete document representations using constrained clustering.

MoPQ:

Matching-oriented Embedding Quantization For Ad-hoc Retrieval - ACL Anthology

MoPQ makes Product Quantization more matching-oriented for ad-hoc retrieval.

Distill-VQ:

[2204.00185] Distill-VQ: Learning Retrieval Oriented Vector Quantization By Distilling Knowledge from Dense Embeddings

Distill-VQ learns retrieval-oriented vector quantization by distilling from dense embeddings.

These references make your experiment easier to position:

native binary training is one form of compression-aware dense retrieval training.

2. Why simple post-hoc binary may be a weak baseline

The current Sentence Transformers binary quantization path is roughly:

normalize float32 embeddings → threshold at 0 → pack bits → search with Hamming distance.

Docs:

Embedding Quantization — Sentence Transformers documentation

That is a very useful baseline, but it is still post-hoc. The original embedding model was not necessarily trained to make every dimension useful after a hard sign/threshold operation.

This is where your result is interesting. If the model learns the projection head and loss with binary retrieval in mind, it may learn a better allocation of semantic information across bits.

There is also an older document-hashing lesson that BERT embeddings may contain information that is not necessarily organized for compact Hamming-space retrieval. So a learned binary head/objective can be meaningful, not just a cosmetic conversion step.

Example:

[2109.02867] Refining BERT Embeddings for Document Hashing via Mutual Information Maximization

3. Stronger practical baselines to include

I would not only compare against simple post-hoc binary.

I would include:

Baseline Why it matters
post-hoc binary only simple baseline
post-hoc binary + rescoring stronger practical baseline
post-hoc int8 / uint8 often a strong quality-memory compromise
native binary only your core method
native binary + rescoring likely practical deployment path
Matryoshka truncation + binary quantization relevant to the “sweet spot” question
BPR-style binary candidate generation + continuous reranking closest learned-binary retrieval reference
PQ / JPQ / RepCONC-style compressed retrieval broader compression-aware comparison

The HF blog is useful for the binary/int8 + rescoring pipeline:

Binary and Scalar Embedding Quantization for Significantly Faster & Cheaper Retrieval

Sentence Transformers quantization utility reference:

quantization — Sentence Transformers documentation

4. What I would measure

Retrieval metrics

I would keep SciFact, but add at least one or two more retrieval tasks.

Possible small set:

Task Why
SciFact current continuity
NFCorpus scientific/medical-ish retrieval, different distribution
FiQA finance QA retrieval
TREC-COVID biomedical retrieval
Quora paraphrase/duplicate retrieval
ArguAna argument retrieval, often behaves differently

Metrics:

  • Recall@10;
  • nDCG@10;
  • MRR if useful;
  • maybe Recall@100 if using binary first-stage retrieval + rescore.

Code diagnostics

Retrieval metrics alone do not tell you if the binary code is healthy.

I would inspect:

Diagnostic What it catches
bit balance bits stuck mostly on one side
bit entropy whether bits carry information
dead-bit ratio unused dimensions
collision rate too many texts mapping to same/similar codes
positive/negative Hamming-distance histograms whether relevant and non-relevant pairs separate
Hamming distance distribution whether code length is too short/long
correlation between float cosine and Hamming distance whether binary space preserves semantic neighborhoods
seed variance whether STE/tanh training is fragile

This is especially important for 2048/4096 bits. If many bits are dead or highly correlated, the effective code size may be much smaller than the nominal code size.

System metrics

I would separate three things:

  1. pure vector/index search time;
  2. retrieve + rescore time;
  3. full application/RAG latency.

FAISS binary search is a useful benchmark, but it is not the whole system.

FAISS binary indexes:

Binary Indexes · facebookresearch/faiss Wiki · GitHub

In a real deployment, latency can also depend on:

  • encoding time;
  • index build time;
  • memory residency vs disk;
  • DB overhead;
  • candidate count;
  • oversampling;
  • rescoring;
  • reranking;
  • batching;
  • p50/p95/p99 latency;
  • whether original float vectors are retained.

This distinction matters because some vector DBs use “binary quantization” as an auxiliary search representation while still storing original vectors for rescoring. That is different from a model that natively emits only packed binary codes.

5. About the 2048-bit sweet spot

I would phrase this carefully.

I would not say:

2048 bits is the sweet spot.

I would say:

2048 bits looks like a good engineering point in this specific setup: small BERT backbone, this training data, this loss, SciFact Recall@10, and FAISS binary retrieval.

The real sweet spot probably depends on:

  • backbone quality;
  • task/domain;
  • bit entropy;
  • dead/redundant bits;
  • whether rescoring is used;
  • whether the index is exact or ANN;
  • CPU cache behavior;
  • candidate count;
  • memory budget;
  • whether the model is trained Matryoshka-style.

MiniLM is definitely worth trying, but I would ask a slightly different question:

what is the lowest bit budget where MiniLM-native-binary still beats a strong post-hoc binary/int8 baseline under the same memory or latency budget?

That seems more actionable than only checking whether 2048 still wins.

6. Product/API-side context

This direction also seems aligned with where embedding APIs and search infrastructure are going.

Cohere supports float/int8/uint8/binary/ubinary embedding output types:

Cohere int8 & binary Embeddings - Scale Your Vector Database to Large Datasets

Introduction to Embeddings at Cohere | Cohere

Voyage also documents binary/ubinary output:

Text Embeddings

Jina/Elastic are also moving in the direction of embeddings and retrieval systems that are robust to binary quantization:

jina-embeddings-v5-text: Compact multilingual embedding models - Elasticsearch Labs

I would treat these as practical signals that binary/int8 outputs matter, not as proof of your training recipe. The open experiment is still useful because the commercial training details are usually not transparent.

7. Vector DB / infrastructure notes

Different systems mean different things by “binary”.

Examples:

Possible sources of confusion:

Term Possible meaning
binary embedding model emits binary or sign-like vector
post-hoc binary quantization float vector is thresholded after encoding
binary vector DB field database stores packed bits directly
binary quantization index compressed auxiliary index, possibly with original vectors retained
binary retrieve + rescore binary search is only first stage
{-1,+1} code convenient for training / dot-like similarity
{0,1} packed code convenient for Hamming search / storage

This is why I would explicitly state:

  • what is stored;
  • what is searched;
  • what query representation is used;
  • what distance metric is used;
  • whether original float vectors are retained;
  • whether rescoring is used.

8. My current confidence table

Claim My current confidence
Hamming/binary retrieval can be much faster on CPU high
native binary training is a promising direction medium-high
native binary beats simple 384-bit post-hoc binary in your current setup supported by your reported result
native binary generally beats post-hoc binary at equal bit budget not yet shown
2048 bits is a general sweet spot not yet shown
pure binary retrieval is the best deployment path unclear; binary + rescore may be stronger
the experiment is worth continuing yes

Final practical suggestion

If I had to suggest one compact next milestone, it would be:

  1. equal-bit native vs post-hoc comparison at 384/768/1024/2048;
  2. one stronger baseline: Sentence Transformers binary/int8 quantization with rescoring;
  3. one extra retrieval task beyond SciFact;
  4. bit diagnostics: entropy, balance, dead bits, collision rate, and Hamming-distance histograms;
  5. report pure binary retrieval separately from binary + rescore and end-to-end latency.

That would make the result much easier for other people to interpret and reproduce.

Overall, I think this is worth continuing. The strongest version of the claim would not be “binary is fast” or “native binary beats post-hoc once.” It would be something like:

metric-aligned native binary training can produce better first-stage retrieval codes than ordinary post-hoc binarization under a fixed memory/latency budget, and it remains useful when compared against current binary/int8 quantization + rescoring baselines.

That would be a genuinely interesting result.

Edit after clarification below: agreed, my equal-bit framing above is better viewed as a separate ablation question, not the central framing of this experiment.

The main question is more like a precision–dimension trade-off: can we spend more binary dimensions while using far fewer bits than float32, and still get useful CPU-only retrieval?

So post-hoc binary384 is not really the middle point; it is the extreme-compression point. Native binary2048 is a different engineering point: much smaller than float32 384, but with much more capacity than 384-bit post-hoc binary.

I would still keep equal-bit native-vs-post-hoc as an interesting mechanism study, but the more directly useful next result is probably a Pareto/frontier table: float32 384, Q4 float384, int8 float384, post-hoc binary384, and native binary512/1024/2048/4096, with bits/vector, bytes/vector, retrieval quality, index size, and CPU latency.

3

I have been in the “Binary Game” since the mid 1990s.

The truth about information representation on a computer is that everything is binary.

To borrow from Hamlet, Act 1, Scene 5:

“There are more things in heaven and earth, Horatio,
Than are dreamt of in your philosophy.”

We can think in terms of Binary Space.

It seems limiting to be reduced to an alphabet {0,1}, but once we live there for a while, we begin to learn something about the nature of information itself.

So my curious peer…

Are you asking about representing information in binary space?

Or are you asking what kinds of structure, relationships, and meaning can emerge when information is allowed to live there?

4

@Ernst03 You have a way with words my friend!

I would love to hear the answer to both questions, something tells me I will find it both enlightening and entertaining.

5

Thanks a lot for your time and your responses, really helpful for someone still learning.

One point I want to clarify on the bit budget comparison, because I think it reframes things a bit:

  • Float 384-dim = 384 × 32 = 12 288 bits
  • Post-hoc binary 384-dim = 384 bits
  • Native binary 2048-dim = 2 048 bits

So post-hoc binary isn’t a middle ground — it’s an extreme compression that shows clearly in the results (Recall@10 drops from 0.313 → 0.236, −25%). Native binary 2048 sits between the two: 6× fewer bits than float, but 5× more than post-hoc, and it recovers meaningful recall (0.276) while being 12× faster on CPU.

The goal of the experiment isn’t really to prove native binary beats post-hoc at equal bit budget. It’s more basic than that: can you trade weight precision for more dimensions and still get useful retrieval on CPU-only hardware? The results suggest yes, and 2048-dim seems to be a reasonable sweet spot for that trade-off.

Your suggestions on the dimension sweep (512, 1024) and bit diagnostics are genuinely useful next steps — I’ll add them, and I will also add the Q4 quantization on float 384 to compare.

The equal-bit ablation is also interesting, but it’s a different research question than what I was trying to answer here.

Appreciate the BPR/JPQ/RepCONC references, I wasn’t familiar with all of them.

I’ll keep you posted.

6

Well, with respect to @korben99, I’m more interested in understanding the question than claiming to have an answer.

After reading the discussion, my current understanding is that the underlying question is less about binary itself and more about preserving relationships.

The goal seems to be something like:

“How can we represent relationships between objects in a much smaller space while preserving the geometry that makes retrieval useful?”

In other words, the exact floating-point values are not the treasure. The treasure is the relative organization: who is near whom, who is far away, and whether that neighborhood structure survives the transformation.

Am I understanding the problem correctly?

I’ve spent many years thinking about binary representations from a dynamical systems perspective, so before offering ideas I’d rather make sure I understand the problem.

My current impression is that this is really about relating objects. “Cat” should remain close to “kitten,” while “truck” remains much farther away, regardless of how compact the representation becomes.

From my own experience working with binary representations, there usually isn’t much “wiggle room” at the binary level. That is exactly why this discussion caught my attention.

So, for now, I’m mostly listening and trying to understand the geometry of the problem. If I eventually have something useful to contribute, I’d like it to be grounded in the actual question rather than in my assumptions.

I let my Tool-Friend organize my thoughts before I’ve had my second cup of coffee. :grinning_face_with_smiling_eyes:

-Ernst

p.S. @korben99 Congratulations on your first post/thread!

7

Thank you Ernst for taking the time to respond and your kind words on my first pub.

You get the geometry point: it’s about preserving who’s-near-whom under compression, not the float values themselves. The constraint that drives everything is the hardware: I wanted a solution where the CPU does the work cheaply (Hamming → POPCNT, no GPU). The goal was never maximum quality — it’s enough quality for the least possible compute. like BitNet project of Microsoft, but for RAG.

I just closed the comparison I was missing, and it came out clearer than I expected. The real efficiency competitor isn’t actually float32 (well it still is of course), it’s int8 scalar quantization (FAISS IndexScalarQuantizer, exact search). Here’s the results at 1M vectors (I have also tried different seeds to takle statistical deviations):

  • float32: 3815 ms, 1536 MB
  • int8 (SQ8): 4719 ms, 384 MB — 4× smaller, but actually slower than float (it dequantizes each vector during search)
  • binary 1024: 102 ms, 128 MB — ~24× faster than float, ~37× faster than int8, and 3× smaller than int8

So binary beats the compact baseline on both axes at once — speed and memory — in exact search. It loses a few points of Recall (0.29 vs 0.31), and that’s the whole trade I’m making: a few % of quality for ~24× speed and 12× memory on CPU. For a lot of retrieval workloads, “good enough and 24× cheaper” wins over “best but needs a GPU”.

The one honest caveat: binary uses exact Hamming, int8 uses exact dot-product with dequantization — same exactness, different metrics, so I’m comparing latency/footprint, not metric-for-metric.

The part still closest to your “no wiggle room” intuition: doubling 1024 → 2048 bits buys almost nothing (≈+0.016 Recall, p=0.16), and the bit diagnostics show why: no dead bits, but some pairs near-perfectly correlated (|r| max ≈ 0.94). The code seems to saturate its useful structure and then duplicate it. Maybe because of the mini-bert projection head (256dim) ?

That’s exactly where the dynamical-systems prespective can help: From your opinion, is there a principled reason binary codes hit a structural ceiling and start copying bits rather than filling the space?

8

Thank you for the thoughtful reply. This is exactly the sort of discussion I was hoping for.

I should begin with a disclaimer. I am a wannabe cyberneticist, not an expert in BERT or modern embedding architectures. My goal is to be around the action, learn from people working in the field, and hopefully contribute a useful perspective from finite dynamical systems. This feels like one of those moments.

The part that immediately caught my attention wasn’t the correlated bits themselves. A correlated bit is an observation. What interests me is that the system repeatedly generates correlated bits as capacity increases. To me, the system appears to have entered a distinct behavior.

From my perspective, that raises a different kind of question. Rather than asking only why are these two bits correlated?, I find myself asking what behavior is the system exhibiting?

My first intuition is that some sort of finite dynamic may be involved. I don’t know enough about your implementation to claim that it is literally cycling, but it reminds me of a system that has reached an attractor where additional capacity reinforces existing structure instead of discovering genuinely new distinctions.

As I was reading your explanation this morning, I realized I was asking very basic questions myself. What exactly is Mini-BERT? What does the projection head do? Is the projection head the place where the binary codes are actually created?

If I understand correctly, the projection head is a learned layer whose job is to transform the Mini-BERT embedding into binary codes rather than simply applying a threshold. If that’s true, then it seems plausible that once the projection has learned nearly all of the useful distinctions available in the original embedding, additional output bits might naturally begin reinforcing those same distinctions instead of creating independent ones.

In other words, perhaps the duplication isn’t a bug at all. Perhaps it is simply the optimizer deciding that repeating an already useful distinction is more valuable than inventing a weak one.

Am I qualified to say that is what your system is doing? No.

Do I suspect that what you’re observing is a systems phenomenon rather than an isolated implementation detail? Yes.

My intuition is that the interesting question isn’t the duplicated bits themselves. It’s why the system transitions into that behavior.

I could be completely wrong about the mechanism, but the behavior itself caught my attention.

I can say that behaviors in system constructs happen all the time. They usually become visible to me when I am trying to make my dog do the trick I want, and the Universe smiles and says, “Not so fast, my clever boy.” That’s usually the moment I realize I’m no longer studying my design—I’m studying the behavior of the system I created.

That is the best contribution I can make with the understanding I have today.

— Ernst

9

I see what you mean, interesting rephrasing.

Shifting from “why are these two bits correlated” to “why does the system enter this regime as capacity grows” is an interesting move, it makes the redundancy look like a strategy rather than a defect.

Your projection-head intuition lines up well with the architecture. Mini-BERT produces a fixed 256-dim pooled embedding; the projection head is the learned layer that maps that into the D-dim binary code (via tanh + straight-through sign, not a plain threshold). So there’s a hard ceiling upstream: once the head has extracted most of the distinctions actually present in that 256-dim source, extra output bits have no new signal to encode. The optimizer then reinforces an existing useful distinction instead of inventing a weak one, which is exactly the duplication I’m seeing. So I think you’re right that it’s a systems-level phenomenon, not an implementation quirk.

We have to be carefull though, the projection is feedforward, there’s no recurrence, so for now I read “attractor” as a useful analogy for information saturation rather than a literal cycle. But the intuition makes a falsifiable prediction I can test: if the ceiling is set by the source embedding, then a richer backbone (MiniLM, bert-base) should push it back, and |r| max should drop at the same output dimension. If a bigger backbone doesn’t reduce the correlation, then the bottleneck is in the binary head itself, and your “the system settles into a preferred structure” reading gets stronger. Either way the experiment tells us something.

That’s the next thing I’ll run, when I have time.

I really appreciate your view on the behavior rather than the symptom.

10

Oh, the fun of hour after hour, day after day, and year after year of it all.

And yet, if it calls to us, can we really resist the song of that siren?

Experimentation. Observation. Modification.

Wash. Rinse. Repeat.

Good luck with the next experiment. I’ll be interested to see which hypothesis survives.
— Ernst

11

I know this doesn’t quite fit in with what you are doing. But non the less, I found it to be rather interesting.

I don’t know if you have ever seen OEIS. But it is basically an online database of lists of integers that get submitted, This particular one is to do with XOR.

You have a sequence of nodes in a closed loop, with numbers at the vertices, say A,B,C that form the loop AB,BC,CA (let’s called this layer 0). Perform XOR (^) on each connection so A XOR B, B XOR C, C XOR A results in a new layer (layer 1): [‘A^B’, ‘B^C’, ‘A^C’]. If you then repeat this and use XOR on layer 1 you get [‘A^B^B^C’, ‘B^C^A^C’, ‘A^C^A^B’] which simplifies to [‘A^C’, ‘B^A’, ‘C^B’] which is the same as layer 1, but just a different order. So a loop of 3 number (3 vertices), a triangle, has two unique layers, the original [A, B, C] and layer 1 [‘A^B’, ‘B^C’, ‘A^C’]. If you try this for closed loops with 4 vertices or 5, etc you get a different number of unique layers (as shown in the sequence) before the layers start repeating. Interesting they repeat in a cyclic fashion. For example for 5 vertices there are 4 unique layers (layers 0 to 3). Layer 4 is a repeat of layer 1 (in a different order) and layer 5 is repeat of layer 2, etc.

Table of n, a(n) for n=1..59.

FORMULA

a(n) = A006519(n) + A085587(n).

PROG

(Python)

# Simulation

def next_layer(layer):

n = len(layer)

return tuple(

    layer\[i\] ^ layer\[(i + 1) % n\]

    for i in range(n)

)

def canonical_rotation(seq):

n = len(seq)

return min(

    seq\[i:\] + seq\[:i\]

    for i in range(n)

)

def a(n, max_layers=None):

\# Each vertex is represented as one bit.

layer = tuple(1 << i for i in range(n))

seen = set()

if max_layers is None:

    \# Safe upper bound for small/medium n.

    \# The state space is finite, so the process must eventually cycle.

    max_layers = (1 << n) + 1

for \_ in range(max_layers):

    key = canonical_rotation(layer)

    if key in seen:

        return len(seen)

    seen.add(key)

    layer = next_layer(layer)

raise RuntimeError("Cycle not found. Increase max_layers.")

print([a(n) for n in range(1, 47)])

Also in the work that I am currently doing I play around with Vázsonyi’s Conjecture and Hamming codes. The things I play aournd with and find the most interesting at the moment are:

  1. Kruskal, J. B., Well-Quasi-Ordering, the Tree Theorem, and Vázsonyi’s Conjecture, Trans. AMS 95, 1960.
  2. Friedman, H. M., FOM archive postings on Embedded Maximal Cliques (2009–2018), Foundations of Mathematics list.
  3. Friedman, H. M., Boolean Relation Theory and Incompleteness, manuscript, 2014 (revised).
  4. Friedman, H. M., Tangible Incompleteness, manuscript series, 2014–2024.
  5. Harrington, L., Conservation theorem for WKL₀ over PRA, unpublished communication; cited in Simpson, Subsystems of Second Order Arithmetic.

Hamming Distance