How can Bayesian nonparametric memory improve test-time adaptation of LLM reasoning?

A cheatsheet stores behaviors, not answers

The paper treats a cheatsheet as a collection of concise, natural-language insights that a model can consult while solving a new problem. The stored content is not the final answer and not a full worked solution: it is a short reasoning behavior produced through self-reflection, such as checking unit consistency before calculating, or testing whether swapping variables leaves an equation unchanged.

The authors deliberately fix this content and vary only its organization. They state that using self-reflection behaviors for memory content allows a clear comparison of memory organization mechanisms without the confounding effect of differences in memory content. So the contribution is about how behaviors are grouped and retrieved, not about inventing better behaviors.

This distinction matters for reading the results. When the Bayesian Cheatsheet beats a baseline, the gain comes from the structure imposed on the same kind of behavior, not from a stronger base model or richer reflections.

Flat retrieval cannot grow or reorganize

The paper argues that as a cheatsheet grows, organization must do more than retrieve similar entries. Related behaviors may form groups, and those groups may be reusable across domains. A new experience at test time may reinforce an existing group or reveal a strategy the current organization does not capture.

Static cheatsheets and flat similarity-based retrieval do not address this, the authors write. Clustering adds organization but does not support principled growth and requires the number of clusters to be known in advance. Existing structured memory systems often rely on LLM judgments and similarity heuristics to define and evolve structure, which the paper says becomes difficult to maintain as memory grows.

The design questions the paper separates are what information to store and how to organize it. It focuses on the second, which is why the comparison targets memory modules rather than reflection quality.

HDP-GMM shares clusters across domains

The Bayesian Cheatsheet is a Hierarchical Dirichlet Process Gaussian Mixture Model over behavior embeddings. As a nonparametric unbounded clustering mechanism, it gives the paper three properties it wants for test-time memory management: the number of clusters is driven purely by the data seen so far, the hierarchical structure separates generally usable memories from domain-specific ones, and the posterior probabilities of cluster assignment serve a dual purpose in assigning memories to clusters and in input-conditioned retrieval.

The hierarchy shares components across domains while allowing domain-specific mixing weights. The paper reports that this explicit domain conditioning matters: in the online setting without refitting on Qwen3-32B, the hierarchical HDP-GMM reached 81.1 on AIME'25, 26.4 on Omni-MATH, and 30.1 on PhysReason, versus 76.7, 24.0, and 27.3 for a flat, domain-pooled DP-GMM with all other mechanisms and hyperparameters held fixed.

The HDP prior also induces a rich-get-richer bias, so components repeatedly observed are favored. Retrieval uses the posterior predictive to select relevant behaviors for a query.

Online updates spawn components only when novel

Adaptation is cheap because the mixture's sufficient statistics are softly updated after each sample. A new globally shared component is spawned only when the posterior predictive probability of a new component for a behavior exceeds a novelty threshold, set to 0.5 in the main experiments; otherwise the behavior is softly added to existing components with weight above 10^-6.

Periodic refitting rebuilds Gaussian statistics from stored hard assignments, runs a single collapsed Gibbs step over all behaviors with domain labels fixed, and greedily merges components whose symmetric Gaussian KL-divergence is below a threshold. This is what lets the memory reorganize and reconcile drift introduced by many soft updates.

The novelty threshold controls the balance. At 0.1 the novelty score consistently exceeds the threshold, aggressively creating new components (212) that must be pruned by the periodic Gibbs sweep, which the paper says likely adds noise to retrieval and noticeably hurts performance (24.3 on Omni-MATH). At 0.7 novelty scores are too low to spawn components, so all births come from refitting. Performance peaks at 0.5, which also balances novelty-based spawning with refit-based creation.

Gains hold across three reasoning benchmarks

The paper reports clear performance gains relative to existing memory modules across AIME'25, Omni-MATH, and PhysReason, even in the cold-start setting. In the reported comparison, BC-PP (the posterior-predictive variant) reached 77.8 on AIME'25, 22.3 on Omni-MATH, and 27.0 on PhysReason, while BC-centroids reached 74.4, 20.5, and 24.8. The base model scored 71.1, 18.1, and 16.4.

Among the baselines, metacognitive reuse with k' = 5 reached 75.6, 17.8, and 21.7; direct behavior retrieval reached 72.2, 18.6, and 23.5; random behavior selection reached 72.2, 18.9, and 18.6. The two Bayesian Cheatsheet variants are the strongest entries in that table.

Retrieval size matters but is not fragile. Sweeping the number of retrieved components k' for static BC-PP on Qwen3-32B, accuracy rose from 72.2 at k' = 1 to 77.8 at k' = 5 on AIME'25, from 19.5 to 22.3 on Omni-MATH, and from 24.8 to 27.0 on PhysReason. The paper notes that even k' = 3 would outperform every baseline across the three benchmarks.

Refit interval trades novelty against Gibbs splits

Component counts can grow two ways: a novelty-triggered spawn, or a new component formed during collapsed Gibbs resampling in the refit step, effectively splitting out of an existing one. The refit interval g controls how often the second happens.

On Omni-MATH with Qwen3-32B, starting from K = 64, aggressive refitting at small g produces mostly Gibbs-induced components: at g = 5 the final count was 94 with a net increase of 30, of which only 5 were novelty-triggered. At g = 50 the final count was 85 with a net increase of 21, split 11 novelty-triggered and 10 refit-triggered, and accuracy was 26.6, the highest reported in that sweep. The paper selected g = 50 for its refitting results and used g = 10 for AIME'25 and PhysReason-mini because a single pass over those test sets contains only 30 and 31 samples.

The paper also notes that every value of g tested would at least match or outperform the strongest baseline for Omni-MATH, so the choice is a tuning preference rather than a cliff.

Threshold spawning plus KL merging works best

The paper compares deterministic threshold-based component creation against a Bernoulli sampling scheme faithful to the CRP birth mechanism, and separately ablates KL-based merging during refitting. On Omni-MATH with refitting at g = 50, threshold with KL-merge scored 26.6, sampling with KL-merge 26.0, threshold without KL-merge 25.9, and sampling without KL-merge 26.2.

The component counts differ sharply. Without refitting (g = 0), thresholding produced a final K of 76 with a net increase of 12, all novelty-triggered, while sampling produced K = 138 with a net increase of 74, all Bernoulli-triggered. With refitting, threshold with KL-merge ended at 85 components and sampling with KL-merge at 129.

One counterintuitive detail: removing KL-merge in the thresholding method slightly reduced the final component count but cut novelty-triggered births from 11 to 2. The paper explains that merging condenses coverage, which raises the novelty score for subsequent points and leads to more components being created through the threshold.

Scope limits and the priority to watch

The experiments focus on single-turn problem solving with small-to-medium-size non-agentic language models of roughly 30B parameters. Agentic and multi-turn benchmarks are explicitly beyond the paper's scope, though the authors see practical potential for iterative retrieval from the Bayesian Cheatsheet. Refitting and retrieval costs also grow over indefinitely long evaluation streams, which the paper says points to a need for principled discarding mechanisms to selectively retain behaviors.

Given those boundaries, the most decision-relevant comparison is not Bayesian Cheatsheet versus the base model, where the gain is largest but least informative, but the two internal choices the paper actually tunes: the novelty threshold and the refit interval. At tau_new = 0.5 and g = 50 the memory balances novelty-triggered births against Gibbs-induced splits, and the paper's own ablations show that pushing either knob to an extreme either floods retrieval with noise or removes novelty-driven growth entirely. Readers evaluating this memory design should treat that balance, not the headline benchmark gap, as the transferable finding.

Sources used in this answer