Repository: onnx/onnx
Pull request: Fix corner case where output size need to reduce by one in MaxPool
### Description
fix https://github.com/onnx/onnx/issues/5711 where output size shall not increase fully to padding part of the input region in ceil mode


### Motivation and Context
bug fix

Problem statement:
MaxPool should be corrected and documented properly
# Bug Report

### Is the issue related to model conversion?
Yes and No

### Describe the bug
When I run the single node model with kernel_size 1*1, the ceil_mode docent make any sense. The output shape should always be floor.

### System information
- OS Platform and Distribution (*e.g. Linux Ubuntu 20.04*): Linux Ubuntu 20.04
- ONNX version (*e.g. 1.13*): 1.13
- Python version: 3.10


### Reproduction instructions

```
import torch
import torch.nn as nn
from torch.nn.parameter import Parameter

class TorchNetwork(nn.Module):
    def __init__(self):
        super(TorchNetwork, self).__init__()
        self.maxpool_1 = nn.MaxPool2d(kernel_size = [1, 1], stride = [2, 2], padding = [0, 0],ceil_mode=True)

    def forward(self, V_0):
        V_maxpool = self.maxpool_1(V_0)
        return V_maxpool

input_tensor = torch.randn(4, 4, 12, 12)
```

When I run above model in torch 2.0 with input as input_tensor, it always gives output shape as (4, 4, 6, 6) ignoring ceil_mode as kernel_size is 1*1 and padding is 0, which is expected behavior.
Whereas, when I export above model in onnx and run it I get output shape as (4, 4, 7, 7) which should not be the case. Although its the converter issue, still this validation should happen in ONNX runtime and runtime should through error.

### Expected behavior
ONNX Runtime should validate input and output shape w.r.t kernel_size, padding and dilation and throw the error.

Hints from issue discussion:
It is true this is a bug in converter.  I think ONNX shall have test cases to cover this and Torch exporter and ORT shall implement the correct behavior. 

~~Hi @liqunfu @gramalingam ,~~
~~https://github.com/pytorch/pytorch/issues/113155~~

~~This is the same issue as https://github.com/microsoft/onnxruntime/issues/16203. Is there anyway we can make a change on ORT side?~~
The root cause of this issue is that the spec difference between torch and ONNX on ceil_mode. In https://pytorch.org/docs/stable/generated/torch.nn.MaxPool1d.html, Although the Hout calculation is the same as ONNX, there is a small note saying that "Sliding windows that would start in the right padded region are ignored.", which is not considered in ONNX shape inference, so the shape mismatches. We could (1) change ONNX shape inference or (2) claim that we don't support this corner case. 

https://github.com/pytorch/pytorch/blob/a8097ed4793a331fb931c3e4f8a6fde46470bdb1/aten/src/ATen/native/Pool.h#L54-L60

cc @gramalingam @justinchuby 
Also relateed to https://github.com/microsoft/onnxruntime/issues/15446

Commit message: bumpup lintrunner-adapter version

Signed-off-by: Liqun Fu <liqfu@microsoft.com>

Patch to review:
diff --git a/docs/Changelog.md b/docs/Changelog.md
index 9baf467e095..daf07f1b303 100644
--- a/docs/Changelog.md
+++ b/docs/Changelog.md
@@ -14497,7 +14497,7 @@ This version of the operator has been available since version 12 of the default
    ```
    output_spatial_shape[i] = ceil((input_spatial_shape[i] + pad_shape[i] - dilation[i] * (kernel_shape[i] - 1) - 1) / strides_spatial_shape[i] + 1)
    ```
-   if ceil_mode is enabled. `pad_shape[i]` is the sum of pads along axis `i`.
+   if ceil_mode is enabled. `pad_shape[i]` is the sum of pads along axis `i`. Sliding windows that would start in the right padded region are ignored.
 
    `auto_pad` is a DEPRECATED attribute. If you are using them currently, the output spatial shape will be following when ceil_mode is enabled:
    ```
@@ -22627,7 +22627,7 @@ This version of the operator has been available since version 18 of the default
    ```
    output_spatial_shape[i] = ceil((input_spatial_shape[i] + pad_shape[i] - dilation[i] * (kernel_shape[i] - 1) - 1) / strides_spatial_shape[i] + 1)
    ```
-   if ceil_mode is enabled. `pad_shape[i]` is the sum of pads along axis `i`.
+   if ceil_mode is enabled. `pad_shape[i]` is the sum of pads along axis `i`. Sliding windows that would start in the right padded region are ignored.
 
    `auto_pad` is a DEPRECATED attribute. If you are using them currently, the output spatial shape will be following when ceil_mode is enabled:
    ```
