Sparse Support Memory Executor Experiment

Finished2026-06-21imported · line YAlgorithmic Memory and Retrieval Structured Execution and Compilers GitHub ↗

The one idea you need

Picture tracking a hidden pair of numbers as a page of suspects. Each program step either reshuffles every suspect the same way or crosses some off with a clue. Keep one line per suspect and the truth always survives; skimp on lines and you sometimes erase it.

The question

When a small system tracks hidden numbers through a chain of clues and transformations, how much scratch memory does it need to never lose the true answer?

What we found

Only when its scratch memory held one slot for every possible starting value. With that, it answered every question correctly through the longest 24-step programs. Cut the memory roughly in half and accuracy fell to about 69%, because whole batches of candidates got erased mid-program, and about 1 in 3 examples lost every candidate and fell back to a guess. A wider memory vector is not the fix; enough addressable slots is.

Why it matters

For symbolic state-tracking, size scratch memory to the number of live possibilities the program must keep alive, not to a wider dense vector, and watch the rate of wiped-out cases as an early warning of undersized memory.

Full memory on the longest programs100%one slot per possible starting value, 24-step programs

Roughly half memory on the longest programsabout 69%16 of 31 possible slots kept, 24-step programs

Cases that lost every candidate at half memoryabout 1 in 3fell back to a guess, 16 slots, 24-step programs

Two-thirds memory, larger number space86.5%64 of 97 possible slots kept, 24-step programs

On this page

Results at a glance
Overview
Report
Experiment log
Figures
Data files
Reproduce
Related

Results at a glance 2

More memory slots keep accuracy as programs get longer

How to read

Horizontal axis is program length in steps; vertical axis is how often the exact answer survives, higher is better. Each line is a memory size; the top line holds one slot per possible starting value.

Takeaway → Only the full line stays flat at the top across all lengths; every smaller-memory line slopes downward, so missing slots cost accuracy on longer programs.

Data table

Program length	4 slots	8 slots	16 slots	31 slots (S = p)
4	70%	93.7%	98.5%	100%
8	55.4%	80%	93.1%	100%
12	42.5%	66.7%	86.9%	100%
16	32.1%	56.3%	78.2%	100%
24	23.4%	41.9%	68.6%	100%

Numbers from experiments/sparse_support_memory_executor/analysis/summary.md (also README/paper table)

Technical framing

Slot capacity vs program length: exact execution appears only at S = p (modulus 31) — With one slot per initial hypothesis (S=31), execution is exact at every length; any smaller memory degrades steadily with length.

The same pattern holds with far more possible answers

How to read

Horizontal axis is program length in steps; vertical axis is how often the exact answer survives, higher is better. Each line is a memory size, with the top line holding one slot per possible starting value.

Takeaway → Even a memory holding two-thirds of the slots leaks accuracy on long programs; only the full-support line stays perfectly flat at the top.

Data table

Program length	16 slots	32 slots	64 slots	97 slots (S = p)
4	94.9%	97.9%	99.7%	100%
8	83.5%	92.6%	98.1%	100%
12	71.4%	86.8%	96.1%	100%
16	61.8%	79.4%	93.1%	100%
24	42.3%	66.6%	86.5%	100%

Numbers from experiments/sparse_support_memory_executor/analysis/summary.md (also README/paper table)

Technical framing

Same capacity threshold at modulus 97 — The threshold replicates at p=97: even 64 slots leaks accuracy with length, while a full-support memory stays exact.

In the author’s words from the Report · “Abstract”

The main result is a sharp capacity threshold: at modulus 31, S=31 reaches 100.0% query mass and 100.0% belief mass through length 24; S=16 reaches 68.6% query mass and 67.6% belief mass at length 24. At modulus 97, the same pattern holds: S=97 is exact, while S=64 reaches 86.5% query mass and 86.3% belief mass at length 24.

Overview

