Does Task Decomposition Break the Solvability Ceiling That Verification Cannot?

Language models solve hard math problems far less reliably than easy ones. A popular fix is to add more models: one proposes steps, another checks them. The most careful study of this setup finds a hard limit. In MAS-ProVe, the authors test step-checking across six multi-agent designs on AIME 2024 and 2025, and checking only makes already-solvable problems more consistent. Problems the system fails every time stay failed. Single-model search methods, by contrast, report large gains on exactly these competitions. rStar-Math runs tree search over code-checked reasoning steps, and ASTRO trains a model on search traces that include backtracking. This note proposes a test of one explanation for the mismatch. A checker can only pick among answers the generator already produces, so it cannot push accuracy past the generator's coverage. Coverage here means the set of problems the model solves at least once when sampled many times. Breaking task decomposition into verified intermediate facts is different: it changes what the generator is asked to produce, and so it might reach problems that sampling never reaches.

The concrete proposal is a coverage-accounting study, paired with one method built to isolate the ingredient we think matters. For each benchmark problem we first estimate whether a fixed base model ever solves it under heavy sampling. We then ask which test-time methods, at matched token budgets, solve problems in the "never solved" set. The method under test is a condition tree. One agent proposes intermediate facts derived from the problem, a second agent accepts or rejects each fact, and the accepted facts are stored as a small branching structure that both agents can return to. This lets the system backtrack without dragging the full conversation history along. If the condition tree crosses the ceiling and best-of-N sampling and verification-only pipelines do not, that is evidence that decomposition, not checking, is the lever. If heavy sampling covers the same problems, the multi-agent story is mostly variance reduction, and we will say so.

Core Claim

The claim has three parts.

First, the solvability ceiling in MAS-ProVe is a coverage ceiling. Any method that only selects among whole-solution samples is bounded by the base model's pass@N, the probability that at least one of N samples is correct.

Second, step-wise decomposition with verified commitment can exceed that bound. A simple calculation shows why. Suppose a solution needs $L$ intermediate facts and the generator produces each correct fact with probability $p$, given the earlier facts. Sampling whole solutions then succeeds with probability about $p^{L}$ per sample. Proposing facts one at a time and committing only accepted ones needs on the order of $L/p$ proposals. That gap is exponential in $L$, and it comes directly from independent attempts at each step versus at the whole chain. The argument holds only if the checker rarely accepts false facts. If its false-accept rate is $\epsilon$, a committed chain is corrupted with probability roughly $1-(1-\epsilon)^{L}$. Measuring $\epsilon$ is therefore part of the study, not an afterthought.

Third, the history problem has a structural fix. DPSDP trains a solver and reviewer and finds that full conversation history hurts, so it keeps only the latest exchange. MAS-ProVe finds that summarized history beats raw history. Both choices discard the record of failed branches, which makes backtracking impossible. A compact tree of accepted and rejected facts keeps exactly what backtracking needs and nothing else.

The prior work plays three different roles here. MAS-ProVe motivates the work, because it found the ceiling. MACM supplies the method: it splits math solving into a Thinker that mines conditions, a Judge that vets them, and an Executor that computes, and it lifts GPT-4 Turbo on Level 5 MATH from 54.68% to 76.73%. MACM's condition list is purely linear, with no branching or backtracking, and it never asks whether its gains come from problems outside the base model's coverage. Our method adds the tree; our analysis adds the coverage question. rStar-Math and ASTRO constrain the design. Their gains rely on code execution as a checker and on trained search policies, so we must separate "decomposition helps" from "a perfect checker helps."

Research Program

Coverage estimation. We fix an open model in the 7–8B range, matching the scale of the Qwen-7B and Ministral-8B models used in rStar-Math and DPSDP, so that heavy sampling is affordable. For every problem we draw 256 chain-of-thought samples. Chain-of-thought prompting means asking the model to write out intermediate reasoning before its answer. From these samples we estimate pass@k curves and define the ceiling set as the problems with zero correct samples. We report how large this set is per benchmark, and we resample a subset at 1024 samples to check that "never solved" is stable.

The condition tree. Each node in the tree is one fact the Thinker proposes, conditioned only on the facts along its path. The Judge either accepts the fact, which expands the node, or rejects it; rejected facts are kept as short negative annotations so they are not proposed again. When a branch stalls for a set number of proposals, control returns to an earlier node, which is the backtracking step. Once the facts on a path are judged sufficient, an Executor writes and runs Python to compute the final answer, following MACM. The context each agent sees is the path plus sibling rejections, never the full transcript. This is the specific answer to the history tension that DPSDP and MAS-ProVe each resolve by throwing information away.

