google-deepmind / google-deepmind/alphatensor
Certified 178-XOR implementation of the released 4×4×4 rank-47 F₂ factorization
- 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
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