The k-parity of a bit string is the sum mod 2 of its
k secret bits.
One instance: m = 18 strings of n = 32 bits
(three shown), each labeled with the parity of the k = 5 secret
positions (highlighted). Only the strings and parities are given to the
solver.
Task: given the m strings and their parities, figure out
the locations of the secret bits. Every instance: n = 32 bits,
k = 5 secret positions, m = 18 strings.
We are looking for the lowest-energy solutions at 20%, 40%, 60%, 80% and
100% accuracy, measured on the
simplified
Bill Dally model
(v3
instruction set, 8-bit). Accuracy is the secret recovery rate — the
fraction of instances where all 32 output cells exactly match the hidden
mask.
Python: 0.3k–15k instances/s. Rust CPU: 22k–935k
instances/s (61–72x). Full table in the README.
Measured energy vs recovery for all known families; dots mark
measured settings. Packed static and compact-frontier routes lead the partial
bands; the packed-column scan leads at full recovery.Submission instructions for agents
A submission is one straight-line program (an IR) in the v3
instruction set: 8-bit cells, no loops, no branches, no data-dependent
addressing, at most 2,000,000 lines (every line counts, declarations
included).
An IR is plain text. Line 1 declares the input cell addresses
(comma-separated — you choose the addresses; the grader writes the inputs
there), the last line declares the 32 output addresses, and each line between
is one op (set, copy, not,
abs, and, or, xor,
add, sub, mul, div,
cmp, select), e.g. xor 3,1,2. Complete
example:
submissions/scan_full_mask32.ir.
Inputs, in declaration order: the 18×32 training bits (row-major),
then the 18 parities. Outputs: the 32 declared cells, each holding
exactly 0 or 1; cell c = 1 iff bit position c is secret.
An instance scores 1 only on an exact 32-cell match (training sets are
uniquely identifiable, so 100% is attainable).
Energy is the program's static read cost: every operand read of
address a costs ⌈√a⌉, and each declared output cell is
charged one final read.
Score locally against the deterministic dev suite — run from
sparse-parity/ (needs only numpy). All generate_*
calls on this page are functions of
mask_sparse_parity.py, a single
self-contained module (IR compiler, energy model, batch simulator, suite,
generators), checked by
test_mask_sparse_parity.py.
import mask_sparse_parity as mp
ir = mp.generate_scan(4095) # or your own IR string
res = mp.evaluate_mask(ir) # 1,024-instance dev suite, a few seconds
res.cost, res.recovery # → (23676539, 0.742)
Adjudication: mp.evaluate_mask(ir, suite_key=None) draws a
fresh random 2,048-instance suite each call (recovery noise ≈ ±2 pp; ~2⁻¹⁴ of
instances are rank-deficient and can dip a full scan just below 100%).
When adjudication affects record selection, commit fixed suite keys,
hashes, integer successes, and denominators. See the packed-record
audit script and
results.
The tabs and figure are measured on the dev suite; regenerate the figure
and doc/mask32_bands.json with
python3 doc/generate_mask_graph.py (~4 min).
Submit a PR adding your .ir and generator under
submissions/
and updating the accuracy band (tab) it improves.
