EntropyShop — Information-Theoretic Conversational Shopping

The problem

Most shopping searches begin with an incomplete description rather than a product name. A customer may start with “I want boots,” then gradually reveal a material, fit, use case, or detail that distinguishes one product from another.

This creates a conversational search problem rather than a simple keyword-search problem. With 50,000 catalog items and a maximum of ten turns, the system must retrieve good candidates, preserve the correct target while information is incomplete, and decide which question is worth asking next.

Inspiration

We were inspired by question-driven guessing games such as Akinator, where progress comes from asking questions that narrow a hidden space of possibilities.

We adapted that idea to shopping search. Instead of treating every customer message as another independent query, EntropyShop treats the customer’s intended product as a hidden target. Each turn is used either to apply new evidence or to ask for the missing preference that would most improve the next recommendation.

The key design question became:

What is the most useful thing we can learn from the customer next?

Why a deterministic system

We chose not to use an LLM in the submitted runtime. This was a deliberate engineering decision, not simply a lack of model access.

The task rewards faithful constraint handling and efficient catalog search more than open-ended text generation. An LLM could introduce latency, cost, run-to-run variability, and the possibility of misinterpreting or hallucinating product attributes. For a structured catalog and a strict local evaluator, we wanted every recommendation and question to be traceable to the catalog and the conversation state.

The result is a transparent, reproducible system with zero model tokens, no runtime API calls, no network dependency, and no hallucination channel.

This is a task-fit decision rather than an anti-LLM claim. LLMs may be useful for broader and less structured shopping experiences, but explicit algorithms were better suited to this fixed-catalog problem.

Our solution

EntropyShop is a conversational shopping copilot for Track 4. On every turn, it:

1. extracts product constraints and intent changes;
2. retrieves candidates through category and lexical routes;
3. ranks products using phrase evidence, catalog facets, conflict penalties, and deterministic priors;
4. estimates a posterior over the remaining candidates; and
5. asks an information-gain question when another clue is likely to improve the search.

The category and lexical routes are combined rather than chained as a hard filter. Category matching provides a strong product-type signal, while lexical matching preserves useful customer wording. This prevents a single incomplete interpretation from eliminating the correct product too early.

The conversation state also handles rejected products and changing intent. When a customer changes direction, the system can clear stale suppression and reopen exploration instead of remaining trapped by an earlier preference.

Question selection

Question selection is the central part of the system.

Raw entropy can favor attributes that divide the catalog efficiently, such as brand, even when the customer cannot answer them. EntropyShop therefore combines information gain with:

• answerability;
• expected ranking improvement;
• missing-value probability; and
• the cost of spending another turn.

The system is not trying to ask the most mathematically informative question in isolation. It is trying to ask the most useful question that a customer is likely to understand and answer.

How we built it

The runtime pipeline is:

Customer message
→ constraint and intent extraction
→ category and lexical retrieval
→ deterministic ranking
→ posterior estimation
→ information-gain question selection

The implementation uses Python 3.11 and the Python standard library. It builds immutable in-memory indexes over the organizer-provided frozen 50,000-product catalog.

The ranking pipeline uses IDF-weighted lexical matching, phrase containment, product facets, conflict penalties, and deterministic priors. The repository also includes the official evaluator integration, ablation scripts, robustness tests, split safeguards, and 57 automated tests.

We implemented intent-conditioned routing and a sparse semantic retrieval route as experimental variants. They remain available for analysis, but the final submission uses the deterministic baseline because it performed better on our held-out guard and is easier to reproduce.

Results

On the official 200-session public development benchmark:

Metric	Official baseline	EntropyShop
Hit Rate@10	0.125	1.000000
MRR	0.068034	0.932103
MTTC	9.81	2.190
Efficiency	0.119	0.881
TechnicalScore	0.10671	0.955831
Runtime model tokens	0	0

The improvement came from several measured changes rather than one large model:

• Lexical retrieval alone scored 0.08458.
• Adding category routing raised TechnicalScore to 0.40718.
• Adding facet scoring raised it to 0.82108.
• Phrase containment and the full ranker raised it to 0.86237.
• Adaptive questioning improved the fixed-order policy from 0.86491 to 0.87458.
• Exploration and staged recommendation budgets improved ranking quality while preserving top-ten target coverage.

The frozen policy achieved Hit Rate@10 of 1.000 on every 40-session fold. Across five deterministic folds, TechnicalScore ranged from 0.944321 to 0.966583, with a mean of 0.955831 and standard deviation of 0.008715.

A separate paraphrase stress test scored 0.92838.

The final release initializes the catalog in approximately 9.6 seconds and averages 39.27 ms per turn, with an 84.88 ms p95 latency on the recorded machine.

What we learned

Our main lesson was that conversational recommendation is an evidence-acquisition problem as much as a ranking problem. A stronger ranker cannot recover information that the customer has not supplied. In many cases, asking the right question is more valuable than generating another paragraph of explanation.

We also learned that the simplest signal was often the strongest one. Category information provided the largest single improvement, while generic profile signals sometimes acted as noisy tie-breakers and were removed.

The final configuration was selected based on measured held-out behavior rather than how advanced a component sounded. The public sessions influenced early development, so the public folds are guards for later changes and not substitutes for the organizer’s unseen private evaluation.

AI assistance disclosure

ChatGPT was used during development as an engineering assistant for brainstorming, code drafting and review, debugging, test design, evaluation analysis, and documentation editing.

The team made and reviewed the final design and implementation decisions. No LLM is called by the submitted runtime. EntropyShop is deterministic, offline, and reports zero model tokens.

Dataset and tools

The evaluation uses the organizer-provided frozen 50,000-product catalog and 200 public development sessions from the participant kit, derived from Amazon Reviews 2023.

Development tools include Python 3.11, Conda, Git, and pytest. The runtime uses the Python standard library only. No runtime APIs, external model assets, private sessions, or network services are used.

Limitations

The public development sessions are not the organizer’s private evaluation set, so the public score is not a guarantee of private-set performance.

The parser and facet vocabulary are hand-engineered for the supplied Clothing, Shoes & Jewelry catalog and may miss unseen synonyms, categories, or conversational phrasing.

The final system does not use a pretrained embedding model or an LLM. It operates on a frozen, read-only catalog and does not provide live inventory, checkout, transactions, or a production consumer interface.

What we would try next

Given more time, we would freeze the current policy and create a genuinely blind evaluation set with new targets, new paraphrases, reordered requirements, and different refusal and override language.

We would then test a confidence-gated hybrid policy: keep the deterministic lexical route as the default, but consult semantic and intent routes only when lexical evidence is weak or the conversation changes direction. We would also collect human feedback on whether questions are easy to answer and genuinely useful, then calibrate the question policy against those responses.

This would help determine whether the gains come from the underlying information-acquisition idea or from familiarity with the public simulator.

Built With

• conda
• git
• pytest
• python-3.11
• python-standard-library