This experiment tests whether exact modular belief-state execution is recovered when the recurrent state is an explicit sparse set of support slots rather than a fixed-width dense vector.

src/sparse_support_memory_experiment.py: task generator, sparse support executor, evaluation harness.
src/analyze_sparse_support_memory.py: analysis and figure generation.
reports/sparse_support_memory_experiment_log.md: chronological experiment log.
reports/sparse_support_memory_paper.md: standalone written report.
reports/sparse_support_memory_paper.html: standalone HTML report.
runs/: JSON and CSV run outputs.
analysis/: generated summaries and figures.
checkpoint_manifest.csv: checkpoint paths and sizes.

Large trainable artifacts, if any, are written outside the experiment directory:

../../large_artifacts/sparse_support_memory_executor/checkpoints/

Download this experiment directory for the normal research bundle. Download ../../large_artifacts/sparse_support_memory_executor/ only when saved model weights are needed.

Report

Rendered from reports/sparse_support_memory_paper.md

Abstract

This experiment tests whether modular belief-state execution requires an explicit support representation. Programs transform two hidden registers, A and B, under modular arithmetic and observation filters. The runtime state is a bounded sparse memory of weighted candidate (A,B) pairs. When the slot budget equals the initial support size, S=p, the executor solves every tested program exactly once the recurrent budget reaches the program length. When S<p, performance degrades in proportion to lost support, and the failure is directly visible through the empty-slot rate.

The main result is a sharp capacity threshold: at modulus 31, S=31 reaches 100.0% query mass and 100.0% belief mass through length 24; S=16 reaches 68.6% query mass and 67.6% belief mass at length 24. At modulus 97, the same pattern holds: S=97 is exact, while S=64 reaches 86.5% query mass and 86.3% belief mass at length 24.

Task

Each example starts from a hidden relation:

B = A + d (mod p), with A unknown

The initial belief therefore contains exactly p possible (A,B) states. Programs contain two kinds of operations:

Arithmetic updates: A=A+c, A=A-c, B=B+c, B=B-c, A=A+B, B=B+A, A=A-B, B=B-A
Observation filters: A % m = r or B % m = r

Observation residues are sampled from the current support, so the target belief is never empty. The final query asks for one distribution over A, B, A+B mod p, or A-B mod p.

Executor

The executor keeps S weighted support slots. Each active slot stores one concrete (A,B) pair. Arithmetic operations update every active slot exactly. Observation filters delete slots that violate the observed residue. The output belief is the normalized distribution represented by the active slots.

If S>=p, initialization stores all initial support states. If S<p, initialization stores a deterministic stride subset of the initial support. When all represented slots are deleted by later observations, the executor falls back to a uniform pair distribution and records an empty_slot_rate event.

Protocol

The experiment evaluates four phases:

Phase	Modulus	Slot capacities	Lengths	Examples per query type
Smoke	7	2, 4, 7	2, 3	64
Pilot	11	4, 8, 11	3, 6, 9, 12	512
Main	31	4, 8, 16, 31	4, 8, 12, 16, 24	512
Scale	97	16, 32, 64, 97	4, 8, 12, 16, 24	256

For each length L, the executor is evaluated at several recurrent budgets K. The headline rows report the first K such that K>=L.

Metrics:

decoder_query_target_mass: probability assigned to the exact final query support.
decoder_belief_target_mass: probability assigned to the exact final (A,B) support.
empty_slot_rate: fraction of examples where all represented slots were deleted and the executor fell back to uniform.
mean_active_slots: mean active slots at the selected recurrent budget.

Main Results

At modulus 31, exact execution appears exactly at S=p.

Slot capacity	L=4 query	L=8 query	L=12 query	L=16 query	L=24 query	L=24 empty
4	70.0%	55.4%	42.5%	32.1%	23.4%	80.3%
8	93.7%	80.0%	66.7%	56.3%	41.9%	60.5%
16	98.5%	93.1%	86.9%	78.2%	68.6%	32.5%
31	100.0%	100.0%	100.0%	100.0%	100.0%	0.0%

