# Neural Algorithmic Reasoning for Hypergraphs with Looped Transformers

arXiv: https://arxiv.org/abs/2501.10688 · HTML: https://mlsanity.com/paper/2501.10688/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Placed in Prompting and chain-of-thought reasoning, one of 17 directions in LLM reasoning.
- Builds on 85 of its 113 references that are in the map.
- First posted on arXiv 18 Jan 2025.

## Placed in

- LLM reasoning / [Prompting and chain-of-thought reasoning](https://mlsanity.com/lr/prompting-and-chain-of-thought-reasoning/)

## Builds on (most cited first, 30 of 85)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [LoRA: Low-Rank Adaptation of Large Language Models](https://mlsanity.com/paper/2106.09685/) (2021)
- [LLaMA: Open and Efficient Foundation Language Models](https://mlsanity.com/paper/2302.13971/) (2023)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [PaLM: Scaling Language Modeling with Pathways](https://mlsanity.com/paper/2204.02311/) (2022)
- [On the Opportunities and Risks of Foundation Models](https://mlsanity.com/paper/2108.07258/) (2021)
- [Prefix-Tuning: Optimizing Continuous Prompts for Generation](https://mlsanity.com/paper/2101.00190/) (2021)
- [The Power of Scale for Parameter-Efficient Prompt Tuning](https://mlsanity.com/paper/2104.08691/) (2021)
- [Tree of Thoughts: Deliberate Problem Solving with Large Language Models](https://mlsanity.com/paper/2305.10601/) (2023)
- [Scaling Instruction-Finetuned Language Models](https://mlsanity.com/paper/2210.11416/) (2022)
- [Sparks of Artificial General Intelligence: Early experiments with GPT-4](https://mlsanity.com/paper/2303.12712/) (2023)
- [Calibrate Before Use: Improving Few-Shot Performance of Language Models](https://mlsanity.com/paper/2102.09690/) (2021)
- [Making Pre-trained Language Models Better Few-shot Learners](https://mlsanity.com/paper/2012.15723/) (2020)
- [Show Your Work: Scratchpads for Intermediate Computation with Language Models](https://mlsanity.com/paper/2112.00114/) (2021)
- [LLaMA-Adapter: Efficient Fine-tuning of Language Models with Zero-init Attention](https://mlsanity.com/paper/2303.16199/) (2023)
- [Transformers learn in-context by gradient descent](https://mlsanity.com/paper/2212.07677/) (2022)
- [Cross-Task Generalization via Natural Language Crowdsourcing Instructions](https://mlsanity.com/paper/2104.08773/) (2021)
- [Universal Transformers](https://mlsanity.com/paper/1807.03819/) (2018)
- [LLaMA-Adapter V2: Parameter-Efficient Visual Instruction Model](https://mlsanity.com/paper/2304.15010/) (2023)
- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [Hypergraph Neural Networks](https://mlsanity.com/paper/1809.09401/) (2018)
- [Demonstrate-Search-Predict: Composing retrieval and language models for knowledge-intensive NLP](https://mlsanity.com/paper/2212.14024/) (2022)
- [Black-Box Tuning for Language-Model-as-a-Service](https://mlsanity.com/paper/2201.03514/) (2022)
- [Looped Transformers as Programmable Computers](https://mlsanity.com/paper/2301.13196/) (2023)
- [Hypergraph Convolution and Hypergraph Attention](https://mlsanity.com/paper/1901.08150/) (2019)
- [Looped Transformers are Better at Learning Learning Algorithms](https://mlsanity.com/paper/2311.12424/) (2023)
- [Representational Strengths and Limitations of Transformers](https://mlsanity.com/paper/2306.02896/) (2023)
- [Neural Execution of Graph Algorithms](https://mlsanity.com/paper/1910.10593/) (2019)

## Built on by (most cited first, 4 of 4)

- [Theoretical Guarantees for High Order Trajectory Refinement in Generative Flows](https://mlsanity.com/paper/2503.09069/) (2025)
- [Theoretical Foundation of Flow-Based Time Series Generation: Provable Approximation, Generalization, and Efficiency](https://mlsanity.com/paper/2503.14076/) (2025)
- [Loom: A Scalable Analytical Neural Computer Architecture](https://mlsanity.com/paper/2604.08816/) (2026)
- [A Symbolic Neural CPU for Quantization-Simulated Writeback and Interpretable Program Execution](https://mlsanity.com/paper/2607.10021/) (2026)

## Abstract (arXiv)

Looped Transformers have shown exceptional neural algorithmic reasoning capability in simulating traditional graph algorithms, but their application to more complex structures like hypergraphs remains underexplored. Hypergraphs generalize graphs by modeling higher-order relationships among multiple entities, enabling richer representations but introducing significant computational challenges. In this work, we extend the Loop Transformer architecture's neural algorithmic reasoning capability to simulate hypergraph algorithms, addressing the gap between neural networks and combinatorial optimization over hypergraphs. Specifically, we propose a novel degradation mechanism for reducing hypergraphs to graph representations, enabling the simulation of graph-based algorithms, such as Dijkstra's shortest path. Furthermore, we introduce a hyperedge-aware encoding scheme to simulate hypergraph-specific algorithms, exemplified by Helly's algorithm. We establish theoretical guarantees for these simulations, demonstrating the feasibility of processing high-dimensional and combinatorial data using Loop Transformers. This work highlights the potential of Transformers as general-purpose algorithmic solvers for structured data.