Conflict Trees for Language Reasoning: Replanning Only What the Verifier Says Is Wrong

Reasoning models fix their own mistakes by writing the fix out in text. They produce a partial answer, notice a contradiction, write "wait, let's backtrack," and then retype a large part of the solution. On constraint-heavy problems such as Sudoku, this habit is necessary. Models trained without it fail completely. It is also expensive, because every abandoned attempt costs tokens, and each token costs one sequential forward pass. Robot path planning ran into the same trade-off decades ago and settled on a different answer. Conflict-Based Search plans each robot separately. When two plans collide, it records a small constraint ("robot A may not be at cell v at time t"), branches on which robot must give way, and replans only that one robot. All bookkeeping about dead ends lives in an external tree, never inside any robot's plan.

This note proposes the same two-level structure for language-model reasoning. The model writes a solution as separate pieces. A deterministic checker finds the specific pair of pieces that contradict each other. An external tree branches on which piece must change. The model then regenerates only that piece, conditioned on a short injected constraint. The model is trained with verifiable-reward reinforcement learning, meaning reinforcement learning whose reward comes from a program that checks correctness rather than from a human or a learned judge. Training teaches the model to obey injected constraints and to write each piece concisely. The claim is that, at equal accuracy, this moves the cost of search out of the token stream. Total tokens and the sequential critical path both shrink compared with models that backtrack in text, and the accuracy collapse that plain length penalties cause on combinatorial tasks does not occur.

Core Claim

Two results in the file are in tension.

DLER penalizes length during reinforcement learning, with fixes for the variance and entropy collapse that naive penalties cause. It cuts reasoning length by 70% and still reaches 55.62% on AIME-24 with about 3,200 tokens. How Much Backtracking is Enough? seeds textual backtracking through supervised traces and then applies reinforcement learning. It shows that Sudoku needs at least five verbalized backtracks before reinforcement learning converges at all (28.9% accuracy), while zero-backtrack models fail entirely.

Length penalties assume a short, unbranching path to the answer exists. Combinatorial problems deny that assumption. We claim the conflict can be dissolved rather than traded off. If branching is done by an external conflict tree, the model never has to verbalize dead ends, so per-call conciseness and deep search stop competing.

What is new is not "LLM plus tree search." Constraints-of-Thought already turns chain-of-thought into (intent, constraint) pairs that prune a single-agent Monte Carlo tree search at inference time, with no training. What is new is the combination of three things:

  1. Branching on verifier-certified conflicts between pieces of a single solution, in the specific CBS style where each node holds constraints and only the constrained piece is regenerated.
  2. Training the piece-writing policy with verifiable rewards inside that tree.
  3. Measuring the outcome as a latency question.

Research Program

The representation. A problem is posed in natural language. The policy first emits a decomposition into named pieces with declared interfaces. Depending on the task, a piece might be a Sudoku box, one agent's route, or one constraint block of an optimization model. A task-specific checker then does two things. It verifies each piece locally. It also detects pairwise conflicts and returns a certificate naming the two pieces and the violated shared fact. This mirrors the vertex conflict (A, B, v, t) of Conflict-Based Search.

For optimization modeling, the certificate is the irreducible infeasible subset of constraints that a mathematical programming solver reports. This is exactly the kind of deterministic error signal Solver-Informed RL exploits for reward, which we instead use for localization.

The high level. A constraint tree is expanded best-first. Node cost is total tokens spent so far plus a lower bound from unresolved conflicts. Each conflict spawns two children: one where piece A receives the constraint, and one where piece B does. We borrow two refinements from ICBS.

  • Conflict ordering. ICBS resolves first the conflicts whose every resolution provably raises cost. Our analogue is to resolve first the conflicts where both pieces are already locally tight, as judged by the checker.
  • Merging. ICBS merges agents that conflict repeatedly into one jointly planned meta-agent. Our analogue is to merge two pieces that conflict repeatedly into one joint call. This is the fallback that keeps the method from thrashing when the decomposition is poor.

We will also test a depth-first priority variant modeled on Priority-Based Search. Instead of constraining a specific fact, it imposes an order between pieces: the lower-priority piece must accommodate the higher one. PBS scales to hundreds of agents by this kind of greedy ordering.

The low level and training. The policy is a single model, called once per piece. Its input is the piece specification plus a short list of injected constraints. Sibling pieces with no shared constraints are generated in parallel. Training uses group-relative policy optimization and gives three rewards:

  • Per-call constraint reward. Each low-level call is rewarded for passing its local check and satisfying its injected constraints. This is dense and deterministic. Unlike the stepwise reward of VSRM, it needs no Monte Carlo sub-rollouts.
  • Episode reward. The whole tree is rewarded for final verified correctness.
  • Length advantage. A per-call length advantage is computed only among correct calls and scaled by pass rate, following the correctness-conditioned scheme of Think Dense, Not Long and the higher clipping bound of DLER. These protect the exploratory tokens that remain inside a single piece.

The decomposition call receives credit from the episode outcome and a penalty proportional to the number of tree nodes. This teaches the model to choose cuts that conflict rarely. Supervised warm-up uses traces produced by running the tree with a classical solver standing in for the low level. Cai et al. found that supervised data mainly supplies the structure, which here means the format of obeying injected constraints. We build on the how-much-backtrack codebase and its Reasoning Gym task generators.

