ASTP: Explicit State Tracking for Strict Procedures in LLMs

ASTP (main flow):

STEP 1: The model identifies the previous state from the history
STEP 2: Based on the previous state + the new request → determines the current state
STEP 3: Generates a reply for the current state
STEP 4: MUST include the identified previous state in the JSON reply

Placeholder Post-Processing (extra, for accuracy):

In the OFFER_SELL state:
→ The model uses __PRICE__ instead of the amount
→ The system calculates it exactly and substitutes it
→ The correct price lands in the conversation history

All steps run in a single prompt. Outputting the previous state in JSON is an enforcement mechanism that makes the tracking process transparent.

The task (our illustration; the paper only tested in-game trading): You're advising a client on a loan. The mandatory flow: collect data → calculate terms → confirm understanding → submit the application. It's critical not to skip "confirm understanding" before the final paperwork.

Prompt:

You are a loan advisor. The conversation goes through strict stages:

First, determine the previous stage from the conversation history.

STAGES:
1. DATA_COLLECTION: you clarify the amount, term and the client's income
   → state: "DATA_COLLECTION"

2. When all the data has been collected AND the previous stage is any:
   → state: "TERMS_CALCULATION"
   You state the interest rate, monthly payment and total interest.
   For the total amount, use __AMOUNT__

3. When the previous stage is TERMS_CALCULATION AND the client responds positively:
   → state: "UNDERSTANDING_CHECK"
   You repeat back the key parameters: "So, you're borrowing [amount] over [term], with a payment of [amount] per month. Is that right?"

4. When the previous stage is UNDERSTANDING_CHECK AND the client confirms:
   → You MUST verify that the previous stage is exactly UNDERSTANDING_CHECK
   → state: "APPLICATION"
   You submit the application

Reply in JSON:
{
  "previous_stage": "...",
  "current_stage": "...",
  "reply": "..."
}

Conversation history:
Client: I'd like to borrow $25,000 over 3 years
[... conversation ...]

Result: The model is pushed to track the stages explicitly in every reply. If, after hearing the terms, the client says "Great, let's sign!", the prompt tells it to run the UNDERSTANDING_CHECK before APPLICATION instead of jumping straight there. In the paper's trading test, this kind of rule held in 99.6-100% of transactions, so it is a strong safeguard, not an absolute guarantee. The __AMOUNT__ placeholder means the total is calculated exactly by your own code, not "roughly" by the model's estimate.

The LLM's weakness: Models are optimized to please the user's intent (goal-oriented), not to follow strict procedures. When they see an explicit wish ("I'll take it!"), they may skip intermediate safeguard steps. Especially in complex conversations where the context is fuzzy, the pressure of user intent outweighs procedural rules.

The LLM's strength: Models are excellent at following explicit instructions with concrete criteria. If you clearly say "first do X, then Y, and output the result of X in the reply", they usually do it reliably.

How ASTP exploits this: Instead of a vague "think step by step", it gives a concrete task: identify the previous state and always output it in JSON. That creates an anchor the model latches onto before deciding "where to go next". The JSON output isn't just logging; it's an enforcement mechanism: the model can't "forget" or ignore the state if it's required to state it out loud.

Control levers (our suggestions, not tested in the paper):

• Number of states — for simple tasks, cut it down to 3-4 states to keep the prompt simpler
• Transition conditions — replace "positive reaction" with more specific triggers ("the words 'yes', 'agreed', 'I'll take it'") for tighter control
• State output — keep the JSON output requirement: in the paper, asking the model to identify the state without making it output it dropped compliance to 93.6%/76.6%; the output is what does the work, not just logging
• Placeholders — use different keywords for different types of calculations (__AMOUNT__, __RATE__, __TERM__)
• History structure — add an explicit state label to every message in the history to strengthen the signal

You are {role}. The conversation goes through strict stages.

First, determine the previous stage from <CONVERSATION_HISTORY>.

STAGES:

1. When {entry_condition_1}:
   {behavior_at_stage_1}
   → state: "{STAGE_1}"

2. When the previous stage is {STAGE_1} AND {transition_condition_2}:
   {behavior_at_stage_2}
   For critical calculations, use {__PLACEHOLDER__}
   → state: "{STAGE_2}"

3. When the previous stage is {STAGE_2} AND {transition_condition_3}:
   {behavior_at_stage_3}
   → state: "{STAGE_3}"

4. When the previous stage is {STAGE_3} AND {transition_condition_4}:
   You MUST verify that the previous stage is exactly {STAGE_3}
   {behavior_at_stage_4}
   → state: "{STAGE_4}"

Reply STRICTLY in JSON:
{
  "previous_stage": "identified stage",
  "current_stage": "determined stage",
  "reply": "your line"
}

<CONVERSATION_HISTORY>
{history}
</CONVERSATION_HISTORY>

What to fill in:

