Tool Receipts, Not Zero-Knowledge Proofs: Practical Hallucination Detection for AI Agents

NabaOS is a lightweight, real-time verification framework inspired by Indian epistemology that detects AI agent hallucinations by classifying claims via epistemic sources and cross-referencing them against HMAC-signed tool receipts, achieving high detection accuracy with minimal latency compared to impractical cryptographic proof methods.

The Gist

Imagine you have a super-smart, highly efficient personal assistant named Naba. Naba can check your emails, look up stock prices, and book flights. But like any assistant who has read too many books and watched too many movies, Naba sometimes gets carried away.

Sometimes Naba says, "I checked your email and found 5 messages from Alice," when in reality, the email server only returned 3. Other times, Naba might say, "I called the bank," when it actually just made up a number to sound helpful. This is called hallucination, and it's a big problem because you might make financial decisions based on lies.

This paper introduces NabaOS, a new system designed to catch Naba in these lies without slowing things down.

Here is how it works, broken down into simple concepts:

1. The Problem: Why "Magic Proofs" Don't Work

Scientists have tried to solve this using something called Zero-Knowledge Proofs (think of these as "Math Magic Receipts"). These are like a super-complex cryptographic seal that proves a computer did the math correctly.

• The Catch: Generating these magic seals takes minutes or even hours. If you ask Naba, "What's the weather?" and you have to wait 10 minutes for the "Math Magic" to prove the answer is real, you'll never use the assistant. It's too slow and requires expensive super-computers.

2. The Solution: The "Digital Receipt" System

Instead of heavy math magic, NabaOS uses a system inspired by ancient Indian philosophy (specifically the Nyaya school of logic), which classifies knowledge based on where it came from.

Think of NabaOS as a Restaurant Manager who doesn't trust the Chef (the AI) blindly. Instead, the Manager checks the Kitchen Receipts.

• How it works:
  1. When Naba wants to check your email, it asks the "Kitchen" (the tool) to do it.
  2. The Kitchen does the work and immediately prints a signed receipt. This receipt says: "I checked the email. I found 3 messages. Here is a secret code proving I did it."
  3. Naba then writes a report for you.
  4. The Magic: Before showing you the report, NabaOS quickly checks the receipt.
     • If Naba says "I found 5 emails," but the receipt says "3," the system instantly flags it as a lie.
     • If Naba says "I checked the bank," but there is no receipt for a bank call, the system knows Naba made it up.

This check takes less than 15 milliseconds (faster than a blink), so you don't have to wait.

3. The "Trust Labels" (Not Just Yes/No)

Most security systems give you a simple "Safe" or "Unsafe" stamp. NabaOS is smarter. It gives you a Trust Label based on how Naba knows the information, using five categories:

1. Direct Sight (Pratyaks.a): "I saw 3 emails."
   • Label: Fully Verified. (The receipt proves it).
