Structured Sparse Memory for Recurrent Reasoning

Conference: NeurIPS2026
arXiv: 2609.33270
Code: https://github.com/water-vapor/charm
Area: LLM Reasoning / Recurrent Reasoning / Structured Task Memory
Keywords: compositional sparse embedding, task-conditioned memory, recurrent reasoning, rule-preserving synthetic data, continual learning

TL;DR

CoSE replaces a large task table with a factorized FiLM conditioning branch and rank-32 instance residuals, reducing task-memory parameters to roughly 1/15 while improving pass@2 in controlled ARC experiments; CHARM combines this memory with synthetic data, recurrent computation, and extended training to reach 84.0% / 46.7% on ARC-AGI-1 / 2 public evaluation, which cannot be attributed entirely to CoSE.

Background & Motivation

From-scratch recurrent models such as HRM, TRM, and URM repeatedly update latent states and candidate outputs rather than expressing reasoning as autoregressive text. Their 7–27M backbone sizes are often contrasted with large pretrained models, but an ARC solver contains more than its backbone: a task table indexed jointly by puzzle, geometric transformation, and color permutation stores an independent conditioning vector for each augmented instance. This table contains approximately 448M parameters on ARC-AGI-1 and 610M on ARC-AGI-2. Excluding sparse lookup parameters hides a major source of memory capacity.

Removing or narrowing the table hurts accuracy, but fully factorizing it over known attributes is also insufficient. Rotated versions of the same puzzle should share rule information, yet particular puzzle–augmentation combinations may need private corrections. Keeping only shared representations removes that instance-specific capacity. Meanwhile, new input–output pairs generated by rule programs offer richer coverage than rotations, reflections, and recoloring alone. Evaluating recurrent architectures therefore requires separating the effects of memory, synthetic data, and test-time compute.

Core Idea: assign reusable puzzle and augmentation structure to a compositional conditioning branch, retain nonshared instance differences in a narrow residual table, and separately measure the contributions of memory, rule-preserving data, and recurrent computation within one system.

Method

Overall Architecture

CHARM takes an ARC input grid and a task descriptor and predicts an output grid. During training, rule-preserving data expands the official training tasks. Each sample's puzzle ID, dihedral transformation, and color permutation enter CoSE to produce a 512-dimensional task condition. This condition occupies the task prefix, the recurrent backbone repeatedly refines its latent state, and the evaluator inverse-transforms and votes over predictions from augmented views and recent checkpoints.

These are two distinct data flows: rule generators provide training supervision, not inference-time answers, whereas CoSE supplies conditioning on every forward pass. The main experiments follow the XRM protocol: demonstration input–output pairs from public-evaluation puzzles are available during training, but the test outputs associated with the inputs to be predicted are not. Adaptation to genuinely unseen puzzles is a separate experiment and must not be conflated with the main generalization setting.

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    S["Official training puzzles"] --> D["Rule-preserving data"]
    X["Input grid and task descriptor"] --> F["Factorized FiLM"]
    D -.->|Training samples and supervision only| X
    F --> M["Instance residual memory"]
    X -->|Joint instance index| M
    M --> R["Recurrent refinement<br/>and aggregation"]
    X -->|Grid encoding| R
    R --> O["Ranked output grids"]
    R -->|Outer-loop latent-state feedback| R

Key Designs

1. Rule-preserving data: expand instances of a rule rather than only changing appearance

Rotations, reflections, and recoloring increase sample count without exposing the model to substantially more object layouts and input structures under the same rule. Re-ARC provides programmatic generators for ARC-AGI-1 training puzzles. Re-ARC2 covers all 1,000 ARC-AGI-2 training puzzles: 391 reuse existing Re-ARC coverage, while a coding agent implements generators and verifiers for the other 609. Each task package must reproduce the official examples with its verifier, generate up to 1,000 unique non-identity examples, and pass programmatic checks, manual visual inspection, and cross-model auditing.

