LLM-ovi uče najkraći put na grafovima — ali padaju kad se produlji horizont zadatka

Novi arXiv rad istražuje sistematsku generalizaciju LLM-ova na problemu najkraćeg puta u grafu po dvije dimenzije: prostorni transfer na neviđene karte radi dobro, ali skaliranje duljinom horizonta dosljedno puca zbog rekurzivne nestabilnosti. Zaključak ima direktne implikacije za autonomne agente — pokrivenost trening podataka definira granicu sposobnosti, RL poboljšava stabilnost ali ne proširuje granice, inference-time scaling pomaže ali ne rješava length-scaling problem.

Što se testiralo?

Tim istraživača Tong, Ye, Borovykh i Shokri objavio je na arXivu rad koji sustavno analizira može li LLM postići sistematsku generalizaciju na klasičnom algoritamskom problemu — pronalaženju najkraćeg puta u grafu. Testiranje je obuhvaćalo dvije nezavisne dimenzije generalizacije:

Prostorni transfer — može li model koji je učio na određenom skupu grafova rješavati probleme na neviđenim kartama s drugačijim topologijama?
Skaliranje horizontom — može li model koji je učio na kraćim putevima (recimo, 5-10 koraka) ispravno riješiti dulje putove (50+ koraka)?

Ova metodologija je namjerno šira od standardnih benchmark tipova — ne mjeri samo jesu li pitanja nova, nego jesu li zahtjevi strukturno zahtjevniji od onog što je model vidio u treningu.

Što su našli?

Rezultati su dosljedni i vrijedni pažnje:

Prostorni transfer: uspješan. Modeli koji nauče pronalaziti putove u skupu grafova uspješno generaliziraju na neviđene topologije iste veličine. To znači da je “naučiti algoritam” u nekoj mjeri moguće.
Length scaling: dosljedan neuspjeh. Kad se duljina puta produlji izvan treninškog raspona, modeli padaju zbog rekurzivne nestabilnosti — male greške u jednom koraku akumuliraju se eksponencijalno do kraja.

Dodatno su testirali tri intervencije:

Pokrivenost podataka definira granicu sposobnosti — model zna ono što je vidio u treningu, skaliranje preko toga ne funkcionira.
RL (reinforcement learning) poboljšava stabilnost u trening rasponu, ali ne proširuje granice generalizacije.
Inference-time scaling (više token-budgeta, chain-of-thought) pomaže, ali ne rješava osnovni length-scaling problem.

Zašto je ovo bitno za autonomne agente?

Mnoge praktične agent zadaće zahtijevaju dug horizont: multi-step planiranje, research, software engineering projekti koji traju danima, iterativno debagiranje složenog sustava. Ako LLM-ovi strukturalno ne mogu skalirati duljinom — što ovaj rad sugerira — onda je autonomnost agenata fundamentalno ograničena veličinom problema koji su vidjeli u treningu.

To se poklapa s ranijim nalazima (npr. LongCoT benchmark gdje GPT 5.2 postiže 9,8 % na dugom chain-of-thought razsuđivanju): naizgled najjači modeli ruše se kad se problem produlji.

Što to znači za praksu?

Istraživači ne tvrde da je problem nerješiv, ali identificiraju tri neizbiježne istine:

Sintetski dataset coverage mora eksplicitno uključivati dugačke putove — inače model nikad neće znati kako da ih obrađuje.
RL i inference-time scaling nisu čarobni štapić — oni poboljšavaju ono što je model već naučio, ali ne dodaju novu sistematsku sposobnost.
Arhitekturne promjene (hijerarhijski agenti, planiranje s eksplicitnim state managementom) mogle bi biti nužne za stvarni length generalization.

Za AI news čitatelja zaključak je: kad sljedeći put pročitate da model radi “autonomne research projekte”, pitanje je koliko je taj horizont zapravo dubok, i je li problem unutar ili izvan trening raspona tog modela.

Česta pitanja

Koji problem rad istražuje?

Može li LLM koji je naučio rješavati probleme najkraćeg puta na malim grafovima generalizirati na velike grafove s duljim putevima, i na neviđene topologije karti.

Zašto je ovo važno za AI agente?

Jer mnoge praktične agentne zadaće (multi-step planiranje, software engineering, research) zahtijevaju dug horizont — ako LLM-ovi ne mogu skalirati duljinom, autonomnost agenata je fundamentalno ograničena.