Slower Generalization, Faster Memorization: A Sweet Spot in Algorithmic Learning

Technische Samenvatting: Langzamere Generalisatie, Snellere Memorizatie: Een Sweet Spot in Algoritmisch Leren

Probleemdefinitie
Hoewel empirische schaalwetten en "grokking"-studies suggereren dat grotere datasets over het algemeen de modelprestaties verbeteren en dat extra data de convergentie op de validatie versnelt zodra een generalisatiedrempel is overschreden, onderzoekt dit artikel of deze intuïtie universeel geldt voor taken met gestructureerde output. De auteurs vragen zich specifiek af: Zodra generalisatie mogelijk wordt, levert de grootste dataset dan altijd de snelste convergentie op de validatie op onder een vastgesteld optimalisatieprotocol? De studie richt zich op het genereren van Needleman–Wunsch (NW)-matrices, een taak waarbij een model een volledige dynamisch-programmerings-scorematrix moet voorspellen op basis van twee invoerstrings. In tegenstelling tot scalaire rekenkundige taken vereist NW de gecoördineerde voorspelling van vele afhankelijke cellen, wat resulteert in een complexe gestructureerde output.

Methodologie
De auteurs hanteren een gecontroleerd experimenteel protocol met decoder-only Transformers die getraind worden op NW-matrixgeneratie en een baseline voor vermenigvuldiging van drie cijfers.

• Taak: Het model koppelt paren invoerstrings $(x, y)$ aan een doelmatrix $M(x, y)$ die gegenereerd wordt door de NW-dynamisch-programmeringsrecursie. De correctheid wordt gemeten via exact-match-nauwkeurigheid (alle matrixvermeldingen moeten correct zijn).
• Variabelen: De primaire variabele is de datasetgrootte ($N$), die wordt doorgelopen over een breed bereik (van 200 tot 300.000 voorbeelden). Modeldiepte, optimizer-instellingen (AdamW) en leerplanschema's blijven constant.
• Maten: De studie meet het aantal optimizer-updates dat nodig is om specifieke drempels voor exact-match-nauwkeurigheid ($\tau$) te bereiken voor zowel training ($IT$) als validatie ($IV$). Deze op updates gebaseerde maat onderscheidt convergentiesnelheid van op epoch-genormaliseerde efficiëntie.
• Probes: Om regellearning te ontwarren van memorizatie, introduceren de auteurs een random-suffix-probe, waarbij een willekeurige suffix van vier bits aan de doelmatrix wordt toegevoegd. Dit isoleert voorbeeldspecifieke informatie (de suffix) van regelgegenereerde structuur (de matrix).
• Baselines: Vermenigvuldiging van drie cijfers dient als contrasttaak om te verifiëren of de waargenomen fenomenen specifiek zijn voor gestructureerde dynamische programmering of artefacten van de exact-match-evaluatie.

Belangrijkste Bijdragen
Het artikel levert drie primaire empirische bijdragen:

1. Identificatie van een Sweet Spot voor Datasetgrootte: Bij NW-matrixgeneratie is de convergentie op de validatie het snelst bij een intermediate datasetgrootte, niet bij de grootste. Dit staat in contrast met de standaard intuïtie na de drempel dat "meer data altijd sneller is" zodra generalisatie haalbaar is.
2. Versnelling van Fitting via Gedeeltelijke Regellearning: In het regime waarin zwakke competentie op de validatie voor het eerst verschijnt, kan het vergroten van de datasetgrootte het aantal updates dat nodig is om hoge trainingsnauwkeurigheid te bereiken, daadwerkelijk verminderen. Dit suggereert dat gedeeltelijke regellearning het fittingproces kan versnellen, in plaats van slechts een memorizatielast toe te voegen.
3. Mechanistische Scheiding van Drukken: De auteurs stellen een "twee-drukken-account" voor waarbij extra data aanvankelijk regeldiscovery helpt (verbetering van structurele dekking), maar uiteindelijk de kosten verhoogt van residuele exacte fitting (het memoriseren van details die niet volledig door de regel worden bepaald).