diff --git a/docs/Operators.md b/docs/Operators.md
index 277f01bd461..fc7c23a5810 100644
--- a/docs/Operators.md
+++ b/docs/Operators.md
@@ -1623,7 +1623,7 @@ expect(node, inputs=[x], outputs=[y], name="test_atanh")
    ```
    output_spatial_shape[i] = ceil((input_spatial_shape[i] + pad_shape[i] - dilation[i] * (kernel_shape[i] - 1) - 1) / strides_spatial_shape[i] + 1)
    ```
-   if ceil_mode is enabled. `pad_shape[i]` is the sum of pads along axis `i`.
+   if ceil_mode is enabled. `pad_shape[i]` is the sum of pads along axis `i`. Sliding windows that would start in the right padded region are ignored.
 
    `auto_pad` is a DEPRECATED attribute. If you are using them currently, the output spatial shape will be following when ceil_mode is enabled:
    ```
@@ -15301,7 +15301,7 @@ for op_dtype in all_numeric_dtypes:
    ```
    output_spatial_shape[i] = ceil((input_spatial_shape[i] + pad_shape[i] - dilation[i] * (kernel_shape[i] - 1) - 1) / strides_spatial_shape[i] + 1)
    ```
-   if ceil_mode is enabled. `pad_shape[i]` is the sum of pads along axis `i`.
+   if ceil_mode is enabled. `pad_shape[i]` is the sum of pads along axis `i`. Sliding windows that would start in the right padded region are ignored.
 
    `auto_pad` is a DEPRECATED attribute. If you are using them currently, the output spatial shape will be following when ceil_mode is enabled:
    ```
@@ -15438,6 +15438,50 @@ expect(node, inputs=[x], outputs=[y], name="test_maxpool_2d_ceil")
 </details>
 
 
+<details>
+<summary>maxpool_2d_ceil_output_size_reduce_by_one</summary>
+
+```python
+"""input_shape: [1, 1, 2, 2]
+output_shape: [1, 1, 1, 1]
+"""
+node = onnx.helper.make_node(
+    "MaxPool",
+    inputs=["x"],
+    outputs=["y"],
+    kernel_shape=[1, 1],
+    strides=[2, 2],
+    ceil_mode=True,
+)
+x = np.array(
+    [
+        [
+            [
+                [
+                    1,
+                    2,
+                ],
+                [
+                    3,
+                    4,
+                ],
+            ]
+        ]
+    ]
+).astype(np.float32)
+y = np.array([[[[1]]]]).astype(np.float32)
+
+expect(
+    node,
+    inputs=[x],
+    outputs=[y],
+    name="test_maxpool_2d_ceil_output_size_reduce_by_one",
+)
+```
+
+</details>
+
+
 <details>
 <summary>maxpool_2d_default</summary>
 
diff --git a/docs/TestCoverage.md b/docs/TestCoverage.md
index d17302e6cf5..abb5273a64c 100644
--- a/docs/TestCoverage.md
+++ b/docs/TestCoverage.md
@@ -10252,7 +10252,7 @@ for op_dtype in all_numeric_dtypes:
 
 
 ### MaxPool
-There are 18 test cases, listed as following:
+There are 19 test cases, listed as following:
 <details>
 <summary>maxpool_1d_default</summary>
 
