PUZZLES: A Benchmark for Neural Algorithmic Reasoning

Статья посвящена исследованию алгоритмического мышления как ключевой когнитивной способности, необходимой для решения задач и принятия решений. Авторы подчеркивают, что RL уже продемонстрировал значительные успехи в таких областях, как управление движением, обработка сенсорных данных и взаимодействие со случайными средами, что стало возможным благодаря разработке соответствующих тестовых платформ. В данной работе представлен новый бенчмарк PUZZLES, основанный на коллекции логических головоломок Саймона Татама, целью которого является развитие алгоритмических и логических навыков RL-агентов. PUZZLES включает 40 разнообразных головоломок с настраиваемыми размерами и уровнями сложности, многие из которых дополнены параметрами конфигурации, что расширяет их вариативность.

Challenging the Boundaries of Reasoning: An Olympiad-Level Math Benchmark for Large Language Models

Статья посвящена разработке нового бенчмарка для оценки математических способностей LLM. OlymMATH — бенчмарк с олимпиадными задачами сложного уровня, созданный для проверки LLM ризонинга. Бенчмарк включает 200 задач. Задачи разделены на два уровня: простые (уровень AIME) для базовой оценки и сложные, чтобы испытать пределы современных моделей. OlymMATH охватывает четыре области математики: алгебру, геометрию, теорию чисел и комбинаторику, каждая задача имеет числовой ответ для объективной проверки. Результаты показывают, что даже передовые модели, такие как DeepSeek-R1 и o3-mini от OpenAI, справляются со сложным уровнем слабо.

Topological Blindspots: Understanding and Extending Topological Deep Learning Through the Lens of Expressivity (ICLR 2025)

Topological deep learning (TDL) is a rapidly growing field that seeks to leverage topological structure in data and facilitate learning from data supported on topological objects, ranging from molecules to 3D shapes. Most TDL architectures can be unified under the framework of higher-order message-passing (HOMP), which generalizes graph message-passing to higher-order domains. In the first part of the paper, we explore HOMP's expressive power from a topological perspective, demonstrating the framework's inability to capture fundamental topological and metric invariants such as diameter, orientability, planarity, and homology. In addition, we demonstrate HOMP's limitations in fully leveraging lifting and pooling methods on graphs. To the best of our knowledge, this is the first work to study the expressivity of TDL from a \emph{topological} perspective. In the second part of the paper, we develop two new classes of architectures -- multi-cellular networks (MCN) and scalable MCN (SMCN) -- which draw inspiration from expressive GNNs. MCN can reach full expressivity, but scaling it to large data objects can be computationally expansive. Designed as a more scalable alternative, SMCN still mitigates many of HOMP's expressivity limitations. Finally, we create new benchmarks for evaluating models based on their ability to learn topological properties of complexes. We then evaluate SMCN on these benchmarks and on real-world graph datasets, demonstrating improvements over both HOMP baselines and expressive graph methods, highlighting the value of expressively leveraging topological information.

code: https://github.com/yoavgelberg/SMCN

Simple Is Effective: The Roles of Graphs and Large Language Models in Knowledge-Graph-Based Retrieval-Augmented Generation
(ICLR 2025)

Large Language Models (LLMs) demonstrate strong reasoning abilities but face limitations such as hallucinations and outdated knowledge. Knowledge Graph (KG)-based Retrieval-Augmented Generation (RAG) addresses these issues by grounding LLM outputs in structured external knowledge from KGs. However, current KG-based RAG frameworks still struggle to optimize the trade-off between retrieval effectiveness and efficiency in identifying a suitable amount of relevant graph information for the LLM to digest. We introduce SubgraphRAG, extending the KG-based RAG framework that retrieves subgraphs and leverages LLMs for reasoning and answer prediction. Our approach innovatively integrates a lightweight multilayer perceptron with a parallel triple-scoring mechanism for efficient and flexible subgraph retrieval while encoding directional structural distances to enhance retrieval effectiveness. The size of retrieved subgraphs can be flexibly adjusted to match the query's need and the downstream LLM's capabilities. This design strikes a balance between model complexity and reasoning power, enabling scalable and generalizable retrieval processes. Notably, based on our retrieved subgraphs, smaller LLMs like Llama3.1-8B-Instruct deliver competitive results with explainable reasoning, while larger models like GPT-4o achieve state-of-the-art accuracy compared with previous baselines -- all without fine-tuning. Extensive evaluations on the WebQSP and CWQ benchmarks highlight SubgraphRAG's strengths in efficiency, accuracy, and reliability by reducing hallucinations and improving response grounding.

code: https://github.com/Graph-COM/SubgraphRAG

Neural Spacetimes for DAG Representation Learning (ICLR 2025)