Strict belief mass follows the same pattern.

Slot capacity	L=4 belief	L=8 belief	L=12 belief	L=16 belief	L=24 belief
4	65.3%	50.6%	37.8%	27.7%	19.9%
8	93.1%	78.9%	65.0%	54.3%	39.5%
16	98.5%	92.9%	86.4%	77.4%	67.6%
31	100.0%	100.0%	100.0%	100.0%	100.0%

Modulus 31 query mass

Modulus 31 belief mass

Scale Results

The same capacity threshold appears at modulus 97.

Slot capacity	L=4 query	L=8 query	L=12 query	L=16 query	L=24 query	L=24 empty
16	94.9%	83.5%	71.4%	61.8%	42.3%	58.7%
32	97.9%	92.6%	86.8%	79.4%	66.6%	33.8%
64	99.7%	98.1%	96.1%	93.1%	86.5%	13.7%
97	100.0%	100.0%	100.0%	100.0%	100.0%	0.0%

Strict belief mass again tracks query mass closely.

Slot capacity	L=4 belief	L=8 belief	L=12 belief	L=16 belief	L=24 belief
16	94.7%	83.0%	70.7%	61.0%	41.3%
32	97.9%	92.5%	86.6%	79.1%	66.2%
64	99.7%	98.0%	96.1%	93.1%	86.3%
97	100.0%	100.0%	100.0%	100.0%	100.0%

Modulus 97 query mass

Modulus 97 empty slot rate

Interpretation

The task is exactly solvable with a compact structured state: one slot per initial support element. The arithmetic operations are bijections over the support, so they do not increase the number of represented states. Observation filters only remove states. Therefore a memory with S=p slots can preserve the exact belief distribution indefinitely under this program family.

Sub-capacity memories fail for a concrete reason. They do not store the whole initial relation, so later observations can delete every represented slot even when the true target support is nonempty. The empty-slot rate grows with length and predicts the drop in both query mass and belief mass.

The result supports a precise design claim: for this class of symbolic latent execution tasks, the critical missing state is not a larger dense vector by itself. The executor needs an addressable support representation whose capacity matches the number of live hypotheses that the program may need to preserve.

Limitations

This executor is not a learned neural model. The arithmetic and observation updates are hand-coded, and initialization is deterministic. The experiment therefore isolates representational sufficiency, not learnability.

The program family also has a bounded-support property: support never grows above the initial p states. A different task with branching uncertainty would need a larger or dynamically allocated memory.

Reproducibility

Run files are in experiments/sparse_support_memory_executor/runs/. Aggregated analysis files are in experiments/sparse_support_memory_executor/analysis/. No model checkpoints are required for this sweep.

Example main run:

PYTHONDONTWRITEBYTECODE=1 python experiments/sparse_support_memory_executor/src/sparse_support_memory_experiment.py \
  --variant_name main_mod31_s31 \
  --modulus 31 \
  --observe_mod 5 \
  --observe_prob 0.3 \
  --slot_capacity 31 \
  --eval_lengths 4,8,12,16,24 \
  --eval_k 0,1,2,4,8,12,16,24 \
  --eval_examples 512 \
  --eval_batch_size 256 \
  --output_dir experiments/sparse_support_memory_executor/runs/main_mod31_s31

Regenerate analysis:

PYTHONDONTWRITEBYTECODE=1 python experiments/sparse_support_memory_executor/src/analyze_sparse_support_memory.py

Experiment log 12

Show the running log (12 entries, 2026-06-21)

Objective

Test whether modular filter-program execution becomes exact when the runtime state is an explicit sparse memory of candidate (A,B) support states.

Each example starts from the relation:

B = A + d (mod p), with A unknown

A program then applies arithmetic updates and observation filters. The executor keeps at most S support slots. Each slot stores one concrete (A,B) pair and a weight. Arithmetic updates move every active slot. Observation filters delete inconsistent slots. The output distribution is the normalized weighted support set represented by the active slots.

