🤖 AI

Semantic Voting: Execution-Grounded Consensus for LLM Code Generation

This paper demonstrates that for LLM code generation without a complete oracle, execution-based consensus methods significantly outperform output-pattern voting, with the quality of generated test inputs being the primary driver of success rather than the specific aggregation rule employed.

Original authors: Shan Jiang, Zijian Yi, Chenguang Zhu

Published 2026-05-12

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Shan Jiang, Zijian Yi, Chenguang Zhu

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a hiring manager trying to pick the best candidate for a coding job. You have a large pool of applicants (generated by an AI), but you don't have a perfect "answer key" to check their work against. You just have to guess which one is right based on how they perform in a test.

This paper is like a massive experiment to figure out the best way to run that interview and pick the winner. The researchers tested 18 different scenarios using various AI models and found three big secrets about how to choose the right code.

Here is the breakdown in simple terms:

1. The Problem: The "All-or-Nothing" Trap

Most systems currently use a method called Majority Voting. Imagine you give all the candidates a single math problem. If a candidate gets the answer right, they get a vote. If they get it wrong (or crash), they get zero votes. The winner is the one with the most votes.

The paper argues this is like a broken voting machine.

The Flaw: If a candidate makes one tiny mistake on a weird test question (like dividing by zero), the system throws their entire application in the trash, even if they were perfect on everything else.
The Result: This method often picks the wrong person or no one at all because it's too sensitive to small errors.

2. The Solution: The "Fingerprint" Approach (Semantic Voting)

The researchers propose a new method called Semantic Voting. Instead of just checking "Right or Wrong," they look at the candidate's fingerprint.

The Analogy: Imagine you don't just ask, "Did you solve the puzzle?" Instead, you watch how they solve it. Did they get stuck on a specific step? Did they crash on a specific type of number?
How it works: The system runs the code on many different test inputs. It records the exact pattern of results (e.g., "Got the answer," "Crashed on negative numbers," "Timed out"). It groups candidates who have the exact same pattern.
The Benefit: Even if everyone crashes on one weird test, the system can still see that 40 out of 50 candidates crashed in the exact same way, while 10 crashed differently. It picks the group with the most consistent "fingerprint," preserving valuable information that the old method would have thrown away.

3. The Three Big Discoveries

Discovery #1: The "Fingerprint" Wins Big

The new "Fingerprint" method (and similar execution-based methods) is massively better than the old "Right/Wrong" voting.

The Stat: It improved accuracy by 19% to 52% across the board.
The Takeaway: It's much better to look at the details of how the code behaves than to just count how many times it got a perfect score.

Discovery #2: The "Test Questions" Matter More Than the "Scoring Rules"

Once you decide to use the "Fingerprint" method, it doesn't actually matter which specific rule you use to count the votes. Whether you use the new "Semantic Voting," a "Weighted Voting" system, or an "MBR" system, they all perform almost identically.

The Real Hero: The most important factor is how you create the test questions.
The Analogy: Imagine you are testing a car.
- Bad Test: You only drive on a perfectly smooth, empty road (Random fuzzing or simple examples). The car looks great, but it fails in the real world.
- Good Test: You ask an expert to design specific scenarios: "Drive on a muddy hill," "Drive through a puddle," "Drive in reverse."
The Result: Using "Sketch-based" inputs (where the AI is asked to invent specific types of challenges, like "a list with duplicates" or "an empty list") was the single biggest factor in success. It beat random testing by up to 11%.
The Lesson: If your test questions are good, the specific way you tally the scores doesn't matter much. If your test questions are bad, no scoring rule can save you.

Discovery #3: "Deep Thinking" Doesn't Always Help

The researchers tested if making the AI "think harder" (using more time to reason before answering) helped.

The Surprise: For the old "Right/Wrong" voting, thinking harder helped a lot. But for the new "Fingerprint" method, thinking harder actually made things slightly worse or stayed the same.
Why? When the AI thinks too hard, it tends to produce very similar answers. This reduces the "diversity" of the candidates. If everyone thinks so hard that they all make the same mistake, the system can't find the unique, correct solution. It's like a choir where everyone sings the same wrong note perfectly in tune; it doesn't help you find the right song.

Summary: What Should We Do?

The paper concludes that when we don't have a perfect answer key, the quality of the evidence matters more than the rule we use to count it.

Stop using simple "Pass/Fail" voting. It throws away too much useful information.
Focus on making better test cases. Ask the AI to generate diverse, specific scenarios (like "a list of negative numbers") rather than just random ones.
Don't overthink the scoring. Once you have good tests and a way to track behavior, the specific math you use to pick the winner matters very little.
Don't force the AI to think too long. Sometimes, a bit of variety in the answers is better than everyone trying to be perfect.

In short: Better questions beat better scoring rules.

Technical Summary: Semantic Voting – Execution-Grounded Consensus for LLM Code Generation

Problem Statement

Large Language Models (LLMs) generate code, but selecting the correct solution from multiple sampled candidates remains challenging when a complete oracle (a full test suite) is unavailable. Existing pipelines typically combine textual voting, ranking heuristics, and execution-based agreement, yet the relative contributions of these components are unclear. Specifically, prior work often conflates two critical axes:

The value of richer behavioral evidence (e.g., exception-aware execution traces) versus "all-or-nothing" output-pattern voting.
The relative importance of input quality versus the aggregation rule once behavioral evidence is utilized.

