🤖 AI

SemLoc: Structured Grounding of Free-Form LLM Reasoning for Fault Localization

SemLoc is a novel fault localization framework that converts free-form LLM reasoning into a structured, verifiable intermediate representation to generate a semantic violation spectrum, thereby significantly outperforming existing coverage-based and LLM-based methods in identifying root causes of semantic bugs.

Original authors: Zhaorui Yang, Haichao Zhu, Qian Zhang, Rajiv Gupta, Ashish Kundu

Published 2026-04-01

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Zhaorui Yang, Haichao Zhu, Qian Zhang, Rajiv Gupta, Ashish Kundu

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 detective trying to solve a crime in a busy city. The city is your computer program, and the "crime" is a bug that causes the program to crash or give wrong answers.

The Old Way: Counting Footprints

For a long time, detectives (software engineers) solved these crimes by looking at footprints. They would ask: "Which streets did the criminal walk on?"

The Method: They checked which parts of the code were "visited" by the tests that failed versus the tests that worked.
The Problem: Sometimes, the criminal (the bug) doesn't leave footprints. They might walk down the exact same street as the innocent people, but they are carrying a hidden weapon (a semantic error).
- Example: Imagine a recipe for soup. If you add salt, it tastes good. If you add too much salt, it tastes terrible. But the recipe steps are identical. If you just look at the list of steps taken (the footprints), you can't tell which step went wrong. The old methods get confused because the "footprints" look the same for both the good and bad outcomes.

The New Detective: SEMLOC

The paper introduces SEMLOC, a new kind of detective that doesn't just count footprints. Instead, it asks the program: "What were you supposed to do?"

Here is how SEMLOC works, broken down into simple steps:

1. The "AI Consultant" (The LLM)

SEMLOC hires a super-smart AI consultant (a Large Language Model) to read the code.

Old AI: The old way asked the AI, "Where is the bug?" The AI would just guess a line of code. Sometimes it was right, sometimes wrong, and it couldn't prove why.
SEMLOC's AI: This time, SEMLOC tells the AI: "Don't just guess the location. Tell me the rules the code is breaking."
- Analogy: Instead of pointing at a suspect and saying "He did it," the AI says, "The suspect broke the rule: 'You must not carry a weapon over 5 pounds.'"

2. Turning Rules into "Sniffer Dogs" (Structured Grounding)

This is the magic trick. The AI's rules are just words. SEMLOC takes those words and turns them into Sniffer Dogs (executable checks) that can actually run inside the program.

It attaches a specific "Sniffer Dog" to a specific part of the code.
Example: If the AI says, "The list of numbers must never be empty," SEMLOC puts a tiny sensor on the code that checks: "Is this list empty? If yes, bark!"

3. The "Spectrum of Barking" (Semantic Spectrum Analysis)

Now, SEMLOC runs the program with many different test cases (some that work, some that fail).

