google-deepmind / google-deepmind/alphatensor

Certified 178-XOR implementation of the released 4×4×4 rank-47 F₂ factorization

Open
#21 0 comments 0 reactions 0 assignees View on GitHub
Dominant language
Python
Stars
2.9k
Forks
258
PR merge metrics
No merged PRs in 30d

Description

Hello,

I reproduced the released rank-47 factorization for 4×4 matrix multiplication over F₂ and synthesized an exact binary linear circuit for its two encoders and decoder.

### Result

Using the factorization contained in the public AlphaTensor data:

- left encoder `U`: **46 XORs**
- right encoder `V`: **46 XORs**
- decoder `Wᵀ`: **86 XORs**
- bilinear products: **47 ANDs**
- total linear cost: **178 XORs**

The verifier checks coefficient-by-coefficient that the resulting circuit computes the full 4×4×4 matrix-multiplication tensor over F₂.

### Additional structural check

For the fixed 47-dimensional span of bilinear encoders, I enumerated all rank-one points in that span:

- the span contains exactly **48** rank-one points;
- the 47 released points plus one additional global point;
- none of the `C(48,46) = 1128` subsets of size 46 spans the target-slice space.

Therefore, a reduction from 47 to 46 products cannot be obtained merely by replacing products inside the same bilinear encoder span and redesigning the decoder. This does **not** rule out a completely different rank-46 factorization.

### Questions

Could you please confirm:

1. whether the 178-XOR count matches the cost model used in your benchmarking pipeline;
2. whether an equal or lower XOR circuit for this released factorization is already known internally or publicly;
3. whether you would be interested in a pull request adding the circuit and verifier to the repository?

I am not claiming that 178 is globally optimal among all implementations or all rank-47 factorizations. The claim is only that this is an exact, reproducible implementation of the released factorization.

### Reproducibility package

Please attach:

[alphatensor_rank47_add178_submission.zip](https://github.com/user-attachments/files/30410086/alphatensor_rank47_add178_submission.zip)

The package contains:

- the released factorization in JSON form;
- the 178-XOR circuit;
- an exact tensor verifier;
- the fixed-span rank-one enumeration certificate;
- instructions for reproducing both checks.

Thank you for making the AlphaTensor factorizations publicly available.

Contributor guide

Open the contributing guide

Research direction

Start with the attached reproducibility package and its instructions, then inspect the released factorization JSON, 178-XOR circuit, exact tensor verifier, and fixed-span rank-one certificate. Run both checks to understand the reported results; completion would require agreement on the benchmarking cost model and a defined repository change for adding the circuit and verifier.

Written by the indexing model from the issue text.

Assessment

Tech stack
python
Domain
tooling
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Quiet
Clarity
Needs clarification
Newbie friendliness
30/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.