sutro-problems

Matrix Multiplication

Author: Codex and Cosmin
Date: 2026-05-28
Problem: 16x16 matmul
Cost: 66,300
IR: best_66300.ir
Method: Claude-assisted simulated annealing over a prior leaderboard physical-address IR

Summary

This IR computes ordinary 16x16 matrix multiplication: 256 A inputs, 256 B inputs, and 256 C outputs. It keeps the standard arithmetic shape: 4,096 multiplies and 3,840 additions.

The score is dominated by reads. A read from address x costs ceil(sqrt(x)); writes and arithmetic themselves are free. This candidate was produced by iterating with Claude and simulated annealing on top of a prior leaderboard physical-address submission. It is checked in as a final physical-address IR rather than as a raw semantic trace, so the companion script verifies the submitted IR directly.

Compared with the prior promoted 66,400 submission, this artifact uses seven fewer copy operations and seven fewer paid reads. The exact score improves by 100 points, from 66,400 to 66,300.

Cost Breakdown By Address Tier

tier addrs reads cost
1 1 5,169 5,169
2 2..4 4,991 9,982
3 5..9 2,359 7,077
4 10..16 852 3,408
5 17..25 1,089 5,445
6 26..36 1,325 7,950
7 37..49 326 2,282
8 50..64 110 880
9 65..81 119 1,071
10 82..100 133 1,330
11 101..121 147 1,617
12 122..144 161 1,932
13 145..169 114 1,482
14 170..196 100 1,400
15 197..225 87 1,305
16 226..256 93 1,488
17 257..289 96 1,632
18 290..324 70 1,260
19 325..361 74 1,406
20 362..400 78 1,560
21 401..441 82 1,722
22 442..484 44 968
23 485..529 45 1,035
24 530..576 47 1,128
25 577..625 49 1,225
26 626..676 21 546
total   17,781 66,300

Instruction Distribution

instruction count paid reads read cost
mul 4,096 8,192 14,272
add 3,840 7,680 26,209
copy 1,653 1,653 21,565
output exit 256 256 4,254
total 9,589 ops 17,781 66,300

Additional shape checks:

Verification

/Users/cosmin/miniconda/bin/python matmul/submissions/best_66300.py
/Users/cosmin/miniconda/bin/python matmul/experiments/random_true_matmul_check.py matmul/submissions/best_66300.ir --n 16 --trials 100 --seed 20260528 --min -31 --max 31

Observed locally:

best_66300.ir  cost=66,300
matmul/submissions/best_66300.ir: cost=66,300 ok 100 random trials