We propose a class of trainable deep learning-based geometries called Neural SpaceTimes (NSTs), which can universally represent nodes in weighted Directed Acyclic Graphs (DAGs) as events in a spacetime manifold. While most works in the literature focus on undirected graph representation learning or causality embedding separately, our differentiable geometry can encode both graph edge weights in its spatial dimensions and causality in the form of edge directionality in its temporal dimensions. We use a product manifold that combines a quasimetric (for space) and a partial order (for time). NSTs are implemented as three neural networks trained in an end-to-end manner: an embedding network, which learns to optimize the location of nodes as events in the spacetime manifold, and two other networks that optimize the space and time geometries in parallel, which we call a neural (quasi-)metric and a neural partial order, respectively. The latter two networks leverage recent ideas at the intersection of fractal geometry and deep learning to shape the geometry of the representation space in a data-driven fashion, unlike other works in the literature that use fixed spacetime manifolds such as Minkowski space or De Sitter space to embed DAGs. Our main theoretical guarantee is a universal embedding theorem, showing that any k-point DAG can be embedded into an NST with 1 + O(log(k)) distortion while exactly preserving its causal structure. The total number of parameters defining the NST is sub-cubic in k and linear in the width of the DAG. If the DAG has a planar Hasse diagram, this is improved to O(log(k) + 2) spatial and 2 temporal dimensions. We validate our framework computationally with synthetic weighted DAGs and real-world network embeddings; in both cases, the NSTs achieve lower embedding distortions than their counterparts using fixed spacetime geometries.

Beyond the Lazy versus Rich Dichotomy: Geometry Insights in Feature Learning from Task-Relevant Manifold Untangling

(ICLR 2025 rejected)

The ability to integrate task-relevant information into neural representations is a fundamental aspect of both human and machine intelligence. Recent studies have explored the transition of neural networks from the lazy training regime (where the trained network is equivalent to a linear model of initial random features) to the rich feature learning regime (where the network learns task-relevant features). However, most approaches focus on weight matrices or neural tangent kernels, limiting their relevance for neuroscience due to the lack of representation-based methods to study feature learning. Furthermore, the simple lazy-versus-rich dichotomy overlooks the potential for richer subtypes of feature learning driven by variations in learning algorithms, network architectures, and data properties.

In this work, we present a framework based on representational geometry to study feature learning. The key idea is to use the untangling of task-relevant neural manifolds as a signature of rich learning. We employ manifold capacity—a representation-based measure—to quantify this untangling, along with geometric metrics to uncover structural differences in feature learning. Our contributions are threefold: First, we show both theoretically and empirically that task-relevant manifolds untangle during rich learning, and that manifold capacity quantifies the degree of richness. Second, we use manifold geometric measures to reveal distinct learning stages and strategies driven by network and data properties, demonstrating that feature learning is richer than the lazy-versus-rich dichotomy. Finally, we apply our method to problems in neuroscience and machine learning, providing geometric insights into structural inductive biases and out-of-distribution generalization. Our work introduces a novel perspective for understanding and quantifying feature learning through the lens of representational geometry.

arxiv: https://arxiv.org/abs/2503.18114

Synthesizing Programmatic Reinforcement Learning Policies with Large Language Model Guided Search (ICLR 2025)

Programmatic reinforcement learning (PRL) has been explored for representing policies through programs as a means to achieve interpretability and generalization. Despite promising outcomes, current state-of-the-art PRL methods are hindered by sample inefficiency, necessitating tens of millions of program-environment interactions. To tackle this challenge, we introduce a novel LLM-guided search framework (LLM-GS). Our key insight is to leverage the programming expertise and common sense reasoning of LLMs to enhance the efficiency of assumption-free, random-guessing search methods. We address the challenge of LLMs' inability to generate precise and grammatically correct programs in domain-specific languages (DSLs) by proposing a Pythonic-DSL strategy - an LLM is instructed to initially generate Python codes and then convert them into DSL programs. To further optimize the LLM-generated programs, we develop a search algorithm named Scheduled Hill Climbing, designed to efficiently explore the programmatic search space to improve the programs consistently. Experimental results in the Karel domain demonstrate our LLM-GS framework's superior effectiveness and efficiency. Extensive ablation studies further verify the critical role of our Pythonic-DSL strategy and Scheduled Hill Climbing algorithm. Moreover, we conduct experiments with two novel tasks, showing that LLM-GS enables users without programming skills and knowledge of the domain or DSL to describe the tasks in natural language to obtain performant programs.

Can ChatGPT Learn My Life From a Week of First-Person Video?

Исследуется способность LLM узнавать о личной жизни владельца с помощью данных с action-камеры. Автор носил гарнитуру с камерой 54 часа в течение недели. Затем вгружал в GPT-4o and GPT-4o-mini и запрашивал анализ полученной инфы. Обе модели узнали базовую информацию об авторе (приблизительный возраст, пол). Более того, GPT-4o правильно сделала вывод, что автор из Питтсбурга, что он аспирант Carnegie Mellon University, правша и владелец кошки. Однако обе модели также страдали галлюцинациями и придумывали имена для людей, присутствующих на видеозаписях.

StructRAG: Boosting Knowledge Intensive Reasoning of LLMs via Inference-time Hybrid Information Structurization (ICLR 2025)

