Premise-Diverse Beam Search for Rule-Heavy Reasoning

When a language model answers a question in an expert domain, such as an emergency-response protocol or a university physics problem, the most damaging mistakes are often made in the first line. The model picks the wrong rule or theorem, or misreads a condition, and every later step faithfully builds on that error. Current search-based decoders keep several candidate reasoning paths alive and prune the weak ones. Because they all branch from whichever start looks most probable, the whole candidate set usually inherits the same wrong premise. We propose to diversify the search over which domain premises each candidate commits to, not over the words it uses. Candidate paths would be pushed to invoke different rules or theorems, or different readings of the given conditions, at the steps where they introduce premises. A step-level checker would then prune paths whose steps do not follow from the premises they cite.

The two-sentence version is this. Search decoders for reasoning fail in the "confidently wrong" regime because their candidates share one mistaken premise. Forcing candidates to disagree about premises, while letting them agree freely on everything else, should raise the chance that some candidate starts from the right rule, and a local verifier can then find it. The work tests whether this premise coverage turns into fewer rule hallucinations and higher accuracy at a fixed compute budget, on the RULER emergency-rule benchmark and on TheoremQA.

Core Claim

Diverse beam search, meaning decoding that splits the beam into groups and penalizes later groups for repeating earlier groups' choices (Vijayakumar et al.), was built to fix beam collapse. Beam collapse is the tendency of beam candidates to become near-duplicates (Gimpel et al.). Its penalty works on surface tokens, which is the wrong unit for expert reasoning. Two paths can share every theorem name and constant and still differ in the one thing that matters: which rule they applied, or how they read a condition. Two paths can also differ in every word and execute the same wrong derivation.

Our claim is that the right unit of diversity in rule- and theorem-driven reasoning is the declared premise set of each step. That set contains the rules, theorems, and interpretations of given conditions the step relies on. A penalty on premise overlap should improve accuracy over both unpenalized verifier-guided search and token- or embedding-level diversity. It should help most on the multi-rule and theorem-application problems where search currently plateaus, and it should specifically reduce fabricated or misapplied rules.

The closest existing systems each have one half of this design. RAMPS scores reasoning steps with a process reward model (a learned scorer of individual reasoning steps) during beam search. It raises multi-rule reasoning on RULER from 5.4 to 7.7 but applies no diversity pressure. Deductive Beam Search and Gambit likewise prune and re-branch from top-scoring prefixes, which is exactly the mechanism that copies an early mistake across the beam. PathFinder does add diversity, through varied sampling temperatures and a cosine-similarity repetition filter. That diversity is over whole-sentence embeddings, and its contradiction check is a generic entailment model that cannot tell whether a physics law was misapplied. None of these systems makes candidates disagree about premises.

Research Program

The decoder works one reasoning step at a time. We borrow the structured output format of the Structural Reasoning Model, where each step explicitly lists its conditions, the operation performed, and its sources. In our setting a "source" must be an identifier into the domain knowledge base: a rule ID from RULER's 1,000 expert rules, or a theorem from TheoremQA's 350-theorem inventory. Conditions quoted from the problem statement are also tagged.

The beam is divided into $G$ groups, as in diverse beam search. The first group runs ordinary verifier-guided step search. Each later group $g$ scores a candidate step $s$ as

$$\text{score}_g(s) = \log P(s \mid \text{prefix}) + \beta \, V(s) - \lambda \max_{h<g} J\big(\Pi(s), \Pi_h\big),$$

where $V(s)$ is the step verifier's score and $\beta$ weights it, $\Pi(s)$ is the set of rule or theorem identifiers and condition readings the step declares, $\Pi_h$ is the premise set already committed to by group $h$ at the same depth, $J$ is Jaccard similarity, and $\lambda$ sets the strength of the penalty.

Two design choices set this apart from lexical diversity. First, the penalty applies only at steps that introduce a new premise, so arithmetic or restatement steps are never pushed apart. Second, facts taken verbatim from the problem are excluded from $\Pi$, so all groups can share them. This targets the known failure of token-level penalties, which also push apart facts that every valid solution must share.