This is neither human-free generation nor the addition of arbitrary new task families. Rule implementation and review supply puzzle-specific priors, and the paper acknowledges that comparisons with and without synthetic data do not have strictly equivalent input conditions. Generation applies only to official training tasks; access to public-evaluation demonstrations belongs to the separate XRM protocol. Default sampling uses 100 synthetic augmentation views per puzzle, up to 1,000 geometric–color views for ordinary tasks, and repeats ConceptARC and public-evaluation demonstrations twice in the sampling index so they are not overwhelmed by synthetic data.

2. Factorized FiLM: share conditioning parameters across puzzle rules and augmentation structure

The original task table converts the joint descriptor into one index and retrieves an independent 512-dimensional vector. CoSE avoids relearning the entire puzzle for every rotation and recoloring: puzzle IDs and the eight dihedral transformations use separate small tables, while color permutations are represented by a shared base vector and nine color-slot vectors. A permutation only reorders those slots, allowing one shared parameter set to cover \(9!=362{,}880\) permutations of non-background colors. The implementation uses a 53-dimensional base and nine 51-dimensional slots, retaining a total width of 512.

The geometric and color vectors are concatenated to generate FiLM scale and shift vectors that modulate the puzzle vector elementwise. Geometric conditioning can therefore change how the puzzle representation responds to a view without requiring a full combinatorial table. With puzzle vector \(p_i\) and augmentation condition \(a_{g,\pi}\), the central mechanism is:

\[ e^{\mathrm{comp}}_{i,g,\pi}=(1+\gamma_{g,\pi})\odot p_i+\beta_{g,\pi},\qquad \gamma_{g,\pi}=W_\gamma a_{g,\pi}+b_\gamma,\quad \beta_{g,\pi}=W_\beta a_{g,\pi}+b_\beta. \]

This branch captures transferable regularities rather than guaranteeing that every instance can be represented exactly by a few factors. In the short-training experiment on training puzzles, more expressive FiLM operators, hypernetworks, and mixture-of-experts alternatives still fail to close the pass@1000 gap to the independent table. Nineteen puzzles are solved by the full table but by none of the pure-composition variants. The authors identify no common manual category among them, so this establishes an observed capacity gap, not a proof that a particular rule class cannot be factorized.

3. Instance residual memory: use narrow private capacity to repair the shared branch's blind spots

Compressing an independent table from width 512 to 32 hurts fitting, while composition alone can lose instance-specific information. CoSE retains both: the original joint index retrieves a rank-32 residual row, a shared bias-free projection expands it to width 512, and the result is added to the compositional representation. The shared branch no longer has to absorb every exceptional combination, and the instance table no longer has to duplicate most rule structure.

An optional sigmoid gate generated from the compositional representation controls how much residual signal enters each hidden dimension. For joint instance index \(j\) and residual table \(R\), fusion is:

\[ e^{\mathrm{CoSE}}_{i,g,\pi}=e^{\mathrm{comp}}_{i,g,\pi}+m_{i,g,\pi}\odot UR[j],\qquad m_{i,g,\pi}=\sigma(W_m e^{\mathrm{comp}}_{i,g,\pi}+b_m). \]

Without gating, \(m\equiv\mathbf{1}\). The ratio \(32/512=1/16\) describes residual row width, not a 1/16 reduction in the whole model: composition, up-projection, gating, and the backbone must still be counted. On ARC-AGI-1 + Re-ARC, the full table has 448.9M task-memory parameters, versus about 29.6M for ungated CoSE and 29.9M for gated CoSE. Total model sizes are approximately 43.3M / 43.5M, not 29.6M / 29.9M. The roughly 1/15 claim concerns total task memory.

The gate is optional and does not consistently improve every metric. With synthetic data on ARC-AGI-1, ungated pass@2 is 80.71%, versus 80.00% with gating. The final ARC-AGI-1 configuration nevertheless uses gating, while ARC-AGI-2 uses the ungated variant. The main text reports average gate utilization of 48.92% ± 0.06%, but this is a soft-gating behavior statistic. It does not provide evidence of sparse operators skipping storage or computation, and cannot justify a further halving of VRAM usage.

