AGENTIC-SYSTEMSJune 8, 20261 min read9 views

Accelerated Fourier SAT (AFSAT): Fully Realising a GPU-based Symmetric Pseudo-Boolean SAT Solver

Researchers have introduced AFSAT, a GPU-accelerated pseudo-Boolean solver based on continuous local search. By leveraging the JAX compiler, AFSAT overcomes memory and floating-point limitations, delivering superior performance and near-linear scaling across multiple accelerators.

Computer Science > Artificial Intelligence

Title:Accelerated Fourier SAT (AFSAT): Fully Realising a GPU-based Symmetric Pseudo-Boolean SAT Solver

View PDF HTML (experimental)Abstract:We present Accelerated Fourier SAT (AFSAT), a GPU-accelerated solver for pseudo-Boolean satisfiability based on continuous local search (CLS). AFSAT realises the proof-of-concept approach, FastFourierSAT, into a fully-engineered solver supporting any heterogeneous mixture of symmetric constraint types and lengths within a single problem instance. Using the JAX compiler, AFSAT leverages pure function composition, automatic vectorisation, automatic differentiation, and just-in-time (JIT) compilation to perform massively parallel CLS across batches of candidate assignments. We demonstrate substantially improved numerical stability, runtime performance, and memory efficiency over the proof-of-concept. We achieve this by way of identifying and addressing various limitations that arise from memory latency and floating-point representation, as well as leveraging automatic parallelisation and compact representations. The inherent representational and stability limitations of floating point are partially addressed by a tailored discrete Fourier transform implementation. We achieve near-linear throughput when scaling to multiple accelerators via JAX array sharding.

Bibliographic and Citation Tools

Code, Data and Media Associated with this Article

Demos

Recommenders and Search Tools

arXivLabs: experimental projects with community collaborators

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.

Source: arXiv cs.AI Recent

More in this category

agentic-systems

GraphContainer: A Unified Platform for Comparing and Debugging Graph RAG Methods

GraphContainer is a novel platform designed to unify and visualize diverse graph RAG workflows for LLMs. It features a Unified Graph Representation (UGR) layer and a Graph Recorder for live, traceable visual debugging and controlled comparison of graph retrieval strategies.

agentic-systems

Profile-Graph Memory for LLM Agents: Implicit Cross-Entity Traversal through Narrative Profiles

Researchers introduce ProGraph, a novel two-layer memory architecture designed to enhance multi-hop reasoning and precise recall for LLM agents. Alongside ProGraph, the team released MemHop, a new benchmark tailored for evaluating complex, multi-step memory retrieval.

agentic-systems

NEXUS: Structured Runtime Safety for Tool-Using LLM Agents

NEXUS is a novel structured-plan safety monitor designed for tool-using LLM agents. By combining deterministic rules and calibrated risk scoring, NEXUS enforces graded intervention policies with sub-millisecond latency.

agentic-systems

Information Discernment in Large Language Models

A new study introducing the Learn2Discern (L2D) benchmark reveals that large language models struggle to evaluate source reliability and truthfulness when integrating external knowledge. Researchers found that models often prioritize source popularity over reliability, though simple inference-time interventions can help mitigate these issues.

agentic-systems

OpenEvoShield: Dual Non-Stationary Continual Defense for Open-World Multi-Agent System Attacks

OpenEvoShield is a co-evolutionary continual defense framework designed to protect LLM-based multi-agent systems from dynamic injection attacks in open-world environments by addressing both fast attack evolution and slow normal behavior drift.

agentic-systems

Stochastic Primal-Dual Decoding for Multiobjective Generative Recommender Systems

Researchers introduced a lightweight inference-time decoding layer for generative recommender systems to optimize multi-objective slates without retraining. The stochastic primal-dual approach dynamically balances relevance and constraints, achieving a +1.8% gain in auxiliary objectives in real-world deployment.