From 0888ad62315b9b18c050d77ef9077b2405eb0aef Mon Sep 17 00:00:00 2001 From: CaptainJack2491 Date: Sat, 29 Aug 2026 23:07:18 +0100 Subject: preregister Addendum 8: 4-arm token-space recurrence & decomposition test (E8) --- design/preregistration.md | 58 ++++++ design/scratchpad_explainer.html | 436 +++++++++++++++++++++++++++++++++++++++ 2 files changed, 494 insertions(+) create mode 100644 design/scratchpad_explainer.html diff --git a/design/preregistration.md b/design/preregistration.md index 07d0791..ad15994 100644 --- a/design/preregistration.md +++ b/design/preregistration.md @@ -310,4 +310,62 @@ cells, per user decision; protocol locked in Addendum 7 post-E6. --- +## Addendum 7 — E7: 20× Long-Horizon Budget Test (locked 2026-08-19, pre-run) + +**Question:** Is the failure of next-prime grokking in E6 an optimization horizon / compute-gated artifact ($H_\text{slow}$), or an algorithmic alignment / task-structure barrier? + +**Protocol (4 cells, seed 0):** +- Candidates: `wd` $\in \{0.1, 0.3\} \times \{\text{rnn}, \text{transformer}\}$ (the $O\text{-PARTIAL}$ cells from E6). +- Budget: $4\,000\,000$ steps ($20\times$ E6's 200k steps). +- Schedule: Adaptive evaluation (530 evals total). +- Range: $[2, 1000]$, `train_frac=0.7`, digits mode, $K=32$. +- Probe: $[1001, 2000]$ (1000 out-of-range items). + +**Interpretation matrix (locked):** +1. **O1 anywhere:** GROKKING CONFIRMED on next-prime: transition exists, was budget-limited at 200k. Record transition step. +2. **O-PARTIAL with `val_em_best > parent best` AND sustained $\ge 50\text{k}$ steps after the parent's entire budget:** Partial progress toward the algorithmic basin; report as slow-basin dynamics, NOT grokking. +3. **Same codes as E6 parents (O-PARTIAL/O4, P4/P2, no P5(k$\ge$10)/P6):** $H_\text{slow}$ REJECTED for these cells at 4M steps: the null is now budget-robust to $20\times$. Surviving hypotheses become task-structure-gated (algorithmic alignment), not compute-gated. + +--- + +## Addendum 8 — E8: Token-Space Recurrence & Decomposition (Arms A, B, C, D) (locked 2026-08-29, pre-run) + +**Question (Q3d / Q1):** Does expanding computation into token space—via explicit algorithmic decomposition (scratchpad), unsupervised compute positions (filler/pause tokens), or random sequence expansion—enable a fixed-depth Transformer to discover the next-prime algorithm ($O1$) where $4\text{M}$ steps of fixed-depth training ($E7$) failed? + +**Background & Theoretical Predictions:** +1. **Algorithmic Decomposition (Nye et al. 2021):** Supervised intermediate computation provides dense gradient pathways through combinatorial search spaces. +2. **Parallel Subcomputation in Filler Tokens (Pfau et al. 2024):** Filler tokens ($\langle\text{pause}\rangle$) only aid computation when underlying subproblems are parallelizable. Next-prime requires trial division across primes $\{2, 3, 5, \dots, \sqrt{c}\}$, which are independent modular tests that can be evaluated in parallel across attention heads at intermediate positions. +3. **Sequence Length / Depth Invariance:** Testing whether random non-digit tokens (Arm D) provide equivalent routing capacity without static token embeddings. + +**Protocol:** +- **Model:** GPT-style transformer (2 layers, 4 heads, `d_model=128`, `d_ff=512`), `wd=0.1`, `lr=1e-3` (const), `batch_size=32`, `max_train_steps=200_000`, `eval_every=200`. +- **Dataset:** Range $[2, 1000]$, `train_frac=0.7`, digits mode, seed 0. +- **Probe:** Generalization evaluated on out-of-range $[1001, 2000]$. +- **Hardware/Precision:** CUDA + AMP fp16 on ichi / voidlaptop (CPU fallback). + +**The Four Experimental Arms:** +1. **Arm A (Direct Baseline / Control):** Standard mapping $n \to \text{next\_prime}(n) + \text{EOS}$. +2. **Arm B (Structured Scratchpad):** Explicit trial division trace: + $n \to \text{candidate and divisor checks } (c = n+1, \dots; d_2:0/1, d_3:0/1, \dots) \to \text{SEP} \to \text{next\_prime}(n) + \text{EOS}$. +3. **Arm C (Fixed Pause / Filler Tokens):** $16$ identical pause tokens: + $n \to \underbrace{\langle\text{pause}\rangle \dots \langle\text{pause}\rangle}_{16} \to \text{SEP} \to \text{next\_prime}(n) + \text{EOS}$. +4. **Arm D (Random Disjoint Tokens):** $16$ uniform random symbols from disjoint alphabet $[a\text{-}p]$: + $n \to \underbrace{r_1 r_2 \dots r_{16}}_{16} \to \text{SEP} \to \text{next\_prime}(n) + \text{EOS}$. + +**Loss Masking & Evaluation Rules:** +- Loss computed over target answer tokens for all arms (and trace tokens for Arm B during teacher forcing). Filler/random tokens in Arms C/D are masked from cross-entropy loss. +- In-range validation exact-match (EM) and out-of-range probe accuracy are scored strictly on the final answer tokens (post-SEP / post-scratch). + +**Interpretation Matrix (Locked):** + +| Code | Observable Condition | Interpretation (Locked) | Next Step | +|---|---|---|---| +| **S1** | Arm B shows $O1$ (sharp val EM $\ge 0.9$), while A, C, D remain $O\text{-PARTIAL}$ or $O4$ | **Decomposition-Gated:** Algorithmic grokking requires explicit trace supervision; unsupervised compute positions are insufficient to discover divisibility. | Sieve-rank probe on scratch outputs; inspect generated traces for correct divisibility. | +| **S2** | Arm C shows $O1$ or significant probe generalization ($P5(k)$ / $P6$ on $[1001, 2000]$) | **Pfau Hypothesis Confirmed:** Unsupervised filler tokens provide enough hidden attention routing to compute parallel divisibility tests without trace supervision. Major positive result. | Sieve-rank estimation; test filler length ablation ($M \in \{4, 8, 16, 32\}$). | +| **S3** | Arm D $\approx$ Arm C $\gg$ Arm A | **Depth/Position Invariance:** Sequence expansion enables attention routing independent of token identity. | Study attention maps across intermediate layers. | +| **S4** | Arm B in-range $\text{val EM} \approx 1.0$, but out-of-range probe $[1001, 2000]$ is $P4$ ($<10\%$) | **Bounded Trace Interpolation:** Scratchpad supervision fits training domain heuristics but does not induce generalizable out-of-distribution reasoning. | Test `is_prime` scratchpad to isolate divisibility vs candidate search. | +| **S5** | All arms A, B, C, D remain $O\text{-PARTIAL}$ / $O4$ ($P4$ out-of-range) | **Strongest Algorithmic Barrier:** Neither internal recurrence (RNN) nor externalized token recurrence (transformer scratch/filler) enables SGD to escape the memorization basin on next-prime. | Transition directly to Phase 2 (`is_prime` 4-arm battery). | + +--- + *Publication note (2026-08-17): this file is mirrored verbatim from the private research repo (prime-grokking/preregistration.md) at the moment the experiment repo went public; hashes cited above are research-repo commits. The experiment repo commit history preserves each mirror step.* diff --git a/design/scratchpad_explainer.html b/design/scratchpad_explainer.html new file mode 100644 index 0000000..1f3807f --- /dev/null +++ b/design/scratchpad_explainer.html @@ -0,0 +1,436 @@ + + + + + + Prime Grokking: Scratchpad & Filler Token Experiment + + + +
+
+
Research Addendum 8
+

