Heavy-Tailed Edit Sizes for Searching Over Humorous Rewrites

A headline becomes funny, or stops being funny, through surprisingly small edits. In a game where players tried to make satirical headlines serious, a third of successful attempts changed one word and 57% changed two or fewer. The remaining 43% needed more, and humor research has no account of how a generator should decide how much to change. Language models make this worse. They either repeat a few memorized jokes or, when pushed toward unlikely words, produce nonsense. This proposal treats humorous rewriting as a search over edits. A language model proposes each edit, and the number of words it is told to change is drawn at random from a power law. A power law is a distribution that mostly picks one-word edits but, with small and only slowly shrinking probability, picks large ones. Theory from evolutionary computation says this kind of step-size distribution is the right choice exactly when good solutions sit across "valleys": regions where every small step makes things worse before a larger step makes them better.

The core claim has two parts, and the first is a measurement. Before building anything, we test whether humor edits actually have valleys. Take a human edit that changes $k \ge 2$ words. Is applying only part of it rated less funny, or less serious, than both the starting text and the full edit? If such valleys are common, a power-law edit-size operator should find good rewrites with fewer scorer calls than one-word greedy search or any fixed edit size. If valleys are rare, the theory predicts no advantage, and we will report that greedy local search suffices. Either outcome is informative. The second outcome would be a useful negative result for anyone tempted to bring evolutionary machinery into text generation.

What exists and what is missing

Heavy-tailed mutation is well understood on bitstrings. The operator analyzed in Evolutionary Algorithms and Submodular Functions: Benefits of Heavy-Tailed Mutations samples a step size $k$ with probability proportional to $k^{-\beta}$ and flips exactly $k$ bits. It reaches approximation guarantees in polynomial time on landscapes where flipping each bit independently with probability $1/n$ takes exponential time. Theoretical Analyses of Multi-Objective Evolutionary Algorithms on Multi-Modal Objectives extends this to two competing objectives. There, pure one-bit local search fails outright, and the heavy-tailed variant gains a $k^{\Omega(k)}$ speedup across valleys of width $k$. Lazy parameter tuning and control and Abnormal Mutations supply the practical argument: power-law sampling removes the need to tune a step size, and Cauchy steps help most on multimodal functions without global structure. These papers supply our method and our predictions. They also constrain them, because heavy tails cost a logarithmic factor on smooth, unimodal problems. If humor landscapes turn out to be smooth, we should expect to lose slightly.

The closest work is Controlling the Mutation in Large Language Models for the Efficient Evolution of Algorithms. It already samples a power-law mutation size and tells a language model how many lines of code to change. It found that GPT-3.5 ignores the instruction ("mutation-blind") while GPT-4o follows it. We reuse that prompting mechanism directly. We differ in three ways. Our search space is natural-language text scored by noisy human-trained judges, not code scored by a benchmark. We measure the landscape's valley structure from human data instead of assuming it. We fit the power-law exponent to the human edit-size distribution rather than taking a default value.

On the humor side, three papers frame humor as a single small substitution. Humicroedit collects one-word headline edits and finds that the distance between the old and new word in embedding space correlates with funniness. Unfun.me collects human edits that make satire serious and records their sizes. Adult humor via lexical constraints performs one constrained substitution per message. All three treat the edit as a one-shot operation and never ask how edit size should be chosen during a search. Humor as Circuits in Semantic Networks does search, over paths in a knowledge graph, but only with ordinary one-step transitions. The motivating failures come from three further papers. ChatGPT is fun, but it is not funny! shows that over 90% of 1,008 generated jokes repeated 25 puns. Humor in AI argues that humor rewards are spiky, so that one token can ruin a joke. It also shows that LLM judges and expert humans disagree drastically: an LLM judge gave Claude a 54.4% win rate, while a professional editor preferred Claude's caption only 1.6% of the time. That second finding constrains how we evaluate.

Research Program

The first step is a valley census. For every Unfun.me pair with an edit of two or more words, and for multi-edit variants we collect on Humicroedit headlines, we enumerate all partial applications of the edit. These are the intermediate texts that apply some but not all of the word changes. We score each one with humans, using the five-judge, 0–3 Humicroedit protocol for funniness or a satirical-versus-serious judgment for unfunning. A pair contains a valley of width $w$ if the partial edits that are $w$ words from the end all score worse than both endpoints. The census produces two things: the empirical distribution of minimal edit sizes, and the fraction of edits that contain valleys of each width. We fit $\beta$ in $\Pr(K=k) \propto k^{-\beta}$ to the minimal-edit-size distribution, truncated at half the headline length. The truncation follows the capping lesson of Fast Mutation in Crossover-Based Algorithms, where uncapped samples wasted evaluations.