Retrieval-augmented generation (RAG) - подход для улучшения LLM во многих задачах, основанных на внешних знаниях. Существующие методы RAG работают не очень хорошо с задачами на ризонинг, поскольку полезная информация, необходимая для этих задач, сильно разбросана по системам хранения знаний. Статья мотивирована когнитивными исследованиями о том, что люди преобразуют необработанную информацию в различные оптимально структурированные знания при решении задач на мышление. В работе предлагается подход StructRAG, который определяет оптимальный тип структуры для данной задачи, транслирует информацию в этот формат и выводит ответы на основе извлеченных знаний. Эксперименты показывают, что StructRAG достигает sota в сложных реальных приложениях.

imho: За этим направлением (разумеется, в более развитой его форме, чем сейчас) следующий хайп и мб AGI

Can LLMs Obfuscate Code? A Systematic Analysis of Large Language Models into Assembly Code Obfuscation (AAAI 2025)

Авторы вредоносных программ часто используют обфускацию кода, чтобы их вредоносное ПО было сложнее обнаружить. Существующие инструменты для генерации обфусцированного кода часто требуют доступа к исходному коду, а добавление новых обфускаций является нетривиальным, трудоемким процессом. Авторы задаются следующим вопросом: могут ли LLM генерировать новый обфусцированный ассемблерный код?

Если да, то это представляет риск для антивирусных фреймворков и потенциально увеличивает гибкость злоумышленников для создания новых шаблонов обфускации. В статья даётся утвердительный ответ на этот вопрос. Разрабатывается бенчмарк MetamorphASM, включающий набор данных MetamorphASM (MAD) вместе с тремя методами обфускации кода: мертвый код, подстановка регистров и изменение потока управления. MetamorphASM позволяет оценивать способность LLM генерировать и анализировать обфусцированный код. Анализируется успешность различных LLM (GPT-3.5/4, GPT-4o-mini, Starcoder, CodeGemma, CodeLlama, CodeT5 и LLaMA 3.1) в создании обфусцированного ассемблерного кода.

imho: очень интересно направление, связанное с обратной задачей по де-обфускации кода с помощью LLM

ReTool: Reinforcement Learning for Strategic Tool Use in LLMs

В статье предлагается подход для улучшения математического ризонинга LLM в задачах, где модели, обученные с помощью RL (например, DeepSeek R1), уступают интерпретаторам кода. Подход называется ReTool и работает в 2 этапа:

1) Динамическое чередование выполнения кода в реальном времени и рассуждений на естественном языке.
2) Автоматизированный RL-based подход обучения модели оптимальному вызову инструментов на основе обратной связи от результатов.

Обучение начинается с генерации синтетических данных для создания трейсов (последовательности) длинных рассуждений с кодом, используемых для тюнинга модели. Далее RL-обучение использует результаты задач как вознаграждения для итеративного улучшения стратегии вызова инструментов. Также авторами выявляется эффект самокоррекции кода, указывающий на адаптивное освоение инструментов.

imho: ресерчить tool reasoning сейчас очень своевременно

Harnessing the Universal Geometry of Embeddings

Работа представляет метод vec2vec для трансляции эмбеддингов текстов из одного векторного пространства в другое без каких-либо парных данных (как в CLIP). Подход основан на гипотезе платонических представлений (предположение, что пространство векторных представлений внутри разных моделей и даже для разных модальностей в конечно счете имеет некоторую универсальную общую семантическую структуру представления знаний), и любой эмбеддинг авторы переводят в это представление и из него. Тестировался метод на эмбеддингах из разных моделей с различными архитектурами, колвом параметров и обучающими наборами данных.

Утверждается, что возможность перевода неизвестных эмбеддингов в другое пространство с сохранением их геометрии имеет понятные последствия для безопасности векторных баз данных: можно из открытых векторных баз данных переводить информацию в скрытые представления какой-то известной Foundation модели, про которую есть очень много методов, как интепретировать представления и извлекать информацию, и таким образом получать очень много казалось бы скрытой инфы.

Enigmata: Scaling Logical Reasoning in Large Language Models with Synthetic Verifiable Puzzles

В работе разрабатывается генеративный датасет Enigmata, который предназначен для улучшения способностей к ризонингу у LLM. Бенчмарк содержит 36 игр и задач из разных категорий (криптография, арифметика, логика, сеточные головоломки и др.) В основе бенчмарка лежит 1) генератор задач (для каждого из 36 типов) контролируемой сложности. 2) автоматический верификатор для оценки ответов ЛЛМ. С помощью генератора-верификатора ЛЛМ Qwen2.5 обучается в Reinforcement Learning with Verifiable Rewards (RLVR, это когда реворд достоверно проверен на корректность) сетапе, полученная модель называется Qwen2.5-32B-Enigmata.

Она превосходит o3-mini-high и o1 на датасетах: EnigmataEval (специально созданный для верификации набор задач из Enigmata), на ARC-AGI (32,8%) и ARC-AGI 2 (0,6%). При обучении на Enigmata модели Seed1.5-Thinking (Mixture-of-Experts система) в RLVR режиме, повышается её производительность в математических (AIME (2024-2025) и STEM задачах.

Т.е. если обучать в RLVR на Enigmata модели, можно относительно за недорого прокачивать их общие ризонинг способности.