🤖 machine learning

Addressing Large Action Spaces in 3D Floorplanning via Spatial Generalization

This paper proposes a continuous action representation for 3D floorplanning that leverages spatial generalization through $L$ -action similarity to decouple model learning from canvas resolution, thereby overcoming scalability bottlenecks associated with large discrete action spaces.

Original authors: Fin Amin, Nirjhor Rouf, Tse-Han Pan, Sounak Dutta, Md Kamal Ibn Shafi, Paul D. Franzon

Published 2026-03-25

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Fin Amin, Nirjhor Rouf, Tse-Han Pan, Sounak Dutta, Md Kamal Ibn Shafi, Paul D. Franzon

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Problem: The "Pixelated" Puzzle

Imagine you are an architect trying to design a massive, 3D skyscraper. You have hundreds of rooms (functional blocks) that need to fit together perfectly. Your goal is to arrange them so that the hallways (wires) are short, the building doesn't overheat, and people don't get stuck in traffic (congestion).

This is exactly what engineers do when designing computer chips, but on a microscopic scale. This is called Floorplanning.

The problem is that there are so many possible ways to arrange these rooms that it's impossible to check them all. It's like trying to find the perfect arrangement of furniture in a house by trying every single inch of every wall.

The Old Way (Discrete Grid):
Previous AI methods treated the floorplan like a giant pixelated video game grid (think Minecraft or Tetris).

The AI had to pick a specific "square" on the grid to place a room.
If the grid was 100x100, the AI had to choose between 10,000 options for just one room.
The Flaw: If the AI learns that placing a room at square #5,000 is good, it doesn't automatically learn that square #5,001 is also probably good. It treats every square as a totally different, unrelated choice. This makes learning incredibly slow and inefficient, especially as the building gets bigger (3D).

The New Idea: The "Smooth" Canvas

The authors of this paper propose a smarter way called Spatial Generalization (SGF).

Instead of forcing the AI to pick a specific pixel on a grid, they let the AI think in continuous space—like a real-world map where you can place a room at any coordinate, not just on a grid line.

The Core Insight: "L-Action Similarity"
The paper relies on a simple human intuition: If a spot is good, the spots right next to it are probably also good.

Analogy: If you find a perfect spot to park your car in a lot, you don't need to test the spot 100 feet away to know it's bad. You know the spot 2 inches to the left is likely just as good.
The authors call this L-action similarity. By teaching the AI this rule, it can learn from one decision and instantly apply that knowledge to its neighbors.

How It Works: The "Dreamer" and the "Judge"

The system uses a two-part team to build the floorplan:

The Dreamer (The Actor):
- Instead of guessing a grid number, the Dreamer points to a smooth, floating coordinate in 3D space (e.g., "Put the room here, roughly at x=0.45, y=0.82").
- Because the AI learns in this smooth space, if it makes a mistake, it gets feedback that helps it understand the entire neighborhood, not just that one specific point. It learns faster.
The Judge (The Critic):
- The Dreamer's floating point isn't a legal spot on the actual chip grid. So, the system finds the 5 closest legal grid spots to that floating point.
- The Judge looks at those 5 spots and picks the one that looks most likely to result in a great building.

The Magic Trick: Learning from "Random" Mistakes

Usually, to train an AI to build a chip, you need a dataset of "perfect" floorplans made by human experts. This is expensive and hard to get.

This paper did something surprising: They trained the AI entirely on random floorplans.

They let the AI place rooms randomly, like a toddler throwing blocks on the floor.
Why it worked: Because of the "Smoothness" rule (L-action similarity), the AI could look at a random, messy layout and say, "Okay, this specific spot was bad, but the spots near it might be okay."
It learned the principles of good design (like "don't put heavy rooms near the edge") just by observing patterns in the chaos, without needing a teacher.

The Results

When they tested this new method against the old "pixelated" methods:

Better Quality: The new AI built chips with shorter wires and better layouts.
Faster Learning: It didn't need to try millions of random combinations to figure things out; it generalized from what it learned.
Scalability: Because the AI doesn't have to memorize a giant list of grid squares, it can handle much larger, more complex 3D designs without crashing.

Summary Analogy

Old Method: Like trying to learn a new city by memorizing a list of 10,000 specific street addresses. If you know address #500 is a bakery, you don't know anything about address #501.
New Method (SGF): Like learning the city by understanding the neighborhoods. If you know the "Downtown" area is busy, you know the streets near Downtown are also busy. You don't need to memorize every single street; you understand the flow.

This paper proves that by letting AI think in "smooth" space rather than "pixelated" space, we can solve massive design problems much faster and with less data.

1. Problem Statement

Floorplanning is a critical, NP-hard stage in Integrated Circuit (IC) design where functional blocks are placed to optimize power, performance, area, and thermal metrics.

The Bottleneck: Recent Machine Learning (ML) approaches, such as CircuitTraining and Chipformer, rely on discrete grid representations. The action space is defined as a classification over grid coordinates.
Scalability Issue: As the canvas resolution increases (especially in 3D), the action space grows exponentially (e.g., a $100 \times 100 \times 2$ $100 \times 100 \times 2$ canvas yields 20,000 discrete actions). This forces models to output a probability distribution over thousands of classes, leading to:
- High computational costs (large output layers).
- Poor sample efficiency (sparse reward signals).
- Lack of generalization (the model learns specific grid coordinates rather than spatial patterns).
Data Scarcity: Most RL-based methods require high-quality "expert" trajectories for pre-training, which are expensive to generate or verify.

