Does the Search Amplify the Stereotype? Representative Reasoning Paths for Bias-Faithful Decoding

A language model that places 65% of its probability on a stereotyped answer and 35% on a non-stereotyped one can still produce the stereotyped answer 100% of the time. This happens when the decoder, the procedure that turns the model's probabilities into one output, always keeps only the most likely continuations. Beam search, greedy decoding, and majority-vote over reasoning chains all discard partial answers at every step. They are therefore a form of pruning, and nobody has asked whether that pruning is itself a source of bias amplification, the tendency of models to exaggerate skews they learned from data. There is already evidence that decoding matters. SocialStigmaQA reports that biased outputs range from 45% to 59% depending on decoding strategy and prompt style, and that chain-of-thought (asking the model to reason step by step) often increases stigma-biased answers. Current bias evaluations cannot tell whether that increase comes from what the model believes or from how the search collapses those beliefs into one answer.

We propose to separate these two sources and to remove the second one. The tool comes from combinatorial optimization. In dynamic programming, two partial solutions can be merged when they behave the same with respect to every possible completion, and algorithms keep only a small "representative set" of states instead of all of them (Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth; An FPTAS of Minimizing Total Weighted Completion Time on Single Machine with Position Constraint). We apply the same idea to the decoder. The decoder keeps a small set of reasoning prefixes that covers every distinct final-answer tendency the model has, rather than the top-k most likely prefixes, and it transfers probability mass instead of throwing it away. The output is then a faithful estimate of the model's own answer distribution at beam-search cost. The same estimate can be used to abstain when that distribution is split.

Core Claim

Much of the bias amplification measured on multi-step reasoning benchmarks is search-induced. It is produced by likelihood-based pruning and argmax aggregation, and it is not present in the model's full distribution over reasoning chains. A decoder that trims states by answer-equivalence rather than by likelihood can recover the model's marginal answer distribution within a controlled error. It can do so with the same number of forward passes as beam search and fewer than naive sampling needs for equal accuracy. The claim is falsifiable in both directions. If the model's full marginal is already as biased as greedy output, search is not the culprit and the work reports that result. FairBelief, which finds harmful beliefs at the peak of the likelihood, predicts that part of the bias will remain in the marginal. We aim to measure how large that part is.

Research Program

The first step is to define what it means for two reasoning prefixes to be equivalent. For a prefix $p$ of a chain-of-thought, we append a short answer cue (for example "Answer:") and read the model's distribution over the benchmark's answer options, $q(p) \in \Delta(\mathcal{A})$. Here $\mathcal{A}$ is the set of answer options, such as the two people and "Unknown" in BBQ, or yes / no / can't tell in SocialStigmaQA. This probe is the reasoning-chain analogue of the combinatorial notion "behaves identically on all future completions." It is only approximate, because two prefixes with the same current answer distribution may diverge later. Measuring that drift is part of the program, not something we assume away.

The decoder follows the state-space trimming scheme used in approximation algorithms. At each step it expands all retained prefixes. It then greedily picks a set $R$ of prefixes so that every discarded prefix $p$ has a retained prefix $r$ with $\|q(p) - q(r)\|_1 \le \epsilon$. The discarded prefix's path probability is added to its nearest retained representative, so no mass is lost. We impose a width cap $k$ equal to the beam width, following the capped heuristic in A heuristic algorithm using tree decompositions for the maximum happy vertices problem. When the cap binds, the procedure merges the closest pairs first. At the end, the decoder reports

$$\hat P(a) = \sum_{r \in R} w_r \, q_T(r)(a),$$

where $w_r$ is the accumulated path mass of retained chain $r$ and $q_T(r)$ is its final answer distribution. The error has two parts. If equivalence were exact, each merge would move at most $\epsilon$ of total-variation distance per step, weighted by the merged mass. The remainder is probe drift, which we estimate directly.

The second step is the decomposition itself. For each prompt, we estimate the model's true marginal answer distribution with a large ancestral-sampling budget (256 chains) as a reference. We then define search-induced amplification as the gap between a decoder's rate of choosing the stereotyped option and that reference marginal. We also report the directional, base-rate-adjusted metric of Directional Bias Amplification. That paper already showed that simply retuning decision thresholds changed measured amplification from 0.040 to 0.001, so output rules matter a great deal. The third step is an output rule. When a single answer is required, the decoder returns the argmax of $\hat P$ only if its mass exceeds a threshold $\tau$ set on held-out disambiguated items; otherwise it returns the abstain or "Unknown" option. On BBQ's ambiguous contexts this is the correct behavior.

The contrasts with prior work are as follows. Determinantal Beam Search also changes which beams are kept, but it rewards string-level diversity and has no notion of answer equivalence or mass conservation. Decoding Matters shows that a decoding heuristic, length normalization interacting with "ghost tokens" whose probability is near 1, amplifies popularity bias in recommendation. That paper motivates our view that search creates amplification, but it addresses a different bias and uses a heuristic fix. Fair Wasserstein Coresets builds fairness-constrained representative subsets of training data or few-shot exemplars, which is offline data selection rather than pruning inside inference. Dataset Representativeness and Downstream Task Fairness constrains our framing: a representative set is not automatically fair. For that reason we target faithfulness to the model's own distribution, not parity. Faithfulness is a necessary floor that any later debiasing target, such as parity, can reweight.