Primary Questions

Is a slot budget equal to the initial support size, S=p, sufficient for exact execution across long programs?
How sharply does performance degrade when S<p?
Does the K-threshold remain clean: weak before K=L, exact or near-exact once the recurrent budget reaches the program length?
Does the same result hold at larger modulus when the support memory scales with the modulus?

Metrics

decoder_belief_target_mass: probability assigned by the slot distribution to the exact final pair-support.
decoder_query_target_mass: query probability after projecting the slot distribution to the requested query.
decoder_belief_top1_on_support: whether the highest-probability pair is in the exact final support.
empty_slot_rate: fraction of examples whose compressed support lost all surviving particles and had to fall back to a uniform distribution.
mean_active_slots: mean active slots after the selected recurrent budget.

The headline metric is decoder_query_target_mass, with decoder_belief_target_mass as the stricter state-execution metric.

Artifact Layout

Code and lightweight outputs: experiments/sparse_support_memory_executor/
Large artifacts: large_artifacts/sparse_support_memory_executor/checkpoints/
Run outputs: experiments/sparse_support_memory_executor/runs/<variant>/
Analysis outputs: experiments/sparse_support_memory_executor/analysis/

Planned Sequence

Smoke test on modulus 7 to validate the sparse executor and output files.
Pilot capacity sweep on modulus 11.
Main capacity sweep on modulus 31.
Scale check on modulus 97.
Generate tables, figures, checkpoint manifest, standalone report, and HTML report.

Variant Plan

smoke_mod7_s{2,4,7}: tiny validation sweep.
pilot_mod11_s{4,8,11}: small-modulus capacity sweep.
main_mod31_s{4,8,16,31}: main sparse-slot capacity sweep.
scale_mod97_s{16,32,64,97}: larger-modulus capacity sweep.

2026-06-21 Setup

Created the standalone experiment directory:

experiments/sparse_support_memory_executor/src/
experiments/sparse_support_memory_executor/reports/
experiments/sparse_support_memory_executor/runs/
experiments/sparse_support_memory_executor/analysis/figures/
large_artifacts/sparse_support_memory_executor/checkpoints/

Next action: implement the sparse support-memory evaluator and analysis script, then run smoke tests before launching the pilot and main sweeps.

2026-06-21 Smoke Tests

Ran three modulus-7 smoke variants with evaluation lengths 2 and 3:

Variant	Slot capacity	L=2 decoder-query	L=2 belief	L=3 decoder-query	L=3 belief	Empty rate at K=L
`smoke_mod7_s2`	2	75.9%	68.5%	70.2%	61.4%	32.8-40.2%
`smoke_mod7_s4`	4	95.9%	95.1%	94.1%	92.8%	5.1-7.4%
`smoke_mod7_s7`	7	100.0%	100.0%	100.0%	100.0%	0.0%

Smoke interpretation:

The harness writes metrics_final.csv, results.json, and analysis artifacts.
The exact-capacity case, S=p, is exactly correct once K reaches the program length.
Undersized slot memories degrade smoothly, and the empty_slot_rate field exposes when the compressed support has lost every surviving state.

Next action: run the modulus-11 pilot sweep with S=4,8,11.

2026-06-21 Pilot Sweep

Ran three modulus-11 pilot variants with evaluation lengths 3, 6, 9, and 12:

Variant	Slot capacity	L=3 decoder-query	L=6 decoder-query	L=9 decoder-query	L=12 decoder-query	L=12 empty rate
`pilot_mod11_s4`	4	87.7%	76.5%	66.8%	60.5%	44.5%
`pilot_mod11_s8`	8	91.8%	86.9%	81.9%	80.6%	22.0%
`pilot_mod11_s11`	11	100.0%	100.0%	100.0%	100.0%	0.0%

Pilot interpretation:

