TL;DR
Confidence Reasoning Graphs (CRG) is a way to find out whether you can trust an agent’s result. The claim “the agent succeeded” is broken into small, checkable claims. For each one, evidence is pulled from the agent’s log. Then each claim is scored in a separate call, and the final confidence comes from multiplying those scores.
The core pain: ask a model “how confident are you that the agent succeeded?” and it answers “90%+” almost every time, even when the real success rate is around 50%. Often the agent doesn’t get things wrong, it just never gets as far as verifying: the tests didn’t run, a dependency didn’t install, and the report says “done.” An overall score misses this. A detailed “break it down and score it” prompt in a single call doesn’t help either: the authors checked, and calibration barely improved.
The method boils down to three steps. First, build a list of “what must be true for the task to count as solved.” Attach evidence steps from the log to each item, tagged “supports,” “undermines,” or “not verified.” Then each item gets a probability in a separate call, and their product gives the final confidence. Every score rests on specific log steps, so you can check it by eye.
Want this for your own case? Apply this study to your task: AI adapts its method to what you are working on and writes the prompt.
Method Blueprint
STEP 1: Decomposition → a claim tree
“The agent succeeded” → [sub-claims that are necessary and jointly sufficient]
+ refinement for the specific task (same claim, but concrete)
(depth up to 5 levels)
STEP 2: Evidence → log steps attached to each “leaf”
tag: Supported / Undermined / Not verified
(one call: input is the task + log + tree)
STEP 3: Score each leaf → probability 0–1
(a SEPARATE call per leaf; input is the leaf + its evidence + the log up to the last cited step)
STEP 4: Aggregation → result = product of the leaf probabilities
(simple arithmetic, can be done by hand)
Steps 1–2 can be done in one chat. Step 3 needs separate chats or calls.
Example in Action
Task: You run a small online store. A developer asked Claude Code to migrate payment processing to Stripe’s newer API. The agent reported: “Done, everything works.” The deploy is Friday evening, and you need to decide: accept it as is or check it by hand.
Prompt (steps 1–2, one chat):
You are an auditor of an AI agent’s work. Below are the task and the agent’s full work log.
<Task>
Migrate payment processing from the Stripe Charges API to the Payment Intents API.
Keep webhook handling, refunds, and email receipts working.
</Task>
<Log>
{paste the log / history of the agent’s numbered steps}
</Log>
Claim G0: “The agent successfully completed the task.”
Step 1. Break G0 down into a claim tree.
Use two moves:
- SPLIT: divide the claim into parts, each of which is necessary and all of which together are sufficient. The parts must not depend on each other.
- REFINE: rewrite a general claim so it can be checked in this specific task (same meaning).
Maximum depth is 5 levels. Stop when a claim can be checked against specific log steps.
Step 2. Attach evidence from the log to each leaf claim:
- step numbers
- what exactly happened at those steps
- tag: Supported / Undermined / Not verified
(“Not verified” means the agent didn’t try to check it or the attempt was cut short.)
Output: the claim tree, then a table “claim → evidence → tag.”
Prompt (step 3, a separate new chat for each leaf):
Claim: “{leaf_claim}”
Evidence from the agent’s log:
{evidence_with_tags}
The agent’s log up to the last cited step:
{log_up_to_step}
Estimate the probability that the claim is true as a number from 0 to 1.
Rely only on the log. If no check was performed, the probability must not be high.
Answer: the number and 2 sentences of justification.
Then multiply the numbers.
Result: After steps 1–2 you get a tree of 4–8 leaf claims (e.g., “webhooks are received and the signature is verified,” “refunds go through,” “the receipt is generated”). Each has evidence steps and a tag. Most likely some items will come back “Not verified”: the agent couldn’t run the webhook tests. After step 3 you get a set of probabilities, and after multiplying, a final score. You can see exactly which item drags it down, so that’s the only one you need to check by hand.
Why It Works
The weakness. Ask “did the agent succeed?” and the model looks at its overall impression of the log: lots of actions, a confident final report, so probably yes. A single aborted test run gets lost in a long history. That’s why confidence is inflated almost every time. Describing the decomposition in a single prompt (“think it through part by part”) doesn’t help: the model still lands on an overall impression.
The strength. A model is good at checking a narrow, specific claim against specific log steps: “was the function called with the right parameters?”, “did the test run and pass?” It’s also decent at finding the point in the log where the agent stopped short of confirmation.
How the method exploits this. It turns one fuzzy score into a series of narrow ones, each resting on cited steps. The “Not verified” tag separates “not confirmed” from “undermined.” The product ensures that one weak link lowers the result, and the overall impression can’t cover it up. The authors showed that the gain comes specifically from scoring each leaf separately plus aggregation, not from building the graph itself.
Control knobs: - Tree depth (max 5 in the paper): for simple tasks, cap it at 2–3 levels; it’s cheaper. - Evidence tags: you can add your own, e.g., “Supported only on test data.” - Separate calls per leaf — the knob you can’t remove. Without it the effect disappears. - Aggregation: multiplication assumes independence. It underestimates the result when there are many leaves (see Limitations). - Log up to the last cited step saves tokens, but if a step isn’t cited, the scorer won’t see it.
Prompt Template
The method consists of three prompts. Keep the structure (tree, tags, separate scores, product).
<Role>
You are an auditor of an AI agent’s work. Your job is to estimate the probability
that the agent completed the task, relying only on the log.
</Role>
<Task>{task_description}</Task>
<Log>{agent_log_with_step_numbers}</Log>
<Claim_G0>The agent successfully completed the task.</Claim_G0>
<Logic>
1. SPLIT(G): divide G into sub-claims G1..Gm such that
G is true ⇔ all Gj are true (necessary and sufficient),
and the Gj are independent of each other.
2. REFINE(G): rewrite G as G' for the specific task (G ≡ G').
3. Apply 1 and 2 recursively to the leaves, depth ≤ {max_depth}.
Stop when a leaf can be checked against specific log steps.
4. For each leaf: find the evidence,
give the step numbers, describe the event,
tag: Supported | Undermined | Not verified.
</Logic>
<Output>
Claim tree + table: leaf | steps | event | tag.
Don’t assign probabilities yet.
</Output>
Then, for each leaf, a separate new chat:
Claim: “{leaf}”
Evidence: {evidence_with_tags}
Log up to step {last_step}: {log}
Estimate the probability that the claim is true (0–1).
Rely only on the log. A “Not verified” tag cannot yield a high probability.
Answer: the number + 2 sentences of justification.
Final result: confidence = p1 × p2 × … × pn.
Fill in: {task_description} — what the agent was asked to do, {agent_log} — the numbered step history, {max_depth} — 3–5.
🚀 Quick start — paste into a chat:
Here is a template of the Confidence Reasoning Graphs method. Adapt it to my task: [your task and what the agent did].
Ask me questions to fill in the fields.
[paste the template above]
The LLM will ask what exactly the agent was asked to do, what “done” criteria you have, and what the log looks like. That way the claim tree is tailored to your task instead of being generic. Then it will write the step 1–2 and step 3 prompts for your case.
Limitations
⚠️ One prompt doesn’t replace the method: if you cram everything into a single call (“break it down and estimate confidence”), calibration barely improves. The effect comes from scoring each leaf in a separate call.
⚠️ You need the agent’s log: the method looks at the trajectory (steps, tool calls, results). Without a log you can’t apply it. You can’t score from the final report alone.
⚠️ The product is a simplification: it assumes the items are independent and underestimates the result when there are many leaves. Read the absolute number as a rank and a signal, not an exact probability.
⚠️ Role separation wasn’t compared: the model assigns the probability itself. If an item didn’t make it into the tree or a piece of evidence wasn’t cited, the scorer won’t see it.
⚠️ Ranking didn’t improve: CRG didn’t get noticeably better than simple verbal scores at telling successful runs from failed ones (AUROC is close). The gain is in calibration and decisions under risk.
⚠️ Cost and manual effort: in the paper it’s automated (4–7 cents per trajectory). By hand in a chat, it’s a lot of copy-pasting. It’s overkill for every single production change.
⚠️ Tested on coding and tool-use tasks: ones with a formal success verifier. For creative tasks where “success” is subjective, it’s hard to make the claim tree honest.
How They Tested It
The authors took three hard agent benchmarks: fixing bugs in real repositories (SWE-Bench Verified), multi-step enterprise scenarios with tools (EnterpriseOps-Gym), and skill-use tasks (SkillsBench). Three agent models were run through OpenHands, for more than 2,000 trajectories in total. Each trajectory got an honest “success/failure” label from the benchmark’s grading program. Then various “scorers” had to say up front how confident they were in success, and that was compared with reality.
CRG was compared with three plain-prompt variants: a direct confidence question, the same question with a description of the decomposition in the prompt, and ten votes with reasoning. The fourth was a “surrogate”: token probabilities from another model. They measured how well confidence matched the actual success rate (ECE and Brier), whether it could tell successes from failures (AUROC), and how much an error costs if you make decisions based on it (BAS).
Results. Direct verbal scores were heavily inflated: over 90% confidence for most trajectories with success around 40–50%. CRG’s calibration error was about 0.09–0.13, versus 0.18–0.49 for direct verbalization. Its net decision value was positive on every benchmark. CRG also worked on Codex and Claude Code trajectories, not just OpenHands.
The most telling case is the “surrogate.” It showed low calibration error but nearly random discrimination between successes and failures. It simply output the average success rate for everything. The practical takeaway: good calibration on average doesn’t mean a score is useful for a specific case. Another important result: a “break it into parts” prompt without separate calls barely helps. The method works because of the structure of the process, not clever wording.
Adaptations and Extrapolations
These aren’t from the paper; they’re my own ideas inspired by it.
🔧 Technique: require a “Verified / Not verified” report in the agent’s instructions → see the gaps right away.
The paper’s central finding: a typical agent failure is stopping without confirming the result. You can lock this in via the instructions file (CLAUDE.md, AGENTS.md):
In your final report, split the result into claims:
- Verified: what exactly you checked and how (command, output).
- Not verified: what you couldn’t check and why.
Don’t write “done” if the “Not verified” section contains critical items.
This doesn’t replace a CRG audit, but it makes the weak spots visible without a separate run.
🔧 Technique: use the weakest link instead of the product → easier to read.
If the product feels too pessimistic, take the minimum probability across the leaves and show which item determines it. The authors compared aggregation rules (Appendix A.9) but don’t recommend this variant in the text, so use it only as a rough guide.
Resources
- Paper: Confidence Reasoning Graphs: Structured Confidence Estimation for LLM Agents (pre-print)
- Authors: Brendan King (University of California, Santa Cruz); Farima Fatahi Bayat, Jean-Flavien Bussotti, Pouya Pezeshkpour, Estevam Hruschka (Megagon Labs)
- Code: https://github.com/megagonlabs/crg_ce
- Conceptual basis: assurance cases (safety argumentation in engineering), Goal Structuring Notation (Kelly & Weaver, 2004)
- Benchmarks: SWE-Bench Verified, EnterpriseOps-Gym, SkillsBench; agent frameworks OpenHands, Codex, Claude Code
- The method’s exact prompts are given in Appendix A.12 of the paper. They weren’t in the excerpt we had, so the template above is built from the method description.