The second step is the search algorithm. It follows the two-objective archive design of the multi-objective analysis. The algorithm keeps the set of rewrites not dominated on two objectives: the target score, and the number of words changed from the original. Fewer changed words is better, which also addresses the verbosity failure noted in Humor in AI. At each step it picks an archive member, samples $k$, and prompts the model to change exactly $k$ words. It then measures the actual word-level edit distance, recording any mismatch as a mutation-blindness rate, and scores the result. The output is a curve from one changed word upward, each point being the best rewrite found at that edit size. That curve shows where the humor trigger lives.

There are two tasks. Unfunning Unfun.me satire is the controlled task. Its search signal is a satire-versus-serious classifier trained on the 9,159 Onion and 9,000 serious headlines, plus a fluency check, and that target is far less ambiguous than funniness. Making Humicroedit's serious headlines funny is the application task. Its search signal is a funniness regressor trained on Humicroedit. Neither signal is used for final evaluation, because a search will find texts that game its scorer. All reported results come from fresh human ratings.

Baselines

The naive reference is a single unconstrained rewrite: the same model is asked once to make the headline funny, or serious. We also report the human edits as a ceiling. On Humicroedit, a human edit's mean grade is the target to match. On Unfun.me, the human edit sizes are the efficiency reference, since 33% of human edits needed one word and 57% two or fewer.

The strongest competitor is best-of-N reranking. The model generates N free rewrites at its default temperature, and the scorer picks the best. This baseline gets the same number of scorer calls and the same model calls as the search. It is the strongest because it uses the same scorer and the same generator, and differs only in having no iterative search and no edit-size control. To beat it, the heavy-tailed search must reach higher human-rated success at an equal evaluation budget, with fewer words changed. We found no reported result on Lacuna for best-of-N reranking on Humicroedit generation. For context, the best published scorer on Humicroedit, a regression ensemble, reaches RMSE 0.497 against a mean-predictor baseline of 0.575 (SemEval-2020 Task 7). We report our scorer's RMSE so readers can judge how much search signal it provides.

Greedy one-word local search always changes exactly one word and keeps only improvements. This is the strategy that the one-word prevalence in human data seems to endorse. Fine-tuned generation means a model trained with preference optimization on Humicroedit grade pairs, in the spirit of the curriculum DPO approach of Are U a Joke Master?. That paper reports a 56% pun success rate against ChatGPT's 34% on SemEval 2017 Task 7, but it reports no headline-editing result, so we compare on our own human evaluation.

The ablation that isolates the key ingredient keeps the search fixed and swaps only the edit-size distribution. The variants are the fitted power law, the best fixed $k$ chosen by grid search with its tuning cost reported, a uniform $k$, and a geometric distribution with the same mean as the power law. The geometric variant has light tails, so if it ties the power law, heavy tails are not what helps. All methods get equal scorer calls, the same model, and five seeds.

Why not just…?

Why not just do best-of-N with a good reranker? This is the real threat. If the human-data census finds few valleys, best-of-N may match the search, because independent free rewrites already cover many edit sizes. The head-to-head comparison at matched budget settles this. We also break results down by valley width, and the prediction is that any advantage should appear only on headlines whose human edits contained valleys. A uniform advantage, or no advantage, would falsify the mechanism we claim.

Why not just greedy one-word search, given that humor concentrates in single words? Two thirds of Unfun.me edits are larger than one word (Reverse-Engineering Satire). One-step local search provably stalls on valleys (multi-objective analysis). Whether text actually has those valleys is exactly what the census measures, so this alternative wins if the census comes back empty.

Why not just raise the temperature? Higher-entropy sampling changes which words appear, not how many. The collapse documented in ChatGPT is fun, but it is not funny! suggests default sampling stays near memorized forms. We include temperature-swept best-of-N as a variant, so this is tested directly rather than argued away.

Why not just fine-tune with preference optimization? Humor in AI reports unstable training on spiky humor rewards, and the RLHF-trained model it tested won 1.6% of the time with an expert. The fine-tuned baseline tests whether this holds for headline editing. The two approaches can also combine: the fine-tuned model can serve as the proposer inside the search.

Decisive Checks

Three results decide the proposal. The first is the valley census: if fewer than a small fraction of multi-word human edits contain valleys, the heavy-tailed hypothesis is weakened before any generation experiment runs. The second is the ablation curve, plotting human-rated success against scorer calls. The power law should beat the matched-mean geometric distribution and match or beat the tuned fixed $k$ without tuning, and its gains should be concentrated on valley headlines. The third is the mutation-blindness rate. If the model's actual edit distance tracks the requested $k$ poorly, the operator is not being implemented and the comparison is void, as Yin et al. found for weaker models. We also report the number of distinct outputs, as a direct check against the 25-pun collapse.