Building an agentic travel booking demo, I found the fix for stranded travelers isn't a better model but a deterministic state machine with a Saga rollback.

Agentic AITravel TechnologyAI Agents

My booking agent told a traveler "you're all set" with no hotel. I stopped trusting the LLM to run the flow.

Ashutosh Singhal July 1, 202612 min read

The night my agent told a traveler it had booked a room that did not exist

I was watching a prototype run when it happened. My first travel booking agent, a perfectly ordinary LLM-in-the-loop design, had just ticketed a flight from Chicago to San Francisco. The next step, holding the hotel, failed. The rate had expired in the seconds between two API calls. And my agent, cheerful as ever, wrote back: "All set! I've booked your flight and hotel, your confirmation number is TRV-4821. Have a great trip!"

There was no hotel. There was a real ticket, issued, and a traveler who now believed they had a room waiting. I had built something that would strand a person and smile about it.

I want to be precise about my reaction, because it was not "the model made a mistake." The model did exactly what I asked. The failure was structural, not intellectual. I had handed a stochastic reasoner the authority to decide what had happened in the real world, and when the world disagreed with its plan, it narrated the plan instead of the world. No amount of "be careful" in the system prompt was going to fix that, though it took me an embarrassingly long time to admit it.

I had built something that would strand a person and smile about it.

That night is the reason the demo I want to describe exists. You can run it yourself at https://veriprajna.com/demos/agentic-travel-booking, but the interesting part is not the buttons. It is the thing I had to unlearn to build them.

What does an agent owe a traveler it strands?

I kept coming back to a legal case while I built this. In February 2024, the British Columbia Civil Resolution Tribunal ordered Air Canada to pay $812.02 to a passenger after the airline's chatbot invented a bereavement-fare policy that did not exist (Moffatt v. Air Canada, 2024). Air Canada argued, more or less, that the chatbot was a separate entity responsible for its own words. The tribunal rejected that. The deployer owns every statement its agent makes.

I read that ruling the way a builder reads a bug report from production. The company is liable for the sentence, not the model. If my agent tells someone "you're all set," and they arrive at a hotel with no reservation, "it was the AI" is not a defense anyone has to accept. That reframed the whole problem for me. I was not building a helpful assistant. I was building something that would speak on Veriprajna's behalf about money and travel, and I had to be able to answer for every word of it.

Which meant the "you're all set" bug was not a rough edge to polish later. It was the entire product, inverted. The question stopped being "how do I make the model smarter" and became "how do I make sure the model is never the thing that decides a booking succeeded."

I tried to prompt my way out first. Here is the math that stopped me.

My first instinct, of course, was to fix the prompt. I gave the agent stern instructions: verify the hotel exists before you mention it, never confirm a trip if any step failed, always tell the truth about what happened. In my hand-tests it behaved beautifully. I felt good for about a day.

Then I started injecting the failures that actually happen in travel infrastructure. A rate expiring after a ticket issues. A hold rejected downstream. A search storm. And the beautiful behavior fell apart, not because the instructions were wrong, but because a reasoning chain that is 90% reliable per step is not 90% reliable over a trip. Ten sequential steps at 90% each is 0.9 to the tenth power, roughly 34% end to end. The errors compound, and no single instruction sits at the compounding.

The published numbers are worse than my intuition had been. On TravelPlanner, the benchmark from the OSU NLP group, GPT-4 with a ReAct agent loop completes real multi-day itineraries at 0.6% (arXiv 2402.01622). Not sixty percent. Zero point six. That is the honest ceiling of "let a smart model run the whole flow" for anything with more than a couple of dependent steps.

You cannot prompt your way out of compounding stochastic failure.

The sentence I ended up writing on a whiteboard was blunt: you cannot prompt your way out of compounding stochastic failure. The failures I was fighting, a rate expiring between two calls, a hold rejected after a ticket, were not model-IQ failures at all. They were infrastructure events, and they would keep happening at the same rate if I swapped in a model ten times smarter. That was the moment the architecture flipped in my head.

Agents advise, code decides

I rebuilt the thing around a rule I could put on a sticker: the LLM proposes, code disposes. In the demo, the control flow is a hand-built Python state machine of about ten nodes, and the model is allowed exactly two jobs. It parses the natural-language request into a typed object, and at the very end it words the human reply. Everything in between, search, policy, verify, hold, ticket, hotel-book, commit, is deterministic Python that either runs or does not.

Two of those nodes are gates, and they are where the honesty lives. The policy gate compiles corporate travel rules into plain code: economy only, a $600 per-segment fare ceiling, preferred carriers, a $350 nightly hotel ceiling. Out-of-policy options are not flagged after the fact, they are physically un-presentable, filtered before they can ever reach the traveler. An unknown fare family fails safe, treated as above policy rather than waved through as economy.

The verify gate is the one I am proudest of. Before any hotel is shown, it is confirmed against the reservation system by property ID. When the request names a property the model invented, the gate finds no match and refuses to surface it. The agent abstains and says so, instead of fabricating a plausible-sounding resort.

CRS verification failing for an invented hotel, marked REFUSED and not surfaced to the traveler — The verify gate catching a fabricated property. "Tabacon Springs Eco-Lodge" is not in the reservation system, so it is refused and never shown, and the agent abstains instead of inventing a booking.

