Technische Samenvatting: Novelty-based Tree-of-Thought Search voor LLM-redenering en planning

Probleemstelling

Hoewel Large Language Models (LLM's) aanzienlijke capaciteiten hebben aangetoond in taakgebonden op taal gebaseerde taken, blijven ze breekbaar in complexe redenering en langetermijnplanning. Naïeve prompting faalt vaak, en gestructureerde benaderingen zoals Tree-of-Thought (ToT) lijden onder exponentiële runtime- en tokenkosten door ongesneden vertakkingszoekopdrachten. Omgekeerd bereiken klassieke planningsalgoritmen, specifiek breedtegebaseerde planners zoals Iterative Width (IW), efficiëntie door toestanden te snoeien op basis van een "novelty"-maatstaf, maar vereisen ze stijve, geformaliseerde probleemstructuren (bijv. PDDL) die zich niet goed vertalen naar natuurlijke taalcontexten. De kernuitdaging die door dit werk wordt aangepakt, is het definiëren van een analoge notie van novelty binnen het ongestructureerde taalgebied om efficiënte snoeiing in ToT mogelijk te maken zonder de flexibiliteit van LLM's in te leveren.

Methodologie

De auteurs stellen een planningsalgoritme voor dat novelty-based snoeiing integreert in het ToT-kader. De benadering decomposeert het planningsproces in vier subtaken:

1. Actiegeneratie: De LLM stelt mogelijke volgende acties voor vanuit een huidige staat.
2. Opvolgerstaatmapping: De LLM mapt acties naar resulterende toestanden.
3. Planverificatie: Het model bepaalt of een toestandsreeks voldoet aan het doel.
4. Novelty-schatting: De nieuwe bijdrage, waarbij de LLM optreedt als novelty-schatter.

Novelty-schatting en Snoeiing

In tegenstelling tot klassieke planners die novelty berekenen als een geheel getal op basis van booleaanse functiesubsets, past deze methode novelty aan voor natuurlijke taal. De LLM wordt bevraagd met een binair "ja/nee"-vraag om te bepalen of een nieuwe staat novelty vertoont in vergelijking met een lijst van eerder bezochte toestanden. Dit maakt gebruik van de vooraf getrainde algemene kennis en semantische begrip van het model om unieke toestanden te identificeren zonder expliciete atoomdefinities of few-shot voorbeelden te vereisen.

De zoekboom kan worden doorkruist met behulp van Breedte-First Search (BFS) of Diepte-First Search (DFS). Hoewel klassieke IW doorgaans BFS gebruikt, merken de auteurs op dat in LLM-contexten BFS kan leiden tot exponentiële kostenstijging; daarom worden de afwegingen tussen BFS en DFS geëvalueerd. De methode is ontworpen om domeinonafhankelijk te zijn, uitsluitend vertrouwend op een handgemaakte contextprompt die domeinregels uitlegt, en vermijdt domeinspecifieke prompt-engineering voor de novelty-schatter zelf.

Belangrijkste Bijdragen

1. Novelty-aanpassing voor LLM's: Het paper stelt een meetbaar concept van novelty voor taalgebieden voor, waarbij gebruik wordt gemaakt van de geïnternaliseerde semantische kennis van de LLM om zoektakken te snoeien op basis van staatsonderscheid in plaats van stijve functievergelijking.
2. Domeinonafhankelijk Kader: Een algemene implementatie is ontwikkeld die flexibele experimenten mogelijk maakt over verschillende domeinen (planning en redenering) met minimale handmatige inspanning, waarbij alleen een wijziging in de contextprompt voor de domeinregels vereist is.
3. Subtaakevaluatie: De auteurs introduceren een dedicated evaluatiekader, geïnspireerd door Plan-Bench, om de vier subtaken (actiegeneratie, statemapping, verificatie en novelty-schatting) onafhankelijk te testen tegen grondwaarheden gegenereerd door klassieke planners.
4. Empirische Analyse van Prompting: Het werk benadrukt de gevoeligheid van LLM-planning voor promptontwerp, met name door terugkerende faalpunten te identificeren (bijv. onderscheid maken tussen "pick-up" en "unstack" in Blocksworld) en aan te tonen hoe gerichte promptuitbreidingen de prestaties aanzienlijk kunnen verbeteren.

Experimentele Resultaten

De benadering werd geëvalueerd op de Blocksworld- en Logistics-planningsdomeinen, evenals op de MATH-benchmark (niveaus 5 moeilijkheidsgraad).

• Subtaakprestaties: Met het Qwen3 14B-model leverden de "Thinking Mode" (redeneertokens) en Natural Language prompting over het algemeen de beste resultaten. Het model slaagde erin novelty-snoeiing uit te voeren in standaardscenario's, maar had moeite met een moeilijkere variant die niet-duplicerende toestanden omvatte en strikte breedtegebaseerde redenering vereiste.
• Token-efficiëntie: In goed geconfigureerde instellingen (specifiek met "Thinking Mode" en "Direct" actiestatemapping) reduceerde de novelty-gesnoeide ToT de tokenkosten met maximaal 20 keer in vergelijking met standaard ToT, terwijl vergelijkbare successpercentages werden behouden. Bijvoorbeeld, in Blocksworld met DFS en Thinking Mode, bedroeg het gemiddelde aantal tokens voor de basis-ToT 330k, terwijl de novelty-gesnoeide versie gemiddeld 18k tokens gebruikte.
• Generaliseerbaarheid: De methode werd effectief overgebracht naar het Logistics-domein en de MATH-benchmark zonder opnieuw te tunen van de novelty-schatting prompts, hoewel optimale token-efficiëntie in verschillende redeneringsdomeinen (zoals MATH) schijnbaar domeinspecifieke prompt-tuning vereiste.
• Beperkingen: In slecht geconfigureerde instellingen degradeerden de prestaties aanzienlijk, met oplossingspercentages dicht bij nul en tokenkosten die met meer dan 100% stegen door de overhead van novelty-vragen. De methode is sterk afhankelijk van de basisprestaties van de onderliggende ToT-configuratie.

Betekenis en Claims

Het paper beweert dat novelty-based snoeiing de efficiëntie van Tree-of-Thought-redenering succesvol kan verbeteren, waardoor het levensvatbaar wordt voor complexe planningsopdrachten door de zoekruimte en tokenconsumptie drastisch te verminderen. De auteurs benadrukken dat, hoewel de methode afwijkt van klassieke breedtegebaseerde planning door het ontbreken van formele garanties op oplossingskwaliteit of nauwkeurige novelty-berekening, het een praktische, flexibele alternatief biedt dat de aanpasbaarheid van LLM's benut.

Echter, blijven de auteurs bescheiden wat betreft de robuustheid van de aanpak. Zij merken op dat de instabiliteit van recursieve LLM-prompting een fundamentele uitdaging blijft, waardoor configuratie arbeidsintensief en onvoorspelbaar is. De snoeigedraging wordt geobserveerd als grotendeels gedreven door duplicaatdetectie in plaats van echte "novelty"-redenering in complexe scenario's. Bijgevolg wordt het werk gepresenteerd als een stap richting efficiënter LLM-planning, met suggesties voor toekomstige richtingen zoals doelserialisatie, alternatieve novelty-schatters, of het gebruik van grotere basismodellen om staatbegrip te verbeteren.