EntroShop

EntroShop: tree-guided shopping copilot that narrows 50,000 products to the one you meant in 1.6 turns, the way binary search narrows a sorted array.

Comment

What inspired us. The track hands you a 50,000-product catalog and a customer who knows what they want but cannot name it. Keyword search never converges, and a chatbot that just chats never finishes. The problem is a clean information game: each turn the customer leaks a bit of the hidden target, and the agent picks the question. You win by asking the questions that cut the candidate pool fastest, then stopping at the right moment.

What we tried first, and abandoned. Our first build was LLM-heavy: an LLM reranker over retrieval, entropy-guided clarification, and an RLHF-style reward loop around the ask policy. It worked, and it taught us what did not matter. The evaluator is a deterministic simulator whose constraints arrive verbatim from the target product's metadata, so the reward is exact and readable. There is no preference model to learn, so RLHF added nothing to the score. The LLM rerank reordered lists but changed no session outcome on the public set (TechnicalScore +0.000036). The entropy part survived. The LLM and RLHF parts did not.

What we built instead. A tree-guided retriever. Every product's category path becomes one chain in an n-ary property tree: parents contain their children, deeper levels are progressively finer properties, and each product owns exactly one chain. Two products that share a chain are information-equivalent at the category level. Clarification became a walk down this tree in the spirit of binary search: each question should cut the remaining pool by the largest factor, and a match deeper in the tree is more discriminative, so deeper matches carry more weight in scoring. The deterministic ranking gets the tree first; the LLM fires only when the tree alone has not converged.

Let \(P_t\) be the candidate pool at turn \(t\). The ideal question maximizes the expected cut:

$$a^* = \arg\max_a \mathbb{E}v!\left[\frac{|P_t \setminus P{a=v}|}{|P_t|}\right]$$

The tree makes this cheap: a disclosed category chain pins a subtree, so one exact chain match can cut tens of thousands of products at once. In binary-search terms, a question worth asking roughly halves the pool. On the official public set, exact-phrase conjunction pins a single product for 66.5% of sessions and ten or fewer for 79%. The official score,

$$\text{TechnicalScore}= 0.50 \cdot \text{Hit@10}+ 0.30 \cdot \text{MRR}+ 0.20 \cdot \text{Efficiency},$$

lands at 0.9055 against the weak BM25 baseline's 0.107, with Hit@10 = 1.000 (200/200), MRR = 0.724, and MTTC = 1.59 turns.

We also replay the agent against a 300-session synthetic stress set with 40% deliberately generic products; every miss there falls in the family-ambiguous corner, the same information bound the competition's disclosure policy cannot resolve.

Challenges we hit. The family-ambiguous corner: some targets share all four disclosed constraints with hundreds of near-identical listings, so no question can separate them. Exact coarse-category identity collapsed the historically ambiguous pool from 459 candidates to 9 and moved Hit@10 from 0.995 to 1.000. The second challenge was resisting the LLM: measured reranking costs about 245k tokens per 200-session run and changes nothing on the public set, so we kept it as a gate for pools the tree cannot converge, not as the default. The third was not overfitting the public 200: the deployed policy is the argmax of an offline search over the simulator, and its winning mechanisms follow from the disclosure rules rather than from the 200 sessions.

What we learned. Readable reward beats scale. When the objective is exact, a deterministic tree walk plus a few exact-match insights outperforms a pipeline of LLM reranking and RLHF by construction: zero tokens, 0.4 s per session, and a score that cannot drift because the core is a pure function of the catalog.

Built With

Share this project:

Updates

Submission history