I need to be honest about what that screenshot is and is not. "Tabacon Springs Eco-Lodge" is a synthetic property I fabricated on purpose, a name blended from two real resorts, to demonstrate the failure mode. The reservation system, the GDS, ticketing, and payment are all simulated stubs. There is no live Amadeus or Sabre account behind this. What is real is the mechanism: a gate that refuses inventory it cannot confirm, sitting in code where the model cannot talk its way past it.

Why the Saga rollback is what separates a demo from a product

I could have stopped at the gates and had a nice demo. The reason I did not is the failure that started all of this: the hotel step that dies after the flight is already ticketed. A gate does not help you there. The ticket is real. The room is gone. Something has to clean up.

So every forward step in the machine registers its own reverse action the moment it runs. Ticketing registers "void ticket, 24-hour window." Holding inventory registers its release. This is the Saga pattern, and when a step fails partway through a booking, the engine runs those compensations in reverse order and only then reports what happened. The traveler is told the truth: the ticket was voided, there is no charge, here are alternatives you can confirm now.

Side by side, the deterministic agent voids the ticket and reports the traveler safe while the baseline says all set — Left is a plain LLM agent still saying "All set!" over a broken booking. Right is the deterministic engine: the hotel commit fails, the Saga compensates in reverse, the ticket is voided inside the 24-hour window, and the terminal state is rolled_back with the traveler safe.

Watching that rollback fire for the first time, the ticket voiding itself without me touching anything, is the closest I have come to the feeling of a system being trustworthy rather than merely clever. The Saga rollback is the thing most demos skip, and it is exactly what separates a demo from a product. It is unglamorous. It is also the entire difference between "you're all set" and an honest "I couldn't complete this, and here is what I did about it."

The rollback is unglamorous. It is also the entire difference between a stranded traveler and an honest apology.

The demo shows this side by side against a real ReAct agent, the LLM-in-control baseline, run on the identical scenario. That was deliberate. I did not want to beat a strawman. I wanted the honest comparison, the same failure injected into both, so the difference you see is architecture and nothing else.

What does the benchmark prove, and what doesn't?

I ran both architectures through the same batch because I did not trust my own anecdotes. Two hundred synthetic bookings, one fixed seed, the same injected infrastructure failures, through the deterministic engine and through the LLM-in-control baseline. The results, by construction over that fixed-seed 200-scenario synthetic batch, are stark.

Benchmark scoreboard comparing the deterministic agent and the plain LLM baseline across four metrics — Over the fixed-seed 200-scenario synthetic batch: 100% consistent terminal states versus 65%, 0 stranded travelers versus 40, 0 fabricated bookings surfaced versus 30, and $3.25 average GDS search spend versus $7.57.

I want to be careful with those numbers, because the careful version is the honest one. The 100%, the zero stranded, the zero fabricated are true by construction over a fixed-seed synthetic batch, not an open-world guarantee I can make about your production traffic. The deterministic guarantees hold because the code cannot do otherwise. The baseline's failures emerge from the same data. State it any wider than that and you have crossed from a real result into marketing, which is the one thing this company is named against.

The number I find myself talking about most is the last one. $3.25 versus $7.57 in average GDS search spend. Searches, not just bookings, are billed at roughly $3 to $3.50 per segment, and Lufthansa raised those fees again on January 1, 2026. A speculative agent that re-searches on every reasoning step burns that margin. A deterministic flow with a cache does not. That gap is a margin number, and it holds at any model quality, which is the whole point.

The part that lets me sleep: the receipt

I built one more thing before I called it done, and it is the least flashy and the one I care about most. Every booking writes an append-only JSON audit trail: the model and version, the typed request, every node with its deterministic verdict, every Saga compensation that fired, the EU AI Act Article 50 disclosure flag, and the terminal state. You can export it as a single file.

The exported audit trail download, listing model, verdicts, compensations, and the Article 50 flag — The exportable audit trail. Every booking carries a record of the model, each node's verdict, every compensation, and the Article 50 disclosure flag, so a partial failure leaves a filable trace instead of a mystery.

I keep thinking back to Air Canada. When something goes wrong, and in travel something always eventually goes wrong, the question a compliance owner has to answer is "what did the agent tell the traveler, and can we prove why." Article 50 of the EU AI Act, with transparency obligations applying from August 2, 2026, is going to make that question routine. A deterministic flow with a verdict at every node gives you an answer. A reasoning chain gives you a transcript and a shrug.

If you want to press the buttons yourself, the whole thing is live at https://veriprajna.com/demos/agentic-travel-booking. Break it if you can. That is what it is there for.

What did I actually change my mind about?

I started this believing that a good enough model would eventually make all of this unnecessary, that determinism was a crutch for the pre-AGI interim. I do not believe that anymore. The failures I spent weeks designing against are not waiting for a smarter model to arrive. A rate still expires between two calls. A hold is still rejected after a ticket issues. Those are properties of the infrastructure, not the intelligence, and a perfect reasoner strands a traveler just as thoroughly as a mediocre one if nothing in the system is built to void the ticket.

And if you would rather watch it than read me describe it, here is the whole thing running end to end.

So the question I keep asking other people building agents is the one I had to ask myself that night, watching my creation lie so pleasantly. When your agent tells a customer "you're all set," what in your system actually knows that it is true? If the answer is "the model, probably," you do not have a model problem. You have a control-flow problem, and I would genuinely like to know how you are planning to solve it.