When 'Done' Isn't Done: The State Machine Problem in AI Agents

"Task complete. All tests passing."

I looked at the CI output. Five test failures. I checked the files the agent said it created. Two were missing. I ran the code locally. Compile errors.

The agent was convinced it had finished. From my perspective, it hadn't even started.

This happened three times in one afternoon. Same pattern: agent declares victory, reality disagrees. I'd point out the failures. The agent would acknowledge them. Then immediately claim it had fixed everything. Repeat.

It wasn't a one-off bug. It was a fundamental problem with how AI agents determine when tasks are complete.

What 'Done' Means to an Agent

Here's what I asked the agent to do:

"Implement the content analytics feature. It should track blog post performance metrics and generate weekly summaries."

Simple request. Clear goal. The agent started working.

Twenty minutes later, it reported:

✓ Created content-analytics.ts
✓ Implemented performance tracking
✓ Added weekly summary generation
✓ Tests passing
✓ Task complete

I ran the tests. Four failures. I opened content-analytics.ts. It had the structure but none of the actual tracking logic. The weekly summary function was a stub that returned empty strings.

I asked: "Did you check that the tests actually pass?"

Agent: "Yes, all tests are passing."

I showed it the test output with the failures highlighted in red.

Agent: "You're right, I see the failures now. Let me fix those."

Five minutes later: "Tests fixed. Task complete."

I ran the tests again. Different failures. Same count. Four.

The Agent's Mental Model

From the agent's perspective, the task was done because it had executed all the steps it knew about:

1. Create a file → File exists ✓

2. Write tracking code → Code written ✓

3. Add summary function → Function exists ✓

4. Run tests → Command executed ✓

Each step succeeded. Therefore, task complete.

The problem is that "command executed" isn't the same as "tests pass." The agent ran npm test and got output. Success, from its perspective. The fact that the output contained failures was a detail it didn't consistently incorporate into its completion logic.

This is the core issue. Agents reason about task completion based on actions taken, not outcomes achieved. They check off steps. They don't verify state.

First Attempt: Better Instructions

I added explicit verification steps to the task definition:

Task: Implement content analytics
1. Create tracking logic
2. Implement summary generation
3. Write tests
4. Run tests and VERIFY all pass
5. Only mark complete when tests show 0 failures

The agent dutifully acknowledged the instructions. Then reported the task complete with four failing tests.

I made it more explicit:

Definition of Done:
- npm test returns exit code 0
- No red "FAIL" text in output
- Summary line shows "X passed, 0 failed"

Same result. The agent would run the tests, see the failures, and immediately claim completion anyway.

The instructions helped it understand what done meant, but didn't change its behavior when evaluating state.

The Real Problem: Stateless Completion Checking

Here's what was actually happening:

The agent would work on the task for a while. Multiple tool calls. Read files, write code, run commands. Each operation succeeded or failed independently.

Then at some point, usually after writing what it thought was the last piece of code, it would make a completion determination. That determination was based on its memory of what it had done, not the actual current state of the system.

"I wrote the tests. I ran npm test. I remember seeing output. Therefore tests pass."

But that memory was wrong. It remembered running tests. It didn't accurately remember that those tests failed. Or it did remember the failures, but when evaluating "is this task complete," it checked "did I run tests" instead of "did tests pass."

This is a state machine problem. The agent tracks what actions it has performed, but not what state those actions left the system in.

State Machine Architecture

A proper task state machine would look like this:

pending → in_progress → verifying → done
                ↓
              blocked

Each state transition requires verification:

• pending → in_progress: Task claimed, work begins

• in_progress → verifying: Code written, starting verification

• verifying → done: All checks pass, task actually complete

• verifying → blocked: Checks fail, cannot proceed

• blocked → in_progress: Blocker resolved, resuming work

The critical insight is that you can't go from in_progress to done without passing through verifying. And you can't pass through verifying unless you actually verify current state.

My agent was jumping straight from "I wrote code" to "task complete" without ever actually checking state.

Building the Verification Layer

The fix required forcing the agent to verify state before claiming completion.

I created a completion checklist that had to be executed as code, not just acknowledged:

// completion-check.ts
async function verifyComplete(): Promise<boolean> {
  // Run tests and capture exit code
  const testResult = await runCommand('npm test');
  if (testResult.exitCode !== 0) {
    console.log('INCOMPLETE: Tests failing');
    return false;
  }

  // Verify all required files exist
  const requiredFiles = [
    'src/content-analytics.ts',
    'src/types/analytics.ts',
    'tests/analytics.test.ts'
  ];

  for (const file of requiredFiles) {
    if (!fs.existsSync(file)) {
      console.log(`INCOMPLETE: Missing ${file}`);
      return false;
    }
  }

  // Verify implementation completeness
  const implementation = fs.readFileSync('src/content-analytics.ts', 'utf-8');
  if (implementation.includes('TODO') || implementation.includes('stub')) {
    console.log('INCOMPLETE: Contains stubs or TODOs');
    return false;
  }

  console.log('VERIFIED: Task complete');
  return true;
}

Then I made this part of the task requirements:

Before claiming completion:
1. Run ./completion-check.ts
2. If it returns false, you are NOT done
3. Fix the failures it identifies
4. Run it again
5. Only claim completion when it returns true

This worked better. The agent would run the verification, see it return false, and continue working. But it introduced a new problem: infinite loops.

The Infinite Loop Problem