4. Recurrent refinement and aggregation: separate forward reasoning depth, learning horizon, and answer ranking

After task conditioning, the model places each grid on a \(30\times30\) canvas, flattens it into 900 tokens, and prepends 16 positions, with the task vector occupying only the first. The URM-style backbone combines non-causal attention with depthwise-convolutional SwiGLU, hidden width 512, and eight attention heads. A block of four unique Transformer layers is applied 12 times, giving 48 layer applications per inner forward pass. Input embeddings are reinjected on each application, while gradients traverse only the final six block applications.

The outer loop runs for up to 16 steps, carries the latent state forward, detaches gradients between steps, and supervises each output. Thus, deeper recurrence and a longer credit-assignment horizon are different choices: the former adds forward computation, while the latter determines how far training can attribute errors. Matched forward-and-backward FLOP experiments find that too many unique layers overfit and too few lack capacity. At fixed forward configuration, intermediate back-propagation horizons outperform very short or full horizons. CoSE primarily replaces conditioning memory rather than introducing an entirely new recurrent backbone.

Standard evaluation performs all 16 steps without early stopping. Predictions from geometric and color views are inverse-transformed, ranked by votes, and confidence breaks ties; votes from the ten most recent checkpoints are pooled. An additional test-time compute variant combines 16 / 24-step outputs and exponentially decays recent-checkpoint votes with a half-life of ten checkpoints. It helps at standard training budgets, but its benefit diminishes near convergence under extended training. The final 84.0% / 46.7% scores therefore use standard aggregation, not the additional replay variant.

A Worked Example

Consider one rotated and recolored training view of an ARC puzzle; this illustrates the mechanism rather than introducing a quantitative case from the paper. The original system retrieves an independent 512-dimensional row for the joint combination. CoSE first retrieves the puzzle's shared 512-dimensional vector, looks up the rotation representation, reorders the nine color slots, and applies FiLM to obtain a compositional representation. The same joint index additionally retrieves only a 32-dimensional private residual, which is expanded and fused.

The fused vector enters the grid prefix, and the recurrent backbone refines the output. During evaluation, the rotation and color mapping are reversed so views vote for the same original answer. Training supervision still comes from known demonstrations or rule-generated examples; this stage does not obtain the output being predicted.

For a puzzle unseen during pretraining, the separate continual-adaptation protocol can freeze all shared weights and add only a puzzle row. The composition-only variant trains just 512 parameters. Adding rank-32 residuals also trains residual rows for multiple augmented instances, so it no longer uses only 512 trainable parameters per puzzle.

Loss & Training

The generic recurrent backbone uses stablemax cross-entropy on non-padding output tokens and a binary halt loss indicating whether the entire predicted grid is correct:

\[ \mathcal{L}=\mathcal{L}_{\mathrm{tok}}+\tfrac{1}{2}\mathcal{L}_{\mathrm{halt}}. \]

This is not a CoSE-specific objective. Training may halt according to the halt logit and, with probability 0.1, imposes a minimum of 2–16 steps to encourage later refinement. Unseen-puzzle adaptation also compares halt-loss weights of 0 and 0.5; removing the auxiliary loss does not remove adaptive halting.

The default global batch is 768. Private task rows use SignSGD at learning rate \(10^{-2}\). In the final system, two-dimensional dense parameters use Muon and other dense parameters use AdamW at learning rate \(10^{-4}\), with weight decay 0.1 for both sparse and dense groups. Both rates receive 2,000 warmup steps and then remain constant. Evaluation uses dense-parameter EMA with decay 0.999, while sparse task rows retain their current values.

Standard ARC-AGI-1 / 2 budgets are 600k / 1M updates, whereas extended training uses 1.6M / 2.38M. Controlled module experiments and final system scores must be interpreted with this budget distinction.

Key Experimental Results

Main Results

The table reports public-evaluation pass@2 in percent. Repeated configurations give means and sample standard deviations over 3–4 runs. The first eight rows come from Tables 1 / 12; the last two are extended-training system results from Table 5, not matched-budget module ablations.

