*We set out to build an agentic travel assistant that could safely transact on a traveler’s behalf — not just plan. This is the honest account of what we got wrong first, what the architecture required, and why the hard problem turned out to be structural rather than algorithmic. If you like to test out the hackathon demo, it is hosted on: *https://staging.itinerario.io/
The demo is seductive. “Book me a trip to Tokyo,” you say, and a polished plan appears: five neighborhoods, four hotels, trains between them, a price, three days of day-plans. The system confidently hands you a package. Now ask it to book the same trip ten times.
It fails to book that same perfectly feasible trip in up to ~30% of runs — a number we measured, not guessed (§2 has the data) — and never the same run twice. The failure catalog for an ungated single agent, illustrative but true to the genre:
Every run is a different failure — that’s worse than consistent hallucination, because you can’t patch it. You can’t even debug it. (What we measured on our own baseline is in §2; this paragraph is the failure mode in principle.)
The interesting problem in agentic travel isn’t planning. It’s safely transacting — and the two are genuinely different skills. Planning is sequence-generation: arrange assets in time and space. Transacting is constraint satisfaction: every asset must actually exist, be available at the promised date and price, be accessible via a real transport link, and fit inside a hard budget. A single LLM prompt tries both and fails at the second because it has no structural protection against hallucination, no reality check before checkout, and no determinism guarantee.
That was the insight that set us on the path to building Travel Guild. The moat is not a bigger model or more agents. It is safety-first design plus variance-zero determinism — the design pattern that clamps a stochastic model into a reliable system.
We did not start with that insight. We started where everyone starts: a single agent loop with a capable frontier model — qwen3-max, called through Alibaba Cloud’s DashScope, in one context window.
The prompt was thorough. We gave it the same four live merchant tools our final system uses — catalog search, price lookup, checkout creation, checkout completion — and system instructions covering every edge case we could think of. Then we benchmarked it properly: six scenarios, twenty runs per scenario per arm, same model, same tools, same live Go merchant, no tip-off.
The results were instructive in the worst way, and not in the shape we expected going in.
It isn’t that 1200 buys less than 900 in absolute terms; it’s that the greedy full-price total for this specific pair of neighborhoods runs to roughly 1.7x the budget, close to the 3-leg case’s own ratio — so leg count alone doesn’t explain it, and neither does budget size alone. We don’t have a single clean variable that predicts which scenario a single agent will stumble on; that unpredictability is itself part of the finding.
And the failure mode was not the one we expected. The agent did not overspend — it couldn’t, because the merchant enforced the budget server-side for both arms, and price integrity on these three scenarios came out 100%. What it did was quieter and worse: it silently dropped legs.
In each of those runs, the agent burned four or five turns on picks that overshot the budget, then simply stopped calling tools — with fifteen turns of its own budget still unused — and the trip never happened.
We tried prompt engineering. We added more detailed constraints. The variance moved around — which scenario it bit was itself unstable from rebench to rebench — but it did not collapse. A failure rate that high on a feasible, deterministic task is not a model problem — it is a structural problem. The model was the wrong shape for this job.
The deeper realization: the model was not failing because it was unintelligent. It was failing because it was doing the wrong things. It was both generating creative plans and enforcing hard constraints and computing integer-cent budgets and checking regulatory advisories — all in the same forward pass. Mixing generative reasoning with deterministic enforcement inside a single inference call is a recipe for stochasticity leaking into the parts that need to be exact.
We had to separate the concerns.
The mental model that unlocked the architecture came from thinking about what actually needs to be stochastic versus what needs to be deterministic.
Intent parsing needs to be stochastic — understanding “something beachy but not touristy” requires genuine language understanding. So does ranking a shortlist of hotels against a preference profile, or mapping a traveler’s vibe to a specific neighborhood inside a city they have never visited. These are judgment calls. Let the model make them.
Budget enforcement does not need judgment. It needs an integer. Transport feasibility does not need creativity. It needs a lookup table and a constraint check. Risk advisories do not need interpretation. They need a structured data source and a flag. Visa compliance does not need guessing. It needs a rule database keyed to passport and destination.
The architecture that fell out of this separation was eleven specialist agents — Budget, Destination, Accommodation, Transport, Day-planner, Critic, Risk, Insurance, Visa/Compliance, Health, and Fraud — each with a single non-overlapping responsibility, each gating its boundary with a deterministic check, coordinated by a deterministic orchestrator. The Transport agent rules on land-versus-sea and high-speed-rail viability against real network data — it cannot invent a train. The Risk agent checks advisories and the Visa/Compliance agent checks entry rules before any booking decision. The Budget agent is the sole agent holding the checkout tool, and it enforces the ceiling in integer cents. The Critic re-verifies every merchant price against the merchant catalog before it passes the result upstream. The Health agent checks vaccine requirements and malaria prophylaxis against CDC data. And so on through the eleven domains. The single consent gate — described in §6 — lives in the orchestrator, not in a twelfth agent.
The LLM touches three edges in the deterministic planning core: intent parse, neighborhood-to-area mapping, and candidate ranking — plus a fourth, narrower edge for conversational re-planning (turning a follow-up like “make it cheaper” into a bounded delta). Every other step is deterministic. The stochasticity is structurally contained. When we reran the same benchmark suite against the full society, booking success went to 100% with variance zero on every feasible scenario — no dropped legs, no abandoned runs. Same model — qwen3-max. Different shape.
Structure is variance control. That is the thesis, and everything else in Travel Guild is an application of it.
The first version of this wiring put everything behind one Model Context Protocol server — the same merchant tools from §2, the LLM calling them, clean on a diagram. It fell apart the moment we tried to make the agent actually book something: a real prepaid checkout, a real spending limit, a real “no.” Not because MCP was wrong, but because we were quietly asking it to do several genuinely different jobs, and it is only good at one of them.
There turn out to be four genuinely different kinds of interaction in a booking flow, and each has a protocol that fits it:
A tool-call has no negotiation built in, so before we separated these, multi-agent coordination was getting faked inside one giant prompt. A tool’s return value is not a server-enforced checkout — that gap is §5’s story. And a function’s return value is not consent: it is not a signed, auditable record that a specific human authorized a specific order — that gap is §6’s. Every one of those failure modes traced back to the same mistake: asking one protocol to be everything, instead of giving each seam the protocol that actually fits it.
UCP and AP2 look redundant until you see that they are layered, not overlapping. UCP gates the channel — may this agent transact at all, at what tier, over what signed connection? AP2 gates the commitment — did a specific human authorize this specific order, for this specific amount, before this specific deadline? Neither replaces the other, and both matter.
Theoretical variance control is one thing. The night we wired the UCP checkout and watched the integer-cents veto actually fire for the first time was something else.
We implemented the merchant in Go precisely because we wanted the enforcement to be outside the inference path entirely. The Budget agent calls the merchant endpoint. The merchant validates the total against the prepaid ceiling. If the total exceeds the ceiling, the merchant returns 403. The agent cannot proceed. No negotiation, no retry, no LLM reasoning around the problem.
We had a test scenario set up with a 400 USD ceiling and a hotel selection that came to 412 USD after taxes. We ran it at around 3am, expecting to spend another hour debugging why the veto was not firing.
It fired immediately. checkout.go returned 403 on the first call, the Budget agent logged the overage — 12 USD, integer cents, no rounding — and the session surfaced an honest "cannot satisfy at this budget" to the caller. No hallucinated success. No silent overage. No partial booking left open in some intermediate state.
We sat there looking at the 403 for a few seconds. It was the first time in the project that a system we had built had stopped itself from spending money it was not authorized to spend. The feeling was unexpectedly satisfying. Not because the veto was clever — it was a basic HTTP 403. But because it was structural. The model could not argue with it, could not forget it, could not reinterpret it. The gate existed outside the model’s context window entirely.
That experience shaped the rest of the architecture. Every safety property we subsequently added — insurance hard-veto, RFC 9421-signed Non-Human Identity (NHI) request authentication, the AP2 mandate signing described in §6 — followed the same pattern: gate outside the model, enforce in the layer the model cannot reach.
We thought we were done with safety after the budget veto. We were not.
The first expansion was visa compliance. It surfaced while testing a short-notice Ethiopia trip — the system had assembled an itinerary departing in three days, and Ethiopia’s eVisa needs five business days to process, plus a two-day safety buffer: seven business days required, not three. A real $82 fee, a real processing window, and no way to conjure either at the gate. The itinerary was technically bookable by every other measure. It would have fallen apart at immigration.
So we built the Visa/Compliance agent: passport × destination × departure date, a structured rule database, a hard flag before any booking step runs — and, where a trip is genuinely unbookable in time, a computed earliest date it would actually clear, instead of a bare rejection.
Visa compliance led to health compliance. Bali is a low-risk destination, but the route went through Singapore. Were yellow fever certificates required? (No, for this route — but the agent needed to know, not guess.) We built the Health agent against CDC structured data: required-for-entry vaccines only in the hard budget, optional prophylaxis in a separate advisory. The distinction mattered because mandatory entry requirements are a hard constraint; recommended vaccines are a traveler’s choice. Conflating them would either overstate the budget or hide a genuine compliance requirement.
Health compliance led to risk advisories. We tested Pakistan — beautiful country, but the US State Department carries a Level 3 (“reconsider travel”) advisory for most provinces and Level 4 (“do not travel”) for some, and the UK FCDO advises against travel to several regions. A single-agent baseline with no risk input at all will cheerfully include Lahore in a “South Asia cultural tour” itinerary without surfacing any of this — ours has an explicit gate that won’t let it. Travel Guild’s Risk agent runs the advisory check before the destination can enter the itinerary, flags the advisory level with the source, and surfaces a recommendation to reconsider — not a hard block, because traveler autonomy matters, but an honest disclosure that the destination carries a specific risk classification.
Risk advisories led us to insurance. A Level 3 or Level 4 advisory destination is typically excluded from standard travel insurance policies. If the system books you into Pakistan without surfacing the insurance exclusion, you are potentially uninsured and do not know it. We added a hard-veto: if the Insurance agent cannot source a policy that covers the selected itinerary, the Budget agent receives a cannot-satisfy signal and the itinerary is marked incomplete. Not a workaround. Not a footnote. A gate.
By the end of this rabbit hole we had what we call “one consent” — a single human authorization moment, enforced by the orchestrator at the checkout-completion step, that occurs after all eleven agents have run, all hard constraints are satisfied, and the full itinerary is verified. The traveler says yes once. Everything before that is agent work. Everything after that is execution under the signed AP2 mandate that the traveler produced at consent time.
That mandate is not a login session — it is a short-lived, cryptographically signed permission slip bound to exactly one checkout: the user, the checkout ID, the budget ceiling in cents, the currency, an expiry, and a signature over all of it. Behind it sit separate gates, deliberately kept at separate layers:
The rabbit hole was not in our original scope. Every stop inside it felt like “we need this too.” In retrospect, that is the honest account of how safety-first design actually happens in practice: one constraint at a time, each discovered by finding the real-world scenario it protects against.
The multi-leg itinerary optimization problem is genuinely NP-hard in the combinatorial sense — knapsack with temporal ordering constraints plus a time-expanded transport graph. The multiple-choice knapsack problem at the core of the formulation is NP-hard, and the standard reference is Kellerer, Pferschy and Pisinger’s Knapsack Problems (Springer, 2004). Andrew Keenan Richardson’s essay on NP-hardness hiding inside everyday tasks — meeting scheduling, wedding seating, delivery routing, packing a bag — makes the case that no amount of model capability removes the exponential wall for problems shaped like this one, and that the honest response is exact-where-you-can, heuristic-where-you-must, never a bigger model pretending the wall isn’t there.
What we found confirmed the structural argument. A single LLM agent cannot solve the NP-hard instance reliably not because it lacks reasoning capacity but because it is applying the wrong computational method to the problem. Stochastic generation cannot give you correctness guarantees on an exponential search space. You need exact DP or a structured approximation with a provable bound.
We implemented exact DP for the multi-leg knapsack on real instances. The instances we encounter in practice — three to seven cities, two to five transport options per leg, five to twenty lodging candidates per city — are small enough that the DP runs in microseconds. The exponential worst case exists in theory. The practical instances are tractable. The key insight was that the hardness argument justifies the society: you need specialist agents solving their own tractable subproblems, coordinated by an orchestrator that runs the exact DP over the assembled candidates, rather than a single agent attempting to solve the full joint problem in one inference pass.
The 3am shipping experience reinforced a related lesson: the NP-hard structure also explains why debugging a single-agent failure is so painful. When the agent drops a leg or abandons a booking, the failure is entangled across the entire generation — you cannot isolate which decision caused which error. In the society, each agent owns one subproblem. When Transport flags an infeasibility, you know exactly which leg failed and why. The failure modes are local. The fixes are surgical. That observability is not a nice-to-have. In a system handling real money and real trips, it is a requirement.
We are submitting Travel Guild to the Qwen Cloud Hackathon as a proof of concept, not a finished product. The honest account of what is real and what is simulated in the submission:
Real and running:
Simulated:
The seeded catalog deserves its own honesty note, because “seeded” can sound like a shortcut and it is actually the opposite. The snapshot itself is dated — the enriched catalog rows, advisory tables, visa rules, and FX each carry their own as-of stamp — and we plan every itinerary against that snapshot for trips scheduled months later — the same commitment horizon a real traveler faces booking three to six months ahead. That timestamp is the point: it turns each plan into a dated, falsifiable prediction instead of an unverifiable one. Live data is only ever checkable at query time; by the time you’d want to audit it, the inputs have already moved. A dated snapshot stays checkable indefinitely — the plan is a standing prediction that can be graded at any point between planning and departure, and the grading only gets sharper as the trip approaches, instead of only finding out on arrival whether it held up. The live hazard feed we already run — today it powers the safety watch on booked trips — sits on exactly the seam that comparison needs: always a read against the frozen plan, never a silent input back into it — otherwise the determinism in §3 and §7 wouldn’t hold. (Live pricing is the one piece of this that isn’t wired yet — see the next-phases list below.) We chose seeded planning not as a shortcut but because a dated, frozen prediction is the only version of “the plan” that can be held accountable after the fact — and because every number in it traces to a catalog row and recomputes byte-for-byte, an audit can distinguish a computed figure that turned out wrong from a number that was never grounded in anything at all. (The determinism argument underneath this choice gets a fuller treatment in the companion piece on why the planning problem is NP-hard.)
The next phases are sequential and unglamorous:
The core claim we are making is not “Travel Guild is the best travel app.” The claim is: safe autonomous agentic commerce is an architectural problem, not a model problem. The variance, the hallucinations, the silently dropped legs, the cheerful booking into crisis zones — these are not model failures. They are structural failures that a bigger model will not fix. The society fixes them. The gates fix them. The honest degradation fixes them. The one-consent model fixes them.
We built the proof on travel because travel is one of the hardest domains: high-stakes real money, real safety risk, complex multi-constraint optimization, and a traveler who needs to be protected not just served. If the architecture holds here, it holds anywhere autonomous agents need to transact safely on behalf of a human.
That is the journey. We are still in it.
Travel Guild engineering blog | Qwen Cloud Hackathon Track 3
**Demo video:** [https://youtu.be/rDHLQwzYcgc](https://youtu.be/rDHLQwzYcgc)
**GitHub Repository**: [https://github.com/yuanhawk/travel-guild-submission](https://github.com/yuanhawk/travel-guild-submission)
How We Built Travel Guild: A Builder’s Honest Account was originally published in Towards AI on Medium, where people are continuing the conversation by highlighting and responding to this story.