sutro-problems

Matrix Multiplication

Author: @SecurityQQ, assisted by OpenCode
Date: 2026-09-07 (UTC)
Problem: 16x16 matmul
Cost: 64,074

Method

Preserve temporary cheap replicas of inputs and read each logical value from its cheapest surviving replica. Relative to the 64,431 submission by @cosminscn and Codex, 244 extra copies reduce multiplication read cost by 520 while increasing copy read cost by 163: 357 saved (0.555%). Input placement, original instruction destinations, and the order and logical operands of all arithmetic operations are unchanged.

The search inserts one input capture at an instruction boundary, accounting for both future read savings and eviction of the destination’s previous value. Reads happen before writes, so a capture can help even at the next overwrite. A follow-up deletion pass removed one capture (B[15,5] into address 36) that later captures had made redundant, saving its source read.

The final searches completed with no improving proposal in any of these neighborhoods, with cheapest-replica source selection and addresses 1..638:

inserting one copy of any live value — input, product, partial sum, or finished output — at any instruction boundary into any destination (all intermediate candidates are screened out: none can repay its own copy-source read);
deleting any single copy;
relocating any single copy (delete plus reinsertion of the same value at any boundary and destination, which subsumes retargeting and moving).

This is not a global optimum claim; paired multi-copy edits, rescheduling, and reduction-tree changes remain unsearched. Costs are abstract Dally v0 read costs, not measured energy or runtime.

Instruction	Count	Read cost	Change from 64,431
`copy`	1,748	20,047	+163
`mul`	4,096	18,832	-520
`add`	3,840	20,751	0
Output exit	256	4,444	0
Total	9,684 instructions	64,074	-357

All 512 inputs and 256 outputs are checked exactly; maximum address is 638.

Verification and Replay

From the repository root, using only the Python standard library:

python3 -S matmul/submissions/best_64074.py
python3 -S -m unittest matmul.test_record_64074 -v

The verifier checks the frozen hash, official symbolic scorer, independent noncommutative-polynomial proof, operation counts, read-cost breakdown, and byte-exact replay. The compact JSON manifest records 244 insertions as [original instruction boundary, input identity, destination]; rows sharing a boundary execute in manifest order. Identities 0..255 are row-major A, 256..511 are row-major B. Replay starts from committed best_64431.ir, inserts the captures, and reselects every source and output at its lowest surviving address. It requires neither the original search workspace nor rerunning the search. The replay also preserves the original copies as logical operations.

SHA-256: b5ca6fb67c61825927e6978c13e16a6a432748c32f6c0f1f52a5dbefb3f2e7dd.