Technische Samenvatting: Lattice Deduction Transformers

Probleemstelling

Huidige grote taalmodellen (LLMs) vertrouwen sterk op het chain-of-thought-paradigma, waarbij ze tussenliggende redeneertokens genereren om tot een definitief antwoord te komen. Hoewel dit effectief is voor veel taken, mist deze aanpak vaak de rigoureuze logische geldigheid die wordt aangetroffen in geautomatiseerde redeneersystemen. Omgekeerd werkt traditioneel geautomatiseerd redeneren (bijv. SAT-oplossers) via iteratieve verfijning van gedeeltelijke informatiestaten, analoog aan discrete diffusiemodellen, maar deze methoden zijn vaak gescheiden van neurale architecturen.

De auteurs stellen een kloof vast: kunnen technieken uit geautomatiseerd redeneren, specifiek abstracte interpretatie, worden geïntegreerd in neurale architecturen om modellen te creëren die geldig redeneren (sound deduction)? Het doel is om een model te bouwen dat bij moeilijke logische problemen ofwel een correct antwoord teruggeeft ofwel zich onthoudt, nooit een incorrecte oplossing produceert, en dit doet met aanzienlijk minder parameters en trainingskosten dan eerdere recurrente redeneerders of geavanceerde LLM's.

Methodologie

De Lattice Deduction Transformer (LDT)

De kernbijdrage is de Lattice Deduction Transformer (LDT), een recurrente transformer-architectuur die is ontworpen om logisch geldig redeneren te benaderen.

1. Kader van Abstracte Interpretatie:
Het model behandelt redeneren als een afdaling door een rooster (lattice) van informatiestaten.

• Concreet Domein ($C$): De machtsverzameling van alle geldige oplossingen (bijv. alle geldige Sudoku-roosters).
• Abstract Domein ($A$): Een "rooster-machtsverzameling" waar elke cel een verzameling haalbare kandidaten bevat.
  • Top ($\top$): Vertegenwoordigt geen informatie (alle kandidaten mogelijk).
  • Bodem ($\bot$): Vertegenwoordigt inconsistentie (geen kandidaten mogelijk).
• Redenering: Een proces dat van $\top$ naar informatieverrijkte staten beweegt. Een staat die instort naar $\bot$ signaleert dat er geen geldige oplossing bestaat voor de huidige tak.

2. Architectuur:

• Recurrente Transformer: Het model gebruikt een stapel van 4 attention-lagen die worden uitgerold voor 16 interne iteraties per forward pass.
• Rooster-Encodering: De abstracte staat wordt gecodeerd als een tensor. Voor roostervragen (zoals Sudoku) is dit een multi-hot-encodering waarbij elke cel binaire sigmoids heeft die de zekerheid vertegenwoordigen dat een specifieke kandidaat nog "in leven" is.
• Projectie: Tussen forward passes wordt de latente staat geprojecteerd naar en vanuit de roosterrepresentatie. Dit dwingt elke forward pass om te fungeren als een geldige redeneerstap.
• Conflictdetectie: Een toegewijde CLS-token sigmoid voorspelt inconsistentie ($\bot$), waardoor het model onbevredigbare staten kan detecteren.

3. Trainingsprocedure (On-Policy Solve Loop):
De training vormt het inferentieproces na, zodat het model dezelfde verdeling van roosterstaten ziet als het bij de testtijd zal tegenkomen.

• De Solve Loop: Een stochastisch zoekproces dat afwisselt tussen:
  1. Redenering: De transformer verfijnt de roosterstaat (kandidaten elimineren).
  2. Vertakking: Als de staat geen oplossing of conflict is, "pint" het model stochastisch een willekeurige cel met meerdere kandidaten naar één waarde (sampling vanuit een softmax over levende kandidaten).
• Supervisie via de $\alpha$-operator: In plaats van te trainen tegen één grondwaarheid-oplossing, wordt het model gesuperviseerd tegen de abstractie van de verzameling geldige oplossingen die consistent is met de huidige staat.
  • Doel $\hat{y} = x \sqcap \alpha(\{y \in Y \mid y \text{ consistent met } x\})$.
  • Dit stelt het model in staat om gelijktijdig te leren van meerdere geldige oplossingen (meerdere-oplossingen-supervisie), waardoor de straf voor het vastleggen op één willekeurige grondwaarheid wordt vermeden wanneer meerdere bestaan.
• Verliesfunctie: Een combinatie van:
  • Asymmetrische Binary Cross-Entropy (BCE) voor kandidaat-eliminatie (sterk straffend voor valse eliminaties om geldigheid te waarborgen).
  • Symmetrische BCE voor conflictdetectie.
  • Cross-Entropy voor cellen die zijn ingestort tot één kandidaat.