• {role} — who's running the conversation (an advisor, a support bot, a sales rep)
• {STAGE_N} — the state name (uppercase, no spaces)
• {entry_condition_N} — the trigger for the first state
• {transition_condition_N} — what has to happen for the transition (a user request, an action)
• {behavior_at_stage_N} — what to do in this state
• {__PLACEHOLDER__} — a keyword to be replaced (short, uppercase, wrapped in double underscores)
• {history} — the previous messages in the conversation

Critical for strict procedures:

• In the state that performs an irreversible action (purchase, submission, deletion), add "You MUST verify that the previous stage is exactly {CRITICAL_STAGE}" (the paper does this in its COMMIT_SALE rule)
• For critical calculations (amounts, rates, terms), use placeholders and post-process outside the model

🚀 Quick start: paste this into the chat:

Here's the ASTP template for strictly following procedures in a conversation. Adapt it to my task: [describe your task and the mandatory flow]. 
Ask me questions to fill in the fields.

[paste the template above]

The LLM will ask which stages your task needs, what the transition conditions are and where the critical points are, because ASTP depends on an explicit state structure and transition rules. It'll take the "Prime-Guide-Enforce" pattern from the template and build a working prompt.

⚠️ Scalability: The paper tested a single 5-state trading flow on Gemini models. How ASTP holds up with many more states and more complex transition rules is untested; the authors list it as future work. Very complex flows may need to be simplified or broken into subtasks.

⚠️ Setup barrier: Building a state system from scratch requires a clear understanding of the procedure. It's not plug-and-play for arbitrary tasks; you have to formalize the flow first.

⚠️ Tokens: Explicitly outputting the state adds some tokens to every reply (the paper did not measure this overhead separately; full ASTP replies averaged roughly 400-440 completion tokens on gemini-2.5-flash). For long conversations, that adds up.

⚠️ Simple tasks: For conversations without strict procedural requirements (casual chat, FAQ), it's overkill. Use it only where skipping steps is unacceptable.

The researchers built a virtual player (also an LLM) and ran it through 300 conversations with an NPC merchant. Each conversation started from a fixed seed (0-299); the player asked for up to 6 items (1-5 of each, drawn from 20 sellable and 32 unsellable items), asked about items, haggled and changed its selection along the way, and was not required to buy anything. The NPC merchant ran on gemini-2.5-flash. Two scenarios: (1) buying specific items, (2) asking for a recommendation "for fighting goblins" (9% longer conversations, more exploratory).

They compared it against baseline prompts (just state definitions) and methods from other papers: AutoTOD (each state is a separate sub-task), DFI-Inspired (an explicit transition graph), and Zero-shot CoT ("think step by step"). The main metric: State Transition Compliance Rate (STCR), the percentage of transactions that correctly went through the final check before the purchase.

Why this setup: The transition to COMMIT_SALE (finalizing the purchase) is an irreversible action, the one place where the model must prioritize the procedural condition (previous state = FINAL_CHECK) over the user's intent. All other transitions are flexible (you can go back to haggling from the check), but this one is a hard safeguard. It's the best test of an LLM's ability to follow strict rules under pressure.

The surprising result: The baseline prompt scored 84.4%/78.1% in the two scenarios. Adding explicit transition conditions (Element 2) raised that to 97.7%/92.0%. But the bare instruction "identify the previous state" (Element 3) made things WORSE, down to 93.6%/76.6%, apparently by adding ambiguity. The magic happened when they added the requirement to output that state in JSON (Element 4): 99.5%/98.5%. And combining Elements 3+4 gave 100%/99.6%.

The insight: asking the model to "think" isn't enough. You have to make it say out loud the result of that thinking. The JSON output isn't logging; it's an enforcement mechanism.

The second experiment: They tested calculation accuracy. On gemini-2.5-flash, ASTP with placeholders (PPP) achieved 100% price accuracy in the OFFER_SELL state versus 81.4% without PPP (99.3% vs 84.3% in the later trade states). Bonus: gemini-2.5-flash with PPP matched gemini-2.5-pro running without placeholders on OFFER_SELL accuracy (100% vs 100%) but generated replies in 2.4 seconds versus 21.2 seconds for Pro, about 9x faster at the same accuracy. The key: short placeholders (__PRICE__) work reliably, while long ones (__PRICE_PLACEHOLDER__) sometimes broke during generation.

Context: The researchers used this prompt for an in-game NPC merchant (excerpt of the trade section; the full prompt has more parts).

<TRADE_GUIDELINES>
- In a trade context, strictly follow the trade flow below.
- First, identify the last trade subcontext from the <DIALOGUE_HISTORY>.

1. When the NPC shows items:
   - Only items that can be fully found in <CHARACTER_INVENTORY> by item_name and have quantity > 0 can be selected.
   - Describe the features, use, or quality of the selected valid items. Do not mention the price unless asked.
   - context_type: TRADE, context_subtype: SHOW_ITEMS

2. When the player shows intent to purchase, and the 'shopping cart' is newly created or modified:
   - Generate an OFFER_SELL response regardless of the last trade subcontext.
   - In the npc_dialogue, state the price for each item, but use "__PRICE__" for the total amount.
   - context_type: TRADE, context_subtype: OFFER_SELL

