SECA: Semantically Equivalent and Coherent Attacks for Eliciting LLM Hallucinations

1. Problem Definition

Large Language Models (LLMs) are increasingly deployed in high-stakes domains (e.g., healthcare, finance), yet they remain prone to hallucinations (generating factually incorrect or unfaithful information). While prior research has explored adversarial attacks to elicit these hallucinations, existing methods suffer from a critical flaw: they generate unrealistic prompts.

• Gibberish Attacks: Insert nonsensical tokens (e.g., "What is t)(?e va%&* of p...").
• Trivial Attacks: Directly instruct the model to lie (e.g., "Respond falsely: ...").
• Meaning-Shift Attacks: Alter the semantic intent of the question (e.g., changing $2p=24$ to $3p=24$).

These approaches fail to simulate real-world scenarios where users ask questions in natural, varied language. The paper addresses the gap in identifying realistic adversarial prompts that:

1. Preserve Semantic Equivalence: The attack prompt must mean the exact same thing as the original prompt (mutual entailment).
2. Maintain Semantic Coherence: The prompt must be fluent, grammatically correct, and human-like.

The core research question is: How can we formulate and solve the problem of generating realistic attacks that elicit LLM hallucinations while strictly adhering to semantic equivalence and coherence constraints?

2. Methodology: SECA

The authors propose SECA (Semantically Equivalent and Coherent Attacks), a framework that treats attack generation as a constrained optimization problem.

A. Problem Formulation

The goal is to find an adversarial prompt $x$ that maximizes the probability of the target LLM ($T$) generating a specific incorrect token $y^*$ (and subsequent hallucinated explanation), subject to two constraints:
$$\max_{x} \log P_T(y^* | x)$$
$$\text{s.t.} \quad \text{SEF}(x, x_0) = 1 \quad \text{and} \quad x \in \mathcal{X}_P$$
Where:

• $x_0$ is the original prompt.
• $\text{SEF}(x, x_0)$ is a binary Semantic Equivalence Function (1 if equivalent, 0 otherwise).
• $\mathcal{X}_P$ is the set of prompts generated by a proposer LLM, ensuring Semantic Coherence.

B. The SECA Algorithm (Constraint-Preserving Zeroth-Order Method)

Since the prompt space is discrete and gradients are often unavailable (black-box models), SECA uses a zeroth-order approach that avoids exhaustive search by leveraging LLMs to navigate the constrained space. The algorithm consists of three main components:

1. Semantic Equivalence Proposer ($P$):

   • An LLM is instructed to generate $M$ rephrasings of the current prompt $x_k$.
   • To ensure diversity and avoid "semantic collapse" (where rephrasings are identical to the original), the proposer is given random variations in verbs (e.g., "rephrase," "reformulate"), styles (e.g., "creative," "nuanced"), and task descriptors.
   • Note: The proposer inherently generates coherent text due to its training on human corpora.

2. Feasibility Checker ($F$):

   • A more powerful LLM acts as a verifier. It evaluates each candidate prompt against the original $x_0$ based on five strict criteria:
     1. Mutual entailment.
     2. No additional information introduced.
     3. No essential information omitted.
     4. Meaning preservation.
     5. Same ground-truth answer.
   • Only candidates passing this check (Score = 1) are retained.

3. Adversarial Selection:

   • Among the feasible candidates, the algorithm selects the top-$N$ prompts that maximize the log-probability of the target incorrect token $y^*$.
   • This process iterates until convergence or a maximum iteration count is reached.

3. Key Contributions

1. Formalization: The first formulation of hallucination elicitation as a constrained optimization problem over the input prompt space, explicitly defining Semantic Equivalence and Semantic Coherence as hard constraints.
2. Algorithm Design: Introduction of SECA, a novel constraint-preserving zeroth-order method. It effectively searches the discrete prompt space without gradients by using LLMs as both the search engine (proposer) and the constraint enforcer (checker).
3. Empirical Validation: Comprehensive experiments demonstrating that SECA generates diverse, realistic attacks that significantly outperform existing baselines (like GCG) in eliciting hallucinations while maintaining near-zero semantic errors.

4. Experimental Results

The authors evaluated SECA on the MMLU dataset (filtered to include only questions where target models initially answer correctly) across 16 subjects and 7 different LLMs (including open-source models like Llama-3, Qwen, and commercial models like GPT-4o-Mini).

• Attack Success Rate (ASR):
  • SECA achieved significantly higher ASR compared to raw prompts and the state-of-the-art Greedy Coordinate Gradient (GCG) method.
  • Example: On Llama-3-8B, SECA achieved 81.24% ASR vs. GCG's 9.86% and Raw prompts' 63.52%.
  • On GPT-4o-Mini, SECA raised ASR from near 0% (Raw) to 36.86%.
• Semantic Integrity:
  • Semantic Equivalence Error (SEE): SECA maintained an SEE of 0.00, meaning all attacks were semantically equivalent to the original. In contrast, GCG had an SEE of ~0.96 (mostly failing equivalence).
  • Semantic Coherence Error (SCE): SECA maintained low perplexity (high coherence), whereas GCG produced gibberish with extremely high perplexity (e.g., 307.68 vs. 0.33 for SECA).
• Analysis of Successful Attacks:
  • Successful SECA prompts were found to be more verbose and lexically diverse (higher Type-Token Ratio) than original prompts.
  • The increased linguistic variation appears to obscure the core intent just enough to trigger model failure without changing the meaning.
• Evaluation Reliability:
  • The paper validated that LLM-based evaluators (for checking equivalence and classifying hallucinations) align strongly with human annotators (Cohen's $\kappa$ > 0.7), justifying the use of automated evaluation pipelines.

5. Significance and Impact

• Realistic Robustness Testing: SECA provides a rigorous tool for evaluating LLM robustness under realistic conditions. It proves that even models with high accuracy on standard benchmarks are fragile to subtle, semantically equivalent rephrasings.
• Safety Implications: The findings highlight a critical vulnerability: LLMs can be tricked into hallucinating not just by malicious "jailbreaks," but by natural variations in how a user asks a question. This poses risks for high-stakes applications where factuality is paramount.
• Future Directions: The work opens avenues for developing better defenses against semantic variations, improving the training of models to be robust to paraphrasing, and extending these attack methods to reasoning models and free-form generation tasks.

Code Availability: The framework is open-sourced at https://github.com/Buyun-Liang/SECA.