Events & Conferences
Amazon Scholar solves century-old problem with automated reasoning
Marijn Heule, an Amazon Scholar and professor of computer science at Carnegie Mellon University, together with his colleague Manfred Scheucher of Technische Universität Berlin, have solved a geometry problem posed almost 100 years ago by the Hungarian-Australian mathematician Esther Szekeres.
Paul Erdős, the legendary Hungarian mathematician who gave his name to the Erdős number, dubbed it the “happy-ending problem”, because work on it led to the marriage of Esther, née Klein, and Erdős’s long-time collaborator George Szekeres.
The problem asks the minimum number of points in a plane, no three of which are collinear, required to guarantee that n of the points constitute a convex polygon that does not contain any of the other points. (“Convex” means that a line segment connecting any two points within the polygon itself lies entirely within the polygon.)
Esther Szekeres dispatched the case of n = 4 in the 1930s. It was almost 50 years before Heiko Harborth determined that 10 points are needed to guarantee an empty pentagon. Around the same time, Joseph Horton showed that the problem is insoluble for polygons with seven or more sides: no number of points will guarantee that a convex 7-gon can be found that contains no other points in the collection.
But the remaining case — the empty hexagon — was still outstanding. That’s the problem that Heule and Scheucher solved. They showed that 30 points is sufficient to guarantee a convex hexagon that doesn’t contain any of the other points.
To prove this result, Heule and Scheucher used a SAT solver, an automated-reasoning tool that determines whether long chains of logical constraints can be satisfied. The SAT solver generates a proof that particular assignments of values to variables are prohibited by the constraints. Verifying the correctness of the proof requires another automated-reasoning tool, a proof checker.
Proofs, however, can be hundreds of terabytes in size, and just managing input-output (I/O) and data retrieval during the proof-checking process can be hugely time consuming. “The cost of checking can be, say, 100% to 200% of the original solving time,” Heule says.
Heule, who is a member of Amazon Web Services’ (AWS’s) Automated Reasoning group, worked with his AWS colleagues to develop the infrastructure for a new streaming approach to proof checking, where a dedicated server core checks the proof as it is generated. This reduces the proof-checking overhead from 100% to 200% to somewhere around 10%.
This innovation, in turn, will be of use to the Automated Reasoning group in its future work on, say, software security, provably correct software, and hardware validation. Of course, those applications still require developers to create rigorous formal models of the systems they’re validating. But during the proof-checking phase, “if we can do things with say 10% overhead instead of 150%, that’s a clear win,” Heule says.
Geometric constraints
SAT problems are NP-complete, meaning that SAT problems can be devised that would be insoluble by all the computers in the world in the lifetime of the universe.
But that doesn’t mean that all SAT problems, or even SAT problems with large numbers of variables, are insoluble, and part of the automated-reasoning researcher’s art is formulating problems in such a way that a SAT solver can solve them.
“Marijn is best-in-the-world at mapping complex problems to solvers,” says Robert Jones, a senior principal applied scientist in the AWS Automated Reasoning group.
The setup of the happy-ending problem can be described using binary (Boolean) variables each of which describes the orientations of three points. The variables all have the same general form: given three points in general position (i.e., not collinear), A, B, and C, C is above the line through A and B. (If the variable is false, C is necessarily below the line.) Chain enough of these together, and you can specify the 30 points of the 6-gon case (or 29 points, or any other number).
Within that framework, the difficulty is to describe the condition that there be at least one hexagon with no point inside it. Scheucher’s group had been batting that problem about for years without arriving at a formulation that a SAT solver could handle. That’s where Heule came in.
People mapping problems to SAT expressions often focus on concision, Heule explains; the more concise the expression, they reason, the fewer possibilities the solver will need to consider. That may be true in general, Heule says, but in his experience, long chains of simple constraints are often easier to reason about than short chains of more complex constraints.
Simplifying the problem
The natural way to approach the empty-hexagon problem is to break hexagons into triangles and reason about whether each triangle has a point in its interior. Prior attempts to map this problem to a SAT expression had taken a general approach, specifying a set of logical constraints that could be applied to any triangle in the collection and all hexagons that included that triangle. The resulting expression, Heule says, was easy to formulate but hard to reason about.
Heule suggested that he and Scheucher take the opposite tack, explicitly labeling every possible configuration of each hexagon, specifying the individual triangles using those labels, and checking each of the named triangles for points in its interior.
“In this case, you really need to blow it up in order to get much smaller later,” Heule explains. “I made it 10 times bigger and afterward realized that the new expression could be compressed substantially. This compression step is also possible with existing automated-reasoning tools.”
One of the ways that SAT solvers reduce the complexity of the problems they’re tackling is by looking for logical redundancies and removing them. In his initial specification of the empty-hexagon problem, Heule divided each hexagon in the point set into four triangles and checked each triangle for a point in its interior.
He noticed, however, that the SAT solver reduced this step to checking only one triangle per hexagon. After thinking it through, Heule and Scheucher realized that in each hexagon, there was a single triangle — call it the inner triangle — that shared all its sides with the hexagon’s other three triangles — call them the outer triangles. If that inner triangle was empty, then it was possible to deduce the existence of an empty hexagon from the points in the point set.
Suppose that one of the outer triangles contains a point. Then it’s possible to draw a new triangle that contains that point and shares a side with the inner triangle. Repeating this process as needed is guaranteed to yield a convex hexagon with no points in its interior.
Heule and Scheucher extracted this line of reasoning from the SAT solver itself. “I have frequently seen that the solver provides useful feedback, although it’s feedback for an expert,” Heule says. “I think it’s really important that this feedback becomes available for nonexperts. For example, you implement something, and the solver says, ‘Okay, you’re trying to do this, but that part of the expression is not needed.’ This feedback can be used to reformulate the expression in such a way that that it is much easier to solve.”
Once Heule and Scheucher understood what the solver was telling them, they were able to devise a more practical specification of the SAT problem. The solver was able to reason through all the possibilities for a 30-point point set and prove that, within that set, there must exist at least one hexagon whose inner triangle contained no other points.
It was still an extremely long proof, but Heule and his AWS colleagues’ new proof-checking mechanism was able to confirm its validity relatively quickly.
“One of the issues here is that many users of these tools don’t know how to get the most out of them,” Heule says. “And that’s not only for this specific problem but for many other problems as well. Within Amazon, there are a lot of applications where SAT solvers could verify developers’ work or find better solutions. I can help by writing an effective encoding, but ideally, everything would be done automatically. I would love to see myself being taken out of the equation.”
Have you ever worked is legacy code? Are you curious what it takes to modernize systems at a massive scale?
Pascal Hartig is joined on the latest Meta Tech Podcast by Elaine and Buping, two software engineers working on a bold project to rewrite the decades-old C code in one of Meta’s core messaging libraries in Rust. It’s an ambitious effort that will transform a central messaging library that is shared across Messenger, Facebook, Instagram, and Meta’s AR/VR platforms.
They discuss taking on a project of this scope – even without a background in Rust, how they’re approaching it, and what it means to optimize for ‘developer happiness.’
Download or listen to the episode below:
You can also find the episode wherever you get your podcasts, including:
The Meta Tech Podcast is a podcast, brought to you by Meta, where we highlight the work Meta’s engineers are doing at every level – from low-level frameworks to end-user features.
Send us feedback on Instagram, Threads, or X.
And if you’re interested in learning more about career opportunities at Meta visit the Meta Careers page.
Amazon Research Awards (ARA) provides unrestricted funds and AWS Promotional Credits to academic researchers investigating various research topics in multiple disciplines. This cycle, ARA received many excellent research proposals from across the world and today is publicly announcing 73 award recipients who represent 46 universities in 10 countries.
This announcement includes awards funded under five call for proposals during the fall 2024 cycle: AI for Information Security, Automated Reasoning, AWS AI, AWS Cryptography, and Sustainability. Proposals were reviewed for the quality of their scientific content and their potential to impact both the research community and society. Additionally, Amazon encourages the publication of research results, presentations of research at Amazon offices worldwide, and the release of related code under open-source licenses.
Recipients have access to more than 700 Amazon public datasets and can utilize AWS AI/ML services and tools through their AWS Promotional Credits. Recipients also are assigned an Amazon research contact who offers consultation and advice, along with opportunities to participate in Amazon events and training sessions.
“Automated Reasoning is an important area of research for Amazon, with potential applications across various features and applications to help improve security, reliability, and performance for our customers. Through the ARA program, we collaborate with leading academic researchers to explore challenges in this field,” said Robert Jones, senior principal scientist with the Cloud Automated Reasoning Group. “We were again impressed by the exceptional response to our Automated Reasoning call for proposals this year, receiving numerous high-quality submissions. Congratulations to the recipients! We’re excited to support their work and partner with them as they develop new science and technology in this important area.”
“At Amazon, we believe that solving the world’s toughest sustainability challenges benefits from both breakthrough scientific research and open and bold collaboration. Through programs like the Amazon Research Awards program, we aim to support academic research that could contribute to our understanding of these complex issues,” said Kommy Weldemariam, Director of Science and Innovation Sustainability. “The selected proposals represent innovative projects that we hope will help advance knowledge in this field, potentially benefiting customers, communities, and the environment.”
ARA funds proposals throughout the year in a variety of research areas. Applicants are encouraged to visit the ARA call for proposals page for more information or send an email to be notified of future open calls.
The tables below list, in alphabetical order by last name, fall 2024 cycle call-for-proposal recipients, sorted by research area.
AI for Information Security
| Recipient | University | Research title |
| Christopher Amato | Northeastern University | Multi-Agent Reinforcement Learning Cyber Defense for Securing Cloud Computing Platforms |
| Bernd Bischl | Ludwig Maximilian University of Munich | Improving Generative and Foundation Models Reliability via Uncertainty-awareness |
| Shiqing Ma | University Of Massachusetts Amherst | LLM and Domain Adaptation for Attack Detection |
| Alina Oprea | Northeastern University | Multi-Agent Reinforcement Learning Cyber Defense for Securing Cloud Computing Platforms |
| Roberto Perdisci | University of Georgia | ContextADBench: A Comprehensive Benchmark Suite for Contextual Anomaly Detection |
Automated Reasoning
| Recipient | University | Research title |
| Nada Amin | Harvard University | LLM-Augmented Semi-Automated Proofs for Interactive Verification |
| Suguman Bansal | Georgia Institute of Technology | Certified Inductive Generalization in Reinforcement Learning |
| Ioana Boureanu | University of Surrey | Phoebe+: An Automated-Reasoning Tool for Provable Privacy in Cryptographic Systems |
| Omar Haider Chowdhury | Stony Brook University | Restricter: An Automatic Tool for Authoring Amazon Cedar Access Control Policies with the Principle of Least Privilege |
| Stefan Ciobaca | Alexandru Ioan Cuza University | An Interactive Proof Mode for Dafny |
| João Ferreira | INESC-ID | Polyglot Automated Program Repair for Infrastructure as Code |
| Sicun Gao | University Of California, San Diego | Monte Carlo Trees with Conflict Models for Proof Search |
| Mirco Giacobbe | University of Birmingham | Neural Software Verification |
| Tobias Grosser | University of Cambridge | Synthesis-based Symbolic BitVector Simplification for Lean |
| Ronghui Gu | Columbia University | Scaling Formal Verification of Security Properties for Unmodified System Software |
| Alexey Ignatiev | Monash University | Huub: Next-Gen Lazy Clause Generation |
| Kenneth McMillan | University of Texas At Austin | Synthesis of Auxiliary Variables and Invariants for Distributed Protocol Verification |
| Alexandra Mendes | University of Porto | Overcoming Barriers to the Adoption of Verification-Aware Languages |
| Jason Nieh | Columbia University | Scaling Formal Verification of Security Properties for Unmodified System Software |
| Rohan Padhye | Carnegie Mellon University | Automated Synthesis and Evaluation of Property-Based Tests |
| Nadia Polikarpova | University Of California, San Diego | Discovering and Proving Critical System Properties with LLMs |
| Fortunat Rajaona | University of Surrey | Phoebe+: An Automated-Reasoning Tool for Provable Privacy in Cryptographic Systems |
| Subhajit Roy | Indian Institute of Technology Kanpur | Theorem Proving Modulo LLM |
| Gagandeep Singh | University of Illinois At Urbana–Champaign | Trustworthy LLM Systems using Formal Contracts |
| Scott Stoller | Stony Brook University | Restricter: An Automatic Tool for Authoring Amazon Cedar Access Control Policies with the Principle of Least Privilege |
| Peter Stuckey | Monash University | Huub: Next-Gen Lazy Clause Generation |
| Yulei Sui | University of New South Wales | Path-Sensitive Typestate Analysis through Sparse Abstract Execution |
| Nikos Vasilakis | Brown University | Semantics-Driven Static Analysis for the Unix/Linux Shell |
| Ping Wang | Stevens Institute of Technology | Leveraging Large Language Models for Reasoning Augmented Searching on Domain-specific NoSQL Database |
| John Wawrzynek | University of California, Berkeley | GPU-Accelerated High-Throughput SAT Sampling |
AWS AI
| Recipient | University | Research title |
| Panagiotis Adamopoulos | Emory University | Generative AI solutions for The Spillover Effect of Fraudulent Reviews on Product Recommendations |
| Vikram Adve | University of Illinois at Urbana–Champaign | Fellini: Differentiable ML Compiler for Full-Graph Optimization for LLM Models |
| Frances Arnold | California Institute of Technology | Closed-loop Generative Machine Learning for De Novo Enzyme Discovery and Optimization |
| Yonatan Bisk | Carnegie Mellon University | Useful, Safe, and Robust Multiturn Interactions with LLMs |
| Shiyu Chang | University of California, Santa Barbara | Cut the Crap: Advancing the Efficient Communication of Multi-Agent Systems via Spatial-Temporal Topology Design and KV Cache Sharing |
| Yuxin Chen | University of Pennsylvania | Provable Acceleration of Diffusion Models for Modern Generative AI |
| Tianlong Chen | University of North Carolina at Chapel Hill | Cut the Crap: Advancing the Efficient Communication of Multi-Agent Systems via Spatial-Temporal Topology Design and KV Cache Sharing |
| Mingyu Ding | University of North Carolina at Chapel Hill | Aligning Long Videos and Language as Long-Horizon World Models |
| Nikhil Garg | Cornell University | Market Design for Responsible Multi-agent LLMs |
| Jessica Hullman | Northwestern University | Human-Aligned Uncertainty Quantification in High Dimensions |
| Christopher Jermaine | Rice University | Fast, Trusted AI Using the EINSUMMABLE Compiler |
| Yunzhu Li | Columbia University | Physics-Informed Foundation Models Through Embodied Interactions |
| Pattie Maes | Massachusetts Institute of Technology | Understanding How LLM Agents Deviate from Human Choices |
| Sasa Misailovic | University of Illinois at Urbana–Champaign | Fellini: Differentiable ML Compiler for Full-Graph Optimization for LLM Models |
| Kristina Monakhova | Cornell University | Trustworthy extreme imaging for science using interpretable uncertainty quantification |
| Todd Mowry | Carnegie Mellon University | Efficient LLM Serving on Trainium via Kernel Generation |
| Min-hwan Oh | Seoul National University | Mutually Beneficial Interplay Between Selection Fairness and Context Diversity in Contextual Bandits |
| Patrick Rebeschini | University of Oxford | Optimal Regularization for LLM Alignment |
| Jose Renau | University of California, Santa Cruz | Verification Constrained Hardware Optimization using Intelligent Design Agentic Programming |
| Vilma Todri | Emory University | Generative AI solutions for The Spillover Effect of Fraudulent Reviews on Product Recommendations |
| Aravindan Vijayaraghavan | Northwestern University | Human-Aligned Uncertainty Quantification in High Dimensions |
| Wei Yang | University of Texas at Dallas | Optimizing RISC-V Compilers with RISC-LLM and Syntax Parsing |
| Huaxiu Yao | University of North Carolina at Chapel Hill | Aligning Long Videos and Language as Long-Horizon World Models |
| Amy Zhang | University of Washington | Tools for Governing AI Agent Autonomy |
| Ruqi Zhang | Purdue University | Efficient Test-time Alignment for Large Language Models and Large Multimodal Models |
| Zheng Zhang | Rutgers University-New Brunswick | AlphaQC: An AI-powered Quantum Circuit Optimizer and Denoiser |
AWS Cryptography
| Recipient | University | Research title |
| Alexandra Boldyreva | Georgia Institute of Technology | Quantifying Information Leakage in Searchable Encryption Protocols |
| Maria Eichlseder | Graz University of Technology, Austria | SALAD – Systematic Analysis of Lightweight Ascon-based Designs |
| Venkatesan Guruswami | University of California, Berkeley | Obfuscation, Proof Systems, and Secure Computation: A Research Program on Cryptography at the Simons Institute for the Theory of Computing |
| Joseph Jaeger | Georgia Institute of Technology | Analyzing Chat Encryption for Group Messaging |
| Aayush Jain | Carnegie Mellon | Large Scale Multiparty Silent Preprocessing for MPC from LPN |
| Huijia Lin | University of Washington | Large Scale Multiparty Silent Preprocessing for MPC from LPN |
| Hamed Nemati | KTH Royal Institute of Technology | Trustworthy Automatic Verification of Side-Channel Countermeasures for Binary Cryptographic Programs using the HoIBA libary |
| Karl Palmskog | KTH Royal Institute of Technology | Trustworthy Automatic Verification of Side-Channel Countermeasures for Binary Cryptographic Programs using the HoIBA libary |
| Chris Peikert | University of Michigan, Ann Arbor | Practical Third-Generation FHE and Bootstrapping |
| Dimitrios Skarlatos | Carnegie Mellon University | Scale-Out FHE LLMs on GPUs |
| Vinod Vaikuntanathan | Massachusetts Institute of Technology | Can Quantum Computers (Really) Factor? |
| Daniel Wichs | Northeastern University | Obfuscation, Proof Systems, and Secure Computation: A Research Program on Cryptography at the Simons Institute for the Theory of Computing |
| David Wu | University Of Texas At Austin | Fast Private Information Retrieval and More using Homomorphic Encryption |
Sustainability
| Recipient | University | Research title |
| Meeyoung Cha | Max Planck Institute | Forest-Blossom (Flossom): A New Framework for Sustaining Forest Biodiversity Through Outcome-Driven Remote Sensing Monitoring |
| Jingrui He | University of Illinois at Urbana–Champaign | Foundation Model Enabled Earth’s Ecosystem Monitoring |
| Pedro Lopes | University of Chicago | AI-powered Tools that Enable Engineers to Make & Re-make Sustainable Hardware |
| Cheng Yaw Low | Max Planck Institute | Forest-Blossom (Flossom): A New Framework for Sustaining Forest Biodiversity Through Outcome-Driven Remote Sensing Monitoring |
AI safety is a priority at Amazon. Our investment in safe, transparent, and responsible AI (RAI) includes collaboration with the global community and policymakers. We are members of and collaborate with organizations such as the Frontier Model Forum, the Partnership on AI, and other forums organized by government agencies such as the National Institute of Standards and Technology (NIST). Consistent with Amazon’s endorsement of the Korea Frontier AI Safety Commitments, we published our Frontier Model Safety Framework earlier this year.
During the development of the Nova Premier model, we conducted a comprehensive evaluation to assess its performance and safety. This included testing on both internal and public benchmarks and internal/automated and third-party red-teaming exercises. Once the final model was ready, we prioritized obtaining unbiased, third-party evaluations of the model’s robustness against RAI controls. In this post, we outline the key findings from these evaluations, demonstrating the strength of our testing approach and Amazon Premier’s standing as a safe model. Specifically, we cover our evaluations with two third-party evaluators: PRISM AI and ActiveFence.
Evaluation of Nova Premier against PRISM AI
PRISM Eval’s Behavior Elicitation Tool (BET) dynamically and systematically stress-tests AI models’ safety guardrails. The methodology focuses on measuring how many adversarial attempts (steps) it takes to get a model to generate harmful content across several key risk dimensions. The central metric is “steps to elicit” — the number of increasingly sophisticated prompting attempts required before a model generates an inappropriate response. A higher number of steps indicates stronger safety measures, as the model is more resistant to manipulation. The PRISM risk dimensions (inspired by the MLCommons AI Safety Benchmarks) include CBRNE weapons, violent crimes, non-violent crimes, defamation, and hate, amongst several others.
Using the BET Eval tool and its V1.0 metric, which is tailored toward non-reasoning models, we compared the recently released Nova models (Pro and Premier) to the latest models in the same class: Claude (3.5 v2 and 3.7 non-reasoning) and Llama4 Maverick, all available through Amazon Bedrock. PRISM BET conducts black-box evaluations (where model developers don’t have access to the test prompts) of models integrated with their API. The evaluation conducted with BET Eval MAX, PRISM’s most comprehensive/aggressive testing suite, revealed significant variations in safety against malicious instructions. Nova models demonstrated superior overall safety performance, with an average of 43 steps for Premier and 52 steps for Pro, compared to 37.7 for Claude 3.5 v2 and fewer than 12 steps for other models in the comparison set (namely, 9.9 for Claude3.7, 11.5 for Claude 3.7 thinking, and 6.5 for Maverick). This higher step count suggests that on average, Nova’s safety guardrails are more sophisticated and harder to circumvent through adversarial prompting. The figure below presents the number of steps per harm category evaluated through BET Eval MAX.
The PRISM evaluation provides valuable insights into the relative safety of different Amazon Bedrock models. Nova’s strong performance, particularly in hate speech and defamation resistance, represents meaningful progress in AI safety. However, the results also highlight the ongoing challenge of building truly robust safety measures into AI systems. As the field continues to evolve, frameworks like BET will play an increasingly important role in benchmarking and improving AI safety. As a part of this collaboration Nicolas Miailhe, CEO of PRISM Eval, said, “It’s incredibly rewarding for us to see Nova outperforming strong baselines using the BET Eval MAX; our aim is to build a long-term partnership toward safer-by-design models and to make BET available to various model providers.” Organizations deploying AI systems should carefully consider these safety metrics when selecting models for their applications.
Manual red teaming with ActiveFence
The AI safety & security company ActiveFence benchmarked Nova Premier on Bedrock on prompts distributed across Amazon’s eight core RAI categories. ActiveFence also evaluated Claude 3.7 (non-reasoning mode) and GPT 4.1 API on the same set. The flag rate on Nova Premier was lower than that on the other two models, indicating that Nova Premier is the safest of the three.
| Model | 3P Flag Rate [↓ is better] |
| Nova Premier | 12.0% |
| Sonnet 3.7 (non-reasoning) | 20.6% |
| GPT4.1 API | 22.4% |
“Our role is to think like an adversary but act in service of safety,” said Guy Paltieli from ActiveFence. “By conducting a blind stress test of Nova Premier under realistic threat scenarios, we helped evaluate its security posture in support of Amazon’s broader responsible-AI goals, ensuring the model could be deployed with greater confidence.”
These evaluations conducted with PRISM and ActiveFence give us confidence in the strength of our guardrails and our ability to protect our customers’ safety when they use our models. While these evaluations demonstrate strong safety performance, we recognize that AI safety is an ongoing challenge requiring continuous improvement. These assessments represent a point-in-time snapshot, and we remain committed to regular testing and enhancement of our safety measures. No AI system can guarantee perfect safety in all scenarios, which is why we maintain monitoring and response systems after deployment.
Acknowledgments: Vincent Ponzo, Elyssa Vincent
-
Funding & Business6 days agoKayak and Expedia race to build AI travel agents that turn social posts into itineraries
-
Jobs & Careers6 days ago
Mumbai-based Perplexity Alternative Has 60k+ Users Without Funding
-
Mergers & Acquisitions6 days ago
Donald Trump suggests US government review subsidies to Elon Musk’s companies
-
Funding & Business6 days ago
Rethinking Venture Capital’s Talent Pipeline
-
Jobs & Careers6 days ago
Why Agentic AI Isn’t Pure Hype (And What Skeptics Aren’t Seeing Yet)
-
Funding & Business4 days ago
Sakana AI’s TreeQuest: Deploy multi-model teams that outperform individual LLMs by 30%
-
Funding & Business7 days agoFrom chatbots to collaborators: How AI agents are reshaping enterprise work
-
Jobs & Careers6 days ago
Astrophel Aerospace Raises ₹6.84 Crore to Build Reusable Launch Vehicle
-
Jobs & Careers6 days ago
Telangana Launches TGDeX—India’s First State‑Led AI Public Infrastructure
-
Funding & Business4 days ago
HOLY SMOKES! A new, 200% faster DeepSeek R1-0528 variant appears from German lab TNG Technology Consulting GmbH