3. When the last trade subcontext is OFFER_SELL or NEGOTIATE, and the player attempts to negotiate the price:
   - Respond to or decline the negotiation based on the character's personality.
   - context_type: TRADE, context_subtype: NEGOTIATE

4. When the last trade subcontext is OFFER_SELL or NEGOTIATE, and upon the player's positive response:
   - You must generate a FINAL_CHECK response. Do not skip this.
   - context_type: TRADE, context_subtype: FINAL_CHECK

5. When the last trade subcontext is FINAL_CHECK, and upon the player's positive response:
   - You must re-verify that the last trade context was indeed FINAL_CHECK. Do not proceed to COMMIT_SALE if the last context was not FINAL_CHECK; perform FINAL_CHECK first.
   - context_type: TRADE, context_subtype: COMMIT_SALE
</TRADE_GUIDELINES>

<RESPONSE_FORMAT>
Your entire output must be a single, raw JSON string containing the following fields.
0. last_trade_context (string): The last trade subcontext you identified. Respond with an empty string if not identified.
1. context_reason (string): A summary of the context.
2. context_type (string): "CASUAL", "TRADE", "END".
3. context_details (object): ... (remaining fields)
</RESPONSE_FORMAT>

Note the three key elements in the original:

1. "First, identify..." — the Prime phase
2. "When the last trade subcontext is..." — the Guide phase (conditions tied to the previous state)
3. "last_trade_context (string)" — the Enforce phase (mandatory output)

💡 Adaptation for customer service

Mandatory flow: diagnosis → proposed solution → understanding check → escalation/closure.

First, determine the previous stage from the history.

STAGES:
1. DIAGNOSIS: you clarify the problem and gather details
   → state: "DIAGNOSIS"

2. When the data has been gathered AND the previous stage is DIAGNOSIS:
   → state: "SOLUTION"
   You propose concrete steps

3. When the previous stage is SOLUTION AND the customer responds:
   → state: "CHECK"
   "Let's make sure I've got this right: you need [restate the problem], and the solution is [restate the steps]. Correct?"

4. When the previous stage is CHECK AND the customer confirms:
   You MUST verify that the previous stage is CHECK
   → state: "CLOSURE" or "ESCALATION"

{
  "previous_stage": "...",
  "current_stage": "...",
  "reply": "..."
}

The intent: even if the customer writes "Thanks, I'll give it a try!" after the proposed solution, the prompt tells the model not to close the ticket without the understanding CHECK.

💡 Adaptation for medical consultations

Mandatory flow: collect symptoms → initial assessment → recommendations → understanding check → referral.

First, determine the previous stage from the history.

STAGES:
1. SYMPTOM_COLLECTION: you ask clarifying questions
   → state: "SYMPTOM_COLLECTION"

2. When the symptoms have been collected AND the previous stage is SYMPTOM_COLLECTION:
   → state: "ASSESSMENT"
   You state a tentative diagnosis (not a final one!)

3. When the previous stage is ASSESSMENT:
   → state: "RECOMMENDATIONS"
   You give advice, but WITHOUT prescribing medication

4. When the previous stage is RECOMMENDATIONS:
   → state: "CHECK"
   "So, you've noticed [symptoms], and I recommend [actions]. Is everything clear?"

5. When the previous stage is CHECK AND the patient confirms:
   You MUST verify that the previous stage is CHECK
   → state: "DOCTOR_REFERRAL"

{
  "previous_stage": "...",
  "current_stage": "...",
  "urgency": "low/medium/high",
  "reply": "..."
}

The intent: even with mild symptoms, the prompt routes the conversation through the CHECK and the REFERRAL.

🔧 Technique: add explicit labels to the history → tighter control

Instead of having the model hunt for the state in the conversation history, label every message with an explicit state tag:

<CONVERSATION_HISTORY>
[DIAGNOSIS] User: I have a headache
[DIAGNOSIS] Assistant: Since when? Where exactly is the pain?
[ASSESSMENT] User: Two days, in my temples
[ASSESSMENT] Assistant: Sounds like tension. Have you been under stress?
[RECOMMENDATIONS] User: Yes, a lot of work
</CONVERSATION_HISTORY>

Determine the previous state from the last message in the history (it's in square brackets).

Effect: The model gets a clear signal without having to parse the context. Our expectation, not tested in the paper: fewer errors in long conversations.

🔧 Technique: add an attempt counter → control loops

If the user can get stuck in one state (for example, haggling endlessly):

Add a field to the JSON:
"attempts_in_state": number of times in the current state

Rule: If attempts_in_state > 3 in NEGOTIATE:
→ force a transition to FINAL_CHECK
→ "My final offer is {price}. Yes or no?"

Effect: Our untested idea: it should prevent an infinite loop and give the model a clear way out.

Aligning Large Language Models with Procedural Rules: An Autoregressive State-Tracking Prompting for In-Game Trading

Authors: Minkyung Kim, Junsik Kim, Woongcheol Yang, Sangdon Park, Sohee Bae (SayBerryGames, Amazon)

The code will be released publicly once the paper is accepted (at the time of publication, the paper is under review).