S=p again gives exact execution at all tested lengths once K>=L.
Sub-capacity memories retain useful query signal, but they lose exact support mass because the initial relation has more live states than the memory can store.
Empty-support fallbacks increase with length for undersized memories, making slot loss directly measurable rather than hidden in the query score.

Next action: run the main modulus-31 capacity sweep with S=4,8,16,31.

2026-06-21 Main Sweep

Ran four modulus-31 variants with evaluation lengths 4, 8, 12, 16, and 24:

Variant	Slot capacity	L=4 decoder-query	L=8 decoder-query	L=12 decoder-query	L=16 decoder-query	L=24 decoder-query	L=24 empty rate
`main_mod31_s4`	4	70.0%	55.4%	42.5%	32.1%	23.4%	80.3%
`main_mod31_s8`	8	93.7%	80.0%	66.7%	56.3%	41.9%	60.5%
`main_mod31_s16`	16	98.5%	93.1%	86.9%	78.2%	68.6%	32.5%
`main_mod31_s31`	31	100.0%	100.0%	100.0%	100.0%	100.0%	0.0%

Strict decoded-belief mass followed the same ordering:

Variant	L=4 belief	L=8 belief	L=12 belief	L=16 belief	L=24 belief
`main_mod31_s4`	65.3%	50.6%	37.8%	27.7%	19.9%
`main_mod31_s8`	93.1%	78.9%	65.0%	54.3%	39.5%
`main_mod31_s16`	98.5%	92.9%	86.4%	77.4%	67.6%
`main_mod31_s31`	100.0%	100.0%	100.0%	100.0%	100.0%

Main interpretation:

Exact symbolic execution appears at the predicted capacity threshold: S=p.
The degradation below S=p is not mysterious decoder error; it tracks support loss directly through empty_slot_rate.
A half-size support memory, S=16, preserves much of the query mass but is still materially below exact on long programs.

Next action: run a larger modulus-97 scale check with S=16,32,64,97.

2026-06-21 Scale Check

Ran four modulus-97 variants with evaluation lengths 4, 8, 12, 16, and 24:

Variant	Slot capacity	L=4 decoder-query	L=8 decoder-query	L=12 decoder-query	L=16 decoder-query	L=24 decoder-query	L=24 empty rate
`scale_mod97_s16`	16	94.9%	83.5%	71.4%	61.8%	42.3%	58.7%
`scale_mod97_s32`	32	97.9%	92.6%	86.8%	79.4%	66.6%	33.8%
`scale_mod97_s64`	64	99.7%	98.1%	96.1%	93.1%	86.5%	13.7%
`scale_mod97_s97`	97	100.0%	100.0%	100.0%	100.0%	100.0%	0.0%

Scale interpretation:

The S=p threshold replicated at a much larger pair space.
Sub-capacity memories can remain highly useful when S is large, but exact belief execution still requires enough slots to cover the initial relation.
At length 24, S=64 preserves 86.5% query mass but still loses support in 13.7% of examples; S=97 removes that failure mode.

Analysis artifacts generated:

analysis/all_metrics_long.csv
analysis/all_metrics_query_mean.csv
analysis/first_k_ge_l_summary.csv
analysis/summary.md
analysis/figures/

Next action: write the standalone report and HTML artifact, then audit the directory layout and checkpoint manifest.

2026-06-21 Final Audit

Completed the standalone write-up and layout audit.

Created report artifacts:

reports/sparse_support_memory_paper.md
reports/sparse_support_memory_paper.html

Audit results:

14 run directories are present, and each has metrics_final.csv plus results.json.
The HTML report references four generated figures, and all four image paths resolve.
The experiment directory is lightweight, about 4 MB.
No trainable checkpoints were produced by this deterministic sparse-support sweep; large_artifacts/sparse_support_memory_executor/ is intentionally empty and checkpoint_manifest.csv contains only the header.
The standalone report does not refer to any older or source experiment.

Final status: complete.