Greedy selection, which repeatedly adds whichever item adds the most value, has a well-known puzzle. Its worst-case guarantee for "diminishing returns" objectives says it reaches only about 63% of the best possible value. On real data it routinely reaches 85–95% or more, and instance-specific certificates now confirm this at scale. A recent line of work, Verbalized Algorithms, places a large language model (LLM) inside greedy selection as the judge of each item's added value. It does this for choosing documents for multi-hop question answering, and it quotes the same worst-case 63% guarantee. That guarantee assumes the judge is exact. An LLM judge is not exact, and nobody has measured how much of the comfortable empirical margin survives a noisy judge, or where the losses come from.
This note proposes to measure exactly that, on selection tasks where the true objective is known but the LLM sees only text. The total shortfall from optimal splits into three parts: algorithmic loss (greedy versus optimum), judging loss (LLM-judged greedy versus exact greedy), and one-shot reasoning loss (an LLM asked to pick the whole set at once). We then use the split to build a cheaper judge-repair rule. It spends extra LLM votes only at greedy steps where the top candidates' estimated gains are close, because only there can a judging error change the choice.
Core Claim
We expect two things. The first is that one-shot LLM selection loses value in proportion to set size and distractor density, consistent with the compounding-error and working-memory failures catalogued in Large Language Model Reasoning Failures. The second is that LLM-judged greedy loses value mainly at a small number of "near-tie" steps, and that how many such steps occur depends on the objective's curvature. Curvature measures how far an objective is from simply adding up item values, and it is what Curvature and Optimal Algorithms for Learning and Minimizing Submodular Functions and On Greedy Maximization of Entropy use to explain greedy's good empirical behavior.
If both hold, verification effort should go to near-tie steps rather than being spread evenly. Spending it this way should match uniform majority voting at a fraction of the LLM calls.
The reasoning behind margin-based allocation is a standard inexact-greedy argument. Suppose that at step $t$ greedy picks an item whose true gain falls short of the best available gain by $\epsilon_t$. Then the final set $S$ satisfies
$$f(S) \ge (1 - 1/e)\,\mathrm{OPT} - \sum_{t=1}^{k} \epsilon_t,$$
where $f$ is the true objective, $\mathrm{OPT}$ its optimum over sets of size $k$, and the bound follows from carrying the per-step shortfall through the usual telescoping proof. A judging error makes $\epsilon_t$ large only when it reverses the order of two candidates whose true gains differ substantially. When the top gains are well separated, even a coarse judge picks correctly. When they are nearly tied, a wrong pick costs little. The steps that matter are therefore those with moderate true separation and noisy estimates. These are the steps the allocation rule tries to find, using the estimated margin and its variance across a few cheap probes.
Relation to Prior Work
The submodular side supplies the measuring instruments and motivates the question. Instance Specific Approximations for Submodular Maximization introduced DUAL, an $O(n \log n)$ method that bounds the optimum from above by lower-bounding the companion covering problem. It certifies greedy ratios of at least 0.85, frequently above 0.95, on real datasets, and runs over 1,000 times faster than curvature or sharpness checks. On the Unreasonable Effectiveness of the Greedy Algorithm: Greedy Adapts to Sharpness explains the same behavior through sharpness, meaning how strongly marginal gains track distance from the optimum. Sharpness needs the optimum to compute, so it is explanatory rather than usable at runtime. Approximate Submodularity and its Applications shows that the submodularity actually encountered along greedy's path is much better than the worst case over the whole dataset. All of these assume exact function values. We reuse DUAL as an instrument for certifying how close each method gets to optimal, and we study the case they leave out: gains estimated by a noisy text judge.
On the LLM side, Verbalized Algorithms is the closest work. It wraps LLM pairwise or triplet judgments in classical algorithms, including greedy document selection on HotpotQA and CUAD. It uses majority voting and order-swapping to counter positional bias, and it reports that a 1.7B model inside an algorithm beats a 32B model reasoning in one shot. It does not measure how far its greedy selection falls from optimal, it does not separate judging error from algorithmic error, and it notes the cost of its polynomial number of LLM calls without addressing it. Our proposal targets all three of these gaps.
Prompt-construction work such as SMILE, Submodular Context Partitioning and Compression for In-Context Learning and Submodular-based In-context Example Selection for LLMs-based Machine Translation computes the objective with embeddings and treats the LLM only as the consumer of the selected prompt. For us, these methods are the "no LLM judge" competitor.
Several LLM-side findings constrain the design. Can Large Language Models Always Solve Easy Problems if They Can Solve Harder Ones? shows that minor distractors break models that handle harder versions of a problem, so distractor density must be a controlled variable. Thought Anchors shows that a few steps in a reasoning trace carry most of the causal weight. We test the analogous claim for greedy steps: that a few near-tie decisions carry most of the loss. The heuristic early stopping of Multi-TAG is the nearest existing mechanism for spending verification adaptively. It stops when tools agree, without any tie to the objective's structure.
We considered treating chain-of-thought steps themselves as a diminishing-returns system, but rejected it. The anchor findings suggest reasoning steps are often complementary: a step is worthless until a later one completes it. That breaks the premise that would make greedy theory apply.
Research Program
We build two families of selection tasks. In both, the true objective is weighted coverage of a ground-truth set of facts, which the LLM never sees directly.
The first family is derived from HotpotQA. We pool the gold and distractor paragraphs of several questions into one candidate set and pose a multi-part information need. The sentence-level supporting-fact labels then define exactly which facts each paragraph covers. Pool size $n$ and budget $k$ can be scaled well beyond the two gold paragraphs of the standard distractor setting.
The second family is synthetic. Items are short texts that each mention a controlled subset of facts. We tune the overlap between items to sweep curvature from near zero, where items cover separate facts and greedy is exactly optimal, to high, where items heavily overlap. We separately insert near-duplicate distractors that look relevant but add no new facts.
On every instance we run the following:
- exact greedy on the true objective;
- an exact optimum by integer programming where the instance is small enough, and a DUAL upper bound otherwise;
- one-shot LLM selection with chain-of-thought;
- LLM-judged greedy in the style of Verbalized Algorithms;
- our margin-adaptive variant.
The resulting error split is measured, not modeled. Algorithmic loss is exact greedy against the bound. Judging loss is LLM-judged greedy against exact greedy. One-shot loss is one-shot selection against exact greedy. For each step of LLM-judged greedy we log the true margin between the top two candidates, the estimated margin, and whether the pick was wrong. This lets us test directly whether loss concentrates in near-tie steps.
We also run DUAL on the LLM-estimated gains, giving an "estimated certificate". We check whether it tracks the true certified ratio closely enough to serve as a runtime audit when no ground truth exists.
Baselines
The naive reference points are top-$k$ by BM25 and top-$k$ by embedding similarity. Verbalized Algorithms reports that its greedy selection beats both on document retrieval likelihood, though no reported numerical result was found on Lacuna for that comparison. These baselines use no LLM calls during selection and are evaluated on the identical pools and budgets.
The second baseline is one-shot LLM selection with chain-of-thought, plus a self-consistency variant that samples several selections and takes the most frequent items. The number of samples is matched to our method's total LLM-call budget, so the comparison is decided by how calls are spent rather than how many are made.
The strongest existing competitor is robust LLM-judged greedy from Verbalized Algorithms. It applies majority voting and order-swapped prompts uniformly at every step. We run it with the same judge model, the same prompts, and the same comparison format. We sweep its votes per step to trace a full quality-versus-calls curve. Beating it means one of two things on held-out instances: reaching its plateau certified ratio with substantially fewer calls (we target at least a 2x reduction), or reaching a higher certified ratio at equal calls.
Two ablations isolate the key ingredient. The first gives the same total vote budget to randomly chosen steps instead of near-tie steps. The second allocates votes by the judge's self-reported confidence rather than by estimated margin. If margin-based allocation does not beat both, the structural argument above adds nothing over generic uncertainty.
Exact greedy on the true objective, and the integer-programming optimum, are reported as ceilings rather than competitors.
For downstream relevance on the HotpotQA-derived pools, we feed each method's selected paragraphs to a fixed reader model and report answer F1. As context for those numbers, published references on standard HotpotQA are 58.28 answer F1 for the BiDAF baseline and 91.40 for humans in the distractor setting (HotpotQA). ChatCoT reports 59.2% accuracy versus 38.0% for standard chain-of-thought. These figures describe a different setup and are orientation only, not targets.
Why not just…?
Why not just use a larger model for one-shot selection? The evidence available cuts against it. Measuring Mathematical Problem Solving With the MATH Dataset found that multi-step reasoning does not follow smooth scaling. Verbalized Algorithms found a small model inside an algorithm beating a much larger one reasoning in one shot. Still, our tasks are new, so we test this directly. We run one-shot selection at two or more model sizes across a sweep of $k$ and distractor density. If the largest model's one-shot loss stays flat as $k$ grows, the case for wrapping the LLM in greedy weakens, and we will report that.
Why not just vote uniformly at every step? This is the most serious threat. Uniform voting is simple, and if judging errors are spread evenly across steps, adaptive allocation cannot help. The per-step logs settle the question directly. If the fraction of total loss carried by the top-decile-margin-risk steps is no larger than chance, the allocation idea fails. In that case the contribution reduces to the error split alone.
Why not just compute gains with embeddings, as in SMILE-style selection, and skip the LLM judge? Embedding coverage is cheap and gives an exact greedy on a proxy objective. It is a real competitor when surface similarity tracks fact coverage. Our near-duplicate distractors are built to break that link: they look similar but add nothing new. HotpotQA's bridge questions, which make up 42% of the dataset, need facts that are not lexically close to the query. We report both regimes. If embeddings match the LLM judge on the natural pools, the LLM judge is justified only under adversarial distractors.
Why not just compare to greedy's own value instead of computing certificates? A ratio against greedy is only meaningful when greedy is itself near-optimal on that instance, and that is precisely what is unknown at scale. On small instances we use the exact optimum, which makes certificates unnecessary there. DUAL earns its place only on large pools. We also check that conclusions drawn with DUAL agree with exact-optimum conclusions where both are available.
Decisive Checks
The proposal stands or falls on four results.
The first is whether judging loss concentrates in near-tie steps. Concretely, steps ranked by estimated margin risk should capture most of the gap between LLM-judged greedy and exact greedy.
The second is whether that concentration grows with curvature in the synthetic sweep. The prediction is that low-curvature instances are robust to judge noise and high-curvature ones are not.
The third is whether margin-adaptive voting dominates both uniform voting and the random and confidence ablations on the quality-versus-calls curve.
The fourth is whether DUAL computed on LLM-estimated gains ranks instances by true certified ratio well enough to flag bad selections at runtime. We will measure this with rank correlation against the true certificate.
A negative result on the first check is informative in its own right. It would mean the comfortable empirical margin of greedy erodes evenly under an LLM judge, and that the worst-case guarantee quoted by verbalized greedy describes an algorithm the system is not actually running.
References
- Verbalized Algorithms
- Large Language Model Reasoning Failures
- Curvature and Optimal Algorithms for Learning and Minimizing Submodular Functions
- On Greedy Maximization of Entropy
- Instance Specific Approximations for Submodular Maximization
- On the Unreasonable Effectiveness of the Greedy Algorithm: Greedy Adapts to Sharpness
- Approximate Submodularity and its Applications: Subset Selection, Sparse Approximation and Dictionary Selection
- SMILE: Extended Deep Submodular Function-Based Instruction and In-context Learning Demonstration Selection
- Submodular Context Partitioning and Compression for In-Context Learning
- Submodular-based In-context Example Selection for LLMs-based Machine Translation
- Can Large Language Models Always Solve Easy Problems if They Can Solve Harder Ones?
- Thought Anchors: Which LLM Reasoning Steps Matter?
- A Toolbox, Not a Hammer - Multi-TAG: Scaling Math Reasoning with Multi-Tool Aggregation
- HotpotQA: A Dataset for Diverse, Explainable Multi-hop Question Answering
- ChatCoT: Tool-Augmented Chain-of-Thought Reasoning on Chat-based Large Language Models
- Measuring Mathematical Problem Solving With the MATH Dataset