Checker analysis. On a sample of committed facts, we label correctness by hand on MATH and automatically on the 24-Point Game, where every intermediate arithmetic claim can be checked exactly. This gives an estimate of $\epsilon$. We then rerun the 24-Point Game with an oracle checker to bound how much ceiling-crossing is lost to Judge errors.

Baselines

The naive reference is single-sample chain-of-thought from the base model, together with its pass@k curve, which defines the ceiling.

The first strong baseline is self-consistency: sample N chains and take a majority vote. Its token budget is matched to the condition tree per problem, by giving it as many samples as the tree consumed in tokens. This is the most direct competitor, because if large-N sampling already covers the hard problems, decomposition adds nothing. Beating it means solving a meaningfully larger fraction of the ceiling set at the same tokens, not just higher average accuracy.

The second is verification-only search, as studied in MAS-ProVe. At each step, three candidates are generated and an LLM judge picks the best greedily. The judge is the same model as our Judge, with the same budget. The file gives no per-benchmark accuracy for this setup on Lacuna; the study reports qualitatively that judges beat process reward models in 24 of 36 configurations and that ceiling problems stay unsolved. Our prediction is that this baseline crosses essentially none of the ceiling set.

The third is linear MACM with our base model and the same Thinker and Judge prompts but no tree and no backtracking. The reported reference number is 76.73% on Level 5 MATH with GPT-4 Turbo (MACM). That figure uses a different model and is quoted only for orientation; the comparison we draw conclusions from is rerun at our scale.

For context on what trained search achieves, we cite reported results rather than rerunning them. On MATH-500, DPSDP reports 63.2% for Ministral-8B, against 58.2% for its baseline. rStar-Math reports 53.3% on AIME 2024 with a 7B model, using a trained preference model and several rounds of self-training. Neither is a fair test-time comparison, and we label them as such.

The key ablation runs the identical condition tree inside a single context. One model plays Thinker and Judge in turn under role prompts, while keeping the same tree-shaped state. This isolates whether separate agents matter, or whether decomposition plus structured state is enough. A second ablation removes backtracking, which tests the tree itself.

Why not just…?

Why not just sample more and vote? This is the main threat. Self-consistency at large N may already reach many problems that a single sample misses. The coverage accounting is built to settle it. We report pass@k up to 1024 next to the condition tree's ceiling-crossing rate at matched tokens. If sampling at matched tokens crosses as many ceiling problems, our second claim fails. The guidance from Meta-CoT that tree search is about 4x more compute-efficient than parallel sampling suggests it will not, but that comparison was not about the ceiling set specifically.

Why not just prompt one model to decompose and self-check? Single-model self-correction has a poor record. Meta-CoT reports only about 25% successful correction for prompted Llama-3.1-70B, and LLM2 finds negligible gains from self-reflection prompting in small models. Still, a single context that keeps tree-structured state is untested, and it might match the multi-agent version. That is exactly our key ablation. If it ties, we will conclude that structured decomposition, not role separation, is what matters, which would itself be a useful result.

Why not just train on search traces, as ASTRO does? ASTRO's gains are real: AIME 2024 rises from 10.0% to 30.0% on Llama-3.1-70B. But they come from fine-tuning plus reinforcement learning on a 70B model, with about 6.3K tokens per problem. Our question is whether fixed weights can cross the ceiling at test time. Training can enlarge coverage too, and a positive result here would motivate distilling condition trees into weights, as a later step.

Proposed Experiments

We use Level 5 MATH and MATH-500 for scale, AIME 2024 and 2025 and Olympiad Bench for the hard regime where MAS-ProVe found the ceiling, and the 24-Point Game as a setting where every intermediate claim can be checked exactly.

The primary metric is the ceiling-crossing rate: the fraction of ceiling-set problems a method solves correctly, at matched tokens per problem. The secondary metrics are overall accuracy, tokens per solved problem, and the Judge false-accept rate $\epsilon$. On AIME, where answers are integers, we also check that crossed problems come with valid reasoning chains, by manual audit of a sample, so that lucky guesses are not counted.

Four outcomes are decisive. The idea is supported if the condition tree crosses a clearly nonzero fraction of the ceiling set while verification-only search and matched-budget voting cross almost none. Under the $p^{L}$-versus-$L/p$ argument, crossing should concentrate on problems that need longer chains of conditions, so we annotate chain length and test for this. The idea is weakened if the oracle-checker run on the 24-Point Game crosses far more problems than the LLM Judge, which would mean the checker, not decomposition, is the bottleneck. It fails outright if large-N sampling matches it.