2. Methodology: Spatial Generalization for Floorplanning (SGF)

The authors propose SGF, a framework that treats floorplanning as a Structured Large Discrete Action Space (SLDAS) problem. Instead of discretizing the canvas first, SGF learns in a continuous action space and discretizes only at inference time.

Core Concepts

L-Action Similarity: The paper formalizes the intuition that placing a module at location $x$ yields a similar reward (return) to placing it at $x + \epsilon$ . Mathematically, the action-value function $Q^\pi(s, a)$ is L-Lipschitz continuous. This means small changes in position result in bounded changes in reward.
Inductive Bias: By operating in continuous space, the model receives gradient signals not just for the chosen action, but for the surrounding spatial region. This allows the model to learn spatial patterns (smoothness) rather than memorizing specific grid cells.

Architecture

SGF adapts the Wolpertinger agent architecture but replaces standard neural networks with Decision Transformers (DT) for both the Actor and Critic.

Actor ( $\pi_\theta$ ):
- Input: State history (Grid, Netlist Graph, Difference Map) and Target Return-to-Go (RTG).
- Output: A continuous 3D coordinate $\hat{\alpha}_t \in [0, 1]^3$ representing the predicted centroid for the next module.
- k-NN Projection: The continuous output is mapped to the $k$ nearest legal discrete grid actions ( $\{ \hat{a}^{(1)}_t, \dots, \hat{a}^{(k)}_t \}$ ) using a k-Nearest Neighbor search.
Critic ( $g^\pi_\theta$ ):
- Input: The state history and the $k$ candidate discrete actions generated by the Actor.
- Output: Predicted Return-to-Go (RTG) for each candidate.
- Selection: The final action is selected as the candidate that minimizes the difference between the predicted RTG and the target RTG:
  $\tilde{a}_t = \arg \min_{a \in N_k(\hat{\alpha}_t)} |g^\pi_\theta(\gamma_t, a) - g_t|$

Training Strategy

Random Trajectory Training: Uniquely, SGF is trained entirely on random floorplan trajectories (no expert data).
Mechanism: This leverages Hindsight Experience Replay (HER) and Goal-Conditioned Supervised Learning (GCSL). The model learns to evaluate whether a random placement aligns with design objectives (wirelength, congestion, thermal) by predicting the future return. The continuous nature of the action space allows the model to generalize from these noisy, sub-optimal examples.

3. Key Contributions

Formalization of SLDAS: The paper is the first to formally define chip layout as a Structured Large Discrete Action Space, introducing L-action similarity as a mathematical constraint for floorplanning.
Continuous Action Representation: Demonstrates that decoupling the output shape from canvas resolution (via continuous coordinates + k-NN) solves the scalability bottleneck of discrete grid methods.
Learning from Randomness: Proves that a model can learn meaningful placement policies and spatial generalization without expert trajectories, relying solely on the inductive bias of spatial smoothness.
Theoretical Error Bound: Derives a bound on sub-optimality (Theorem 1), showing that the performance gap is bounded by the Lipschitz constant ( $L$ ), the distance of the continuous proposal to the optimal action, and the critic's prediction error.

4. Results

The authors evaluated SGF against Chipformer (a state-of-the-art discrete grid-based method) on standard benchmarks (ami33, ami49, n50, n100, ibm6).

Performance: SGF achieved lower Manhattan wirelength (better performance) across all benchmarks compared to Chipformer, despite Chipformer undergoing online fine-tuning while SGF used only offline training.
- Example (ami49): SGF (32,304) vs. Chipformer (37,530).
- Example (n100): SGF (16,607) vs. Chipformer (25,229).
Stability: While Chipformer's performance fluctuated or stagnated with additional online rollouts, SGF maintained consistent performance, indicating superior generalization.
Critic Accuracy: The SGF critic successfully predicted return-to-go values with decreasing error as more modules were placed, demonstrating its ability to capture structured reward trends.
Scalability: The model's output dimensionality remained fixed (3 coordinates) regardless of the canvas resolution, whereas discrete models require output units proportional to the grid size.

5. Significance and Implications

Paradigm Shift: The paper challenges the necessity of discrete grid representations in physical design automation. It suggests that spatial generalization is a more efficient inductive bias for physical placement tasks than discrete classification.
Data Efficiency: By showing that high-quality policies can emerge from random data, SGF reduces the dependency on expensive expert datasets or complex pre-training pipelines.
3D Readiness: The approach naturally extends to 3D floorplanning without the combinatorial explosion of action space size that plagues discrete methods, making it highly relevant for advanced packaging and 3D-IC design.
Theoretical Foundation: It provides a rigorous mathematical framework (L-Lipschitz continuity) for understanding why continuous representations work better for spatial optimization problems.

In conclusion, SGF demonstrates that leveraging the inherent smoothness of physical space allows reinforcement learning agents to solve complex 3D floorplanning problems more efficiently and scalably than traditional discrete approaches, even without access to expert human data.