Prime Grokking: Scratchpads & Fillers

+

A visual breakdown of why standard neural networks fail on prime numbers, and how token-space computation tests the boundaries of algorithmic emergence.

+
+ + +
+

1. The Core Puzzle: Why Primes Break Standard Grokking

+
+

When researchers train neural networks on modular arithmetic (like (a + b) mod 97), the network suddenly experiences grokking: after long overfitting, it abruptly discovers the generalized circle algorithm (Fourier transform) because it is simpler and lower-norm than memorization.

+

Next-Prime is completely different. Finding the next prime after n requires a two-level nested algorithm:

+ +
+ + + + Outer Loop: Candidates + c = n+1, n+2, n+3, ... + + + + + + + Inner Loop: Trial Division + Check if c is divisible by + p ∈ {2, 3, 5, 7, ..., √c} + + + + + If no divisors: + Return c + + + + If divisible: reject & next candidate + + + + + + + +
+

A standard feedforward Transformer has a fixed number of layers. It cannot run an unbounded while-loop. In experiments E1–E7, we proved that even training for 4,000,000 steps never produces grokking on next-prime: the model just memorizes a lookup table for numbers in range, and scores 0%–3% out-of-range.

+
+
+ + +
+

2. The Proposed Solution: Computation in Token Space

+
+

