Skip to content

README.md

Latest commit

 

History

History
116 lines (87 loc) · 5.22 KB

README.md

File metadata and controls

116 lines (87 loc) · 5.22 KB
Raw

Sparse Parity Challenge

Can you solve sparse parity with less energy than a neural network?

Given random {-1, +1} inputs and a label that's the product of k secret bits, find those bits. The catch: we measure not just accuracy and speed, but data movement -- how much energy your solution costs at the hardware level.

Submit a Solution

Submit Solution

Paste a Python function, pick a config, submit. GitHub Actions runs it automatically and posts your results.

Function signature

def solve(x, y, n_bits, k_sparse):
    """
    Args:
        x: numpy array (n_samples, n_bits), values in {-1, +1}
        y: numpy array (n_samples,), values in {-1, +1}
        n_bits: int, total number of bits
        k_sparse: int, number of secret bits
    Returns:
        list[int]: sorted indices of the k secret bits
    """

Rules

  • Only numpy allowed (imported as np)
  • No file I/O, network, or dynamic execution
  • 60 second timeout
  • Must achieve ≥95% accuracy across 3 seeds
  • Evaluated with TrackedArray for automatic DMD measurement

Submitting via CLI

Adding labels requires collaborator access. If you're not a collaborator, use the web form above -- it auto-applies the label and works for everyone.

# Collaborators only: create issue + add label
gh issue create --repo cybertronai/sparse-parity-challenge \
  --title "Submission: your_method_name" \
  --body "$(cat your_solution.py)"
gh issue edit <number> --repo cybertronai/sparse-parity-challenge --add-label submission

Leaderboard

Ranked by DMD (Data Movement Distance) -- lower is better.

Rank Method Author DMC Time Accuracy Issue
1 Sequential Elimination @Hydral8 19,153 0.0085s 100% #30
2 passive_gf2_rref_minimal_22rows @Hydral8 45,904 0.0002s 100% #24
3 GF(2) Ultra-Minimal (n+1 samples, retry) @SethTS 286,011 0.0044s 100% #19
4 GF(2) Minimal (2n samples) @SethTS 601,157 0.0087s 100% #17
5 SMT Backtracking (n+1 samples) (v1) @0bserver07 1,625,260 0.0063s 100% #33
6 GF(2) Gaussian Elimination @SethTS 11,164,685 0.1011s 100% #13
7 new solution coded live during the Friday Rochester seminar. @yaroslavvb 14,748,439 0.1075s 100% #37
8 new gf2 proposed candidate @yaroslavvb 24,397,704 0.0019s 100% #22

The metric

Current evaluation: TrackedArray (element-level, numpy-aware). Your numpy operations get automatically tracked. DMD = sum of sqrt(stack_distance) per element read. Lower = better.

New (in transition): ByteDMD -- byte-granularity, pure Python, deterministic. Vendored at src/bytedmd/. Reads cost ceil(sqrt(depth)) per byte, writes are free. Tests in tests/test_bytedmd.py.

The transition is in progress. Existing leaderboard entries are measured with the legacy TrackedArray metric. New submissions can be evaluated under both metrics once bin/evaluate is updated. See cybertronai/ByteDMD for the spec.

The neural network baseline (SGD) has DMD ~1.3M under TrackedArray. The best known solution (KM influence estimation) has DMD ~3,600. Can you beat it?

Research context

This challenge comes from the Sutro Group, a study group at South Park Commons exploring energy-efficient AI training. 36 experiments across algebraic, information-theoretic, and neural approaches. The full research is at cybertronai/SutroYaro.

Local testing

git clone https://github.com/cybertronai/sparse-parity-challenge.git
cd sparse-parity-challenge
pip install numpy

# Test your solve() function locally
PYTHONPATH=src python3 -c "
import numpy as np
from sparse_parity.tracked_numpy import TrackedArray, tracking_context
from sparse_parity.lru_tracker import LRUStackTracker

# Your function here
def solve(x, y, n_bits, k_sparse):
    # example: GF(2) or whatever you want to try
    pass

# Generate data
rng = np.random.RandomState(42)
n_bits, k_sparse = 20, 3
secret = sorted(rng.choice(n_bits, k_sparse, replace=False).tolist())
x = rng.choice([-1.0, 1.0], size=(500, n_bits))
y = np.prod(x[:, secret], axis=1)

# Evaluate with tracking
tracker = LRUStackTracker()
with tracking_context(tracker):
    x_t = TrackedArray(x, 'x', tracker)
    y_t = TrackedArray(y, 'y', tracker)
    result = solve(x_t, y_t, n_bits, k_sparse)

print(f'Found: {result}')
print(f'Secret: {secret}')
print(f'Correct: {sorted(result) == secret}')
print(f'DMD: {tracker.summary()[\"dmd\"]:,.1f}')
"