diff options
| author | CaptainJack2491 <jayrupnakawala@gmail.com> | 2026-08-29 23:07:18 +0100 |
|---|---|---|
| committer | CaptainJack2491 <jayrupnakawala@gmail.com> | 2026-08-29 23:07:18 +0100 |
| commit | 0888ad62315b9b18c050d77ef9077b2405eb0aef (patch) | |
| tree | 4473ae7c8aee00472890d7fc1fd88867ce1f1e97 | |
| parent | c93eeaf282d71a0839d19cb3db9839cc3357f91a (diff) | |
preregister Addendum 8: 4-arm token-space recurrence & decomposition test (E8)
| -rw-r--r-- | design/preregistration.md | 58 | ||||
| -rw-r--r-- | design/scratchpad_explainer.html | 436 |
2 files changed, 494 insertions, 0 deletions
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 @@ +<!DOCTYPE html> +<html lang="en"> +<head> + <meta charset="UTF-8"> + <meta name="viewport" content="width=device-width, initial-scale=1.0"> + <title>Prime Grokking: Scratchpad & Filler Token Experiment</title> + <style> + :root { + --bg: #0f172a; + --card-bg: #1e293b; + --border: #334155; + --text-primary: #f8fafc; + --text-secondary: #94a3b8; + --accent-blue: #38bdf8; + --accent-purple: #c084fc; + --accent-green: #4ade80; + --accent-amber: #fbbf24; + --accent-rose: #fb7185; + --code-bg: #090d16; + } + + * { + box-sizing: border-box; + margin: 0; + padding: 0; + } + + body { + font-family: -apple-system, BlinkMacSystemFont, "Segoe UI", Roboto, Helvetica, Arial, sans-serif; + background-color: var(--bg); + color: var(--text-primary); + line-height: 1.6; + padding: 2rem 1rem; + } + + .container { + max-width: 1050px; + margin: 0 auto; + } + + header { + margin-bottom: 3rem; + text-align: center; + border-bottom: 1px solid var(--border); + padding-bottom: 2rem; + } + + h1 { + font-size: 2.4rem; + font-weight: 800; + background: linear-gradient(135deg, var(--accent-blue), var(--accent-purple)); + -webkit-background-clip: text; + -webkit-text-fill-color: transparent; + margin-bottom: 0.75rem; + } + + .subtitle { + font-size: 1.15rem; + color: var(--text-secondary); + max-width: 750px; + margin: 0 auto; + } + + .badge { + display: inline-block; + padding: 0.25rem 0.75rem; + border-radius: 9999px; + font-size: 0.8rem; + font-weight: 600; + text-transform: uppercase; + letter-spacing: 0.05em; + margin-bottom: 1rem; + background: rgba(56, 189, 248, 0.1); + color: var(--accent-blue); + border: 1px solid rgba(56, 189, 248, 0.2); + } + + section { + margin-bottom: 3rem; + } + + h2 { + font-size: 1.6rem; + color: var(--text-primary); + margin-bottom: 1.25rem; + display: flex; + align-items: center; + gap: 0.5rem; + } + + h2::before { + content: ""; + display: inline-block; + width: 4px; + height: 1.4rem; + background: var(--accent-blue); + border-radius: 2px; + } + + p { + color: var(--text-secondary); + margin-bottom: 1rem; + font-size: 1.05rem; + } + + .card { + background: var(--card-bg); + border: 1px solid var(--border); + border-radius: 12px; + padding: 1.5rem; + margin-bottom: 1.5rem; + box-shadow: 0 4px 6px -1px rgba(0, 0, 0, 0.2); + } + + .grid-2 { + display: grid; + grid-template-columns: 1fr 1fr; + gap: 1.5rem; + } + + @media (max-width: 768px) { + .grid-2 { + grid-template-columns: 1fr; + } + } + + .arm-card { + background: var(--card-bg); + border: 1px solid var(--border); + border-radius: 12px; + padding: 1.5rem; + position: relative; + overflow: hidden; + transition: transform 0.2s, border-color 0.2s; + } + + .arm-card:hover { + transform: translateY(-2px); + border-color: var(--accent-blue); + } + + .arm-header { + display: flex; + justify-content: space-between; + align-items: center; + margin-bottom: 1rem; + } + + .arm-tag { + font-weight: 700; + font-size: 1.1rem; + } + + .arm-a { border-top: 4px solid var(--text-secondary); } + .arm-b { border-top: 4px solid var(--accent-green); } + .arm-c { border-top: 4px solid var(--accent-blue); } + .arm-d { border-top: 4px solid var(--accent-amber); } + + .token-sequence { + background: var(--code-bg); + border: 1px solid var(--border); + border-radius: 8px; + padding: 1rem; + font-family: ui-monospace, SFMono-Regular, Menlo, Monaco, Consolas, monospace; + font-size: 0.9rem; + margin: 1rem 0; + display: flex; + flex-wrap: wrap; + gap: 0.4rem; + align-items: center; + } + + .token { + display: inline-flex; + align-items: center; + justify-content: center; + padding: 0.25rem 0.6rem; + border-radius: 4px; + font-weight: 600; + } + + .tok-input { background: #1e3a8a; color: #93c5fd; border: 1px solid #3b82f6; } + .tok-trace { background: #064e3b; color: #6ee7b7; border: 1px solid #10b981; } + .tok-pause { background: #312e81; color: #c4b5fd; border: 1px solid #6366f1; } + .tok-rand { background: #78350f; color: #fde68a; border: 1px solid #d97706; } + .tok-ans { background: #831843; color: #fbcfe8; border: 1px solid #ec4899; } + .tok-sep { background: #374151; color: #d1d5db; } + + .comparison-table { + width: 100%; + border-collapse: collapse; + margin: 1.5rem 0; + font-size: 0.95rem; + } + + .comparison-table th, .comparison-table td { + padding: 0.9rem 1rem; + text-align: left; + border-bottom: 1px solid var(--border); + } + + .comparison-table th { + background: rgba(30, 41, 59, 0.8); + color: var(--text-primary); + font-weight: 600; + } + + .comparison-table tr:hover { + background: rgba(51, 65, 85, 0.3); + } + + .highlight-green { color: var(--accent-green); font-weight: 600; } + .highlight-blue { color: var(--accent-blue); font-weight: 600; } + .highlight-amber { color: var(--accent-amber); font-weight: 600; } + .highlight-rose { color: var(--accent-rose); font-weight: 600; } + + .diagram-container { + background: var(--code-bg); + border: 1px solid var(--border); + border-radius: 12px; + padding: 1.5rem; + margin: 1.5rem 0; + text-align: center; + } + + svg { + max-width: 100%; + height: auto; + } + + .takeaway-box { + background: linear-gradient(135deg, rgba(56, 189, 248, 0.1), rgba(192, 132, 252, 0.1)); + border: 1px solid rgba(56, 189, 248, 0.3); + border-radius: 12px; + padding: 1.5rem; + margin-top: 2rem; + } + + .takeaway-box h3 { + color: var(--accent-blue); + margin-bottom: 0.5rem; + } + </style> +</head> +<body> + <div class="container"> + <header> + <div class="badge">Research Addendum 8</div> + <h1>Prime Grokking: Scratchpads & Fillers</h1> + <p class="subtitle">A visual breakdown of why standard neural networks fail on prime numbers, and how token-space computation tests the boundaries of algorithmic emergence.</p> + </header> + + <!-- SECTION 1: THE PUZZLE --> + <section> + <h2>1. The Core Puzzle: Why Primes Break Standard Grokking</h2> + <div class="card"> + <p>When researchers train neural networks on <strong>modular arithmetic</strong> (like <code>(a + b) mod 97</code>), the network suddenly experiences <strong>grokking</strong>: after long overfitting, it abruptly discovers the generalized circle algorithm (Fourier transform) because it is simpler and lower-norm than memorization.</p> + <p><strong>Next-Prime is completely different.</strong> Finding the next prime after <em>n</em> requires a <em>two-level nested algorithm</em>:</p> + + <div class="diagram-container"> + <svg viewBox="0 0 800 220" xmlns="http://www.w3.org/2000/svg"> + <!-- Candidate search --> + <rect x="50" y="30" width="200" height="60" rx="8" fill="#1e3a8a" stroke="#3b82f6" stroke-width="2"/> + <text x="150" y="65" fill="#ffffff" text-anchor="middle" font-size="14" font-weight="bold">Outer Loop: Candidates</text> + <text x="150" y="80" fill="#93c5fd" text-anchor="middle" font-size="12">c = n+1, n+2, n+3, ...</text> + + <!-- Arrow --> + <path d="M 250 60 L 330 60" stroke="#94a3b8" stroke-width="2" marker-end="url(#arrow)"/> + + <!-- Divisibility test --> + <rect x="330" y="20" width="240" height="80" rx="8" fill="#064e3b" stroke="#10b981" stroke-width="2"/> + <text x="450" y="50" fill="#ffffff" text-anchor="middle" font-size="14" font-weight="bold">Inner Loop: Trial Division</text> + <text x="450" y="70" fill="#6ee7b7" text-anchor="middle" font-size="12">Check if c is divisible by</text> + <text x="450" y="88" fill="#6ee7b7" text-anchor="middle" font-size="12">p ∈ {2, 3, 5, 7, ..., √c}</text> + + <!-- Output decision --> + <path d="M 570 60 L 630 60" stroke="#94a3b8" stroke-width="2"/> + <rect x="630" y="30" width="130" height="60" rx="8" fill="#831843" stroke="#ec4899" stroke-width="2"/> + <text x="695" y="58" fill="#ffffff" text-anchor="middle" font-size="13" font-weight="bold">If no divisors:</text> + <text x="695" y="76" fill="#fbcfe8" text-anchor="middle" font-size="12">Return c</text> + + <!-- Rejection loop --> + <path d="M 450 100 L 450 160 L 150 160 L 150 90" fill="none" stroke="#fb7185" stroke-width="2" stroke-dasharray="5,5"/> + <text x="300" y="150" fill="#fb7185" font-size="12">If divisible: reject & next candidate</text> + + <defs> + <marker id="arrow" viewBox="0 0 10 10" refX="6" refY="5" markerWidth="6" markerHeight="6" orient="auto-start-reverse"> + <path d="M 0 0 L 10 5 L 0 10 z" fill="#94a3b8"/> + </marker> + </defs> + </svg> + </div> + <p>A standard feedforward Transformer has a <strong>fixed number of layers</strong>. It cannot run an unbounded while-loop. In experiments E1–E7, we proved that even training for <strong>4,000,000 steps</strong> never produces grokking on next-prime: the model just memorizes a lookup table for numbers in range, and scores <strong>0%–3% out-of-range</strong>.</p> + </div> + </section> + + <!-- SECTION 2: THE IDEA --> + <section> + <h2>2. The Proposed Solution: Computation in Token Space</h2> + <div class="card"> + <p>If the model doesn't have enough internal depth to perform multiple serial operations, we can give it <strong>intermediate tokens</strong> to think before answering.</p> + <p>Recent theoretical work by <em>Pfau et al. (2024, "Let's Think Dot by Dot")</em> made a surprising prediction: <strong>filler tokens (e.g. dots or pauses) only help if the hidden subcomputations are parallelizable</strong>. Checking divisors {2, 3, 5, 7} are independent parallel operations! Therefore, next-prime is the ideal testbed for this hypothesis.</p> + </div> + </section> + + <!-- SECTION 3: THE 4-ARM EXPERIMENT --> + <section> + <h2>3. The 4-Arm Experimental Design</h2> + <p>To scientifically isolate <em>why</em> intermediate tokens help (or don't), we test four distinct arms:</p> + + <div class="grid-2"> + <!-- ARM A --> + <div class="arm-card arm-a"> + <div class="arm-header"> + <span class="arm-tag">Arm A: Direct Baseline</span> + <span class="badge" style="background:#334155;color:#f8fafc;border:none;">Control</span> + </div> + <p>Input goes directly to output. No intermediate steps.</p> + <div class="token-sequence"> + <span class="token tok-input">4</span> + <span class="token tok-input">2</span> + <span class="token tok-sep">→</span> + <span class="token tok-ans">4</span> + <span class="token tok-ans">3</span> + <span class="token tok-sep"><eos></span> + </div> + <p style="font-size:0.9rem;"><em>Tests: Can pure fixed-depth attention solve next-prime? (We know from E7 this fails out-of-range).</em></p> + </div> + + <!-- ARM B --> + <div class="arm-card arm-b"> + <div class="arm-header"> + <span class="arm-tag highlight-green">Arm B: Structured Scratchpad</span> + <span class="badge" style="background:rgba(16,185,129,0.2);color:#34d399;border:none;">Algorithm Supervision</span> + </div> + <p>Ground-truth trial division steps are spelled out in tokens.</p> + <div class="token-sequence"> + <span class="token tok-input">4</span><span class="token tok-input">2</span> + <span class="token tok-sep">→</span> + <span class="token tok-trace">c=43</span> + <span class="token tok-trace">d2:0</span> + <span class="token tok-trace">d3:0</span> + <span class="token tok-trace">d5:0</span> + <span class="token tok-sep">#</span> + <span class="token tok-ans">4</span><span class="token tok-ans">3</span> + </div> + <p style="font-size:0.9rem;"><em>Tests: If the algorithm is explicitly supervised, does the model grok and generalize to unseen ranges?</em></p> + </div> + + <!-- ARM C --> + <div class="arm-card arm-c"> + <div class="arm-header"> + <span class="arm-tag highlight-blue">Arm C: Pause / Filler Tokens</span> + <span class="badge" style="background:rgba(56,189,248,0.2);color:#38bdf8;border:none;">Pfau Hypothesis</span> + </div> + <p>Fixed 16 identical pause tokens (no intermediate labels).</p> + <div class="token-sequence"> + <span class="token tok-input">4</span><span class="token tok-input">2</span> + <span class="token tok-sep">→</span> + <span class="token tok-pause"><p></span> + <span class="token tok-pause"><p></span> + <span class="token tok-pause"><p></span> + <span class="token tok-pause">...</span> + <span class="token tok-sep">#</span> + <span class="token tok-ans">4</span><span class="token tok-ans">3</span> + </div> + <p style="font-size:0.9rem;"><em>Tests: Does extra compute depth alone allow the transformer to execute parallel divisor checks silently?</em></p> + </div> + + <!-- ARM D --> + <div class="arm-card arm-d"> + <div class="arm-header"> + <span class="arm-tag highlight-amber">Arm D: Random Noise Tokens</span> + <span class="badge" style="background:rgba(251,191,36,0.2);color:#fbbf24;border:none;">Length / Bias Control</span> + </div> + <p>Fixed 16 random letters from a disjoint alphabet (<code>[a-p]</code>).</p> + <div class="token-sequence"> + <span class="token tok-input">4</span><span class="token tok-input">2</span> + <span class="token tok-sep">→</span> + <span class="token tok-rand">x</span> + <span class="token tok-rand">m</span> + <span class="token tok-rand">k</span> + <span class="token tok-rand">...</span> + <span class="token tok-sep">#</span> + <span class="token tok-ans">4</span><span class="token tok-ans">3</span> + </div> + <p style="font-size:0.9rem;"><em>Tests: Does any sequence expansion help, or is static pause token embedding special?</em></p> + </div> + </div> + </section> + + <!-- SECTION 4: WHAT EACH OUTCOME PROVES --> + <section> + <h2>4. What Each Comparison Proves</h2> + <div class="card"> + <table class="comparison-table"> + <thead> + <tr> + <th>Observed Pattern</th> + <th>Scientific Interpretation</th> + <th>Significance</th> + </tr> + </thead> + <tbody> + <tr> + <td><strong class="highlight-green">Arm B >> Arm A, C, D</strong></td> + <td><strong>Algorithm Decomposition Required:</strong> Extra compute alone does nothing; explicit intermediate supervision is required to guide SGD.</td> + <td>Confirms Nye et al. Scratchpad mechanism.</td> + </tr> + <tr> + <td><strong class="highlight-blue">Arm C >> Arm A</strong></td> + <td><strong>Pfau et al. Confirmed:</strong> Unsupervised filler tokens provide enough hidden attention routing to compute parallel divisibility tests.</td> + <td><strong>Major theoretical finding!</strong> First clean toy demonstration on non-group tasks.</td> + </tr> + <tr> + <td><strong class="highlight-amber">Arm D ≈ Arm C > Arm A</strong></td> + <td><strong>Pure Depth Invariance:</strong> Expanding sequence length improves representational capacity regardless of token semantics.</td> + <td>Points to transformer attention capacity dynamics.</td> + </tr> + <tr> + <td><strong class="highlight-rose">All Arms Fail ($P4$) Out-of-Range</strong></td> + <td><strong>Absolute Algorithmic Wall:</strong> Neither internal recurrence nor token-space scratchpads allow next-token models to generalize prime discovery.</td> + <td>Falsifies scratchpad extrapolation for unbounded search.</td> + </tr> + </tbody> + </table> + </div> + + <div class="takeaway-box"> + <h3>Summary of the Proposed Experiment</h3> + <p>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 <strong>in-range ($[2, 1000]$)</strong> and on the unseen <strong>probe range ($[1001, 2000]$)</strong> to test true algorithmic generalization.</p> + </div> + </section> + </div> +</body> +</html> |