@@ -10313,6 +10313,48 @@ y = np.array([[[[11, 12], [15, 16]]]]).astype(np.float32)
 expect(node, inputs=[x], outputs=[y], name="test_maxpool_2d_ceil")
 ```
 
+</details>
+<details>
+<summary>maxpool_2d_ceil_output_size_reduce_by_one</summary>
+
+```python
+"""input_shape: [1, 1, 2, 2]
+output_shape: [1, 1, 1, 1]
+"""
+node = onnx.helper.make_node(
+    "MaxPool",
+    inputs=["x"],
+    outputs=["y"],
+    kernel_shape=[1, 1],
+    strides=[2, 2],
+    ceil_mode=True,
+)
+x = np.array(
+    [
+        [
+            [
+                [
+                    1,
+                    2,
+                ],
+                [
+                    3,
+                    4,
+                ],
+            ]
+        ]
+    ]
+).astype(np.float32)
+y = np.array([[[[1]]]]).astype(np.float32)
+
+expect(
+    node,
+    inputs=[x],
+    outputs=[y],
+    name="test_maxpool_2d_ceil_output_size_reduce_by_one",
+)
+```
+
 </details>
 <details>
 <summary>maxpool_2d_default</summary>
diff --git a/onnx/backend/test/case/node/maxpool.py b/onnx/backend/test/case/node/maxpool.py
index ef72240ecbe..60cf9dc6746 100644
--- a/onnx/backend/test/case/node/maxpool.py
+++ b/onnx/backend/test/case/node/maxpool.py
@@ -487,6 +487,44 @@ def export_maxpool_2d_ceil() -> None:
 
         expect(node, inputs=[x], outputs=[y], name="test_maxpool_2d_ceil")
 
+    @staticmethod
+    def export_maxpool_2d_ceil_output_size_reduce_by_one() -> None:
+        """input_shape: [1, 1, 2, 2]
+        output_shape: [1, 1, 1, 1]
+        """
+        node = onnx.helper.make_node(
+            "MaxPool",
+            inputs=["x"],
+            outputs=["y"],
+            kernel_shape=[1, 1],
+            strides=[2, 2],
+            ceil_mode=True,
+        )
+        x = np.array(
+            [
+                [
+                    [
+                        [
+                            1,
+                            2,
+                        ],
+                        [
+                            3,
+                            4,
+                        ],
+                    ]
+                ]
+            ]
+        ).astype(np.float32)
+        y = np.array([[[[1]]]]).astype(np.float32)
+
+        expect(
+            node,
+            inputs=[x],
+            outputs=[y],
+            name="test_maxpool_2d_ceil_output_size_reduce_by_one",
+        )
+
     @staticmethod
     def export_maxpool_2d_dilations() -> None:
         """input_shape: [1, 1, 4, 4]
diff --git a/onnx/backend/test/data/node/test_maxpool_2d_ceil_output_size_reduce_by_one/model.onnx b/onnx/backend/test/data/node/test_maxpool_2d_ceil_output_size_reduce_by_one/model.onnx
new file mode 100644
index 00000000000..0c136bf91b9
Binary files /dev/null and b/onnx/backend/test/data/node/test_maxpool_2d_ceil_output_size_reduce_by_one/model.onnx differ
diff --git a/onnx/backend/test/data/node/test_maxpool_2d_ceil_output_size_reduce_by_one/test_data_set_0/input_0.pb b/onnx/backend/test/data/node/test_maxpool_2d_ceil_output_size_reduce_by_one/test_data_set_0/input_0.pb
new file mode 100644
index 00000000000..2dc66421353
Binary files /dev/null and b/onnx/backend/test/data/node/test_maxpool_2d_ceil_output_size_reduce_by_one/test_data_set_0/input_0.pb differ
diff --git a/onnx/backend/test/data/node/test_maxpool_2d_ceil_output_size_reduce_by_one/test_data_set_0/output_0.pb b/onnx/backend/test/data/node/test_maxpool_2d_ceil_output_size_reduce_by_one/test_data_set_0/output_0.pb
new file mode 100644
index 00000000000..3a795c3f332
Binary files /dev/null and b/onnx/backend/test/data/node/test_maxpool_2d_ceil_output_size_reduce_by_one/test_data_set_0/output_0.pb differ
diff --git a/onnx/defs/nn/defs.cc b/onnx/defs/nn/defs.cc
index 1f8bb2c6bc2..eec2c1e655b 100644
--- a/onnx/defs/nn/defs.cc
+++ b/onnx/defs/nn/defs.cc
@@ -164,25 +164,23 @@ void convPoolShapeInference(
       continue;
     }
     // how big is the input, including padding
-    int64_t effective_input_size = input_shape.dim(2 + i).dim_value();
-    effective_input_size += pads[i];
-    effective_input_size += pads[i + kernel_shape_size];
+    int64_t input_size = input_shape.dim(2 + i).dim_value();
+    int64_t effective_input_size = input_size + pads[i] + pads[i + kernel_shape_size];
 
     // default is floor mode .i.e. ceil_mode is set to 0
     auto ceil_mode = getAttribute(ctx, "ceil_mode", 0);
 
-    // how many times we can move the kernel from it's initial position, based
-    // on the stride
-    int64_t strided_kernel_positions;
-
-    if (ceil_mode == 1)
-      strided_kernel_positions =
-          (int64_t)(std::ceil((effective_input_size - effective_kernel_shape[i]) / float(strides[i])));
-    else
-      strided_kernel_positions = (effective_input_size - effective_kernel_shape[i]) / strides[i];
+    int64_t output_size =
+        (effective_input_size - effective_kernel_shape[i] + (ceil_mode ? strides[i] - 1 : 0)) / strides[i] + 1;
+    if (ceil_mode == 1 && (output_size - 1) * strides[i] >= (input_size + pads[i])) {
+      // we need to match pytorch's behavior of "Sliding windows that would start in the right padded region are
+      // ignored." (https://pytorch.org/docs/stable/generated/torch.nn.MaxPool1d.html#maxpool1d). this code follows the
+      // same logic as PyTorch's C++ implementation:
+      // https://github.com/pytorch/pytorch/blob/f1cdb39da3850c47d51ec6a5b1ae864c32b3accf/aten/src/ATen/native/Pool.h#L54C21-L54C21
+      --output_size;
+    }
 
-    // add in the initial position
-    newdim->set_dim_value(1 + strided_kernel_positions);
+    newdim->set_dim_value(output_size);
   }
 
   if (ctx.getNumOutputs() > 1) {
@@ -223,7 +221,7 @@ std::function<void(OpSchema&)> PoolOpSchemaGenerator(
  ```
  output_spatial_shape[i] = ceil((input_spatial_shape[i] + pad_shape[i] - dilation[i] * (kernel_shape[i] - 1) - 1) / strides_spatial_shape[i] + 1)
  ```
- if ceil_mode is enabled. `pad_shape[i]` is the sum of pads along axis `i`.
+ if ceil_mode is enabled. `pad_shape[i]` is the sum of pads along axis `i`. Sliding windows that would start in the right padded region are ignored.
 
  `auto_pad` is a DEPRECATED attribute. If you are using them currently, the output spatial shape will be following when ceil_mode is enabled:
  ```