Dataset	Synthetic data	Task memory / system	pass@2	Training updates
ARC-AGI-1	None	Full task table	59.97 ± 1.77	600k
ARC-AGI-1	None	CoSE, gated	64.91 ± 2.25	600k
ARC-AGI-1	Re-ARC	Full task table	78.50 ± 1.03	600k
ARC-AGI-1	Re-ARC	CoSE, ungated	80.71 ± 0.51	600k
ARC-AGI-2	None	Full task table	15.42 ± 1.51	1M
ARC-AGI-2	None	CoSE, ungated	18.61 ± 1.63	1M
ARC-AGI-2	Re-ARC2	Full task table	28.23 ± 3.58	1M
ARC-AGI-2	Re-ARC2	CoSE, ungated	37.22 ± 1.77	1M
ARC-AGI-1	Re-ARC	CHARM full system, gated	84.0	1.6M
ARC-AGI-2	Re-ARC2	CHARM full system, ungated	46.7	2.38M

On ARC-AGI-2, matched synthetic data improves the full table by 12.81 percentage points and ungated CoSE by 18.61 points. CoSE's advantage over the full table increases from 3.19 points without synthetic data to 8.99 points with it, supporting an interaction between memory structure and data coverage. Matched synthetic data remains the largest measured driver.

Ablation Study

Table 4 fixes the backbone, data, and optimization setup on ARC-AGI-1 + Re-ARC and changes only task memory. Parameter counts exclude the backbone. Architectural variants without error bars are single runs. pass@1000 checks whether the correct output appears among up to 1,000 candidates, not performance when only two answers are submitted.

Config	Task-memory parameters	pass@1	pass@2	pass@1000
Full task table	448.9M	73.25 ± 0.74	78.50 ± 1.03	91.38 ± 0.65
Rank-32 table only	28.1M	70.62	76.62	88.88
Compositional branch only	1.5M	73.50	79.25	89.00
CoSE, rank-32	29.6M	74.29 ± 0.75	80.71 ± 0.51	90.62 ± 0.50
CoSE, gated rank-32	29.9M	74.59 ± 0.74	80.00 ± 0.70	90.94 ± 1.10
CoSE, rank-512	450.4M	77.75	81.50	92.12

Composition alone already exceeds the full table at pass@2 in this synthetic-data public-evaluation setting, but remains lower at pass@1000. Without synthetic data, its pass@2 is only 51.50%, below the full table's 59.97%. Neither “composition is insufficient” nor “composition is sufficient” is a universal conclusion independent of data and metric. Improved pass@2 for rank-32 CoSE likewise does not imply improved coverage under every candidate budget.

Unseen-puzzle adaptation is reported separately below. Starting from 600k-step ARC-AGI-1 checkpoints, models sequentially adapt to 233 previously unseen ARC-AGI-2 training puzzles and 114 public-evaluation puzzles. Only demonstrations are optimized, shared weights stay frozen, and each puzzle receives 1,000 updates. These are memory-only CL results from Table 26, not the main protocol producing 46.7%.

Unseen-puzzle adaptation config	Updated parameters per puzzle: train / eval stream	Train-stream pass@2	Eval-stream pass@2
Full table, rank-512	499.93k / 510.10k	19.73 ± 0.49	4.47 ± 0.57
CoSE, composition only	512 / 512	39.73 ± 1.48	10.76 ± 0.96
CoSE, rank-32	31.76k / 32.39k	43.58 ± 0.58	12.19 ± 0.90

Key Findings

