Small language models often cannot solve multi-step reasoning tasks at all. On many benchmarks, accuracy sits near chance until models pass a size threshold and then jumps. A common explanation is compounding: if each of $k$ dependent steps succeeds with probability $P$, the whole chain succeeds with about $P^k$. That number stays tiny until $P$ is close to 1. Techniques that help large models, such as long chains of thought or asking the model to check its own work, tend to make small models worse. This proposal asks whether an old idea from document browsing can break that compounding. The idea is Scatter/Gather: cluster a collection coarsely, keep only the promising clusters, and re-cluster just those at finer grain. Here the "collection" is a small model's own sampled guesses about a hidden rule, and the thing that keeps promising clusters is running the guesses as code, not asking the model to judge them.
Stated plainly, the method has four steps. A small model proposes many candidate programs for a puzzle defined by input/output examples. We run the candidates and group them by what they actually output. We keep the groups that match the most examples. We then ask the model to propose refinements inside each kept group, showing it that group's failures. We then measure whether this pushes the model size at which a task "turns on" downward, at the same compute budget as flat sampling.
Core Claim
On programming-by-example tasks, recursive behavioural partitioning of sampled hypotheses turns one long, all-or-nothing reasoning attempt into a sequence of short, externally checked selections. We claim this lowers the smallest model size at which accuracy lifts off the floor. We also claim that the clustering step itself, not just the extra execution feedback, produces part of the gain. It does so by exposing the "consistently wrong" attractors that small models fall into, which lets the budget flow to behaviourally distinct regions of hypothesis space.
The prediction is conditional in a useful way. The benefit should appear only where cluster selection can use an external check. Where selection must rely on the model's own judgment, it should disappear or reverse.
Where This Sits
Three lines of prior work motivate the design.
The first shows that structured inference helps weaker models reason. Hypothesis Search samples natural-language rule hypotheses from GPT-4, reduces them to a subset, implements them in Python, and filters them against examples. On List Functions this raised accuracy from 31% to 69%. HINT runs a fixed three-phase pipeline on ARC-AGI-2: retrieve past solutions by execution similarity, search in natural language, then write and debug code. With a cheaper backbone (Grok 4.1-Fast) it reached 20.8%, where direct code synthesis with GPT-5.2 reached 5%. Neither paper evaluates open-weight models below 8B. Both use a flat or fixed-depth structure rather than recursive re-partitioning. Our method borrows HINT's execution-similarity grouping and Hypothesis Search's execute-and-filter loop, and makes the grouping iterative and lazy.
The second line constrains the design. Small models are hurt by self-directed structure. Self-verification degrades 0.4B and 1.3B models. Self-AMPLIFY helps 7B models but hurts Gemma-2B. Constraint-First Reasoning helps 9B+ models but harms 1.5B models, because they invent false constraints. SLM-MUX finds that small models agree confidently on wrong answers and that discussion among them lowers accuracy by more than 5%. Taken together, these results rule out any design in which the small model chooses which partition to expand. In our design the model only generates candidates, and execution does all of the selecting.
The third line supplies the partitioning template. Scatter/Gather re-clusters only the user-selected subset of a collection. CLAIMSPECT recursively splits claims into aspect trees and penalizes overlap between sibling branches. P-IPP refines coarse partitions and gains a monotone anytime bound as partitions grow finer; it also reports near-optimal solutions at very coarse partitions ($k \approx 5$ to $10$). We take from CLAIMSPECT the rule that siblings must be distinct: two clusters are merged if their behaviour on the examples is identical. We take from P-IPP the anytime property: the best partial-match score can only rise as the tree deepens.
Research Program
We would build a solver that is the same across all model sizes. At the root, the model samples $N_0$ candidate programs, each preceded by a one-line natural-language rule. Each candidate runs on the training inputs. Its behaviour signature is the vector of its outputs on those inputs, and candidates with identical signatures fall into one cluster. Clusters that match no example are dropped. Each surviving cluster gets a score: the fraction of examples it matches, with ties broken by cluster size.
The top $b$ clusters are then expanded. The model receives two or three representative programs from the cluster, along with the specific examples that cluster fails. It samples $N_1$ refinements, which are re-clustered in the same way. Signatures already seen anywhere in the tree are discarded, which is the sibling-distinctness rule. The process stops when a candidate matches all training examples or the token budget runs out. The final answer is the full-match program from the largest cluster, applied to the test input.
Why should this move the threshold? Flat sampling succeeds with probability $1-(1-q)^N$. Here $q$ is the chance that one sample is fully correct and $N$ is the number of samples. For a sub-threshold model, $q$ behaves like $P^k$ and is negligible, so doubling $N$ buys very little. Partitioning replaces $q$ with a product of per-level chances, each of the form "some refinement fixes at least one more example than its parent cluster." Each factor is much larger than $q$ because it asks for a partial improvement, not a complete solution. We will measure these per-level chances directly rather than assuming the decomposition holds.
The analysis has two quantities. The first is the onset scale: the smallest model in a size-graded family at which accuracy exceeds twice the direct-prompting accuracy and at least 20% absolute. The second is the attractor mass: the share of root samples that fall into the single largest wrong cluster. SLM-MUX's "consistently wrong" finding predicts that this share grows as models shrink. If so, flat sampling at small scale largely re-draws the same wrong answer, and deduplication should matter most exactly there.
Baselines
The naive reference is direct prompting: one greedy program per task, run on the test input. Every method uses the same model family, one open-weight family spanning roughly 0.5B to 72B (for example Qwen 2.5, whose 7B and 72B members appear in SLM-MUX), the same prompts, and the same executor.
The strongest existing method is flat sample-and-filter in the style of Hypothesis Search. We sample as many candidates as the tree solver consumes in total tokens and keep a full-match program, chosen by majority over signatures. On List Functions, Hypothesis Search reports 69% accuracy with GPT-4, against 31% for direct prompting, as reported in Hypothesis Search. On 1D-ARC the figures are 73.1% against 39.6%, and on SyGuS 94.3% against 74.8% for CrossBeam. No reported result was found on Lacuna for sub-8B models on these benchmarks. The primary comparison is therefore our own compute-matched rerun, and the GPT-4 figures serve only as a ceiling reference. Beating this baseline means a higher accuracy and a lower onset scale at matched tokens, across three seeds, on at least two of the three benchmarks.
The second baseline is execution-guided beam refinement. It keeps the top-$b$ individual programs by partial-match score and refines each with its failing examples, with no clustering. This is the ablation that isolates our key ingredient. It has the same feedback and the same budget as the tree solver, and differs only in whether candidates are grouped and deduplicated by behaviour. A random-grouping control, which uses clusters of the same sizes but assigned at random, separates the effect of grouping from the effect of deduplication.
The third baseline is SLM-MUX-style confidence aggregation across two small models of different families. It represents the best existing training-free way to combine small models without letting them talk to each other.
All tuning of $N_0$, $N_1$, $b$ and depth happens on a held-out split of List Functions. Each baseline gets an equal tuning grid.
Why not just…?
Why not just sample more and filter, as Hypothesis Search does? This is the main threat. If the chance of a fully correct sample is small but not negligible, flat sampling at a matched budget could tie with our method. Our argument is that for small models most of the budget lands in a few repeated wrong clusters, so extra samples add little new behaviour. The attractor-mass measurement tests this directly. If flat sampling matches the tree solver at every model size, the claim is false, and we would report it that way.
Why not just refine the best candidate with execution feedback, as program-repair loops and HINT's debugging phase do? Beam refinement shares our feedback signal, which is why it is the central ablation. Its weakness is predictable: the top-$b$ programs of a small model are often behavioural duplicates, so the beam collapses onto one attractor. If beam refinement equals the tree solver, the useful ingredient is execution feedback, not partitioning, and the browsing framing adds nothing. The experiment is built to show exactly that if it is true.
Why not just distill or fine-tune the small model? Specializing Smaller Language Models lifted Flan-T5 11B to 27.1% on GSM8K through distillation, but performance on BigBench Hard collapsed and the method needed a large teacher. Our method changes no weights. As a secondary check we will measure accuracy on BigBench Hard before and after, to confirm that no "specialization tax" applies. Distillation and partitioning could also be combined, but that is outside the core question.
Why not just let the model judge its own clusters, or use small-model debate? The self-verification, Self-AMPLIFY, Constraint-First Reasoning and SLM-MUX results all predict that this fails below roughly 7B. We run it anyway as the negative control described below. That turns a design constraint into a test of the mechanism.
Proposed Experiments
The main experiment runs direct prompting, flat sampling, beam refinement, random grouping, SLM-MUX and the tree solver on List Functions, 1D-ARC and SyGuS for every model size. It reports accuracy against model size at matched token budgets, together with the onset scale for each method. ARC-AGI-2 serves as a stretch evaluation at the top three sizes, compared against HINT's reported 20.8% for Grok 4.1-Fast.
The first decisive check is the onset shift. The tree solver must lower the onset scale by at least one step of the size ladder relative to flat sampling. It must also beat beam refinement at the smallest sizes where either method leaves the floor.
The second check is mechanism. The tree solver's advantage over flat sampling should correlate with attractor mass across model sizes. The per-level refinement success rates should also account for the observed accuracy better than the root full-correct rate does.
The third check is the negative control. We swap execution-based cluster scoring for the model's own rating of each cluster. We also run the same tree on GSM8K, where no executable partial check exists and selection must come from the model. We predict that the benefit disappears or reverses below about 7B, mirroring the self-verification and Constraint-First Reasoning findings. If the benefit survives without external checking, our explanation is wrong even if the method works, and the note would have to be rewritten around whatever does explain it.
References
- Hypothesis Search: Inductive Reasoning with Language Models
- HINT: Task Demonstrations for Hierarchical Inference in Abstract Reasoning
- Large Language Models are Better Reasoners with Self-Verification
- Self-AMPLIFY: Improving Small Language Models with Self Post Hoc Explanations
- Constraint-First Reasoning: A Training-Free Protocol for Exploiting Answer-Space Constraints in Mathematical Problem Solving
- SLM-MUX: Orchestrating Small Language Models for Reasoning
- Revealing Collection Structure through Information Access Interfaces
- Beyond True or False: Retrieval-Augmented Hierarchical Analysis of Nuanced Claims
- Fast Lifted MAP Inference via Partitioning
- Specializing Smaller Language Models towards Multi-Step Reasoning