If the model doesn't have enough internal depth to perform multiple serial operations, we can give it intermediate tokens to think before answering.

+

Recent theoretical work by Pfau et al. (2024, "Let's Think Dot by Dot") made a surprising prediction: filler tokens (e.g. dots or pauses) only help if the hidden subcomputations are parallelizable. Checking divisors {2, 3, 5, 7} are independent parallel operations! Therefore, next-prime is the ideal testbed for this hypothesis.

+
+
+ + +
+

3. The 4-Arm Experimental Design

+

To scientifically isolate why intermediate tokens help (or don't), we test four distinct arms:

+ +
+ +
+
+ Arm A: Direct Baseline + Control +
+

Input goes directly to output. No intermediate steps.

+
+ 4 + 2 + → + 4 + 3 + <eos> +
+

Tests: Can pure fixed-depth attention solve next-prime? (We know from E7 this fails out-of-range).

+
+ + +
+
+ Arm B: Structured Scratchpad + Algorithm Supervision +
+

Ground-truth trial division steps are spelled out in tokens.

+
+ 42 + → + c=43 + d2:0 + d3:0 + d5:0 + # + 43 +
+

Tests: If the algorithm is explicitly supervised, does the model grok and generalize to unseen ranges?

+
+ + +
+
+ Arm C: Pause / Filler Tokens + Pfau Hypothesis +
+

Fixed 16 identical pause tokens (no intermediate labels).

+
+ 42 + → + <p> + <p> + <p> + ... + # + 43 +
+

Tests: Does extra compute depth alone allow the transformer to execute parallel divisor checks silently?

+
+ + +
+
+ Arm D: Random Noise Tokens + Length / Bias Control +
+

Fixed 16 random letters from a disjoint alphabet ([a-p]).

+
+ 42 + → + x + m + k + ... + # + 43 +
+

Tests: Does any sequence expansion help, or is static pause token embedding special?

+
+
+
+ + +
+

4. What Each Comparison Proves

+
+ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
Observed PatternScientific InterpretationSignificance
Arm B >> Arm A, C, DAlgorithm Decomposition Required: Extra compute alone does nothing; explicit intermediate supervision is required to guide SGD.Confirms Nye et al. Scratchpad mechanism.
Arm C >> Arm APfau et al. Confirmed: Unsupervised filler tokens provide enough hidden attention routing to compute parallel divisibility tests.Major theoretical finding! First clean toy demonstration on non-group tasks.
Arm D ≈ Arm C > Arm APure Depth Invariance: Expanding sequence length improves representational capacity regardless of token semantics.Points to transformer attention capacity dynamics.
All Arms Fail ($P4$) Out-of-RangeAbsolute Algorithmic Wall: Neither internal recurrence nor token-space scratchpads allow next-token models to generalize prime discovery.Falsifies scratchpad extrapolation for unbounded search.
+
+ +
+

Summary of the Proposed Experiment

+

We will train a 2-layer GPT Transformer across all four arms in the $[2, 1000]$ regime for 200k steps with weight decay $0.1$. We evaluate exact-match accuracy both in-range ($[2, 1000]$) and on the unseen probe range ($[1001, 2000]$) to test true algorithmic generalization.

+
+
+
+ + -- cgit v1.2.3