• Candidate coverage and ranking are distinct: CoSE improves low-candidate-budget pass@2 without improving pass@1000 in every setting. Short-training capability diagnostics are not public-evaluation results.
• Frozen shared parameters provide a structural retention guarantee: only new private rows are added; old rows remain unchanged. Table 28's final retained-model comparison is 43.37% ± 0.48%, not Table 26's 43.58% ± 0.58%; the two aggregation settings are not merged.
• More residual capacity is not always better for combinatorial transfer: across seven CAR runs, three-factor CoSE achieves seen pass@2 of 58.86% ± 0.90% but unseen pass@2 of 2.73% ± 0.48%. Composition alone reaches 3.69% ± 0.56% unseen, versus 0 for the full table. Residuals help fit seen combinations but may reduce early pressure to learn shared regularities.
• Language-model evidence has a specific scope: on nanochat d12 trained with 1.19B tokens and Engram hashed 2/3-gram memory, Engram / CoSE at approximately 254M / 258M memory parameters achieve validation bpb of 0.84638 / 0.84436. Composition alone offers almost no benefit at zero lookup capacity, and more training tokens shrink the advantage. This does not establish improvements for all LLMs or downstream tasks.

Highlights & Insights

• Count hidden capacity as part of the model: the task table is not free input encoding. Separately reporting conditioning memory, backbone capacity, and aggregation compute makes comparisons between compact reasoning systems more meaningful.
• Shared regularities and private exceptions are complementary: factorization need not eliminate instance memory entirely. A narrow residual can preserve low-candidate-budget performance more effectively than pure compression or pure sharing.
• New tasks can be written without rewriting old tasks: freezing the backbone and shared composer while adding puzzle rows gives a verifiable path to retention. Storage still grows per puzzle, so this is not unlimited-capacity continual learning.

Limitations & Future Work

• Public-evaluation demonstrations are used in main training, while test outputs are not optimized. The main setting is not zero-shot solving of entirely unseen tasks, and no private-test score is available here to report.
• Several key experiments have 3–4 repeats, but many architectural variants have only one run and some exploratory runs terminate early. Small differences need more seeds, matched budgets, and complete confidence intervals.
• Parameter savings do not imply faster execution. Appendix H estimates ARC-AGI-1 URM / CHARM training-step times of 0.385 / 0.390 seconds on one node with eight H100s, and total times of 86.8 / 87.6 hours. These are estimates, not measured production-run wall-clock durations.
• Synthetic data depends on rule implementation and repeated human review, and generators and verifiers may share mistakes. Independent rule checks, distribution-shift audits, and accounting for human effort would strengthen the evidence.
• Source-level distinctions should be preserved: the main CAR paragraph attributes unseen 3.69% to “structured composition,” while Table 16 identifies it as composition only, with full CoSE at 2.73%. Table 44's 80.71% row matches the ungated result in Table 12, whereas the implementation section specifies gating for the final ARC-AGI-1 configuration. Not every 80.71% result should therefore be labeled gated.
• Future work could constrain residual interference with shared-factor learning and test generalization and system efficiency on genuinely unseen tasks, under fixed storage budgets and measurable sparse execution.

Related Work & Insights

• vs HRM / TRM / URM: CHARM inherits recurrent refinement, task conditioning, and deep supervision, while restructuring task memory and decomposing system gains. Its contribution is not simply deeper recurrence replacing data and capacity.
• vs VARC / Re-ARC: it adopts rule-preserving generation and extends it to ARC-AGI-2. CHARM's main evaluation is not VARC-style per-puzzle test-time training, so protocol differences remain important.
• vs FiLM / factorized embeddings: FiLM supplies factor-conditioned modulation. CoSE's key addition is instance residual capacity alongside composition, rather than affine modulation itself.
• vs Engram: the language experiments retain hashed lookup, contextual gating, and short convolution, adding a shared FiLM path composed from the current and preceding two token embeddings. This variant combines n-gram features rather than directly transplanting ARC puzzle IDs into a language model.

Rating

• Novelty: 4/5 — Reconstructs task memory using shared composition and instance residuals, supported by an empirical decomposition of hidden capacity.
• Experimental Thoroughness: 4/5 — Includes controlled ablations, unseen-puzzle adaptation, and cross-domain tests, but some variants are single runs and protocols are complex.
• Writing Quality: 4/5 — Mechanisms and parameter accounting are clear, with a few table-to-text distinctions requiring careful checking.
• Value: 4/5 — Offers practical lessons for capacity auditing and conditioning-memory design in compact reasoning systems.