4. Inferentie:
Inferentie voert een parallelle solve-procedure uit. Meerdere ketens verkennen tegelijkertijd de zoekruimte. Als een keten een conflict tegenkomt (gedetecteerd door de roosterstaat of CLS-token), backtrack het of start het opnieuw. Het systeem is ontworpen om empirisch geldig te zijn: als het een antwoord teruggeeft, is het correct; als het geen pad kan vinden, onthoudt het zich.

Kernbijdragen

1. Architectuur: Een recurrente transformer die latente staten bij elke iteratie projecteert op een abstract rooster, waardoor forward passes worden omgezet in geldige redeneerstappen.
2. On-Policy Training: Een trainingsprocedure waarbij roosterstaten evolueren onder de eigen forward pass van het model, waardoor trainingsstaten in-distribution blijven met inferentie-zoekstaten.
3. De $\alpha$-operator: Een supervisiemechanisme dat geldige oplossingen aggregeert die consistent zijn met de huidige roosterstaat. Dit creëert een regime van "on-policy maar gesuperviseerd door een domein-agnostische, staten-afhankelijke doelstelling", wat problemen met meerdere geldige oplossingen op een natuurlijke manier aanpakt.
4. Kenmerken van Compute-trade-off: Empirisch bewijs dat toegenomen trainingscompute de inferentie-zoektijd aanzienlijk verkort (met ordes van grootte), waardoor de last verschuift van zoekruimte bij testtijd naar leren bij traintijd.

Resultaten

De auteurs hebben de LDT geëvalueerd op drie benchmarks, waarbij ze deze vergeleken met geavanceerde LLM's (Claude Opus 4.6, DeepSeek V4-Pro, GPT-5.4) en eerdere recurrente redeneerders (HRM, TRM, Sotaku).

• Sudoku-Extreme:
  • Een 800K-parameter LDT behaalde 100% nauwkeurigheid op Sudoku-Extreme en Snowflake Sudoku.
  • Het bereikte empirische geldigheid (100% correct of onthouding) met 4.000 trainingsstappen.
  • Kosten: Getraind in ~15 minuten op een enkele B200 GPU, een fractie van de kosten van eerdere methoden (bijv. TRM vereiste 36 uur op 4 L40S GPU's).
  • Geavanceerde LLM's: Scoren 0% op alle benchmarks.
• Snowflake Sudoku:
  • Het model generaliseerde naar hexagonale roosters met variabele topologie (orde $n=4$ tot $8$) zonder architecturale wijzigingen, met behulp van een vast dekkingrooster en masking.
  • Behaalde 100% nauwkeurigheid met 4 minuten training.
• Maze-Hard:
  • Een 1,8M-parameter variant behaalde 99,9% nauwkeurigheid op 30x30 labyrinten met meerdere geldige kortste paden.
  • Het gebruik van meerdere-oplossingen-supervisie ($K=512$) verbeterde de prestaties ten opzichte van single-oplossingen-supervisie ($K=1$).
  • Geavanceerde LLM's scoorden opnieuw 0%.

Efficiëntie: De LDT demonstreert een sterke trade-off: extra trainingscompute vermindert drastisch het aantal forward passes (zoekstappen) dat bij inferentie vereist is.

Betekenis en Claims

Het artikel beweert dat de LDT de kloof tussen neurale netwerken en geautomatiseerd redeneren succesvol overbrugt door redeneren te behandelen als een vastpunt-berekening over een rooster.

• Geldigheid: In tegenstelling tot standaard LLM's die kunnen hallucineren, is de LDT ontworpen om empirisch geldig te zijn. Het geeft ofwel een geverifieerd correct antwoord terug of onthoudt zich, en geeft nooit een vals positief resultaat.
• Efficiëntie: Kleine modellen (onder de 2M parameters), getraind met deze specifieke on-policy, rooster-gebaseerde aanpak, presteren beter dan veel grotere recurrente redeneerders en foutloze geavanceerde LLM's op logische benchmarks.
• Generalisatie: De aanpak is domein-agnostisch wat betreft de roosterstructuur. Hoewel het is geïmplementeerd op combinatorische puzzels, kan de architectuur theoretisch worden toegepast op elk abstract domein dat een redeneeroperator toestaat.
• Beperkingen: De auteurs merken op dat de LDT momenteel het meest geschikt is voor taken met duidelijke, vaste logische regels. Het heeft moeite met taken zoals ARC-AGI, waarbij de regels zelf moeten worden afgeleid uit few-shot demonstraties, omdat de conflictkop onbetrouwbaar wordt zonder vooraf gedefinieerde redeneeroperators. Het dichten van deze kloof vereist mogelijk diepere recursieve structuren of abstracte domeinen over de programma's die oplossingen genereren.

Kortom, de LDT biedt een schaalbaar, geldig en efficiënt alternatief voor chain-of-thought-redeneren voor gestructureerde logische problemen, waarbij abstracte interpretatie wordt ingezet om neurale zoekprocessen te sturen.