Current baselines, such as Output-Pattern Majority Voting (MV), often discard candidates that crash on any generated input, reducing selection to an exact match of concatenated return strings. This approach is sensitive to imperfect generated inputs and fails to preserve partial behavioral evidence.

Methodology: SEMANTICVOTE and Experimental Design

The SEMANTICVOTE Pipeline

The authors introduce SEMANTICVOTE, a method designed to study execution-based consensus. Unlike standard MV, SEMANTICVOTE retains "exception-aware execution fingerprints."

Candidate Generation: An LLM samples $N$ candidate solutions.
Input Generation (Sketch-Based): The LLM generates $K$ abstract input sketches (e.g., "an empty list," "a list with duplicates") targeting distinct behavioral equivalence classes. Each sketch is instantiated $M$ times with concrete values, yielding $D = K \times M$ diverse test inputs.
Fingerprinting: Each candidate is executed on all $D$ inputs in a sandbox. The system records a fingerprint vector: a tuple of (status, value) pairs for each input, where status includes success, exception type, or timeout.
Clustering: Candidates are clustered by exact equality of their fingerprints.
Selection: The system selects the representative from the largest cluster. If an "all-success" cluster exists, it is preferred; otherwise, the largest exception-aware cluster is chosen. The shortest program in the selected cluster is returned (Occam's razor).

Experimental Setup

The study evaluates 18 configurations across:

Models: Three Gemini preview endpoints (3.1 Pro, 3 Flash, 3.1 Flash Lite).
Thinking Levels: Low, Medium, and High.
Benchmarks: HumanEval+ and MBPP+ (augmented versions with significantly more test cases).

The authors compare SEMANTICVOTE against:

Output-Pattern Majority Voting (MV): Discards any candidate with an execution error; clusters by exact output string.
Weighted Voting (WV): Groups by output pattern but weights candidates by their success rate.
MBR-Exec: Selects the candidate with the highest sum of agreements on input outputs/exceptions.
AST-normalized MV: A structural baseline that groups by canonical AST structure.

Key Findings

1. Execution-Based Selection Outperforms Output-Pattern Voting

Across all 18 configurations, the best execution-based selector (SEMANTICVOTE, WV, or MBR-Exec) exceeds Output-Pattern Majority Voting by 19–52 percentage points.

Output-pattern MV consistently underperforms even simple "Best-of-N" (selecting the first syntactically valid candidate) and often fails entirely when generated inputs cause all candidates to crash.
The primary failure mode of MV is its "all-success" filter, which discards candidates that are correct on the benchmark but fail on a specific generated input. Execution-based methods preserve partial agreement and exception types, allowing them to recover correct solutions.

2. Input Quality is the Primary Driver of Performance

Once candidates are executed on diverse inputs, the specific aggregation rule (SEMANTICVOTE vs. Weighted Voting vs. MBR-Exec) has a limited effect.

Statistical Indistinguishability: Paired bootstrap tests show no significant difference ( $p > 0.05$ ) between SEMANTICVOTE and the other execution-based aggregators across all 18 configurations. The performance difference is negligible (e.g., SEMANTICVOTE differs from Weighted Voting by only $-0.79$ to $+0.61$ pp).
Input Strategy Dominance: The choice of input generation strategy is the largest source of variance.
- Sketch-based generation (abstract categories instantiated concretely) is the strongest strategy, outperforming direct LLM input generation by 0.6–2.1 pp and random fuzzing or example-only inputs by up to 11.3 pp.
- This benefit transfers consistently to all three execution-based aggregators.

3. Interaction with Thinking Depth

The impact of "thinking level" (reasoning budget) differs between selection families:

Output-Pattern MV: Deeper thinking improves performance (e.g., +12 pp on HumanEval+ Flash) by generating more consistent outputs.
Execution-Based Methods: Performance remains flat or slightly degrades with deeper thinking. The authors hypothesize that deeper thinking reduces candidate diversity, leaving fewer distinct behavioral clusters to exploit, which limits the utility of execution-based consensus.

4. Oracle-Gap Decomposition

Failure analysis reveals that generation failures (no correct candidate in the pool) are the dominant bottleneck, accounting for the majority of errors. Selection failures (a correct candidate exists but is not chosen) average only 1.5–2.7%.

Because the pool of correct candidates is small, there is little room for any aggregation rule to differentiate performance, explaining the convergence of SEMANTICVOTE, WV, and MBR-Exec.
Increasing the number of test inputs ( $D$ ) yields diminishing returns; performance saturates around $D=30$ , with $D=10$ capturing most of the gain.

Significance and Scope

The paper positions itself as an empirical decomposition rather than a novel method proposal. Its primary contribution is reframing inference-time code selection as a signal-quality problem rather than an aggregation-rule problem.

Signal Quality: When oracles are unavailable, the quality of the behavioral evidence (derived from diverse, well-structured inputs) matters significantly more than the rule used to aggregate that evidence.
Practical Implication: To improve code selection, practitioners should prioritize generating diverse, behaviorally representative test inputs (e.g., via sketch-based generation) over optimizing complex voting algorithms.
Limitations: The study is limited to Python benchmarks and Gemini models. The sketch-based input generation relies on the LLM's domain familiarity, and programs with intentional nondeterminism may produce inconsistent fingerprints.

The authors conclude that while SEMANTICVOTE serves as the instrument for evaluation, the convergence of execution-based methods suggests that once high-quality behavioral traces are established, the specific clustering or weighting mechanism becomes secondary.