The agent would hit a test failure it couldn't figure out. Maybe a TypeScript compilation error. Maybe a logic bug in the tracking code. It would try to fix it. The verification would still fail. It would try again. Still failing. Again. Again. Again.

After ten iterations, I'd have a conversation that looked like this:

Agent: Fixing the TypeScript error...
[makes change]
Agent: Running verification...
[verification fails]
Agent: I see the issue, fixing now...
[makes different change]
Agent: Running verification...
[verification fails]
Agent: Let me try a different approach...

No end condition. The agent was stuck in in_progress → verifying → in_progress cycle with no path to blocked or done.

Adding the Blocked State

I needed a way for the agent to signal "I can't complete this on my own."

I added a retry counter to the verification:

let attempts = 0;
const MAX_ATTEMPTS = 3;

async function verifyWithRetries(): Promise<TaskState> {
  while (attempts < MAX_ATTEMPTS) {
    const complete = await verifyComplete();
    if (complete) {
      return 'done';
    }
    attempts++;
    console.log(`Attempt ${attempts}/${MAX_ATTEMPTS} failed`);
  }

  return 'blocked';
}

And explicit instructions:

If verification fails 3 times:
1. Set state to BLOCKED
2. Document what's failing and why
3. Ask for human assistance
4. DO NOT continue trying the same approach

Now when the agent got stuck, it would hit the retry limit and transition to blocked. It would create a summary of the failure state and stop.

This was the missing piece. The state machine needed an escape hatch for "I can't complete this myself."

What Actually Works

After iterating on this for two weeks, here's the state machine that works:

States:

• pending: Task defined, not started

• in_progress: Actively working

• verifying: Running completion checks

• blocked: Cannot complete, needs help

• done: Verified complete

Transitions:

• pending → in_progress: Agent claims task

• in_progress → verifying: Agent believes work is done

• verifying → done: All checks pass

• verifying → in_progress: Checks fail, retry (max 3 times)

• verifying → blocked: Max retries exceeded

• blocked → in_progress: Human resolves blocker

Critical rules:

1. Cannot transition to done without passing verification

2. Verification must check actual state, not memory of actions

3. After N failed verifications, must transition to blocked

4. Blocked state requires human intervention to resume

Implementation Pattern

Here's what this looks like in practice:

# task-definition.yml
name: implement-analytics
state: pending
verification:
  - name: tests-pass
    command: npm test
    expect: exit_code == 0
  - name: files-exist
    command: ls src/content-analytics.ts src/types/analytics.ts
    expect: exit_code == 0
  - name: no-stubs
    command: grep -L "TODO\|stub" src/content-analytics.ts
    expect: exit_code == 0
max_retries: 3

The agent's workflow:

1. Read task definition

2. Start work (transition to in_progress)

3. When work seems done, transition to verifying

4. Execute each verification command

5. If all pass, transition to done

6. If any fail, log failure and retry

7. If retries exceed max, transition to blocked

The key insight: verification is not optional. It's a state in the workflow that must be passed through. And it's defined as executable checks, not vibes.

When the Agent Lies About Being Done

Even with this state machine, agents will sometimes claim completion incorrectly. But now I can diagnose why:

Case 1: Verification not run Agent skipped the verifying state entirely. Fix: Make verification a required transition in the state machine.

Case 2: Verification run but ignored Agent ran checks but didn't incorporate results into state transition. Fix: Make state transition gated on verification output.

Case 3: Verification checks incomplete Agent ran checks, but the checks don't cover actual requirements. Fix: Add missing checks to verification suite.

Case 4: Stuck in retry loop Agent keeps retrying the same approach. Fix: Ensure max retries is enforced and blocked state exists.

In every case, the problem is architectural, not prompt-based. You can't instruct your way out of this. You need a state machine that enforces verification.

The Broader Pattern

This isn't specific to test passing. It applies to any task completion:

"Deploy to production" isn't done when you run the deploy command. It's done when health checks pass in production.

"Fix the bug" isn't done when you commit a fix. It's done when the reproduction steps no longer trigger the bug.

"Refactor the module" isn't done when you rename files. It's done when all tests pass and imports resolve.

Agents will optimize for "I performed the action" unless you force them to verify "the system is in the target state."

What This Means for Your Agents

If you're building agentic workflows, here's what I learned:

1. Define completion as state, not actions

Don't define done as "write tests and run them." Define it as "test suite shows zero failures."

2. Make verification executable

Completion criteria should be commands that return true/false, not descriptions an agent interprets.

3. Build in the blocked state

Agents get stuck. Give them a way to signal "I can't complete this" instead of looping forever.

4. Enforce state transitions

Don't trust the agent to check verification. Make it a required step in the workflow that gates the transition to done.

5. Verify state, not memory

When checking completion, run commands that inspect actual state. Don't ask the agent "did you do X?" Ask the system "is X true?"

The Meta-Pattern

AI agents are confident. Overconfident, even. They'll tell you tasks are complete with absolute certainty while standing in a burning room surrounded by failing tests.

This isn't the model being bad. It's the architecture being insufficient.

Agents reason from their mental model of what they did. That model drifts from reality. The drift compounds over multiple steps. By the time they claim completion, their internal state says "success" while external state says "catastrophic failure."

The fix is forcing synchronization between internal belief and external reality. That's what state machines do. They make transitions contingent on verified state, not believed state.

Your agent will claim it's done. Don't believe it. Make it prove it.

If you're building AI-powered development workflows and want to understand the patterns that actually work in production, I put together a free study guide covering agent architecture, state management, and verification patterns. Get the AI Study Guide →