The verifier $V$ has two parts. A lookup checks that each cited identifier exists in the knowledge base, which catches fabricated rules (RULER's "extrinsic" hallucination). A local judge, following the Structural Reasoning Model's approach, scores whether the step follows from its cited parents and the retrieved text of the cited rule. We chose that approach because it reports large precision gains over judging whole chains. Where a trained process reward model is available, as in RAMPS, it replaces or combines with the judge, so we can separate the effect of diversity from the effect of verifier quality.

The final answer is chosen by aggregating verifier scores over each surviving path's dependency graph. It is not chosen by majority vote, since majority vote is the mechanism that fails when the model is confidently wrong.

The analysis centers on one measurable quantity: premise coverage at beam size B. This is the fraction of problems on which at least one surviving path cites the gold rule set or theorem. Both benchmarks make it measurable, because RULER questions are generated from known rules and TheoremQA questions are tagged with their theorem. Coverage separates two questions: whether diversity helps the search find the right premise, and whether the verifier can recognize it once found.

Baselines

The naive reference point is single-path chain-of-thought and program-of-thought prompting with the rule or theorem text supplied in context. On TheoremQA this is the setting where TheoremQA reports GPT-4 program-of-thought at 51% and open-source models below 15%, with theorem augmentation giving no significant gain. On RULER, vanilla models plateau at 5.4 of 10 on multi-rule reasoning and GPT-4o zero-shot scores 4.0 (RULER/RAMPS).

The strongest existing method is RAMPS: process-reward-guided beam search, reported at 7.7 of 10 on RULER multi-rule reasoning with Qwen3-14B and 7.6 on the intrinsic hallucination sub-score (RAMPS). It is the right opponent because it already combines domain rule knowledge, step-level verification, and beam search, which leaves diversity as the only differing ingredient. We will run it on Qwen3-14B with the same beam width, step budget, and total generated tokens as our method. If its reward model is not released, we will retrain it with the published recipe (search-synthesized traces with located error points) and require that our reproduction reach roughly 7.7 before any comparison counts. Our method then adds the premise penalty on top of that same reward model. Beating RAMPS means a multi-rule score reliably above 7.7 and a better intrinsic hallucination sub-score at equal tokens, across at least three seeds. For TheoremQA we found no reported result on Lacuna for any search-based or verifier-guided decoder, so the reported 51% GPT-4 program-of-thought figure is the only external anchor. We will establish RAMPS-style search on TheoremQA ourselves as the internal strong baseline.

Three ablations isolate the key ingredient. We swap the premise penalty for the token Hamming penalty of Vijayakumar et al.. We swap it for a sentence-embedding cosine penalty in the style of PathFinder and of maximal-marginal-relevance beam search (Song et al.). We replace grouped penalties with stochastic beam search, which samples candidates without replacement and is reported to beat diverse beam search on translation quality-versus-diversity trade-offs, though that paper gives no scalar figure. All three use the identical verifier and budget. If premise diversity does not beat the embedding penalty, the claim that premises are the right unit fails.

Why not just…?

Why not just sample many paths at high temperature and take a majority vote? This fails when the model's probability mass sits on the wrong rule, because extra samples then mostly repeat the dominant mode. Kool et al. show that sampling with replacement from low-entropy sequence models produces heavy duplication. The Structural Reasoning Model reports sampling-consistency detection at around 25% average precision on HumanEval, against 83.08% for its graph-based method, because errors are consistent across samples. We will still run self-consistency at matched tokens and report premise coverage for it. If its coverage matches ours, the diversity mechanism is unnecessary.

Why not just widen the beam of verifier-guided search? A wider beam in RAMPS or Gambit buys more candidates, but re-branching from top prefixes means those candidates share the top prefix's premises. Gambit reports efficiency gains from exactly this re-branching and measures no diversity or factual grounding. This is a real threat on problems whose rule choice is easy. We will plot accuracy and coverage against beam width for both methods at equal tokens. If the gap closes as width grows, the method's value is limited to tight budgets, and we will report that.

Why not just prompt the model to list candidate rules first and then solve under each one? This is the most serious alternative, because it produces premise diversity at the first step with no decoder changes. It diversifies only once, however, and it has no verifier to redistribute compute, while multi-rule problems introduce premises at several depths. We will run it with the same verifier-based final selection. We will also measure the depth at which the first wrong premise enters failed baseline traces. If most errors enter at step one and enumeration matches our accuracy, we will recast the contribution as a verified form of enumeration and not claim a new decoder.

Why not just fine-tune on domain data? RULER's setting assumes rulebooks without worked examples. Fine-tuning GPT-3.5 on osteoarthritis guidelines did not reliably improve consistency and sometimes lowered it (Xi Chen et al.). The decoder also applies to frozen and API-served models, a point KCTS makes for its own decoding-time grounding.

Proposed Experiments

Experiments use Qwen3-14B as the main model, matching RAMPS, plus one smaller open model to test whether the gains shrink or grow as base knowledge weakens. They cover the RULER multi-rule and single-rule-application splits, all four TheoremQA subjects, and a small transfer check on the 34 osteoarthritis guideline questions (Xi Chen et al.). Metrics are RULER's 10-point scores including the intrinsic and extrinsic hallucination sub-scores, TheoremQA accuracy, premise coverage at beam size B, the rate of cited identifiers that do not exist, and total generated tokens.

Three results decide the question. The first is whether premise-diverse search raises coverage over unpenalized RAMPS-style search at equal tokens. If it does not, the mechanism is inert. The second is whether coverage gains turn into accuracy gains. If coverage rises but accuracy does not, the bottleneck is the verifier, and we will show this by substituting an oracle that marks the gold-premise path. The third is whether the premise penalty beats the token and embedding penalties at every $\lambda$ on a quality-versus-diversity curve. This tests the claim that premises, not surface form, are the right unit.

We also report how often models fail to declare a premise they actually use. The Structural Reasoning Model notes this weakness, and it bounds how far the method can reach: premises that are never declared cannot be diversified.