Baselines

Plain policy. The reference point is the same base model trained with standard outcome-reward GRPO on each task, using no backtracking seeding, no tree, and no length term. This shows what verifiable reward alone buys and how long its chains grow.

Textual backtracking. The strongest existing method on the combinatorial tasks is the textual-backtracking recipe of How Much Backtracking is Enough?. It applies supervised seeding with synthetic DFS traces containing a tuned number of backtracks, followed by reinforcement learning. The paper reports 28.9% accuracy on Sudoku with five backtracks and 69.7% on Countdown with one backtrack, against 38.9% for cold-start reinforcement learning. It is the strongest competitor because it targets exactly our regime and already achieves search through the model's own text. We rerun it from its released code on the same base model, the same task generators and difficulty settings, and the same number of reinforcement-learning samples, retuning the backtrack count per task. The file reports no token counts for this method, so we measure its tokens ourselves.

Textual backtracking plus length control. We add DLER-style length control on top of the textual-backtracking model. This is the obvious "just compress it" competitor. DLER's reported 55.62% AIME-24 at roughly 3,200 tokens comes from mathematics, not from these tasks, and no reported result was found on the file for DLER on Sudoku or Countdown.

Optimization modeling. The strongest baseline is SIRL-32B, at a reported 68.3% macro average across NL4OPT, MAMO, IndustryOR and OptMATH. We will either compare at a matched model size by retraining the SIRL recipe ourselves, or report against the published number with the size difference stated.

Key ablation. The most important ablation keeps the tree's certificate but drops locality. On a detected conflict, the model regenerates the entire solution with the certificate appended as feedback. This isolates whether the gain comes from replanning only the affected piece or merely from receiving a precise error message.

All methods receive the same training samples, the same hyperparameter search budget, and the same inference hardware. Beating the field means matching or exceeding textual-backtracking accuracy on Sudoku and Countdown at their hardest generator settings while using fewer total tokens and fewer critical-path tokens. It also means beating the length-controlled variant on accuracy at the same token budget.

Why not just…?

Why not just add a length penalty to the backtracking model? This is DLER's lesson, and it is credible on mathematics. Cai et al. show, however, that removing backtracks on Sudoku drops accuracy to zero. Cutting tokens therefore cuts the very search the task needs. The experiment that settles this is the accuracy-versus-tokens curve of the length-controlled backtracking model against our method on Sudoku and Countdown, swept over penalty strength. If that curve dominates ours, the proposal fails.

Why not just sample many full solutions and keep the one the checker accepts? This is the most serious threat. Parallel sampling also moves search outside the text, and DLER reports that concise models gain 27% accuracy in a fixed wall-clock window through parallel test-time scaling. Our argument is that independent resamples throw away the pieces that were already correct. Since the chance of getting all k pieces right at once shrinks roughly geometrically in k, full resampling should fall behind as problems grow. We test this directly. We compare against best-of-N with the same checker at matched total tokens and matched wall-clock, sweeping problem size through Reasoning Gym's difficulty knobs. We expect the gap to open only beyond some size. If it never opens, the locality idea is not worth its machinery.

Why not just translate the problem to a formal language and call a classical solver? For fully formal puzzles such as Sudoku, this will win, and we report it as an upper reference rather than pretend otherwise. The method is aimed at cases where translation itself is the reasoning. Optimization modeling is the clearest example: no solver writes the model, but the solver can tell you which written constraints are mutually infeasible. The puzzle tasks serve as controlled testbeds where conflicts and problem size can be dialed. The decisive evidence for the method's practical value must come from the optimization-modeling benchmarks.

Proposed Experiments

Experiment 1: the combinatorial core. We use Reasoning Gym Sudoku, Countdown, and a graph-coloring generator from Reasoning Gym, training 1.5B and 7B base models. The metrics are:

  • verified accuracy;
  • total generated tokens;
  • critical-path tokens, meaning the longest chain of sequential calls;
  • wall-clock time per problem on fixed hardware.

The decisive check is whether our method reaches at least the 28.9% Sudoku and 69.7% Countdown reported by Cai et al. with fewer critical-path tokens than the textual-backtracking model trained under identical conditions. A second check is that the full-regeneration ablation recovers most of the accuracy but not the token savings. If it recovers both, locality is not the mechanism.

Experiment 2: scaling. We sweep puzzle size and conflict density, recording tree nodes, merge frequency and tokens. The CBS literature predicts the method degrades when problems have many symmetric alternatives (open spaces, in the robot setting) and when pieces are densely entangled. We expect the same here and will report where the merge fallback dominates, the point at which the method reduces to monolithic generation.

Experiment 3: optimization modeling. On NL4OPT, MAMO, IndustryOR and OptMATH, we use the solver's infeasibility certificates as conflicts and compare against SIRL-style training at matched scale, reporting accuracy and tokens.

Experiment 4: exploratory token use. We measure whether the per-call policy retains exploratory tokens such as "wait" inside pieces. This tests whether moving search outside the text actually removes the pressure that, according to DLER and DDCA, leads to entropy collapse under length penalties.