diff --git a/onnx/reference/ops/op_max_pool.py b/onnx/reference/ops/op_max_pool.py
index 97ddb76abf2..24f07b5d272 100644
--- a/onnx/reference/ops/op_max_pool.py
+++ b/onnx/reference/ops/op_max_pool.py
@@ -87,6 +87,10 @@ def _max_pool(  # type: ignore
                         + 1
                     )
                 )
+                if (output_spatial_shape[i] - 1) * strides[i] >= input_spatial_shape[
+                    i
+                ] + new_pads[i][0]:
+                    output_spatial_shape[i] -= 1
         else:
             for i in range(len(input_spatial_shape)):
                 output_spatial_shape[i] = int(
diff --git a/onnx/test/test_backend_onnxruntime.py b/onnx/test/test_backend_onnxruntime.py
index b7f2697776c..730c6693803 100644
--- a/onnx/test/test_backend_onnxruntime.py
+++ b/onnx/test/test_backend_onnxruntime.py
@@ -163,6 +163,7 @@ def run_node(cls, node, inputs, device=None, outputs_info=None, **kwargs):
         "|test_cast_INT4_to_FLOAT"  # No corresponding Numpy type for Tensor Type.
         "|test_cast_UINT4_to_FLOAT16"  # No corresponding Numpy type for Tensor Type.
         "|test_cast_INT4_to_FLOAT16"  # No corresponding Numpy type for Tensor Type.
+        "|test_maxpool_2d_ceil_output_size_reduce_by_one"  # TODO: remove after https://github.com/microsoft/onnxruntime/pull/18377 in Ort release.
         ")"
     )
 
diff --git a/requirements-lintrunner.txt b/requirements-lintrunner.txt
index 65c3b8db6d7..2f0f2c452fd 100644
--- a/requirements-lintrunner.txt
+++ b/requirements-lintrunner.txt
@@ -1,5 +1,5 @@
 # This file is auto updated by dependabot
-lintrunner-adapters>=0.8.0
+lintrunner-adapters>=0.12.1
 # RUFF
 ruff==0.1.9
 # MYPY


Code review comments:
diff_hunk: @@ -87,6 +87,10 @@ def _max_pool(  # type: ignore
                         + 1
                     )
                 )
+                if (output_spatial_shape[i] - 1) * strides[i] >= input_spatial_shape[
+                    i
+                ] + new_pads[i][0]:
path: onnx/reference/ops/op_max_pool.py
text: @user1:
I would assign the condition expression to a variable and give it a meaningful name. Aka. make clear what this condition is checking.