Human-authored tinygrad work

Bounty #3039 Workbench

A scratchpad and test plan for Thomas to implement the associative-scan bounty himself, while keeping AI assistance outside the tinygrad code contribution.

$500 bounty · research/workbench only

Rule: do not copy AI-authored tinygrad code into the submission. Use this page for reasoning, test design, benchmarks, notes, and a human-authored implementation checklist.

Open bounty #3039 ↗ · Reference closed PR #17557 ↗

1. Understand the target

Read bounty #3039 and write the exact acceptance criteria in your own words. Identify the smallest tinygrad API surface needed for an inclusive associative scan. Confirm axis, reverse, odd-length, dtype, and shape semantics. Include a non-commutative operation test so accidental reordering is caught.

2. Correctness test matrix

lengths: 1, 2, 3, 5, 8, 17
forward and reverse
axis 0 and non-zero axis
integer + floating point
non-commutative matrix-prefix composition
compare to a simple sequential reference

Start with correctness before parallel-depth optimization.

3. Algorithm checkpoint

Candidate family: work-efficient tree/prefix scan. Your implementation should preserve operation order, handle non-power-of-two lengths, and expose enough parallelism that depth grows roughly logarithmically rather than linearly.

Write the algorithm yourself from primary references or your own derivation. Avoid lifting code from the abandoned AI-authored PR.

4. Benchmark plan

Record sequential reference timing. Benchmark several scan lengths, including awkward odd sizes. Inspect generated schedule/kernel count as a proxy for parallel depth. Check that common tinygrad tests remain green.

Your implementation notes

Notes and checklist state stay in this browser via localStorage.

Definition of done

The tinygrad patch is personally authored and understood by Thomas. Sequential-reference comparisons pass across the correctness matrix. The implementation demonstrates meaningful parallel depth/work behavior. Relevant upstream test suites pass locally. PR description explains semantics, algorithm, validation, and performance without overstating results.