From Heuristics to Bayesian Policies: Toward a Unified Decision-Theoretic Foundation for Adaptive Algorithms in Computational Mathematics

У цьому документі пропонується фундаментальна зміна парадигми в тому, як ми проектуємо та оптимізуємо алгоритми в обчислювальній математиці. Замість того, щоб покладатися на вручну налаштовані емпіричні евристики, ми виступаємо за те, щоб розглядати кожну ключову точку прийняття рішення як послідовну задачу прийняття рішення в умовах невизначеності та вирішувати її за допомогою інструментів баєсівської теорії прийняття рішень — оптимальної зупинки, багаторуких бандитів та марковських процесів прийняття рішень. Використовуючи цілочисельну факторизацію як основний приклад, ми демонструємо, як замінити статичні пороги адаптивними, специфічними для екземпляра політиками, які мають теоретичні гарантії жалю. Така ж методологічна основа природно поширюється на розв'язувачі SAT, алгоритми скорочення решітки, обчислення базису Грьобнера, пошук простих чисел та числові методи в наукових обчисленнях. Основний внесок полягає не лише в потенційному прирості продуктивності (аналітично оціненому на рівні 7–20% для факторизації), а й у загальному, переносимому рецепті перетворення непрозорих евристик на прозорі, самовдосконалювані байєсівські політики. Ця робота спрямована на поєднання обчислювальної теорії чисел із сучасною теорією рішень та машинним навчанням, відкриваючи шлях до нового покоління адаптивних, «самосвідомих» алгоритмів. Супровідний технічний препринт з детальними висновками для випадку факторизації доступний за адресою: https://doi.org/10.5281/zenodo.20682765 Від евристик до Bayesian Policies: Нова парадигма адаптивних алгоритмів у теорії чисел та обчислювальній математиці Автор: Serhii Kanivets Дата: 13 червня 2026 Версія: 1.0 (draft для обговорення) Анотація Сучасна обчислювальна математика, особливо теорія чисел, досі значною мірою спирається на евристики, які роками тюнілися вручну. Ми пропонуємо радикальну зміну парадигми: систематичне переписування цих евристик як задач Bayesian decision making під неповною інформацією. На прикладі факторизації цілих чисел ми демонструємо, як optimal stopping, multi-armed bandits, Markov Decision Processes та Bayesian inference дозволяють замінити «магічні константи» на формальні оптимальні політики з теоретичними гарантіями (regret bounds). Цей підхід не обмежується факторизацією. Він відкриває двері до універсальної методології адаптивних алгоритмів у SAT-solving, lattice reduction, symbolic computation, пошуку простих чисел та навіть чисельних методах фізики. Найцінніше — не локальне прискорення, а методологічний міст між computational number theory та сучасним AI/decision theory. Ми віримо, що це може стати початком нової ери «самоусвідомлених» алгоритмів, які навчаються та оптимізуються в реальному часі під конкретну задачу. 1. Вступ: Криза евристик У теорії чисел ми маємо потужні алгоритми (GNFS, ECM, LLL/BKZ, CDCL SAT-солвери), але їхня ефективність залежить від десятків параметрів, порогів та стратегій перемикання, які підбираються емпірично. Ці евристики працюють добре на «середніх» випадках, але часто субоптимальні для конкретних інстансів. Ручне тюніння — це bottleneck розвитку. Пропонована парадигма: Кожну евристичну точку вибору трактувати як послідовне рішення за умов невизначеності, де: Стан = поточні posterior ймовірності успіху/гладкості/збігання. Дії = продовжити, змінити параметри, переключити стратегію, зупинитися. Utility = очікуваний час до рішення мінус cost обчислень. 2. Приклад: Факторизація як Bayesian Decision Process (Короткий огляд з твоєї статті, розширений) Early-abort у сівінгу → Optimal Stopping Problem з гібридною моделлю smoothnes (Dickman + logistic regression на фічерах). Вибір ECM-профілів → Bayesian Multi-Armed Bandit (Thompson Sampling). Перехід ECM ↔ GNFS → Bayesian stopping criterion. Глобальний workflow → MDP з (майже) сепарабельною структурою. Теоретичні результати (regret bounds, decomposition bound) показують, що втрати від субоптимальності мінімальні, а потенціал прискорення — значний. 3. Перенесення на інші домени (найцікавіша частина) 3.1 SAT-solvers Сучасні CDCL-солвери повні евристик: restart frequency, clause deletion policies, branching heuristics (VSIDS, LRB). Bayesian перепис: Моделювати ймовірність успіху гілки за допомогою online Bayesian inference. Використовувати bandits для портфоліо різних heuristics. Early-abort або перемикання search strategies як optimal stopping. Вже існують RL/GNN-підходи (GQSAT та інші) — наш фреймворк дає теоретичні гарантії та уніфікує їх. Потенціал: 2–5× прискорення на важких інстансах (крипто, verification). 3.2 Lattice Reduction (LLL, BKZ, Slide Reduction) Евристики: block size, tour length, pruning strategies, early termination. Bayesian підхід: На кожному турі оновлювати posterior на якість поточної бази. MDP для рішення: продовжувати редукцію чи переходити до enumeration/SVP-оракула. Bandits для вибору pruning параметрів. Це критично для криптоаналізу (NTRU, Kyber тощо) та атак на lattice-based crypto. 3.3 Symbolic Computation (Groebner bases, Cylindrical Algebraic Decomposition) Adaptive term ordering. Early abandonment неперспективних гілок на основі Bayesian прогнозу ступеня розростання. Bandits для вибору heuristics у Buchberger algorithm. 3.4 Пошук простих чисел та Primality Testing Adaptive вибір witnesses у Miller-Rabin. Dynamic switching між probabilistic та deterministic тестами. Optimal stopping для probabilistic tests. 3.5 Integer Relation Algorithms (PSL/Q, LLL-based) Bayesian early stopping при пошуку relation’ів. 3.6 Чисельні методи в фізиці та наукових обчисленнях Adaptive mesh refinement. Monte Carlo integration з Bayesian optimal experimental design. MDP для choice of numerical schemes. 4. Чому це працює саме зараз? Зрілість Bayesian methods та online learning. Обчислювальна потужність дозволяє online inference. Успіхи RL у games та SAT показують feasibility. Потреба в адаптивності росте з розміром задач (post-quantum crypto, verification, scientific computing). 5. Виклики та шлях вперед Обчислювальний overhead Bayesian inference (рішення: lightweight approximations, amortized updates). Моделювання невизначеності — потрібні хороші priors та feature engineering. Теоретичні гарантії vs реальна продуктивність (потрібні великі бенчмарки). Інтеграція з існуючими софтверами (CADO-NFS, GMP-ECM, CaDiCaL, fplll тощо). Пропозиція: Створити open-source фреймворк «Bayesian Algorithmic Decision Layer» (BADL), який можна накладати поверх класичних бібліотек. Висновок: Нова філософія алгоритмів Ми стоїмо на порозі переходу від статичних евристичних алгоритмів до адаптивних Bayesian policies, які самі розуміють, що роблять, і оптимізують свої дії в реальному часі. Це не просто оптимізація факторизації. Це універсальний рецепт для багатьох галузей обчислювальної математики. Найбільша цінність — у методологічному зсуві: від «як ми завжди робили» до «що оптимально робити зараз, виходячи з того, що ми вже дізналися». Якщо половина оцінок у факторизації правильна, то справжній вплив буде в десятках інших доменів. Запрошуємо спільноту до експериментів, реалізації та розширення цієї парадигми. Це може стати одним із тих papers, які змінюють спосіб мислення цілої галузі.