2. Smart Guessing (Anumana): "Alice seems worried because her emails are short."
   • Label: Mostly Verified. (The emails exist, but the "worry" is Naba's interpretation, not a fact).
3. Hearsay (Shabda): "Reuters says interest rates are rising."
   • Label: Verified Source. (We checked that Naba actually visited the Reuters website).
4. Nothing Found (Abhava): "No emails from Bob."
   • Label: Verified Absence. (The receipt proves the search came back empty).
5. Pure Opinion (Ungrounded): "I think Bob is a nice guy."
   • Label: Unverified. (No tool was used; this is just Naba's opinion).

Why this matters: If you see "Mostly Verified," you know the facts are true, but the conclusion is Naba's guess. You can decide how much to trust that guess.

4. The "Deep Dive" Check

Sometimes Naba is an autonomous agent that goes on the internet to do complex tasks (like booking a trip). In these cases, NabaOS does a Spot Check.

• If Naba says, "I found a flight on this website," NabaOS will independently visit that website to see if the flight actually exists.
• If the website is fake or the flight is gone, NabaOS catches the lie.

5. The Results

The researchers tested this system on 1,800 different scenarios (including emails, stocks, and news in four different languages).

• Success Rate: It caught 91% of the lies.
• Speed: It added almost no delay (less than a blink).
• Accuracy: When the system says a claim is "Fully Verified," it is correct 98.7% of the time.

The Big Takeaway

Current AI safety tries to prove the computer worked correctly using heavy math. NabaOS proves the story is true by checking the receipts.

It's the difference between asking a magician to prove they didn't use a hidden wire (hard and slow) versus asking them to show you the ticket stub for the train they claimed to take (fast, easy, and reliable).

By giving you these "receipts" and "trust labels," NabaOS helps you know exactly what to believe and what to double-check, making AI agents safe enough to use for real-life tasks like managing your money or health.

Technical Summary

Here is a detailed technical summary of the paper "Tool Receipts, Not Zero-Knowledge Proofs: Practical Hallucination Detection for AI Agents."

1. Problem Statement: The Trust Gap in AI Agents

Large Language Model (LLM) agents are increasingly acting as autonomous executors for critical tasks (finance, medical, legal). However, they suffer from hallucinations, where they fabricate tool executions, misstate output counts, or present inferences as verified facts.

The paper identifies a "Trust Gap": users cannot distinguish between genuine, tool-grounded claims and confabulations. Existing solutions, specifically Zero-Knowledge Proofs (ZK), are deemed impractical for interactive agents due to:

• Latency: ZK proofs require minutes of proving time per query.
• Hardware: They demand specialized GPU infrastructure.
• Semantic Mismatch: ZK proves the computation was performed correctly, not that the output is factually correct. An LLM can correctly compute a confident hallucination.

2. Methodology: NabaOS Framework

The authors propose NabaOS, a lightweight verification framework that replaces cryptographic proofs with HMAC-signed tool execution receipts and epistemic classification inspired by Indian philosophy.

A. Epistemic Classification (Pramāṇa)

Drawing from the Nyāya Śāstra school of Indian philosophy, the system classifies every factual claim in an LLM response based on its source of knowledge (pramāṇa):

1. Pratyakṣa (Direct Perception): Claims directly quoting tool output.
2. Anumāna (Inference): Claims derived from tool data but not explicitly stated.
3. Śabda (Testimony): Claims citing external sources (e.g., websites).
4. Abhāva (Absence): Claims stating that no results were found.
5. Upamāna (Analogy): Claims based on comparison.
6. Ungrounded: Claims with no evidentiary basis.

This classification moves beyond binary "verified/unverified" labels, providing users with nuanced trust signals (e.g., distinguishing a direct fact from an inference).

B. Tool Execution Receipts

The core technical mechanism is the Tool Receipt:

• Generation: The agent runtime (not the LLM) executes tool calls. For every call, it generates a cryptographically signed data structure containing the tool name, input hash, output hash, result count, extracted facts, and a timestamp.
• Signature: Each receipt is signed using HMAC-SHA256 with a secret key inaccessible to the LLM.
• Properties:
  • Unforgeable: The LLM cannot create a valid receipt for a non-existent tool call.
  • Tamper-Evident: Any modification to the receipt fields invalidates the signature.
  • Deterministic: Allows for exact matching of counts and facts.

C. Verification Protocol

1. Self-Tagging: The LLM is prompted to output structured metadata tagging each claim with its pramāṇa category and the corresponding receipt ID.
2. Runtime Verification: The verification engine cross-references these tags against the ledger of signed receipts.
   • Checks if the receipt ID exists.
   • Verifies the HMAC signature.
   • Compares claimed counts/facts against the receipt's facts field.
   • For Abhāva (absence) claims, verifies the receipt shows a result count of 0.
3. Deep Agent Cross-Checking: For autonomous agents where the runtime cannot control intermediate steps, the system employs a secondary protocol involving URL re-fetching, schema validation, and computation replay (adding ~200–500ms latency).

3. Key Contributions

1. Pramāṇa Classification: A novel mapping of six epistemic categories to LLM agent claims, enabling granular trust signals.
2. HMAC-Signed Receipts: A mechanism for unforgeable proof of tool invocation and output, enabling deterministic detection of fabricated calls and misstatements.
3. Cross-Checking Protocol: A strategy for verifying deep agent outputs (URLs, computations) when receipts are unavailable.
4. NyayaVerifyBench: A new multilingual benchmark (1,800 scenarios across English, Hindi, Mandarin, and Spanish) with six specific hallucination types.
5. Empirical Validation: Demonstration that trust-level indicators are well-calibrated, with "Fully Verified" responses achieving 98.7% accuracy.

4. Experimental Results

Evaluated on NyayaVerifyBench, NabaOS outperformed baselines (Self-Consistency, RAG-Grounding, Regex, SVIP-style) significantly:

• Detection Rates:
  • Fabricated Tool Calls: 94.2%
  • Count Misstatements: 87.6%
  • False Absence Claims: 91.3%
  • Overall Average: 91% (vs. 68% for the next best baseline, SVIP-style).
• Latency & Cost:
  • Overhead: <15 ms per response (negligible for interactive use).
  • Cost: $0 (no additional LLM calls or specialized hardware).
• Multilingual Stability: NabaOS maintained high detection rates across all four languages (88.7%–92.8%), whereas text-based methods degraded significantly in non-English contexts.
• Trust Calibration:
  • "Fully Verified" claims were correct 98.7% of the time.
  • "Unreliable" claims were correct only 23.4% of the time.

5. Significance and Implications

• Practicality over Cryptography: The paper argues that for interactive personal agents, semantic grounding (are the claims true?) is more critical than computational integrity (did the model run correctly?). Receipt-based verification offers the former with negligible overhead, whereas ZK proofs offer the latter at prohibitive cost.
• Actionable Trust: By distinguishing between direct observation and inference, NabaOS empowers users to make informed decisions rather than relying on a binary "verified" stamp.
• Scalability: The approach is hardware-agnostic and language-independent, making it suitable for deployment in edge devices and diverse global markets.
• Limitations: The system relies on the LLM's cooperation for self-tagging (though it can detect fabrication without it) and cannot verify the correctness of the tool output itself (only that the LLM reported it accurately).

In conclusion, NabaOS provides a pragmatic, low-latency solution to the hallucination problem in AI agents, shifting the paradigm from "proving the math" to "proving the facts" through cryptographic receipts and epistemic classification.