Reducing Hallucinations in LLM-Generated Code via Semantic Triangulation

1. Problem Statement

Large Language Models (LLMs) can generate executable code from natural language, but the output frequently contains bugs due to hallucinations (confabulations). Current methods to mitigate this rely on:

• Plurality Voting: Selecting the most frequent output among multiple samples.
• Proxy Verification: Using LLM-generated tests or auto-formalized specifications (e.g., Hoare triples) to verify correctness.

Limitations of Existing Approaches:

• Correlated Errors: LLMs often produce the same errors across different samples. Plurality voting amplifies these dominant errors rather than filtering them out.
• Biased Proxies: Since tests and specifications are also generated by the same imperfect LLM, they often "corroborate" the hallucinated code rather than catching errors. For example, an auto-generated specification might be overly permissive (e.g., True), accepting both correct and incorrect code.
• Inexact Problems: Many coding tasks allow multiple valid solutions (non-equivalent correct outputs). Existing consensus methods struggle here because they assume a single correct answer, leading to the rejection of valid solutions that differ from the majority.

2. Methodology: Semantic Triangulation

The authors propose Semantic Triangulation, a theory-grounded framework designed to decorrelate model errors by transforming the original coding task into a dissociative variant.

Core Concept

Instead of asking the LLM to solve the same problem repeatedly, the framework:

1. Transforms the original problem $d$ into a new problem $d'$ using a dissociative transformation $\tau$. This transformation must require a fundamentally different algorithm (e.g., inverting a function requires a parser where the original required a printer).
2. Samples solutions for both $d$ and $d'$.
3. Checks Consistency using a hyperproperty $\phi$ that defines a relationship between solutions to $d$ and $d'$.
4. Selects solutions where the consistency check passes, serving as "plausibility witnesses."

Theoretical Requirements

For the framework to provably increase confidence, the transformation and consistency check must satisfy two properties:

1. Bijection-Inducing: The relationship $\phi$ must establish a one-to-one correspondence between equivalence classes of programs for $d$ and $d'$. This ensures that distinct errors in the original problem map to distinct errors in the transformed problem, making it statistically unlikely for two independent hallucinations to match by chance.
2. Correctness-Coupling: The correspondence must preserve correctness. A correct solution to $d$ must map to a correct solution to $d'$.

Concrete Implementations (The just-tri-it Tool)

The authors instantiate this framework with four methods, all automatically generated via LLM prompting:

• FWD-INV (Full Inversion): Transforms a function $f(x) \to y$ into finding $x$ given $y$.
• FWD-SINV (Set-valued Partial Inversion): Handles non-bijective functions by returning all inputs that produce a specific output.
• ENUM-SINV (Answer Enumeration): For inexact problems, it generates an "enumerator" that lists all valid outputs for a given input, then triangulates this against a set-valued inverse.
• STREAM: Decomposes stream-processing problems into pointwise operations to apply triangulation.

The framework uses RANSAC (Random Sample Consensus) to aggregate agreements across the sample pool, allowing the system to abstain from selecting a solution if no consistent candidate is found.

3. Key Contributions

1. Semantic Triangulation Framework: A novel, theory-grounded approach to hallucination detection that uses dissociative problem transformations to decorrelate errors, proven to outperform plurality voting under a formal model of LLM hallucinations.
2. Theoretical Guarantees: Formal proofs (mechanized in Lean) demonstrating that under assumptions of "stochastic parrots" (LLMs relying on shallow features) and correlated errors, semantic triangulation strictly increases the probability of identifying correct code compared to standard voting.
3. Handling Inexact Problems: The ENUM-SINV method is the first to reliably handle tasks with multiple valid, non-equivalent solutions, a known weakness of previous consensus methods.
4. Practical Tool (just-tri-it): An implementation supporting Python code generation that integrates these triangulation methods.

4. Experimental Results

The tool was evaluated on LiveCodeBench (175 problems) and CodeElo-Inexact (31 inexact problems) using three state-of-the-art models: GPT-4o, DeepSeek-V3, and Gemini 2.5 Flash.

• Confidence Enhancement: Triangulation increased the probability of selecting a correct program by 24% over the strongest baselines (test generation, metamorphic testing, and auto-formalized specifications).
• Selection & Abstention:
  • Achieved a 26% higher F1 score in selection-or-abstention scenarios compared to baselines.
  • Successfully identified correct solutions with very low sampling probabilities (as low as 0.07), whereas baselines often abstained or selected errors.
  • Outperformed "Majority Voting with threshold 0.5" by 8% in reliable accuracy.
• Inexact Problems: It was the only method that consistently handled inexact problems without degrading performance, whereas baselines failed to form consensus on tasks with multiple valid answers.
• Ablation Study: Removing the "bijection-inducing" property caused a 23% drop in correctness probability, confirming the theoretical necessity of the framework's design.
• Cost: The method incurs a 2.5x increase in time and 4.9x more tokens compared to simple plurality voting, but offers significantly higher reliability.

5. Significance

This paper addresses a critical bottleneck in LLM-assisted software engineering: the inability to reliably verify code when the model itself is the source of both the code and the verification logic.

• Paradigm Shift: It moves beyond "more sampling" (plurality) to "different perspectives" (triangulation), effectively breaking the correlation of errors.
• Robustness: By mathematically proving that dissociative transformations reduce the likelihood of coincidental error matching, it provides a theoretical foundation for reliable code generation.
• Practical Impact: The ability to handle inexact problems and low-probability correct solutions makes this approach viable for complex, real-world coding tasks where multiple valid implementations exist and perfect solutions are rare.

In summary, Semantic Triangulation offers a principled, black-box mechanism to significantly boost the trustworthiness of LLM-generated code, particularly in scenarios where traditional voting and specification-based verification fail.