Baselines

The naive reference points are greedy decoding and standard beam search (width $k$, answer read from the top beam). These are what published numbers use. SocialStigmaQA reports 59.2% biased outputs for Flan-UL2 and 45.0% for Flan-T5-XXL under greedy decoding. We re-run both on identical prompts to anchor our measurements to those figures.

The strongest competitor is ancestral sampling of $N$ chains with two readouts. The first is majority vote over sampled answers, the usual self-consistency-style procedure. The second, stronger readout reports the empirical answer histogram and applies the same abstention threshold $\tau$. For self-consistency-style voting on SocialStigmaQA or BBQ, there is no reported result found on Lacuna. The fair comparison fixes total forward-pass tokens: $N$ is chosen so that sampling uses the same compute as our decoder at width $k$, and both share $\tau$ tuned on the same held-out split. We beat this baseline if, at matched compute, our estimate of the marginal is closer to the 256-chain reference and our BBQ ambiguous-context accuracy is higher. Disambiguated accuracy must stay within one point.

We also run Determinantal Beam Search at the same width, both with its string kernel and with a kernel built from our answer probe $q$. The second version gives diversity the same information our method uses. It is the fairest test of whether mass conservation, rather than diversity, is what matters.

Three ablations isolate our key ingredient. The first uses answer-equivalence trimming but discards mass instead of merging it. The second merges mass using a random representative. The third uses probes computed only at the final step. Together they tell us whether the gain comes from coverage, from conservation, or from intermediate lookahead.

Why not just…?

Why not just sample many chains and report the histogram? This is the real threat. With unlimited compute it is exactly correct, and it is our reference. Our bet is that at beam-search budgets (8 to 16 chains), sampling misses low-mass but decision-relevant answer modes, such as a 15% "can't tell" mode, and so gives a noisy histogram that makes abstention unstable. The matched-compute experiment settles this. If sampling at equal cost matches our marginal error, the method has no reason to exist beyond the diagnostic decomposition, and we will say so.

Why not just skip chain-of-thought and read the answer distribution directly? That removes the search but also changes the model's distribution. SocialStigmaQA shows that reasoning changes bias rates, and Uncovering Stereotypes in Large Language Models shows stereotypes resurfacing as task complexity grows, which is exactly where reasoning is needed. We report the no-reasoning distribution as an additional reference point. The scientific question is whether reasoning's harm lives in the chains or in the pruning of the chains.

Why not just lower the temperature or use nucleus truncation? FairBelief finds harmful completions at the top of the likelihood, so truncating the tail concentrates the stereotyped mode instead of removing it. The greedy result in SocialStigmaQA points the same way. We include top-p sampling at matched compute for completeness.

Why not just add a counter-stereotype diversity penalty to beam search? Penalties like those in Decoding Matters or determinantal diversity push the output away from the model's beliefs by an amount the user cannot interpret. Our target is different: faithfulness first, then an explicit and auditable output rule. The determinantal-kernel baseline built on our probe tests whether a diversity objective gets the same result without mass conservation.

Proposed Experiments

The testbeds are BBQ and SocialStigmaQA, both run with chain-of-thought prompts. BBQ has 58,492 items across nine social dimensions; in ambiguous contexts UnifiedQA's errors were biased about 77% of the time, and disambiguated accuracy dropped 3.4 points when the answer ran against a stereotype. SocialStigmaQA has 10,360 prompts covering 93 stigmas and includes a No-Stigma control. The models are Flan-T5-XXL and Flan-UL2, matching the SocialStigmaQA reference numbers, plus Vicuna-7B, which scored most hurtful on HONEST in FairBelief. The metrics are:

  • search-induced amplification against the 256-chain reference;
  • base-rate-adjusted directional amplification;
  • BBQ ambiguous and disambiguated accuracy;
  • SocialStigmaQA biased-answer rate relative to its No-Stigma control;
  • total-variation error of the estimated marginal as a function of forward passes.

The first decisive check is the decomposition. On each model, the gap between greedy bias and reference-marginal bias tells us what fraction of amplification the search creates. If this gap is near zero, the paper becomes a negative result about decoding-level fixes. The second check is probe drift: we measure how often prefixes merged at step $t$ end with answer distributions more than $\epsilon$ apart, across $\epsilon$ and task length. This tests whether the equivalence assumption holds, and whether it degrades on the harder, longer items where Uncovering Stereotypes in Large Language Models sees guardrails collapse. The third check is the matched-compute curve against histogram sampling: marginal error and ambiguous-context accuracy at 4, 8, 16, and 32 chain-equivalents. Our method should dominate at small budgets and converge with sampling at large ones. Finally, because seed and wording sensitivity is known to swing SocialStigmaQA scores by over 10 points, every comparison uses at least three seeds and two template paraphrases. We count a difference as real only if it exceeds that variation.