The Old Way: Looked at which streets were walked on.
SEMLOC's Way: Listens to which Sniffer Dogs barked.
- If a dog barks only when the program crashes, that dog found the real culprit!
- If a dog barks when the program works and when it crashes, that dog is just confused (it's barking at a symptom, not the cause).

4. The "What-If" Test (Counterfactual Verification)

Sometimes, a dog barks because of a chain reaction.

Analogy: Imagine a house fire. The smoke detector (Dog A) barks because of smoke. The fire alarm (Dog B) barks because of heat. But the fire started in the kitchen.
SEMLOC asks a "What-If" question: "If we fixed the problem the dog found, would the fire stop?"
It virtually patches the code and re-runs the tests.
- If the crash disappears, that was the Root Cause.
- If the crash stays, that dog was just barking at the smoke (a side effect), so SEMLOC ignores it.

The Result: A Laser-Focused Solution

In the real world, SEMLOC found that:

Old methods had to check almost half the code to find the bug.
SEMLOC narrowed it down to less than 8% of the code.
It found the exact line of the bug 42% of the time on the very first try (compared to only 6% for old methods).

Summary Analogy

Old Method: A detective looking at a map of where people walked. If everyone walked the same path, the detective is stuck.
SEMLOC: A detective who asks, "What are the laws of physics here?" Then, it sets up motion sensors to see exactly where the laws of physics were broken. Finally, it runs a simulation to see if fixing that specific break stops the disaster.

In short: SEMLOC stops guessing where the bug is and starts proving why the code is wrong, turning vague AI guesses into hard, checkable evidence.

1. Problem Statement

Fault localization (FL) aims to identify the specific code locations responsible for software failures. Existing techniques primarily rely on syntactic spectra (e.g., statement coverage, control-flow divergence, or dependency reachability). While effective for structural bugs, these methods fail when failures stem from semantic bugs.

The Limitation: In semantic bugs (e.g., off-by-one errors, missing normalization, incorrect relational operators), passing and failing executions often traverse identical code paths with identical coverage profiles. The only difference lies in whether semantic intent (invariants, constraints) is honored.
The LLM Gap: Recent Large Language Model (LLM) approaches attempt to use semantic reasoning but suffer from stochasticity and lack of grounding. They produce free-form natural language outputs that vary across runs, cannot be systematically cross-referenced against runtime evidence, and lack mechanisms to distinguish root causes from cascading downstream symptoms.

2. Methodology: SEMLOC Framework

SEMLOC is a fault localization framework that converts free-form LLM semantic reasoning into executable, checkable evidence through a structured intermediate representation. It operates in four stages:

A. Structural Anchor Extraction

Before invoking the LLM, SEMLOC parses the target Python program using Tree-sitter to extract structural anchors. It performs a lightweight Static Single Assignment (SSA) transformation to:

Identify specific program locations (entry, return, loop heads/tails, variable definitions, and uses).
Version variables (e.g., x__1, x__2) to resolve ambiguity in control-flow paths.
Generate a definition map linking SSA names to precise byte offsets for instrumentation.

B. Agentic Semantic Grounding (Constraint Inference)

SEMLOC prompts an LLM (e.g., Claude Sonnet 4.6 or Gemini 2.5 Pro) to infer semantic constraints. Crucially, the prompt enforces a Closed Intermediate Representation (cbfl-ir):

Structured Output: The LLM must output JSON conforming to a strict schema, selecting from a closed set of 9 constraint categories (e.g., PRECONDITION, POSTCONDITION, VALUE_RANGE, RELATION).
Grounding: Constraints must reference specific SSA-versioned anchors (e.g., anchor: {"var": "shifted__1"}) and instrumentation regions (e.g., AFTER_DEF).
Result: This converts vague LLM reasoning into precise, typed, executable boolean predicates bound to specific code locations.

C. Semantic Spectrum Analysis

SEMLOC instruments the program to evaluate the inferred constraints against the test suite ( $T = T^+ \cup T^-$ ):

Execution: It runs all tests and records which constraints are violated.
Spectrum Matrix: It constructs a constraint-by-test violation matrix ( $V$ ).
Scoring: It calculates a suspiciousness score for each constraint using the Ochiai coefficient (similar to traditional SBFL), based on how often a constraint is violated in failing tests ( $e_f$ ) versus passing tests ( $e_p$ ).
Propagation: Scores are propagated from violated constraints to the specific statements that established the violated property (e.g., the assignment line).

D. Counterfactual Verification

To handle noise (over-approximate constraints violated in both passing/failing tests) and cascading effects, SEMLOC applies a causal verification step:

Over-approximation Check: Constraints violated in passing tests are immediately discarded.
Patch Generation: For high-scoring constraints, the LLM generates a minimal counterfactual patch (a hypothetical fix) for the attributed line.
Re-execution: The patched program is re-run.
- Primary: If the patch makes all failing tests pass, the location is the root cause.
- Secondary: If the patch reduces but doesn't eliminate failures, it is a cascading effect.
- Irrelevant: If the patch has no effect, the constraint is pruned.
Pruning: Dominance-based pruning removes redundant constraints, retaining only those with primary causal status.

3. Key Contributions

Structured Semantic Grounding: A novel framework that converts unstructured LLM reasoning into a closed, executable intermediate representation (cbfl-ir) bound to typed program anchors.
Semantic Spectrum Analysis: A method to rank code locations based on semantic violation patterns rather than syntactic coverage, effectively handling cases where execution traces are identical.
Counterfactual Verification: A causal reasoning step that distinguishes root-cause violations from downstream symptoms, significantly improving localization precision.
SemFault-250 Benchmark: A curated dataset of 250 Python programs with single semantic faults, derived from real-world repositories (e.g., Redis, Apache Fineract) and existing benchmarks, specifically designed to challenge syntactic FL techniques.
Full Implementation: A working system integrating Tree-sitter, LLM agents, and pytest for end-to-end fault localization.

4. Experimental Results

Evaluated on SemFault-250 against five baselines (SBFL-Ochiai, SBFL-Tarantula, Delta Debugging, AutoFL, and ablation variants):

Localization Accuracy:
- Top-1 Accuracy: SEMLOC achieves 42.8% (using Claude Sonnet 4.6), significantly outperforming SBFL-Ochiai (6.4%) and Delta Debugging (0.0%).
- Top-3 Accuracy: SEMLOC reaches 68.0%, compared to 13.2% for SBFL-Ochiai.
Inspection Effort:
- SEMLOC flags only 7.6% of executable lines as suspicious, a 5.7× reduction compared to SBFL (which flags ~43.6%).
Component Impact:
- Semantic Indexing: Removing the structured grounding (direct LLM line prediction) drops Top-3 accuracy from 68.0% to ~44.0%, proving the value of executable constraints.
- Counterfactual Verification: Removing this step drops Top-1 accuracy from 42.8% to 30.8%, demonstrating its critical role in filtering noise and identifying root causes.
Real-World Applicability:
- Tested on the BUGSINPY dataset (specifically youtube-dl), SEMLOC achieved 57.1% Top-1 and 100% Top-5 accuracy, validating its portability to real-world repositories when combined with a function-level navigator (AutoFL).

5. Significance

Paradigm Shift: SEMLOC moves fault localization from syntactic execution signals (coverage) to semantic violation signals. This addresses the fundamental limitation of current tools in detecting bugs where control flow remains unchanged.
Reliability of LLMs: By forcing LLMs into a structured, executable format and validating their output via runtime counterfactuals, SEMLOC mitigates the stochasticity and hallucination risks inherent in free-form LLM debugging.
Actionable Diagnosis: Unlike methods that only output a ranked list of lines, SEMLOC provides structured explanations (the specific violated constraint) and causal validation, offering developers a clear path to the root cause.
Scalability: The framework demonstrates that semantic reasoning can be operationalized efficiently, narrowing the search space from nearly half the codebase to less than 8% with high precision.

In conclusion, SEMLOC establishes a new standard for fault localization by treating semantic intent as a first-class, executable signal, effectively bridging the gap between high-level LLM reasoning and low-level program debugging.