Resultaten

• Niet-monotoon Convergentie op Validatie: Voor NW volgt het aantal updates om strikte validatiedrempels te bereiken (bijv. $\tau=0.98$) een U-vormige curve. Kleine datasets falen in generalisatie of vereisen lange vertragingen. Intermediate datasets convergeren het snelst. Grote datasets generaliseren nog steeds, maar vereisen aanzienlijk meer updates om dezelfde drempel te bereiken, wat wijst op een "vertraging na de drempel".
• Contrast met Vermenigvuldiging: De vermenigvuldigingsbaseline vertoont deze vertraging niet; de convergentie op de validatie blijft vlak of verbetert bij grotere datasets. Dit bevestigt dat het fenomeen gekoppeld is aan de specifieke structuur van de NW-taak (lange, afhankelijke outputs) en niet aan de exact-match-maatstaf zelf.
• Timing van Training versus Validatie: Nabij het begin van generalisatie kunnen grotere datasets het aantal updates verminderen dat nodig is voor hoge trainingsnauwkeurigheid. Dit geeft aan dat memorizatie en generalisatie niet strikt sequentieel zijn; gedeeltelijke regelacquisitie kan de resterende fittingtaak gemakkelijker maken.
• Random-Suffix Diagnostiek: Bij grotere datasetgroottes past het model de regelgegenereerde matrix voordat het de willekeurige suffix past. Dit ondersteunt de hypothese dat het gestructureerde component profiteert van de geleerde regel, terwijl de ongestructureerde suffix de residuele "exact-fitting"-last vertegenwoordigt die groeit met de datasetgrootte.
• Train-Validatie Gap: De gap tussen trainings- en validatienauwkeurigheid ($G = A_T - A_R$) wordt precies positief wanneer de validatienauwkeurigheid begint te stijgen, wat suggereert dat dezelfde door regel bemiddelde vooruitgang beide aandrijft.

Betekenis en Claims
Het artikel claimt de klassieke grokking- en kritieke-datasetgrootte-literatuur te verfijnen, in plaats van te contrasteren.

• Verfijning van Kritieke Datasetgrootte: Waar kritieke datasetgrootte ($N_c$) het begin markeert van generalisatie (wanneer een oplossing identificeerbaar wordt), tonen de auteurs aan dat de datasetgrootte die de op updates gebaseerde convergentiesnelheid optimaliseert ($N^*$), verschillend kan zijn van $N_c$ en verschillend van de maximaal beschikbare dataset.
• Divergentie van Leringsfasen: De resultaten tonen aan dat bij taken met gestructureerde output "het leren van de regel" en "het voltooien van exacte fitting" kunnen divergeren. Zodra een bruikbare regel is ontdekt, kan verdere data voornamelijk de last vergroten van het fiten van residuele details, wat de convergentie vertraagt in termen van gradient-updates.
• Reikwijdte: De auteurs claimen bescheiden dat dit fenomeen specifiek is voor taken die herbruikbare algoritmische structuur combineren met hoge outputcomplexiteit per voorbeeld (bijv. dynamisch-programmeringstabellen zoals edit distance of Viterbi-decodering). Zij claimen niet dat dit van toepassing is op alle algoritmische taken of dat grotere datasets intrinsiek schadelijk zijn voor asymptotische nauwkeurigheid, maar eerder dat het pad naar convergentie in termen van optimizer-updates niet-monotoon is in specifieke gestructureerde settings.

De studie concludeert dat voor leren met gestructureerde output, de snelste route naar generalisatie op de validatie kan plaatsvinden bij een intermediate datasetgrootte waar de voordelen van regeldiscovery zijn verzadigd, maar de kosten van residuele exacte fitting nog niet dominant zijn geworden.